Решение задач симплекс методом

ЗАДАЧА 1

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

Виды сырья	Расходы сырья на единицу продукции			Общий запас сырья, ед.
	М1	М2	М3
П1	2	4	3	266
П2	1	3	4	200
П3	3	2	1	303
Уровень прибыли на ед. продукции	20	24	28

Содержание задачи.

Цех кондитерской фабрики вырабатывает три ассортиментные группы конфет, условно обозначенные М1
, М2
, М3
/в ед./.

Для их производства используются основные виды ресурсов /сырья/ трех видов, условно названных П1
, П2
, П3
/в ед./.

Расход каждого ресурса на производство единицы продукции является за­данной величиной, определяется по рецептуре и обозначается символами а11
, a12
..., а33
, где а - норма расхода, первая подстрочная 1 – номер ресурса, вторая подстрочная 1, 2, 3 – номер ассортиментной группы конфет.

Наличие каждого ресурса для производства всех, групп конфет принимает­ся как известная величина и обозначается символами в1
, в2
, в3
.

Прибыль на продукцию также принимается как известная величина и обо­значается символами c1
, c2
, с3
.

Перечисленные параметры являются величинами известными и выражают­ся в единых единицах измерения, кроме прибыли. Прибыль или другой какой показатель, являющийся критерием оптимальности, выражается в единицах из­мерения дохода /например, прибыли/, получаемого от производства единицы продукции в денежном или другом каком-нибудь выражении.

Поскольку решение задачи заключается в поиске такого плана производст­ва, который обеспечивал бы в принятых условиях наибольший доход, принима­ются те величины, которые являются неизвестными и обозначающими количест­ва каждой группы конфет, включаемых в план производства: x1
для M1
; х2
для М2
; х3
для М3
.

Экономико-математическая модель в символическом виде.

Система ограничений

Целевая функция /суммарный доход/ F = с1
х1
+ с2
х2
+ с3
х3
= мах

Условия неотрицательности неизвестных х1
≥ 0, х2
≥ 0, х3
≥ 0

Символическая модель, наполненная численной информацией, будет иметь следующий вид:

2x1
+ 4x2
+ 3x3
≤ 266

1x1
+ 3x2
+ 4x3
≤ 200

3x1
+ 2x2
+ 1x3
≤ 303

Прибыль от реализации выпускаемой продукции должна быть максималь­ной, то есть F
= 20х1
+ 24х2
+ 28х3
= max;

Решение задачи.

Для решения задачи симплексным методом неравенства преобразуются в эквивалентные равенства путем добавления в каждое неравенство по одному до­полнительному неизвестному с коэффициентом + 1 и нулевым уравнением при­были. Для удобства расчетов левые и правые части уравнений меняются места­ми. В этом случае исходные неравенства примут вид симплексных уравнений:

266 = 2x1
+ 4x2
+ 3x3
+ 1x4

200 = 1x1
+ 3x2
+ 4x3
+ 1x5

303 = 3x1
+ 2х2
+ 1x3
+ 1x6

F= 20х1
+ 24х2
+ 28х3
+ 0x4
+ 0x5
+ 0x6

Коэффициенты при неизвестных записываются в симплексной таблице, в которой выполняются расчеты и отражаются полученные результаты.

Исходная таблица

cj	p0	x0	20	24	28	0	0	0
			x1	х2	х3	х4	х5	х6
0	х4	266	2	4	3	1	0	0
0	х5	200	1	3	4	0	1	0
0	х6	303	3	2	1	0	0	1
Zj - Cj		0	-20	-24	-28	0	0	0

В столбцах таблицы записывают: в первом (Cj
) – прибыль единицы про­дукции, которая вводится в план выпуска; во втором (Р0
) – неизвестные, вклю­чаемые в план; в третьем (Х0
) – свободные величины; в остальных – коэффици­енты при неизвестных уравнений. В верхней части этих столбцов отражаются коэффициенты при неизвестных целевой функции.

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

В последних трех столбцах коэффициенты при дополнительных неизвест­ных, равные единице, расположены по диагонали. Эта часть таблицы, называе­мая единичной подматрицей, необходима для вычислительных и аналитических целей.

