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

Симплекс-метод является методом направленного перебора решений системы (2.4.2) – (2.4.3). Каждое следующее решение улучшает значение целевой функции.

Симплекс-метод включает два этапа:

1) определение начального решения, удовлетворяющего ограничениям
(2.4.2), (2.4.3);

2) последовательное улучшение начального решения и получение оптимального решения задачи (2.4.1) – (2.4.3).

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

Система (2.4.2) содержит линейно независимых уравнений, и их число меньше числа неизвестных, входящих в систему, следовательно, систему (2.4.2) можно разрешить относительно неизвестных, например , выразив их через остальные неизвестные

(Коэффициенты в полученной системе, естественно, отличны от коэффициентов системы (2.4.2), но для простоты обозначены той же буквой).

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

После указанных преобразований задача (2.4.1) – (2.4.3) запишется в следующем виде:

(2.5.1)

(2.5.2)(2.5.3)

Форма записи (2.5.1) – (2.5.3) называется стандартной.

Алгоритм решения системы (2.5.1) — (2.5.3) симплекс-методом

Шаг 1. Получение начального решения.

Выбираются переменных, называемых базисными и обладающих следующим свойством: они входят с коэффициентом 1 только в одно уравнение и с коэффициентом 0 в остальные уравнения системы (2.5.2).

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

Все свободные переменные полагаются равными 0, а базисные переменные – равные правым частям соответствующих ограничений системы (2.5.2).

Пусть базисных переменных – это переменные (в противном случае переменные всегда можно перенумеровать). Тогда начальное решение имеет следующий вид:

.

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

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

(Значения коэффициентов , естественно, отличны от значений коэффициентов в формуле (2.5.1), но для простоты обозначены той же буквой.)

Переход к шагу 3.

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

Составляется симплекс-таблица (табл. 2.5.1).

Таблица 2.5.1

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

В левой колонке симплекс-таблицы находятся базисные переменные, в колонке свободных членов – правые части соответствующих ограничений. В -й строке, -м столбце стоит коэффициент при -й переменной в -м ограничении (2.5.2), . В последней строке (-строке) стоит коэффициент с противоположным знаком при -й переменной в целевой функции . В последнем столбце последней строки стоит значение свободного члена, входящего в целевую функцию.

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

Переход к шагу 4.

Шаг 4. Получение нового решения.

Шаг 4.1. Выбор переменной, вводимой в список базисных переменных.

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

Шаг 4.2. Выбор переменной, выводимой из списка базисных переменных.

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

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

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

(2.5.4)(2.5.5)

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

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

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

Поясним на примерах некоторые шаги алгоритма.

Дата добавления: 2014-01-04