Задачи линейного программирования.

Графический метод.

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

Задача 1.

Рассмотрим систему неравенств

(1)

и линейную форму

(2)

Найти минимум и максимум линейной формы (2) из области решений системы (1).

Решение.

Построим выпуклый многоугольник, заданный системой неравенств (1). Для этого построим прямоугольную систему координат х₁ох₂. Если в этой системе координат построить прямую ах₁+bх₂=с, то эта прямая разбивает плоскость х₁ох₂ на две полуплоскости, каждая из которых лежит по одну сторону от прямой. Сама прямая в этом случае называется граничной и принадлежит обеим полуплоскостям. Координаты точек, лежащих в одной полуплоскости удовлетворяют неравенству ах₁+вх₂≤с, а координаты точек, лежащих в другой полуплоскости, удовлетворяют неравенству ах₁+вх₂≥с. Построим в плоскости х₁ох₂ граничные прямые:

1) 4)

2) 5)

3)

В результате получим пятиугольник АВСDЕ (рис. 2)

Значения х₁ и х ₂, удовлетворяющие системе неравенств (1), являются координатами точек, лежащих внутри или на границе найденного пятиугольника. Теперь задача сводится к тому, чтобы найти те значения х ₁ и х ₂ при которых линейная форма L (2) имеет минимум, и те значения х₁ и х ₂ при которых линейная форма L достигает максимума. Из рис. 2 видно, что координаты всех точек, лежащих внутри или на границе пятиугольника, не являются отрицательными, т.е. все значения х ₁ и х ₂ больше или равны нулю.

Рис. 2

Для каждой точки плоскости х₁ох ₂ линейная форма L принимает фиксированное значение. Множество точек, при которых линейная форма L принимает фиксированное значение L ₁, есть прямая , которая перпендикулярна вектору . Если прямую передвигать параллельно самой себе в положительном направлении вектора , то линейная форма L будет возрастать, а в противоположном направлении – убывать. Построим прямую для того случая, когда L = 0, т.е. построим прямую . Как видно из рис. 2, при передвижении прямой в положительном направлении вектора она впервые встречается с вершиной А(0;2) построенного пятиугольника АВСDЕ. В этой вершине линейная форма L имеет минимум. Следовательно,

.

При дальнейшем передвижении прямой параллельно самой себе в положительном направлении вектора значение линейной формы будет возрастать, и оно достигает максимального значения в точке С(8;6). Таким образом,

.

Задача 2.

Туристской фирме требуется не более 10 автобусов грузоподъёмностью 3 тонны и не более 8 автобусов грузоподъёмностью 5 тонн. Цена автобуса первой марки 20000 у.е., цена автобуса второй марки 40000 у.е. Туристская фирма может выделить для приобретения автобусов не более 400000 у.е. Сколько следует приобрести автобусов каждой марки в отдельности, чтобы их общая (суммарная) грузоподъёмность была максимальной.

Решение.

Пусть приобретено х ₁ трёхтонных, х ₂ пятитонных автобусов, тогда заданные условия задачи можно записать так:

или (1)

Линейная форма L (часто её называют целевой функцией) применительно к условиям нашей задачи имеет вид:

(2)

Требуется найти те значения х₁ и х ₂, при которых L достигает максимального значения. По условию задачи . Решим задачу графическим методом, который был использован при решении задачи 1. Построим многоугольник АВСDЕ (рис. 3), все точки которого удовлетворяют системе неравенств.

(3)

Затем построим вектор и прямую . Перемещая прямую параллельно самой себе в положительном направлении вектора , установим, что L достигает максимального значения в точке С, для которой х ₁ = 10 и х₂ = 5. Следовательно, туристской фирме следует приобрести 10 трёхтонных и 5 пятитонных автобусов. В этом случае общая грузоподъёмность составит 55 тонн. ()