При решении задач на максимум целевой функции наличие в целевой строке отрицательных чисел указывает на возможность начала или продолжения решения задачи. Порядок решения таков: из отрицательных чисел целевой строки выбирается наибольшее по модулю. Столбец, в котором оно находится, принимается за ключевой (или разрешающий) и для удобства расчетов выделя­ется. В нашем примере таким столбцом будет Х3
, имеющий в целевой строке наибольшую по модулю величину -28.

1-ая итерация

cj	p1	x0	x1	х2	х3	х4	х5	х6
0	х4	116	1.3	1.75	0	1	-1	0
28	х3	50	0.3	0.75	1	0	0.3	0
0	х6	253	2.8	1.25	0	0	-0	1
Zj - Cj		1400	-13	-3	0	0	7	0

Затем элементы столбца Х0
(свободные величины) делят на соответствую­щие коэффициенты ключевого столбца и полученные результаты сопоставляют между собой. Строка с наименьшим отношением принимается за ключевую и также для удобства выделяется. В нашем случае 266/3 = 88,7; 200/4 = 50; 303/1 = 303. Наименьшее отношение 50 имеет срока х5
, она и будет ключевой. Ключевой элемент 4.

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

В столбцах Ро
и Cj
занимают место вводимая в план неизвестная х3
с при­былью 28 (итерация 1-я). Остальные элементы преобразуются по следующему правилу:

- для преобразуемого элемента в его столбце находят элемент ключевой строки, а в его строке - элемент ключевого столбца;

- соответствующие элементы ключевой строки и ключевого столбца пере­множаются и полученное произведение делят на ключевой момент;

- частное от деления вычитают из значения элемента, которое он имел до преобразования, и полученный результат будет преобразованным элементом, ко­торый записывается в новую таблицу в том же самом месте. Следуя этому пра­вилу, преобразование элементов столбца х0
будет:

Включение на первой итерации в план неизвестной х3
обеспечит сумму прибыли 1400 руб.

Решение задачи продолжается, так как в целевой строке два отрицатель­ных элемента. Наибольший по модулю элемент -13. Он находится в столбце х1
, который принимается за ключевой, а ключевой строкой будет х6
(116:1,3=92,8; 50:0,3=200; 253:2,8=92), ключевым элементом 2,8. Элементы таблицы преобра­зуются в том же порядке по изложенному правилу и записываются в новую таб­лицу.

2-я итерация

cj	p2	x0	x1	х2	х3	х4	х5	х6
0	х4	1	0	1.18	0	1	-1	-0.5
28	х3	27	0	0.64	1	0	0.3	-0.1
13	х1	92	1	0	0	0	0	0
Zj - Cj		2596	0	2.91	0	0	5.8	4.7

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

Как видно из таблицы, оптимальный план предусматривает выпуск про­дукции П1
27 ед. (х1
= 27), П3
92 ед. (х3
= 92), дополнительного неизвестного П4
1 ед. (х4
= 1). П2
и дополнительные неизвестные в план не вошли, следовательно, х2
= 0, х5
= 0 х6
= 0. Подставив значения неизвестных в уравнения, получим:

2 * 92 + 4 * 0 + 3 * 27 + 1 = 266

1 * 92 + 3 * 0 + 4 * 27 + 0 = 200

3 * 92 + 2 * 0 + 1 * 27 + 0 = 303

F = 20 * 92 + 24 * 0 + 27 * 28 = 2596

Анализ оптимального плана.

а) Запасы сырья трех видов используются не полностью, так как х4
= 1, а х5
= х6
= 0.

б) Рассмотрим элементы матрицы.

От выпуска продукции II следует отказаться.

Элементы столбца х5
показывают, что увеличение запасов сахара на I ед. (х5
= 1) позволит увеличить выпуск продукции III вида на 0,3 ед. Сумма прибыли увеличится на 5,8 руб.

Элементы столбца х6
показывают, что увеличение запасов жира на I ед. (х6
= 1) позволит уменьшить выпуск только продукции III вида на 0,1 ед. (27 - 0.1) Сумма при­были увеличится на 4,7 руб.

Снижение запасов сырья приводит к изменениям выпуска продукции и суммы прибыли в обратном порядке.

Элементы целевой строки оптимального плана называются двойственными оценками, которые определяют величину изменения прибыли при изменении за­пасов сырья на I ед.

