5.Признак оптим-ти опорного плана злп

Если в симплексной таблице, содержащей опорный план, все элементы F-строки (не считая свободного члена) неотрицательны, то данный опорный план является оптимальным.

1. Полученный оптимальный опорный план будет единственным, если все элементы F-строки положительны.

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

ИЛИ

1. Проверка базисного решения на оптимальность.

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

2. Выбор разрешающего столбца.

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

3. Вычисление симплексного отношения и выбор разрешающей строки.

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

4. Выбор разрешающего элемента.

На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент. Обозначим его через bsr.

5. Симплексное преобразование таблицы.

Выполняется точно так же, как и в предыдущем алгоритме. После чего осуществляется переход к шагу 1.

6.Осн.Теор. Двойст-ти в лп и их экон.Сод.

Каждой задаче ЛП соответствует двойственная задача, которая строится по следующим правилам:

1. Если исходная задача на максимум, то двойственная на минимум и наоборот.

2. Коэффициенты целевой функции исходной задачи становятся правыми частями ограничений двойственной задачи. Правые части ограничений исходной задачи становятся коэффициентами целевой функции двойственной задачи.

3. Матрицей коэффициентов двойственной задачи - транспонированная матрица коэффициентов исходной задачи.

5. Число переменных в двойственной задаче равно числу ограничений в исходной задаче. Каждому ограничению исходной задачи соответствует переменная двойственной задачи. Если ограничение исходной задач имеет знак ≥, то соответствующая переменная двойственной задачи неотрицательна. Если ограничение имеет знак =, то соответствующая переменная двойственной задачи – произвольная, наоборот.

Эк. содержание. Вектор x – это вектор выпускаемой продукции, y – двойственные оценки ресурсов прямой задачи. Левая часть ограничений двойственной задачи представляет собой оценку затрат на единицу выпускаемой продукции в двойственных ценах. Прямая задача представляет собой задачу на определение плана, обеспечивающего максимальный выпуск продукции при заданных ценах реализации и ограничениях на ресурсы. Двойственная задача – определение таких оценок ресурсов, в которых стоимость имеющихся ресурсов минимальна, а затраты на производство единицы продукции не меньше цен реализации продукции.

Теорема 1. Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций равны z(x*)=f(y*). Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.

Эк. содержание: план производства и вектор оценок ресурсов оптимальны тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают как инструмент балансирования затрат и результатов.

Теорема 2 (о дополняющей нежесткости). Для того, чтобы планы x* и y* пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:

Эк. содержание: двойственные оценки могут служить мерой дефицитности ресурсов; дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а ресурс избыточный (используемый не полностью) имеет нулевую оценку

Теорема 3 (об оценках). Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения задачи:

Эк. содержание: величина двойственной оценки численно равна изменению целевой функции при изменении соответствующего свободного члена ограничений на единицу