В. 20 Двойственность ЛП

Рассмотрим задачу об оптимальном распределении ресурсов.

Предположим, что у нас сейчас: 2 вида продукта (n=2), 2 вида ресурса (m=2); c₁, c₂ – цены товаров; b₁, b₂ - объём ресурсов; x₁, x₂ – количество товаров; a_ij – норма расхода i-го вида ресурса, необходимого для получения j-го вида продукции.

P: с₁x₁+с₂x₂→max

x₁, x₂≥0

Предположим, что предприятие может продавать эти ресурсы. Продавать нужно по таким ценам, чтобы с одной стороны, это было не слишком дорого, с другой - прибыль должна быть не<, чем, если бы мы эти ресурсы переработали. Цены ресурсов (u₁ и u₂) по которым будем продавать.

D: b₁u₁+b₂u₂→min – деньги, которые получим от продажи.

a₁₁u₁+a₂₁u₂≥c₁ – по чём мы продадим единицу товара х₁.

a₁₂u₁+a₂₂u₂≥c₂

u₁, u₂≥0

Задача D называется двойственной к задаче P. Переменные u_i называются двойственными оценками (или теневыми ценами, или справедливыми).

Если больше 2-х переменных.

P:

, i=1…m

x_j ≥0, j=1…n

D:

, j=1…n

u_i ≥0, i=1…m.