26. Несовместность условий в линейном программировании.

При несовместности условий в линейном программировании задача может не иметь решения, так как система ограничений противоречива в двух случаях:

1. Если при решении задачи симплекс-методом с искусственным базисом получается, что расширенная задача не имеет решения, так как целевая функция не ограничена снизу при наличии искусственных векторов в базисе.

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

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

ограничений противоречива, то есть ОДЗ=∅ .

27. Двойственность в линейном программировании:

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

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

1) Количество переменных двойственной задачи равняется количеству ограничений исходной задачи.

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

3) Если в исходной задаче требуется опр-ть минимальное значение целевой функции z, то в двойственной – требуется определить максимальное значение целевой функции F и наоборот.

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

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

6) Определение типов ограничения двойственной задачи.

Определение 1. Если целевая функция задачи на минимум, то неравенства типа «больше или равно» называются «правильными», а неравенства типа «меньше или равно» – «неправильными». Если целевая функция задачи на максимум, то неравенства типа «меньше или равно» называются «правильными», а неравенства типа «больше или равно» называются «неправильными».

Определение 2. Если на некоторую переменную накладываются ограничения «больше или равно» нуля, то такая переменная называется «правильной», если «меньше или равно» – «неправильной».

28. Транспортная задача, ее модель.

Классическая транспортная задача ЛП формулируется следующим образом.

Имеется m пунктов производства (поставщиков) и n пунктов

потребления (потребителей) однородного продукта. Заданы величины:

- объем производства (запас) i-го поставщика,  i=1, m  ;

- объем потребления   (спрос) j-го потребителя, i=1, n ;

- стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к  j-му потребителю.

Требуется составить такой план перевозок, при котором спрос всех потребителей был бы выполнен и при этом общая стоимость всех перевозок была бы минимальна.

Математическая модель транспортной задачи имеет вид

Транспортная задача, в которой суммарные запасы и суммарные потребности совпадают, называется закрытой моделью; в противном случае - открытой.

29. Теорема об оптимальном плане транспортной задачи. В силу специфики содержательной постановки транспортной задачи допустимое решение называется планом, базисное допустимое решение называется опорным планом, оптимальное решение называется оптимальным планом. Теорема 2. Любая закрытая ТЗ имеет оптимальный план. (Чтобы открытую ТЗ превратить в закрытую мы должны добавить фиктивного поставщика или потребителя, чтобы А=В).