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

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

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

Однако, перед применением симплекс – метода исходную задачу линейно­го программирования следует записать в канонической форме:

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

1. Если требуется найти минимум целевой функции L, то, заменяя функ­цию L на функцию (- L), переходят к задаче максимизации.

2. Если ограничение содержит неравенство со знаком «не более», то от не­го переходят к равенству, добавляя в левую часть ограничения до­полнительную неотрицательную переменную.

3. Если ограничение содержит неравенство со знаком «не менее», то от него переходят к равенству, вычитая из левой части ограничения до­полнительную неотрицательную переменную.

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

Задача линейного программирования, записанная в канони­ческой форме, называется основной задачей линейного програм­ми­рования.

Пусть записана основная задача линейного программирования. Предполо­жим, что все уравнения системы ограничений независимы, т.е. выражают неза­висимые друг от друга условия задачи. Если это не так, то лишние, зависимые от других, уравнения просто исключают. Основную задачу линейного програм­мирования имеет смысл решать только тогда, когда число уравнений системы ограни­чений меньше числа входящих в них неизвестных, т.е. когда: m < n. В против­ном случае, если m = n, то система имеет единственное решение и пропадает смысл задачи максимизации, если же m > n, то система переопределена и, в об­щем случае, не имеет решения.

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

Реализа­ция симплекс-метода включает в себя два крупных этапа:

1. Определение начального решения, удовлетворяющего ограни­чениям.

2. Последовательное улучшение начального решения и получение оптимального решения задачи.

 

Пусть система уравнений ограничений содержит ровно m линейно незави­симых уравнений, и, кроме того, m < n, тогда эту систему можно разрешить относительно m неизвестных, например: , выразив их через осталь­ные (n – m) неизвестные.

После про­ведения таких преобразований основная задача линейного программирования оказывается записанной в стандарт­ном виде:

 

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

 

Шаг 1. Получение начального решения. Выбираются m пере­мен­ных, на­зываемых базисными и обладающих следующим свойст­вом: они входят с коэф­фициентом единица (безразлично, с плюсом или с минусом) только в одно уравнение системы ограничений, и с коэффи­циентом нуль (т.е. не входят) – в остальные уравнения систе­мы ограничений.

Остальные (n – m) переменных называются свободными. При этом все сво­бодные переменные полагают равными нулю, но тогда базисные переменные будут равны свободным членам уравнений системы ограничений.

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

 

 

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

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

Шаг 3. Проверка решения на оптимальность. Составляется начальная симплекс–таблица. В левой колонке этой таблицы помещают базисные пере­менные, а в крайней правой колонке – свободные члены соответствующих урав­нений системы ограничений. На пересечении i -ой строки и j -го столбца разме­щают коэффициент при j -ой переменной в i -ом ограничении. В последней от­черкнутой строке (L – строке) размещают коэффициент при j -ой переменной в целевой функции, взятый с противоположным знаком. В последнем столбце L –строки (т.е. в правом нижнем углу таблицы) помещают значение свободного члена целевой функции со своим знаком. Чаще всего этим значением оказывается нуль. Пример начальной симплекс–таблицы:

 

Базисные переменные	Коэффициенты при переменных				Свободные члены
			…
…	…	…	… …   … …	…	…
			…		0

 

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

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

 

Шаг 4. Получение нового решения.  Этот шаг условно может быть раз­делен на три более мелких шага.

Шаг 4.1. Выбор переменной, вводимой в список базисных перемен­ных.   Просматривается последняя строка симплекс – таблицы. Среди элементов этой строки выбирается максимальный по модулю отрицательный элемент. Столбец, в котором стоит этот элемент, называется разрешающим. Если, напри­мер, это p -ый столбец, то переменная  вводится в список базисных перемен­ных.

Шаг 4.2. Выбор переменной, выводимой из списка базисных перемен­ных.   Находят отношения элементов столбца свободных членов к элементам разрешающего столбца. При этом при делении на отрицательный, или нулевой элемент разрешающего столбца результат деления полагают равным +¥. Среди всех этих отношений находят минимальное. Строка, соответствующая мини­маль­ному отношению, на­зывается разрешающей. Пусть, например, это q -ая строка, тогда базисная переменная  выводит­ся из списка базисных перемен­ных. Элемент симплекс – таблицы, стоящий на пе­ресечении разрешающих строки и столбца называется разрешающим, в рассмотренном случае это будет элемент .

Шаг. 4.3. Выполнение симплекс – преобразования и переход к новой симплекс – таблице. Элемент  новой симплекс-таблицы вычисляется с по­мощью следующего симплекс – преобразования:

 

 

При проведении симплекс–преобразования весьма удобно поль­зо­вать­ся правилом треугольника:

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

 

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

Новое решение имеет следующую структуру: все свободные переменные в нем полагаются равными нулю, а все базисные переменные – свободным чле­нам, стоящим в одной строке с ними. После построения новой симплекс–таб­лицы следует вернуться к выполнению шага 3.

 

ПРИМЕР: Найти оптимальное решение задачи линейного программирования заданной математической моде­лью вида:

 

 

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

 

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

Шаг 1. Базисные переменные: , а свободные: . При этом началь­ное решение имеет вид:  при этом .

Шаг 2. Целевая функция уже выражена через свободные переменные.

Шаг 3. Составим начальную симплекс–таблицу (верхняя в каскаде таблиц):

 

БП					СЧ
	1	0	1	0	4
	0	1	0	1	2
L	-1	-1	0	0	0
	1	0	1	0	4
	0	1	0	1	2
L	0	-1	1	0	4
	1	0	1	0	4
	0	1	0	1	2
L	0	0	1	1	6

 

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

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

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

Составим теперь новую симплекс – таблицу, которая помещена ниже пре­ды­­дущей, начальной таблицы, под общей «шапкой».

Замечание. На практике обычно для экономии места все симплекс – табли­цы располагают ниспадающим каскадом, одна под другой, под общей вер­хней «шапкой».

 

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

Разрешающим в этом случае будет второй столбец. Поскольку , вторая строка будет разрешающей, а ее элемент  разрешающим элементом (аналогично выделен во второй таблице). Учитывая эти результаты, составим новую, третью симплекс – табли­цу и возвратимся к шагу 3.

Последнее решение имеет вид:  при этом .

Это решение оптимально, т.к. все числа, стоящие в L –строке в столбцах свободных переменных неотрицательны. Это решение единственно, т.к. они строго положительны.

Итак, получено оптимальное решение задачи линейного программирова­ния в виде: .