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

Задачу ЛП можно решать аналитическими и графическими методами. Аналитические методы являются основой для решения задачи на ЭВМ. Их единственный недостаток заключается в том, что в отличие от графических методов они недостаточно наглядны. Графические методы достаточно наглядны, но они пригодны лишь для решения задач на плоскости.

Теорема Вейерштрасса:

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

Для линейной функции:

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

Алгоритм метода:

1) Построить систему ограничений в виде прямых.

2) Определить допустимую область, в которой ограничение выполняется. Для этого координаты произвольной точки подставляем в ограничение. Если неравенство выполняется, значит выбранная точка лежит в допустимой полуплоскости. Недопустимую полуплоскость будет зачеркивать

3) Определить область допустимых решений (ОДР), в которой выполняются все ограничения одновременно.

4) Рассчитать координаты вершин ОДР, из решения систем 2-х линейных уравнений, образующих эту вершину.

5) Вычислить значение критерия в каждой вершине. Из сопоставления полученных значений определить оптимальную вершину.

Пример 2. 3.1.

Трикотажное ателье изготавливает два вида изделий из шерстяной пряжи. Трудоемкость изготовления изделия вида A₁ в 2,5 раза выше трудоемкости изготовления изделия вида А₂. Если бы ателье выпускало только изделия вида А₁, суточный объем производства мог бы составлять 26 изделий. Суточный объем сбыта изделий вида А₁ ограничен до 17 изделий: изделий вида А₂ – до 35 штук. Прибыль от продажи изделия вида А₁ равна 20 дол., а изделия вида А₂ – 11 долл. Определить, какое количество изделий каждого вида следует изготовлять ателье, чтобы получить максимальную прибыль.

Математическая формулировка задачи

х₁ – количество изделий вида А₁, х₂ – количество изделий вида А₂.

Получим ограничения на совместный выпуск продукции.

Так как трудоемкость изготовления изделий вида А₂ в 2,5 раза ниже, то если бы ателье изготавливало только изделия вида А₂, то ателье выпустило бы в 2,5 раза больше изделий, а именно 65 изделий вида А₂ (2,5×26= 65).

Уравнение прямой, проходящей через точки К(26;0) и М(0;65)

; ;

65×х₁-26×65=-26×х₂

65×х₁+26× х₂=1960 /13

5×х₁+2×х₂=130

тогда ограничение на совместный выпуск изделий примет вид

5×х₁+2×х₂ 130

Математическая модель задачи

f=20х₁+11х₂®max

х₁£17 (1)

х₂£35 (2)

5×х₁+2×х₂ 130 (3)

х_i³0, i=1,2

Находим отрезки, которые прямая 5×х₁+2×х₂=130 (3) отсекает по осям:

при х₁=0 5×0+2х₂ =130; х₂= =65

при х₂=0 5×х₁+2×0 =130; х₁= =26

Рис.6. Графическое решение задачи

Допустимую область, в которой выполняется неравенство находим путем подстановки координат любой точки, например точки О(0;0) в неравенство. Если неравенство выполняется для точки, то эта точка принадлежит допустимой области. 5^.0+2^.0=0<130. Допустимая область лежит на прямой (3) и ниже. Зачеркиваем недопустимую область решений.

Переменная х₁³ 0 в первом и четвертом квадранте, поэтому зачеркиваем второй и третий квадрант.

Переменная х₂³ 0 в первом и втором квадранте, зачеркиваем недопустимые третий и четвертый квадранты.

Область допустимых решений - это многоугольник ОАВСД.

Найдем координаты вершины В из решения системы уравнений прямых (2) и (3).

х₂=35 (2)