Введение

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

Глава 1. Постановка задачи

Кондитерская фабрика «Конти - Рус» выпускает два вида продукции. При этом используется три вида ресурсов. Известны нормы расхода ресурсов на единицу продукции, фонды ресурсов и прибыль от реализации единицы каждой продукции.  Данные представлены в виде таблицы (таб.1.1). Нужно определить оптимальный план выпуска продукции. 

 

    Нужно определить, сколько выпустить печенья и вафель, чтобы получить максимально возможную прибыль. Следовательно, критерием будет прибыль.

х₁  -  количество выпускаемого печенья,

х₂  -  количество выпускаемых вафель.

    Математическая модель будет иметь вид:

                L = 4x₁ + 3x₂  ®  max

                        7x₁ + 2x₂ ≤ 91

                        3x₁ + 5x₂ ≤ 68

                        1x₁ + 6x₂ ≤ 66

                           x_1,2 ≥ 0

    В условиях знак “≤”, так как использовать ресурса больше, чем есть в запасе, мы не можем. Переменные не могут быть отрицательными, так как количество выпускаемой продукции должно быть больше нуля или равно нулю (если эта продукция не выпускается). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

        Глава  2.   Нахождение  оптимального  плана  выпуска  продукции

1. Графическое  решение  задачи  линейного  программирования  (геометрическая  интерпретация  процесса  решения  задачи  симплексным  методом).

Рассмотрим решение задачи графическим методом.

Модель задачи имеет вид:              

                 L = 4x₁ + 3x₂  ®  max

                        7x₁ + 2x₂ ≤ 91

                        3x₁ + 5x₂ ≤ 68

                        1x₁ + 6x₂ ≤ 66

                           x_1,2 ≥ 0

Строим систему координат х₁0х₂. В этой системе будем строить допустимое множество задачи.

    Ограничения x_1,2 ≥ 0 образуют угол х₁0х₂, за приделы которого допустимое множество выходить не может. 

Рис.2.1

      Х₂

  
 

                                                                                               С               

                                                                                                          (3)

                                                                                       (2)

                                                                                           L^*

                                                          

                                                                                                   х₁

                                                                                               (1)

                     L                         

                                                                                

             

Определим полуплоскости каждого условия.

     Берем первое условие:

                                               7x₁ +2 x₂ ≤ 91.

  Заменяем на равенство:   

  7 x₁ + 2x₂ = 91.

    Чтобы построить эту прямую, подбором выбираем две точки:

                                х₁ = 13                       х₁ = 11

                                х₂ = 0                         х₂ = 7

    Эта прямая делит все множество на два подмножества. Чтобы определить, с какой стороны от прямой находится допустимое множество, воспользуемся контрольной точкой (проще всего взять точку начала координат). Если при подстановке координат этой точки в условие задачи, последнее выполняется как истинное, то допустимое множество со стороны этой точки, а, если как ложное, то с другой стороны от прямой. При подстановке координат точки (0,0) в условие, последнее выполняется как истинное, следовательно, допустимое множество находится со стороны этой точки от прямой.

    Аналогично строим две другие прямые:

         3x₁ + 5x₂ ≤ 68                                                        x₁ + 6x₂ ≤ 66

         3x₁ + 5x₂ = 68                                                        x₁ + 6x₂ = 66

х₁ = 6                     х₁ = 11                                  х₁ = 0                    х₁ = 6

