Линейная оптимизация. Обобщённый алгоритм решения задачи линейной оптимизации (линейного программирования), страница 2

      Совокупность неотрицательных значений переменных x₁, x₂, …, x_n, удовлетворяющих ограничениям (2), называются допустимым решением ОЗЛП, а совокупность всех допустимых решений представляет собой подмножество допустимых решений ОЗЛП. Допустимое решение ОЗЛП в виде совокупности значений переменных, обеспечивающих минимальное значение целевой функции L(), называется оптимальным решением ОЗЛП. 

        Ввиду того, что m < n, все множество переменных x₁, x₂, …, x_n можно представить в виде двух подмножеств: базисных и свободных переменных. При этом число базисных переменных равно m, а число свободных соответственно – k = n – m.     В качестве свободных обычно принимают переменные x₁, x₂,…, x_k, а в качестве базисных – x_k+1, x_k+2, …, x_k+l, …, x_k+m.

        Вторым шагом для решения ЗЛП с помощью симплекс-метода является её представление в стандартной форме.       

       Для этого, во-первых, в системе уравнений-ограничений (1) базисные переменные выражаются через свободные. В результате получается система уравнений вида

;

    ;

............................................................................

                                 ;                         (3)

  ………………………………………………             ,

где коэффициенты  являются комбинациями коэффициентов a_ij  и  b_i.

Целевая функция вида (2) также выражается через свободные переменные  и  в результате принимает вид

                                       ,                                    (4)

где коэффициенты   являются комбинациями коэффициентов c_j.

Затем система уравнений (3) и выражение для целевой функции (4) преобразуются к виду

;

…………………………………………………

                             ;                              (5)

…………………………………………………

,

                                   ,                                         (6)                                                                  

где     ; .

         Третьим шагом является построение исходной симплекс-таблицы на  основании соотношений (5) и (6).    Данная таблица имеет вид (табл. 1)

                                      Таблица 1

       Четвёртым  шагом  является  проверка  допустимости решения ЗЛП на основе заполненной симплекс-таблицы. В качестве признака допустимости решения ЗЛП выступает требование неотрицательности всех элементов второго столбца (коэффициентов ) симплекс-таблицы (коэффициент  в расчёт не принимается).  

Если данное требование не выполняется (т.е. среди коэффициентов  имеется хотя бы один отрицательный), то осуществляется замена базисных переменных на свободные в соответствии с алгоритмом, описанным в приложении 2 лабораторной работы №5. При этом если в ходе поиска допустимого решения возникнет ситуация, когда в симплекс-таблице один или несколько элементов второго столбца отрицательны, и хотя бы в одной строке, соответствующей одному из этих элементов, остальные элементы положительны, то это свидетельствует об отсутствии у ЗЛП допустимого решения.

После того какполучено допустимое решение ЗЛП, пятым шагом является проверка данного допустимого решения на оптимальность.  Признаком оптимальности решения ЗЛП является требование отрицательности всех элементов второй строки (коэффициентов r_j) симплекс-таблицы (коэффициент  в расчёт не принимается). Если данное требование не выполняется (т.е. среди коэффициентов r_j имеется хотя бы один положительный), то осуществляется замена базисных переменных на свободные в соответствии с алгоритмом, описанным в приложении 1 лабораторной работы №5, до тех пор,  пока не будет получено единственное оптимальное решение. При этом искомыми оптимальными значениями переменных будут значения базисных переменных второго столбца конечной симплекс-таблицы, а минимальным значением целевой функции – значение .

         При этом если в ходе поиска оптимального решения возникнет ситуация, когда во второй строке  симплекс-таблицы один или несколько элементов равны нулю (коэффициенты r_j), а все остальные отрицательны, то это свидетельствует о том, что данная ЗЛП имеет бесчисленное множество оптимальных решений.  Если же в ходе поиска оптимального решения окажется, что во второй строке  симплекс-таблицы один или несколько элементов положительны, а в столбце, соответствующем положительному элементу, остальные элементы (коэффициенты ) отрицательны,  то это свидетельствует о том, что данная ЗЛП не имеет оптимального решения.