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

     На втором шаге два последних уравнения обратились в то-             3. РАЗЛИЧНЫЕ ФОРМЫ МОДЕЛИ ЗАДАЧИ
ждественные равенства 0 = 0. Исключаем их из дальнейшего рас-               ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
смотрения. Первым двум строкам соответствует система уравне-
ний:                                                                В зависимости от особенностей системы ограничений все
                         ⎧2 x1 − x3 + x4 = 1,                   постановки основной ЗЛП укладываются в три основные формы:
                         ⎨                                      стандартную, каноническую, общую.
                         ⎩3 x1 + x2 − x3 = 2 ,
которая эквивалентна исходной.                                                3.1. Формулировка основной задачи
    Так как число неизвестных больше числа уравнений, то сис-                    линейного программирования
тема является неопределенной. Ее общее решение имеет вид:
                                                                                    3.1.1. Общая форма модели
                          x4 = 1 − 2 x1 + x3 ,
                                                                     Общая форма модели ЗЛП характеризуется следующим
                          x2 = 2 − 3 x1 + x3 ,
                                                                образом:
где x1 и x3 − любые действительные числа.                            Найти совокупность значений n переменных x1 , x2 ,K , xn ,
      Переменные x1 и x3 являются свободными, а переменные      удовлетворяющих системе ограничений:
 x2 и x4 − базисными.                                                                ⎧a11 x1 + K + a1n xn = b1 ,
      Так как свободные переменные могут принимать любые                             ⎪K K K K K K K
значения, то система имеет бесчисленное множество решений.                           ⎪
      Полагая значения свободных переменных равными нулю                             ⎪⎪ak 1 x1 + K + akn xn = bk ,
                                                                                      ⎨
(x1 = x3 = 0) , получим x2 = 2, x4 = 1 .                                              ⎪ak +1,1 x1 + K + ak +1,n xn ≤ bk +1 ,
      Полученное таким образом решение:                                               ⎪K K K K K K K
                                     ⎛0⎞                                              ⎪
                                     ⎜ ⎟                                              ⎪⎩am1 x1 + K + amn xn ≤ bm
                                     ⎜ 2⎟                       и условиям неотрицательности:
                                X =⎜ ⎟
                                       0
                                     ⎜ ⎟                                           x1 ≥ 0, x 2 ≥ 0, K , xt ≥ 0 (t ≤ n ) ,
                                     ⎜1 ⎟                       для которых линейная функция (целевая функция)
                                     ⎝ ⎠
называется базисным решением системы.                                                 Z = c1x1 + c2 x2 + K + cn xn
       Ответ. Задача имеет бесчисленное множество решений:      достигает экстремума (максимума или минимума).
                          x4 = 1 − 2 x1 + x3 ,                                  3.1.2. Стандартная форма модели
                         x2 = 2 − 3 x1 + x3 ,
                                                                     Найти совокупность значений n переменных x1 , x2 ,K , xn ,
где x1 и x3 − произвольные действительные числа.                удовлетворяющих системе ограничений:
                                                                                           n
                                                                                           ∑ aij x j ≤ bi    (i = 1, m)
                                                                                           j =1


                                27                                                                      28