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

 

Требуется найти оптимальный план перевозок от поставщиков к потребителям с минимальными затратами на перевозку (транспортировку).

3.2.Данные задачи запишем в виде матрицы перевозок (таблица 3.1).

Таблица 3.1

	B 1		B 2		B 3		B 4		B 5
A 1	26	10	39	11		9		6		8	65
A 2		8	8	9		6		4		7	8
A 3		7	0	5	47	4	14	4	30	5	91
A 4		0		0		0		0	26	0	26
	26		47		47		14		56

 

В правом верхнем углу каждой клетки проставлены тарифы, взятые из матрицы  С.

Тариф С_ij -это величина, равная (или пропорциональная) стоимости перевозки единицы груза из данного пункта отправления А_i в указанный пункт назначения В_j.

Обозначим Х_ij (ед.) - величина поставки от базы-поставщика i (i = 1,2,3,4) потребителю

j (j- 1,2,3,4,5); Z (руб.) - общая стоимость всех перевозок.

Совокупность  неизвестных (Х_ij), где i = 1,2,3,4; j = 1,2,3,4,5 - называется планом перевозок. Очевидно, поставки Х_ij > 0, они вписываются в клетки матрицы перевозок.

Требуется найти оптимальный план перевозок  от поставщиков к потребителям с  минимальными затратами на перевозку, т. е. Z→min.

Составляем  первоначальный опорный план (ОП) поставок методом северо – западного угла. Ставим поставку максимально возможную поставку 26 ед. в верхний левый угол, затем отдаем остаток от поставщика А₁ потребителю В₂ (39 ед.), и так далее , заполняя таблицу поставок с левого верхнего угла.

Подсчитываем  количество заполненных клеток в  таблице 3.1. Любому ОП должно соответствовать ровно (m + n -1) заполненных клеток, где m – количество поставщиков (строк), n – количество потребителей (столбцов).

В нашей  задаче: m + n -1= 4 + 5-1=8, у нас оказалось тоже 8 заполненных клеток, следовательно, полученный ОП в таблице 1 не  вырожденный.

Из таблицы  3.1 видно, что Х₁₁=26; Х₁₂=39; Х₂₂=8; Х₃₂=0; Х₃₃=47; Х₃₄=14; Х₃₅=30; Х₄₅=26.

Стоимость перевозок, соответствующая первому  ОП, определяется с помощью тарифов:

Z = 26*10+39*11+8*9+0*5+47*4+14*4+30*5+26*0=1155 (руб.)

Проверим  оптимальность плана полученного  методом северо-западного угла.

- потенциалы поставщиков (строк),

- потенциалы потребителей (столбцов).

Найдем потенциалы из уравнения  α_i+β_j=c_ij для заполненных клеток:

αi	0	-2	-6	-11
βj	10	11	10	10	11

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

α_i+β_j -c_ij≤0:

Клетка ( 1, 3):  0+ 10= 10> 9

Клетка ( 1, 4):  0+ 10= 10> 6

Клетка ( 1, 5):  0+ 11= 11> 8

Клетка ( 2, 1): -2+ 10= 8= 8

Клетка ( 2, 3): -2+ 10= 8> 6

Клетка ( 2, 4): -2+ 10= 8> 4

Клетка ( 2, 5): -2+ 11= 9> 7

Клетка ( 3, 1): -6+ 10= 4< 7

Клетка ( 4, 1): -11+ 10=-1< 0

Клетка ( 4, 2): -11+ 11= 0= 0

Клетка ( 4, 3): -11+ 10=-1< 0

Клетка ( 4, 4): -11+ 10=-1< 0

Значит, полученный план не оптимален.

Найдем оптимальный план.

Оптимизация клетки ( 1, 4)

Перемещаем 14 единиц груза по циклу.

Получаем новый опорный план.

	B 1		B 2		B 3		B 4		B 5
A 1	26	10	25	11		9	14	6		8	65
A 2		8	8	9		6		4		7	8
A 3		7	14	5	47	4		4	30	5	91
A 4		0		0		0		0	26	0	26
	26		47		47		14		56

Z = 1099 (руб.)

Найдем потенциалы из уравнения  α_i+β_j=c_ij для заполненных клеток:

αi	0	-2	-6	-11
βj	10	11	10	6	11

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

α_i+β_j -c_ij≤0:

Клетка ( 1, 3):  0+ 10= 10> 9

Клетка ( 1, 5):  0+ 11= 11> 8

Клетка ( 2, 1): -2+ 10= 8= 8

Клетка ( 2, 3): -2+ 10= 8> 6

Клетка ( 2, 4): -2+ 6= 4= 4

Клетка ( 2, 5): -2+ 11= 9> 7

Клетка ( 3, 1): -6+ 10= 4< 7

