Исходные данные для примера

Выбор состава оборудования для технологической линии.

Есть технологическая линия, то есть цепочка, последовательность операций.

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

i
j

Стоимость сырья

Расходы, связанные с использованием единицы оборудования j-го типа на i-ой операцииПроизводительности, соответственно, по выходу и входу и для j-го типа оборудования, претендующего на i-ую операцию.

Решение:

Для того, чтобы решить данную задачу методом динамического программирования введем следующие обозначения:

N = 3 – число шагов.

- Технологическая линия.

= (0,0,0)

= ()

– выбор оборудования для i-ой операции.

U_i – область допустимых УВ на i-м шаге.

т.е.

W_i – оценка минимальной себестоимости, полученная в результате реализации i-го шага.

S – функция общего выигрыша т. е. минимальная себестоимость.

вектор – функция, описывающая переход системы из состояния в состояние под действием УВ.

- вектор УВ на i-ом шаге, обеспечивающий переход системы из состояния x_i-1 в состояние x_i, т.е. оптимальный выбор оборудования за N шагов.

S_i+1() – максимальный выигрыш (в нашем случае минимальная себестоимость), получаемый при переходе из любого состояния в конечное состояние при оптимальной стратегии управления начиная с (k+1)-го шага.

S₁() – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния в конечное при реализации оптимальной стратегии управления . Очевидно, что S = S₁(), если = 0.

Запишем вектора допустимых значений

Запишем вектора допустимых управляющих воздействий

Запишем вектор – функцию, описывающую переход системы из состояния состояние под действием УВ.

Запишем основное функциональное уравнение

1) Обратный проход

Для i=3

Учитывая то, что этот шаг у нас последний и следующей операции

уже не будет, а также то, что мы на обратном проходе, вместо функции

возьмем стоимость сырья

при =

при =

т. е.

Для i=2

		115,2

при =

		138,04

при =

	102,8

при =

		123,1

при =

т. е.

Для i=1

			140,2

при =

		125,3

при =

125,3

при =

		125,3

при ==

		125,3

при =

		125,3

при =

		125,3

при =

т. е.

2)

Прямой проход

Учитывая то, что и = (0,0,0) имеем

i=1

i=2

i=3

Таким образом оптимальный выбор состава оборудования технологической линии предполагает следующее:

На 1-ую операцию назначим оборудование 2-го вида

На 2-ую операцию назначим оборудование 1-го вида

На 3-ью операцию назначим оборудование 2-го вида

Оценка минимальной себестоимости составит 105,5.

Тема 2. Задача инвестирования.

Предположим, что в начале каждого из следующих n лет необходимо сделать инвестиции P1, P2,…, Pn соответственно. Вы имеете возможность вложить капитал в два банка: первый банк выплачивает годовой сложный процент r1, а второй - r2. Для поощрения депозитов оба банка выплачивают новым инвесторам премии в виде процента от вложенной суммы.

Премиальные меняются от года к году, и для і-ого года равны qi1 и qi2 в первом и втором банках соответственно. Они выплачиваются к концу года, на протяжении которого сделан вклад, и могут быть инвестированы в один из двух банков на следующий год. Это значит, что лишь указанные проценты и новые деньги могут быть инвестированы в один из двух банков. Размещенный в банке вклад должен находится там до конца рассматриваемого периода. Необходимо разработать стратегию инвестиции на следующие n лет.

Элементы модели динамического программирования следующие:

Этап і представляется порядковым номером года і, і=1,2,...n

Вариантами решения на і-м этапе (для і-ого года) являются суммы li и инвестиций в первый и второй банк соответственно.

Состоянием xi на і-м этапе является сумма денег на начало і-ого года, которые могут быть инвестированы.

Заметим, что по определению =xi-li. Следовательно,

где і=2,3,…n, x1=P1. Сумма денег xi, которые могут быть инвестированы, включает лишь новые деньги и премиальные проценты за инвестиции, сделанные на протяжении (і-1)-го года.

Пусть fi(xi)- оптимальная сумма инвестиций для интервала от і-го до n-го года при условии, что в начале і-го года имеется денежная сумма xi. Далее обозначим через si накопленную сумму к концу n-го года при условии, что li и (xi-li)-объемы инвестиций на протяжении і-го года в первый и второй банк соответственно. Обозначая , і=1,2, мы можем сформулировать задачу в следующем виде.

Максимизировать z=s1+s2+…+sn, где

Так как премиальные за n-й год являются частью накопленной денежной суммы от инвестиций, в выражения для sn добавлены qn1 и qn2.

Итак, в данном случае рекуррентное уравнение для обратной прогонки в алгоритме динамического программирования имеет вид

где xi+1 выражается через xi в соответствии с приведенной выше формулой, а fn+1(xn+1)=0.

Дата добавления: 2014-01-15