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

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

n

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

j=1

Геометрическая интерпретация задачи. Обоснование подхода к решению - student2.ru a11 x1 + a12 x2 +…+ a1n xn = b1

… (1)

am1 x1 + am2 x2 +…+ amn xn = bm

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

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

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

Геометрическая интерпретация задачи. Обоснование подхода к решению - student2.ru x3 = a31 x1 + a32 x2 + B3

x4 = a41 x1 + a42 x2 + B4

xn = an1 x1 + an2 x2 + Bn

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

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

0 = x3 = а31 x1 + a32 x2 + β3

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

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

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

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

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

Z = γ1 x1 + γ2 x2 + γ0

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

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

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

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

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

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

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

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

Наши рекомендации