Основная идея метода

• 1. На каждом шаге выбирают главный элемент матрицы А — максимальный по модулю коэффициент в матрице a_pq. Строка р — главная строка.
• 2. Для всех строк, кроме главной, вычисляются множители:

• 3. К каждой неглавной строке добавляют главную, умноженную на сомножитель /и,-. В результате q-i столбец — нулевой.
• 4. Вычеркиваем р-ю строку и q-й столбец. В результате получаем матрицу А размерность которой на единицу меньше предыдущей матрицы А.
• 5. Процедуру повторяем с первого шага (п — 1) раз.
• 6. В результате составляем новую систему уравнений из вычеркнутых строк. Полученная матрица не треугольного вида, как в схеме единственного деления Гаусса. Но каждое уравнение содержит разное количество неизвестных: в последнем уравнении — 1 неизвестное, в (п — 1)-м — 2 неизвестных и т. д., в первом уравнении — все п неизвестных. Такой вид преобразованной системы позволяет последовательно находить неизвестные, начиная с последнего уравнения.

Решение той же самой системы методом Гаусса с выбором главного элемента представлено в табл. 4.4. В таблице выделены главные элементы и главные строки.

Таблица 4.4.

Метод Гаусса с выбором главного элемента

Симплекс-метод тесно связан с «методом Гаусса с выбором главного элемента» и основан на ряде утверждений, декларируемых в виде следующих теорем.

Теорема 1. Множество опорных планов — выпукло.

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

То есть оптимальное решение соответствует крайней точке выпуклого множества.

Число опорных планов конечно и определяется числом.

Основная идея симплекс-метода состоит в направленном переборе опорных планов с последовательным уменьшением целевой функции. Принадлежит эта идея двум авторам: американскому математику Дж. Данцигу (1947 г.) и российскому математику Л. В. Канторовичу (1939 г.).

Алгоритм симплекс-метода включает три основных этапа:

I. Выбор начального опорного плана.

II. Переход от начального опорного плана к другому опорному плану с лучшим значением целевой функции.

III. Продолжение поиска опорного плана, улучшающего целевую функцию до достижения оптимального плана. Приведение системы для смежного опорного плана к каноническому виду.

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

Таким образом, механизм симплекс-метода состоит в получении смежных опорных планов.

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

Составим симплекс-таблицу для задачи использования ресурсов (4.3). Для этого запишем задачу в каноническом виде и заменим цель поиска максимум на минимум.

Начальный опорный план и начальная симплекс-таблица приведены в табл. 4.5.

Начальный опорный план

Таблица 4.5.

I. Итак, это начальный опорный план х . Переменные х₃, х₄, х₅ — базисные, х, х, — свободные. Свободные — значит, что они могут принимать любые значения, но чаще их выбирают нулевыми.

Сам опорный план Целевая функция.

II. Нахождение смежного плана.

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

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

Определение. Приращение целевой функции А_к — это величина.

где к е свободным переменным, в нашем примере к = 1, к = 2.

У означает, что суммирование ведется только по базисным пе;

/' е баз ременным, но для столбца свободных переменных.

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

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

Это заключение основывается на следующей лемме.

Лемма 1. Если все приращения симплекс-плана А_к >0, следовательно, текущий опорный план оптимальный.

Симплекс-метод использует следствие этой леммы.

Улучшение целевой функции приносит та свободная переменная х_к, приращение которой отрицательно: А_к < 0.

Так как в текущем опорном плане может быть несколько отрицательных А_к, то выбирать для замены можно любую переменную х_к, но обычно выбирают переменную х_к с минимальным Д₄<0 .

В нашем примере такой переменной является дг,. Строго говоря, эго может быть и х₂, так как Д, < 0.

Другая важнейшая величина симплекс-алгебры — это отношение.

Величины 6_t вычисляются для выбранного &-го столбца (с минимальным значением Д^). Величина 0, определяет, какая из базисных переменных уйдет в свободные на место х_к, при этом отношение вычисляется только для a_jk > 0. Выбирается та переменная х, для которой отношение в₍ минимально.

Теоретической основой этого шага служит лемма.

Лемма 2. Если хотя бы одно из приращений А_к < 0 и при этом среди коэффициентов a_jk есть хотя бы один положительный, то существует опорный план, улучшающий текущий.

Выбранная для данного примера переменная х₅ меняется местами с Х. Элемент, стоящий на пересечении выбранного столбца и выбранной строки, называется ведущим, а вся строка — ведущей строкой.

III. Приведение системы к каноническому виду.

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

'О'.

нулю. Записав второй столбец 0, осуществим эквивалентные преоб;

разования с первой строкой системы.

Преобразование основано на методе Гаусса с выбором главного элемента.

К каждой неглавной строке добавляем главную, умноженную на коэффициент т = ——, где а,_к — главный или ведущий элемент;

к — номер столбца ведущего элемента; р — строка ведущего элемента.

Таким образом, можно записать следующий смежный план:

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

Таблица 4.6.

Симплекс-таблица

Запишем последовательности опорных планов. Шаг 1.

Шаг 2.

Шаг 3.

Шаг 4.

Так как вес приращения положительны (Д₃, А₄ >0), следовательно, опорный план нельзя улучшить.

Замечание

Если на шаге I выбрать А_к = -2 разрешающим столбцом, то стратегия поиска такова:

Оптимум достигнут за 2 шага.