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

Побудуємо початковий опорний план перевезень методом мінімального елементу матриці. Згідно з ним, відшукуємо у матриці клітинку з мінімальним значенням транспортних витрат (таблиця 6.8). Це клітинка А₁В₄. Призначаємо у ній поставку т. Зменшуємо запас постачальника А₁ та потребу споживача В₄ на 8 т.

Наступні клітинки з мінімальним значенням транспортних витрат А₂В₂ та А₄В₃. Призначаємо у клітинці А₂В₂ поставку т, зменшуємо запас постачальника А₂ та потребу споживача В₂ на 9 т; призначаємо у клітинці А₄В₃ поставку т, зменшуємо запас постачальника А₄ та потребу споживача В₃ на 9 т.

Тепер мінімальні значення транспортних витрат мають клітинки А₁В₂ , А₁В₃, А₂В₁ , А₃В₄, А₄В₁. У перші дві не можуть бути призначені поставки, оскільки запас постачальника А₁ споживачів В₂ та В₃ вже вичерпано. Призначаємо у клітинку А₂В₁ поставку т та зменшуємо запас постачальника А₂ та потребу споживача В₁ на 2 т. Призначаємо у клітинку А₃В₄ поставку т та зменшуємо запас постачальника А₃ та потребу споживача В₄ на 5 т. Призначаємо у клітинку А₄В₁ поставку т та зменшуємо запас постачальника А₄ та потребу споживача В₁ на 1 т.

Останньою призначаємо поставку у клітинку А₃В₁.

Таблиця 6.8 – Початковий опорний план перевезень

	В1	В2	В3	В4	Запас
А1	4	3	3	8 1	8; 0
А2	2 3	9 2	4	8	11; 2; 0
А3	1 6	4	6	5 3	6; 1; 0
А4	1 3	5	9 2	4	10; 1; 0
Потреба	4; 2; 1; 0	9; 0	9; 0	13; 5; 0

Кількість заповнених клітинок таблиці дорівнює 7 = 4+4–1, отже план є не виродженим. Транспортні витрати за цим планом перевезень складають ткм.

Для перевірки початкового опорного плану перевезень складемо рівняння для заповнених клітинок:

Покладемо, наприклад, , тоді з системи рівнянь однозначно можна знайти значення всіх потенціалів:

; ; ; ; ; ; .

Для кожної вільної клітинки розраховуємо оцінки

;

;

;

;

;

< 0;

;

;

.

Таким чином, план не є оптимальним, оскільки є клітинка А₃В₂ з від’ємним значенням . Для перспективної клітинки А₃В₂ будуємо цикл перерахунку А₃В₂ – А₃В₁ – А₂В₁ – А₂В₂ (показаний пунктиром у табл. 6.8). Починаючи з клітинки А₃В₂ у вершинах контуру проставляємо по черзі знаки “+” та “–“. Переглядаємо клітинки, позначені знаком “–“. Найменша поставка записана у клітинку А₃В₁. Додаємо х ₃₁ = 1 до поставок у клітинках, позначених знаком “+” та віднімаємо 1 від поставок у клітинках, позначених знаком “–“. В результаті отримаємо новий опорний план (таблиця 6.9).

Таблиця 6.9 – Оптимальний план перевезень

Перевіряємо цей план на оптимальність, для чого розраховуємо потенціали , та оцінки .

Þ Þ

Таким чином, план є оптимальним. Транспортні витрати за цим планом складають ткм.

Контрольні запитання

1. Дайте формулювання транспортної задачі у загальному вигляді.

2. Запишіть математичну постановку транспортної задачі лінійного програмування.

3. У якому випадку модель транспортної задачі називається відкритою?

4. Назвіть методи складання базисного опорного плану транспортної задачі та поясніть їх сутність.

5. Сформулюйте признак оптимальності опорного плану транспортної задачі.

6. Як розраховуються потенціали рядків та стовпчиків матриці транспортної задачі?

7. Як побудувати цикл перерахунку для покращення плану транспортної задачі та який вигляд він може мати?