Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

РОЗДІЛ 3. ТЕОРІЯ ДВОЇСТОСТІ ТА ДВОЇСТІ ОЦІНКИ У ЛІНІЙНОМУ ПРОГРАМУВАННІ

«И самый последний нищий, при других условиях,

способен быть первым богачом».

Сочинения Козьмы Пруткова

3.1. Економічна інтерпретація прямої та двоїстої задач лінійного програмування

Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею.

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

Пряма задача: max F = c1x1 + c2x2 + … + cnxn (3.1)

за умов: (3.2)

. (3.3)

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

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

На виготовлення одиниці j-го виду продукції витрачається згідно з моделлю (3.1)—(3.3) m видів ресурсів у кількості відповідно . Оскільки ціна одиниці і-го виду ресурсу дорівнює , то загальна вартість ресурсів, що витрачаються на виробництво одиниці j-го виду продукції, обчислюється у такий спосіб:

.

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

.

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

.

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

(3.4)

за умов: (3.5)

(3.6)

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

Зауважимо, що справжній зміст величин — умовні ціни, що виражають рівень «цінності» відповідного ресурсу для даного виробництва. Англійський термін «shadow prices» у літературі перекладають як «оцінка» або «тіньова, неявна ціна». Академік Л. В. Канторович назвав їх об’єктивно обумовленими оцінками відповідного ресурсу.

Задача (3.4)—(3.6) є двоїстою або спряженою до задачі (3.1)—(3.3), яку називають прямою (основною, початковою). Поняття двоїстості є взаємним. По суті мова йде про одну і ту ж задачу, але з різних поглядів. Дійсно, не важко переконатися, що двоїста задача до (3.4)—(3.6) збігається з початковою. Тому кожну з них можна вважати прямою, а іншу — двоїстою. Симетричність двох таких задач очевидна. Як у прямій, так і у двоїстій задачі використовують один набір початкових даних: , ; . Крім того, вектор обмежень початкової задачі стає вектором коефіцієнтів цільової функції двоїстої задачі і навпаки, а рядки матриці А (матриці коефіцієнтів при змінних з обмежень прямої задачі) стають стовпцями матриці коефіцієнтів при змінних в обмеженнях двоїстої задачі. Кожному обмеженню початкової задачі відповідає змінна двоїстої і навпаки.

Початкова постановка задачі та математична модель може мати вигляд як (3.1)—(3.3), так і (3.4)—(3.6). Отже, як правило, кажуть про пару спряжених задач лінійного програмування.