ЗАДАЧА 2

Требуется определить минимальную по стоимости смесь сырья для изго­товления пищевых концентратов, которые должны содержать питательные ве­щества (П). Эти вещества содержаться в сырье (М) в различных сочетаниях. Со­держание питательных веществ в сырье и готовом продукте, а также цена на ка­ждый вид сырья показаны в таблице.

Питательные вещества	Виды сырья			Минимальное содержание (единиц) питательных веществ в готовом продукте
	M1	М2	М3
П1	1	1	0	50
П2	4	1	3	140
П3	1	4	1	127
П4	0	3	2	80
Цена за единицу сырья, руб.	8	12	10

Виды используемого сырья условно обозначены через М1
, М2
, М3
; содер­жание питательных веществ в сырье и готовом продукте обозначены П1
, П2
, П3
, П3
.

Исходные условия задачи выражаются неравенствами:

1х1
+ 1х2
+ 0х3
≥ 50

4х1
+ 1х2
+ 3х3
≥ 140

1х1
+ 4х2
+ 1х3
≥ 127

0х1
+ 3х2
+ 2х3
≥ 80

F
=
8х1
+ 12х2
+ 10х3
= min

Умножив обе части неравенств на -1, получим систему с другим направле­нием знака неравенств:

-1х1
- 1х2
- 0х3
≥ -50

-4х1
- 1х2
- 3х3
≥ -140

-1х1
- 4х2
- 1х3
≥ -127

0х1
- 3х2
- 2х3
≥ -80

F
=
8х1
+ 12х2
+ 10х3
= min

Преобразуем неравенства в эквивалентные равенства с помощью дополни­тельных неизвестных. Симплексные уравнения будут следующими:

-50 = -1х1
- 1х2
- 0х3
+ 1х4
+ 0х5
+ 0х6
+ 0х7

-140 = -4х1
- 1х2
- 3х3
+ 0х4
+ 1х5
+ 0х6
+ 0х7

-127 = -1х1
- 4х2
- 1х3
+ 0х4
+ 0х5
+ 1х6
+ 0х7

-80 = 0х1
- 3х2
- 2х3
+ 0х4
+ 0х5
+ 0х6
+ 1х7

F
=
8х1
+ 12х2
+ 10х3
+ 0х4
+ 0х5
+ 0х6
+ 0х7
= min

Записанные уравнения отличаются от тех, которые нами рассматривались выше, тем, что коэффициенты при основных неизвестных и свободные члены имеют отрицательные знаки.

Решение таких задач производится двойственным симплексным методом. Система симплексных уравнений записывается в таблице.

cj	p0	x0	8	12	10	0	0	0	0
			x1	х2	х3	х4	х5	х6	х7
0	х4	-50	-1	-1	0	1	0	0	0
0	х5	-140	-4	-1	-3	0	1	0	0
0	х6	-127	-1	-4	-1	0	0	1	0
0	х7	-80	0	-3	-2	0	0	0	1
Zj - Cj		0	-8	-12	-10	0	0	0	0

Элементы целевой строки рассчитывают по обычным правилам и получа­ют отрицательные знаки.

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

В итоговом столбце свободные числа имеют отрицательные знаки. Это яв­ляется свидетельством того, что данный план нельзя считать допустимым, так как он противоречит экономическому смыслу. План можно считать допустимым только тогда, когда в итоговом столбце не будет отрицательных чисел.

Ликвидация отрицательных чисел в итоговом столбце начинается с наи­большего по абсолютной величине. В нашем примере таким числом является (-140). Строка х5
, в которой находится это число, принимается за ключевую и со­ответственно выделяется.

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

Столбцы х1
, х2
, х3
будут иметь следующие отно­шения:

Наименьшее отношение имеет столбец х1
,он и будет являться ключевым.

Определив ключевую строку, ключевой столбец и ключевое число, по обычным правилам преобразуются все элементы матрицы и записываются в но­вой таблице.

1-я итерация

cj	p0	x0	18	15	24	0	0	0	0
			x1	х2	х3	х4	х5	х6	х7
0	х4	-15	0	-0.75	0.75	1	-0.25	0	0
8	х1	35	1	0.25	0.75	0	-0.25	0	0
0	х6	-92	0	-3.75	-0.25	0	-0.25	1	0
0	х7	-80	0	-3	-2	0	0	0	1
Zj - Cj		280	0	-10	-4	0	-2	0	0

