Графический способ решения ЗЛП.

Геометрическая интерпретация экономических задач дает возможность наглядно представить, их структуру, выявить особенности и открывает пути исследования бо­лее сложных свойств. ЗЛП с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в простран­ствах, размерность которых больше трех, графическое решение, вообще говоря, невозможно. Случай двух переменных не имеет особого практиче­ского значения, однако его рассмотрение проясняет свой­ства ОЗЛП, приводит к идее ее решения, делает геомет­рически наглядными способы решения и пути их практи­ческой реализации.

Пусть дана задача

(11)

(12)

(13)

Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (12), (13) задает на плоскости некоторую полуплоскость. Полу­плоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множест­вом. Отсюда следует, что область допустимых решений задачи (11) — (13) есть выпуклое множество.

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП — не­пустое множество, например многоугольник .

Выберем произвольное значение целевой функ­ции. Получим . Это уравнение пря­мой линии. В точках прямой NМ целевая функция сохра­няет одно и то же постоянное значение . Считая в ра­венстве (11) параметром, получим уравнение семей­ства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

Найдём частные производные целевой функции по и

(14)

(15)

Частная производная (14) ((15)) функции пока­зывает скорость ее возрастания вдоль данной оси. Следо­вательно, и — скорости возрастания соответст­венно вдоль осей и . Вектор называ­ется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

Вектор — указывает направление наискорейшего убывания целевой функции. Его называют антигра­диентом.

Вектор перпендикулярен к прямым семейства

Из геометрической интерпретации элементов ЗЛП вы­текает следующий порядок ее графического решения.

1. С учетом системы ограничений строим область до­пустимых решений

2. Строим вектор наискорейшего возра­стания целевой функции — вектор градиентного направ­ления.

3. Проводим произвольную линию уровня

4. При решении задачи на максимум перемещаем ли­нию уровня в направлении вектора так, чтобы она касалась области допустимых решений в ее крайнем по­ложении (крайней точке). В случае решения задачи на минимум линию уровня перемещают в антиградиентном направлении

5. Определяем оптимальный план и экстре­мальное значение целевой функции .