Практический блок

Пример 1

Для двух предприятий выделено a единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f₁(x), а доход от y единиц средств, вложенных во второе предприятие, равен f₂(y). Остаток средств к концу года составляет g₁(x) для первого предприятия и g₂(y) для второго предприятия.

a=1000, f₁=3х, g₁=0,1х; f₂=2у; g₂= 0,5y.

РЕШЕНИЕ. Процесс распределения средств разобьем на 4 этапа – по соответствующим годам.

Обозначим a_k = x_k + y_k – средства, которые распределяются на k –ом шаге как сумма средств по предприятиям.

Суммарный доход от обоих предприятий на k –ом шаге:

z_k = f₁(x_k) + f₂(a_k − x_k) = 3x_k + 2(a_k − x_k) = 2a_k + x_k .

Остаток средств от обоих предприятий на k –ом шаге:

a_k+1 =g₁(x_k)+ g₂(a_k –x_k) =0,1x_k +0,5(a_k –x_k) =0,5a_k –0,4x_{k .}

Обозначим z*_k (a_k) – максимальный доход, полученный от распределения средств a_k между двумя предприятиями с k-го шага до конца рассматриваемого периода.

Рекуррентные соотношения Беллмана для этих функций

z*₄(a₄)= a₄+ x₄},

z*_k(a_k)= a_k + x_k + z*_k+1(0,5a_k – 0,4x_k)}.

Проведем оптимизацию, начиная с четвертого шага:

Й шаг.

Оптимальный доход равен:

z*₄(a₄ )= a₄+ x₄}= 3a₄ ,

т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при x₄= a₄.

Й шаг.

z*₃(a₃)= a₃+ x₃ + 3(0,5a₃– 0,4x₃)}= a₃– 0,2x₃)}= a₃

т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при x₃= 0.

Й шаг.

z*₂(a₂)= a₂+ x₂ + 3.5(0,5a₂– 0,4x₂)}= a₂– 0,4x₂)}= a_{2 ,}

т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при x₂=0.

Й шаг.

z*₁(a₁)= a₁+ x₁+ 3.75(0,5a₁– 0,4x₁)}= a₁– 0,5x₁)}= a_1,

т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при x₁=0.

Результаты оптимизации:

z*₁(a₁)= 3,875a₁, x*₁ =0,

z*₂(a₁)= 3,75a₂, x*₂ =0,

z*₃(a₃)= 3,5a₃, x*₃ =0,

z*₄(a₄)= 3a₄, x*₄ = a_4.

Определим количественное распределение средств по годам:

Т.к. a₁=a=1000, x*₁=0, получаем a₂=0.5a₁– 0.41x*₁=500. Далее аналогично:

x*₂=0, a₃= 0.5a₂–0.4 x*₂=250,

x*₃=0, a₄= 0.5a₃−0.4 x*₃=125,

x*₄= a₄=125.

Представим распределение средств в виде таблицы:

При таком распределении средств за 4 года будет получен доход, равный

z*₁(a₁)= 3,875 ·1000= 3875 .

Пример 2

Строительный подрядчик оценивает минимальные потребности в рабочей силе на каждую из последующих пяти недель следующим образом, 6, 5, 3, 6, 8 рабочих соответственно. Содержание избытка рабочей силы обходится подрядчику в 300 долларов за одного рабочего в неделю. А наем рабочей силы на протяжении одной недели обходится 400 долларов плюс 200 долларов за одного рабочего в неделю. Каждому уволенному рабочему выплачивается выходное пособие в размере 100 долларов. Найти оптимальное решение задачи.

Решение.

1. Этап i представляется порядковым номером недели, i =1, 2, 3, 4, 5.

2. Вариантом решения на i-том этапе являются значения –количество работающих на протяжении i-той недели.

3. Состояние на i-том этапе является – количество работающих на протяжении (i-1)-й неделе.

Рекуррентное уравнение динамического программирования представляется в виде:

– затраты, связанные с содержанием избытка;

– затраты, связанные с наймом;

– затраты, связанные с увольнением.

,

,

,

,

.

Проведем оптимизацию, начиная с пятого этапа:

Этап 5.

Оптимальное решение
	300*0+400+200*2+100*(-2)= 600
	300*0+400+200*1+100*(-1)= 500
	300*0+400+200*0+100*0= 400

Этап 4.

+ Оптимальное решение
	= 6	= 7	= 8

Этап 3.

+ Оптимальное решение

Этап 2.

+ Оптимальное решение

	= 5
	300*0+400+200*(-1)+100+1500=1800
	300*0+400+200*(-2)+200+1500=1700
	300*0+400+200*(-3)+300+1500=1600

Этап 1.

+ Оптимальное решение

	= 6	= 7	= 8

Оптимальное решение определятся последовательно таким образом:

