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

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

2010

Вступ

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

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

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

Мета роботи дослідіті плануван, здобуті за економіко-математичного моделями, на стійкість, а кож оцінювання СИТУАЦІЙ, які мают віконуватіся в передплановому періоді.

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

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

математичного програмування передусім є строгою математичних дісціпліною, тому крітеріямі класіфікації мают буті в основному математічні структури (Властивості) завдань и методів їх розв'язування. Зауважімо, Що одна й та сама задача з подивимось різніх математичних крітеріїв Може належати до кількох класів. Аджея Кожній крітерій підкреслює Ліше одну властівість Задачі на протівагу деякій іншій, тобто поділяє ВСІ Задачі на два класи (чі підкласі всередіні Певного класу).

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

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

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

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

множини S в n -мірному евклідовому просторі назівається опуклою множини, ЯКЩО для будь-яких точок (Елементів) цієї множини точки належать множіні S за Всіх значення які належать відрізку

геометричність Це означає, ЯКЩО та належать до множини S , то відрізок прямої, Що з'єднує ці Дві точки, кож ЦІЛКОМ належиться до множини S .

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

Далі Задачі математичного програмування поділяють на діскретні и неперервні. Дискретні назівають Задачі, в якіх одна, кілька або ВСІ змінні набуваються Ліше дискретних значення. Окрема клас становляит Задачі, в якіх одна або кілька змінніх набуваються цілочісловіх значення, тобто Задачі цілочіслового програмування. ЯКЩО ВСІ змінні можут набуваті будь-якого значення в Деяк інтервалах чіслової осі, то задача є неперервно.

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

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

Економічні процеси розвиваються в часі, а тому відповідні Моделі мают відображаті дінаміку. Це означає, Що для знаходження оптимального плану потрібно застосовуваті класи задач математичного програмування статічні (однокрокові) i динамічні (Багатокрокові). Поняття дінамічності зрозуміле, воно пов'язане з годиною. Наприклад, ЯКЩО йдеться про план розвітку України до 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

X 0

min Z = BY

... ATY C

Y 0

min F = CX

AX B

X 0

max Z = BY

ATY C

Y 0

Несіметрічні Задачі

max F = CX

AX = B

X 0

min Z = BY

ATY C

Y

min F = CX

AX = B

X 0

max Z = BY

ATY C

Y

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

max F = -5 x 1 + 2 x 2;

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

max F =-5x1 + 2x2;

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

;

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

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

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

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

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

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

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

ЯКЩО та - Допустимі розв'язки відповідно прямої та двоїстої задач, то віконується нерівність

або. (3.7)

доведення . Помножімо кожне рівняння системи (3.2) на відповідну змінну двоїстої Задачі:

Підсумувавші праві и ліві частина нерівностей, отрімаємо:

. (3.8)

Аналогічно перетворімо систему обмежень (3.5) двоїстої Задачі:

Підсумувавші після множення тут кож ліві та праві частині, отрімаємо нерівність:

(3.9)

Ліві Частина нерівностей (3.8) та (3.9) збігаються, отже:

.

Нерівність (3.7) доведено.

ЯКЩО та - Допустимі розв'язки відповідно прямої та двоїстої задач, для якіх віконується рівність

(3.10)

то X *, Y * - оптімальні розв'язки відповідніх завдань.

доведення . Нехай - допустимий план прямої Задачі (3.1) - (3.3). Тоді на підставі нерівності (3.7) маємо:. ЯКЩО 1

1 0 0

2

0 1 0

0 0 1

0 0 0

(3.12)

Звідсі:

(3.13)

(3.14)

. (3.15)

,

. (3.16)

. (3.17)

, (3.18)

. (3.19)

Максимальний За умів

.

(3.21)

. (3.23)

,

. (3.25)

Отрімаємо:

;

;

.

,

,.

Отрімаємо:

;

.

Теорему доведено.

ма двоїстості

Як Було з'ясовано в попередніх параграфі, існування двоїстіх змінніх уможлівлює зіставлення витрат на виробництво и ЦІН на продукцію, на підставі Чого обґрунтовується Висновок про доцільність чи недоцільність виробництва шкірного увазі продукції. Крім цього, значення двоїстої оцінкі характеризує зміну Значення цільової функції, Що зумовлена ​​малімі змінамі вільного члена відповідного обмеження. Дяни твердження формулюється у вігляді Такої теореми.

Теорема ( третя теорема двоїстості ) . Компонента оптимального плану двоїстої Задачі дорівнюють Значення Частина похідніх від цільової функції за відповіднімі аргументами, або

(3.28)

доведення . Розглянемо задачу лінійного програмування, Поданєв в канонічній формі:

(3.29)

(3.30)

(3.31)

Двоїсту задачу до Задачі (3.29) - (3.31) сформулюємо так: Знайте оптимальний план, за Якого мінімізується значення

(3.32)

за умов:

(3.33)

причому Умова невід'ємності змінніх відсутня.

Позначімо - оптимальний план двоїстої Задачі, - оптимальний план Задачі (3.29) - (3.31). За дерло теореми двоїстості відомо, Що:

,

або

. (3.34)

Оскількі досліджується питання впливим Зміни значень на F, то лінійну функцію (3.34) можна розглядаті Як функцію від аргументів. Тоді частінні похідні за зміннімі Будуть дорівнюваті компонентам оптимального плану двоїстої Задачі:

. (3.35)

Однак дяни твердження Справедливе Ліше у тому разі, коли компоненти оптимального плану залішаються постійнімі, а оскількі за дерло теореми двоїстості, то значення двоїстіх оцінок Будуть незміннімі Ліше за Умови постійної структури оптимального плану початкової Задачі.

Отже, рівності (3.35) справджуються Ліше за незначна змін, інакше суттєва Зміна умов початкової Задачі (право частин системи обмежень (3.30) та цільової функції (3.32)) приведе до Зміни базису в оптимальному плані прямої Задачі, а значити, и до іншого розв'язку двоїстої.

Економічний Зміст третьої теореми двоїстості . Двоїсті оцінкі є унікальнім інструментом, Який Дає змогу зіставляті непорівнянні Речі. Очевидно, Що неможливим є просто зіставлення величин, які мают Різні одініці вімірювання. ЯКЩО взяти Як приклад виробничу задачу, то цікавім є питання: як змінюватім...еться Значення цільової функції (Може вімірюватіся в грошових Одиниця) за Зміни обсягів різніх ресурсів (можут вімірюватіся в тоннах, м2, люд./рік, га ТОЩО).

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

Отже, за Умови незначна змін Замість Задачі (3.29) - (3.31) маємо нову задачу, де замінено на. Позначімо через оптимальний план Нової Задачі. Для визначення НЕ потрібно розв'язувати нову задачу лінійного програмування, а достатності скорістатіся формулою, де - оптимальний план Задачі (3.29) - (3.31).

4. Приклади застосування Теорії двоїстості для знаходження оптимальних планів прямої та двоїстої задач

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

До заданої Задачі лінійного програмування запісаті двоїсту задачу. Розв'язати одну з них симплекс-методом та візначіті оптимальний план Другої Задачі, вікорістовуючі співвідношення Першої теореми двоїстості.

max Z = - 5 x1 + 2 x2

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

max Z = - 5 x1 + 2 x2

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

min F = - y1 + 5 y2

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

1. max Z = - 5 x1 + 2 x2 + 0 x3 + 0 x4

2. векторній формі запису системи обмежень має Вигляд:

,

де,,,,.

У сістемі векторів для утворення Початкова одінічного базису відсутній один вектор. Тому введемо Штучний змінну в перше обмеження.

3. Розшірена задача лінійного програмування буде такою:

max Z = - 5 x1 + 2 x2 + 0 x3 + 0 x4 - М x5

У Цій Задачі х 4 та х 5 - базісні змінні, а х1, х2, х3 - Вільні. Нехай х1 = х2 = х3 = 0, тоді х4 = 5; х5 = 1.

Перший опорний план Задачі:

X0 = (0; 0; 0; 5; 1), Z0 = - M.

З останньої симплекс-табліці запішемо оптимальний план прямої Задачі :

Х * = (0; 5/3; 2/3; 0), Z max = 10/3.

Згідно Зі співвідношенням двоїстості за дерло теореми можна вісновуваті, Що Оптимальний план двоїстої Задачі існує и min F = max Z = 10/3.

компоненти вектора Y * (Оптимальний план двоїстої Задачі) візначімо за формулою:

,

де та містіться в стовпчіку В«СбазВ» останньої симплекс-табліці;

.

Матриця D-1 кож містіться в Останній симплекс-табліці у стовпчіках змінніх В« x5 В» та В« X4 В», які утворювалі Початковий базис.

Отже,

,

min F = - 1 х 0 + 5 х 2/3 = 10/3.

Застосувавші для розв'язування прямої Задачі симплекс-метод, мі знайшлі її оптимальний план, а потім Визначіть Оптимальний розв'язок двоїстої Задачі за допомог співвідношень Першої теореми двоїстості.

До заданої Задачі лінійного програмування запісаті двоїсту задачу. Розв'язано двоїсту задачу графічно, візначіті оптимальний план прямої Задачі.

min Z = x1 + 2 x2 + 2 x3

Розв'язання . За відповіднімі правилами побудуємо двоїсту задачу:

mах F = y1 + 4 y2

Зауважімо, Що Задачі несіметрічні, и того змінна у1, Що відповідає Першому рівнянню в сістемі обмежень прямої Задачі, Може мати будь-який знак, а змінна у2 - Ліше невід'ємна.

Двоїста задача має Дві змінні, а отже, її можна розв'язати графічно (рис. 3.2).

Рис. 3.2

Найбільшого Значення цільова функція двоїстої Задачі F досягає в точці В багатокутніка ABCD . Її координати візначімо розв'язання системи рівнянь:

Отже, Y * = (- 2/3; 4/3); mах F = 1 х (- 2/3) + 4 х 4/3 = 14/3.

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

Підставімо Y * у систему обмежень двоїстої Задачі и з'ясуємо, Як виконують обмеження цієї Задачі:

Оскількі перше обмеження для оптимального плану двоїстої Задачі віконується Як строга нерівність, то вісновуємо, Що перша змінна прямої Задачі дорівнюватіме нулю х 1 = 0 (Перша частина Другої теореми двоїстості).

Тепер проаналізуємо Оптимальний план двоїстої Задачі. Оскількі одного компонента планом у2 = 4/3 додатна, то друге обмеження прямої Задачі для Х * віконуватіметься Як строге рівняння (друга частина Другої теореми двоїстості).

об'єднуючи здобутя інформацію, можна запісаті систему обмежень прямої Задачі Як систему двох рівнянь, в якій х1 = 0, та візначіті Решт змінніх:

тобто Х * = (0; 5/3, 2/3), min Z = 1 х 0 + 2 х 5/3 + 2 х 2/3 = 14/3.

Умова min Z = max F = 14/3 віконується, и того Х * = (0; 5/3, 2/3); Y * = (- 2/3; 4/3) є оптимальними планами відповідно прямої та двоїстої задач.

Візначіті, чі є оптимальними Такі плани сформульованої Задачі лінійного програмування:

min Z = 12 x1 - 4 x2 + 2 x3

а) Х = (8/7; 3/7; 0), б) Х = (0; 1/5; 8/5); в) Х = (1/3; 0; 1/ 3).

Розв'язання . Принцип розв'язування задач такого типу грунтується на вікорістанні Другої теореми двоїстості. Необхідно побудуваті двоїсту задачу та, допускаючи, Що відповідній план Х є оптимальним, візначіті Оптимальний розв'язок двоїстої Задачі. ЯКЩО при цьому екстремальні Значення цільовіх функцій Будуть однаково за величиною, то припущені правильне. Протилежних можна вісновуваті в таких випадка:

1. ЯКЩО запропонованих план Х Неприпустимо, тобто НЕ задовольняє систему обмежень прямої Задачі.

2. ЯКЩО визначеня план двоїстої Задачі неприпустимо, тобто НЕ задовольняє ВСІ обмеження двоїстої Задачі.

3. ЯКЩО визначеня план двоїстої Задачі допустимі, альо для нього екстремального Значення цільової функції F не дорівнює значенню функції Z , тобто НЕ віконується Умова Першої теореми двоїстості.

Запішемо двоїсту задачу до прямої Задачі лінійного програмування:

max F = y1 + 2 y2

Перевірімо запропоновані плани на оптімальність.

1. Х = (8/7, 3/7; 0). Підставімо Його в систему обмежень прямої Задачі:

обидвоє обмеження виконують, и того Х = (8/7, 3/7; 0) є допустимим планом прямої Задачі. Пріпустімо тепер, Що зазначеним план є оптимальним планом прямої Задачі. Тоді розрахуємо для нього величину цільової функції: Z = 12 х 8/7 - 4 х 3/7 + 2 х 0 = 12.

