Методом минимальной стоимости

Распределим поставки методом наименьшей стоимости, посчитаем потенциалы и значение целевой функции.

 

 

ai bj		1	2	1	3	0	-2
		200	400	100	200	100	300
0	200	1	1	12	2	5	0
		200			[-1]
1	100	2	3	8	4	7	0
		=0=	100
3	200	3	5	4	6	9	0
		[-1]		=0=	200
2	400	4	4	3	8	2	0
				100		=0=	300
1	400	5	3	7	10	1	0
			300			100

 

F=3000

 

ai bj		-1	1	0	2	-1	-3
		200	400	100	200	100	300
0	200	1	1	12	2	5	0
					200
2	100	2	3	8	4	7	0
			100		=0=
4	200	3	5	4	6	9	0
		200	=0=
3	400	4	4	3	8	2	0
				100		=0=	300
2	400	5	3	7	10	1	0
			300			100

 

F=2600

Клеток с отрицательными потенциалами нет, значит, мы нашли оптимальный план распределения поставок. F min = 2600

 

II способ: распределение поставок

Методом северо-западного угла

 

ai bj		1	2	1	6	0	-1
		200	400	100	200	100	300
0	200	1	7	12	2	5	0
		200			[-4]
1	100	2	3	8	4	7	0
		=0=	100		=0=
3	200	3	5	4	6	9	0
		[-1]	200		[-3]
2	400	4	4	3	8	2	0
			100	100	200	=0=	[-1]
1	400	5	3	7	10	1	0
						100	300

F=4800

Распределим поставки методом северо-западного угла, посчитаем потенциалы и значение целевой функции.

 

ai bj		-1	1	0	2	-1	-2
		200	400	100	200	100	300
0	200	1	7	12	2	5	0
					200
2	100	2	3	8	4	7	0
			100		=0=
4	200	3	5	4	6	9	0
		200	=0=
3	400	4	4	3	8	2	0
			300	100		=0=	[-1]
2	400	5	3	7	10	1	0
						100	300

 

F=2900

 

ai bj		-1	1	0	2	-1	-3
		200	400	100	200	100	300
0	200	1	7	12	2	5	0
					200
2	100	2	3	8	4	7	0
			100		=0=
4	200	3	5	4	6	9	0
		200	=0=
3	400	4	4	3	8	2	0
				100			300
2	400	5	3	7	10	1	0
			300			100

 

F=2600

 

Клеток с отрицательными потенциалами нет, значит мы нашли оптимальный план распределения поставок. F min =2600

Транспортная задача с ограничениями на пропускную способность

Если требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l к потребителю с номером k. Возможны ограничения двух типов x_lk >= a и x_lk =< b, где a и b – постоянные величины.

1. Если x_lk >= a, то необходимо, прежде чем решать задачу, сократить запасы l-го поставщика и запросы k-го потребителя на величину а (зарезервировать перевозку x_lk = a). В полученном оптимальном решении следует увеличить объем перевозки x_lk на величину а.

2. Если x_lk =< b, то необходимо вместо k-го потребителя с запросами b_k ввести двух других потребителей. Один из них с номером k должен иметь запасы b_k` = b, а другой с номером n+1 – запросы b_n+1 = b_k – b. Стоимости перевозок для этих потребителей остаются прежними, за исключением c_l(n+1), которая принимается равной сколь угодно большому числу М. После получения оптимального решения величины грузов, перевозимых к (n+1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как c_l(n+1) = М, то в оптимальном решении клетка с номером (l, n+1) останется пустой (x_l(n+1) = 0) и объем перевозки x_lk не превзойдет b.

 

V  Задание:

I способ: распределение поставок