Итерация: 12

	b1=7	b2=12	b3=3	b4=11	b5=8	b6=20
a1=14	7	7					0
a2=7		5	2				0
a3=22			1	11	8	2	0
a4=17						17	0
a5=1						1	0
	0	0	0	0	0	0

Получено допустимое начальное решение – опорный план (см. таблицу ниже), удовлетворенны нужды всех потребителей и использованы все запасы производителей.

	b1=7	b2=12	b3=3	b4=11	b5=8	b6=20
a1=14	7	7
a2=7		5	2
a3=22			1	11	8	2
a4=17						17
a5=1						1

Шаг 3

Проверим полученный опорный план  на не вырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1 .

В нашем случае N=10, n+m=6+5=11 , что удовлетворяет условию не вырожденности плана. 

Шаг 4

Вычислим общие затраты на перевозку всей продукции. Для этого запишем транспортную таблицу в которой совместим найденный опорный план с величинами издержек. В левом верхнем углу каждой клетки будем указывать количество единиц продукции а в правом нижнем затраты на перевозку единицы продукции. (см. таблицу ниже) 

	b1=7	b2=12	b3=3	b4=11	b5=8	b6=20
a1=14	7	7
a2=7		5	2
a3=22			1	11	8	2
a4=17						17
a5=1						1

	Потребители
Склад №	1	2	3	4	5	6
1	1.1	2	2.05	1	3	0.5
2	3	2.15	4.8	3	11.07	2.2
3	0.8	1	0.75	2.12	0.1	2.8
4	0.7	0.3	1.1	3.7	1	0.2

	b1=7	b2=12	b3=3	b4=11	b5=8	b6=20
a1=14	7 1.1	7 2
a2=7		5 2.15	2 4.8
a3=22			1 0.75	11 2.12	8 0.1	2 2.8
a4=17						17 0.2
a5=1						1 0

7,7+14= 21,7

10,75+9,6=20,35

0,75+23,32+0,8+5,6=30,47

3,4

72,52

Перемножим числа стоящие в одной клетке (для всех клеток), затем полученные произведения сложим. Получим значение суммарных затрат, для данного начального решения. 

Pнач=

75.92

Шаг:5 Проведем поэтапное улучшение начального решения, используя метод потенциалов. Итерация: 1

Составим вспомогательную рабочую матрицу затрат. Она строится из исходной матрицы издержек (см. Таблицу 3) путем переноса только тех ячеек P_ij которые соответствуют заполненным клеткам транспортной таблицы. Остальные ячейки остаются пустыми. Кроме того, введем

• вспомогательный столбец, в который внесем значения неизвестных U₁ ... U₅ (m =5 - число складов) и

• вспомогательную строку в которую внесем значения неизвестных V₁ ... V₆ (n =6 - число потребителей).

На рисунке они представлены желтым цветом. Эти n+m неизвестных должны для всех (i,j), соответствующих загруженным клеткам, удовлетворять линейной системе уравнений U_i+V_j=P_ij Эту систему всегда можно решить следующим способом:

1. На первом шаге полагают V₆ = 0. Если на k-м шаге найдено значение неизвестной, то в системе всегда имеется еще не определенная неизвестная, которая однозначно может быть найдена на (k+1)-м шаге из уравнения U_i+V_j=P_ij, т.к. значение другой неизвестной в этом уравнении уже известно.

2. То какую неизвестную можно найти на (k+1)-м шаге, определяют методом проб. Переменные U_i и V_j называются симплекс - множителями или потенциалами. Рабочая матрица затрат с рассчитанными потенциалами представлена ниже.

	Потребители
Склад №	1	2	3	4	5	6
1	1.1	2	2.05	1	3	0.5
2	3	2.15	4.8	3	11.07	2.2
3	0.8	1	0.75	2.12	0.1	2.8
4	0.7	0.3	1.1	3.7	1	0.2

Порядок вычисления потенциалов был следующий:

	b1	b2	b3	b4	b5	b6
