Методические указания к выполнению задания. Рассмотрим применение метода динамического программирования на примере распределения грузов между 4-мя торговыми суднами

Рассмотрим применение метода динамического программирования на примере распределения грузов между 4-мя торговыми суднами. Пусть общая вместимость торговых суден составляет не более 500 тонн. На основе технико-экономических расчетов установлено стоимость перевозки каждым судном определенного количества груза, которая приведена в таблице 1. Необходимо определить оптимальное распределение грузов между суднами, обеспечивающее минимизацию затрат предприятий. Таким образом, в этой оптимизационной задаче используется критерий – суммарная стоимость загрузки.

Таблица 1.

Пусть х1, х2, х3, х4 ¾ вместимость соответственно первого, второго, третьего и четвертого судна, 0£ хi £5, i = 1,4. Обозначим f1(x), f2(x), f3(x), f4(x) ¾ функции изменения стоимости перевозки первого, второго, третьего и четвертого предприятия при из загрузке х тыс.тонн. Этим функциям соответствуют строки 1, 2, 3, 4 в табл.1.

Определим минимум функции цели

F (х₁, х₂, х₃, х₄) = f₁(x) + f₂(x) + f₃(x) + f₄(x) àmin.

При этом на объемы загрузки х₁, х₂, х₃, х₄ наложены ограничения

х₁ + х₂ + х₃ + х₄ = А,

тыс.тонн.

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

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

Выделим в нашей задаче 3 шага:

¾ А тыс. тонн загружаются в первое, второе судно одновременно;

¾ А тыс. тонн загружаются в первое, второе, третье судно вместе;

¾ А млн. тонн. загружаются в четыре судна одновременно.

Обозначим: F1,2 (А), F1,2,3 (А), F1,2,3,4 (А) ¾ соответственно оптимальные распределения грузов для первого, второго и третьего шагов.

Алгоритм метода динамического программирования состоит из двух этапов. На первом этапе выполняется условная оптимизация, заключающаяся в том, что для каждого из трех шагов находят условный оптимальный выигрыш F1,2 (А), F1,2,3 (А), F1,2,3,4 (А). На втором этапе выполняется безусловная оптимизация. Используя результаты первого этапа, находят величины загрузки торговых суден х1, х2, х3, х4, обеспечивающие минимальную стоимость перевозки.

Первый этап включает следующие шаги:

1) Вычисление максимума критерия оптимизации для различных значений по объемам загрузки х = 0, 100, 200, 300, 400, 500, которые используются только для суден 1 и 2. Расчет ведется по формуле

F_1,2 (А) = min [ f₁(x) + f₂ (A - x) ];

0 £ x £ 500;

0 £ A £ 500.

Результаты расчета представлены в табл.2.

Таблица2.

Например, для того, чтобы определить F_1,2 (2), надо вычислить

f₁(2) + f₂ (0) = 550 + 4000 = 4550;

f₁(1) + f₂ (1) = 500 + 4200 = 4700;

f₁(0) + f₂ (2) = 400 + 4300 = 4700.

Наименьшее из полученных значений будет 4400. Остальные F1,2 (х) получаются как наименьшее значение каждой диагонали в таблице (эти значения в таблице подчеркнуты:

F₂ (0) = min (4400) = 4400;

F₂ (1) = min (4500, 4600) = 4500;

F₂ (2) = min (4550, 4700, 4700) = 4550;

F₂ (3) = min (4700, 4750, 4800, 4900) =4700;

F₂ (4) = min (4750, 4900, 4850, 5000, 5000) =4750;

F₂ (5) = min (5000, 4950, 5000, 5050, 5100)=4950.

2) Вычисление минимума критерия оптимизации для различных значений по объемам загрузки х = 0, 100, 200, 300, 400, 500, которые используются только для торговых суден 1,2 и 3.

Расчет ведется по формуле

F_1,2,3 (А) = min [ F_1,2(A) + f₃ (A - x) ];

0 £ x £ 500;

0 £ A £ 500.

Результаты расчетов занесем в табл.3, которая аналогична табл.2, только вместо f1(x) в ней указаны значения F₂ (А), а f₂ (A - x) заменена на f₃ (A - x).

Таблица3.

Значения F_1,2,3 (A) будут следующими:

F_1,2,3 (0) = 4400; F_1,2,3 (1) = 4500; F_1,2,3 (2) = 4550;

F_1,2,3 (3) = 4650; F_1,2,3 (4) = 4750; F_1,2,3 (5) = 4850.

3) Вычисление минимума критерия оптимизации по объемам загрузки х = 0, 100, 200, 300, 400, 500, которые используются для всех торговых суден.

Расчет ведется по формуле

F_1,2,3,4 (А) = min [ F_1,2,3(A) + f₄ (A - x) ];

0 £ x £ 500;

0 £ A £ 500.

Результаты расчетов заносим в табл.4.

Таблица4.

Значения F_1,2,3,4 (А) в результате расчета будут следующими:

F_1,2,3,4 (0) = 5000; F_1,2,3,4 (1) = 5100;

F_1,2,3,4 (2) = 5150; F_1,2,3,4 (3) = 5250;

F_1,2,3,4 (4) = 5350; F_1,2,3,4 (5) = 5450.

На этом первый этап решения задачи динамического программирования заканчивается.

Перейдем ко второму этапу решения задачи динамического программирования ¾ безусловной оптимизации. На этом этапе используются табл.4,3,2. Определим оптимальные объемы загрузки суден для А = 0, 100, 200, 300, 400, 500. Для этого выполним следующие расчеты.

1) Пусть объем загрузки всех суден составляет А = 500 тис. тонн.

Определим объем загрузки четвертого судна. Для этого используем табл. 4. Выберем на ней диагональ, соответствующую А = 500 ¾ это значения 5450, 5500, 5550, 5500, 5600, 5600. Из этих чисел возьмем минимальное F_1,2,3,4 (5) = 5450 тыс. грн. Отмечаем столбец, в котором стоит эта величина. Далее определяем в отмеченном столбце объем загрузки четвертого судна х₄ = 0.

На загрузку первого, второго и третьего судна остается

А = 500 - х₄ = 500 тыс. тонн.

2) Определим объем, выделенный на загрузку третьего судна.

Для этого используем табл.3. Выберем в этой таблице диагональ, соответствующую А = 500 ¾ это значения 4950, 4850, 5100, 5350, 5350, 5300. Отмечаем столбец, в котором стоит минимальная величина стоимости F_1,2,3 (4) = 4850 тыс. грн. Определяем значение х₄ = 100 тыс. тон. в отмеченном столбце.

3) На загрузку первого и второго судна остается сумма

А = 5 - х₄ - х₃ =400 тыс. тонн.

Определим объем загрузки второго судна. Используем для этого табл.2. Выберем в таблице диагональ, соответствующую А = 400 ¾ это значения 4750, 4900, 4850, 5000, 5000. Отмечаем столбец с минимальной величиной стоимости F_1,2 (1) = 4750 тыс. грн. Тогда в этом столбце х₂ =0 тыс. тонн.

4) Определим объем загрузки первого судна. А=500-100=400 тыс. тонн.

Таким образом, для объема груза в А = 500 тыс. тонн. оптимальным является загрузка первого судна на 400 тыс. тон, а третьего на 100 тыс. тон. Загружать второе и четвертое судно экономически не выгодно. При этом суммарная стоимость загрузки 750+100=850 тыс. т.