Системное програмирование

 
 

Вариант 10.

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

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

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

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

На рис. 2.1 изображено выпуклое множество (выпуклый многоугольник), а на рис. 2.2 - невыпуклое.

Определение 2. Пересечение конечного числа выпуклых множеств также выпуклое множество.

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

Утверждение 1. Множеством решений системы m линейных неравенств с n переменными является выпуклый многогранник в n-мерном пространстве (исключая случай, когда система несовместна).

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

  Теоремы линейного программирования:

  Теорема 1. Множество допустимых решений основной задачи линейного программирования выпукло.

  Теорема 2. Линейная функция задачи линейного программирования достигает своего экстремального значения в крайней точке множества решений.

  При решении системы ограничений  могут возникнуть следующие случаи:

1) Система  ограничений несовместна, поэтому  отыскать  оптимальное решение  невозможно (рис. 2.8).

2) Система  ограничений имеет единственное  решение (рис. 2.9).

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

4) Система  ограничений имеет бесчисленное  множество решений (рис. 2.11).

             Рис. 2.8                           Рис. 2.9                            Рис. 2.10                          Рис. 2.11 

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

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

    

рис. 2.6

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

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

с₁х₁ + с₂х₂ = а (2.14)

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

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

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

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

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

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

F = с₁х₁ + с₂х₂ =а₁, (I)

F = с₁х₁ + с₂х₂ = а₂ (II)

F = с₁х₁ + с₂х₂ =а₃, (III)

причем  линия II заключена между линиями I и III. Тогда а₁ < а₂ < а₃ или а₁ > а₂ > а₃

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

рис. 2.7

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

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

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

Найдем  решение задачи, состоящей в определении  максимального значения функции

F=c₁x₁+c₂x₂ (2.15)

при условиях

a_i1x₁ + a_i2x₂ £ b_i (i=1, k ), (2.16)

(j = 1,2).  (2.17)

Каждое  из неравенств (2.16), (2.17) системы ограничений  задачи геометрически определяет полуплоскость  соответственно с граничными прямыми  a_i1x₁ + a_i2x₂ = b_i (i=1, k ), x₁=0 и х₂ = 0. В том случае, если система неравенств (2.16), (2.17) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей — выпуклое, то областью допустимых решений задачи (2.15) —(2.17) является выпуклое множество, которое называется многоугольником решений (введенный ранее термин «многогранник решений» обычно употребляется, если n ³ 3). Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.

   Таким образом, исходная задача линейного  программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция  F принимает максимальное значение. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня c₁x₁+c₂x₂ = а (где а — некоторая постоянная), проходящую через многоугольник решений, и будем передвигать ее в направлении вектора С=(с₁; c₂) до тех пор пока она не пройдет через последнюю ее общую точку с многоугольником решений. Координаты указанной точки и определяют оптимальный план данной задачи.

Заканчивая  рассмотрение геометрической интерпретации  задачи (2.11) —(2.17), отметим,

 
 
 
 
 
 
 
 
 

                                  

                            рис. 2.8                                                 рис. 2.9

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

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

Отметим, что нахождение минимального значения линейной функции при данной системе  ограничений отличается от нахождения ее максимального значения при тех  же ограничениях лишь

тем, что  линия уровня c₁x₁+c₂x₂ = h  передвигается не в направлении вектора С=(с₁; c₂), а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее

минимального  значения.

Итак, нахождение решения задачи линейного программирования (2.15)—(2.17) на основе ее геометрической интерпретации включает следующие  этапы:

1. Строят прямые, уравнения которых получаются в результате замены в ограничениях (2.16) и (2.17) знаков неравенств на знаки точных равенств.
2. Находят полуплоскости, определяемые каждым из ограничений задачи.
3. Находят многоугольник решений.
4. Строят вектор =(с₁; c₂).
5. Строят прямую c₁x₁+c₂x₂ = а, проходящую через многоугольник решений.
6. Передвигают прямую c₁x₁+c₂x₂ = а в направлении вектора , в результате чего либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность сверху функции на множестве планов.
7. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.

Пример 1

Минимизировать  функцию

F = -3x₁ — 4х₂ 
 

рис. 2.12

при ограничениях х ₁, х₂ ³  0,

х₁ + х₂ £ 20,

-х₁ + 4х₂ £ 20,

х₁ ³ 10,

х₂ ³  5.