Геометрическая интерпретация ОЗЛП

Пусть необходимо найти оптимальный план производства двух видов продукции (x ₁ и x ₂ ), т.е. такой план, при котором целевая функция (общая прибыль) была бы максимальной, а имеющиеся ресурсы использовались бы наилучшим образом. Условия задачи приведены в табл. 3.1.

Таблица 3.1 – Данные о запасе и нормах расхода ресурсов

Вид продукции	Норма расхода ресурса на единицу продукции	Прибыль на единицу изделия
	А	В	С
		0,1	3,5
		0,5
Объем ресурса

Оптимизационная модель задачи запишется следующим образом:

а) целевая функция:

б) ограничения:

(ограничение по ресурсу А),

(ограничение по ресурсу B),

(ограничение по ресурсу C);

в) условие неотрицательности переменных:

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

Преобразуем нашу систему ограничений, найдя в каждом из уравнений x ₂ , и отложим их на графике. Любая точка на данном графике с координатами x ₁ и x ₂ представляет вариант искомого плана. Однако ограничение по ресурсу А сужает область допустимых решений. Ими могут быть все точки, ограниченные осями координат и прямой АА, так как не может быть израсходовано ресурса А больше, чем его на предприятии имеется. Если точки находятся на самой прямой, то ресурс используется полностью.

Аналогичные рассуждения можно привести и для ресурсов В и С. В результате условиям задачи будет удовлетворять любая точка, лежащая в пределах заштрихованного многоугольника. Данный многоугольник называется областью допустимых решений.

Рисунок 3.3.– Геометрическая интерпретация оптимизационной задачи линейного программирования

Однако нам необходимо найти такую точку, в которой достигался бы максимум целевой функции. Для этого построим произвольную прямую 4 x ₁ + 5x ₂ = 20, как x ₂ = 4 - 4/ 5x ₁ (число 20 произвольное). Обозначим эту линию РР. В каждой точке этой линии прибыль одинакова. Перемещая эту линию параллельно ее исходному положению, найдем точку, которая удалена от начала координат в наибольшей мере, однако не выходит за пределы области допустимых решений. Это точка М, которая лежит на вершине многоугольника. Координаты этой точки (x' ₁ = 3,03 и x' ₂ = 7,4) и будут искомым оптимальным планом.

Дата добавления: 2014-01-04