Решение задач линейной оптимизации с использованием MathCad и Excel. Бундаев В.В. - 2 стр.

                                    3                                                                                               4

                                                                                                                                   r
                                                                            производные ни в какой точке X ∈ U не равны нулю. Отметим
    1. ФОРМУЛИРОВКА ОБЩЕЙ ЗАДАЧИ ЛИНЕЙНОГО                                                                           r
    ПРОГРАММИРОВАНИЯ                                                        также, что минимум F ( X ) всегда достигается либо в вершинах
                                                                            многоугольника (многогранника) допустимых решений, либо на
    Пусть в m-мерном векторном пространстве Еm необходимо                   его границе.
                           r
выбрать такой вектор X = {x1 , x 2 ,..., x m } , который удовлетворя-
                                                                                2. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО
ет следующим ограничениям:                                                      ПРОГРАММИРОВАНИЯ В КАНОНИЧЕСКОЙ ФОРМЕ
   ai1 ·х1 + ai 2 ·х 2 + ... + aim ⋅ x m ≤ b i ,
                                                                   (1.1)       Вводя дополнительные переменные xm+q ≥ 0, q = 1,2,…n-m
   a k1 ·х1 + a k 2 ·х 2 + ... + a km ⋅ x m = b k ,                        все ограничения-неравенства можно записать в виде равенств.
   a ·х + a ·х + ... + a ⋅ x ≥ b , i ≠ k ≠ p                               Следовательно, любая задача линейного программирования мо-
    p1 1        p2     2            pm    m      p
                                                                            жет быть записана в каноническом виде:
   x j ≥ 0, j = 1,2,..., m;           bi ≥ 0, bk ≥ 0, b p ≥ 0
                                                                                           a11 x1 + a12 x 2 + ⋅ ⋅ ⋅ + a1n x n = b1
для которого достигается минимум линейной функции, т.е.                                    a x + a x + ⋅⋅⋅ + a x = b
         F(x1,x2,…,xm) = c1·x1 + c2·x2+…+ cm·xm,        (1.2)                              21 1                22 2                        2n n              2      (2.1)
                                                                                          
                                                                                          ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
и определить значение этого минимума.
    Отметим, что если в конкретной задаче требуется отыскание
                                                                                           a m1 x1 + a m 2 x 2 + ⋅ ⋅ ⋅ + a mn x n = bm
не минимума, а максимума функции F(x1,x2,…,xm), то эту задачу
можно превратить в задачу на поиск минимума, поменяв знак                             x j ≥ 0; bi ≥ 0; i = 1,..., m; j = 1,...n                                      (2.2)
целевой функции на обратный, т.е.                                                                      r
                                            {      }
                            r             r                                                                          n

                      r F ( X ) = min
                     max           r  − F(X )                                                   F ( X ) = ∑ c j x j → min,                                           (2.3)
                       X                X                                                                            j =1
    Также заметим, что ограничения (1.1), так же как и функция                   r
(1.2), являются линейными.                                                  где X = ( x1 , x 2 ,..., x n ) - вектор неизвестных в пространстве En;
                                                                                r
    Таким образом, приведенные соотношения (1.1)-(1.2) можно                    C = (c1 , c 2 ,..., c n ) - вектор коэффициентов целевой функции
считать общей формой записи задачи линейного программиро-
                                                                            (2.3);
вания. При этом функцию F(x1,x2,…,xm) называют целевой
                            r                                                   A = (aij) – прямоугольная матрица коэффициентов системы
функцией, а множество точек X ∈ U , на котором ищется ми-                   уравнений (2.1), размерность m×n; m - число уравнений, n –
нимум этой функции – множеством допустимых решений.                         число неизвестных в системе (2.1).
Это множество описывается системой ограничений (1.1) и пред-                     r
                                                                                 B = (b1 , b2 ,..., bm ) - вектор правых частей системы уравнений
ставляет собой выпуклый многоугольник или многогранник.
    Решение поставленной задачи (1.1)-(1.2) на нахождение экс-              (2.1);
тремума с помощью обычного способа приравнивания нулю                               Можно показать, что всякому решению системы ограничений
производной целевой функции (1.2) и решения системы полу-                   (1.1) соответствует определенное решение системы линейных уравнений
                                                                r           (2.1), у которого те же самые значения основных переменных х1,
ченных уравнений непригодны ввиду линейности F ( X ) , т.е. ее              х2,…,хm.