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

 

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

 

Табл. 9

Поставщики	Ki		0	15,10	0
		Заводы
Si		К1=50	К2 =40	К3 = 45	К4 = 60
5,0	S1= 65	10,5	12	10 5	9 60
10,0	S2 = 60	11	8	13	9,5
	S3 = 70	9,5	6 40	8 30	11

 

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

Табл. 10

Поставщики	Ki	0	0	0	0
	Склады	Заводы
Si		К1=50	К2 =40	К3 = 45	К4 = 60
0	S1= 65	10,5	12	10 5	9 60
0	S2 = 60	11 50	8	13 10	9,5
0	S3 = 70	9,5	6 40	8 30	11

 

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

Z= 5*10 + 60*9 + 50*11 + 10*13 + 40*6 + 30*8 = 1750.

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

Выберем вспомогательные  коэффициенты U_i и V_j (i=, j=), обращающие в нули коэффициенты при базисных переменных, то есть

С_ij- U_i- V_j=0

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

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

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

Табл.11

	Заводы
Поставщики	К1=50	К2 =40	К3 = 45	К4 = 60	Ui
S1= 65	10,5	12	10 5	9 60	U1 =
S2 = 60	11 50	8	13 10	9,5	U2 =
S3 = 70	9,5	6 40	8 30	11	U3 =
Vi	V1 =	V2 =	V3 =	V4 =

 

 

 

 

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

С13-U1-V3=0		10-U1-V3=0
С14-U1-V4=0		9-U1-V4=0
С21-U2-V1=0	11-U2-V1=0
С23-U2-V3=0	13-U2-V3=0
С32-U3-V2=0	6-U3-V2=0
С33-U3-V3=0	8-U3-V3=0

 

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

U₁  = 0

V₁ = 8

U₂  = 3

V₂ = 8

U₃ = -2  

V₃ = 10 

V₄ = 9

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

Табл. 12

	Заводы
Поставщики	К1=50	К2 =40	К3 = 45	К4 = 60	Ui
S1= 65	10,5	12	10 5	9 60	U1 =0
S2 = 60	11 50	8	13 10	9,5	U2 =3
S3 = 70	9,5	6 40	8 30	11	U3 =-2
Vj	V1 =8	V2 =8	V3 =10	V4 =9

 

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

G_ij = C_ij - S_ij, где S_ij = U_i + V_j

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

G11=С11-U1-V1	G11=10,5-0-8=2,5
G12=С12-U1-V2	G12=12-0-8=4
G22=С22-U2-V2	G22=8-3-8= -3
G24=С24-U2-V4	G24=9,5-3-9=-2,5
G31=С31-U3-V1	G31=9,5+2-8=3,5
G34=С34-U3-V4	G34=11+2-9=4

 

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

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

Табл. 13

	Магазины
Склады	К1=50	К2 =40	К3 = 45	К4 = 60	Ui
S1= 65	10,5	12	10 5	9 60	U1 =0
S2 = 60	11 50	8     (+)	13     (-) 10	9,5	U2 =3
S3 = 70	9,5	6     (-) 40	8      (+) 30	11	U3 =-2
Vj	V1 =8	V2 =8	V3 =10	V4 =9

 

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

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

Z =10*5 + 9*60 + 11*50 + 8*10 + 6*30 + 8*40 = 1720тыс. у.е.

Табл.14

	Магазины
Склады	К1=50	К2 =40	К3 = 45	К4 = 60
S1= 65	10,5	12	10 5	9 60
S2 = 60	11 50	8 10	13	9,5
S3 = 70	9,5	6 30	8 40	11

 

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

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

 

 

Табл. 15

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

 

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

С13-U1-V3=0	10-U1-V3=0
С14-U1-V4=0	9-U1-V4=0
С21-U2-V1=0	11-U2-V1=0
С22-U2-V2=0	8-U2-V2=0
С32-U3-V2=0	6-U3-V2=0
С33-U3-V3=0	8-U3-V=0