Главная->ЕММ->Содержание->5. Транспортна задача. Метод потенціалів. Приклад 6.

5. Транспортна задача. Метод потенціалів. Приклад 6.

Знайти оптимальний план перевезення палива з трьох складів А1, А2, А3 в яких у наявності є відповідно 120, 160, 70 т. палива, передбаченого для трьох АЗС: В1, В2, В3, потреби палива складають відповідно 90, 120, 85 т. при наступній матриці витрат на перевезення 1 т. палива.

  – кількість постачань,  – кількість споживачів.

1.     Знайдемо опорний розв’язок застосовуючи метод найменшого елементу:

–       ­визначаємо якого типу задача:

запас палива:  90+120+85=295,      потреби в паливі: 120+160+70=350, отже           

дана транспортна задача відноситься до відкритого типу.

Робимо задачу закритого типу: додаємо снопчик-споживач з потребами 55 т. (різниця 350–295=55);

–       в першу чергу заповнюємо ті клітинки, де вартість перевезення найменша (по рядку);

–       перевіряємо чи отриманий план перевезень не вироджений:  ((кількість споживачів),  (кількість постачальників)) 6=6, кількості заповнених клітин – поставок (табл. 11).

Таблиця 11

План перевезення палива

		U
90	120	85	55
120	4	3 35	2 85	0	7
160	9 20	5 85	5	0 55	9
70	3 70	3	2	0	3
V	0	-4	-5	-9	350

Цільова функція F=1090.

2.     Знаходимо потенціали постачальників і споживачів.

 – потенціали постачальників;  – потенціали споживачів.

Для всіх базисних клітинок має виконуватися рівність: . Кількість таких рівнянь дорівнює числу базисних клітинок (у даній задачі 6), а кількість невідомих на одиницю більше. Саме з цієї причини прийнято фіксувати  (або ). Всі інші потенціали знаходимо «ланцюжком»:

, тобто     ,   і т.д.

Значення потенціалів  і  прийнято записувати в додатковому останньому стовпці та рядку таблиці розв’язку.

3.    Для обчислення оцінки вільних клітинок використовуємо формулу: . Теорема про оптимальний розв’язок транспортної задачі стверджує, що побудований опорний план перевезень є оптимальним, якщо для вільних клітинок усі оцінки . Перевіримо цю умову:

,        ,      ,

,     ,      .

4. Якщо є від’ємні, то обираємо найбільшу за модулем від’ємну серед оцінок вільних клітинок. Якщо ж таких оцінок декілька, то вибираємо ту клітинку, у якій вартість перевезення найменша (але не із числа фіктивних клітинок). У нашому випадку  (табл. 12).

Таблиця 12

План перевезення палива

		U
90	120	85	55
120	+  4	-  3 35	2 85	0	7
160	-  9 20	+  5 85	5	0 55	9
70	3 70	3	2	0	3
V	0	-4	-5	-9	350

 

5. Будуємо цикл перерозподілу. Цикл перерозподілу – це замкнена лінія, що складається з вертикальних і горизонтальних відрізків. Одна з вершин циклу обов’язково знаходиться у вибраній точці з найбільшим по модулю від’ємним потенціалом. Всі інші вершини – у базисних клітинках. Починаючи з вершини, що була вільною розставляємо знаки «+», «–» по порядку проходжуючи всі вершини (табл. 12). Серед постановок, що записані у вершинах зі знаком «–» вибираємо мінімальну. Саме цей об’єм палива необхідно додати до поставок у вершинах циклу зі знаком «+» і відняти у тих базисних клітинках, де стоїть «–». У нас цей об’єм 20 т. Таким чином отримано новий план, що аналогічним чином перевіряється на оптимальність (табл. 13).

Таблиця 13

План перевезення палива

		U
90	120	85	55
120	4 20	3 15	2 85	0	4
160	9	5 105	5	0 55	6
70	3 70	3	2	0	3
V	0	-1	-2	-6	350

Цільова функція F= 1030. Обчислюємо оцінки вільних клітинок:

,     ,      ,

,          ,      .

Усі оцінки  – побудований опорний план перевезень є оптимальним.

Висновок: оптимальний план перевезень: , , отже підприємство понесе витрати на перевезення палива у сумі 1030 гр.од., 55 одиниць вантажу залишилося на складі А2.

 

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Схожі підручники

• РЕАЛЬНІ ІНВЕСТИЦІЇ
• Белая книга (частина 4) (онлайн)
• Страхові послуги (частина 1)
• Сучасна математика і математична освіта
• ГРОШІ І КРЕДИТ (частина 2)
• Фінансовий Ринок остовні питання