Полная версия

Главная arrow Экономика arrow Исследование операций в экономике

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

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

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

Рассмотрим задачу в стандартной форме (1.4)-(1.6) с двумя переменными п = 2. К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных п больше числа уравнений т на 2, т.е. пт = 2.

Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис. 4.1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F = с1х1 + с2х2 принимает максимальное (или минимальное) значение.

Рассмотрим так называемую линию уровня линейной функции F, т.е. линию, вдоль которой функция принимает одно и то же фиксированное значение а, т.е. F= а, или

(4.1)

Линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии, так называемые изотермы, есть не что иное, как линии уровня температуры Т = с. Еще более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.

Предположим, надо найти самую северную точку какой-либо области, например страны или материка. Это будет точка, имеющая наибольшую широту, т.е. точка, через которую проходит параллель (линия уровня) с самой большой широтой (уровнем).

Рис. 4.1

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

Уравнение линии уровня функции (4.1) есть уравнение прямой линии. При различных уровнях а линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением коэффициентов с1 и с2 и, следовательно, равны. Таким образом, линии уровня функции F – это своеобразные "параллели", расположенные обычно под углом к осям координат.

Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в другую сторону – только убывает.

Пусть имеются три линии уровня:

причем линия II заключена между линиями I и III. Тогда αχ< а2< а3 или а{> а2> а3.

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

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

Рис. 4.2

функция принимает максимальное или минимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 4.1 это точка С или А).

4.1. Решить геометрически задачу 1.1 из параграфа 1.2:

при ограничениях:

Решение. Изобразим многоугольник решений (аналогично тому, как в задаче 2.5) на рис. 4.3. Очевидно, что при F= = 0 линия уровня { + 2 = 0 проходит через начало координат (строить ее не обязательно). Зададим, например, F= б и построим линию уровня { + Зх2 = 6. Ее расположение указывает на направление возрастания линейной функции (вектор q)[1] (см. рис. 4.3). Так как рассматриваемая задача – на отыскание

максимума, то оптимальное решение – в угловой точке С, находящейся на пересечении прямых I и II, т.е. коошшнаты точки

С определяются решением системы уравнений

откуда т.е. С (6; 4).

Максимум (максимальное значение) линейной функции равен

Итак, : при оптимальном решении т.е. максимальная прибыль в 24 руб.[2] может Рыть достигнута при производстве 6 единиц продукции Р, и 4 единиц продукции Р2. ►

4.2. Решить геометрически задачу 1.2 из параграфа 1.2: при ограничениях:

Решение. Многогранник решений представляет собой неограниченную многоугольную область (рис. 4.4). По расположению линии уровня, например F = 12, или находим направление вектора(этот вектор указывает на направление возрастания линейной функции). Очевидно, что точка минимума – это точка В "входа" в многоугольник решений, ибо при дальнейшем перемещении линии уровня в направлении векторазначения линейной функции увеличиваются.

Находим координаты точки В (2; 3), при этом

Итак,при оптимальном решении

т.е. минимальная стоимость рациона 26 руб., если в него включить 2 единицы корма I и 3 единицы корма II. ►

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

О 4.3. Решить геометрически следующие задачи:

  • а)
  • б)

при ограничениях: при ограничениях:

Решение. 1) Геометрическое решение задачи показано на рис. 4.5, а, из которого следует, что линия уровня с максимальным уровнем совпадает с граничной линией Л В многоугольника решений ABCD, т.е. с линией . Следовательно, на всем отрезке АВ линейная функция принимает одно и то же максимальное значение, равное . Это означает, что задача имеет бесконечно много оптимальных решений (их задают координаты точек отрезка АВ), среди которых базисных оптимальных решений два – соответственно в угловых точках А (3;5) и В (6; 2).Точки отрезка АВ задаются уравнением , где

Рис. 4.5

Итак, Fmax = 24 при бесконечном множестве оптимальных решений хх = с, х2 = 8 – с, где 3 < с < 6.

Замечание. При геометрическом решении подобных задач важно точно установить, действительно ли совпадает линия уровня с границей многоугольника решений или это связано с неточностью построений, мелким масштабом рисунка и т.п. Ответ на этот вопрос будет положительным, если линия уровня и граничная прямая параллельны, т.е. их коэффициенты при переменных пропорциональны. В рассматриваемом примере коэффициенты при переменных линии уровня F = 3χί + Зх2 пропорциональны соответствующим коэффициентам граничной прямой х{ + х2 = 8.

2) Геометрическое решение задачи показано на рис. 4.5, б, из которого следует, что если линию уровня перемещать в направлении убывания линейной функции (т.е. в направлении, противоположном вектору q), то она всегда будет пересекать многоугольник решений, следовательно, линейная функция неограниченно убывает.

Итак, конечного оптимума линейной функции нет[3], т.е. !!!F ■ =

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

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

Однако только геометрический метод решения никак не может удовлетворить ни математиков, ни экономистов. Возможны "технические" погрешности, которые неизбежно возникают при приближенном построении графиков. Второй недостаток геометрического метода заключается в том, что многие величины, имеющие четкий экономический смысл (такие, как остатки ресурсов производства, избыток питательных веществ и т.п.), не выявляются при геометрическом решении задач. Но самое главное – геометрический метод неприемлем для решения практических задач. Его можно применить только в том случае, когда число переменных в стандартной задаче равно двум. Поэтому необходимы аналитические методы, позволяющие решать задачи линейного программирования с любым числом переменных и выявлять экономический смысл входящих в них величин. Эти методы будут рассмотрены в следующих главах.

  • [1] Вектор q является градиентом функции F(x), т.е. q = grdiF(xv х2) = = (Cj, с2), который перпендикулярен линии уровня. В данном случае q = = (2; 3).
  • [2] Напоминаем, что η задаче все цифры условные.
  • [3] Если задачу с той же линейной функцией и с той же системой ограничений решать на максимум (F–"max), то линию уровня следует перемещать в направлении возрастания F(т.е. в направлении вектора у́), и в этой задаче отсутствует конечный оптимум (см. рис. 4.5, 6), т.е. Fmax =+°°.
 
<<   СОДЕРЖАНИЕ   >>