Графический метод решения задач линейного программирования Случай двух переменных

Постановка задачи в этом случае имеет вид:

(1.6)

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

,

Если рассматривается система неравенств, то областью её решений может быть один из следующих случаев. 1) Система несовместна, когда область решений является пустым множеством.

2) Система неравенств совместна, то есть, область её решений выпуклое непустое множество, называемое многоугольником решений (в отличие от «многогранника решений», когда число неизвестных ), либо выпуклая многогранная область, уходящая в бесконечность.

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

Для определения экстремума ограниченной сверху целевой функции необходимо для случая:

1. Если , построить линию уровня (h –некоторая постоянная), таким образом, чтобы она проходила через многоугольник решений. При выполнении условия (то есть, проходит через начало координат) линия называется опорной. Построить вектор – градиент целевой функции . Передвигать линию уровня параллельно самой себе в направлении градиента, до тех пор, пока не будет достигнута последняя точка многоугольника решений (Рис.1.1). Координаты соответствующей точки дадут оптимальный план решений. Координаты точки можно уточнить аналитически, решая систему уравнений для прямых, которые пересекаются в данной точке.

2. Если , то линия уровня передвигается в направлении, противоположном своему градиенту (в направлении антиградиента) до достижения крайней точки многоугольника решений (Рис.1.2).

При решении могут встретиться следующие случаи.

1. Целевая функция F принимает максимальное значение в единственной точке А рис.1.1 (единственное решение).

2. Целевая функция принимает минимальное значение в точке В рис. 1.2 (единственное решение).

3. Целевая функция F принимает максимальное значение в любой точке прямой АВ рис 1.3. Прямая АВ перпендикулярна градиенту. (бесконечное множество решений).

4. Целевая функция не ограничена сверху на множестве допустимых решений Рис. 1.4. Максимум недостижим.

5. Система ограничений несовместна рис. 1.5. Решений нет.

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

1. Построить область решений задачи, то есть, многоугольник решений:

а) построить прямые, которые получаются из ограничений заменой знаков неравенств на знаки равенства,

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

2. Для определения целевой функции:

а) построить прямую (линию уровня) , проходящую через область допустимых значений (иногда удобно строить опорную линию f = ),

б) передвигать линию уровня параллельно самой себе в направлении градиента (при отыскании максимума), либо в направлении антиградиента (при отыскании минимума), до точки, в которой целевая функция либо принимает максимальное (минимальное) значение, либо устанавливается её неограниченность,

в) определить координаты точки пересечения граничных прямых, в которой целевая функция принимает экстремальное значение.

Пример 3. Найти максимальное и минимальное значения функции

,

при ограничениях

Решение. Строим координатную плоскость и наносим на неё прямые - ограничения (Рис.1.6). Первое уравнение неравенства можно преобразовать в равенство, уравнение границы или уравнение прямой (1) в отрезках и построить её, откладывая на соответствующих осях и отрезки 3 и 8. Если в неравенство (1) подставить координаты точки О(0;0), то неравенство будет , что неверно, отсюда следует, что области решений будет принадлежать полуплоскость со стороны, противоположной началу координат. Аналогичным образом преобразуем второе неравенство: и построим прямую (2). Области решений будет принадлежать полуплоскость с той стороны от прямой, где находится начало координат, так как при подстановке точки О(0;0) получим верное неравенство . Преобразуем третье неравенство: и построим прямую (3). Области решений будет принадлежать полуплоскость с той стороны от прямой, где находится начало координат, так как при подстановке точки О(0;0) получим верное неравенство . Таким образом, область решений задачи представляет собой треугольник АВD.

Для определения максимума целевой функции строим линию уровня , проходящую через область решений, и перпендикулярно к ней – вектор . В направлении этого вектора перемещаем линию уровня параллельно самой себе до точки А, которая является конечной точкой области решений. Эта точка, в которой целевая функция достигает максимума. Чтобы найти её координаты, решаем совместно второе и третье уравнения

Таким образом, максимальное значение целевой функции будет .

Оптимальное решение .

Чтобы найти минимальное значение целевой функции, линию уровня передвигаем влево, до конечной точки В. Получаем . Координаты точки В получаем, решая совместно первое и третье уравнения

Следовательно, минимальное значение целевой функции будет

.

Оптимальное решение .