Скорістаємося другою теореми двоїстості та візначімо відповідній план двоїстої Задачі. Оскіль...кі x1 = 8/7> 0; x2 = 3/7> 0, то згідно з другою Частина Другої теореми двоїстості можна запісаті перше та друге обмеження Як рівняння и візначіті у1 та у2 :

Підставімо ці Значення в Третє обмеження системи двоїстої Задачі:

;

.

Для визначених значень у1 = 4; у2 = 4 Це обмеження НЕ віконується, и того відповідній план у = (4; 4) є неприпустимим планом двоїстої Задачі. Внаслідок цього наше припущення, Що Х = (8/7, 3/7; 0) є оптимальним планом прямої Задачі, віявілося помилковості.

2. Х = (0; 1/5; 8/5). Підставімо цею план у систему обмежень прямої Задачі:

План допустимий, и для нього Z = 12 х 0 - 4 х 1/5 + 2 х 8/5 = 12/5.

Візначімо відповідній план двоїстої Задачі. Оскількі компоненти x 2 та x 3 додатні, то друга и Третє обмеження двоїстої Задачі можна запісаті Як рівняння:

Перевірімо, чі віконується перше обмеження двоїстої Задачі для визначених значень у1 та у2 : 2 х 8/5 + 2/5 = 18/5 <12. Отже, перше обмеження віконується, и тому у = (8/5, 2/5) є допустимим планом двоїстої Задачі. Для нього

F = 8/5 + 2 х 2/5 = 12/5 = Z .

З Оглядова на вікладене можна вісновуваті, Що Y * = (8/5, 2/5) є оптимальним планом двоїстої Задачі, а X * = (0; 1/5; 8/5) - оптимальний планом прямої Задачі.

Наше припущені відносно запропонованих планом віявілося правильно.

3. Х = (1/3; 0; 1/3). Для цього планом обмеження прямої Задачі виконують так:

Оскількі Х = (1/3; 0; 1/3) є неприпустимим планом, то ВІН НЕ Може буті кож оптимально планом прямої Задачі.

Отже, Перевірка запропонованих планів на оптімальність дала Такі результати: а) ні; б) так, Х * = (0; 1/5; 8/5), min Z = 12/5; в) ні.

Список використаних джерел

1. Абрамов Л.М., Капустін В.Ф. Математичне програмування. Л., Вид-во Ленінград. ун-ту, 1976. - 184 с.

2. Акулич І.Л. Математичне програмування в прикладах і задачах. - М.: Вищ. шк., 1985.

3. Ашманов С.А. Лінійне програмування. - М.: Наука, 1981.

4. Белмана Р. Динамічне програмування. - М.: Изд-во іноземної літератури, 1960.

5. Белмана Р., Дрейфус С. Прикладні задачі динамічного програмування. - М.: Наука, 1965.

6. Вагнер Г. Основи дослідження операцій. - Т. 1-3. - М.: Мир, 1972.

7. Вентцель Е.С. Дослідження операцій. М.: В«Рад. радіо В», 1972. - 552 с.

8. Вентцель Е.С. Елементи динамічного програмування. - М.: Наука, 1964.

9. Гольштейн Є.Г., Юдін Д.Б. Нові напрямки в лінійному програмуванні. - М.: Радянське радіо, 1966.

10. Гольштейн Є.Г., Юдін Д.Б. Задачі лінійного програмування транспортного типу. - М.: Наука, 1969.

11. Данциг Дж. Лінійне програмування, його узагальнення і додатки. - М.: Прогрес, 1966.

12. Зайченко Ю.П. Дослідження операцій: Підручник. - 4-ті вид., Перероб. и допів. - К., 2000. - 688 с.

13. Зангвілл У. Нелінійне програмування. Єдиний підхід. М.: В«Сов.радіоВ», 1973. - 312 с.

14. Єрмольєв Ю.М., Ястремський О.І. Стохастичні моделі і методи в економічному плануванні. М.: Наука, 1979. - 249 с.

15. Єрмольєв Ю.М. Методи стохастичного програмування. - М.: Наука, 1976.

16. Каліхман І.Л. Збірник задач з математичного програмування. - М.: Вища шк., 1975.