Симплекс метод

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

Историческая справка
В работе Л. В. Канторовича «Математические методы организации и планирования производства» (1939) были впервые изложены принципы новой отрасли математики, которая позднее получила название линейного программирования.
Исторически общая задача линейного программирования была впервые поставлена в 1947 году Джорджем Бернардом Данцигом, Маршаллом Вудом и их сотрудниками в департаменте военно-воздушных сил США. В то время эта группа занималась исследованием возможности использования математических и смежных с ними методов для военных задач и проблем планирования. В дальнейшем для развития этих идей в ВВС была организована исследовательская группа под названием Project SCOOP. Первое успешное решение задачи линейного программирования на ЭВМ SEAC было проведено в январе 1952 года.

Основное содержание симплексного метода заключается в следующем:
Указать способ нахождения оптимального опорного решения;
Указать способ перехода от одного опорного решения к другому, на котором значение целевой функции будет ближе к оптимальному, т.е. указать способ улучшения опорного решения;
Задать критерии, которые позволяют своевременно прекратить перебор опорных решений на оптимальном решении или сделать заключение об отсутствии оптимального решения.

Для того, чтобы решить задачу симплексным методом необходимо выполнить следующий алгоритм:
Привести задачу к каноническому виду;
Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений);
Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода;
Если выполняется признак единственности оптимального решения, то решение задачи заканчивается;
Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения.

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

Исходные данные для решения задачи симплекс-методом:
Предприятие выпускает 4 вида изделий, обрабатывая их на 3-х станках. Нормы времени (мин./шт.) на обработку изделий на станках, заданы матрицей A:

Фонд времени работы станков (мин.) задан в матрице B:
Прибыль от продажи каждой единицы изделия (руб./шт.) задана матрицей C:
Целью данной задачи является составление такого плана производства, при котором прибыль предприятия будет максимальной.

Проводим вычисления с помощью табличного симплекс-метода:
Обозначим X1, X2, X3, X4 планируемое количество изделий каждого вида. Тогда искомый план: (X1, X2, X3, X4)
Запишем ограничения плана в виде системы уравнений:

3. Тогда целевая прибыль:
То есть прибыль от выполнения производственного плана должна быть максимальной.

4. Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X5, X6, X7).

5. Примем следующий опорный план:
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
6. Занесем данные в симплекс-таблицу:
! В последнюю строку заносим коэффициенты при целевой функции и само ее значение с обратным знаком;

7. Выбираем в последней строке наибольшее (по модулю) отрицательное число.
Вычислим b = Н / Элементы_выбранного_столбца
Среди вычисленных значений b выбираем наименьшее.

Пересечение выбранных столбца и строки даст нам разрешающий элемент. Меняем базис на переменную соответствующую разрешающему элементу (X5 на X1).

8. Теперь необходимо пересчитать все элементы симплекс-таблицы, кроме столбца b. Вот как это можно сделать:
Сам разрешающий элемент обращается в 1.
Для элементов разрешающей строки – aij(*) = aij / РЭ (то есть каждый элемент делим на значение разрешающего элемента и получаем новые данные).
Для элементов разрешающего столбца – они просто обнуляются.
Остальные элементы таблицы пересчитываем по правилу прямоугольника.

AIJ(*) = AIJ – ( A * B / РЭ )
Берем текущую пересчитываемую ячейку и ячейку с разрешающим элементом. Они образуют противоположные углы прямоугольника. Далее перемножаем значения из ячеек 2-х других углов этого прямоугольника. Это произведение (A * B) делим на разрешающий элемент (РЭ). И вычитаем из текущей пересчитываемой ячейки (aij) то, что получилось. Получаем новое значение - aij(*).

9. Вновь проверяем последнюю строку (c) на наличие отрицательных чисел. Если их нет – оптимальный план найден, переходим к последнему этапу решения задачи. Если есть – план еще не оптимален, и симплекс-таблицу вновь нужно пересчитать.
Так как у нас в последней строке снова имеются отрицательные числа, начинаем новую итерацию вычислений.

10. Так как в последней строке нет отрицательных элементов, это означает, что нами найден оптимальный план производства! А именно: выпускать мы будем те изделия, которые перешли в колонку «Базис» - X1 и X2. Прибыль от производства каждой единицы продукции нам известна (матрица C). Осталось перемножить найденные объемы выпуска изделий 1 и 2 с прибылью на 1 шт., получим итоговую (максимальную!) прибыль при данном плане производства.
ОТВЕТ:
X1 = 32 шт., X2 = 20 шт., X3 = 0 шт., X4 = 0 шт.
P = 48 * 32 + 33 * 20 = 2 196 руб.