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

Цель:

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

• научиться определять область допустимых решений системы линейных уравнений.

Ход работы

Пример 2.1.

Решить с помощью геометрического метода задачу планирования производства:

Для изготовления двух видов продукции Р1 и P2 используют четыре вида ресурсов S1, S2, S3 и S4. Запасы ресурсов, число еди­ниц ресурсов, затрачиваемых на изготовление единицы продук­ции, приведены в табл. 2.1 (цифры условные).

Таблица 2.1 – Данные об использовании ресурсов

Вид ресурса	Запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
		Р1	Р2
S1	18	1	3
S2	16	2	1
S3	5	-	1
S4	21	3	-

Прибыль, получаемая от единицы продукции Р1 и Р2, – соот­ветственно 2 и 3 грн.

Решение

На предыдущем занятии была построена экономико-математическая модель нашей задачи. Она имеет вид:

Применим геометрический метод для ее решения.

Этап 1. Построение области допустимых решений.

Сначала проведем оси: на горизонтальной будут указываться значения переменной а на вертикальной – Кроме того, условие неотрицательности переменных показывает, что область допустимых решений (ОДР) будет лежать в первом квадранте (т.е. выше оси и правее оси ). Чтобы учесть ограничения задачи следует заменить неравенства на равенства (получив уравнение прямых), а затем на плоскости провести эти прямые (рис. 2.1).

Заметим, что для построения прямых достаточно определить две произвольные точки. Так, например, для прямой возьмем для первой точки x₁ = 3, тогда . Для второй точки возьмем x₁ = 6, тогда . Через точки (3; 5) и (6; 4) единственным образом можно провести прямую (прямая BC на рис. 2.1).

Рисунок 2.1 – Область допустимых решений

Теперь рассмотрим, как графически интерпретируются неравенства. Каждое неравенство делит плоскость на два полупространства, которые располагаются по обе стороны прямой. Точки плоскости, расположенные по одну сторону прямой, удовлетворяют неравенству (допустимое полупространство), а точки, лежащие по другую сторону, – нет. Тестовой точкой для проверки того, точки какого полупространства удовлетворяют неравенству, а какого – нет, может служить, например, точка (0,0). Например, первому неравенству данная точка удовлетворяет Это означает, что область допустимых решений нашей задачи располагается ниже прямой ВС. Аналогично поступают и с остальными неравенствами. На рис. 2.1 область допустимых решений заштрихована.

Этап 2. Поиск оптимального решения.

Точки пространства допустимых решений, показанного на рис. 2.1, удовлетворяют одновременно всем ограничениям задачи. Это пространство ограничено отрезками прямых, которые соединяются в угловых точках (точках пересечения прямых) ABCDEO. Любая точка, расположенная внутри или на границе области является допустимым решением, т.е. их бесконечное множество. Наша задача – определить оптимальное из этих решений.

Для того чтобы найти оптимальное решение, необходимо определить направление возрастания целевой функции (напомним, что функцию F следует максимизировать). Для этого строится вектор градиента, который начинается в точке (0; 0) и направлен в точку . То есть вектор градиента строится по координатам, совпадающим с коэффициентами целевой функции , и показывает направление ее максимального возрастания. Перпендикулярно ему в направлении градиента откладываются линии уровня (изоцели), на точках которой целевая функция принимает одинаковые значения. На рис. 2.1 видно, что самой крайней изоцелью в пределах ОДР будет изоцель, проходящая через точку С, находящейся на пересечении прямых BC и СD. Эта точка и будет оптимальным решением, дающим максимум целевой функции. Для ее нахождения нужно решить систему:

откуда x₁ = 6, x₂ = 4, то есть С(6; 4).

Итак, при выпуске 6 единиц продукции P1 и 4 единиц P2 прибыль достигает максимального значения: F = 2·6+3·4 = 24.

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