х₂ = 10                   х₂ = 7                                     х₂ = 11                  х₂ = 10

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

      Выделим допустимое множество как пересечение всех этих подмножеств. Допустимым множеством будет выпуклый многогранник. Любая точка этого многогранника удовлетворяет всем условиям задачи и может быть ее решением (рис.2.1).Но нам нужно найти оптимальное решение.Для этого нужно построить линию критерия.        

   Чтобы построить прямую критерия, сначала строят вектор С, начало которого лежит в точке (0;0), а конец в точке с координатами, соответствующими коэффициентам в критерии, то есть (4;3).

    Перпендикулярно этому вектору в точке (0;0) проводим прямую, которая и будет прямой критерия (на графике линия L).

    В сторону вектора С критерий всегда увеличивается.

    Так как критерий в задаче стремиться к максимуму, передвигаем его прямую в сторону увеличения, то есть по вектору С до самой последней точки допустимого множества (на графике прямая  L^*).

    Координаты точки, через которую проходит прямая L^* и будут оптимальными значениями х₁^* и х₂^*:

                                    х₁^* = 11       х₂^* = 7

    Чтобы определить оптимальное значение критерия, подставим эти значения в формулу критерия:

                                  L^* = 4 · 11+3 · 7= 65 

    Определим смысл этих значений для данной задачи об использовании ресурсов: для получения максимальной прибыли в размере 65 денежных единиц необходимо выпустить 11 единиц печенья и 7 единиц вафель.

                                                                              

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

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

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

   Решим симплекс-методом задачу об использовании ресурсов:

                 L = 4x₁ + 3x₂  ®  max

                        7x₁ + 2x₂ ≤ 91

                        3x₁ + 5x₂ ≤ 68

                        1x₁ + 6x₂ ≤ 66

                           x_1,2 ≥ 0

             

    Приведем задачу к каноническому виду:

               L = 4x₁ + 3x₂ +0x₃ + 0x₄ + 0x₅ ®  max

                                  7 x₁ + 2x₂ + x₃ = 91

                                   3x₁ + 5x₂+ x₄= 68

                                  1x₁ + 6x₂+ x₅ = 66

                                       x_i ≥ 0,   I = 1, 5

    Переменные x₃, x₄, x₅ - базисные.

                                                                                             Таблица 2.1.

 

Таблица является оптимальной и последней, если все элементы строки (-L) не положительны.

    Так как в нашей таблице в строке (-L) есть положительные элементы, то необходимо продолжить решение и выполнить пересчет таблицы

Чертим новую таблицу. 
 
 
 
 

                                                                                                                Таблица 2.2

 
 

Вторая таблица тоже не оптимальная. Снова проводим пересчет таблицы. В  результате получим третью симплекс-таблицу. 

                                                                                                                                                Таблица 2.3

 

В строке (-L) все элементы неположительные, следовательно, данная таблица оптимальная и последняя.

    В столбце «Базис» находятся базисные переменные, в столбце «Свободные  члены» их значения. Если переменной нет в базисе, то она равна нулю. В строке (-L) в столбце «Свободные члены» находится значение критерия с коэффициентом минус единица.

    Следовательно,  х₁^* = 11, x₂^* = 7, L^* = 65. Для проверки подставим значения x₁^* и x₂^* в  формулу критерия:

                                   L^* = 4 · 11 + 3 · 7 = 65.

    Получили тот же ответ, что и при решении задачи графическим методом: для получения максимальной прибыли в размере 65 денежные единицы необходимо выпустить 11 единиц печенья и 7 единиц вафель.

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

 Глава  3.   Построение  и  решение  двойственной  задачи

   Двойственные пары задач подразделяются на симметричные и несимметричные. Симметрия имеет место, если все условия имеют вид неравенств и все переменные ограничены по знаку.

3.1. Правила  построения  двойственных  задач

Для  симметричных  двойственных  задач

1. Если целевая функция прямой задачи стремиться к максимуму, то в двойственной она будет стремиться к минимуму и наоборот.
2. Число переменных в двойственной задаче равно числу условий в прямой задаче.  Число условий в двойственной задаче равно числу переменных в прямой.
3. Матрица условий А (коэффициенты а_ij) в двойственной задаче получается транспонированием матрицы условий прямой задачи.
4. Коэффициенты критерия двойственной задачи образуются свободными членами условий прямой задачи.
5. Свободные члены условий двойственной задачи образуются коэффициентами критерия прямой задачи.
6. Знаки неравенств в условиях меняются на обратные (если  все  условия  имеют  один  знак;  причем,  если  критерий  стремиться  к  максимуму,  то  условия  должны  иметь  вид  меньше  или  равно  и  наоборот). Двойственные переменные неотрицательны.

