Двойственный симплекс-метод

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

Двойственная задача к задаче планирования торговли

Каждой задаче линейного программирования можно сопоставить другую задачу, называемую двойственной или сопряженной по отношению к исходной или прямой. Составим двойственную задачу к задаче планирования товарооборота (2.1) – (2.3), которую будем называтьпрямой.Обозначимyi () – двойственная оценка (неявная стоимость) единицы i-го ресурса. Тогда двойственная задача к задаче планирования торговли формулируется следующим образом:Требуется определить оценку единицы каждого вида ресурса, чтобы при заданных объемах ресурса bi, нормах их расхода aij и показателях прибыли cj, общая стоимость ресурсов, затраченных на организацию торгового процесса, была бы минимальной.

Запишем математическую модель двойственной задачи к задаче линейного программирования (2.1) – (2.3).

Определить , который удовлетворяет условиям

, (3.1)

yi ≥ 0, (3.2)

и доставляет минимальное значение целевой функции

(3.3)

Ограничения (3.1) показывают, что оценка (стоимость) всех ресурсов, затраченных на продажу единицы j группы товаров, должна быть не меньше прибыли, получаемой от продажи единицы j группы товаров, а общая стоимость всех ресурсов (3.3) должна быть минимальной.Задачи (2.1) – (2.3) и (3.1) – (3.3) представляют симметричную пару двойственных задач, так как системы ограничений заданы неравенствами и на переменные xj и yi накладывается условие неотрицательности.

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

1. Число переменных в двойственной задаче равно числу ограничений в прямой задаче.

2. Матрица коэффициентов системы ограничений двойственной задачи получается из матрицы коэффициентов системы ограничений прямой путем транспонирования.

3. Если система ограничений прямой задачи задана неравенствами смысла «≤», то система ограничений двойственной задачи записывается неравенствами смысла «≥».

4. Свободными членами системы ограничений двойственной задачи являются коэффициенты функции цели прямой задачи.

5. Если целевая функция прямой задачи задается на максимум, то целевая функция двойственной задачи – на минимум.

6. Коэффициентами функции цели двойственной задачи являются свободные члены системы ограничений прямой задачи.

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

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

 

14. Определение значимости ресурсов

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

В данном случае Yопт = (0, 1/4, 5/8, 0, 0). Таким образом, из двух
“дефицитных” ресурсов оборудование второго типа имеет большую значимость и увеличении интервала работы на этом оборудовании более выгодно с точки зрения влияния на значение целевой функции.

15. Первая (основная) теорема двойственности. Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны: . (6.11) Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы.

Из первой части утверждения теоремы следует, что равенство (6.10) является не только достаточным признаком оптимальности решений, но и необходимым признаком оптимальности решений взаимно двойственных задач.

Экономический смысл первой (основной) теоремы двойственности. План производства и набор цен (оценок) ресурсов оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при "внешних" (известных заранее) ценах с ₁, с ₂, ..., с_n равна затратам на ресурсы по "внутренним" (определяемым только из решения задачи) ценам у ₁, у ₂ ,..., у_т. Для всех же других планов X и Y обеих задач в соответствии с основным неравенством теории двойственности прибыль (выручка) от продукции всегда меньше (или равна) затрат на ресурсы.