АНАЛІЗ ОТРИМАНИХ ОПТИМАЛЬНИХ РІШЕНЬ

З кожним завданням лінійного програмування тісно пов'язано інше лінійне завдання, зване подвійною; первинне завдання називається початковим, або прямій.

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

Добре розроблений математичний апарат лінійного програмування дозволяє не тільки отримувати оптимальний план, але і робити ряд економічно змістовних виводів, заснованих на властивостях завдання, подвійного до початкової ЗЛП. Змінні подвійного завдання у, називають подвійними оцінками, або «цінами» ресурсів, або тіньовими цінами. Кожне із завдань подвійної пари фактично є самостійним завданням лінійного програмування і може бути вирішена незалежно від іншої.

Подвійне завдання по відношенню до початкової складається згідно наступним правилам:

1. Цільова функція початкового завдання формулюється на максимум, а цільова функція подвійного завдання - на мінімум, при цьому в завданні на максимум всі нерівності у функціональних обмеженнях мають вигляд, в завданні на мінімум - вигляд .

2. Матриця, складена з коефіцієнтів при невідомих в системі обмежень початкового завдання, і аналогічна матриця в подвійному завданні виходять один з одного транспонуванням.

3. Число змінних в подвійному завданні дорівнює числу функціональних обмежень початкового завдання, а число обмежень в системі подвійного завдання - числу змінних в початковому завданні.

4. Коефіцієнтами при невідомих в цільовій функції подвійного завдання є вільні члени в системі обмежень початкового завдання, а правими частинами в обмеженнях подвійного завдання - коефіцієнти при невідомих в цільовій функції початкового завдання.

5. Кожному обмеженню одного завдання відповідає змінна іншого завдання: номер змінної збігається з номером обмеження; при цьому обмеженню, записаному у вигляді нерівності, відповідає змінна, пов'язана з умовою позитивності. Якщо функціональне обмеження початкового завдання є рівністю, то відповідна змінна подвійного завдання може набувати як позитивних, так і негативних значень.

Математичні моделі пари подвійних завдань можуть бути симетричними і несиметричними. У несиметричних подвійних завданнях система обмежень початкового завдання задається у вигляді рівності, а подвійною - у вигляді нерівностей, причому в останній змінні можуть бути і негативними. У симетричних завданнях система обмежень як початкового, так і подвійного завдання задається нерівностями, причому на подвійні змінні накладається умова позитивності.

Модель початкового (прямій) завдання в загальному вигляді може бути записана таким чином:

Модель подвійного завдання має вигляд:

Два приведені завдання утворюють пару симетричних подвійних завдань.

Поиск по сайту: