Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Основні теореми подвійності






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

Перша теорема подвійності:

Для двох взаємно двоїстих ЗЛП має місце один з взаємовиключних випадків:

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

. (7)

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

3. Області визначення обох завдань є порожні множини.

Друга теорема подвійності (теорема рівноваги):

Для того, щоб X = (x1, x2,..., х п) і Y =(у1, у2, …, уm) – припустимі рішення відповідно вихідної та двоїстої задач – були їх оптимальними рішеннями, необхідно і достатньо виконання таких умов «доповнюючої не жорсткості»:

, (8)

. (9)

Іншими словами, допустимі плани Х і Y пари двоїстих задач оптимальні тоді і тільки тоді, коли вони задовольняють таким умовам:

1) якщо x j > 0, то

2) якщо y i > 0, то

3) якщо то x j = 0,

4) якщо то y i = 0.

Умови (8)-(9) дозволяють по оптимальному рішенню однієї з взаємно двоїстих задач, знайти оптимальне рішення іншої задачі. Тому для розв’язання певної ЗЛП можна спочатку розв’язати двоїсту задачу, а потім визначити рішення вихідної задачі.

Третя теорема подвійності (теорема про оцінки):

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

. (10)

Звідси випливає, що приріст цільової функції DF визначається добутком приросту запасу ресурсів Dbi на величину оптимальної оцінки уi. Рівність справедлива, якщо величина Dbi є відносно невеликою (межі зміни встановлюються на основі теорії стійкості оптимальних рішень ЛП).

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

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал