Математика. Курзина В.М - 316 стр.

                                     316

      Чтобы решить задачу линейного программирования, необходимо
среди точек этого многоугольника найти такую точку, в которой линейная
функция F = c1 x1 + c2 x2 принимает максимальное (или минимальное, если
это требуется в условиях задачи) значение.

   x2                         C


                 B
        F=Fmin
                                            F=Fmax


  F=0
           A                                D

           q                 F= a
                       E
                                                          x1


                                    Рис.1

      Рассмотрим так называемую линию уровня линейной функции F, т.е.
линию, вдоль которой эта функция принимает одно и то же значение a. Та-
ким образом, уравнение, задающее линию уровню запишется
                                       F = a,
или
                                 c1 x1 + c2 x2 = a .
      Это уравнение задает прямую линию на плоскости (см. рис. 1). При
графическом решении задач линейного программирования следует по-
строить множество линий уровня для различных значений a и на много-
угольнике решений найти точку, через которую проходит линия уровня
функции F с наибольшим (если функция максимизируется) или наимень-
шим (если она минимизируется) уровнем.
      Все линии уровня функции F параллельны. Направление, в котором
значение функции F возрастает при смещении линии уровня параллельно
самой себе, показывает вектор нормали к прямой (линии уровня)
q = (c1 ; c2 ) . При смещении линии уровня в направлении против направлени
вектора нормали значение функции F убывает.
      Пример. Решить геометрически задачу линейного программирования
                                F = x1 + x2 → max
при ограничениях