Розв'язок задачі лінійного програмування (стр. 3 из 4)

Економічну інтерпретацію кожної з пари задач розглянемо на прикладі виробничої задачі.

Початкова задача:

max z = c1x1 + c2x2 + … + cnxn

,

Визначити, яку кількість продукції

кожного j-го виду необхідно виготовляти в процесі виробництва, щоб максимізувати загальну виручку від реалізації продукції підприємства. Причому відомі: загальна кількість ресурсів – , нормативи використання кожного і-го виду ресурсу на кожен j-ий вид продукції – , а також – ціна реалізації одиниці продукції.

Розглянемо тепер ту саму задачу з іншої точки зору. Припустимо, що за певних умов доцільно продавати деяку частину чи всі наявні в господарстві ресурси. Необхідно визначити цінність ресурсів. Кожному ресурсу

поставимо у відповідність його оцінку . Умовно вважатимемо, що – ціна одиниці і-го ресурсу.

На виготовлення одиниці j-го виду продукції

витрачається згідно моделі всі m видів ресурсів у кількості відповідно . Оскільки ціни одиниці кожного виду ресурсів за припущенням дорівнюють , то загальна вартість ресурсів, що витрачені на виробництво одиниці j-го виду продукції обчислюється як

Продавати ресурси доцільно лише за умови, що кошти отримані в результаті продажу ресурсів будуть дорівнювати або перевищуватимуть суму, яку можливо було б отримати за реалізацію продукції виготовленої з тієї самої кількості ресурсів, тобто

.

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

.

Отже в результаті маємо двоїсту задачу:

Визначити, які мінімальні ціни можливо встановити для одиниці кожного і-го виду ресурсу

, щоб продаж ресурсів був більш доцільним ніж виробництво продукції. Причому відомі: загальна кількість ресурсів – , нормативи використання кожного і-го виду ресурсу на кожен j-ий вид продукції – , а також – ціна реалізації одиниці продукції.

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

», а для задачі відшукання мінімального значення – до вигляду « ».

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

1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.

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

3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі — на визначення найменшого значення (min), і навпаки.

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

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

6. Матриця

,

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

утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків — рядками.

Теорема (перша теорема двоїстості). Якщо одна з пари спряжених задач має оптимальний план, то і інша також має розв’язок, причому для оптимальних розв’язків значення цільових функцій співпадають

.

Якщо цільова функція однієї із задач не обмежена, то інша задача також не має розв’язку.

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

Пряма задача: Двоїста задача:

Для розв’язування задач симплексним методом необхідно привести їх до канонічної форми, для чого в систему обмежень задачі необхідно ввести m невід’ємних змінних, а в систему обмежень – n невід’ємних змінних. Поставимо обмеженням кожної задачі у відповідність змінні двоїстої.

Аналогічно:

Отримали наступну відповідність між змінними спряжених задач:

Основні змінні прямої задачі Додаткові змінні прямої задачі

Додаткові змінні двоїстої задачі Основні змінні двоїстої задачі