Математические методы в экономике
Главная | Симплексный метод решения задач линейного программирования | Регистрация | Вход
 
Пятница, 24.11.2017, 23:07
Приветствую Вас Гость
Главное меню
Статистика
Форма входа

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

В предыдущем параграфе для решения ОЗЛП с двумя переменными был применен графический метод. В общем случае ОЗЛП решается с помощью симплекс-метода, к изложению которого мы сейчас и переходим. Рассмотрим ОЗЛП с системой ограничений в следующей форме:

Для реализации СМ необходимо 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 по векторам нового базиса и числа F0j по следующим формулам:

где k – номер направляющего столбца (вектор Ak вводится в базис), r – номер направляющей строки (Ar исключается из базиса).

Полученные данные записываются в новую симплекс–таблицу:

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


Copyright MyCorp © 2017Бесплатный конструктор сайтов - uCoz