Розділ 1. Застосування теорії двоїстості для задач лінійного програмування
В результаті ми отримуємо нову задачу (1.4) — (1.6) і вона називається двоїстою до задачі (1.1) — (1.3). Ці задачі записані у матричній формі виглядатимуть так: Тепер уявімо, що деяке інше підприємство звернулося до даного підприємства із пропозицією викупити всі наявні ресурси відповідно за цінами. Вивчення теорії двоїстості доцільно розпочати із побудови пари двоїстих задач. Для цього… Читати ще >
Розділ 1. Застосування теорії двоїстості для задач лінійного програмування (реферат, курсова, диплом, контрольна)
Поняття двоїстості та її економічна інтерпретація для ЗЛП
Теорія двоїстості вивчає властивості двох тісно пов’язаних між собою задач. Кожній задачі лінійного програмування можна поставити у відповідність іншу, спеціальним чином побудовану, задачу, яка називається двоїстою. Дві такі задачі утворюють пару взаємодвоїстих задач. Початкову задачу в такій парі називають прямою. Якщо прямою вважати двоїсту задачу, то двоїста до неї буде співпадати з початковою. Зв’язок між прямою і двоїстою задачою настільки тісний, що, розв’язавши одну з них, можна отримати розв’язок іншої.
Вивчення теорії двоїстості доцільно розпочати із побудови пари двоїстих задач. Для цього використаємо задачу виробничого планування.
Нехай підприємство виготовляє певну кількість товарів, використовуючи певну кількість різноманітних ресурсів. Відомою є кількість одиниць кожного виду ресурсу, що використовується для виготовлення одиниці кожного виду продукції, запас кожного ресурсу, а також ціна одиниці всіх видів продукції.
Складемо економіко-математичну модель задачі.
Нехай.
n — кількість видів продукції, що виготовляються на підприємстві;
m — кількість видів ресурсів, що використовуються для виробництва продукції;
— кількість одиниць продукції іго виду, що використовуються для виготовлення одиниці продукції jго виду;
— запас ресурсу іго виду; - прибуток від реалізації одиниці продукції jго;
— кількість одиниць продукції jго виду, що буде вигототовлятися підприємством.
Отже, математична модель задачі матиме такий вигляд:
;(1.1).
;(1.2).
.(1.3).
Пряма задача полягає у визначенні такого оптимального плану виробництва продукції.
.
який дає найбільший дохід.
Тепер уявімо, що деяке інше підприємство звернулося до даного підприємства із пропозицією викупити всі наявні ресурси відповідно за цінами .
Підприємству буде вигідно продати ресурси лише тоді, коли кошти, отримані від продажу, будуть не менші ніж прибуток, отриманий від продажу виготовленої продукції.
Якщо друге підприємство закупить усі ресурси, то воно заплатить.
Метою другого підприємства буде мінімізація витрат на купівлю ресурсів, звідси одержуємо таку задачу:
(1.4).
; (1.5).
. (1.6).
В результаті ми отримуємо нову задачу (1.4) — (1.6) і вона називається двоїстою до задачі (1.1) — (1.3). Ці задачі записані у матричній формі виглядатимуть так:
(1.7).
(1.8).