12. Сутність двоїстості в лінійному програмуванні. Зв'язок між математичними моделями двоїстих задач. Задача раціонального використання ресурсів і двоїста задача для неї, їх економічна інтерпретація.

С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной.

Первоначальная задача называется исходной.ДЗ имеет свою мат.модель: g(y)=∑biyi(min)-функция цели ДЗ; ∑aijyi≥cj, j=1,n – система функ.ограничений; yi≥0, i=1,m

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

Для производства n видов продукции расходуется m видов ресурсов. Известны:

aij-норма расхода ресурса i–го вида на ед. продукции j–го вида (i = 1,m; j =1,n)

bi-запас ресурса i–го вида на планируемый период(i=1,m)

cj-прибыль от реализации еденицы продукции j–го вида(j=1,n)

Составить план производства, обеспечивающий максим. прибыль. Введем обозначения: xij-планируемый выпуск продукции j-го вида; z-прибыль от реализации всей производственной продукции.

Найти вектор xj, который обеспечивает максимум функции

Z = C1x1 + C2x2 + … + Cnxn(max) (1)

(2) a11x1 + a12x2 + … + a1nxn ≤ b1,

a21x1 + a22x2 + … + a2nxn ≤b2,

…………………………………

am1x1 + am2x2 + … + amnxn ≤bm,

(3)xj ≥0 (j =1,..,n)

Экономическая интерпретация этой задачи: сколько и какой продукции требуется произвести, чтобы при заданных обьемах расходуемых ресурсов минимизировать прибыль.

Составим матем. Модель и дадим эконом. Интерпретацию двойственной задачи по отношению к задаче (1)-(3)

Пусть уi - цена единицы i-го ресурса, тогда стоимость всех ресурсов, равна

f = b1y1 + b2y2 + … + bmym.

Прибыль от продажи ресурсов, необходимых для выпуска еденицы j-го изделия не должна быть меньше прибыли от реализации готового изделия: a1j y1 + a2jy2 + … + amjym ≥Cj

Итак, двойственную задачу можно сформулировать след. образом. Найти такие y1, y2, .., ym, которые придают минимум функции

f = b1y1 + b2y2 + … + bmym.

И удовлетворяют ограничениям

a11y1 + a12y2 + … + am1ym ≥C1,

a12y1 + a22y2 + … + am2ym ≥ C2,

…………………………………

a1ny1 + a2ny2 + … + amnym ≥Cm,

yj ≥0 (i =1,.., m)

эконом. интерпретация:

Исходная задача. Сколько и. какой продукции xj (j =1,2, ..., n)

необходимо произвести, чтобы при заданных стоимостях Cj (j =1,2, ..., n)

единицы продукции и размерах имеющихся ресурсов bi (i =1,2, ..., n)

максимизировать выпуск продукции в стоимостном выражении.

Двойственная задача. Какова должна быть цена единицы

каждого из ресурсов, чтобы при заданных количествах ресурсов bi и величинах

стоимости единицы продукции Ci минимизировать общую стоимость затрат?

Переменные уi называются оценками или учетными, неявными ценами.

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

исходных или двойственных задач, поэтому имеет смысл говорить о паре

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

13. Симетричні і несиметричні пари двоїстих задач. Можливі види математичних моделей двоїстих пар задач.

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

Если система основных ограничений исходной задачи имеет вид уравнений, а двойственной задачи – вид неравенств одинакового смысла, то такую двойственную пару назыв. несимметричной двойственной парой. На переменные двойственной задачи не наклыдывается условие неотрицательности.

Виды:

Несимметричные задачи

(1) Исходная задача Двойственная задача

Z = CX(min); f= YB (max);

AX = B; YA ≤С.

X ≥0.

(2) Исходная задача Двойственная задача

Z= CX (max); f = YB(min);

AX = B; YA ≥С.

X ≥ 0.

Симметричные задачи

(3) Исходная задача Двойственная задача

Z = CX(min); f = YB(max);

AX≥ B; YA ≤ С.

X ≥0. Y≥ 0.

(4) Исходная задача Двойственная задача

Z= CX (max;) f= YB(min);

AX ≤ B; YA ≥С.

X ≥0. Y ≥ 0.

14. Зв'язок між оптимальними планами двоїстих пар задач (1-ша і 2-га теореми двоїстості). Як знайти розв'язок однієї із двоїстої пари задач при розв'язанні СМ другої задачі. Властивості двоїстих оцінок оптимального плану вихідної задачі.

1теорема. Для взаимодвойственных ЗЛП имеет мести один из след.взаимоисключащих случаев:1.в прямой и ДЗ имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают,тоесть min g(y)=max f(x);2. в прямой задаче допустимое множество не пусто.а целевая функция на этом множестве неограниченна сверху,при этом у ДЗ будет пустое допустимое множество.;3. В ДЗ допустимое множество не пусто,а целевая функция неограниченна снизу на этом множестве, при этом у ИЗ допустимое множество оказывается пустым.;4. Обе из рассматриваемых задач двойственной пары имеют пустое допустимое множество.

2 теорема. Пусть х=(х1,х2..хn)-допустимое решение ИЗ,а у=(у1,у2,..,уn)-допустимое решение ДЗ. Для того, что бы х и у были оптимальными решениями необходимо и достаточно след.условия: yi(∑aijxj-bj)=0, i=1,m; xj(∑aijyi-cj)=0,j=1,n. Эти условия позволяют зная оптимальное решение одной из двойственных задач найти оптимальное решение другой.