14. Сімплекс-метод. Алгоритм симплексного метода.

Сімплекс-метод – метод направленого перехода от одного опорного решения к другому, позволяющий за наименьшее число шагов найти оптим.решение линейн.оптимиз. задачи или доказать, что оно не существует, когда ОДР пустое множество,либо ц.ф. стремится к ∞.

Алгоритм симплекс-метода

1. Представить математическую модель в каноническом виде.

2. Определить исходный опорный план.

3. Заполнение симплекс-таблицы.

4. Анализ исходного опорного решения на оптимальность.

А) вычеслить значение ц.ф., соответствующее данному опорному решению.

F= i *

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

i * - , (j=1;n)

В) анализ получения оценок выделяет следующие варианты:

- если все оценки не отрицательные, то опорное решение является оптимальным;

- если среди оценок существуют отрицательные и хотя бы один из них соответствующих столбцов не содержит положительных элементов, то ОДР не ограничено и Fmax→∞.

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

5. Переход к новому опорному плану.

А) среди отрицательных оценок выбирается наименьшая соответствующая разрешающему столбцу с номером р.

Б) в разрешающем столбце выбираются положительные значения для каждого из которых вычесляются отношения

В) из полученных соотношений выбирается наименьшее соответ. разрешающей строке с номером r.

На пересечении разрешительного столбца и строки лежит разр. элемент.

Примечание:

Разрешающая строка соответствует переменой, которая выводится из базиса, разрешающий столбец переменной,которая вводится в базис.

Г) Заполнение симплекс-таблицы начинается со строки соответствующей разрешающей. Ее элементы вычесляются.

Оставшиеся элементы разрешающего столбца = 0.

Оставшиеся элементы таблицы вычесляются по формуле:

Записываются базисные переменные в соответствии с полученными коэф. или на осоновании значений p,r.

Вычесляя оценки для новой симплекс-таблицы, новое опорное решение оценивается на оптимальность.

18. Алгоритм побудови моделі двоїстої задачі.

0)Упорядочить прямую задачу;1)Вводятся переменные двойственно задачи Yij, количество которых равно количество ограничений прямой задачи.

2)Построение ц.ф.. Ц.ф. двойственной задачи линейная и в качестве коэффициента при переменных правой части (двойственной) содержит системы ограничений прямой – Bi, при чём направление опти-ции изменяется на противоположный (Если прямая задача направлена к максимуму, то двойственная ей к минимуму и наоборот);

3) С-ма огранич состоит из 3х осн элементов: левая часть, правая ч. и знак неравенства. А)Матрица коэффициентов левых частей ограничений двойственной задачи (а11, а21…) является транспонированной к соответственной матрице прямой задачи;Б)В качестве правых частей системы ограничений двойственной задачи берутся соответствующие коэффициенты ц.ф. прямой задачи;

В)Знаки неравенств двойственной задачи соответствуют упорядоченной форме (max - =; ≤; Min- =;≥). При этом если на і-переменную прямой задачи наложено условие неотрицательности, то j-ограничение двойственной задачи – неравенство, а если не наложено, то равенство;

Если і-ограничение прямой задачи – неравенство, то на j-переменную двойственной задачи накладывается условие неравенства и наоборот.