Геометрическая интерпретация задачи. Обоснование подхода к решению

Все последующие рассуждения применимы к формулированию задачи ЛП в стандартной форме, имеющей следующее представление:

_n

Z = ∑ Cjxi → max (-Z→min)

^j=1

a₁₁ x₁ + a₁₂ x₂ +…+ a_1n x_n = b₁

… (1)

a_m1 x₁ + a_m2 x₂ +…+ a_mn x_n = b_m

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

Ответить на вопрос, всегда ли задача имеет решение, а так же сформулировать требования к подходу решения можно на основании геометрической интерпретации. Геометрическая интерпретация в постановке и решении задач наглядна при условии n-m=k=2, то есть число уравнений - m на 2 меньше, чем число переменных - n, в этом случае интерпретация может быть проиллюстрирована на плоскости.

Известно, что m линейно-независимых уравнении всегда можно разрешить относительно n базисных переменных, выразив их через k=n-m (в нашем случае 2) свободные переменные. Обозначим свободные переменные – x₁ и x₂, базисные – x₃…x_n, тогда из уравнений (1) можно получить следующую систему:

x₃ = a₃₁ x₁ + a₃₂ x₂ + B₃

x₄ = a₄₁ x₁ + a₄₂ x₂ + B₄

…

x_n = a_n1 x₁ + a_n2 x₂ + B_n

Теперь будем изображать пару свободных переменных в системе координат.

Так как по определению переменные не отрицательны, то первое условие допустимой области решения является первый квадрат системы координат. Теперь уточним область допустимых решений на плоскости x₁0x₂ с учетом заданных ограничений. Приравняем значение переменной x₃=0 и запишем исходное уравнение в следующем виде:

0 = x₃ = а₃₁ x₁ + a₃₂ x₂ + β₃

В системе координат x₁0x_2, данное уравнение, отображается соответствующей прямой (см. рис.). Ее наклон и расположение определяется соответствующими коэффициентами. Данная прямая характеризуется тем, что любая расположенная на ней точка соответствует условию x₃=0. Соответственно, в зависимости от коэффициентов, значение x₃ будет больше 0 (выше отсекающей прямой), меньше 0 (ниже отсекающей прямой).

Аналогичным образом можем построить соответствующие прямые для переменных x₄…x_n

Совокупность данных прямых, при условии неотрицательных переменных, отсекают область допустимых решений (если она не пуста). Проведем подобную операцию с целевой функцией (Z). Выразим Z через свободные переменные и получим:

Z = γ₁ x₁ + γ₂ x₂ + γ₀

Где γ₁ ,γ₂ – коэффициенты, γ₀ – свободный член (который для простоты опустим). Обратим данное уравнение в 0. Тогда, соответственно, для данного уравнения в системе координат x₁0x₂ может быть построена прямая, проходящая через систему координат.

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

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

Ответим на вопрос, всегда ли задача имеет решение и всегда ли оно единственно. Для этого рассмотрим 2 случая:

1: область не ограничена сверху. Задача не имеет решения, так как всегда можно найти значение лучше предыдущего.

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

Замечание: важно то, что к оптимальным относятся и краевые точки, задаваемые пересечением прямых области ограничения.