Нахождение решения задачи линейного программирования

Для решения ЗЛП существует универсальный метод – метод последовательного улучшения плана или симплекс-метод, который состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом (М-метод).

Выбор конкретной вычислительной процедуры осуществляется после приведения исходной ЗЛП к каноническому виду.

Для применения симплекс-метода с естественным базисом ЗЛП должна содержать единичную подматрицу размером mxm – в этом случае очевиден начальный опорный план.

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

В первом столбце таблицы "Базис" записывают базисные векторы данного опорного плана. Во втором столбце - коэффициенты целевой функции (с₁, с_2,…, с_m) при базисных переменных (напомним, что в базис входят только векторы, образующую единичную подматрицу). В третьем столбце Р₀ - правая часть ограничений задачи (базисные компоненты плана). Таким образом, перемножая элементы второго столбца таблицы со столбцом Р₀, и суммируя эти произведения, мы получаем значение целевой функции (F₀=с₁*b₁ + с₂*b₂+…+ с_m*b_m).

Первая строка симплексной таблицы содержит коэффициенты целевой функции нашей задачи и остается неизменной на протяжении всего решения (с₁, с_2,…, с_m).

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

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

1. Все оценки , значит на основании признака оптимальности получен оптимальный план.

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

3. для некоторых индексов j, и для каждого такого j по крайней мере одно из чисел , значит можно перейти к новому опорному плану, при котором значение целевой функции увеличится.

Переход от одного опорного плана к другому осуществляется исключением из исходного базиса какого-нибудь из векторов и введением в него нового вектора. В качестве вводимого в базис вектора берётся один из векторов, для которых . Пусть это будет вектор Р_k.

Для определения вектора, подлежащего исключению из базиса находят . Тогда выполняется условие неотрицательности значений опорного плана. Пусть этот минимум достигается при i=r. Тогда из базиса исключают вектор Р_r, а число называют разрешающим элементом.

Элементы новой симплекс-таблицы получают методом Жордана-Гаусса по формулам:

для i = r;

.

Значения нового опорного плана рассчитываются по формулам:

для i = r;

.

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

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

Метод искусственного базиса заключается в том, что для получения единичной подматрицы коэффициентов мы вводим в исходную задачу неотрицательные так называемые искусственные переменные и включаем их в целевую функцию с коэффициентом +М для задачи минимизации и с коэффициентом -М для задачи максимизации, где М>0 - сколь угодно большое число. Полученная задача называется расширенной по отношению к исходной. Искусственные переменные образуют начальное базисное решение. Применив симплекс-метод, необходимо вывести из базиса все искусственные переменные. Если удается доказать (или показать), что искусственные переменные полностью вывести из базиса невозможно, то это означает, что задача не имеет решения, то есть ее ограничения противоречивы.

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