Экономическая интерпретация двойственной задачи и теории двойственности

Переменные у 1, у2, у3 будут обозначать условную предполагаемую цену за ресурс 1, 2, 3 вида соответственно. Тогда доход от продажи видов сырья, расходуемых на производство одной единицы продукции I, равен: 5у1 + 1· у3. Т.к. цена продукции I типа равна 3 ед., то 5у1 + у3 ≥ 3, в силу того, что интересы предприятия требуют, чтобы доход от продажи сырья был не меньше, чем от реализации продукции. Именно в силу такого экономического толкования система ограничений двойственной задачи принимает вид:

А целевая функция G = 400y1 + 300y2 + 100y3 подсчитывает условную суммарную стоимость всего имеющегося сырья. Понятно, что в силу I теоремы двойственности F(x*) = G(y*) равенство означает, что максимальная прибыль от продажи всей готовой продукции совпадает с минимальной условной ценой ресурсов. Условные оптимальные цены уi показывают наименьшую стоимость ресурсов, при которой выгодно обращать эти ресурсы в продукцию, производить.

Еще раз обратим внимание на то, что уi - это лишь условные, предполагаемые, а не реальные цены на сырье. Тот факт, что у1* = 0 вовсе не означает, что реальная цена первого ресурса нулевая. Равенство нулю условной цены означает лишь, что этот ресурс не израсходован полностью, имеется в излишке, недефицитен. Действительно, посмотрим на первое неравенство в системе ограничений задачи I, в котором подсчитывается расход первого ресурса: 5х1* + 0,4х2* + 2х3* + 0,5х4* = 66 < 400. его избыток составляет х5 = 334 ед. при данном оптимальном плане производства. Этот ресурс имеется в избытке, и поэтому для производителя он недефицитен, его условная цена равна 0, его не надо закупать. Наоборот, ресурс 2 и 3 используются полностью, причем у3 = 4 а у2 = 1, т.е. сырье третьего вида более дефицитно, чем второго, его условная цена больше. Если производитель продукции имел бы возможность приобретать дополнительно сырье к уже имеющемуся, с целью получения максимального дохода от производства, то увеличив сырье второго вида на единицу, он бы получил дополнительно доход в у2 денежных единиц, с увеличением на единицу сырья третьего вида, значение целевой функции увеличилось бы еще на у3 единицы.

Если перед производителем стоит вопрос, "выгодно ли производить какую-либо продукцию при условии, что затраты на единицу продукции составят 3, 1, 4 единиц 1, 2, 3-го видов сырья соответственно, а прибыль от реализации равна 23 единицам", то в силу экономического истолкования задачи ответить на этот вопрос несложно, поскольку затраты и условные цены ресурсов известны. Затраты равны 3, 1, 4, а цены у1* = 0, у2* = 1, у3* = 4. Значит, можно посчитать суммарную условную стоимость ресурсов, необходимых для производства этой новой продукции: 3 · 0 + 1 · 1 + 4 · 4 = 17 < 23. значит продукцию производить выгодно, т.к. прибыль от реализации превышает затраты на ресурсы, в противном случае ответ бы на этот вопрос был отрицательным.

Ответим на вопрос, как изменится целевая функция в оптимальном плане, если цену первого вида продукции увеличить до 20? Оценка y1=0, ресурс не дефицитен, и оптимальный план X не изменится: ΔFmax=Δc1*x1=(20-3)*0=0 В данном случае, значение целевой функции не изменилось, поскольку в оптимальном плане x1=0.

Анализ решения задачи линейного программирования с помощью теории двойственности

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

Двойственность

т.е. вторая переменная не ограничена по знаку, она может быть как больше 0, так и меньше 0. Построим двойственную задачу. Так как число ограничений равно трем, то имеем три переменных: u1, u2, u3. ЦФ задачи (Д) имеет вид: max W = U*B = u1b1 + u2b2 + u3b3 = u1 + 4u2 + 3u3 В прямой задаче имеем матрицу А: . В задаче (Д) имеем транспонированную матрицу: . Таким образом, двойственная задача выглядит так: max W = u1 + 4u2 + 3u3

Теорема двойственности. Если X и U - соответственно допустимые решения произвольных прямой и двойственной задач, то Z = C*X ≥ W = U*B. Следствие из теоремы. Если X * , U * - соответственно решения прямой и двойственной задач, удовлетворяющих равенству C*X * = U * B, то планы X * и U * – оптимальные решения прямой и двойственной задач соответственно. Теорема. Пусть заданы прямая и двойственная задачи: а) если прямая и двойственная задачи имеют решения, то каждая из этих задач имеет оптимальное решение и Z * = min(П) = max(Д) = W * б) если одна из них имеет неограниченный оптимум, то другая не имеет решения. Теорема. Два решения (X и U) соответственно прямой и двойственной задач оптимальны тогда и только тогда, если выполняется условие: (U* Aj - cj)*xj = 0; j = 1, n, где Aj – j–й столбец матрицы A. Поясним некоторые вопросы. На этапе постановки задачи производится анализ с целью ответить на вопросы: «Что будет, если…?» и (или) «Что надо, …, чтобы …?». Анализ с целью ответа на первый вопрос называется вариантным анализом, на второй – решениями по заказу. Вариантный анализ бывает следующих видов: Параметрическим будем называть такой анализ, который заключается в решении задачи при различных значениях некоторого параметра; Под структурным анализом будем понимать решение задачи оптимизации при различной структуре ограничений; Многокритериальный анализ – это решение задачи по разным целевым функциям; Если исходные данные, используемые при решении задачи, зависят от соблюдения дополнительных условий, то такой анализ называется анализом при условных исходных данных. Во вторую группу – решения по заказу – входят задачи, целью которых является решение задачи оптимизации при заданных значениях: переменных, левых частей ограничений, целевой функции. Кроме анализа, выполняемого на этапе постановки задачи, мощным средством, помогающим принять решение, является анализ полученного оптимального плана.