Решение задач линейного программирования

    Достаточное условие оптимальности: если в задаче на максимум коэффициенты целевой функции отрицательны, то соответствующий базисный план оптимален.

    В задаче на минимум достаточное условие  — неотрицательные коэффициенты целевой функции.

    Если  хотя бы один из коэффициентов целевой  функции в задаче на минимум положителен, на максимум — отрицателен, то целевую функцию можно улучшить, увеличив значения соответствующих базисных переменных.

Для решения  задач симплекс-методом необходимо:

1. привести задачу к канонической форме.
2. преобразовать задачу линейного программирования к симплексной форме, т.е. разделить переменные задачи на две группы: базисные и небазисные. Разрешить систему относительно базисных переменных и исключить базисные переменные из целевой функции.
3. Вспомнить одну или более итераций симплекс-метода, которые включают:
1. проверку достаточных условий оптимальности и выбор ведущей переменной
2. вычисление максимально допустимого шага вдоль ведущей переменной и выбор разрешающего уравнения
3. преобразование симплексной формы, связанное с заменой в базисе — переменная, соответствующая разрешающему уравнению, покидает базис, на ее место вводится ведущая переменная.

    Рассмотрим  задачу линейного программирования в канонической форме:

            (3.1)

    Симплексной формой задачи (3.1) называется такое ее представление, при котором система основных ограничений разрешены относительно m переменных, которые называются базисными.

    i₁, i₂, …, i_m — индексы базисных переменных.

    Тогда система основных ограничений разрешенная  относительно базисных переменных будет иметь вид:

          (3.2)

    J_б = {i₁, i₂, …, i_m} — базисные переменные

    J_н = {j₁, j₂, …, j_m} — небазисные переменные

    J_б È J_н = J = {1, 2, …, n}

    Используя уравнение системы (3.2) мы можем исключить базисные переменные из целевой функции: 

    

            (3.3)

    x_j ³ 0, j = J (3.4) — известные ограничения.

    Задачу  линейного программирования с целевой  функцией (3.3) и ограничениями (3.2) и (3.4) будем называть задачей линейного программирования в симплексной форме, если все свободные члены b_i ³ 0, .

    

            (3.5)

    Такой задаче ставим в соответствие базисный план, который состоит из:

    

    Введем  дополнительное обозначение:

     

     Задачу  (5) можно переписать в следующем виде:

             (3.6)

1. Симплекс-метод  в табличной форме.

Предположим, что  задача линейного программирования в канонической форме приведена  к симплексной форме (3.6). Перенесем коэффициенты целевой функции вектора свободных членов и матрицы R, L, в специальную симплексную таблицу:

1 этап: проверяем достаточное условие оптимальности (таблица) базисного плана.

Если в задаче на максимум коэффициенты целевой функции  удовлетворяет условию:

в задаче на минимум:

, то базисный план, соответствующий симплексной таблице является оптимальным и решение ЗПП окончено.

Допустим, что  достаточное условие оптимальности  не выполняется. В этом случае найдем максимальный по модулю, не удовлетворяющий  условию оптимальности, коэффициент целевой функции. Соответствующую переменную назовем ведущей. Этот индекс обозначен через j_*. Соответствующий столбец симплексной таблицы назовем ведущим.

2 этап: вычисление оптимально допустимого шага.

Из системы  основных ограничений симплексной формы следует:

Из  вытекает, что

      (3.7)

Очевидно, что  соотношение (7) может нарушаться только в том случае, если , поэтому для каждой базисной переменной :

, то соответствующая базисная  переменная ни при каком значении  не обращается в ноль.

Максимально допустимый шаг определим как минимум  из чисел  .

возможны 2 случая:

     Это означает, что шаг  может быть бесконечно большим. Соответственно значение целевой функции может неограниченно возрастать, если задача на максимум, или неограниченно убывать, если задача на минимум. С экономической точки зрения такая ситуация свидетельствует о несоответствии математической модели реальной экономической модели (неучтены или неправильно учтены ограничения задачи). Решение ЗПП при этом считается законченным.

2. (конечное число)

     

       называется ведущей или разрешающей переменной.

     3 этап: преобразование симплексной таблицы.

     Как уже отмечалось в пункте 1, должна выводиться из базиса, на ее место вводится переменная — небазисная.

     Нарисуем  новую симплексную таблицу. 

           (3.8)

             (3.9)

            (3.10)

             (3.11)

     Правила:

    На  место ведущего элемента в новой  таблице записывается элемент, обратный ведущему.

,

    Правило: новые элементы ведущей строки вычисляются по старым элементам делением последних на ведущий элемент, взятый с противоположным знаком.

i — номер произвольной строки.

Элементы ведущего столбца получаются из старых элементов  делением последних на ведущий элемент.

4)

,

,

    Новый элемент симплексной таблицы, не находящийся в ведущей строке или столбце, получается из старого, если вычесть из последнего произведение его проекций деленное на ведущий элемент.  

         Двухфазный  симплекс-метод. 

    Если  после приведения математической модели к канонической форме не все ограничения  находятся в предпочтительном виде, то для решения задачи требуется  применить двухфазный симплекс-метод.

    Целевая функция вспомогательной задачи представляет собой сумму фиктивных  переменных, которую необходимо минимизировать.

    Начальный базис вспомогательной задачи составляют переменные:

1. в  ограничениях, которые находятся  в предпочтительном виде, -те переменные, которые обеспечили предпочтительность этих ограничений.