Цель	ci, j xi, j	min		x1,2 x2,2 x3,2		200
	таблица
	x1,1 x2,1 x3,1 160					x1,3 x2,3 x3,3	120
xi, j
	Si	Тамбов 160		Тверь 200		Томск 120
строка i
	М 100	11a	x1,1	10		60
					x	x
					1,2	1,3
	СПб 130	6d	x2,1	20c	x2,2	10a x2,3
	Ввост 250	5a		3b	x3,2	8c
			x3,1			x3,3

x1,1	x1,2	x1,3 100
x2,1	x2,	2 x2,3	130
x3,1	x3,2 x3,3		250

Цель

xi, j строка i

ci, j xi, j	min	x1,2 x2,2		x3,2 x4,2 300
таблица
x1,1 x2,1	x3,1 x4,1 200				x1,3 x2,3	x3,3 x4,3 120
Si	Тамбов 200		Тверь 300		Томск 120
М 100	11a	x1,1	10		60
				x	x
				1,2	1,3
СПб 120	6d	x2,1	20c	x2,2	10a x2,3
Ввост 240	5a		3b	x3,2	8c
		x3,1			x3,3
	20		5(d+c)		5(a+c+d)
Ростов 160		x4,1		x4,2	x4,3	160
		x4,1 x4, 2			x4,3

x1,1	x1,2	x1,3 100
x2,1	x2,	2 x2,3	120
x3,1	x3,2 x3,3		240

	Одесса	Минск	Томск	Львов
	50(c+a)	200a	140(c+b)	80a
Мкв	11a	10	60	11d
180a
СПб	6d	20c	10a	5(2a+с+d)
140b
Ввост	5a	3b	8c	14+b+c
190c
Ростов	20	5(d+c)	5(a+c+d)	5(c+1+ d)
150a

Транспортная задача

Метод Северо-Западного Угла

		Тамбов 200	Тверь 300	Томск 120
		(0)	(0)	(0)
Москва	(0)	Мin(100,200)=100
100
СПб 120		Мin(120,100)=100	Мin(20,300)=20
	(0)
Владивосток			Мin(240,280)=240
240	(0)
Ростов 160			Мin(160,40)= 40	Мin(120,120)=120
	(0)

Транспортная задача

					Транспортная задача
		Метод минимального элемента
					Тамбов 80	Тверь	Томск 120
		1002 (0)			(0)	(0)		(0)
	М				Мin(100,80)=80	Мin(20, 20)=20	8
	СПб 120 (0)				Мin(120,200)=120	5	9
	ВлВосток				11	Мin(120,140)=120	Мin(240,120)=120
	240 120		(0)
					12	Мin(160,300)=160	10
	Ростов 160(0)
	Архангск	Томск 200a		Херсон				Одесса	Минск	Томск	Львов
								50(c+a)	200a	140(c+b)	80a
	50(c+a)			140(c+b)
Мкв 100a	11a	10		60			Мкв	11a	10	60	11d
							180a
СПб 140b	6d	20c		10a			СПб 140b	6d	20c	10a	5(2a+с+d)
Ввост 190c	5a	3b		8c			Ввост	5a	3b	8c	14+b+c
							190c
Ростов 150a	20	5(d+c)		5(a+c+d)			Ростов	20	5(d+c)	5(a+c+d)	5(c+1+ d)
							150a

Транспортная задача

Метод Потенциалов

таможня

Тверь 300

Томск 120

Тамбов 200

v 0

v2 7

v3 6

М

100

1

Ввозные пошлины

1

0 12= 20

u1 3 0x11=80

пошлиныСПб 120

1 0x21= 120

3

2

v2

ВлВосток

0

11

0x32= 120

0x33= 120

240

u3

u

4

5

17

0x42= 160

9

Ростов

160

Вывозные

Одесса

Минск

Томск

Львов

Архангск

Томск 200a

Херсон

Новые тарифыМкв

50(c+a)

200a

140(c+b)

80a

50(c+a)

140(c+b)

Мкв 100a

11a

10

60

11a

10

60

11d

180a

СПб 140b

6d

20c

10a

СПб 140b

6d

20c

10a

5(2a+с+d)

Ввост 190c

5a

3b

8c

Ввост

5a

3b

8c

14+b+c

190c

Ростов 150a

20

5(d+c)

5(a+c+d)

Ростов

20

5(d+c)

5(a+c+d)

5(c+1+ d)

150a

Транспортная задача

Цикл ПЕРЕСЧЁТА															В минусах поставка падает
																	Считаем минимум среди
									Тамбов 200				Тверь 300				минусов (падает не ниже 0)
																	Томск 120
М	100																-1
							+							-20 20
									x11=80 20				x12=		0
СПб 120											100						2
									x21= 120				-3 min(120,20)
					0							20	+ 20
				v2				-				100
ВлВосток					0		11						x32= 120				x33= 120
240				u3
Ростов		160							17
													x42= 160				9
		u4 5
																	В плюсах поставка растёт

На сколько поставки	Берём минимальный вдоль
	цикла источник
	(отрицательный элемент)

падают в начале стрелок на столько они возрастают на их концах!!

	Одесса	Минск	Томск	Львов
	50(c+a)	200a	140(c+b)	80a
Мкв	11a	10	60	11d
180a
СПб 140b	6d	20c	10a	5(2a+с+d)
Ввост	5a	3b	8c	14+b+c
190c
Ростов	20	5(d+c)	5(a+c+d)	5(c+1+ d)
150a

6-ти членный цикл пересчёта

«Теорема».

Для каждой базисной переменной существует

ровно один означенный цикл данного типа

проходящий через неё и

базисные переменные.

			Транспортная задача
	Метод Потенциалов
		таможня		Тверь 300	Томск 120
			Тамбов 200
			v1 0	v2 3		v3 3
	М 100		0 11=100	3	-	2
	u1 0
	СПб 120	0	0 1= 100	0 22= 20	6
	v2
	ВлВосток	3	8	0x32= 120	0x33= 120
	240 u3
	Ростов 160		14	x42= 160	9
	u4 3
				0
	Рассчитаем новые тарифы

Данный план оптимален

Отрицательных тарифов нет