Лекция: Области решений задачи линейного программирования

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

Системой линейных неравенств называется система вида:

Решением системы линейных неравенств называется совокупность значений переменных которые удовлетворяют всем неравенствам этой системы:

где — действительное число,

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

Рассмотрим систему линейных неравенств в двумерном пространстве и изучим область ее решений:

Область решений каждого неравенства этой системы состоит из двух множеств:

1) множества точек, удовлетворяющих уравнению;

2) множества точек, удовлетворяющих строгому неравенству.

Множество точек, удовлетворяющих уравнению

где

составляют прямую, разбивающую плоскость на две полуплоскости.

Множества точек, удовлетворяющих строгому неравенству

где

будут лежать по одну сторону от прямой и задавать одну из полуплоскостей.

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

Если для этой точки выполняется неравенство

то она лежит на искомой полуплостости. Если нет, то — на другой полуплостости.

▼

Пример

Определим область решений неравенства:

а)

б)