Xreferat.com » Рефераты по экономико-математическому моделированию » Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

2010

Вступ


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

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

Предметом дослідження є аналіз ринку ресурсів у передплановому періоді.

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

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


1. Теорія двоїстості та двоїсті оцінки у лінійному програмуванні


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

Задачі математичного програмування поділяються на два великі класи лінійні та нелінійні. Якщо цільова функція та обмеження є лінійними функціями, тобто вони містять змінні Хj у першому або нульовому степені. В усіх інших випадках задача буде нелінійною. Важливою перевагою лінійних задач є те, що для їх розв’язування розроблено універсальний метод, який називається симплексним методом. Теоретично кожну задачу лінійного програмування можна розв’язати. Для деяких класів лінійних задач, що мають особливу структуру, розробляють спеціальні методи розв’язування, які є ефективнішими. Наприклад, транспортну задачу можна розв’язати симплексним методом, але ефективнішими є спеціальні методи, наприклад метод потенціалів.

Економічні та технологічні процеси, як правило, є нелінійними, стохастичними, розвиваються в умовах невизначеності. Лінійні економіко-математичні моделі часто є неадекватними, а тому доводиться будувати нелінійні та стохастичні моделі. Розв’язувати нелінійні задачі набагато складніше, ніж лінійні, оскільки немає універсального методу розв’язування таких задач. Для окремих типів нелінійних задач розроблено численні спеціальні ефективні методи розв’язування. Проте слід зазначити, що на практиці застосовують, здебільшого, лінійні економіко-математичні моделі. Часто нелінійні залежності апроксимують (наближають) лінійними. Такий підхід на практиці є доволі ефективним.

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

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

Множина S в n-мірному евклідовому просторі називається опуклою множиною, якщо для будь-яких точок (елементів) цієї множини Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів точки Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів належать множині S за всіх значень Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів які належать відрізку Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Геометрично це означає, якщо Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів та Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів належать до множини S, то відрізок прямої, що з’єднує ці дві точки, також цілком належить до множини S.

Функція Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів визначена на опуклій множині лінійного простору (на опуклій множині S), називається опуклою, якщо виконується нерівність Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів для всіх Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів які належать відрізку Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планівКвадратичне програмування – цільова функція квадратична, а обмеження лінійні.

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

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

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

Економічні процеси розвиваються в часі, а тому відповідні моделі мають відображати динаміку. Це означає, що для знаходження оптимального плану потрібно застосовувати класи задач математичного програмування статичні (однокрокові) і динамічні (багатокрокові). Поняття динамічності зрозуміле, воно пов’язане з часом. Наприклад, якщо йдеться про план розвитку України до 2005 року, мають бути обґрунтовані значення відповідних макроекономічних показників не лише на 2005 рік, а й на всі проміжні роки, тобто враховано динаміку розвитку народногосподарських процесів. Такий план називають стратегічним.

У ньому має бути обґрунтована оптимальна (раціональна) траєкторія розвитку народного господарства. Проте під впливом некерованих чинників реальні показники щороку можуть відхилятися від планових. Тому постає потреба коригувати кожний річний план. Такі плани називають тактичними. Вони визначаються в результаті реалізації статичної економіко-математичної моделі.

Важливо чітко усвідомити відмінність між одно – та багатокроковими задачами. Багатокроковість як метод розв’язування задач математичного програмування зумовлюється, насамперед, їх багатовимірністю. Сутність цього методу полягає в тому, що оптимальні значення розглядуваної множини змінних знаходять крок за кроком, послідовно застосовуючи індукцію, причому рішення, яке приймається на кожному кроці, має задовольняти умови оптимальності щодо рішення, прийнятого на попередньому кроці. Така процедура може бути і не бути пов’язаною з часом. Однокрокові задачі, навпаки, характеризуються тим, що всі компоненти оптимального плану задачі визначаються одночасно на останній ітерації (кроці) алгоритму. Потрібно розрізняти ітераційність алгоритму і його багатокроковість. Наприклад, симплекс-метод розв’язування задач лінійного програмування є ітераційним, тобто якимось чином задаємо допустимий план і в результаті деякої кількості ітерацій дістаємо оптимальний план. Тут виконуються ітерації (кроки) алгоритму симплексного методу, але це не інтерпретується як багатокроковість економічного процесу (явища).

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

Щойно було розглянуто лише найбільші класи задач математичного програмування, які визначені згідно з математичними критеріями. Можна також за різними ознаками виокремити й підкласи. Це особливо стосується задач лінійного, нелінійного і стохастичного програмування. Наприклад, як окремий клас розглядають дробово-лінійне програмування, коли обмеження є лінійними, а цільова функція – дробово-лінійна. Особливий клас становлять задачі теорії ігор, які широко застосовуються в ринковій економіці. Адже тут діють дві чи більше конфліктних сторін, які мають цілі, що не збігаються, або протилежні цілі. У сукупності задач теорії ігор, у свою чергу, також виокремлюють певні підкласи. Наприклад, ігри двох осіб із нульовою сумою. Наведену класифікацію використано для структурування курсу «Математичне програмування».


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


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

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

Пряма задача:


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)


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

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

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

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


2.1 Правила побудови двоїстих задач


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

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

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

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

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

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

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

6. Матриця


Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів,


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

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів


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

Процес побудови двоїстої задачі зручно зобразити схематично:


Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Рис. 3.1. Схема побудови двоїстої задачі до прямої


Пари задач лінійного програмування бувають симетричні та несиметричні.

У симетричних задачах обмеження прямої та двоїстої задач є лише нерівностями, а змінні обох задач можуть набувати лише невід’ємних значень.

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

Всі можливі форми прямих задач лінійного програмування та відповідні їм варіанти моделей двоїстих задач у матричній формі наведено нижче.


Пряма задача

Двоїста задача

Cиметричні задачі

max F = CX

AX Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів B

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів 0

min Z = BY

ATY Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів C

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів 0

min F = CX

AX Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів B

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів 0

max Z = BY

ATY Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів C

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів 0


Несиметричні задачі

max F = CX

AX = B

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів 0

min Z = BY

ATY Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів C

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

min F = CX

AX = B

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів 0

max Z = BY

ATY Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів C

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів


До даної задачі лінійного програмування записати двоїсту.

max F = –5x1 + 2x2;


Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів


Розв’язання. Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція F максимізується і в системі обмежень є нерівності, то вони мусять мати знак «Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів». Тому перше обмеження задачі помножимо на (–1). Після цього знак нерівності зміниться на протилежний. Отримаємо:

max F = –5x1 + 2x2;

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Тепер за відповідними правилами складемо двоїсту задачу:


Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів;

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів


Або схематично (використовуючи компоненти векторів та матриць) зв’язок між парою цих задач можна зобразити так:


Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів


До заданої задачі лінійного програмування записати двоїсту.

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Розв’язання. Пряму задачу зведемо до стандартного вигляду. Оскільки цільова функція F мінімізується і в системі обмежень є нерівності, то вони мають бути виду «Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів». Тому друге обмеження задачі необхідно помножити на (–1). При цьому знак нерівності зміниться на протилежний. Отримаємо:

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Двоїста задача:

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів

Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планівДвоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планів


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


3. Основні теореми двоїстості та їх економічний зміст


Зв’язок між оптимальними розв’язками прямої та двоїстої задач встановлюють леми та теореми двоїстості. Розглянемо задачі (3.1) – (3.3) та (3.4) – (3.6) з економічною інтерпретацією.

Якщо Двоїста задача лінійного програмування: економічна інтерпретація знаходження оптимальних планівта Двоїста задача
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: