2.3 Решение симплекс методом

Получение начального опорного плана

С помощью дополнительных неотрицательных переменных перейдем к системе уравнений:

.

Для нахождения первоначального базисного решения разобьём переменные на две группы: основные и неосновные. Так как определитель, составленный из коэффициентов при дополнительных переменных х₃, х₄, х₅ отличен от нуля, то эти переменные можно взять в качестве основных на первом шаге решения задачи. Столбцы коэффициентов при дополнительных переменных представляют собой единичные векторы, которые линейно независимы. Следовательно, соответствующие этим векторам переменные х₃, х₄, х₅ являются базисными.

Разрешим систему уравнений относительно базисных переменных.

Целевую функцию запишем в виде уравнения F(X)=0-(-15х₁-10x₂).

Положим неосновные переменные равными нулю, т.е. х₁=х₂=0, получим первый опорный план .

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

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

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

Таблица 1.

Определение направляющих столбца и строки

Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине. Направляющий столбец, соответствующий выбранному коэффициенту, показывает, какая переменная на следующем шаге перейдет из свободных в основные (базисные). Так как, то направляющий столбец соответствует переменной х₁. Элементы столбца значений базисных переменных симплексной таблицы делим на соответствующие положительные коэффициенты направляющего столбца. В результате получаем значения столбца И. Из значений столбца И выбираем минимальное. Строка симплексной таблицы, соответствующая минимальному значению И, является направляющей. Она определяет переменную х₄, которая на следующем шаге выйдет из базиса и станет свободной. На пересечении направляющих столбца и строки находится разрешающий элемент, равный 1.

Определение нового опорного плана

Для перехода к, новому опорному плану производится пересчет симплексной таблицы методом Жордана-Гаусса.

Формируем следующую симплексную таблицу. В левом столбце «Базисные переменные» записываем новый базис: вместо основной переменной х₄ записываем переменную х₁. Строку, соответствующую переменной х₁, получаем путем деления всех элементов строки х₄ первой таблицы на разрешающий элемент, равный 1, то есть она остается без изменения. В остальных клетках столбца х₁ проставляем нули. Все остальные элементы, вычисляем по правилу прямоугольника. Аналогично проводятся расчеты по всем строкам таблицы, включая индексную. Далее возвращаемся к этапу - проверка плана на оптимальность. Выполняя последовательно все этапы алгоритма, заполняем таблицы.

Таблица 2.

.

Второй план в задаче тоже не оптимальный, так как в индексной строке еще остается отрицательный коэффициент. Направляющий столбец, соответствующий выбранному коэффициенту, показывает, какая переменная на следующем шаге перейдет из свободных в основные (базисные). Так как, отрицательное число в индексной строке стоит в столбце, который соответствует переменной х₂, то этот столбец будет направляющим. Элементы столбца значений базисных переменных симплексной таблицы делим на соответствующие положительные коэффициенты направляющего столбца. В результате получаем значения столбца И. Из значений столбца И выбираем минимальное. Строка симплексной таблицы, соответствующая минимальному значению И, является направляющей. Она определяет переменную х₃, которая на следующем шаге выйдет из базиса и станет свободной.

Определение нового опорного плана

Для перехода к, новому опорному плану производится пересчет симплексной таблицы методом Жордана-Гаусса. Формируем следующую симплексную таблицу. В левом столбце «Базисные переменные» записываем новый базис: вместо основной переменной х₃ записываем переменную х₂. Строку, соответствующую переменной х₂, получаем путем деления всех элементов строки х₃ первой таблицы на разрешающий элемент. На месте разрешающего элемента в таблице 3 получаем единицу. В остальных клетках столбца х₂ проставляем нули. Все остальные элементы, вычисляем по правилу прямоугольника.

Таблица 3.

На третьем шаге в таблице получен оптимальный план, так как все коэффициенты в индексной строке неотрицательны.

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