Таблица является оптимальной и последней, если все элементы строки (-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₁ - это стоимость всего ресурса первого вида, идущего на производство единицы продукции первого вида.

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

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

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

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