Геометрический метод решения задач линейного
Программирования
Решение начнем с самых простых задач. Однако сразу же отметим, что простота этих задач состоит не в том, что предельно упрощена рассматриваемая ситуация, а в том, что мы сознательно уменьшим количество неизвестных. Суть дела от этого не изменится, а работа очень сильно упростится и, самое главное, появится возможность наглядной графической интерпретации хода решения задач.
Предположим, предприятие планирует выпуск изделий двух видов: изделие А и изделие В. На предприятии имеются два вида ресурсов: норма рабочего времени обрабатывающих станков – 420 часов и наличие применяемого сырья – 80 кг. Допустим также, что известны плановые нормативы затрат этих ресурсов в расчете на единицу каждого изделия и прибыль от реализации каждой единицы этих изделий (см. таблицу 4).
Таблица 4.
| Ресурсы и прибыль | Изделие А | Изделие В |
| Норма рабочего времени станков 420 часов | 0,6 | 0,7 |
| Сырье: 80 кг | 0,1 | 0,2 |
| Прибыль, ден. ед. |
Требуется определить оптимальную структуру выпуска изделий, обеспечивающую максимум прибыли от их реализации.
Обозначим через x1 и x2 неизвестное количество выпускаемых изделий А и В. Для их производства потребуется 0,6x1 + 0,7x2 часов рабочего времени станков и 0,1x1 + 0,2x2 килограммов сырья, ограниченных, соответственно, 420 часами и 80 кг. Математически условия задачи примут следующий вид. Суммарная прибыль от реализации товаров А и В определится функцией (функция цели) f = 5x1 + 8x2 Ì max (1.19)
Система ограничений:
0,6x1 + 0,7x2 ≤ 420 (1.20)
0,1x1 + 0,2x2 ≤ 80 (1.21)
x1 ≥ 0, x2 ≥ 0 (1.22)
Условия (1.22) (прямые ограничения) являются обязательными для всех задач, встречающихся в экономике. Условия (1.20) и (1.21) рассматриваются, как ограничения по ресурсам.
Сформулированная задача является задачей линейного программирования. Наличие только двух переменных позволяет представить условия задачи и ее решение графически. Возьмем прямоугольную систему координат и будем откладывать по оси абсцисс переменную x1 а по оси ординат переменную x2 (рис. 1).
| x2 |
| D |
| M |
| C |
| B |
| A |
| 0 200 400 600 800 x1 |
Рис. 1
Все значения переменных x1 и x2, удовлетворяющие ограничениям (1.20) - (1.21), определяют точки, расположенные внутри многоугольника АОDМ, и именно среди этих значений следует искать оптимальное решение поставленной задачи. Поэтому многоугольник АОDМ часто называют многоугольником решений.
Из всех возможных решений следует выбрать такое (x1˚, x2˚), которое обеспечит максимум прибыли, т.е. максимум функции (1.19): f = 5x1 + 8x2. Для этого проведем прямую линию ЕF (см. рис. 2, где представлен тот же самый многоугольник АОDМ, что и на рис 1), которую мы получим, придав функции f некоторое произвольное значение (например, f = 2000 д.е.).
| f= 2000 |
| M (560; 120) |
| C |
| B |
| D |
| F |
| f=3760 |
| E |
| A |
| 0 200 400 600 800 x1 |
Рис. 2
Отрезок прямой EF оказался полностью расположенным внутри многоугольника решений, причем все точки отрезка (x1 , x2) обеспечивают получение одинаковой прибыли (2000 д. ед.). Однако, эта прибыль не является максимальной. С увеличением f прямая 5x1 + 8x2 = f будет двигаться параллельно самой себе дальше от начала координат. Наконец, при некотором значении f = f0 прямая f0 = 5x1 + 8x2 и многоугольник АОDМ будут иметь только одну общую точку М (x1˚, x2˚). Эти значения переменных: x1˚, x2˚ как раз и будут искомым оптимальным решением задачи, обеспечивающим получение максимальной прибыли. Для того, чтобы определить f0, можно на графике рис. 2 найти координаты точки М, либо решить систему, составленную из уравнений прямых
0,6x1 + 0,7x2 = 420
0,1x1 + 0,2x2 = 80,
найдя их общую точку, которая как раз и будет точкой М. В результате получим x1˚ = 560, x2˚ = 120. Подставим эти значения в функцию f = 5x1 + 8x2. Соответствующая максимальная прибыль составит f˚= 3760 (д. ед.). Это и есть единственное решение нашей задачи, состоящее в том, что при имеющихся ресурсах предприятие получит наибольшую прибыль (3760 д. ед.), если будет выпускать и реализовывать в месяц 560 ед. изделий А и 120 ед. изделий В.
Данные этой задачи были специально подобраны для того, чтобы можно было продемонстрировать ход решения наиболее удобным образом. На практике могут встречаться самые различные ситуации, и даже сама постановка задачи может выглядеть иначе. Пусть, например, объем некоторых ресурсов можно менять в определенных пределах. Как при этом будет изменяться прибыль? Допустим, в условиях предыдущей задачи у руководителя предприятия имеется возможность дополнительно приобрести станок. Увеличится ли при этом прибыль, и если увеличится, то насколько?
Обратимся опять к рисункам 1 и 2. Увеличение ресурса времени станков сверх 420 часов приведет к тому, что прямая АВ отодвинется от начала координат, оставаясь параллельной самой себе. Однако, если точка А окажется дальше от начала координат, чем точка С (рис. 1), то ограничение по рабочему времени в действительности перестает быть ограничением в нашей задаче, поскольку прибыль будет в этом случае определяться полностью ограничением по сырью. Поэтому, увеличивая ресурсы рабочего времени, можно увеличить прибыль только до f0 = 5 * 800 + 8 * 0 = 4000 (д. ед.) (точка М совпадет с точкой С). При этом ресурсы рабочего времени станков составят 0,6 * 800 + 0,7 * 0 = 480 час. Излишние ресурсы не будут израсходованы. При наличии ресурса рабочего времени станков в 480 часов оказывается выгоднее всего ограничиться изготовлением только изделия А в количестве 800 ед. в месяц, а выпуск изделий вида В вообще не производить.
Рассуждая точно так же, можно заключить, что если не увеличивать норму рабочего времени станков, а увеличить количество сырья, то максимально возможная прибыль составит f0 = 5 * 0 + 8 * 600 = 4800 (д. ед.). При этом количество сырья целесообразно увеличить только до 120 кг, и план выпуска изделий составить таким образом, что x1˚ = 0, x2 ˚ = 600, т.е. изделие А вообще не следует изготавливать.
Если предприятию планируется минимальный выпуск по каждому изделию, то математическая постановка задачи несколько изменится и будет выглядеть следующим образом:
при ограничениях 0,6x1 + 0,7x2 ≤ 420 0,1x1 + 0,2x2 ≤ 80
x1 ≥ r1, x2 ≥r2, (r1 ≥ 0, r2 ≥0)
найти max f = max = (5x1 + 8x2)
Значения постоянных r1 и r2 определяются из плановых заданий изготовления изделий А и В и их цен. На рис. 3 показан многоугольник решений при дополнительных ограничениях снизу на количество изготовленных изделий (r1 = r2 = 200 ед.).
| D |
| M |
| C |
| B |
| A |
| М˚ (400; 200) |
| 0 200 400 600 800 x1 |
Рис. 3
Несмотря на то, что возможность для достижения максимальной прибыли от реализации изделий существенно уменьшилась, все еще осталась возможность для маневрирования ресурсами. Максимальная величина прибыли составит f0 = 3600 (д. ед.) при условии, что будет изготовлено x1˚ = 400ед. изделийА и x2˚ = 200 ед. изделий В, тогда как запланированный выпуск изделий составил бы прибыль от реализации f0 = 2600 (д. ед.). Кроме того, образовались бы излишки ресурсов рабочего времени станков, составляющие 40 ч. (0,6*400 + 0,7*200 = 380 ч. < 420 ч.).
Из вышеизложенного следует, что проводить оптимизацию деятельности предприятий можно только в том случае, если есть свобода выбора, математическим выражением которой является наличие многоугольника решений. Если же предприятие вынуждено работать при наличии таких ограничений, которые не образуют многоугольника решений, то проводить оптимизацию невозможно. В этом случае говорят, что осуществляется «жесткое» планирование.
Графический метод решения задачи линейного программирования имеет весьма ограниченную область применения (не более двух переменных). Однако, несмотря на это, он оказывается весьма полезным для интерпретации общих идей, лежащих в основе других методов решений, и для придания им необходимой наглядности. При решении задачи геометрическим способом возможны следующие случаи:
· оптимальное решение единственно: прямая f (x1, x2) = fmax имеет единственную общую точку с многоугольником решений – точку М, рис. 2;
· оптимальных решений бесконечное множество, если уравнение прямой f (x1, x2) = fmax будет совпадать с уравнением одной из прямых, ограничивающих многоугольник допустимых решений;
· оптимальное решение может и не существовать, если система ограничений противоречива (когда многоугольник решений отсутствует) или область допустимых решений не ограничена.
Анализируя оптимальные решения общей задачи линейного программирования на плоскости, можно отметить следующие их свойства:
· оптимальное решение, если оно существует, лежит не внутри, а на границе многоугольника решений;
· если решение единственное, оно достигается в одной из вершин многоугольника решений;
· если решений множество, оно достигается на одной из сторон выпуклого многоугольника.