Выясним вначале особенности геометрического представления неравенств, входящих в систему ограничений, которые в общем виде для случая двух переменных имеют вид
a11x1 + a12x2 
b1
a21x1 + a22x2 b2
………………..
am1x1 + am2x2 bm
x1 
0, x2 0
Предположим для определенности, что одно из неравенств системы имеет вид
3х1 + 2х2 12
Пусть оно иллюстрирует условие ограниченности некоторого ресурса, запас которого равен 12. Рассмотрим предельный (граничный) случай
3х1 + 2х2 = 12
Такая замена неравенства на равенство имеет место в случае, когда расход соответствующего ресурса в точности равен запасу. Уравнение 3х1 + 2х2 = 12 задает на координатной плоскости Х1 0 Х2 прямую (граничную прямую), изображенную на рис. 3.1.
X2
| X1 |
| 3x1+2x2=12 |
| bi<12 |
| bi>12 |
Рис.3.1.
Для ответа на вопрос, где расположена область значений переменных х1, х2, удовлетворяющая условию 3x1 + 2х2 12, достаточно взять любую точку, лежащую левее и ниже прямой (либо правее и выше), и проверить, удовлетворяет ли она данному неравенству. Взяв, например, точку с координатами (1,1), т.е. точку, соответствующую значениям x1= 1, x2 = 1, и подставив эти значения, получаем верное неравенство 5 12. Из чего можно сделать вывод, что неравенству (одному из ограничений задачи) соответствует множество точек (пар значений (x1, х2)), лежащих ниже и левее построенной граничной прямой.
Таким образом, в случае двух переменных область, соответствующая каждому ограничению задачи ЛП, записанному в виде неравенства, представляет собой полуплоскость, расположенную по одну из сторон соответствующей граничной прямой.
Так как переменные х1, и х2 неотрицательны, то область значений, соответствующая первому неравенству, и условиям неотрицательности, будет такой, как показано на рис. 3.1.
Попутно заметим, что при увеличении или уменьшении запаса ресурса bi, т. е. правой части ограничения, прямая не изменяет угол наклона, а лишь перемещается параллельно самой себе в ту или другую сторону. Соответственно изменению запаса ресурса будет изменяться и область допустимых решений (ОДР), расширяя или ограничивая возможности выбора.
Действительно, если в ограничении запас ресурса увеличить с 12 до 18, чему соответствует новое неравенство 3х1 + 2х2 < 18, то получим новую прямую 3x1 + 2x2 = 18, параллельную исходной (рис. 3.2).
Рис. 3.2. Изменение положения границы ОДР при изменении запаса ресурса (правой части ограничения)
|
Выясним, как будет изменяться ОДР с добавлением в систему других ограничений. Пусть, например, помимо первого неравенства и условий неотрицательности существует еще одно ограничение: х1+ 2x2> 4.
Теперь требуется построить область, удовлетворяющую системе ограничений
3x1 + 2x2 12
x1 +2x2 
4
x1 0, x2 0
Повторим процедуру нахождения области, удовлетворяющей новому условию x1+ 2x2 4. Для этого на графике строим прямую x1 + 2х2 = 4, выясняем путем подстановки, что новому условию удовлетворяет область, лежащая правее и выше этой прямой (рис. 3.3). Объединяя этот результат с результатом, полученным ранее, находим область допустимых решений, все точки которой удовлетворяют ограничениям этой новой системы.
X2
| X1 |
| 3x1+2x2=12 |
| bi<12 |
| bi>12 |
| X1+2x2=4 |
Рис.3.3.
Добавим еще одно ограничение, а именно 2х1– x2 
1, и построим область допустимых решений для новой системы неравенств:
3x1 + 2x2 12
x1 +2x2 4
2х1– x2 1
x1 0, x2 0
Для этого найдем область, удовлетворяющую условию 2x1 – x2 1. Строим граничную прямую (рис. 3.4) и выясняем, что новому условию удовлетворяет область, лежащая левее и выше прямой 2x1 – x2 =1. Объединив результат, полученный ранее (рис. 3.3), с полуплоскостью, расположенной левее и выше этой прямой, получаем новую область допустимых решений. Все ее точки удовлетворяют ограничениям системы. Геометрически она показана на рис. 3.4.
Таким образом, всякая система ограничений задачи линейного программирования с двумя переменными задает на плоскости некоторую область, представляющую собой так называемый в ыпуклый многоугольник, — область допустимых решений. Выпуклость означает, что отрезок, соединяющий две любые точки области, также целиком принадлежит этой области.
| 2x1-x2=1 |
| X1 |
| 3x1+2x2=12 |
| bi<12 |
| bi>12 |
| X1+2x2=4 |
Рис. 3.4. Область допустимых решений системы ограничений
