виробництва (зберігання) у кількостях A = (а1, а2, ..., аm) одиниць, необхідно розподілити між n пунктами споживання, яким необхідно відповідно B = (b1, b2, ..., bn ) одиниць. Вартість перевезення одиниці продукту з i-го пункту відправлення в j-ий пункт призначення дорівнює C = | сij | і відома для всіх маршрутів. Необхідно скласти план перевезень, при якому запити всіх пунктів споживання були б задоволені за рахунок наявних продуктів у пунктах виробництва і загальні транспортні витрати з доставки продуктів були мінімальними. p align="justify"> матриця транспортних витрат
- вектор обсягу ресурсів
A = (24; 20; 31; 40) - вектор обсягу споживання
У нашій задачі 4 споживача і 3 постачальника, причому сумарний обсяг поставок рівний 129 перевищує сумарний обсяг споживання рівний 115. Тому для вирішення завдання ведемо додатково ще одного споживача, з споживанням рівним 14. p align="justify"> Маємо:
В
-тарифна вартість перевезення 1 одиниці вантажу;
? ij-фактична вартість перевезення 1 одиниці вантажу;
D ij-умова оптимальності;
рi-платежі за одиницю вантажу в пункті відправлення;
pj-платежі за одиницю вантажу в пункті призначення
+ qj = Cij
Для заповнених (базисних) клітин:? ij = Cij
Для порожніх: Xij = 0
опорна = 24 * 1 +6 * 2 +14 * 1 +31 * 3 +40 * 1 = 183 (загальна сума витрат)
Перевірка на оптимальність
Т.к. не всі D ij ВЈ 0 , то ми ще не знайшли оптимальне рішення.
Далі вибираємо порожню клітину таблиці з максимальною переплатою D ij Ві 0.
У ній буде вершина циклу, а інші повинні бути в зайнятих клітках. Будуємо наступну таблицю. br/>В
Отже, виконується умова оптимальності: D ij ВЈ 0, і ми отримали оптимальний план витрат.
оптим . = 24 * 1 +6 * 2 +20 * 1 +25 * 3 +40 * 1 = 171
L D = 183-171 = 12
5. Динамічне програмування. Розподіл капітальних вкладень
Динамічне програмування - це обчислювальний метод для вирішення завдань управління певної ст...
