Математическое программирование (линейное программирование). Киселева Э.В - 18 стр.

                                                                        4. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ
                                                                             ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

                                                                   Рассмотрим графический метод решения ЗЛП в стандартной
                                                                форме с двумя переменными, т.е. задачи вида:
                                                                       Найти вектор (x1 , x2 ) , удовлетворяющий системе ограниче-
                                                                                           T

           а                 б              в                   ний:
                    Рис. 3.2. Примеры множеств                                            ⎧a11 x1 + a12 x2 ≤ b1 ,
     Определение 3.6. Точка X1 выпуклого множества D на-                                  ⎪a x + a x ≤ b ,
                                                                                          ⎪ 21 1      22 2     2
зывается его угловой (крайней) точкой, если она не может                                  ⎨
быть представлена выпуклой линейной комбинацией двух                                      ⎪ K          K        K
других точек этого множества (не является внутренней                                      ⎪⎩am1 x1 + am 2 x2 ≤ bm ,
точкой ни для какого отрезка, концы которого принадле-
жат множеству D).
                                                                                             x1 ≥ 0 ,       x2 ≥ 0 ,
     Например, крайними точками треугольника являются его       для которого функция цели Z = c1x1+c2x2 достигает максимума.
вершины, крайними точками круга – точки окружности, которая          Графический метод решения ЗЛП условно можно разбить на
его ограничивает.                                               два этапа:
     Однако не всякое выпуклое множество имеет крайние точки.        1. Построение ОДР ЗЛП.
Прямая, плоскость, полуплоскость, пространство, полупростран-
ство угловых точек не имеют.
                                                                                                                       (     )T
                                                                    2. Нахождение среди всех точек ОДР такой точки x1∗ , x2∗ , в
                                                                которой целевая функция Z принимает максимальное значение.
     Определение 3.7. Выпуклым многогранником (много-
                                                                    Перейдем к рассмотрению этих этапов.
угольником на плоскости) называется замкнутое ограни-
ченное выпуклое множество, имеющее конечное число
                                                                                                   ЭТАП 1
крайних (угловых) точек.
     Теорема 3.2. Любая точка выпуклого многогранника              4.1. Геометрическая интерпретация множества решений
может быть представлена как выпуклая линейная комби-                               линейного неравенства
нация его вершин (крайних точек).                                      Рассмотрим неравенство:
                                                                                               a1 x1 + a 2 x2 ≤ b .
                                                                    Известно, что точки, координаты которых удовлетворяют
                                                                уравнению a1 x1 + a 2 x2 = b , лежат на прямой. Назовем эту пря-
                                                                мую граничной. Граничная прямая разбивает плоскость на две
                                                                полуплоскости. Координаты точек одной полуплоскости удовле-
                                                                творяют исходному неравенству a1 x1 + a2 x2 ≤ b , а другой полу-
                                                                плоскости – неравенству a1 x1 + a2 x2 ≥ b. Следовательно, геомет-
                                                                рической интерпретацией множества решений линейного нера-
                                 37                                                                     38