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

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

Cij - Ui - Vj =0. (16)

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

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

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

	Магазины
Склады	^i=30	К2 =10	К3 = 30	К4 = 30	Ui
5, =25	3	5	2	2 25	ux =
S2 = 45	6 30	1 10	4	3 5	U2 =
S3 = 30	2	3	1 30	4 0	U3 =
Vi	Vi =	V2 =	V3 =	V4 =

Целесообразно назначить нулевую перевозку в клетку (3, 4), т.е. со склада St, в магазин К₄, чтобы была возможность вычислить потенциал V₃ (см. табл. 11). Тогда число занятых клеток будет равно 6.

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

12. - U_x - V₄ = 0 6-U2-V1=0 1 - и₂- V₂ = 0 3-U₂-V₄ = 0 (17)

2. U₃-V₃ = 0 4 - U₃- V₄ = 0

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

U_x = -\ V, =6 /У₂=0 V₂=l U₃= 1 V₃ = 0

к₄ = з

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

Табл. 12

Склады	Магазины
	Ki =30	K2=\0	K3 = 30	0 m II	Ui
Si =25	3	5	2	2 25	Ui = -1
£2 = 45	6 30	1 10	4	3 5	11 0
S3 =3 0	2	3	1 30	4 0	1/з = 1

Vi

V] = 6

v2 = 1

0 II

V4 = 3

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

Gij = Cij - Sij, где Sij = Ui + V/

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

G\\ = Сц - U\ - V\ G\\ = 3 + 1- 6 = -2

G\₂ — C\₂ - U\ - V₂ G₁₂ = 5 +1-1 = 5

Gu = C₁₃- U\ - V3 G,3 = 2+1-0 = 3

G₂3 = C₂₃- U2-V3 G₂₃ = 4 - 0 - 0 = 4 (18)

G31 = C31- U3 - V\ G₃i = 2-1-6 =-5

G32 = C32-U3-V₂ G₃₂ = 3-1-1 = 1

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

14. Найдем новое базисное решение (табл. 13).

Табл. 13

Склады	Магазины
	Кх =30	о II к ^	Кз = 30	о СП II
S, =25	3	5	2	2 25
52 = 45	6 30 (-)	1 10	4 (+)	3 5
S3 = 30	1 2 (+)|	3	! 1 30 (-) |	4

Для этого введем переменную Ху (назначим перевозку) в ту клетку табл. 15, которой соответствует отрицательная невязка, например, в клетку (3, 1). Отметим ее знаком (+) (см. табл. 15). Знак (+) означает, что в эту клетку следует ввести перевозку. Вводя новую переменную (перевозку), в какую-нибудь клет­ку, необходимо изменить значения других переменных по меньшей мере в трех заполненных клетках, чтобы не нарушились итоговые значения в строках Si и столбцах Kj. Для этого построим четырехугольник (или многоугольник) вер­шинами которого будут отмеченные знаками клетки, причем отрезки, соеди­няющие их, должны располагаться по вертикали или горизонтали. Например, если в клетку (3,1) поставили (+), то в клетку (1,2) надо поставить (-), в клетку (2,3) - (+), в клетку (3,3) - (-). В пустые клетки знак (-) ставить нельзя. В сво­бодную клетку должно быть перенесено меньшее из чисел, (обозначающих пе­

ревозку), стоящих в клетках со знаком (-). Значения перевозок в остальных, отмеченных знаками клетках, должны быть изменены на это же число: если в клетке стоит знак (+) - увеличены, если стоит знак (-) - уменьшены.

В табл. 13 оба числа, находящиеся в клетках со знаком (-), равны 30: х₂₁ = Х33 =30, поэтому во всех клетках, помеченных знаком (+), значения перевозок увеличим на 30, а во всех клетках, помеченных знаком (-) - уменьшим на 30. В результате х₂\ = х₃₃ = 0 и исключаются из базиса. Получим план перевозок, представленный в табл. 16, для которого значение целевой функции равно:

Z= 2-25 + 1 10+ 4-30+ 3-5 + 2-30 =255.

Табл. U
Склады	Магазины
	М,= 30	М2=10	М3=30	о го II
£,=25	3	5	2	2 25
£2=45	6	1 10	4 30	3 5
s3=30	2 30	3	1	4

Перейдем к повторению выполнения действий, описанных в пунктах 1- 4.

15. Для всех xij >0 (т.е. для всех занятых клеток) составим потенциальные урав­нения. Как уже говорилось, должно быть т + п -1 = 6, а имеется число занятых клеток, равное 5. Решение опять вырожденное, следовательно, необходимо на­значить нулевую перевозку, чтобы получить недостающее потенциальное уравнение. Добавим нулевую перевозку в ячейку (3,4): х₃₄ = 0 (табл. 15).

Табл. 15

Склады	Магазины
	о го II	К2=\0	к3-зо	о го II	Ui
£,=25	3	5	2	2 25	U\ = -1
S2=45	6	1 10	4 30	3 5	0 11
s3=30	2 30	3	1	4 0	иъ = 1
Vj	II	II	II	V4 = 3

Получим потенциальные уравнения (19):

16. - U\- V₄ = О \-U₂-V₂ = 0

3. - U₂- V₃ = О

17. - U₂- V₄ = 0 (19) 2- U₃- V, =0

4- U₃- V₄ = О

2. Решим систему уравнений (19), присвоив значение, равное нулю, потенциалу U₂. Если U2 = 0, тогда

£/,=-1 F, = 1 С/₂=0 F₂= 1 £/₃ = 1 V₃ = 4 V₄ = 3.

Занесем их в столбцы Ui и Vj табл. 17.

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

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

Gu = C„ -U\-V\ G„=3 +1-1=3

G\2 ⁼ C\2 - U\ - V₂ G12 = 5 + 1- 1 = 5

G\₃ = C,₃ - U\- V₃ G\₃ = 2+ 1- 4 = -1

G₂\ = C₂, -U₂-V\ G₂ i=6-0-1=5 (20)

G₃₂= C₃₂ - t/₃- K₂ G₃₂= 3 - 1 - 1= 1 G₃₃ = C₃₃-U₃-V₃ G₃₃ = 1 - 1 - 4 = - 4 Имеем две отрицательные невязки Gi₃ = -1 и G₃₃ = -4, поэтому найденный план не оптимален.

2. Найдем новое базисное решение.

Клетку (3,3), например которой соответствует меньшая отрицательная невязка, равная -4, отметим знаком (+) (табл. 16). Одновременно установим равновесие по всему многоугольнику: если в клетку (3,3) поставили (+), то в клетку (3,1) поставим (-), если в клетку (1,1) - (+), в клетку (1,4) - (-), если в клетку (2,4) - (+), в клетку (2,3) - (-).

Склады	Магазины
	К\ = 30		о 1—Н II fc*!	о СП II кэт	К4 =	30
00 II ы		3	5	2		2
	(+)				25	(-)
S2 = 45		6	1 10	4 30	5	3 (+)
				(■) (
о 'П II to	30 в	2	3	1		4
				(+)

Наименьшим из чисел, находящихся в клетках со знаком (-), является со­держимое клетки (1,4), где Х_]4 = 25, поэтому во всех клетках, помеченных зна­ком (+), надо увеличить перевозки на 25, а во всех клеток, помеченных знаком (-) уменьшить перевозки на 25 (табл. 17). Переменная Хи становится равной ну­лю, т.е. выводится из базиса.

Табл. 17

Склады	Магазины
	Кх= 30	К2=\0	К3=30	КА=30
S,=25	3 25	5	2	2
52=45	6	1 10	4 5	3 30
s3=30	2 5	3	1 25	4

Получим план перевозок (см. табл. 17), при котором значение целевой функции равно:

Z= 3 25 + 1 10 + 4-5 + 3-30 + 2-5 + 1 25 = 230.

Повторим действия, описанные в пунктах 1+ 4.

18. Для всех xij > 0 (см. табл. 17) составим потенциальные уравнения:

4. _ и_х - V_t = 0 1 - U₂- V₂ = 0

5. _ и₂-У_ъ = 0

2. - t/₂ - К₄ = 0 (21)

2. и_ъ- V_x =0

1 - С/з-К₃ = 0

т + п-1=6 и число занятых клеток равно 6, значит решение невырожденное.

19. Определим неизвестные потенциалы (21), присвоив значение, равное нулю, например, наиболее часто встречающемуся неизвестному индексу: U₂ = 0, тогда

U\ = -2 V] = 5

и₂= о F₂=l

U₃ = -3 F₃ = 4 V₄ = 3

Занесем вычисленные потенциалы в табл. 18.

Табл. 18

Склады	Магазины
	о m II	К2=\0	^з=30	К4=30
Si=25	3 25	5	2	2	Ux =-2
52=45	6	1 10	4 5	3 30	о II
53=30	2 5	3	1 25	4	U3=- 3
	V] = 5	V2 = 1	ll	m II