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

Понятие двойственности. Построение двойственных задач.

ЛЕКЦИЯ 4

Рассмотрим задачу оптимального использования сырья. Пусть на предприятии решили использовать рационально отходы основного производства. В плановом периоде появились отходы сырья m -видов, в объеме b_{i ,} где i =1,2,….,m. Из этих отходов можно выпуклость n-видов неосновной продукции. Пусть a _{i j} –норма расхода сырья i –вида на единицу j –продукции, где j =1,2…, n. c _j –цена реализации единицы j –продукции. х_j –объем выпуска j –продукции, обеспечивающий предприятию max прибыли.

Max Z = c₁x₁ + c₂x₂ +…+ c _n x _n

a₁₁x₁ + a₁₂x₂ +…+ a_1nx_n <= b₁

……………………………

A_m1x₁ + a_m2x₂ +….+ a _mn x _n < b _m

Предположим, что при изучении вопроса об использовании отходов основного производства, на предприятии появилась возможность реализации их некоторой организации. Обозначим цены на эти отходы У₁,У₂,…,У_m.

Данные цены (оценки) должны быть установлены исходя из некоторых требований, отражающих несовпадающие интересы предприятия и сторонней организации

Данные цены (оценки) должны быть установлены исходя из некоторых требований, отражающих несовпадающие интересы предприятия и сторонней организации:

1)общую стоимость отходов сырья, покупаемая организация стремиться минимизировать.

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

Min f=b₁y₁ + b₂y₂ +…+ b _m y _m

A₁₁y₁ + a₂₁y₂ +…+ a_m1y_m =>c₁, левая часть означает выручку за сырье, которая поступает на производство единицы продукции первого вида.

……………………………

A_1ny₁ + a_2ny₂ +…+ a _mn y _m => c _n

Переменные y _i называются двойственными оценками. Или объективно-обусловленными оценками. Или же теневыми ценами.

Эти задачи называются парой взаимодвойственных задач. Так как эти задачи записаны в симметричной форме их привыкли называть парой симметричных двойственных задач.

Прямая Max Z=c j x j a ij xj <=b I

Двойственная Min Z=bi x i a ij xj => cj

Их взаимосвязь между собой:

1)если прямая на max,то двойственная будет на min и наоборот.

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

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

4)матрицы ограничений прямой и двойственной задач является транспонированными друг другу.

5)если прямая задача на max,то ее система ограничений неравенства со знаком меньше или равно. Двойственная решается на min и ее система больше или равно.

6)чисто ограничений прямой равно числу переменных двойственной,а число ограничений двойственной равно числу переменных прямой.

7)все переменные в задачах неотрицательные.

Пример: предприятие может выпускать 4 вида продукции, сбыт любого количества продукции обеспечен. Для изготовления продукции используются трудовые ресурсы: полуфабрикаты и становочные оборудования. Общий объем ресурсов в расчете на трудовую неделю, расход каждого ресурса на единицу выпускаемой продукции и прибыль,получаемая за единицу выпускаемой продукции. Требуется определить план выпуска, доставляющий max прибыли. Выполнить послеоптимизационный анализ решения и параметров модели.

ресурсы	П1	П2	П3	П4	Объем
Трудовые
Полуфабрикаты
Стан.оборуд-е
Цена за единицу

Max Z =65 V₁ +70 V₂ +60 V₃ +120 V₄

4 V₁ +2 V₂ +2 V₃ +8 V₄ <=4800

2 V₁ +10 V₂ +6 V₃ <=2400

V₁ +2 V₃ + V₄ <=1500

V₁, V₂,V₃, V₄ =>0

Min f =4800 y₁ +2400 y₂ +1500 y₃

y ₁,y ₂ =>0

4 y₁ +2 y₂ + y₃ =>65

Дата добавления: 2014-01-07