Сборник задач по линейному программированию (стр. 7 )

       3. Неравенства ≥ 0 и ≥ 0 обозначают условия неотрицательности переменных и .

Прямые и – это оси координат ОХ2 и ОХ1, а искомые полуплоскости лежат правее и выше этих прямых соответственно.

                               Рис. 3

Множество точек, координаты которых удовлетворяют исходной системе неравенств, должны удовлетворять всем неравенствам одновременно. Очевидно, это область на плоскости Х1ОХ2 соответствующая многоугольнику ОСЕВО.

Область решений системы неравенств может состоять из бесчисленного множества решений, из конечного числа решений или не содержать решений. В последнем случае область решений называется пустой.

Если область решений системы линейных неравенств не пуста, то система неравенств называется совместной. В противном случае – несовместной.

Пример 4. Это пример несовместной системы неравенств.

Анализ решения можно пояснить с помощью рис.4.

                       Рис. 4.

Пример 5. Определить область решения системы неравенств:

Смысл решения можно понять из графика на рис. 5. Решением системы неравенств будут координаты только одной точки А (0,1)

                               

  Рис. 5.

       

       Задачи и упражнения.

1. Решить графически неравенства:

       

Решить графически системы неравенств и определить координаты вершин областей решений.

;                ;

;                ;

;                ;

;                ;

;                ;

;                ;

;                ;                

;                .

4. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

       Рассмотрим  задачу линейного программирования на частном примере.

Пример 1. Найти наибольшее и наименьшее значения функции при следующих ограничениях:

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

На графике получилась область (многоугольник) ОАВСDО. Это многоугольник допустимых решений. Выпишем целевую функцию . Зафиксируем значение целевой функции. Пусть равна константе . Построим линию . Это прямая (см. рис. 6) проходящая через точку (0,0). Если изменять значения и строить прямые , то получим семейство прямых линий (линии уровня целевой функции), параллельных друг другу. Как определить, куда будут смещаться эти прямые при увеличении или уменьшении ? Это определяется направлением вектора , компоненты которого равны коэффициентам при соответствующих переменных  целевой функции. В нашем случае (см. рис. 6). Вектор целевой функции перпендикулярен семейству линий уровня и направлен в сторону увеличения значения . В противоположном направлении значения уменьшаются. Поэтому, для нахождения максимального , строим линии уровня в направлении вектора . Последняя точка многоугольника решений, которой коснется прямая