Графические методы поиска оптимального решения линейных моделей

ЦЕЛЬ РАБОТЫ: развить навыки анализа экономико-математических моделей на основе графических методов поиска их оптимальных решений.

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ. Возможны различные подходы к анализу линейных оптимизационных моделей. Однако наиболее наглядным и простым способом является геометрическая интерпретация линейной модели и всех ее элементов.

Для построения графического аналога линейной оптимизационной модели необходимо выбрать систему координат. Наиболее удобной для этой цели является прямоугольная декартовая система координат, где каждой управляющей переменной x_j, j = 1, n соответствует своя ось. В наиболее простом случае – это плоскость с двумя координатными осями. Важно помнить, что все свойства модели, характерные для 2–х и 3–х мерных моделей, полностью сохраняют свои свойства и для n –х пространств и моделей.

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

z ₀ = p ₁ x ₁ + p ₂ x ₂ → max;

y_r = – a_{r 1} – a_{r 2} x ₂ + a_r ≥ 0, r = 1, k;

y_l = a_{l 1} x ₁ + a_{l 2} x ₂ – a_l ≥ 0, l = k + 1, m;

x ₁ ≥ 0, x ₂ ≥ 0.

При построении осей для 2-мерной модели, как правило, по горизонтали откладывают объем услуг1-го вида. По вертикальной оси - объем услуг2-го вида. Таким образом, каждая точка на плоскости является программой оказания обоих видов услуг, а координаты этой точки определяют конкретный объем оказания услуг 1-го и 2-го вида.

Геометрический смысл целевой функции z ₀ = p ₁ x ₁ + p ₂ x ₂ – прямая, которая проходит перпендикулярно к нормальному вектору p с координатами p = (p ₁, p ₂). Этим вектором фиксируется направление прямой (p ₁ x ₁ + p ₂ x ₂) относительно координатных осей. При z ₀ = 0 эта прямая проходит через начало координат. Экономический смысл этой прямой заключается в том, что прямая z ₀ = 0 определяет множество возможных вариантов программ, суммарная прибыль для которых равна нулю. Направляющий вектор

p = (p ₁, p ₂) показывает, где лежат точки (программы) с положительным значением прибыли z ₀ > 0. В противоположном направлении расположены точки (программы) с отрицательным значением суммарной прибыли z ₀ < 0 (убытки).

Все остальные прямые, соответствующие уравнениям y_r и y_l, строятся по двум точкам. Для этого попеременно приравнивается нулю x₁ и x_2.

Геометрический смысл переменной y_r – прямая, не проходящая через начало координат, так как a_r ≠ 0. Прямая y_r проходит перпендикулярно вектору A_r = (-a_{r 1}, -a_{r 2}) с отрицательными координатами. Экономический смысл этой прямой при y_r = 0 состоит в том, что на ней лежат все программы по оказанию услуг, для которых экономия r -го производственного ресурса равна нулю, т.е. фонды (лимиты) по этому ресурсу израсходованы. Вектор

A_r = (- a_{r 1}, - a_{r 2}) показывает, в каком направлении лежат точки (программы) с большей экономией r -го ресурса, ниже - его перерасхода.

Геометрический смысл переменной y_l - прямая, не проходящая через начало координат, так как контрольные цифры программы (плана) отличны от нуля, то есть a_l ≠ 0. На этой прямой лежат все точки (программы), для которых перевыполнение плана по l -му экономическому показателю равно нулю. Другими словами, программа по оказанию услуг выполняется на 100%.

Направляющий вектор A_l = (a_{l 1}, a_{l 2}) показывает область, где планы по выполнению услуг перевыполняются y_l > 0, или составляют более 100%. В противоположном направлении лежат планы, для которых задание по l -му экономическому показателю y_l < 0, то есть не выполняется, или составляет менее 100%.

МТОДИКА ПОСТРОЕНИЯ ГРАФИЧЕСКОЙ МОДЕЛИ ЛИНЕЙНОГО ТИПА

1. Приравниваются к нулю каждая из переменных, входящих в модель. Эту процедуру начинают с управляющих переменных: x₁ =0, x ₂=0 – это две прямые, которые рассматриваются в качестве координатных осей (см. рис.1). Каждая точка плоскости, ограниченная штриховкой, является программой (планом) оказания услуг двух видов (x ₁ и x ₂).

y2=0

			y4=0

		X1(x2=0)

(4)

(1)

		(2)
	P1
			(3)

Рисунок 1 - Пример графического поиска и анализа оптимального

решения модели линейного типа

2. Приравнивается к нулю переменная z ₀, и строится прямая z ₀=0, перпендикулярная вектору p (p ₁, p ₂), направление которого показывает, в какую сторону следует изменять план.

3. Приравниваются к нулю переменные y ₁ и y₂ (y_r1 и y_r2 ) характеризующие экономию ресурсов. Строятся прямые y ₁=0, y ₂=0, перпендикулярные векторам A ₁(- a ₁₁, - a ₁₂) и A ₂(- a ₂₂, - a ₂₂). Направления векторов показывают, как следует изменить программу оказания услуг (или выпуска продукции), чтобы увеличить экономию ресурсов (см. рис.1).

4. Приравниваются к нулю переменные y ₃ и y ₄ (y_l1 и y_l2), характеризующие перевыполнение программы по экономическим показателям. Строятся прямые y ₃=0, y ₄=0, перпендикулярные векторам

A ₃(- a ₃₁, - a ₃₂) и A ₄(- a ₄₁, - a ₄₂). Направления векторов указывают, в какой области лежат программы по оказанию услуг, обеспечивающие рост экономических показателей.

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