2 Часть

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

2. Вводим в базис неизвестное, находящиеся в разрешающем столбце вместо базисного неизвестного, которое находится в этой же строке. Все пересчитывается методом (Ж-Г)

В результате этих преобразований можно найти оптимальное решение, если иное существует

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

11.Двойственные задачи линейного программирования. Правила построения двойственной задачи по заданной исходной. Виды двойственных задач. Теоремы двойственности. Экономический смысл двойственных задач.

Пусть А- прямая задача, а А*-двойственная задача.

Если в задачи А нужно максимизировать функцию призаданных ограничениях, то в задаче А* находится min целевой функции. Задачи А и А* взаимно двойственны; решая одну из них, автоматически решается другая.

Правила построения двойственных задач

Переменные, на знаки которых наложены ограничения ( хj>=0), называется ограниченными; если ограничения не наложены(хj><0) произвольные

Виды двойственных задач

1) симметричные – если все ограничения, как в прямой так и в двойственной задачи неравенства

2) несеметричные – остальные

Теоремы двойственности

1 – основная

1) если одна из них обладает оптимальным решением, то и другая его имеет, причем экстремальные значения целевой функции равны

2) если у одной из задач целевая функция не ограничена, то двойственная не имеет допустимых решений (противоречива)

3) если одна из задач противоречива, то А* имеет неограниченную целевую функцию или противоречива

Следствие:

2- условия дополняющей нежесткости

Если х^, и у^, оптимальны, то решение удовлетворяет условиям

Экономический смысл

Обычно эта задача связывается с задачей максимизации дохода при производстве некоторой продукции при наличии ограничений на ресурсы. Коэффициенты имеют смысл дохода от единицы продукции j-го ресурса, — количество единиц продукции j-го вида. Коэффициенты имеют смысл затрат i-го ресурса на производство продукции j-го типа.

10. Метод искусственного базиса.

...-метод, позволяющий приводить систему ЗЛП к единичному базису и одновременно улучшать решение. Метод удобен, когда кол-во переменных знач больше кол-ва уравнений. В ур-ия, где нет баз. переменных, вводим искусственные с коэф. (–М). Например: «-Мx5-Mx6» Целевая изм. и F* окаж. отриц, F* преврат. F, когда все исскуств. переменные будут выведены из базиса. Выводить будем с исп. 2 индексных строк (∆ и ∆М) по естественным и искусственным переменным соответственно. Решаем задачу как обычно, но разр. элемент выбираем по строке ∆М. После вывода из базиса искусств. переменной, ее столбец зачеркивают и прекращают с ней работу. После нескольких итераций обычно все искусственные переменные выводятся и продолжаем решать уже по обычной индексной строке. Замечание: если в ∆М нет отриц коэф., но еще не все искусств. переменные выведены, то задача не имеет решения.