Клетка ( 3, 4): -6+ 6= 0< 4

Клетка ( 4, 1): -11+ 10=-1< 0

Клетка ( 4, 2): -11+ 11= 0= 0

Клетка ( 4, 3): -11+ 10=-1< 0

Клетка ( 4, 4): -11+ 6=-5< 0

Значит, полученный план не оптимален.

Найдем оптимальный план.

Оптимизация клетки (1, 5)

Перемещаем 25 единиц груза по циклу.

Получаем новый опорный план.

 

 

 

 

	B 1		B 2		B 3		B 4		B 5
A 1	26	10		11		9	14	6	25	8	65
A 2		8	8	9		6		4		7	8
A 3		7	39	5	47	4		4	5	5	91
A 4		0		0		0		0	26	0	26
	26		47		47		14		56

Z = 1024 (руб.)

Найдем потенциалы из уравнения α_i+β_j=c_ij для заполненных клеток:

αi	0	1	-3	-8
βj	10	8	7	6	8

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

α_i+β_j -c_ij≤0:

Клетка ( 1, 2):  0+ 8= 8< 11

Клетка ( 1, 3):  0+ 7= 7< 9

Клетка ( 2, 1):  1+ 10= 11> 8

Клетка ( 2, 3):  1+ 7= 8> 6

Клетка ( 2, 4):  1+ 6= 7> 4

Клетка ( 2, 5):  1+ 8= 9> 7

Клетка ( 3, 1): -3+ 10= 7= 7

Клетка ( 3, 4): -3+ 6= 3< 4

Клетка ( 4, 1): -8+ 10= 2> 0

Клетка ( 4, 2): -8+ 8= 0= 0

Клетка ( 4, 3): -8+ 7=-1< 0

Клетка ( 4, 4): -8+ 6=-2< 0

Значит, полученный план не оптимален.

Найдем оптимальный план.

Оптимизация клетки ( 2, 1)

Перемещаем 5 единиц груза по циклу.

Получаем новый опорный план.

	B 1		B 2		B 3		B 4		B 5
A 1	21	10		11		9	14	6	30	8	65
A 2	5	8	3	9		6		4		7	8
A 3		7	44	5	47	4		4		5	91
A 4		0		0		0		0	26	0	26
	26		47		47		14		56

Z = 1009 (руб.)

Найдем потенциалы из уравнения  α_i+β_j=c_ij для заполненных клеток:

αi	0	-2	-6	-8
βj	10	11	10	6	8

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

α_i+β_j -c_ij≤0:

Клетка ( 1, 2):  0+ 11= 11= 11

Клетка ( 1, 3):  0+ 10= 10> 9

Клетка ( 2, 3): -2+ 10= 8> 6

Клетка ( 2, 4): -2+ 6= 4= 4

Клетка ( 2, 5): -2+ 8= 6< 7

Клетка ( 3, 1): -6+ 10= 4< 7

Клетка ( 3, 4): -6+ 6= 0< 4

Клетка ( 3, 5): -6+ 8= 2< 5

Клетка ( 4, 1): -8+ 10= 2> 0

Клетка ( 4, 2): -8+ 11= 3> 0

Клетка ( 4, 3): -8+ 10= 2> 0

Клетка ( 4, 4): -8+ 6=-2< 0

Значит, полученный план не оптимален.

Найдем оптимальный план.

Оптимизация клетки ( 4, 2)

Перемещаем 3 единиц груза по циклу.

Получаем новый опорный план.

 

	B 1		B 2		B 3		B 4		B 5
A 1	18	10		11		9	14	6	33	8	65
A 2	8	8		9		6		4		7	8
A 3		7	44	5	47	4		4		5	91
A 4		0	3	0		0		0	23	0	26
	26		47		47		14		56

Z = 1000 (руб.)

Найдем потенциалы из уравнения  α_i+β_j=c_ij для заполненных клеток:

αi	0	-2	-3	-8
βj	10	8	7	6	8

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

α_i+β_j -c_ij≤0:

Клетка ( 1, 2):  0+ 8= 8< 11

Клетка ( 1, 3):  0+ 7= 7< 9

Клетка ( 2, 2): -2+ 8= 6< 9

Клетка ( 2, 3): -2+ 7= 5< 6

Клетка ( 2, 4): -2+ 6= 4= 4

Клетка ( 2, 5): -2+ 8= 6< 7

Клетка ( 3, 1): -3+ 10= 7= 7

Клетка ( 3, 4): -3+ 6= 3< 4

Клетка ( 3, 5): -3+ 8= 5= 5

Клетка ( 4, 1): -8+ 10= 2> 0

Клетка ( 4, 3): -8+ 7=-1< 0

Клетка ( 4, 4): -8+ 6=-2< 0

Значит, полученный план не оптимален.

Найдем оптимальный план.