Перевіряємо опорний план ТЗ на оптимальність за допомогою методу потенціалів

Знаходимо потенціали. Кожному рядку і зіставляємо потенціал U_i, кожному стовпцю зіставляємо потенціал V_j, i, j = 1,2,3,4. Для кожної базисної клітинки (заповненої клітинки х_ij) зіставляємо рівняння:

U_i + V_j = С_ij, i, j = 1,2,3,4. (*)

де С_ij – вартість одиниці перевезень вантажу з i в j.

Кількість невідомих U_i, V_j дорівнює m + n, а число рівнянь (*) дорівнює m + n – 1. Для розв’язку системи рівнянь (*) треба одну із невідомих задати, тоді останні знаходяться однозначно. Для довільної вільної змінної х_{ij ­}, яка не ввійшла до опорного плану, обчислюємо значення: С^’_ij­ = U_i + V_j. С^’_ij – побічна вартість, заносимо її значення в правий верхній кут вільної змінної х_ij. Якщо С^’_ij ≤ С_ij, то початкове опорне рішення оптимальне, інакше дане опорне рішення не оптимальне і його можна покращити, перейшовши до нового базису. Так роблять доти, доки не отримують оптимальне рішення

Праворуч і знизу в табл.5 заносимо потенціали. Для їх знаходження складаємо систему рівнянь відповідно до опорного плану:

U₁ + V₁ = 7, U_1­ + V_2­ = 4, U₁ + V₃ = 6, U₂ + V₃ = 6, U₃ + V₃ = 1, U₄ + V₃ = 0, U₄ + V₄ = 0.

Задаємо U₁ = 0 (один з потенціалів треба назначити довільно), знаходимо V₁=7 з першого рівняння, V₂=4 – з другого, V₃=6 – з третього і так далі отримуємо, U₂ =6, U₃= -5, U₄ = -6, V₄=6.

Обчислюємо побічні вартості С^’_ij­. Для наочності будемо заносити значення побічної вартості С^’_ij для вільної змінної х_{ij ­} в правий верхній кут і зафарбовувати в сірий колір, якщо С^’_ij ≤ С_ij, інакше – в чорний (табл.5). Нагадаємо, що для базисних змінних завжди С^’_ij = С_ij.

С^’_21­­­ = U­₂ + V­_1­ = 0+7 = 7 > 4, С^’₃₁ = U­₃ + V­_1­ = -5+7 = 2<5, С^’₄₁ = U­₄ + V­_1­ = -6+7 = 1<M (М – велике число)

С^’_22­­­ = U­₂ + V­_2­ = 0+4 = 4 > 2, С^’₃₂ = U­₃ + V­_2­ = -5+4 = -1<3, С^’₄₂ = U­₄ + V­_2­ = -6 +4= -2<0,

С^’_14­­­ = U­₁ + V­_4­ = 0+6 = 6 < 8, С^’₂₄ = U­₂ + V­_4­ = 0+6 = 6<7, С^’₃₄ = U­₃ + V­_4­ = -5+6 = 1<5,

Таблиця 5.

Запаси в пунктах відправлення a­ij

Потреби в пунктах призначення b­j

U­i

85

--

+

U­1= 0

+

--

U­2= 0

-1

U­3= -5

М

-2

U­4= -6

V­j

V­1 = 7

V­2 = 4

V­3 = 6

V­4 = 6

Оскільки не всі С^’_ij­­­­­ ≤ С_{ij­­­­­­}, то початковий опорний план не оптимальний і його можна поліпшити.

Дата добавления: 2014-10-15