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

Сущность метода

Симплекс-метод – универсальный метод решения задач линейного программирования.

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

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

Количество неизвестных (n) в системе ограничений должно быть больше количества уравнений (m).

Основные этапы решения задачи симплекс-методом

• Приведение задачи к каноническому виду.

• Приведение задачи к допустимому виду (выделение базиса) и преобразование целевой функции.

• Нахождение первого допустимого базисного решения системы ограничений или установление факта ее несовместности.

• Проверка полученного решения на оптимальность. Если решение не оптимально, то

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

П. 4 и 5 повторяются до нахождения оптимального решения

1. Приведение задачи к каноническому виду

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

Неканонический вид: Канонический вид:

2. Приведение задачи к допустимому виду

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

Неизвестные, которые выражаются через остальные неизвестные, называются базисными, а весь набор этих неизвестных – базисом.

Остальные неизвестные называются свободными.

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

Преобразование целевой функции

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

Для исключения базисных переменных из целевой функции нужно умножить первое уравнение системы ограничений на c1, второе на c2, и т.д., сложить полученные произведения и вычесть целевую функцию.

Получим:

где

3. Нахождение первого допустимого базисного решения

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

Базисное решение называется допустимым базисным решением или опорным решением, если значения базисных переменных в нем неотрицательны.

Основная теорема симплекс-метода

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

Таким образом симплекс-метод представляет собой процедуру направленного перебора опорных решений.

4. Проверка решения на оптимальность

Допустимое базисное решение системы ограничений является оптимальным реше-нием задачи линейного программирования тогда и только тогда, когда все ∆j ≥ 0.

Если все ∆j строго положительны, то решение является единственным.

5. Поиск другого допустимого базисного решения

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

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

Пусть задача приведена к виду:

Симплекс-таблица: развернутый вариант

Симплекс-таблица: сокращенный вариант

Симплекс-таблица: алгоритм решения

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

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

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

• Базисная переменная, отвечающая строке ключевого элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу ключевого элемента, вводится в число базисных. Новая таблица строится по следующему алгоритму.

• 4а. в обозначениях строк и столбцов переменная, вводимая в базис и переменная, выводимая из него, меняются местами;

• 4б. на месте ключевого элемента записываем обратное ему число;

• 4в. ключевую строку (за исключением ключевого элемента) делим на ключевой элемент; полученную строку вписываем на место ключевой;

• 4г. ключевой столбец (за исключением ключевого элемента) делим на ключевой элемент с противоположным знаком; полученный столбец вписываем на место ключевого;

• 4д. все остальные элементы таблицы, включая строку оценок и столбец свободных членов, пересчитываем по так называемому «правилу прямоугольника»:

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

• 5. Новая симплекс-таблица отвечает новому допустимому базисному решению. Проверяем новое решение на оптимальность, если решение не оптимально, то повторяем алгоритм.

Пример

Для производства четырех видов изделий A1 , A2 , A3 , A4 завод должен использовать три вида сырья I, II, III. Требуется составить план выпуска, обеспечивающий максимальную прибыль.

Математическая модель задачи:

Приведение задачи к каноническому виду:

Примем за базисные переменные x5, x6, x7.

Тогда первое опорное решение:

(0; 0; 0; 0; 1000; 600; 150).

Пример. 1 шаг симплекс-метода, развернутая таблица.

Пример. 1 шаг симплекс-метода, сокращенная таблица.

Базисное решение (0; 0; 0; 0; 1000; 600; 150).

Поиск ключевой строки:

Выводим из базиса переменную x7 и вводим переменную x1

Пример. 2 шаг симплекс-метода.

Базисное решение (150; 0; 0; 0; 250; 0; 0).

Определение ключевой строки:

Выводим из базиса переменную x6 и вводим переменную x2.

Пример. 3 шаг симплекс-метода.

Базисное решение (150; 0; 0; 0; 250; 0; 0).

Определение ключевой строки:

Выводим из базиса переменную x1 и вводим переменную x4.

Пример. 4 шаг симплекс-метода.

Оптимальное решение:

(0; 225; 0; 150; 475; 0; 0),

при котором Fmax = 1050.

То есть, для получения наибольшей прибыли, равной 1050 денежных единиц, предприятие должно выпустить 225 единиц продукции вида A2, 150 единиц продукции вида A4. Продукцию вида A1 и A3 производить не выгодно. При этом сырье типа II и III будет использовано полностью, а 475 единиц сырья типа I останутся неизрасходованными.