Математическое программирование

     

     Сначала полагаем h=0, т.е. строим нулевой уровень функции цели.

      - прямая линия

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

     Координаты  этой точки и есть решение задачи, т.е. ее оптимальный план.

     При этом возможны следующие 4 случая:

       
 
 
 

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

     Итак, графический метод решения задач линейного программирования состоит из следующих этапов:

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

Пример 1.:

                     

Пример 2.

                     

3.2. Симплексный метод решения задач линейного программирования. 

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

      Пусть требуется найти максимальное значение функции

Запишем эту  задачу в канонической форме:

Таким образом, мы перешли к рассмотрению задачи линейного программирования в пространстве R_n+m.

Такая система m уравнений с (n+m) неизвестными имеет бесконечное множество решений. Пусть переменные W₁,...,W_m – базисные.

Полагая свободные переменные равными нулю, получим первое базисное решение. Чтобы перейти к другому базисному решению, надо поменять ролями одну свободную и одну базисную переменные. Опорный план ЗЛП является одним из базисных решений системы уравнений-ограничений.

Первый допустимый (опорный) план задачи:

      

      Переход от одного базисного решения к  другому реализуется с помощью  метода модифицированных жордановых исключений (МЖИ), что удобнее делать в виде симплексных таблиц. 

 

      Решение осуществляется по следующей схеме:

1. В строке F выбирают самый большой по модулю отрицательный элемент. Столбец, в котором он стоит, будет разрешающим.
2. Для элементов разрешающего столбца находят симплексное отношение (не отрицательное отношение элементов столбца свободных членов b к элементам разрешающего столбца).
3. Разрешающая строка будет соответствовать наименьшему симплексному отношению.
4. На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент. (В данном случае это                  , ему соответствуют базисная переменная W₁ и свободная переменная x₂.)
5. Составляем новую симплекс-таблицу, меняя местами x₂ и W_1.
6. Разрешающий элемент в новой таблице заменяем на обратную величину a₁₂→1/a_12.
7. Элементы разрешающей строки делятся на разрешающий элемент.
8. Элементы разрешающего столбца делим на разрешающий элемент с противоположным знаком.
9. Остальные элементы таблицы пересчитываем по правилу прямоугольника. 
    
   

 

10. Процедура повторяется до тех пор, пока все  элементы строки F станут неотрицательными.

 

    Оптимальный план задачи – это базисное решение, при котором все элементы строки F положительны, а оптимальное значение функции цели записано в клетке таблицы на пересечении строки F и столбца b.

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

    Пример: 

    Для производства 2-х видов продукции  П1 иП2 предприятие расходует два вида ресурсов Р₁ и Р₂. Расход каждого вида ресурса на единицу продукции каждого вида, запасы ресурсов и прибыль от реализации единицы продукции каждого вида приведена в таблице 

 

    Математическая  модель задачи:

    L₁:

    S₁:

    Математическая формулировка ЗЛП: найти такие значения переменных х₁ и х₂, удовлетворяющих системе ограничений S₁, которые максимизируют функцию цели F.

    1. Приведем задачу к каноническому  виду, введя дополнительные неотрицательные  переменные w₁ и w₂.

      

      

    2. Разрешим систему ограничений  задачи относительно w₁ и w_2:

    

     , где w₁, w₂ – базисные переменные; х₁, х₂ – свободные. 

    Запишем задачу в виде симплекс-таблицы:

    Т.1.

                                                #

     - опорный план

    F=0

    w₁, w₂ – остатки ресурсов 

    Т.2.

                             #

    

    F₂=9/2 

    Т.3.