183653 (Решение задач симплекс-методом), страница 2

Как видно из таблицы, оптимальный план предусматривает выпуск про­дукции П₁ 27 ед. (х₁ = 27), П₃ 92 ед. (х₃ = 92), дополнительного неизвестного П₄ 1 ед. (х₄ = 1). П₂ и дополнительные неизвестные в план не вошли, следовательно, х₂ = 0, х₅ = 0 х₆ = 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

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

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

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

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

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

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

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

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

ЗАДАЧА 2

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

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

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

1х₁ + 1х₂ + 0х₃ ≥ 50

4х₁ + 1х₂ + 3х₃ ≥ 140

1х₁ + 4х₂ + 1х₃ ≥ 127

0х₁ + 3х₂ + 2х₃ ≥ 80

F = 8х₁ + 12х₂ + 10х₃ = min

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

-1х₁ - 1х₂ - 0х₃ ≥ -50

-4х₁ - 1х₂ - 3х₃ ≥ -140

-1х₁ - 4х₂ - 1х₃ ≥ -127

0х₁ - 3х₂ - 2х₃ ≥ -80

F = 8х₁ + 12х₂ + 10х₃ = min

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

-50 = -1х₁ - 1х₂ - 0х₃ + 1х₄ + 0х₅ + 0х₆ + 0х₇

-140 = -4х₁ - 1х₂ - 3х₃ + 0х₄ + 1х₅ + 0х₆ + 0х₇

-127 = -1х₁ - 4х₂ - 1х₃ + 0х₄ + 0х₅ + 1х₆ + 0х₇

-80 = 0х₁ - 3х₂ - 2х₃ + 0х₄ + 0х₅ + 0х₆ + 1х₇

F = 8х₁ + 12х₂ + 10х₃ + 0х₄ + 0х₅ + 0х₆ + 0х₇ = min

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

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

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

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

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

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

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

Столбцы х₁, х₂, х₃ будут иметь следующие отно­шения:

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

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

1-я итерация

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

2-я итерация

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

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