11) Алгоритм симплексного метода с искусственным базисом.

Применяется в , когда затруднительно найти первоначальный опорный план исходной задачи ЛП, записанной в канонической форме. Метод заключается в применении правил симплекс-метода к так называемой М-задаче. Она получается из исходной добавлением к левой части системы уравнения в канонической форме исходной ЗЛП таких искусственных единичных векторов с соответствующими неотрицат искусственными переменами, чтобы вновь полученная матрица содержала систему единичных линейно-зависимых векторов. В линейную форму исходной задачи добавляется в случае ее максимизации слагаемое, представляющее собой произведение числа (-М) на сумму искусственных переменных, где М – достаточно большое положительное число. В полученной задаче первоначальный опорный план очевиден. При применении к этой задаче симплекс-метода оценки   теперь будут зависеть от «буквы М». Для сравнения оценок нужно помнить, что М – достаточно большое положит число, поэтому из базиса будут выводиться в первую очередь искусственные переменные. В процессе решения М-задачи следует вычеркивать в симплекс-таблице искусствен векторы по мере их выхода из базиса. Если все искусствен векторы вышли из базиса, то получаем исходную задачу. Если оптимальное решение М-задачи содержит искусствен векторы или М-задача неразрешима, то исходная задача также неразрешима. Путем преобразований число вводимых переменных, составляющих искусственный базис, может быть уменьшено до одной.

12) Особые случаи решения злп симплексным методом

1ый особый случай решения ЗЛП: решение не единственное (линия уровня параллельна одной из линий на границе области допустимых решений). Это означает, что задача имеет бесконечное множество оптимальных решений. Его задают координаты точек отрезка с угловыми точками. 2ой особый случай решения ЗЛП – задача не имеет решения, т.к. область решений не ограничена сверху. 3ий особый случай решения ЗЛП – задача не имеет решения, т.к множество планов пусто, нет ни одной общей точки

16) Двойственные оценки в ЗЛП, интервалы устойчивости двойственных оценок. Свойства дв оценок и их использование для анализа оптимальных решений. Значения переменных в оптимальном решении двойственной задачи- это оценки влияния свободных членов системы ограничений – неравенств прямой задачи на величину . Свойства: 1) оценка как мера дефицитности ресурсов и продукции. Данное свойство вытекает из 1 соотношения 2 теоремы двойственности . если . Если ресурс в оптимальном плане используется не полностью то его двойств оценка равна 0. этот ресурс недифицитен, не влияет на план выпуска продукции. Отличная от 0 двойственная оценка свидетельствует о том что ресурс в оптимальном плане дифицитен. Дальнейшее увеличение целевой функции возможно только при увеличении запасов дифицитных ресурсов. Чем больши величина двойственной оценки тем острее дефицитность данного рес-са. 2) дв-ные оценки как инструмент эффективности отдельных вариантов плана. Данное свойство основано на 2 соотношении 2 теоремы двойств. , если Если изделие вошло в оптимальный план то в двойственных оценках оно не убыточно, т.е. стоимость ресурсов, затраченных на производство ед изделия равна цене изделия. Если стоимость ресурсов больше цены, то изделие убыточно и оно не войдет в оптимальный план. 3) Оценка как мере влияния ограничений на ЦФ. Это свойство вытекает из теоремы об оценках . Используя этот метод можно определить не решая задачу заново симплексным методом как изменится значение ЦФ прямой задачи при изменении правых частей ограничений, т.е. можно определить как изменится стоимость выпускаемой продукции при увеличении или уменьшении запасов ресурсов. Данным свойством можно пользоваться только в пределах интервалов устойчивости двойственных оценок. Интервалы устойчивости можно найти в протоколе «устойчивость» поиска решений. Интервалы устойчивости показывают на сколько ед можно увеличить или уменьшить запас ресурсов, чтобы его цена при этом не изменилась. Изменение запасов ресурсов приведет к изменению общей стоимости продукции и к изменению плана выпуска. Однако структура плана при этом не меняется. 4) Дв оценки, как инструмент балансирования суммарных затрат и результатов. Это свойство основано на 1 теореме двойственности. При любом плане выпуска продукции , затраты на выпуск продукции больше дохода. Разница между f(X) и g(Y) наз производственными потерями от неоптимального плана. При оптимальном и произ потери =0.