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

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

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

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


Реферат на тему:
Теорія двоїстості та двоїсті оцінки в аналізі розв'язків лінійних оптимізаційних моделей.
План.
1. Геометрична інтерпретація двоїстих задач.
2. Приклади розв'язування пари двоїстих задач.
3. Література
Геометрична інтерпретація двоїстих задач.
Якщо число перемінних у прямій і двоїстої задачах, що утворять дану пару, дорівнює двом, то, використовуючи геометричну інтерпретацію задачі лінійного програмування, можна легко знайти рішення даної пари задач, при цьому має місце один з наступних трьох взаємно виключаючих один одного випадків: 1) обидві задачі мають плани; 2) плани має тільки одна задача; 3) для кожної задачі двоїстої пари більшість планів порожньо
1. Для задачі, що складає у визначенні максимального значення функції F = 2x1+7x2 при умовах
- 2 x1 + 3x2 14,
x1 + x2 8,
x1, x2 0,
скласти двоїсту задачу і знайти розв'язок обох задач.
Розв'язок. Двоїстою задачею стосовно вихідної є задача, що складається у визначенні мінімального значення функції F*=14y1 + 8y2 при умовах
- 2y1 + y2 2
3y1 + y2 7,
y1, y2 0.
Як у вихідної, так і в двоїстій задачі число невідомих дорівнює двом. Отже, їхнє рішення можна знайти, використовуючи геометричну інтерпретацію задачі лінійного програмування (мал. 1. і 2.)
Як видно з мал. 1., максимальне значення цільова функція вихідної задачі приймає в крапці В Отже, Х* = (2; 6) є оптимальним планом, при якому Fmax= 46.
Мінімальне значення цільова функція двоїстої задачі приймає в точці Е (мал. 4.). Виходить, Y* = (1; 4) є оптимальним планом двоїстої задачі, при якому Fmin=46 Таким чином, значення цільових функцій вихідної і двоїстої задач при їхніх оптимальних планах рівні між собою.
мал. 1 мал. 2
З мал. 1. видно, що при всякому плані вихідної задачі значення цільової функції не більше 46.
Одночасно, як видно з мал. 2., значення цільової функції двоїстої задачі при будь-якому її плані не менше 46. Таким чином, при будь-якому плані вихідної задачі значення цільової функції не перевершує значення цільової функції двоїстої задачі при її довільному плані.
2. Знайти розв'язок двоїстої пари задач.
Вихідна задача:
- 4x1 + 2x2 4,
x1 + x2 6,
x1, x2 0.
Двоїчна задача:
- 4y1 + y2 -2,
2y1 + y2 -3,
y1, y2 0.
Розв'язок. Як вихідна, так і двоїста задача містять по дві змінні. Тому їхнє рішення знаходимо, використовуючи геометричну інтерпретацію задачі лінійного програмування (мал. 3. і 4.). З мал. 3. видно, що вихідна задача не має оптимального плану через необмеженість знизу її цільової функції на безлічі припустимих рішень.
З мал. 4. випливає, що двоїста задача не має планів, оскільки багатокутник рішень її порожній. Це означає, що якщо вихідна задача двоїстої пари не має оптимального плану через необмеженість на безлічі припустимих рішень її цільової функції, то двоїста задача також не має планів.
Знаходження розв'язку двоїстих задач. Розглянемо пари двоїстих задач - основну задачу лінійного програмування (1) - (3) і двоїсту до неї задачу (4), (5).
Припустимо, що за допомогою симплексного методу знайдений оптимальний план X* задачі (1) - (3) і цей план визначається базисом, утвореним векторами Рi1, Рi2,…,Pim.
Позначимо через С6=(ci1,ci2,…,cim) вектор-рядок, складений з коефіцієнтів при невідомих у цільовій функції (1) задачі (1) - (3), а через Р-1- матрицю, зворотню матриці Р, складеної з компонентів векторів Рi1, Рi2,...,Рim базисa. Тоді має місце наступне твердження.
Теорема 3. Якщо основна задача лінійного програмування має оптимальний план X*, тo Y* = С6Р-1 є оптимальним планом двоїстої задачі.
Таким чином, якщо знайти симплексним методом оптимальний план задачі (1) - (3), то, використовуючи останню симплекс-таблицю, можна визначити С6 і Р-1 і за допомогою співвідношення Y*=С6Р-1 знайти оптимальний план двоїстої задачі (4), (5).
У тому випадку, коли серед векторів Р1, P2,…,Рn, складених з коефіцієнтів при невідомих у системі рівнянь (2), є m одиничних, зазначену матрицю Р-1 утворять числа перших m рядків останньої симплекс-таблиці, які містяться у стовпцях даних векторів Тоді немає необхідності визначати оптимальний план двоїстої задачі множенням C6 на Р-1, оскільки компоненти цього плану збігаються з відповідними елементами (m+1)-й рядка стовпців одиничних векторів, якщо даний коефіцієнт cj=0, і дорівнюють сумі відповідного елемента цього рядка і cj якщо cj 0.
Сказане вище має місце і для симетричної пари двоїстих задач. Оскількищо система обмежень вихідної задачі містить нерівності виду " ", то компоненти оптимального плану двоїстої задачі збігаються з відповідними числами (m+1)-й рядка останньої симплекс-таблиці розв'язки вихідної задачі. Зазначені числа стоять у стовпцях векторів, що відповідають додатковим змінним.
3. Для задачі, що складає у визначенні максимального значення функції F=x1 + 2x2-x2 при умовах
-x1 + 4x2 - 2x3 12,
x1 + x2 + 2x3 17,
2x1 - x2 + 2x3 = 4,
x1, x2, x3 0.
скласти двоїсту задачу і знайти її розв'язок.
Розв'язок. Двоїста задача стосовно вихідної складається в перебуває в знаходженні мінімуму функції F*= 12y1 + 17y2 + 4y3 при умовах:
- y1 + y2 + 2y3 1,
4y1 + y2 - y3 2,
- 2y1 + 2y2 + 2y3 - 1,
y1, y2 0.
Щоб знайти розв'язок двоїстої задачі, спочатку знаходимо розв'язок вихідної задачі методом штучного базису. Приклад наведено в табл 1.
З останньої симплекс таблиці видно, що двоїста задача має розв'язок
Оптимальні двоїсті оцінки задовільняють усім умови двоїстої задачі . При цьому мінімальне значення цільової функції двоїстої задачі, рівне 12·(5/7)+17·0+4·(6/7)=12, збігається з максимальним значенням цільової функції Fmax вихідної задачі.
I
Базис
C6
P0 1 1 -1 0 0 -M
P1 P2 P3 P4 P5 P6
1
2
3
4
5
1
2
3
4
1
2
3
4 P4
P5
P6
P4
P5
P1
P2
P5
P1 0
0
-M
0
0
1
2
0
1
12
17
4
0
-4
14
15
2
2
4
9
4
12 -1
1
2
-1
-2
0
0
1
0
0
0
1
0 4
1
-1
-2
1
7/2
3/2
-1/2
-5/2
1
0
0
0 -2
2
2
1
-2
-1
1
1
2
-2/7
13/7
6/7
9/7 1
0
0
0
0
1
0
0
0
2/7
-3/7
1/7
5/7 0
1
0
0
0
0
1
0
0
0
1
0
0 0
0
1
0
0
1/2
-1/2
1/2
1/2
1/7
-5/7
4/7
6/7
Використана література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.:
КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф таін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти)
"Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л.Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.36-47.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: "Рута", 1998.-168 с
Loading...

 
 

Цікаве