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

эффициентов системы ограничений, соответст-                               Сырье
                                                                                                Нормы расхода                      Объем
вующего компонентам r j < 0 исследуемого опорного                                          I      II     III           IV         ресурсов
                                                                            1              4      2       1             4           1200
плана в симплекс-таблице.                                                   2              1      5       3             1           1000
                 6.3. Понятие о вырождении                                Доход           15      5       3            20

      Опорное решение, в котором хотя бы одна из базисных пе-         Составить план производства, обеспечивающий фирме наи-
ременных принимает нулевое значение, называется вырожден-         больший суммарный доход.
ным, и соответствующая ЗЛП называется вырожденной.
      Пусть, например, в вырожденном плане базисная переменная        Решение. Обозначим через Χ = ( х1 , х2 , х3 , х4 )Т план выпус-
 хi 0 = 0 . Если на очередном шаге строка i0 окажется разрешаю-   ка продукции. Математическая модель задачи примет вид:
щей, то и новое опорное решение также будет вырожденным                           Ζ = 15 х1 + 5 х 2 + 3 х3 + 20 х 4 → max,
(вводимая в базис в новом опорном плане переменная также бу-                              ⎧ 4 x1 + 2 x 2 + x 3 + 4 x 4 ≤ 1200 ,
дет равна нулю). Нетрудно видеть, что при этом значения всех                              ⎨
                                                                                          ⎩ x1 + 5 x 2 + 3 x 3 + x 4 ≤ 1000 ,
остальных переменных остаются прежними, и значение целевой
функции также не изменится. (Показать самим!)                                             x j ≥ 0 ( j = 1,4 ) .
      Отсюда можно сделать вывод, что данная итерация не при-         Преобразуем ее к каноническому виду. Введем две дополни-
вела ни к каким изменениям и, следовательно, является лишней.     тельные (балансовые) неотрицательные переменные х5 и х6 и пе-
Однако это не так. Изменяется состав базисных и свободных пе-     рейдем к функции Z1= – Z. Модель примет вид:
ременных. Вообще говоря, после конечного числа шагов можно                 Ζ 1 = − 15 х1 − 5 х 2 − 3 х3 − 20 х 4 − 0 ⋅ х 5 − 0 ⋅ х 6 → min ,
вернуться к ранее встречавшемуся набору свободных и базисных
                                                                                      ⎧ 4 x1 + 2 x2 + x3 + 4 x4 + x5 = 1200 ,
переменных при неизменности значения целевой функции. Появ-                           ⎨
ляется так называемое зацикливание в схеме расчетов. Зацикли-                         ⎩ x1 + 5 x2 + 3 x3 + x4 + x6 = 1000 ,
вание недопустимо особенно при автоматизации процесса вы-                                        x j ≥ 0 ( j = 1,6) .
числений, так как требует вмешательства человека для изменения
вычислительного алгоритма.                                            Поиск решения ЗЛП состоит из следующих этапов: нахож-
      Поэтому существуют специальные методы избавления от за-     дение первоначального опорного плана, проверка полученного
цикливания. Хотя вырожденные ЗЛП встречаются относительно         опорного плана на оптимальность и переход от одного опорного
часто, к зацикливанию они приводят лишь в исключительных          плана к другому, если найденный опорный план не является оп-
случаях.                                                          тимальным.
                                                                      1. Запишем условия задачи в виде симплексной таблицы:
         Примеры решения задач симплекс-методом                                                Переменные                            Свободный
                                                                     БП     х1       х2        х3        х4       х5        х6          член
    Пример 6.2. Фирма выпускает изделия четырех типов. При
этом используется сырье двух видов, запасы которого соответст-       х5     4        2         1         4        1         0          1200
венно 1200 и 1000 единиц. Нормы расхода сырья на изготовление        х6     1        5         3         1        0         1          1000
каждого типа продукции, а также доход, полученный от выпуска         Z1    –15       –5        –3       –20       0         0           0
единицы каждого типа продукции, заданы таблицей:
                               67                                                                           68