8. Графический метод решения двухмерной задачи линейного программирования.

Графический метод основан на 2-х утверждениях из аналитической геометрии.

Утв.1. Прямая, заданная уравнением а_х+в_у=с делит числовую плоскость Оху на две полуплоскости, в одной из которых выполняется неравенство

I: а_х+в_х>с

II: а_х+в_х<с

Утв.2. Отыскание оптимальной точки.

Пусть прямая на плоскости задана уравнением а_х+в_х=с, вектор = а,в состоит из коэфф. перпендикулярной прямой и называется его нормальным вектором.

L₁: а_х+в_х=с₁ параллельно прямой

Прямая L₁получена перемещением прямой L в направлении вектора , если С₁>С и противоположен , если С₁<С

Алгоритм графического метода:

I этап: Построение множества допустимых планов.

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

Пересечение всех построенных линий на плоскостях дает множество допустимых планов.

Если множество допустимых планов не пусто, то переходим ко второму этапу.

II Этап: Строим вектор =(С1,С2) координаты, которого соотв. при переменной в целевой функции через произв.точку множество допустимых планов проводим прямую L перпендикулярную вектору

При решении задачи по max прямая L перемещается по направлению вектора до крайнего положения пока она имеет общие точки с множеством допустимых планов, это крайнее положение называется разрешающим положением прямой L Корд. крайней точки дают оптимальный , а их подстановка в целевую функцию оптимальное значение.

При решении задачи на min прямая перемещается в направлении против вектора , до разрешающего положения.

9. Основы постоптимизационного анализа: определение статуса ресурсов, пределов изменения запасов ресурсов.

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

Это связано с ограничением модели на активные и неактивные.

Ограничение называется активным, если отвечающая ему прямая проходит через оптимальную точку и не активным в прямом случае.

Т.С. Образована пересечением прямых L2 и L3 2-е и 3-е ограничение модели выполняются как точные равенства, являются активными, это означает, что оптимальным планом ресурсы II и III типа исчерпываются полностью, т.е. имеют статус дефицита.

Т.С. лежит ниже прямой L1, т.е. первый ресурс является не дефицитным, т.е. имеется в избытке.

Можно написать пример

7. Формы записи задач линейного программирования: общая задача линейного программирования в развернутой, матричной и векторной форме. Правила преобразования общей задачи линейного программирования в каноническую.

Общей задачей линейного программирования называется задача следующего типа:

F(Х1, Х2,…Хn) = → max (min)