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

тимых решений достигают экстремальных значений одновремен-                вим к левым частям ограничений-неравенств. В целевую функ-
но. Оптимальному решению ( x1∗ ,K , xn∗ ) задачи (3.1)–(3.3) соот-        цию все дополнительные переменные введем с коэффициентами,
                                                                          равными нулю. Получим каноническую форму модели:
ветствует оптимальное решение ( x1∗ , K , x n∗+ m ) задачи (3.4)–(3.6),            Z = 5 x1 + 3 x 2 + 0 ⋅ x3 + 0 ⋅ x 4 + 0 ⋅ x5 + 0 ⋅ x6 → max,
т.е. исходная модель и ее каноническая форма эквивалентны.                                    ⎧2 x1 + 3 x 2 + x3             = 20,
      Пример. При производстве двух видов изделий (А и В)                                     ⎪
предприятие использует 4 вида ресурсов. Нормы расхода ресур-                                  ⎪3 x1 + 2 x3       + x4         = 15,
                                                                                              ⎨
сов на производство единицы продукции, объем ресурсов, а так-                                 ⎪4 x1                + x5      = 16,
же прибыль от реализации единицы продукции приведены в таб-                                   ⎪⎩     3x2               + x 6 = 12,
лице:
                        Нормы затрат ресурсов         Объем                                     xj ≥0                   ( j = 1,6).
      Вид ресурса
                            А              В          ресурса                 Отметим экономический смысл дополнительных перемен-
           1                2              3            20                ных. Очевидно,
           2
           3
                            3
                            4
                                           1
                                           0
                                                        15
                                                        16                                      xn+i = bi − ∑ aij x j
                                                                                                                        2
                                                                                                                                        (i = 1,4) ,
                                                                                                                        j =1
           4                0              3            12
        Прибыль             5              3                              т.е. дополнительная переменная xn +i показывает величину не-

    Определить оптимальный план производства продукции,                   использованного i-го ресурса (i = 1,4 ) .
обеспечивающий предприятию максимальную прибыль.
                                                                               3.4.2. Переход от канонической формы модели задачи
    Составить математическую модель задачи и привести ее к
                                                                                    линейного программирования к стандартной
каноническому виду.
                                                                              Пусть ЗЛП задана в канонической форме:
    Решение. Обозначим через X = (x1 , x 2 )T план выпуска про-                                                  n
дукции. Модель задачи примет вид:                                                                    Z = ∑ c j x j → max ,
                                                                                                                 j =1
                          Z = 5 x1 + 3x2 → max ,
                                                                                                                                    (         )
                                                                                                     n
                          ⎧2 x1 + 3 x2 ≤ 20 ,                                                      ∑a       ij   x j = bi i = 1, m ,
                          ⎪3 x + x ≤ 15,                                                            j =1
                          ⎪ 1 2
                          ⎨
                                     ≤ 16 ,
                                                                                                           xj ≥ 0              ( j = 1, n).
                          ⎪4 x1                                               Первый способ
                          ⎪⎩     3x2 ≤ 12 ,                                   Каждое ограничение-равенство может быть заменено экви-
                             x1 ≥ 0; x2 ≥ 0.                              валентной системой неравенств:
    Модель записана в стандартной форме.
    Перейдем к модели в каноническом виде. Введем балансо-
вые неотрицательные переменные x3 , x 4 , x5 , x 6 , которые приба-

                                   33                                                                                          34