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

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

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

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

Обозначим через и_i теневую цену единицы ресурса S_i. Величины и_i должны быть такими, чтобы теневая цена ресурсов, используемых в любом технологическом про­цессе, не была меньше получаемого дохода, т.е. чтобы расходы не превысили доходов. Запишем это условие в виде:

, где а_ij – число единиц i-го ресурса, используемых в j-м продукте.

Если ввести переменные и_т+j ³0, представляющие со­бой превышение теневой цены единицы j-й продукции над доходами от ее реализации, то система неравенств превращается в систему уравнений

Оптимальными теневыми ценами будем считать такие, которые минимизируют общую теневую стоимость ресурсов, т. е. величину

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

Нетрудно заметить, что прямая и двойственная зада­ча оказываются тесно связанными между собой. Эта связь проявляется в следующем:

- если прямая задача является задачей максимизации целевой функции, то двойственная задача является зада­чей минимизации;

- коэффициенты целевой функции в прямой задаче являются свободными членами в ограничениях двойст­венной задачи;

- свободные члены из ограничений прямой задачи ста­новятся коэффициентами целевой функции в двойствен­ной задаче;

- коэффициенты при переменных в ограничениях двой­ственной задачи представляют собой столбцы таблицы коэффициентов прямой задачи;

- знаки неравенств в ограничениях меняются на проти­воположные.

Существует тесная связь между решениями прямой и двойственной задач линейного программирования. Для установления этой связи запишем уравнения прямой и двойственной задач в иной форме.

Примем в прямой задаче переменные сво­бодными и сформулируем ее в следующем виде:

Максимизировать

при условиях

, где x_l+i - недоиспользуемый i-й ресурс.

Этой задаче соответствует матрица вида

В двойственной задаче примем за свободные перемен­ные u₁, ..., и_т и сформулируем ее в следующем виде:

Минимизировать

при условиях

, где U_m+j – превышение теневой цены единиц j-й продукции над доходами.

Этой задаче соответствует матрица вида

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

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

Пример. Задача на распределение ресурсов задана табл.5. В добавочных графах этой таблицы приведено решение прямой и двойственной задач линейного программирования, т. е. указан опти­мальный план распределения ресурсов, остатки ресурсов при опти­мальном плане и теневые цены. Из таблицы видно, что ресурсы вида S₁, имеющиеся в избытке, имеют нулевую цену. Наивысшую цену имеют ресурсы S₂, которые требуются для всех технологиче­ских процессов и запасы которых невелики.

Таблица 5

Следовательно, предприятию для повышения доходов необходимо дополнительно приобретать ресурсы S₂ , S₃, S_{4 .}