9.10. Задания для самостоятельной работы
Работа заключается в решении одной оптимизационной задачи методом динамического программирования. Содержание задачи по вариантам и соответствующие исходные данные приводятся ниже.
Указания. Целесообразно придерживаться следующего порядка решения задачи:
1. Составить модель задачи.
2. Представить задачу как многошаговую: выделить и пронумеровать шаги. Эта нумерация должна сохраниться до конца решения.
3. Определить параметры состояния.
9. Составить уравнение состояния.
5. Ввести последовательность функций, четко определив их смысл и математическое представление.
6. Записать первую функцию последовательности и вывести рекуррентное соотношение с указанием переменных и области их изменения, по которым определяется экстремум в соотношении.
7. Провести условную оптимизацию. При решении функциональных уравнений там, где возможно, следует использовать отыскание оптимума в общем виде (классическим методом). Существенное значение имеет обоснованный выбор диапазона значений параметров состояния и шага дискретизации.
8. Используя результаты условной оптимизации, провести безусловную оптимизацию для всех заданных значений исходного состояния.
9. Выписать оптимальное решение и все соответствующие ему показатели, сделать выводы по результатам решения.
10. Осмыслить полученные результаты.
В некоторых вариантах используется процедура снижения размерности. Для них перечисленные действия недостаточны, так как может быть необходим еще один этап оптимизации, а условная и безусловная оптимизации могут повторяться несколько раз. Однако в целом схема решения аналогична.
В большинстве вариантов один из параметров задан в диапазоне, например 50-60. Это означает, что нужно найти решения для значений этого параметра от 50 до 60.
При решении задачи методом динамического программирования совершенно естественно применение компьютера, особенно в вариантах с большим объемом вычислений.
При использовании компьютера следует приводить укрупненную блок-схему алгоритма, текст программы с краткими комментариями, оформленные в таблицы конечные результаты расчета по шагам (или полные результаты, включая промежуточные при поиске экстремума).
При представлении конечных результатов необходимо также привести значения критерия на каждом шаге для возможных значений переменных. (Например, при распределении ресурса Х по трем предприятиям это доходы r1(x1), r2(x2) и r3(x3)).
Безусловная оптимизация проводится вручную с соответствующими пояснениями действий.
Варианты 1.1 - 1.3
В каждый месяц
планового периода известен спрос на
машины Dt(t=1,..,T),
которые выпускает предприятие. Запас
машин на складе предприятия составляет
единиц на
начало периода планирования. Общие
затраты предприятия складываются из
затрат на производство машин С(Х)
и затрат на их содержание на складе.
Пусть затраты на производство одной машины определяются выражением
С(х)=С0-С1Х2,
а затраты на хранение одной машины в течение месяца равны h. Месячное производство машин ограничено величиной В, а на складе можно хранить не более М машин. Отправка потребителю производится в конце месяца, а выпуск машин - равномерно в течение каждого месяца.
Требуется определить оптимальный план выпуска машин, а также вычислить максимальные потери от неоптимальности.
Значения параметров по вариантам даны в табл. 1.
Таблица 1
|
Вариант |
D1 |
D2 |
D3 |
D4 |
D5 |
C0 |
C1 |
h |
B |
M |
i0 |
|
1.1 |
7 |
5 |
6 |
4 |
7 |
12 |
0,04 |
2 |
10 |
12 |
0-8 |
|
1.2 |
10 |
13 |
12 |
11 |
8 |
10 |
0,03 |
1 |
15 |
18 |
5-8 |
|
1.3 |
11 |
14 |
15 |
15 |
13 |
20 |
0,07 |
3 |
16 |
18 |
2-12 |