Сутність двоїстості в лінійному програмуванні. Зв'язок між математичними моделями двоїстих задач. Задача раціонального використання ресурсів і двоїста задача для неї, їх економічна інтерпретація.
Теория двойственности - центральная часть линейного прогр-вания. Исследование двойств-ти позволило получить важные теорит-ские (разработать эффективные методы решения ЗЛП, проанали-вать и оценить чувствительность моделей линей-го програми-ния) и практические результаты (дать эконо-кое истолкование полученного решения, раскрыть новые закономерности).На начальной стадии исследований ЗЛП обнаружили, что каждой ЗЛП соответствует другая, вполне определенная ЗЛП, т.е эти задачи взаимосвязаны: если исходной считать вторую, то ей будет соответствовать первая. Рассмотрим общий слушай задачи рационального использования ресурсов: Найти такие Xj,которые обеспечивают максимум функций, Z=c1x1+c2x2+…+cnxn(max)/
a11x1+a12x2 +..+ a1nxn< b1
a21x1+a22x2 +..+ a2nxn< b2
am1x1+am2x2 +..+ amnxn< bm
Экон-ская интерпретация этой задачи: сколько и какой продукции нужно произвести, чтобы при заданных объемах расходуемых ресурсов максим-вать прибыль. Для двойственной задачи: Пусть yi цена ед ресурса і-го вида.Найти такие у1,у2,..уm, которые придают минимум функции – f= b1y1+b2y2+..+bmym(min)
a11y1+a12y2 +..+ am1ym> C1
a12y1+a22y2 +..+ am2ym> C2
a1ny1+a2ny2 +..+ amnym> Cn
yi>0 (i=1?m)
Экон-кая интерпретация двойств-ой задачи: какими должны быть цены ед. ресурсов, чтобы при заданных объемах ресурсов(bi) и прибыль от реализации ед. продукции миним-вать общую стоимость ресурсов.
Симетричні і несиметричні пари двоїстих задач. Можливі види математичних моделей двоїстих пар задач.
Если системы основных ограничений как в исходной, так и в двойс-ой задаче, имеют вид неравенств, то такие пары наз. симметричными. При этом на переменные двойс-ой задачи накладывается условие неотриц-сти. Сущ. 2 вида матем-их моделей симметричной пары двойст-ых задач
(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.
Если система основных ограничений исходной задачи имеет вид уравнений, а двойс-ой задачи – вид неравенства одинакового смысла, то такую двоуст-ую пару называют несимметричной . Сущ. 2-х видов:
(1) Исходная задача Двойственная задача
Z = CX(min); f= YB (max);
AX = B; YA ≤С.
X ≥0.
(2) Исходная задача Двойственная задача
Z= CX (max); f = YB(min);
AX = B; YA ≥С.
X ≥ 0.
Зв'язок між оптимальними планами двоїстих пар задач (1-ша і 2-га теореми двоїстості). Як знайти розв'язок однієї із двоїстої пари задач при розв'язанні СМ другої задачі. Властивості двоїстих оцінок оптимального плану вихідної задачі.
Перша теорема двоїстості. Якщо одна з двоїстої пари задач має розвязок, то інша також розв’язувана, причому екстремальні значення цільових функцій однакові. Якщо цільова функція однієї із задач не обмежена на множині планів (немає розв’язків), то система обмежень іншої задачі суперечна (також немає розв’язків).
Друга теорема двоїстості. Для того, щоб плани X*=(x1*,x2*,…xn*) і Y*=(y1*,y2*,…,ym*) вихідної та двоїстої задач були оптимальними, необхідно і достатньо, щоб виконувались умови:
Компоненти оптимального плану двоїстої задачі дорівнюють відповідним оцінкам початкових базисних векторів (змінних).
Двоїсті оцінки опт. плану вихідної задачі використовуються:
1) як міра дефіцитності ресурсів. Якщо двоїста оцінка ресурсу нульова, то даний ресурс недефіцитний (після виробництва він є в надлишку); якщо ж більше 0, то відповідні ресурси дефіцитні (повністю використ-ся при виробництві).
2) як міра впливу обмежень на цільову функцію (розшивка «вузьких місць»). Для цього визнач-ся для кожного ресурсу верхні та нижні межі змін запасу, або інтервали стійкості. Інтервали стійкості відносно незмінності додатних компонент опт. плану:
3) як інструмент визначення ефективності включення тих чи інших видів продукції в опт. план вир-ва.
4) для балансування витрат та результатів (значення ц.ф. двоїстих задач співпадають).
5) як показник взаємозамінності ресурсів.