Экономико-математические методы и модели в логистике

 

Среди оставшихся клеток, не принадлежащих закрытой строке или  закрытому столбцу (см. табл. 7), наименьшую стоимость перевозки имеет клетка С₂₄. Запишем в нее значение Х₁₄ = min (50,40) = 40. Остаток для строки S₂ =55-40=15, а для столбца К₄ = 40-40 = 0. Запишем их в соответствующие клетки. Четвертый столбец становится закрытым (табл. 8).

Табл. 8

Остатки	Ki	35		0	0
	Склады	Магазины
Si		К1=50	К2 =30	К3 = 45	К4 = 40
	S1= 50	16	14	11	12,5
15	S2 = 55	13	13,5	15	12 40
0	S3 = 60	10 15	12,5	9 45	14

 

Из оставшихся незакрытых клеток (табл. 8) С₂₁=13- клетка с наименьшей стоимостью перевозки, следовательно, в клетку соответствующую С₂₁ записывается значение х₂₁ = min (15,35) = 15. В клетки S₂ и К₄ записываются остатки: остаток во второй строке - (15-15 = 0), в первом столбце - (35-15=20). Вторая строчка становится закрытой (табл. 9).

Табл. 9

Остатки	Ki	20		0	0
	Склады	Магазины
Si		К1=50	К2 =30	К3 = 45	К4 = 40
	S1= 50	16	14	11	12,5
0	S2 = 55	13 15	13,5	15	12 40
0	S3 = 60	10 15	12,5	9 45	14

 

Незакрытыми остаются первая строка и первый со вторым столбцом (см. табл. 9). Остаются ячейки ячейка С₁₂=14 и С₁₁=16. В клетки, соответствующие С₁₂ и С₁₁, записываются значения х₁₂ = min (50,30) = 30 и х₁₁ = min (20,20) = 20 соответственно. В клетки с остатками S₁ , К₂  и К₁ записываются остатки: остаток во второй строке - (50-30-20 = 0), во втором столбце - (30-30 = 0), в первом столбце - (20-20 = 0). (Первый столбец, второй столбец и первая строка закрываются) (табл. 10).

Табл. 10

Остатки	Ki	0	0	0	0
	Склады	Магазины
Si		К1=50	К2 =30	К3 = 45	К4 = 40
0	S1= 50	16 20	14 30	11	12,5
0	S2 = 55	13 15	13,5	15	12 40
0	S3 = 60	10 15	12,5	9 45	14

 

Все строки и столбцы становятся закрытыми, следовательно, исходный базисный план найден. Этому плану соответствует  стоимость перевозки:

Z= 20*16 + 30*14 + 15*13 + 40*12 + 15*10 + 45*9 = 1970.

 

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

 

Выберем вспомогательные  переменные 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, найденный план не оптимален.

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

Табл. 13

	Магазины
Склады	К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

 

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

В табл. 13 числа, находящиеся  в клетках со знаком (-), равны = 20 и = 45, min (20,45) = 20, поэтому во всех клетках, помеченных знаком (+), значения перевозок увеличим на 20, а во всех клетках, помеченных знаком (-) - уменьшим на 20. В результате = 0 и исключается из базиса,  = 25 и оно остается в базиса. Получим план перевозок, представленный в табл. 16, для которого значение целевой функции равно:

Z =15*13 + 35*10 + 30*14 + 20*11 + 25*9 + 40*12 = 1980.

Табл.14

	Магазины
Склады	К1=50	К2 =30	К3 = 45	К4 = 40
S1= 50	16	14 30	11 20	12,5
S2 = 55	13 15	13,5	15	12 40
S3 = 60	10      35	12,5	9       25	14

 

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

1. Для всех xij >0 (т.е. для всех занятых клеток) составим потенциальные уравнения. Как уже говорилось, должно быть т + п -1 = 6. (табл. 15).

Табл. 15

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