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

    Так как все свободные члены неотрицательны, то таблица                                            Переменные
                                                                                                                                  Свободный
содержит первоначальный опорный план. Его получим, положив                  БП                                                       член
                                                                                  х1     х2       х3        х4      х5      х6
свободные переменные равными нулю: х1 = х2 = х3 = х4 = 0 , при
                                                                            x4    1     1/2      1/4         1     1/4      0         300
этом базисные переменные равны значениям соответствующих                    х6    0     9/2      11/4        0     –1/4     1         700
свободных членов. Имеем:
                                                                            Z1    5      5        2          0        5     0         6000
                   Χ оп
                     1
                        = ( 0 , 0 , 0 , 0 , 1200 , 1000 ) Т .
    2. Выпишем вектор r , компонентами которого являются ко-              Таблица содержит новый опорный план:
эффициенты при свободных переменных целевой функции:
                        r = ( − 15 , − 5 , − 3, − 20 ) .
                                                                                              Χ оп2 = ( 0, 0, 0, 300 , 0 , 700 )Т .
    Все компоненты вектора r отрицательны, следовательно,                 Видим, что все компоненты вектора r=(5, 5, 2, 5) положи-
                                                                      тельные, следовательно, этот опорный план является оптималь-
первоначальный опорный план Χ оп        1
                                           не является оптимальным.
                                                                      ным, при этом Z1 min= – 6000.
    3. Выберем максимальную по модулю отрицательную ком-                  Обратимся к исходной модели. В ней содержится 4 ограни-
поненту вектора r:                                                    чения и целевая функция Z= – Z1. Оптимальным решением ис-
                 max {− 15 , − 5 , − 3 , − 20 } = − 20 .              ходной задачи будет:
     Ей соответствует четвертый столбец таблицы. Анализируем                                   Χ * = (0, 0, 0, 300)Т ,
коэффициенты вектора-столбца коэффициентов при х4. Они по-            при этом                      Z max=6000.
ложительны: а14=4, а24=1. Есть возможность перейти к новому
опорному плану, выведя из свободных переменных х4.                        Пример 6.3. Решить симплекс-методом задачу:
     Выбираем четвертый столбец за разрешающий и переходим                             Ζ = 2 x1 + x 2 − x 3 + х 4 − х 5 → max
к п. 4.
                                                                      при ограничениях:
     4. Для выбора разрешающей строки составляем неотрица-
тельные отношения                                                                             ⎧ x1 + x 2 + x3 = 5,
                       b1   1200      b2     1000
                                                                                              ⎪⎪
                          =      ,         =                                                   ⎨2 x1 + x 2 + x 4 = 9,
                      a14     4       a 24     1                                               ⎪
и выбираем среди них минимальное:                                                              ⎪⎩ x1 + 2 x 2 + x5 = 7,
                          ⎧ 1200 1000 ⎫ 1200 .
                      min ⎨      ,    ⎬=                                                              x j ≥ 0,   j = 1,2, K ,5
                          ⎩ 4      1 ⎭    4
    Разрешающей строкой будет первая, разрешающим элемен-             и дать геометрическую интерпретацию процесса решения.
том – элемент а14 = 4.                                                      Решение. Прежде всего необходимо перейти к минимизации
    5. Выполняя симплексное преобразование с разрешающим              целевой функции. Для этого введем в рассмотрение функцию
элементом а14=4, придем к новой таблице:                                                                  Z1= – Z.
                                                                      Тогда             Ζ 1 = −2 x1 − x2 + x3 − х4 + х5 → min.
                                                                            В системе ограничений уже выделены базисные переменные
                                                                      х3 , х4 и х5. Теперь все исходные данные поместим в таблицу:
                                 69                                                                              70