Базисний план транспортного завдання

Постачальники (потужність)	Споживачі (потреба)	Коефіцієнт рядка
1 (800)	2 (1400)	3 (1300)
А (1500)
				-
Б (800)
-
В (1200)							-1
-		-
Коефіцієнти стовпчиків

Порядок розрахунку коефіцієнтів базисного плану (табл. 11.5.):

К_стр.₁ =1,

К_ст.1 = С₁₁ – К_{стр. 1}=4-1=3,

К_ст.2 = С₁₂ – К_{стр. 1}=2-1=1,

К_стр.2 = С₂₂ – К_{ст. 2}=3-1=2,

К_ст.3 = С₂₃ – К_{стр. 2}=5-2=3,

К_стр.3 = С₃₃ – К_{ст. 3}=2-3=-1,

Значення коефіцієнтів рядків та стовпчиків заносимо у табл. 11.5.

Значення цільової функції (вартості перевезень) плану, що визначений в табл. 11.5:

Z= 800 · 4 + 700 · 2 +700 · 3 + 100 · 5 + 1200 · 2 = 9600.

Складений план вважається оптимальним, коли для незаповнених клітинок досягається умова:

(11.2)

де С_пij, - вартісна оцінка незаповненої клітинки.

Отже, перевірка умови оптимальності для плану (табл. 11.5):

А₃: 3-(1+3) = -1;

Б₁: 1 - (2+3) = -4;

В₁: 7-(3-1) =5;

В₂: 6-(1-1) = 6;

Оскільки умова оптимальності не зберігається для клітинок А₃ та Б₁ план вважається неоптимальним і потребує поліпшення. З цією метою будується додатковий план розподілу вантажів за такими правилами:

- в одній із вершин плану фіксується значення незамовленої клітинки, для якої в більшості не витримана умова оптимальності, тобто це клітинка Бь

- в інші вершини додаткового плану складають заповнені клітинки;

- додатковий план формується переміщенням порожньої клітинки по рядках та стовпчиках до тих пір, поки не буде знайдена перша заповнена клітинка;

- додатковий план повинен уявляти щонайменше чотирикутник або геометричну фігуру, кожен кут якої є прямим кутом.

З використанням цих правил побудови додаткового плану для плану табл. 11.5, додатковий план має такий вигляд:

Таблиця 11.6.

Дата добавления: 2014-11-06