а1	1.1	2					u1= 6.7
а2		2.15	4.8				u2= 6.85
а3			0.75	2.12	0.1	2.8	u3= 2.8
а4						0.2	u4= 0.2
а5						0	u5= 0
	v1= -5.6	v2= -4.7	v3= -2.05	v4= -0.68	v5= -2.7	v6= 0

   1) Пусть V₆ = 0 ;
   2) U₃ = P_3,6 - V₆ ;
   3) U₄ = P_4,6 - V₆ ;
   4) U₅ = P_5,6 - V₆ ;
   5) V₃ = P_3,3 - U₃ ;
   6) V₄ = P_3,4 - U₃ ;
   7) V₅ = P_3,5 - U₃ ;
   8) U₂ = P_2,3 - V₃ ;
   9) V₂ = P_2,2 - U₂ ;
 10) U₁ = P_1,2 - V₂ ;
 11) V₁ = P_1,1 - U₁ ;

Порядок вычисления потенциалов был следующий:

Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки S_ij, по формуле S_ij = P_ij – U_i - V_j (зеленый цвет). Каждая такая оценка показывает на сколько изменятся общие транспортные затраты при загрузке данной клетки единицей груза. Таким образом, если среди оценок имеются отрицательные (затраты уменьшаются) то данный план можно улучшить переместив в соответствующую клетку некоторое количество продукции. Если же среди оценок нет отрицательных - план является оптимальным. Рабочая матрица затрат с заполнеными оценками клетками представлена ниже.

	b1	b2	b3	b4	b5	b6
a1	1.1	2	-2.6	-5.02	-1	-6.2	u1= 6.7
a2	1.75	2.15	4.8	-3.17	6.92	-4.65	u2= 6.85
a3	3.6	2.9	0.75	2.12	0.1	2.8	u3= 2.8
a4	6.1	4.8	2.95	4.18	3.5	0.2	u4= 0.2
a5	5.6	4.7	2.05	0.68	2.7	0	u5= 0
	v1= -5.6	v2= -4.7	v3= -2.05	v4= -0.68	v5= -2.7	v6= 0

Из всех отрицательных оценок имеет смысл выбрать наибольшую по модулю (красный цвет), так как ее воздействие на общие затраты является максимальным. В нашем случае такая оценка находится в ячейке а₁,b₆ (красный цвет), в соответствующую ячейку транспортной таблицы мы должны переместить некоторое количество продукции т.е. загрузить ее. Отметим в транспортной таблице ячейку а₁,b₆ знаком + . Кроме нее мы пометим знаками - и + другие занятые числами ячейки таким образом, что в каждой строке и каждом столбце транспортной таблицы число знаков + будет равно числу знаков - . Это всегда можно сделать единственным образом, причем в каждой строке и каждом столбце содержится по одному + и - .То есть помеченные знаками клетки должны образовывать цикл.

	b1= 7	b2= 12	b3= 3	b4= 11	b5= 8	b6= 20
a1= 14	7	7 -				+
a2= 7		5 +	2 -
a3= 22			1 +	11	8	2 -
a4= 17						17
a5= 1						1

Затем мы определим минимум M из всех элементов, помеченных знаком - , и выбираем одну ячейку где этот минимум достигается. В нашем случае таковой является а₂,b₃ и обозначает загруженную клетку, которая должна стать свободной.

Число M при этом составляет:

2

Переход к новой транспортной таблице разбивается на следующие шаги. а) В ячейку а₁,b₆ новой таблицы записывается число M. б) Ячейка а₂,b₃ остается пустой. в) В остальных ячейках, помеченных знаками - или +, число M соответственно вычитается из стоящего в ячейке числа или складывается с ним. Результат вносится в соответствующую ячейку новой таблицы. г) Непомеченные числа переносятся в новую таблицу без изменений. Остальные ячейки новой таблицы остаются пустыми.

	b1= 7	b2= 12	b3= 3	b4= 11	b5= 8	b6= 20
