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

    Тогда исходная таблица примет вид:                              X F . Для этого умножим первую строку последней таблицы на
                     B        F           b                         сB и вычтем из второй строки, чтобы коэффициенты в строке Z
                     cB       cF          0                         при базисных неизвестных были равны 0. Получим таблицу:
    Первая строка таблицы соответствует уравнению:
                                                                               E             B −1 F            B −1b
                        B⋅ XB + F ⋅ XF = b.
    Напомним, что на первом шаге симплекс-метода необходимо                      0          с F − с B B −1 F              − сB B −1b
найти первоначальный опорный план (неотрицательное базисное             Обозначим через r = сF − сB B −1F вектор, состоящий из ко-
решение системы), для этого умножим обе части уравнения на
                                                                    эффициентов при свободных неизвестных целевой функции. Со-
матрицу B −1 слева (она существует, так как по предположению        гласно рассуждениям, проведенным в п. 6.1, опорное решение
B − невырожденная матрица). Получим
                        −1              −1         −1
                                                                     X = ( B −1b, 0) T будет оптимальным, если r ≥ 0. Последняя строка
                   B ⋅ B ⋅ X B + B ⋅ F ⋅ X F = B ⋅b .               таблицы соответствует значению функции:
      Полагая X F = 0 , найдем значения базисных переменных:                                       (                  )
                                                                                        Z = 0 ⋅ X B + с F − с B B −1 F X F + с B B −1b .
                              X B = B −1 ⋅ b                           В найденном опорном плане (при X F = 0 ) значение
     −1
(B        ⋅ B = E − единичная матрица m-го порядка).                                         Z ( X ) = сB B −1b .
      Если при этом B −1 ⋅ b ≥ 0 , то                                  Видим, что соответствующее значение находится в правом
                                    (        )
                              X = B −1 ⋅ b,0 T                      нижнем углу таблицы с противоположным знаком.
является первоначальным опорным планом.                                              6.2.1. Алгоритм симплекс-метода
    Эти преобразования системы ограничений соответствуют
                                                                        1. Запишем условия задачи:
таблице:                                                                                                 n
                       E         B −1 ⋅ F      B −1 ⋅ b                                        Z = ∑ c j x j → min,
                                                                                                     j =1
                       cB        cF            0
    Вычислим значение целевой функции, соответствующее                                      ⎧a11 + K + a1n xn = b1 ,
опорному         плану,      подставив       X       в  выражение                           ⎪
                                                                                            ⎨K K K             K
Z = c B X B + c F X F (вторая строка таблицы). Получим                                      ⎪a + K + a x = b ,
                                                                                            ⎩ m1         mn n      m
                       Z ( X ) = c B ⋅ B −1 ⋅ b .
                                                                                                  x j ≥ 0,     j = 1, n
    Рассматривая идею симплекс-метода, мы пришли к выводу,
что опорный план является оптимальным, если в целевой функ-         в виде таблицы:
ции, выраженной только через свободные переменные, все                   БП           х1           ...                 хn      Свободный член
коэффициенты неотрицательны.                                                         a11           ...                a1n            b1
                                                                                      ...          ...                 ...            ...
    Чтобы проверить полученный опорный план на оптималь-
                                                                                     am1           ...                amn            bm
ность, выразим целевую функцию через свободные переменные
                                                                          Z           c1           ...                 cn             0         ,
                                        59                                                                   60