Симплексный метод решения задач линейного программирования
В предыдущем параграфе для решения ОЗЛП с двумя переменными был применен графический метод. В общем случае ОЗЛП решается с помощью симплекс-метода, к изложению которого мы сейчас и переходим. Рассмотрим ОЗЛП с системой ограничений в следующей форме:
Для реализации СМ необходимо 3 основных момента.
Необходимо отыскать способ отыскания исходного допустимого решения. Должен быть описан механизм перехода от одного допустимого решения к другому (к другой вершине многоугольника). Должен быть сформулирован критерий, с помощью которого можно проверить на оптимальность: остановить процесс поиска или идти дальше.
Если ввести в систему ограничений дополнительные переменные
xn+1,xn+2,...,xn+m
по формулам
то система ограничений преобразуется в систему уравнений
Алгоритм решения задачи.
1. Стандартная задача ЛП сводится к основной задаче.
F = c1x1+…+cnxn → max
2. Определяется начальное допустимое решение. Для этого запишем систему ограничений в векторной форме: x1A1+x2A2+...+xnAn+xn+1An+1+...+xn+mAn+m = A0, где
An+1...An+m - линейно-независимые векторы m-мерного пространства. Первоначальное допустимое решение: x0 = (0,...0,b1...bm)
3. По данным задачи составляется симплекс-таблица
В (m+1)-й строке в столбцах векторов Аj записываются значения
ciaij - значение целевой функции, если вместо неизвестных подставить коэффициенты разложения j-го вектора по векторам базиса. ∆ - называют оценками плана.
Значение F0 равно скалярному произведению вектора А0 на вектор C∆
4. Полученное допустимое решение проверяется на оптимальность (в случае максимизации).
Используются теоремы:
Теорема 1: если для некоторого опорного плана x* выполняются неравенства ∆j≥0, то этот план оптимальный.
Теорема 2: если для опорного плана X задачи ЛП существует хотябы один элемент j, для которого ∆j<0 и среди коэффициентов разложения j-го вектора есть хотя бы один aij>0, то существует такой опорный план x', для которого F(x')>F(x).
Если хотя бы для одной отрицательной оценки ∆j < 0 коэффициенты разложения aij соответствующего вектора не положительные, то линейная функция не ограничена на многограннике решений, и следовательно, задача не имеет решения.
Наличие оптимальности проверяется по следующему признаку:
Согласно теореме выясняется, имеется ли хотя бы одно отрицательное ∆j (ЦФ исследуется на максимум). Если нет, то найденное решение является оптимальным.
Если же среди чисел ∆j имеются отрицатльные, то либо устанавливается неразрешимость задачи, либо переходят к новому допустимому решению.
В случае исследования целевой функции на минимум допустимое решение является оптимальным, если все разности ∆j ≤ 0 . Если хотя бы одно ∆j > 0, тогда в базис включается вектор, соответствующий этой оценке, и вычисляется новое допустимое решение, при котором линейная целевая функция будет принимать меньшее значение.
Если положительных элементов в последней строке симплекс-таблицы, несколько, то в базис должен быть включен вектор, которому соответствует максимальный положительный ∆j > 0.
Если имеется несколько одинаковых максимальных значений ∆j, то из соответствующих им векторов включается в базис вектор, которому соответствует минимальное Сj.
Если хотя бы для одной положительной оценки (∆j > 0) коэффициенты разложения aij соответствующего вектора неположительные, то линейная функция не ограничена на многограннике решений, и следовательно, задача не имеет решения.
Находится направляющий столбец и направляющая строка. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом ∆j, а направляющая строка – минимальным отношением компонент столбца вектора А0 к положительным компонентам направляющего столбца направляющая строка
Выбор максимального по модулю отрицательного элемента ∆j означает включение в базис переменной, увеличение которой приводит к максимальному росту ЦФ
6. Определяются положительные компоненты нового допустимого решения и коэффициенты разложения векторов Aj по векторам нового базиса и числа F0 ∆j по следующим формулам:
где k – номер направляющего столбца (вектор Ak вводится в базис), r – номер направляющей строки (Ar исключается из базиса).
Полученные данные записываются в новую симплекс–таблицу:
7. Проверяют найденное допустимое решение на оптимальность. Если решение не является оптимальным то возвращаются к п.5, если решение оптимальное или установлена неразрешимость задачи процесс решения заканчивается.
|