Общая идея симплексного метода

Основная теорема линейного программирования может навести на мысль, что можно найти все угловые точки многогранника допустимых планов и сравнить в них значения целевой функции. Пусть задача записана в канонической форме и содержит m равенств с n переменными (m < n),

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

.

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

Базисное решение (план). Так называют решение одной из выделенных групп уравнений, если для этой группы оно является единственным. Соответствующие переменных называют базисными, а переменных, которым были присвоены нулевые значения, небазисными, или свободными.

Опорное базисное решение (опорный план). Так называют базисное решение, если все базисных переменных неотрицательны.

Недопустимое базисное решение. Имеет место если хоть одна базисная переменная отрицательна.

Вырожденное базисное решение. Имеет место тогда, когда хоть одна базисная переменная нулевая.

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

Алгоритм симплекс-метода нахождения оптимального плана всегда начинается с некоторого допустимого базисного решения. Далее следует проверка, можно ли улучшить значение целевой функции, если увеличить одну из небазисных (нулевых) переменных, ввести ее в базис. Если такой переменной нет, то оптимальное решение найдено. Если есть, то необходимо перейти к новому, лучшему (или хотя бы не худшему) базисному решению. Но базисное решение содержит точно m переменных, поэтому после определения переменной, вводимой в базис, необходимо определить исключаемую из базиса переменную.

Каждый такой цикл преобразования называют итерациями, а методы вычислений, основанные на последовательных итерациях,– итерационными методами.

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

Построение опорного плана

Рассмотрим сначала частный случай ограничений типа «меньше или равно», использованных при построении модели оптимального планирования производства. После приведения к каноническому виду система ограничений будет:

Про такую систему говорят, что она имеет предпочтительный вид, поскольку выполняются два условия:

1. Правые части ограничений-равенств неотрицательны (для рассматриваемой задачи это объемы имеющихся ресурсов).

2. Каждое ограничение содержит предпочтительную переменную, входящую в него с коэффициентом, равным единице, и не входящую в остальные ограничения (для приведенного примера это , где .

Для такой системы ограничений всегда можно найти опорное решение, если принять предпочтительные переменные за базисные, а остальные считать свободными и приравнять нулю. Тогда базисные переменные равны правым частям ограничений-равенств и опорный план будет:

.

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

В общем случае любую задачу линейного программирования можно преобразовать к каноническому виду:

Без ограничения общности можно считать, что правые части ограничений-равенств неотрицательны, иначе соответствующие ограничения было бы достаточно умножить на –1, но предполагать предпочтительный вид даже для отдельных ограничений оснований нет.

Наиболее общим способом построения опорного плана является использование искусственных переменных , которые добавляются ко всем левым частям ограничений-равенств, не имеющих предпочтительного вида. В частности, для модели формирования минимальной продовольственной корзины получим:

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

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

Такой метод называют M-методом, или методом больших штрафов, а полученную задачу – M-задачей, соответствующей исходной. Естественно ожидать, что все искусственные переменные в процессе оптимизации получат нулевые значения. Однако, если исходная задача несовместна, то при любом штрафе исключить все искусственные переменные не удастся. Например, если задачу оптимального планирования производства дополнить условиями по минимальным объемам производства отдельных видов продукции, то при недостатке наличных ресурсов придется приобретать их по любой цене. Зато сразу видно, что задача не имеет допустимого решения и более того видно, сколько и каких именно ресурсов не хватает.

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

При компьютерных вычислениях всегда имеют место ошибки округления, особенно, когда в операциях сложения или вычитания одновременно участвуют и большие, и малые числа. В этом легко убедиться экспериментом, вычисляя, например, значение 10¹⁵ + 1. Скорее всего, единица просто не будет прибавлена. Если это не так, то достаточно увеличить первое или уменьшить второе число. Поэтому лучше не следовать бездумно теоретическому требованию о «большом значении» M, а назначать его исходя из «разумной достаточности». Если же в решение необоснованно войдет искусственная переменная, то соответствующий ей штраф можно увеличить.

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

Признак оптимальности опорного плана

Если начальный опорный план найден, то далее следует проверить, можно ли улучшить значение целевой функции, если увеличить одну из небазисных (нулевых) переменных и ввести ее в базис.

Пусть задача линейного программирования преобразована к канонической форме и ее ограничения имеют предпочтительный вид:

Выражая базисные переменные через свободные, получим

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

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

, , …, , ;

а также для коэффициентов целевой функции при базисных переменных

.

Тогда целевая функция может быть представлена как

,

а если ввести обозначения для входящих в нее слагаемых

и ,

то окончательно получим

.

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

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

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

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

Переход к нехудшему опорному плану

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

В столбце БП перечислены все переменные, входящие в текущий базис, в столбцах и – коэффициенты функционала при базисных переменных и сами значения этих переменных.