WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Теорія двоїстості та двоїсті оцінки в аналізі розв’язків лінійних оптимізаційних моделей - Реферат

Теорія двоїстості та двоїсті оцінки в аналізі розв’язків лінійних оптимізаційних моделей - Реферат


Реферат на тему:
Теорія двоїстості та двоїсті оцінки в аналізі розв'язків лінійних оптимізаційних моделей.
План.
1.Зв?язок між розв'язками прямої і двоїстої задачі.
2. Література
Зв'язок між розв'язками прямої і двоїстої задач.
Розглянемо кілька двоїстих задач, утворену основною задачею лінійного програмування і двоїстої до неї.
Вихідною задачею є: знайти максимум функції
(1)
при умовах
(2)
(3)
Двоїста задача: знайти мінімум функції
(4)
при умовах
(5)
Кожна з задач двоїстої пари (1) - (3) і (4), (5) фактично є самостійною задачею лінійного програмування і може бути вирішена незалежно одна від іншої. Однак при визначенні симплексним методом оптимального плану однієї з задач тим самим знаходиться рішення й іншої задачі.
Існуючі залежності між рішеннями прямої і двоїстої задач характеризуються сформульованими нижче лемами і теоремами подвійності.
Лемма 1.1. Якщо X - деякий план вихідної задачі (1) - (3), а В - довільний план двоїстої задачі (4), (5), те значення цільової функції вихідної задачі при плані X завжди не перевершує значення цільової функції двоїстої задачі при плані Y, тобто F(X) F*(Y)
Лемма 1.2. Якщо F(X*) = F*(Y*) для деяких планів X* і Y* задач (1) - (3) і (4), (5), то X* - оптимальний план вихідної задачі, a Y* - оптимальний план двоїстої задачі
Теорема 1. (перша теорема подвійності) Якщо одна з пари двоїстих задач (1) - (3) чи (4), (5) має оптимальний план, то й інша має оптимальний план і значення цільових функцій задачпри їхніх оптимальних планах рівні між собою, тобто .
Якщо ж цільова функція однієї з пари двоїстих задач не обмежена (для вихідної (1) - (3) -зверху, для двоїстої (4), (5) - знизу), то інша задача взагалі не має планів.
Теорема 2. (друга теорема подвійності). План задачі (1) - (3) і план задачі (4), (5) є оптимальними планами цих задач тоді і тільки тоді, коли для будь-якого виконується рівність
Використана література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.:
КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти)
"Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л.Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.36-47.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: "Рута", 1998.-168 с
Loading...

 
 

Цікаве