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

                        ⎧n
                        ⎪∑ a ij x j ≤ bi ,
                                                                                                                    n
                                                                                                                                       (
                                                                                                                  ∑ α ij x j ≤ β i i = 1, m .  )
                                                                                                               j = m +1
                        ⎪ j =1
                        ⎨n                                                                 Стандартная форма модели ЗЛП примет вид:
                        ⎪ a x ≥b
                        ⎪⎩∑    ij j    i                 (i = 1,m).                                                     n
                                                                                                            Z = ∑ γ j ⋅ x j + γ 0 → max ,
                          j =1
                                                                                                                    j = m +1
               n
                             (             )
Неравенства ∑ a ij x j ≥ bi i = 1, m умножением обеих частей на –1
                                                                                                              n
                                                                                                              ∑ α ij x j ≤ β i           (i = 1, m),
              j =1                                                                                          j = m +1
                                           n
превращаются в неравенства − ∑ a ij x j ≤ −bi i = 1, m .       (           )                                        xj ≥ 0     ( j = m + 1, n) .
                                          j =1
    Второй способ                                                                                           3. 5. Выпуклые множества
    Предположим, в системе ограничений:
                         n
                         ∑ a ij x j = bi                (i = 1, m)                           Определение 3.4. Вектор λ1 X 1 + λ 2 X 2 + K + λ m X m назы-
                         j =1                                                          вается выпуклой линейной комбинацией векторов
канонической формы модели m < n и все m уравнений линейно                              X 1 , X 2 ,K , X m , если коэффициенты λ1 , λ2 ,K , λm удовле-
независимы (ранг системы r = m ). В этом случае система имеет
                                                                                       творяют условиям:
бесчисленное множество решений. Ее можно разрешить относи-                                                    m
тельно m переменных x1 , x 2 , K, x m , например методом Жорда-                                              ∑ λi = 1, λi ≥ 0 (i = 1,m ) .
                                                                                                             i =1
на–Гаусса, если векторы-столбцы коэффициентов при этих неиз-
вестных линейно независимы:                                                                 В частности, выпуклой линейной комбинацией двух векто-
                                                                                       ров (точек) X 1 и X 2 является вектор:
                      xi = β i − ∑ α ij x j
                                           n
                                                             (i = 1, m).       (3.7)                         (1 − λ ) X 1 + λX 2 , где 0 ≤ λ ≤ 1.
                                         j = m +1
                                                                                            Определение 3.5. Множество D векторов (точек) ли-
    В этом случае x1 , x 2 , K, x m являются базисными перемен-
ными, а x m +1 , x m + 2 , K , x n − свободные переменные.                             нейного пространства R n называется выпуклым, если
    Целевую функцию также выразим через свободные перемен-                             вместе с любыми его двумя точками X 1 и X 2 ему при-
                                     (              )
ные, подставив значения xi i = 1, m из равенств (3.7) в функцию
                                                                                       надлежит отрезок, соединяющий эти точки.
                                                                                           Аналитически условие выпуклости множества D ⊂ R n за-
цели.
    В результате преобразования получим:                                               писывается следующим образом: для любых X 1 ∈ D , X 2 ∈ D и
                                 n                                                     любого 0 ≤ λ ≤ 1 выполняется условие:
                      Z = ∑ γ j ⋅ x j + γ 0 → max ,
                             j = m +1
                                                                                                              (1 − λ )X 1 + λ X 2 ∈ D .
так как x j ≥ 0 , то из равенств (3.7) имеем:                                              На рис. 3.2 изображены выпуклые множества (а, б) и множе-
                                                                                       ство, не являющееся выпуклым (в).

                                               35                                                                                36