Динамическое программирование

Пусть имеется начальная подпоследовательность s. Тогда вычисляются величины:

d_C(s) = С(s) + , (1)

d_B(s) = В (s) + +  min c_j , (2)

d_A(s) = A (s) +   +  (3)

где J (s) — множество символов,  образующих последовательность s.

За оценку критерия С (s) для варианта s можно принять величину

                         D(s) = max {d_A(s), d_B (s), d_C (s)}.    (4)

Тогда ход решения  задачи трех станков можно представить  следующей формальной схемой.

Нулевой шаг. Задание множества G⁽⁰⁾, образуется всеми возможными последовательностями (s = 0).

  Вычисление  оценки для множества G₀:

  где   D(0) = max {d_A(0), d_B (0), б_C (0)},

;  ;  .

Первый шаг.Образование    множеств    G₁⁽¹⁾ U G₁⁽²⁾ U... …G₁⁽ⁿ⁾.

   Подмножество  G_k определяется всеми последовательностями с началом i_k(k — 1, ...,n ).

Вычисление оценок. Оценку для последовательности s_k определяют из соотношения (4), т. е.

   D(s_k) = max {d_A(s_k), d_B (s_k), d_C (s_k)};  k = 1, n.

Выбор варианта для продолжения. Из всех подпоследовательностей, построенных на предыдущем шаге, выбирают наиболее перспективную последовательность s_k с наименьшей оценкой, т. е.

D(s_k⁽¹⁾)=min D(s_j⁽¹⁾).

Ветвление. Выбрав наиболее перспективный вариант последовательности s_k⁽¹⁾, развивают его построением всех возможных подпоследовательностей длиной 2 с началом  s_k⁽¹⁾ вида   s_k+1⁽²⁾= (s_k⁽¹⁾, j), где j не входит в s_k.

Вычисление  оценок производят в соответствии с соотношениями (1), (2), (3).

k - ш а г. Допустим, что уже проведено k шагов, в результате чего построены варианты s₁^(k), s₂^(k) ,…,s_vk^(k), а именно подпоследовательности длиной k.

Выбираем  самый перспективный вариант s_S^(k) такой, что

D(s_s^(k))=min D(s_j^(k)).

Множество G_s^(k) разбиваем на (п — k) подмножеств, каждое из которых образуется добавлением к последовательности s_s^(k) некоторого элемента i_k+1 такого, что i_k+1 .

Оценка  определяется в соответствии с соотношениями (1) — (4).

В результате строим дерево вариантов следующего вида: вершина О отвечает s = 0, вершины первого уровня G₁⁽¹⁾, G₂⁽¹⁾..., G_n⁽¹⁾ соответствуют последовательностям длиной 1, т. е. s₁⁽¹⁾ = 1, s₂⁽¹⁾ = 2,..., s_n⁽¹⁾ = п и т. д. Каждая конечная вершина отвечает последовательности максимальной длины п.

Признак оптимальности. Если s_v⁽ⁿ⁾  отвечает конечной вершине дерева, причем оценка наименьшая из оценок всех вершин, то s_v⁽ⁿ⁾ — искомый вариант, иначе переходим к продолжению варианта с наименьшей оценкой.

Пример 6. Рассмотрим задачу .трех станков, условия которой  приведены в табл. 1: 
 

Таблица 1

    Нулевой шаг. s = 0.

    d_A(s = 0) = A(0) +

  +   = 0 + 14 + 3 = 17;

    d_B(s = 0) = В(0) +

+  min c_j = 0 + 15 + 2 = 17;

d_C(s = 0) = С(0) +

=14 . 

Тогда

∆ (s = 0) = max {17, 17,14} = 17.

Первый шаг. Конструируем все возможные последовательности длиной 1

s₁⁽¹⁾  = 1;  s₂⁽¹⁾ = 2;   s₃⁽¹⁾ = 3;   s₄⁽¹⁾ = 4;   s₅⁽¹⁾ = 5.

