Линейное программирование. Филькин Г.В. - 11 стр.

      Мы рассмотрим две модификации симплексного метода сначала изу-
чим простейший случай – случай когда в матрице ограничений есть единич-
ная подматрица порядка m, где m – число ограничений или, что то же самое в
системе векторов А1, А2, ….. Аn в разложении (Д) есть m – единичных и раз-
личных, очевидно, что эти вектора являются линейно независимыми и обра-
зуют базис m-мерном пространстве.
      Для простоты будем рассматривать симплексный метод и его основные
идеи на конкретном примере. Основную работу будем вести в специальной
таблице (симплексная таблица).
      Задача 1. Для изготовления различных изделий А,В,С предприятие ис-
пользует 3 вида сырья. Информация о производстве и запасах сырья приве-
дена в таблице. Требуется составить план производства изделий, при котором
общая стоимость всей произведённой продукции будет наибольшей.

                        Нормы затрат сырья на одно изделие
 Вид сырья                                                   Запасы сырья
                         А              В              С
     1                   18            15              12        360
     2                    6             4               8        192
     3                    5             3               3        180
Цена 1 изде-
                          9              10           16
  лия, д.е.

      Составим математическую модель задачи.
1. Введем управляемые переменные.
      x1 – количество единиц изделия А
      x2 – количество единиц изделия В
      x3 – количество единиц изделия С
2. Составим функцию цели Z=9x1+10x2+16x3 → max
      Введем систему ограничений
     ⎧18 x1 + 15 x2 + 12 x3 ≤ 360
     ⎪6 x + 4 x + 8 x ≤ 192
     ⎪ 1             2 3
     ⎨
     ⎪5 x1 + 3 x2 + 3 x3 ≤ 180
     ⎪⎩ x1, 2, 3, ≥ 0
     Приведём задачу к каноническому виду введением дополнительных
переменных:
     z=9x1+10x2+16x3 → max
     ⎧18 x1 + 15 x2 + 12 x3 + x4 = 360
     ⎪
     ⎨ 6 x1 + 4 x2 + 8 x3 + x5 = 192
     ⎪ 5 x + 3 x + 3 x + x = 180
     ⎩     1      2     3    6

     x j ≥ 0 j = 1,6




                                         10