Решение задач линейного программирования методом больших штрафов

Метод больших штрафов также называется методом искусственного базиса (М-методом)

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

(10.24)

при условиях

(10.25)

(10.26)

где

;

– единичные векторы, образующие базис m-мерного пространства.

Пусть . Допустим, что

Теорема 10.5 (условие оптимальности). Опорный план задачи (10.24) – (10.26) является оптимальным, если для любого j, .

Теорема 10.6. Если опорный план Х0 задачи (10.24) – (10.26) невырожден и , но среди чисел есть положительные (не все ), то существует такой опорный план , что .

Теорема 10.7. Если для некоторого j = k и среди чисел нет положительных , то целевая функция (10.24) задачи (10.24) – (10.26) не ограничена на множестве ее планов.

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

1. Находят опорный план.

2. Составляют симплекс-таблицу (см. табл. 10.3).

Базисные переменные

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

Таблица 10.3

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

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

5. По формулам

определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов по векторам нового базиса и числа . Все эти числа записываются в новой симплекс таблице (табл. 10.4).

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

Таблица 10.4

Базисные переменные

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

М-метод.

Выше было показано, что если ограничения задачи линейного программирования содержат единичную матрицу порядка m (среди n векторов Aj имеется m единичных), то тем самым при неотрицательных правых частях уравнений определен первоначальный опорный план, исходя из которого с помощью симплексного метода находится оптимальный план. Однако для многих задач линейного программирования, записанных в канонической форме и имеющих опорные планы, среди векторов Aj не всегда есть m единичных. Рассмотрим такую задачу.

Пусть требуется найти максимум функции

(10.27)

при условиях

(10.28)

xj  0, j=1, 2,…, n, (10.29)

где  0 (i = 1, 2,…, m) m<n и среди векторов (j = 1, 2,…, n) нет m единичных.

Задача, состоящая в определении максимального значения функции

(10.30)

при условиях

(10.31)

, j=1,2,…, n+m,

где M – некоторое достаточно большое положительное число, конкретное значение которого обычно не задается, называется расширенной задачей (Т-задачей) по отношению к задаче (10.27) – (10.29).

Выражение называется М–функцией.

Т- задача имеет опорный план

который определяется системой единичных векторов , образующих базис пространства , который называется искусственным. Сами векторы, так же как и переменные (i = 1, 2,…, m), называются искусственными. Так как Т-задача имеет опорный план, то ее решение может быть найдено симплексным методом.

Теорема 10.8. Если в оптимальном плане Т-задачи значения искусственных переменных (, то план является оптимальным планом задачи (10.27) – (10.29). Если хотя бы одна из переменных (, то система ограничений исходной задачи несовместна. Если же , то исходная задача также неразрешима, причем либо , либо условия задачи противоречивы.

Дата добавления: 2015-04-29