Большая коллекция рефератов

Главная Контакты
Главное меню Главная Биология и химия Хозяйственное право Цифровые устройства Мировая экономика МЭО Немецкий Неопределено Основы права Этика эстетика Не Российское законодательство Нотариат Общениеэтика семья брак Охрана окружающей среды экология Иностранные языки и языкознание История и исторические личности Коммуникации связь цифровые приборы и радиоэлектроника Краеведение и этнография Кулинария и продукты питания Маркетинг реклама и торговля Счетчики Реклама Решение задач симплекс-методом Решение задач симплекс-методом ЗАДАЧА 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

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 ткм.

Все права защищены © 2010