a1= 14	7	5				2
a2= 7		7
a3= 22			3	11	8	0
a4= 17						17
a5= 1						1

Итерация: 2 Рабочая матрица затрат с пересчитанными потенциалами и оценкам.

	b1	b2	b3	b4	b5	b6
a1	1.1	2	3.6	1.18	5.2	0.5	u1= 0.5
a2	1.75	2.15	6.2	3.03	13.12	1.55	u2= 0.65
a3	-2.6	-3.3	0.75	2.12	0.1	2.8	u3= 2.8
a4	-0.1	-1.4	2.95	4.18	3.5	0.2	u4= 0.2
a5	-0.6	-1.5	2.05	0.68	2.7	0	u5= 0
	v1= 0.6	v2= 1.5	v3= -2.05	v4= -0.68	v5= -2.7	v6= 0

Ячейка а₃,b₂, транспортной таблицы, должна загрузиться.

	b1= 7	b2= 12	b3= 3	b4= 11	b5= 8	b6= 20
a1= 14	7	5 -				2 +
a2= 7		7
a3= 22		+	3	11	8	0 -
a4= 17						17
a5= 1						1

M =

0

Ячейка а₃,b₆ становится свободной.

	b1= 7	b2= 12	b3= 3	b4= 11	b5= 8	b6= 20
a1= 14	7	5				2
a2= 7		7
a3= 22		0	3	11	8
a4= 17						17
a5= 1						1

Итерация: 3 Рабочая матрица затрат с пересчитанными потенциалами и оценкам.

	b1	b2	b3	b4	b5	b6
a1	1.1	2	0.3	-2.12	1.9	0.5	u1= 0.5
a2	1.75	2.15	2.9	-0.27	9.82	1.55	u2= 0.65
a3	0.7	1	0.75	2.12	0.1	3.3	u3= -0.5
a4	-0.1	-1.4	-0.35	0.88	0.2	0.2	u4= 0.2
a5	-0.6	-1.5	-1.25	-2.62	-0.6	0	u5= 0
	v1= 0.6	v2= 1.5	v3= 1.25	v4= 2.62	v5= 0.6	v6= 0

Ячейка а₅,b₄, транспортной таблицы, должна загрузиться.

	b1= 7	b2= 12	b3= 3	b4= 11	b5= 8	b6= 20
a1= 14	7	5 -				2 +
a2= 7		7
a3= 22		0 +	3	11 -	8
a4= 17						17
a5= 1				+		1 -

Ячейка а₅,b₆ становится свободной.

M =

1

	b1= 7	b2= 12	b3= 3	b4= 11	b5= 8	b6= 20
a1= 14	7	4				3
a2= 7		7
a3= 22		1	3	10	8
a4= 17						17
a5= 1				1

Итерация: 4.

	b1	b2	b3	b4	b5	b6	Рабочая матрица затрат с пересчитанными потенциалами и оценкам
a1	1.1	2	0.3	-2.12	1.9	0.5	u1= 0.5
a2	1.75	2.15	2.9	-0.27	9.82	1.55	u2= 0.65
a3	0.7	1	0.75	2.12	0.1	3.3	u3= -0.5
a4	-0.1	-1.4	-0.35	0.88	0.2	0.2	u4= 0.2
a5	2.02	1.12	1.37	0	2.02	2.62	u5= -2.62
	v1= 0.6	v2= 1.5	v3= 1.25	v4= 2.62	v5= 0.6	v6= 0

Ячейка а₁,b₄, транспортной таблицы, должна загрузиться.

	b1= 7	b2= 12	b3= 3	b4= 11	b5= 8	b6= 20
a1= 14	7	4 -		+		3
a2= 7		7
a3= 22		1 +	3	10 -	8
a4= 17						17
a5= 1				1

Ячейка а₁,b₂ становится свободной.

M =

4

	b1= 7	b2= 12	b3= 3	b4= 11	b5= 8	b6= 20
