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

Решение. Введем необходимые обозначения. Обозначим объем производства продукции П₁ через х₁, продукции П₂ через х₂. Таким образом, формально (математически) план производства (производственная программа) - это вектор . С учетом введенных обозначений математическая модель задачи по критерию "максимум прибыли" имеет вид

при ограничениях

Приведем эту ЗЛП к каноническому виду, введя дополнительные переменные х₃ и х₄:

или

КЗЛП имеет необходимое число единичных столбцов, т.е. обладает очевидным начальным опорным планом (0, 0, 300, 150). Решение осуществляется симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах (табл. 2.2).

В исходной симплекс-таблице с номером 0 строка оценок определяется по приведенной выше формуле (2.22):

Исходный опорный план (0, 0, 300, 150) не является оптимальным, так как среди оценок ∆_j имеются отрицательные. Переход к новому опорному плану осуществим, введя в базис вектор А₂, имеющий минимальную отрицательную оценку. Определяем вектор, выходящий из базиса:

т.е. вектор А₃ следует вывести из базиса. Разрешающим элементом является а₁₂ = 3 (выделен рамкой). Переход к следующей симплекс-таблице осуществляем с помощью преобразований Жордана - Гаусса, при этом рекомендуется пользоваться двумя описанными выше вычислительными процедурами симплексного метода, включая правило прямоугольного треугольника.

Таблица 2.2

Решение ЗЛП в симплекс-таблицах

Второй опорный план (0, 100, 0, 50) не оптимальный; переход к следующему опорному плану осуществим, вводя в базис вектор A₁ и выводя вектор А₄.

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

Максимальное значение целевой функции равно 375.

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

Симплекс-метод с искусственным базисом (М-метод)

Применяется в тех случаях, когда затруднительно найти первоначальный опорный план исходной задачи ЛП, записанной в канонической форме.

М-метод заключается в применении правил симплекс-метода к так называемой М-задаче. Она получается из исходной добавлением к левой части системы уравнений в канонической форме исходной ЗЛП таких искусственных единичных векторов с соответствующими неотрицательными искусственными переменными, чтобы вновь полученная матрица содержала систему единичных линейно-независимых векторов. В линейную форму исходной задачи добавляется в случае ее максимизации слагаемое, представляющее собой произведение числа (-М) на сумму искусственных переменных, где М - достаточно большое положительное число.

В полученной задаче первоначальный опорный план очевиден. При применении к этой задаче симплекс-метода оценки ∆_j теперь будет зависеть "от буквы М". Для сравнения оценок нужно помнить, что М - достаточно большое положительное число, поэтому из базиса будут выводиться в первую очередь искусственные переменные.

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

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

Пример 2.8. Найти максимум целевой функции: при условиях

Решение. Матрица условий содержит только один единичный вектор, добавим еще один искусственный вектор (искусственную неотрицательную переменную у_х в первое ограничение):

Получим следующую М-задачу: найти максимум целевой функции - Му₁ при условиях

М-задачу решаем симплекс-методом. Начальный опорный план (0, 0, 6, 8), решение проводим в симплекс-таблицах (табл. 2.3).

В начальной таблице наименьшее ∆_j соответствует вектору А₁ - он вводится в базис, а искусственный вектор P₁ из базиса выводится, так как ему отвечает наименьшее Q. Столбец, соответствующий Р₁, из дальнейших симплексных таблиц вычеркивается.

Таблица 2.3

Решение М-задачи в симплекс-таблицах

Полученный новый опорный план является опорным планом исходной задачи. Для него все ∆_j > 0, поэтому он является и оптимальным. Таким образом, получен оптимальный план исходной задачи (4, 0, 2) и максимальное значение целевой функции max .

Пример 2.9. Решить ЗЛП:

Решение. Приведем ЗЛП к каноническому виду, перейдя к задаче "на максимум":

Для нахождения опорного плана переходим к М-задаче:

Дальнейшее решение проводим в симплекс-таблицах (табл. 2.4).

Таблица 2.4

Решение ЗЛП М-методом

В симплекс-таблице II получен опорный план исходной ЗЛП; поскольку все симплекс-разности , то этот план является и оптимальным, т.е. (исходные переменные), (дополнительные переменные), при этом

При рассмотрении графического метода выделялись три особых случая решения ЗЛП. В симплекс-методе эти случаи определяются следующим образом.

1. Если найден оптимальный план и оценки всех свободных переменных строго больше нуля, то оптимальный план является единственным', если оценки некоторых свободных переменных в оптимальном плане равны нулю, то этот план будет неединственным, так как ввод этих переменных в базис не нарушает критерия оптимальности и не меняет оптимальное значение целевой функции. В соответствии с этим оптимальный план в табл. 2.2 является единственным, а в табл. 2.3 и 2.4 - несдинственным (первый особый случай).

2. Если в процессе решения ЗЛП М-методом искусственные переменные не выводятся из базиса, это является свидетельством того, что область определения исходной ЗЛП является пустым множеством: в этом случае ЗЛП не имеет решения ввиду противоречивости системы ограничений (второй особый случай).

3. Если в направляющем столбце все элементы a_jk неположительны (см. 2.23), то это свидетельствует о незамкнутости области определения ЗЛП; в этом случае ЗЛП не имеет решения ввиду неограниченности целевой функции (третий особый случай).

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

Однако для корректного и эффективного использования программных средств необходимо знать основы линейного программирования, изложенные выше в данной главе.