После преобразования элементов в итоговом столбце осталось еще три от­рицательных числа в строке х4
, х6
и х7
. Наибольшим по абсолютной величине яв­ляется число в строке х6
. Эта строка будет принята за ключевую для последую­щего расчета. Ключевой столбец определяется по наименьшему отношению эле­ментов целевой строки к элементам ключевой строки. Им будет столбец х2
. Вво­дим этот вид сырья в программу вместо неизвестного х6
. По общим правилам преобразуем элементы матрицы.

2-я итерация

cj	p0	x0	x1	х2	х3	х4	х5	х6	х7
0	х4	3.4	0	0	0.8	1	-0.2	-0.2	0
8	х1	28.9	1.0	0.0	0.7	0.0	-0.3	0.1	0.0
15	х2	24.5	0.0	1.0	0.1	0.0	0.1	-0.3	0.0
0	х7	-6.4	0.0	0.0	-1.8	0.0	0.2	-0.8	1.0
Zj - Cj		525.3	0.0	0.0	-3.3	0.0	-1.3	-2.7	0.0

После преобразования элементов в итоговом столбце осталось еще одно отрицательное число в строке х7
. Эта строка будет принята за ключевую для по­следующего расчета. Ключевой столбец определяется по наименьшему отноше­нию элементов целевой строки к элементам ключевой строки. Им будет столбец х3
. Вводим этот вид сырья в программу вместо неизвестного х7
. По общим пра­вилам преобразуем элементы матрицы.

В таблице записаны преобразованные числа, полученные на 3-й итерации. В итоговом столбце все отрицательные числа исчезли, значит полученный план является допустимым и одновременно оптимальным. Вывод о том, что план по­лучен оптимальный, позволяют сделать элементы целевой строки. Все они отри­цательны или равны нулю, что свидетельствует об оптимальности результата при решении задач на минимум целевой функции.

3-я итерация

cj	p0	x0	x1	х2	х3	х4	х5	х6	х7
0	х4	0.6	0.0	0.0	0.0	1.0	-0.1	-0.6	0.4
8	х1	26.3	1.0	0.0	0.0	0.0	-0.2	-0.3	0.4
15	х2	24.3	0.0	1.0	0.0	0.0	0.1	-0.3	0.0
10	х3	3.6	0.0	0.0	1.0	0.0	-0.1	0.4	-0.6
Zj - Cj		537.2	0.0	0.0	0.0	0.0	-1.7	-1.2	-1.9

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

1 * 26,3 + 1 * 24,3 + 0 * 3,6 ≥ 50

4 * 26,3 + 1 * 24,3 + 3 * 3,6 ≥ 140

1 * 26,3 + 4 * 24,3 + 1 * 3,6 ≥ 127

0 * 26,3 + 3 * 24,3 + 2 * 3,6 ≥ 80

Стоимость сырья при этом будет минимальной и составит:

F
=
8 * 26,3 + 12 * 24,3 + 12 * 3,6 = 537,2

ЗАДАЧА 3

Составить оптимальный план перевозок пищевых продуктов от 4-х по­ставщиков к 6-ти потребителям. Поставщики (П), потребители (М), объемы вы­воза и завоза, кратчайшие расстояния между пунктами вывоза и завоз приведены в таблице.

Поставщики	Потребители						Объемы вывоза, т
	М1	М2	М3	М4	М5	М6
П1	24	30	42	15	39	21	144
П2	9	24	30	33	27	29	148
П3	24	22	20	45	21	23	76
П4	11	36	27	40	30	8	132
Объемы завоза, т	92	84	80	112	96	36

Решение задачи начинается с распределения у имеющихся у поставщиков объемов вывоза между потребителями с учетом объемов завоза. Для первоначального распределения используются способы: северо-западного угла, наименьшего элемента по строке, наименьшего элемента по столбцу, наименьшего элемента матрицы.

Способ северо-западного угла состоит в том, что распре­деление объемов вывоза производится, начиная с верхнего лево­го угла таблицы и кончая нижним углом ее. Результаты распреде­ления показаны в таблице.