Вывод: в результате решения задачи получилось, что на первой неделе надо нанять 6 человек, на второй уволить 1 рабочего, на третьей уволить 2 рабочих, на четвертой нанять троих рабочих и на пятой нанять двоих рабочих.

Пример 3

Компания по прокату автомобилей разрабатывает план по обновлению парка своих машин на следующие пять лет. Каждый автомобиль должен проработать не менее 2-х и не более 4-х лет. В следующей таблице приведена стоимость замены автомобиля в зависимости от года покупки и срока эксплуатации.

Решение

Сведем задачу к задаче нахождения кратчайшего пути в сети:

Получаем кратчайший путь 2000→2002→2005.

К наименьшим затратам приведет замена автомобиля в 2002 и 2005 годах.

Тесты

1. Какую особенность имеет динамическое программирование как многошаговый метод оптимизации управления:

а) отсутствие последействия;

б) наличие обратной связи;

в) управление зависит от бесконечного числа переменных.

2. Вычислительная схема метода динамического программирования:

а) зависит от способов задания функций;

б) зависит от способов задания ограничений;

в) связана с принципом оптимальности Беллмана.

3. Какую задачу можно решить методом динамического программирования:

а) транспортную задачу;

б) задачу о замене оборудования;

в) принятия решения в конфликтной ситуации.

4. Что из себя представляет динамическое программирование?

а) особый метод оптимизации решений, специально приспособленный к так называемым “одношаговым” (или “одноэтапным”) операциям;

б) особый метод оптимизации решений, специально приспособленный к так называемым “многошаговым” (или “многоэтапным”) операциям;

в) особый метод оптимизации состава предприятия;

г) особый метод оптимизации решений, специально приспособленный к задачам линейного программирования;

д) все вышеперечисленное.

5. Что предполагает принцип динамического программирования?

а) что каждый шаг оптимизируется отдельно, независимо от других;

б) шаговое управление должно выбираться дальновидно, с учетом всех его последствий в будущем;

в) выбор на данном шаге управления, при котором эффективность этого шага максимальна;

г) выбор на данном шаге управления, при котором эффективность этого шага минимальна;

д) все вышеперечисленное.

6. К какой задаче относится задача распределение средств по предприятиям и по годам?

а) задачи линейного программирования;

б) задачи целочисленного программирования;

в) задачи нелинейного программирования;

г) задачи стохастического программирования;

д) задачи динамического программирования.

7. К какой задаче относится задача прокладки наивыгоднейшего пути между двумя пунктами?

а) задачи линейного программирования;

б) задачи целочисленного программирования;

в) задачи нелинейного программирования;

г) задачи стохастического программирования;

д) задачи динамического программирования.

8. Каким методом лучше всего решить экономическую задачу о распределении ресурсов?

а) методом линейного программирования;

б) методом динамического программирования;

в) методом целочисленного программирования;

г) методом нелинейного программирования;

д) методом стохастического программирования.

9. В чем метод динамического программирования отличается от метода линейного программирования?

а) не сводится к какой-либо стандартной вычислительной процедуре;

б) оно может быть передано на машину только после того, как записаны соответствующие формулы, а это часто бывает не так-то легко;

в) сводится к какой-либо стандартной вычислительной процедуре;

г) содержание п. а и б;

д) содержание п. а, б и в.

10. Что необходимо делать, когда планировать операцию приходится не на строго определенный, а на неопределенно долгий промежуток времени?

а) необходимо рассмотреть в качестве модели явления бесконечношаговый управляемый процесс, где не существует “особенного” по сравнению с другими последнего шага (все шаги равноправны);

б) для этого, разумеется, нужно, чтобы функции выигрыша и функции изменения состояния не зависели от номера шага;

в) необходимо рассмотреть в качестве модели явления одношаговый управляемый процесс;

г) необходимо рассмотреть в качестве модели явления бесконечношаговый неуправляемый процесс;

д) содержание п.а и б.

Ответы к тестам

Контрольные вопросы

1. Как поставить общую задачу динамического программирования?

2. Как формулируется задача динамического программирования и в чем ее отличие от задач линейного программирования?

3. В чем заключается особенности математической модели ДП?

4. Что лежит в основе метода ДП?

5. Сформулируйте задачу определения кратчайших расстояний по заданной сети. На сколько этапов разбивается задача? Сколько шагов содержится в каждом этапе и в чем суть этапа и шага?

6. Что является переменной управления и переменной состояния в задаче выбора оптимальной стратегии обновления оборудования?

7. Запишите функциональные уравнения Беллмана, используемые на каждом шаге управления в задаче выбора оптимальной стратегии обновления оборудования.

8. Запишите математическую модель оптимального распределения инвестиций и рекуррентное соотношение Беллмана для ее реализации.

9. Что такое принцип оптимальности и как записываются уравнения Беллмана?