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

 

    

    F₃=9 → F_max

     - оптимальный план. 

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

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

    При решении задачи отыскания минимума функции цели, когда все элементы в строке F симплексной неотрицательные, изменяется правило выбора разрешающего столбца: столбец выбирается по наибольшему положительному коэффициенту в строке F. Разрешающая строка выбирается так же.

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

    Рассмотрим  случай, когда в столбце свободных  членов есть отрицательные элементы. (bi<0).

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

    При этом необходимо руководствоваться  следующим правилом выбора разрешающего элемента:

    - выбирают любую строку с отрицательным свободным членом;

    - если среди элементов этой  строки нет отрицательных, то  система ограничений несовместна;

    - если среди элементов этой  строки есть отрицательные, то  выбирают любой из них, и  столбец, в котором он стоит,  будет разрешающим;

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

    Пример:

    

                              

    

                            #

     - 1-е базисное решение, не  является допустимым планом, т.к.  W₂=-2<0 

                            #

    

    F₂=2

                                               #

    

    F₃=5

 

    

    F_max=

    4. Двойственные задачи линейного программирования. 

    Каждой  задаче линейного программирования можно определенным образом сопоставить другую задачу линейного программирования, называемую двойственной или сопряженной. Например, задача планирования производства – прямая, а задача оценивания ресурсов – двойственная.

    4.1. Постановка двойственной задачи об оценивании ресурсов.

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

    Составим  математическую модель задачи L₁⁺.

    Пусть y₁ и y₂ – цены ресурсов R₁ и R₂. Стоимость ресурса R₁, идущего на выпуск единицы продукции 1-го вида П₁ – 1y₁, а стоимость ресурса R₂, также идущего на выпуск единицы продукции 1-го вида П₁, - 2y₂, общая стоимость ресурсов на выпуск единицы продукции П₁ 1y₁+2y₂.

    Общая стоимость ресурсов, идущих на выпуск единицы П2:

    5y₁+1y₂.

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

    

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

    15y₁+12y₂→min

    В результате получаем математическую модель двойственной задачи L⁺ об оценивании ресурсов:

    T₁(y)= 15y₁+12y₂→min

    

    4.2. Математическая формулировка задачи L₁⁺.

    Найти такие значения переменных y₁ и y₂, удовлетворяющих системе ограничений S⁺, при которых функция цели Т(у) принимает наименьшее значение.

    4.3. Общая постановка задачи L₁⁺.

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

    (1)

    (2)

    (3)

    Задача, состоящая в нахождении минимального значения функции:

    (4) Т(у)=b₁y₁+b₂y₂+...+b_my_m

    при условиях:

    (5)

    (6)

    называется  двойственной по отношению к задаче (1)-(3).

    Задачи (1)-(3) и (4)-(6) образуют пару задач, которая  называется двойственной парой.

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

1. Целевая функция исходной задачи (1)-(3) задается на максимум, а двойственной – на минимум.
2. Матрица , составленная из коэффициентов при неизвестных в системе ограничений (2) исходной задачи и аналогичная матрица получаются друг из друга транспонированием, т.е. заменой строк столбцами, а столбцов – строками.
3. Число переменных в двойственной задаче (4)-(6) равно числу ограничений в системе (2) исходной задачи (1)-(3), а число ограничений в двойственной задаче (5) – числу переменных в исходной задаче.
4. Коэффициентами в целевой функции Т(у) (4) L⁺являются свободные члены в соотношениях (2) задачи L₁, а правыми частями в системе ограничений (5) двойственной задачи L₁⁺ являются коэффициенты при неизвестных в целевой функции F(x) исходной задачи (1).
5. Если переменная xj в задаче L₁ (1)-(3) может принимать только положительные значения (x_j≥0), то ограничение с таким же номером (j-тое) в системе (5) задачи L₁⁺ (4)-(6) является неравенством вида «≥». Если же переменная x_j может быть как >0, так и <0, то (j-тое) соотношение в системе ограничений (5) задачи L⁺ представляет собой равенство.
6. Аналогично, если i–тое соотношение в системе ограничений (2) исходной задачи L₁ является неравенством, i-тая переменная двойственной задачи y_i≥0, в противном случае переменная может быть как положительной, так и отрицательной.

Пример:

      (1)

      (2)                          L₁

      (3)

      Cоставить двойственную задачу.

      а) Согласно п.3, число переменных в  двойственной задаче L₁⁺ равно трем (у₁, у₂, у₃), согласно п.4 – целевая функция имеет вид:

      

      б) Согласно п.1 необходимо найти минимум  этой функции

      в) Матрица коэффициентов задачи L₁

      а матрица коэффициентов задачи L₁⁺

      г) Согласно п.5, т.к. все переменные исходной задачи L₁ , система ограничений задачи L₁⁺ имеет вид

      

     д) Согласно п.5, т.к. все три ограничения  в системе (2) исходной задачи L₁ – равенства, переменные y_i в задаче L₁⁺ могут быть как больше нуля, так и меньше нуля (т.е. ).

     Итак, математическая модель двойственной задачи L₁+ имеет вид:

              (4)

                               (5)

                   (6) 

5. Связь между решениями прямой и двойственной задач. 

     Каждая  из двойственной пары задач (1)-(6) и (4)-(6) может быть решена самостоятельно. Но при решении симплекс-методом можно получить оптимальное решение обеих задач.

     Зависимость между решениями L₁ и L₁⁺ характеризуется следующими леммами и теоремами. 

     Лемма 1. Если Х – некоторый план задачи L₁ (1)-(3)? а У – произвольный план задачи L₁⁺ (4)-(6), то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане У.

     

     Лемма 2. Если для некоторых планов Х⁰ и У⁰ исходной и двойственной задач, то Х⁰ – оптимальный план задачи L₁⁺, У⁰ – оптимальный план задачи L₁. 

     Теорема (Первая теорема двойственности).