Поставщики и объемы вывоза, т		Потребители и объемы завоза						Потенциалы строк
		М1	М2	М3	М4	М5	М6
		92	84	80	112	96	36
П1	144	24	30	42	15	39	21	0
		92	52
П2	148	9	24	30	33	27	29	-6
		32	80	36
П3	76	24	22	20	45	21	23	6
		76	0
П4	132	11	36	27	40	30	8	15
		96	36
Потенциалы столбцов		24	30	36	39	15	-7

Проверка плана на оптимальность. Когда исходный план получен и рассчитана соответствующая ему суммарная тонно-километровая работа, определяют, является ли этот план оптимальным. Для проверки плана на оптимальность применяется метод потенциалов.

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

Для решения задач методом потенциалов исходный план дол­жен иметь количество заполненных клеток m + n – 1 (m - число строк, n - число столбцов). Если план не отвечает этим требованиям, то не для всех строк и столбцов можно рассчи­тать потенциалы, а без них нельзя проверить план на оптималь­ность.

Потенциалы строк и столбцов определяются по заполненным клеткам, находящимся на их пересечении.

Элемент заполненной клетки должен равняться сумме потен­циалов строки и столбца, на пересече

нии которых находится эта заполненная клетка.

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

Обозначив потенциалы строк ui
, потенциалы столбцов Vj, элементы заполнения клеток , можно записать порядок расчета потенциалов для общего случая.

Из основного требования = ui
+ Vj вытекает:

ui
= - Vj; Vj = - ui

Из этих выражений видно, что для расчета потенциала строки необходимо иметь заполненную клетку, в столбце которой потенциал уже определен, а для расчета потенциала столбца нужна заполненная клетка, имеющая потенциал в строке.

Потенциалы показаны в таблице.

После того, как по строкам и столбцам определены потенциа­лы, с их помощью выясняется, является ли план оптимальным, и если нет, то как его можно улучшить. С этой целью для каждой свободной клетки вычисляется сумма потенциалов строк и столбцов, на пересечении которых находится эта клетка.

Сравнение суммы потенциалов с величиной элемента в свобод­ных клетках позволяет определить, нужно ли заполнять эту клетку или ее нужно оставить свободной.

При решении задач на минимум функционала (в нашем случае на минимум тонно-километровой работы) не заполняются те свобод­ные клетки, в которых сумма потенциалов меньше величины эле­мента (в нашем случае - расстояния).

Иными словами, если характеристика, значение которой равно разности - (ui
+ Vj), положительная, то свободная мет­ка не заполняется при решении задачи на минимум функции.

Свободные клетки, имеющие нулевое значение характеристики, показывают на то, что их заполнение приведет к перераспределению поставок, но объем работ (значение функционала) останется неиз­менным.

Суммы потенциалов, значения элементов и характеристики для незаполненных клеток приведены в таблице.

Шифры клеток	П1 -М3	П1 -М4	П1 -М5	П1 -M6	П2 -М1	П2 -М5	П2 -М6	П3 -М1	П3 -М2	П3 -М3	П3 -М6	П4 -М1	П4 -М2	П4 -М3	П4 -М4
Суммы потенциалов	36	39	15	-7	18	9	-13	30	36	42	-1	39	45	51	54
Значение элементов	42	15	39	21	9	27	29	24	22	20	23	11	36	27	40
Характеристики	6	-24	24	28	-9	18	42	-6	-14	-22	24	-28	-9	-24	-14

В первоначальном плане шесть клеток имеют положительные характеристики, в девяти клетках характеристики отрицательные.

Так как задача решается на минимум целевой функции, то именно эти отрицательные клетки должны быть заполнены поставщиками. Но заполнение свободной клетки и связанное с ним пере­распределение поставок производится не изолированно, а в связи с несколькими заполненными клетками. Эта связь выявляется путем построения замкнутых многоугольников, вершинами которых явля­ются клетки таблицы. Одна вершина многоугольника находится в свободной клетке, а все остальные - в заполненных клетках. Многоугольник, или как его называют цепь, имеет прямые углы и четное число вершин.

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

Те клетки цепи, у которых поставки увеличиваются, называ­ются положительными, а те, у которых поставки уменьшаются - отрицательными. Каждая цепь имеет одинаковое число положитель­ных и отрицательных вершин (клеток). Положительные и отрица­тельные вершины чередуются. Если свободную клетку, в которую предполагается произвести запись, принять как положительную (поскольку изменение произойдет в сторону увеличения), то сле­дующая клетка будет отрицательной, затем опять положительной, снова отрицательной, и т.д.

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

+П4М1 -П1М1 +П1М2 -П2М2 +П2М4 -П3М4 +П3М5 -П4М5

Поставщики и объемы вывоза, т		Потребители и объемы завоза						Потенциалы строк
		М1	М2	М3	М4	М5	М6
		92	84	80	112	96	36
П1	144	24	30	42	15	39	21	0
		60	84
П2	148	9	24	30	33	27	29	-6
		80	68
П3	76	24	22	20	45	21	23	6
		44	32
П4	132	11	36	27	40	30	8	15
		32	64	36
Потенциалы столбцов		24	30	36	39	15	-7

Шифры клеток	П1 -М3	П1 -М4	П1 -М5	П1 -М6	П2 -М1	П2 -М2	П2 -М5	П2 -М6	П3 -М1	П3 -М2	П3 -М3	П3 -М6	П4 -М2	П4 -М3	П4 -М4
Суммы потенциалов	36	39	15	-7	18	24	9	-13	30	36	42	-1	45	51	54
Значение элементов	42	15	39	21	9	24	27	29	24	22	20	23	36	27	40
Характеристики	6	-24	24	28	-9	0	18	42	-6	-14	-22	24	-9	-24	-14

+П2М5 -П4М5 +П4М1 -П1М1 +П1М4 -П2М4

Поставщики и объемы вывоза, т		Потребители и объемы завоза						Потенциалы строк
		М1	М2	М3	М4	М5	М6
		92	84	80	112	96	36
П1	144	24	30	42	15	39	21	0
		16	84	44
П2	148	9	24	30	33	27	29	18
		80	68
П3	76	24	22	20	45	21	23	-22
		76
П4	132	11	36	27	40	30	8	-13
		76	20	36
Потенциалы столбцов		24	30	12	15	43	21

Шифры клеток	П1 -М3	П1 -М5	П1 -М6	П2 -М1	П2 -М2	П2 -М5	П2 -М6	П3 -М1	П3 -М2	П3 -М3	П3 -М4	П3 -М6	П4 -М2	П4 -М3	П4 -М4
Суммы потенциалов	12	43	21	42	48	61	39	2	8	-10	-7	-1	17	-1	2
Значение элементов	42	39	21	9	24	27	29	24	22	20	45	23	36	27	40
Характеристики	30	-4	0	-33	-24	-34	-10	22	14	30	52	24	19	28	38

+П2М5 -П4М5 +П4М1 -П1М1 +П1М4 -П2М4

Поставщики и объемы вывоза, т		Потребители и объемы завоза						Потенциалы строк
		М1	М2	М3	М4	М5	М6
		92	84	80	112	96	36
П1	144	24	30	42	15	39	21	0
		84	60
П2	148	9	24	30	33	27	29	18
		80	52	16
П3	76	24	22	20	45	21	23	12
		76
П4	132	11	36	27	40	30	8	21
		92	4	36
Потенциалы столбцов		-10	30	12	15	9	-13

Шифры клеток	П1 -М1	П1 -М3	П1 -М5	П1 -М6	П2 -М1	П2 -М2	П2 -М6	П3 -М1	П3 -М2	П3 -М3	П3 -М4	П3 -М6	П4 -М2	П4 -М3	П4 -М4
Суммы потенциалов	-10	12	9	-13	8	30	5	2	42	24	27	-1	51	33	36
Значение элементов	24	42	39	21	9	24	29	24	22	20	45	23	36	27	40
Характеристики	34	30	30	34	1	-6	24	22	-20	-4	18	24	-15	-6	4

+П3М2 -П1М2 +П1М4 -П2М4 +П2М5 -П3М5

Поставщики и объемы вывоза, т		Потребители и объемы завоза						Потенциалы строк
		М1	М2	М3	М4	М5	М6
		92	84	80	112	96	36
П1	144	24	30	42	15	39	21	0
		32	112
П2	148	9	24	30	33	27	29	-2
		80	68
П3	76	24	22	20	45	21	23	-8
		52	24
