Решение задач симплекс-методом
1
ЗАДАЧА 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>, a>12>..., а>33>, где а - норма расхода, первая подстрочная 1 – номер ресурса, вторая подстрочная 1, 2, 3 – номер ассортиментной группы конфет.
Наличие каждого ресурса для производства всех, групп конфет принимается как известная величина и обозначается символами в>1>, в>2>, в>3>.
Прибыль на продукцию также принимается как известная величина и обозначается символами c>1>, c>2>, с>3>.
Перечисленные параметры являются величинами известными и выражаются в единых единицах измерения, кроме прибыли. Прибыль или другой какой показатель, являющийся критерием оптимальности, выражается в единицах измерения дохода /например, прибыли/, получаемого от производства единицы продукции в денежном или другом каком-нибудь выражении.
Поскольку решение задачи заключается в поиске такого плана производства, который обеспечивал бы в принятых условиях наибольший доход, принимаются те величины, которые являются неизвестными и обозначающими количества каждой группы конфет, включаемых в план производства: x>1> для M>1>; х>2> для М>2>; х>3> для М>3>.
Экономико-математическая модель в символическом виде.
Система ограничений
Целевая функция /суммарный доход/ F = с>1>х>1 >+ с>2>х>2> + с>3>х>3> = мах
Условия неотрицательности неизвестных х>1> ≥ 0, х>2> ≥ 0, х>3> ≥ 0
Символическая модель, наполненная численной информацией, будет иметь следующий вид:
2x>1> + 4x>2> + 3x>3> ≤ 266
1x>1> + 3x>2> + 4x>3> ≤ 200
3x>1> + 2x>2> + 1x>3> ≤ 303
Прибыль от реализации выпускаемой продукции должна быть максимальной, то есть F = 20х>1> + 24х>2> + 28х>3> = max;
Решение задачи.
Для решения задачи симплексным методом неравенства преобразуются в эквивалентные равенства путем добавления в каждое неравенство по одному дополнительному неизвестному с коэффициентом + 1 и нулевым уравнением прибыли. Для удобства расчетов левые и правые части уравнений меняются местами. В этом случае исходные неравенства примут вид симплексных уравнений:
266 = 2x>1> + 4x>2> + 3x>3> + 1x>4>
200 = 1x>1> + 3x>2> + 4x>3> + 1x>5>
303 = 3x>1> + 2х>2> + 1x>3> + 1x>6>
F = 20х>1> + 24х>2> + 28х>3> + 0x>4> + 0x>5> + 0x>6>
Коэффициенты при неизвестных записываются в симплексной таблице, в которой выполняются расчеты и отражаются полученные результаты.
Исходная таблица
|
c>j> |
p>0> |
x>0> |
20 |
24 |
28 |
0 |
0 |
0 |
|
x>1> |
х>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 |
|
Z>j> - C>j> |
0 |
-20 |
-24 |
-28 |
0 |
0 |
0 |
В столбцах таблицы записывают: в первом (C>j>) – прибыль единицы продукции, которая вводится в план выпуска; во втором (Р>0>) – неизвестные, включаемые в план; в третьем (Х>0>) – свободные величины; в остальных – коэффициенты при неизвестных уравнений. В верхней части этих столбцов отражаются коэффициенты при неизвестных целевой функции.
В нижней строке (целевой) записываются получаемые расчетным путем показатели: в столбце х>0> – суммарная прибыль планового выпуска, в остальных столбцах – прибыль единицы продукции с отрицательным знаком.
В последних трех столбцах коэффициенты при дополнительных неизвестных, равные единице, расположены по диагонали. Эта часть таблицы, называемая единичной подматрицей, необходима для вычислительных и аналитических целей.
При решении задач на максимум целевой функции наличие в целевой строке отрицательных чисел указывает на возможность начала или продолжения решения задачи. Порядок решения таков: из отрицательных чисел целевой строки выбирается наибольшее по модулю. Столбец, в котором оно находится, принимается за ключевой (или разрешающий) и для удобства расчетов выделяется. В нашем примере таким столбцом будет Х>3>, имеющий в целевой строке наибольшую по модулю величину -28.
1-ая итерация
|
c>j> |
p>1> |
x>0> |
x>1> |
х>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 |
|
Z>j> - C>j> |
1400 |
-13 |
-3 |
0 |
0 |
7 |
0 |
Затем элементы столбца Х>0> (свободные величины) делят на соответствующие коэффициенты ключевого столбца и полученные результаты сопоставляют между собой. Строка с наименьшим отношением принимается за ключевую и также для удобства выделяется. В нашем случае 266/3 = 88,7; 200/4 = 50; 303/1 = 303. Наименьшее отношение 50 имеет срока х>5>, она и будет ключевой. Ключевой элемент 4.
Далее элементы таблицы преобразуются и записываются в новую таблицу. Первоначально преобразуют элементы ключевой строки путем деления их на ключевой элемент. Преобразованные элементы записывают в том же самом месте.
В столбцах Р>о> и C>j> занимают место вводимая в план неизвестная х>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-я итерация
|
c>j> |
p>2> |
x>0> |
x>1> |
х>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 |
|
Z>j> - C>j> |
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
Требуется определить минимальную по стоимости смесь сырья для изготовления пищевых концентратов, которые должны содержать питательные вещества (П). Эти вещества содержаться в сырье (М) в различных сочетаниях. Содержание питательных веществ в сырье и готовом продукте, а также цена на каждый вид сырья показаны в таблице.
|
Питательные вещества |
Виды сырья |
Минимальное содержание (единиц) питательных веществ в готовом продукте |
||
|
M>1> |
М>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
Записанные уравнения отличаются от тех, которые нами рассматривались выше, тем, что коэффициенты при основных неизвестных и свободные члены имеют отрицательные знаки.
Решение таких задач производится двойственным симплексным методом. Система симплексных уравнений записывается в таблице.
|
c>j> |
p>0> |
x>0> |
8 |
12 |
10 |
0 |
0 |
0 |
0 |
|
x>1> |
х>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 |
|
Z>j> - C>j> |
0 |
-8 |
-12 |
-10 |
0 |
0 |
0 |
0 |
Элементы целевой строки рассчитывают по обычным правилам и получают отрицательные знаки.
В отличие от вычислительной процедуры основного симплексного метода решение задач двойственным методом выполняется в обратном порядке.
В итоговом столбце свободные числа имеют отрицательные знаки. Это является свидетельством того, что данный план нельзя считать допустимым, так как он противоречит экономическому смыслу. План можно считать допустимым только тогда, когда в итоговом столбце не будет отрицательных чисел.
Ликвидация отрицательных чисел в итоговом столбце начинается с наибольшего по абсолютной величине. В нашем примере таким числом является (-140). Строка х>5>, в которой находится это число, принимается за ключевую и соответственно выделяется.
Определив ключевую строку, находим ключевой столбец. Для этого нужно элементы целевой строки разделить на элементы ключевой строки и из полученных отношений выбрать наименьшее. Столбец, имеющий наименьшее отношение, принимается за ключевой и так же как ключевая строка, выделяется.
Столбцы х>1>, х>2>, х>3> будут иметь следующие отношения:
Наименьшее отношение имеет столбец х>1>, он и будет являться ключевым.
Определив ключевую строку, ключевой столбец и ключевое число, по обычным правилам преобразуются все элементы матрицы и записываются в новой таблице.
1-я итерация
|
c>j> |
p>0> |
x>0> |
18 |
15 |
24 |
0 |
0 |
0 |
0 |
|
x>1> |
х>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 |
|
Z>j> - C>j> |
280 |
0 |
-10 |
-4 |
0 |
-2 |
0 |
0 |
После преобразования элементов в итоговом столбце осталось еще три отрицательных числа в строке х>4>, х>6> и х>7>. Наибольшим по абсолютной величине является число в строке х>6>. Эта строка будет принята за ключевую для последующего расчета. Ключевой столбец определяется по наименьшему отношению элементов целевой строки к элементам ключевой строки. Им будет столбец х>2>. Вводим этот вид сырья в программу вместо неизвестного х>6>. По общим правилам преобразуем элементы матрицы.
2-я итерация
|
c>j> |
p>0> |
x>0> |
x>1> |
х>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 |
|
Z>j> - C>j> |
525.3 |
0.0 |
0.0 |
-3.3 |
0.0 |
-1.3 |
-2.7 |
0.0 |
После преобразования элементов в итоговом столбце осталось еще одно отрицательное число в строке х>7>. Эта строка будет принята за ключевую для последующего расчета. Ключевой столбец определяется по наименьшему отношению элементов целевой строки к элементам ключевой строки. Им будет столбец х>3>. Вводим этот вид сырья в программу вместо неизвестного х>7>. По общим правилам преобразуем элементы матрицы.
В таблице записаны преобразованные числа, полученные на 3-й итерации. В итоговом столбце все отрицательные числа исчезли, значит полученный план является допустимым и одновременно оптимальным. Вывод о том, что план получен оптимальный, позволяют сделать элементы целевой строки. Все они отрицательны или равны нулю, что свидетельствует об оптимальности результата при решении задач на минимум целевой функции.
3-я итерация
|
c>j> |
p>0> |
x>0> |
x>1> |
х>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 |
|
Z>j> - C>j> |
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 - число столбцов). Если план не отвечает этим требованиям, то не для всех строк и столбцов можно рассчитать потенциалы, а без них нельзя проверить план на оптимальность.
Потенциалы строк и столбцов определяются по заполненным клеткам, находящимся на их пересечении.
Элемент заполненной клетки должен равняться сумме потенциалов строки и столбца, на пересечении которых находится эта заполненная клетка.
Для начала вычислений первый потенциал для строки или столбца принимается условно равным нулю, все остальные потенциалы определяются с помощью элементов заполненных клеток.
Обозначив потенциалы
строк u>i>,
потенциалы столбцов Vj,
элементы заполнения клеток
,
можно записать порядок расчета потенциалов
для общего случая.
Из основного требования
= u>i>>
>+ Vj
вытекает:
u>i>
=
- Vj;
Vj
=
- u>i>
Из этих выражений видно, что для расчета потенциала строки необходимо иметь заполненную клетку, в столбце которой потенциал уже определен, а для расчета потенциала столбца нужна заполненная клетка, имеющая потенциал в строке.
Потенциалы показаны в таблице.
После того, как по строкам и столбцам определены потенциалы, с их помощью выясняется, является ли план оптимальным, и если нет, то как его можно улучшить. С этой целью для каждой свободной клетки вычисляется сумма потенциалов строк и столбцов, на пересечении которых находится эта клетка.
Сравнение суммы потенциалов с величиной элемента в свободных клетках позволяет определить, нужно ли заполнять эту клетку или ее нужно оставить свободной.
При решении задач на минимум функционала (в нашем случае на минимум тонно-километровой работы) не заполняются те свободные клетки, в которых сумма потенциалов меньше величины элемента (в нашем случае - расстояния).
Иными словами, если
характеристика, значение которой равно
разности
- (u>i>>
>+ Vj),
положительная, то свободная метка
не заполняется при решении задачи на
минимум функции.
Свободные клетки, имеющие нулевое значение характеристики, показывают на то, что их заполнение приведет к перераспределению поставок, но объем работ (значение функционала) останется неизменным.
Суммы потенциалов, значения элементов и характеристики для незаполненных клеток приведены в таблице.
|
Шифры клеток |
П>1>-М>3> |
П>1>-М>4> |
П>1>-М>5> |
П>1>-M>6> |
П>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 ткм.