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

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

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₂

X1

3x1+2x2=12

bi<12

bi>12

 

Рис.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₂

X1

h ABK8QODdAAAACQEAAA8AAABkcnMvZG93bnJldi54bWxMj01PwzAMhu9I/IfISFwmlq6oY5SmEwJ6 48IAcfUa01Y0TtdkW+HXY8QBbv549PpxsZ5crw40hs6zgcU8AUVce9txY+DlubpYgQoR2WLvmQx8 UoB1eXpSYG79kZ/osImNkhAOORpoYxxyrUPdksMw9wOx7N796DBKOzbajniUcNfrNEmW2mHHcqHF ge5aqj82e2cgVK+0q75m9Sx5u2w8pbv7xwc05vxsur0BFWmKfzD86Is6lOK09Xu2QfUG0utlJqgU qwUoAX4HWwNZdgW6LPT/D8pvAAAA//8DAFBLAQItABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAA AAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAA lAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAhAILdXhoNAgAA zgMAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9Eb2MueG1sUEsBAi0AFAAGAAgAAAAhABK8QODd AAAACQEAAA8AAAAAAAAAAAAAAAAAZwQAAGRycy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAABx BQAAAAA= "/>

3x1+2x2=12

bi<12

bi>12

X1+2x2=4

 

Рис.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.

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

 

 

2x1-x2=1

X₂

X1

h ABK8QODdAAAACQEAAA8AAABkcnMvZG93bnJldi54bWxMj01PwzAMhu9I/IfISFwmlq6oY5SmEwJ6 48IAcfUa01Y0TtdkW+HXY8QBbv549PpxsZ5crw40hs6zgcU8AUVce9txY+DlubpYgQoR2WLvmQx8 UoB1eXpSYG79kZ/osImNkhAOORpoYxxyrUPdksMw9wOx7N796DBKOzbajniUcNfrNEmW2mHHcqHF ge5aqj82e2cgVK+0q75m9Sx5u2w8pbv7xwc05vxsur0BFWmKfzD86Is6lOK09Xu2QfUG0utlJqgU qwUoAX4HWwNZdgW6LPT/D8pvAAAA//8DAFBLAQItABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAA AAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAA lAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAhAD2uDFANAgAA zgMAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9Eb2MueG1sUEsBAi0AFAAGAAgAAAAhABK8QODd AAAACQEAAA8AAAAAAAAAAAAAAAAAZwQAAGRycy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAABx BQAAAAA= "/>

3x1+2x2=12

bi<12

bi>12

X1+2x2=4

 

 

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