Для данной задачи  построить двойственную:

                                    L = 4x₁ + 3x₂  ®  max                                

                                   y₁     7x₁ + 2x₂ ≤ 91

                                   y₂     3x₁ + 5x₂ ≤ 68

                                   y₃    x₁ + 6x₂  ≤ 66

                                              x_1,2 ≥ 0

Оптимальное решение этой задачи уже известно, оно было найдено ранее двумя методами - графическим и симплексным:

                     x₁^* = 11, x₂^* = 7, L^* = 65. 

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

   Каждому условию прямой задачи ставим в соответствие двойственную переменную и, пользуясь правилами, построим двойственную задачу:

                     L = 91y₁ + 68y₂ + 66y₃ ® min

                             7y₁ + 3y₂ + y₃ і 4

                             2y₁ + 5y₂ + 6y₃ і 3

                                  y_i і 0,  i = 1, 3

    Для нахождения оптимальных значений двойственных переменных воспользуемся теоремами двойственности 4 и 5.

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

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

Подставим оптимальные значения x₁^*=11 и x₂^*=7 в условия прямой задачи.

Первое условие:     7x₁ + 2x₂ ≤ 91    

                                 7 · 11 + 2 · 7 = 91

                    91 = 91

   Условие выполняется как равенство, следовательно, по теореме 5, соответствующая двойственная переменная положительная.

То есть y₁^* > 0.

Второе условие:    3x₁ + 5x₂ ≤ 68

                            3 · 11 + 5 · 7 = 68

                                                 68 = 68   

Условие выполняется как равенство, следовательно, y₂^* > 0. 

Третье условие:       x₁ + 6x₂ ≤ 66

                                 11 + 6 · 7 Ј 53

                                              53 < 66

  Условие выполняется как строгое неравенство, следовательно, по теореме 4, соответствующая двойственная переменная равна нулю. То есть y₃^*=0. 

    Учитывая, что y₃^*=0, перепишем систему условий:

                                     7y₁^* + 3y₂^* і 4

                                     2y₁^* + 5y₂^* і 3

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

                                     7y₁^* + 3y₂^* = 4

                                     2y₁^* + 5y₂^* = 3

    В результате вычислений получим следующие оптимальные значения двойственных переменных:

                                         y₁^* = 11/29

                                         y₂^* = 13/29

                                         y₃^* = 0

    Вычислим оптимальное значение критерия:

                                       L^* = 91 · 11/29 + 68 · 13/29 + 66 · 0 = 65

    Оптимальные значения критериев прямой и двойственной задач совпали, что и подтверждает вторую теорему двойственности.

    Значения двойственных переменных можно найти также в последней симплекс-таблице в строке (-L) в столбцах начального базиса (x₃,  x₄,  x₅) с коэффициентом минус единица (таб. 2.3). 

3.2 Экономический смысл двойственной задачи

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

   Двойственная же задача описывает ту ситуацию, при которой предприятие вместо выпуска продукции  продает ресурсы.

       Экономический смысл двойственной переменной - стоимость единицы ресурса.

       Рассмотрим условие двойственной задачи:

                                  a₁₁y₁ + a₂₁y₂ + a₃₁y₃ і C₁

    a₁₁ - это количество ресурса первого вида, необходимое для производства продукции первого вида.

   y₁ - это стоимость единицы ресурса первого вида.

   Следовательно, a₁₁y₁ - это стоимость всего ресурса первого вида, идущего на производство единицы продукции первого вида.

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

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

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

    Интересы покупателя отражает критерий: