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

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

 Линейное  программирование — раздел математического  программирования, применяемый при  разработке методов отыскания  экстремума линейных функций  нескольких переменных при линейных  дополнительных ограничениях, налагаемых  на переменные. По типу решаемых  задач его методы разделяются  на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений. 
     Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений. Отсюда — необходимость разработки новых методов. 
     Формы записи задачи линейного программирования: 
     Общей задачей линейного программирования называют задачу 
                         (2.1) 
     при ограничениях 
               (2.2) 
                  (2.3) 
                     (2.4) 
                                 (2.5) 
      - произвольные                   (2.6) 
     где   - заданные действительные числа; (2.1) – целевая функция; (2.1) – (2.6) –ограничения;   - план задачи. 
     Пусть ЗЛП представлена в следующей записи: 
                                                       (2.7) 
                                        (2.8) 
                                            (2.9) 
     Чтобы задача (2.7) – (2.8) имела решение, системе её ограничений (2.8) должна быть совместной. Это возможно, если  r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r=n система имеет единственное решение, которое будет при  оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть r<n. В этом случае система векторов  содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть несколько, но не более  . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные n – r переменных будутсвободными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов  . Этому базису соответствуют базисные переменные  , а свободными будут переменные  . 
     Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным решением (планом). 
     Теорема. Если система векторов   содержит m линейно независимых векторов  , то допустимый план  
                                       (2. 10) 
     является крайней точкой многогранника планов. 
     Теорема. Если ЗЛП имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника решений. Если же целевая функция достигает экстремального значения более чем в одной крайней точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией.

Графический способ решения ЗЛП    

 Геометрическая  интерпретация экономических задач  дает возможность наглядно представить, их структуру, выявить особенности  и открывает пути исследования  более сложных свойств. ЗЛП с  двумя переменными всегда можно  решить графически. Однако уже  в трехмерном пространстве такое  решение усложняется, а в пространствах, размерность которых больше трех, графическое решение, вообще говоря, невозможно. Случай двух переменных  не имеет особого практического  значения, однако его рассмотрение  проясняет свойства ОЗЛП, приводит  к идее ее решения, делает геометрически  наглядными способы решения и  пути их практической реализации. 
     Пусть дана задача 
                                          (2.11) 
                                         (2.12) 
                                                (2.13) 
     Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (2.12), (2.13) задает на плоскости  некоторую полуплоскость. Полуплоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (2.11) — (2.13)  есть выпуклое множество. 
     Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП — непустое множество, например многоугольник  . 
       
      Выберем произвольное значение целевой функции  . Получим  . Это уравнение прямой  линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение  . Считая в равенстве (2.11)   параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения). 
     Найдём частные производные целевой функции по   и  : 
      ,                                                (2.14) 
      .                                               (2.15) 
     Частная производная (2.14)  (так же как и (2.15)) функции показывает скорость ее возрастания вдоль данной оси. Следовательно,   и   — скорости возрастания   соответственно вдоль осей   и  . Вектор   называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции: 
       
     Вектор   указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом. 
     Вектор   перпендикулярен к прямым   семейства   . 
     Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок ее графического решения. 
     1. С учетом системы ограничений строим область допустимых решений  . 
     2. Строим вектор   наискорейшего возрастания целевой функции — вектор градиентного направления. 
     3. Проводим произвольную линию уровня   .  
     4. При решении задачи на максимум перемещаем линию уровня   в направлении вектора   так, чтобы она касалась области допустимых решений в ее крайнем положении (крайней точке). В случае решения задачи на минимум линию уровня   перемещают в антиградиентном направлении.  
     5. Определяем оптимальный план   и экстремальное значение целевой функции  .

Симплексный метод решение ЗЛП    

 Общая идея  симплексного метода (метода последовательного  улучшения плана) для решения  ЗЛП состоит 
     1) умение находить начальный опорный план; 
     2) наличие признака оптимальности опорного плана; 
     3) умение переходить к нехудшему опорному плану. 
     Пусть ЗЛП представлена системой ограничений в каноническом виде: 
      . 
     Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части   левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю. 
     Пусть система ограничений имеет вид 
       
     Сведем задачу к каноническому виду. Для этого прибавим к левым частям неравенств дополнительные переменные    . Получим систему, эквивалентную исходной:  
      , 
     которая имеет предпочтительный вид  
      . 
     В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю    . 
     Пусть далее система ограничений имеет вид 
      . 
     Сведём её к эквивалентной вычитанием дополнительных переменных     из левых частей неравенств системы. Получим систему  
      . 
     Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные   входят в левую часть (при  ) с коэффициентами, равными –1. Поэтому, вообще говоря, базисный план   не является допустимым. В этом случае вводится так называемый искусственный базис. К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные  . В целевую функцию переменные  , вводят с коэффициентом М в случае решения задачи на минимум и с коэффициентом - М для задачи на максимум, гдеМ - большое положительное число. Полученная задача называется М-задачей, соответствующей исходной. Она всегда имеет предпочтительный вид. 
     Пусть исходная ЗЛП имеет вид 
      ,                      (2.16) 
      ,        (2.17) 
        ,                         (2.18) 
     причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так: 
                 (2.19) 
                            (2.20) 
        ,  ,                   (2.21) 
     Задача (2.19) - (2.21) имеет предпочтительный план. Её начальный опорный план имеет вид 
       
     Если некоторые из уравнений (2.17) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.