П4	132	11	36	27	40	30	8	1
		92	4	36
Потенциалы столбцов		10	30	32	15	29	7

Шифры клеток	П1 -М1	П1 -М3	П1 -М5	П1 -М6	П2 -М1	П2 -М2	П2 -М4	П2 -М6	П3 -М1	П3 -М3	П3 -М4	П3 -М6	П4 -М2	П4 -М3	П4 -М4
Суммы потенциалов	10	32	29	7	8	28	13	5	2	24	7	-1	31	33	16
Значение элементов	24	42	39	21	9	24	33	29	24	20	45	23	36	27	40
Характеристики	14	10	10	14	1	-4	20	24	22	-4	38	24	5	-6	24

+П4М3 -П2М3 +П2М5 -П4М5

Поставщики и объемы вывоза, т		Потребители и объемы завоза						Потенциалы строк
		М1	М2	М3	М4	М5	М6
		92	84	80	112	96	36
П1	144	24	30	42	15	39	21	0
		32	112
П2	148	9	24	30	33	27	29	-2
		76	72
П3	76	24	22	20	45	21	23	-8
		52	24
П4	132	11	36	27	40	30	8	-5
		92	4	36
Потенциалы столбцов		16	30	32	15	29	13

Шифры клеток	П1 -М1	П1 -М3	П1 -М5	П1 -М6	П2 -М1	П2 -М2	П2 -М4	П2 -М6	П3 -М1	П3 -М3	П3 -М4	П3 -М6	П4 -М2	П4 -М4	П4 -М5
Суммы потенциалов	16	32	29	13	14	28	13	11	8	24	7	5	25	10	24
Значение элементов	24	42	39	21	9	24	33	29	24	20	45	23	36	40	30
Характеристики	8	10	10	8	-5	-4	20	18	16	-4	38	18	11	30	6

+П2М1 -П2М3 +П4М3 -П4М1

Поставщики и объемы вывоза, т		Потребители и объемы завоза						Потенциалы строк
		М1	М2	М3	М4	М5	М6
		92	84	80	112	96	36
П1	144	24	30	42	15	39	21	0
		32	112
П2	148	9	24	30	33	27	29	-2
		76	72
П3	76	24	22	20	45	21	23	-8
		52	24
П4	132	11	36	27	40	30	8	0
		16	80	36
Потенциалы столбцов		11	30	27	15	29	8

Шифры клеток	П1 -М1	П1 -М3	П1 -М5	П1 -М6	П2 -М2	П2 -М3	П2 -М4	П2 -М6	П3 -М1	П3 -М3	П3 -М4	П3 -М6	П4 -М2	П4 -М4	П4 -М5
Суммы потенциалов	11	27	29	8	28	25	13	6	3	19	7	0	30	15	29
Значение элементов	24	42	39	21	24	30	33	29	24	20	45	23	36	40	30
Характеристики	13	15	10	13	-4	5	20	23	21	1	38	23	6	25	1

+П2М2 -П2М5 +П3М5 -П3М2

Поставщики и объемы вывоза, т		Потребители и объемы завоза						Потенциалы строк
		М1	М2	М3	М4	М5	М6
		92	84	80	112	96	36
П1	144	24	30	42	15	39	21	0
		32	112
П2	148	9	24	30	33	27	29	-6
		76	52	20

П3	76	24	22	20	45	21	23	-12
		76
П4	132	11	36	27	40	30	8	-4
		16	80	36
Потенциалы столбцов		15	30	31	15	33	12

Шифры клеток	П1 -М1	П1 -М3	П1 -М5	П1 -М6	П2 -М3	П2 -М4	П2 -М6	П3 -М1	П3 -М2	П3 -М3	П3 -М4	П3 -М6	П4 -М2	П4 -М4	П4 -М5
Суммы потенциалов	15	31	33	12	25	9	6	3	18	19	3	0	26	11	29
Значение элементов	24	42	39	21	30	33	29	24	22	20	45	23	36	40	30
Характеристики	9	11	6	9	5	24	23	21	4	1	42	23	10	29	1

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

Объем работ составит: 32 * 30 + 112 * 15 + 76 * 9 + 52 * 24 + 20 * 27 + 76 * 21 + 16 * 11 + 80 * 27 + 36 * 8 = 9332 ткм.