Находим

    d_A⁽¹⁾  = A₁  +

  +   = 14 + 3 = 17;

    d_B⁽¹⁾(s = 0) = В₁ +

+   = 5 + 12 + 2 = 19;

d_C⁽¹⁾ = С₁ +

= 9 + 10 = 19 .

Откуда ∆ (1) = max {17, 19, 19} = 19.

Аналогично определяем ∆ (2), ∆ (3), ∆ (4), ∆ (5).

Второй  шаг. Среди множества подпоследовательностей длиной 1, s₁⁽¹⁾ = 1, s₂⁽¹⁾ = 2,..., s₅⁽¹⁾  = 5  выбираем наиболее перспективную s = 1, для которой величина оценки-прогноза ∆ (s) оказывается наименьшей. Далее развиваем ее, конструируя возможные варианты длиной 2, т. е. (1.2), (1.3), (1.4), (1.5).

Для каждого  из этих вариантов вновь определяем оценки по формулам (1) — (4).

Процесс вычислений продолжаем аналогично.

Процесс построения дерева вариантов приведен на рис. 1.

Каждой  конечной вершине дерева вариантов  будет отвечать полная последовательность s = i₁,i_2,,.i_n. Если для некоторой такой вершины величина оценки ∆ (s) не превосходит величины оценок для всех остальных вершин, то эта оценка определяет искомый оптимальный вариант. В противном случае разбиваем более перспективный вариант с наилучшей оценкой.

Конечная  вершина определяет вариант (последовательность) = 3, 1, 5, 2, 4  с наилучшей оценкой ∆ = 20. Поэтому данный вариант является оптимальным.

Непосредственной  проверкой убеждаемся, что время  обработки всей последовательности деталей для этого варианта совпадает со значением оценки-прогноза и является минимальным:

 
 
 
 
 
 
 
 
 
 
 
 
 
 

     ЗАКЛЮЧЕНИЕ 

     При написании курсовой работы, передо мной стояла цель – выявить наилучший  способ решения задач динамического программирования. В первой части курсовой работы, мною был изучен смысл динамического программирования и выявлено, что метод динамического программирования можно использовать для решения весьма широкого круга задач и какими принципами следует руководствоваться при постановке задач динамического программирования. Было определено, что динамическое программирование позволяет осуществлять оптимальное планирование управляемых процессов, сформулирован общий принцип, лежащий в основе решения всех задач динамического программирования, отмечена структура динамического программирования.

     Во  второй части курсовой работы мной была изучена основная идея и особенности  вычислительного метода динамического  программирования. А также подробно рассмотрена общая постановка, алгоритм решения задач методом динамического программирования , приведены примеры решения задач методом динамического программирования.

     Динамическое  программирование хорошо приспособлено  для решения задач оптимизации  многостадийных процессов, особенно тех, в которых состояние каждой стадии характеризуется относительно небольшим числом переменных состояния. Однако при наличии значительного числа этих переменных, т. е. при высокой размерности каждой стадии, применение метода динамического программирования затруднительно вследствие ограниченных быстродействия и объема памяти вычислительных машин.

     Именно  благодаря данной программе можно  облегчить труд человека, решающего  задачи методом динамического программирования. 
 
 

Библиографический список

1. Таха Х. Введение в исследование операций.–М.: Мир,2004.
2. Кузнецов Ю. Н. Математическое программирование. –М.: Наука,1976.
3. Вентцель Е. С. Исследование операций. –М.: Наука,1976.
4. Вентцель Е. С. Элементы динамического программирования. –М.: Наука,1987.
5. Акоф Р., Сасиени М. Основы исследования операций. –М.: Мир,1971.
6. Вентцель Е. С. Исследование операций: задачи, принципы, методология. –М.: Наука,2001.
7. Карманов В. Т. Математическое программирование. –М.:Наука,1986.
8. Зайченко Ю. П. Исследование операций. –К.: Высшая школа,1985.
9. Аоки М. Введение в методы оптимизации. –М.: Наука,1997.
10. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. –М.: Наука,2007.