Построение области допустимых решений в задаче ЛП с двумя переменными

Выясним вначале особенности геометрического представления неравенств, входящих в систему ограничений, которые в общем виде для случая двух переменных имеют вид

a₁₁x₁ + a₁₂x₂ b₁

a₂₁x₁ + a₂₂x₂ b₂

………………..

a_m1x₁ + a_m2x₂ b_m

x₁ 0, x₂ 0

Предположим для определенности, что одно из неравенств системы имеет вид

3х₁ + 2х₂ 12

Пусть оно иллюстрирует условие ограниченности некоторого ресурса, запас которого равен 12. Рассмотрим предельный (граничный) случай

3х₁ + 2х₂ = 12

Такая замена неравенства на равенство имеет место в случае, когда расход соответствующего ресурса в точности равен запасу. Уравнение 3х₁ + 2х₂ = 12 задает на координатной плоскости Х₁ 0 Х₂ прямую (граничную прямую), изображенную на рис. 3.1.

X₂

Рис.3.1.

Для ответа на вопрос, где расположена область значений переменных х₁, х₂, удовлетворяющая условию 3x₁ + 2х₂ 12, достаточно взять любую точку, лежащую левее и ниже прямой (либо правее и выше), и проверить, удовлетворяет ли она данному неравенству. Взяв, например, точку с координатами (1,1), т.е. точку, соответствующую значениям x₁= 1, x₂ = 1, и подставив эти значения, получаем верное неравенство 5 12. Из чего можно сделать вывод, что неравенству (одному из ограничений задачи) соответствует множество точек (пар значений (x₁, х₂)), лежащих ниже и левее построенной граничной прямой.

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

Так как переменные х₁, и х₂ неотрицательны, то область значений, соответствующая первому неравенству, и условиям неотрицательности, будет такой, как показано на рис. 3.1.

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

Действительно, если в ограничении запас ресурса увеличить с 12 до 18, чему соответствует новое неравенство 3х₁ + 2х₂ < 18, то получим новую прямую 3x₁ + 2x₂ = 18, параллельную исходной (рис. 3.2).

Рис. 3.2. Изменение положения границы ОДР при изменении запаса ресурса (правой части ограничения)

Выясним, как будет изменяться ОДР с добавлением в систему других ограничений. Пусть, например, помимо первого неравенства и условий неотрицательности существует еще одно ограничение: х₁+ 2x₂> 4.

Теперь требуется построить область, удовлетворяющую системе ограничений

3x₁ + 2x₂ 12

x₁ +2x₂ 4

x₁ 0, x₂ 0

Повторим процедуру нахождения области, удовлетворяющей новому условию x₁+ 2x₂ 4. Для этого на графике строим прямую x₁ + 2х₂ = 4, выясняем путем подстановки, что новому условию удовлетворяет область, лежащая правее и выше этой прямой (рис. 3.3). Объединяя этот результат с результатом, полученным ранее, находим область допустимых решений, все точки которой удовлетворяют ограничениям этой новой системы.

X₂

Рис.3.3.

Добавим еще одно ограничение, а именно 2х₁– x₂ 1, и построим область допустимых решений для новой системы неравенств:

3x₁ + 2x₂ 12

x₁ +2x₂ 4

2х₁– x₂ 1

x₁ 0, x₂ 0

Для этого найдем область, удовлетворяющую условию 2x₁ – x₂ 1. Строим граничную прямую (рис. 3.4) и выясняем, что новому условию удовлетворяет область, лежащая левее и выше прямой 2x₁ – x₂ =1. Объединив результат, полученный ранее (рис. 3.3), с полуплоскостью, расположенной левее и выше этой прямой, получаем новую область допустимых решений. Все ее точки удовлетворяют ограничениям системы. Геометрически она показана на рис. 3.4.

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

Рис. 3.4. Область допустимых решений системы ограничений

12
• 3
• Далее ⇒