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

Геометрический метод решения основной задачи линей­ного программирования с двумя переменными основан на следующих теоретичес­ких положениях:

1. Наибольшее или наименьшее значение линейная целе­вая функция (5.26) может принимать только на границе мно­гоугольной области - области решений системы линейных ограничений.

2. Направление вектора = (С ₁ С ₂ ) представляет направ­ление наибольшего возрастания целевой функции.

3. Множество точек плоскости, для которых целевая функция F имеет постоянное значение F ₀, то есть C ₁ х ₁ +C ₂ х ₂+ С ₀ = F ₀, пред­ставляет прямую, перпендикулярную вектору . Множество та­ких прямых - множество прямых, параллельных друг другу.

Алгоритм геометрического метода реше­ния задачи

1. Строим многоугольную область - область решений сис­темы линейных ограничений (5.27).

2. Строим вектор = (С ₁ С ₂ ) и прямую, перпендикуляр­ную этому вектору.

3. Перемещаем эту прямую параллельно самой себе в на­правлении вектора . Первая точка встречи этой прямой с построенной в п. 1 многоугольной областью (точка входа) представляет оптимальное решение, в которой функция F принимает наименьшее значение. Последняя точка (точка выхода) - это оптимальное решение, в которой фун­кция принимает наибольшее значение.

Пример. Найти наибольшее и наименьшее значения це­левой функции F = 2 х ₁ + 2 х ₂, если выполняется система ли­нейных ограничений (5.30).

Решение. Многоугольная область, соответствующая систе­ме (5.30), построена ранее и изображена на рис. 5.11. Пост­роим вектор = (2,2) и прямую, перпендикулярную этому вектору (рис. 5.12).

Перемещая эту прямую в направлении вектора парал­лельно самой себе, находим точку входа A (1;0) и точку выхо­да B (3;7,5).

Следовательно, целевая функция достигает наименьшего значения при х ₁ = 1 и х ₂ = 0 и наибольшего значения при х ₁ = 3 и х ₂ = 7,5. Эти значения соответственно равны:

F _min = F (1;0) = 2×1 + 2×0 = 2,

F _max = F (3;7,5) = 2×3 + 2×7,5 = 21.

Пример. Пусть требуется решить задачу об использова­нии сырья, о которой шла речь в п. 5.5.1, если известна таб­лица исходных данных:

Виды сырья	Запасы сырья	Виды продукции
Р 1	Р 2
S 1
S 2
S 3
S 4
Доход

В соответствии со сказанным выше система линейных ог­раничений представлена в виде:

(5.31)

При этом целевая функция имеет вид:

F = 7 x ₁ + 5 x ₂. (5.32)

Ищем наибольшее значение функции (5.32) при выпол­нении условий (5.31).

Построим область решения системы (5.31) (рис. 5.13).

Неравенство 2 x ₁ + З х ₂ £ 19 определяет полуплоскость, ог­раниченную прямой 2 x ₁ + З х ₂ =19, или

отсе­кающей на осях координат отрезки 9 ½ и 6 1 / 3, в которой лежит начало координат.

Неравенство 2 x ₁ + х ₂ £ 13 опреде­ляет полуплоскость, ограниченную прямой 2 x ₁ + х ₂ =13, или

отсекающей на осях координат отрезки 6 ½ и 13, в которой лежит начало координат.

Неравенство 3 x ₂ £ 15, или x ₂ £ 5, определяет полуплоскость, лежащую ниже пря­мой х ₂ = 5.

Неравенство 3 x ₁ £ 18, или x ₁ £ 6, определяет по­луплоскость, лежащую слева от прямой х ₁ = 6.

О полуплос­костях x ₁³ 0, x ₂³ 0 подробно было сказано при решении примера 3 п. 5.5.3.

Область допустимых решений представляет многоуголь­ник OABCDE.

Построим вектор N = (7;5).

Будем перемещать прямую, перпендикулярную вектору , в направлении этого вектора параллельно самой себе. Тогда точкой выхода из области бу­дет точка С (5;3), являющаяся точкой пересечения прямых 2 x ₁ + х ₂ =13, 2 x ₁ + З х ₂ =19, и поэтому находится из систе­мы уравнений этих прямых:

Отсюда:

3 х ₁ – х ₂ = 19 – 13; х ₂ = 3,

2 х ₁ = 19 – 3 х ₂ = 19 – 9 = 10; х ₁ = 5.

Следовательно, наибольшее значение целевой функции (5.32) достигается при x ₁ = 5 х ₂ = 3. Это значение равно:

F _max = F (5;3) = 7×5 + 5×3 = 50.

Таким образом, мы видим, что для наиболее рационально­го использования сырья, гарантирующего предприятию наи­больший доход, следует выпускать 5 единиц продукции вида Р ₁ и 3 единицы вида Р ₂, причем максимальный доход соста­вит 50 денежных единиц. При этом сырье видов S ₁ и S ₂используется полностью, a S ₃ и S ₄ - не полностью, так как при плане выпуска продукции х ₁ = 5, х ₂ = 3:

2 х ₁ + 3 х ₂ = 5×2 + 3×3 = 19,

2 х ₁ + х ₂ = 5×2 + 3 = 13,

3 х ₂ = 3×3 = 9 < 15,

3 х ₁ = 3×5 = 15 < 18.

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

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

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

Задача 1.

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

(1)

и линейную форму (2)

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

Решение.

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

1) 4)

2) 5)

3)

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

Значения х₁ и х ₂, удовлетворяющие системе неравенств (1), являются координатами точек, лежащих внутри или на границе найденного пятиугольника.

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

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

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

Рис. 2

Задача 2.

Туристской фирме нужно не более 10 автобусов на 3 тонны и не более 8 автобусов на 5 тонн. Цена автобуса первой марки 20000 у.е., цена автобуса второй марки 40000 у.е.

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

Решение.

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

или (1)

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

(2)

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

(3)

Дата добавления: 2014-01-13