Последовательное улучшение допустимого решения методом потенциалов

Выберем вспомогательные переменные Ui и Vj (I = 1-3, j = 1-4), обращаю­щие в нули коэффициенты при базисных переменных, то есть

Cij - Ui - Vj =0. (16)

Такие переменные называются потенциалами. Введем в табл. 10 для за­писи потенциалов вспомогательную строку и столбец (табл. 11).

Метод потенциалов заключается в выполнении следующих шагов:

1. Для всех Ху > 0 (т.е. всех занятых клеток) составляются потенциальные урав­нения по формуле (16). Для определения т + п потенциалов необходимо, чтобы было т + п - 1 уравнений (где т - число строк, п - число столбцов). То­гда одному из потенциалов можно присвоить значение, равное нулю, а значе­ния других потенциалов получить, решая систему уравнений (17). Для данной задачи т + п -1 = 6, и число занятых клеток равно 5 (см. табл. 10).

	Магазины
Склады	К1=50	К2 =30	К3 = 45	К4 = 40	Ui
S1= 50	16 20	14 30	11	12,5	U1 =
S2 = 55	13 15	13,5	15	12 40	U2 =
S3 = 60	10 15	12,5	9 45	14	U3 =
Vi	V1 =	V2 =	V3 =	V4 =

Составим потенциальные уравнения для заполненных клеток:

С11-U1-V1=0	16-U1-V1=0
С21-U2-V1=0	13-U2-V1=0
С31-U3-V1=0	10-U3-V1=0
С12-U1-V2=0	14-U1-V2=0
С33-U3-V3=0	9-U3-V3=0
С24-U2-V4=0	12-U2-V4=0

2. Решим систему уравнений (17), присвоив значение, равное нулю, наиболее часто встречающемуся неизвестному потенциалу: U₂ = 0, тогда

U₁ = 3 V₁ = 13

U₂ = 0 V₂ = 11

U₃ = -3 V₃ = 12

V₄ = 12

Данные потенциалы занесем в столбцы Ui и Vj табл. 12.

Табл. 12

	Магазины
Склады	К1=50	К2 =30	К3 = 45	К4 = 40	Ui
S1= 50	16 20	14 30	11	12,5	U1 =3
S2 = 55	13 15	13,5	15	12 40	U2 =0
S3 = 60	10 15	12,5	9 45	14	U3 =-3
Vj	V1 =13	V2 =11	V3 =12	V4 =12

3. Для всех небазисных переменных, т.е. для = 0 (для пустых клеток), опре­делим невязки:

Gij = Cij - Sij, где Sij = Ui + Vj

(Cij - стоимость перевозки единицы товара, Sij— косвенная стоимость). Полу­чим (18)

G22=С22-U2-V2	G22=13,5-0+11=2,5
G32=С32-U3-V2	G32=12,5+3-11=4,5
G13=С13-U1-V3	G13=11-3-12=-4
G23=С23-U2-V3	G23=15-0-12=3
G14=С14-U1-V4	G14=12,5-3-12=-2,5
G34=С34-U3-V4	G34=14+3-12=5

Так как имеются отрицательные невязки: G13= -4 и G14 = -2,5, найденный план не оптимален.