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

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

Ui + Vj = Сij, i, j = 1,2,3,4. (*)

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

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

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

U1 + V1 = 7, U1­ + V2­ = 4, U1 + V3 = 6, U2 + V3 = 6, U3 + V3 = 1, U4 + V3 = 0, U4 + V4 = 0.

Задаємо U1 = 0 (один з потенціалів треба назначити довільно), знаходимо V1=7 з першого рівняння, V2=4 – з другого, V3=6 – з третього і так далі отримуємо, U2 =6, U3= -5, U4 = -6, V4=6.

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

С’21­­­ = U­2 + V­1­ = 0+7 = 7 > 4, С’31 = U­3 + V­1­ = -5+7 = 2<5, С’41 = U­4 + V­1­ = -6+7 = 1<M (М – велике число)

С’22­­­ = U­2 + V­2­ = 0+4 = 4 > 2, С’32 = U­3 + V­2­ = -5+4 = -1<3, С’42 = U­4 + V­2­ = -6 +4= -2<0,

С’14­­­ = U­1 + V­4­ = 0+6 = 6< 8, С’24 = U­2 + V­4­ = 0+6 = 6<7, С’34 = U­3 + 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­­­­­­, то початковий опорний план не оптимальний і його можна поліпшити.