a1= 14	7			4		3
a2= 7		7
a3= 22		5	3	6	8
a4= 17						17
a5= 1				1

Итерация: 5 Рабочая матрица затрат с пересчитанными потенциалами и оценкам.

	b1	b2	b3	b4	b5	b6
a1	1.1	2.12	2.42	1	4.02	0.5	u1= 0.5
a2	-0.37	2.15	2.9	-0.27	9.82	-0.57	u2= 2.77
a3	-1.42	1	0.75	2.12	0.1	1.18	u3= 1.62
a4	-0.1	0.72	1.77	3	2.32	0.2	u4= 0.2
a5	-0.1	1.12	1.37	0	2.02	0.5	u5= -0.5
	v1= 0.6	v2= -0.62	v3= -0.87	v4= 0.5	v5= -1.52	v6= 0

Ячейка а₃,b₁, транспортной таблицы, должна загрузиться.

	b1= 7	b2= 12	b3= 3	b4= 11	b5= 8	b6= 20
a1= 14	7 -			4 +		3
a2= 7		7
a3= 22	+	5	3	6 -	8
a4= 17						17
a5= 1				1

Ячейка а₃,b₄ становится свободной.

M =

6

	b1= 7	b2= 12	b3= 3	b4= 11	b5= 8	b6= 20
a1= 14	1			10		3
a2= 7		7
a3= 22	6	5	3		8
a4= 17						17
a5= 1				1

Итерация: 6 Рабочая матрица затрат с пересчитанными потенциалами и оценкам.

	b1	b2	b3	b4	b5	b6
a1	1.1	0.7	1	1	2.6	0.5	u1= 0.5
a2	1.05	2.15	2.9	1.15	9.82	0.85	u2= 1.35
a3	0.8	1	0.75	1.42	0.1	2.6	u3= 0.2
a4	-0.1	-0.7	0.35	3	0.9	0.2	u4= 0.2
a5	-0.1	-0.3	-0.05	0	0.6	0.5	u5= -0.5
	v1= 0.6	v2= 0.8	v3= 0.55	v4= 0.5	v5= -0.1	v6= 0

Ячейка а₄,b₂, транспортной таблицы, должна загрузиться.

	b1= 7	b2= 12	b3= 3	b4= 11	b5= 8	b6= 20
a1= 14	1 -			10		3 +
a2= 7		7
a3= 22	6 +	5 -	3		8
a4= 17		+				17 -
a5= 1				1

Ячейка а₁,b₁ становится свободной.

M =

1

	b1= 7	b2= 12	b3= 3	b4= 11	b5= 8	b6= 20
a1= 14				10		4
a2= 7		7
a3= 22	7	4	3		8
a4= 17		1				16
a5= 1				1

Итерация: 7 Рабочая матрица затрат с пересчитанными потенциалами и оценкам.

	b1	b2	b3	b4	b5	b6
a1	0.7	1.4	1.7	1	3.3	0.5	u1= 0.5
a2	1.05	2.15	2.9	0.45	9.82	0.15	u2= 2.05
a3	0.8	1	0.75	0.72	0.1	1.9	u3= 0.9
a4	0.6	0.3	1.05	3	1.6	0.2	u4= 0.2
a5	0.6	0.4	0.65	0	1.3	0.5	u5= -0.5
	v1= -0.1	v2= 0.1	v3= -0.15	v4= 0.5	v5= -0.8	v6= 0

В приведенной выше таблице нет отрицательных оценок (план улучшить нельзя), следовательно достигнуто оптимальное решение.

	b1= 7	b2= 12	b3= 3	b4= 11	b5= 8	b6= 20
a1= 14				10 1		4 0.5
a2= 7		7 2.15
a3= 22	7 0.8	4 1	3 0.75		8 0.1
a4= 17		1 0.3				16 0.2
a5= 1				1 0

Общие затраты на перевозку всей продукции, для оптимального плана составляют: 

Pопт=

43.2