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

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

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

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


Реферат на тему:
Теорія двоїстості та двоїсті оцінки в аналізі розв'язків лінійних оптимізаційних моделей.
План.
1. Розв'язування задач з використанням двоїстого симплекс-методу.
2. Література
Розв'язування задач з використанням двоїстого
симплекс-методу.
1.Знайти максимальне значення функції при умовах
Розв'язання: Запишемо вихідну задачу лінійного програмування в формі основної задачі: знайти максимальне значення функції при умовах
Помножимо друге і третє рівняння системи обмежень на -1 і перейдемо до наступної задачі: найти максимальне значення функції
(1)
при умовах
(2)
(3)
Складемо для останньої задачі двоїсту. Такою є задача, в результаті розв'язання якої потрібно знайти мінімальне значення функції
(4)
при умовах
(5)
(6)
Вибравши в якості базису вектори , складемо симплексну таблицю (табл. 1) для вихідної задачі (1)-(3).
Таблиця 1.
I Базис
1 1 2 0 0
1
2 8 1 1 1 0 0
2
0 -4 -1 1 0 1 0
3
0 -6 -1 -2 0 0 1
4 16 1 1 0 0 0
Із цієї таблиці бачимо , що планом двоїстої задачі (4)-(6) є При цьому плані . Так як в стовбці вектора табл. 1 є два від'ємних числа ((-4) і (-6)), а в 4-му рядку від'ємних чисел немає, то у відповідності з алгоритмом двоїстого симплекс-методу переходимо до нової симплекс таблиці (в даному випадку це можна зробити, так як у рядках векторів і є від'ємні числа. Якщо б їх не було, то задача не мала б розв'язків). Вектор який виключається з базису, визначається найбільшим по абсолютній величині від'ємним числом, що стоїть в стовбці вектора . В даному випадку це число (-6). Отже, з базису виключаємо вектор . Щоб визначити, який вектор необхідно ввести в базис знаходимо ), де Маємо
Значить в базис вводимо вектор . Переходимо до нової симплекс-таблиці (табл. 2).
I базис
1 1 2 0 0
P1 P2 P3 P4 P5
1 P3 2 5
0 1 0
2 P4 0 -7 -3/2 0 0 1
3 P2 1 3
1 0 0
13
0 0 0
Із цієї таблиці бачимо, що отриманий новий план двоїстої задачі Y=(2;0;1/2). При цьому плані значення її лінійної форми рівне Таким чином з допомогою алгоритму двоїстого симплекс-методу проведений упорядкований перехід від плану двоїстої задачі до другого плану. Так як в стовбці вектора табл. 2 є від'ємне число (-7), то розглянемо елементи другого рядка. Серед цих чисел є одне від'ємне (-3/2). Якщо б такого числа не було, то вихідна задача не розв'язувалася б. Вданому випадку переходимо до нової симплекс-таблці (табл. 3).
і базис Cб P 1 1 2 0 0
P1 P2 P3 P4 P5
1 P3 2 8/3 0 0 1 1/3 2/3
2 P1 1 14/3 1 0 0 -2/3 -1/3
3 P2 1 2/3 0 1 0 1/3 -1/3
32/2 0 0 0 1/3 2/3
Яквидно із табл.3 знайдені оптимальні плани вихідної і двоїстої задач. Ними є X*=(14/3;2/3;8/3;0) і Y*=(2;1/3;2/3). При цих планах значення лінійних форм вихідної і двоїстої задач рівні:
2. Знайти максимальне значення функції F=2x1+3x2+5x4 при умовах
Розв'язання: Помноживши перше і третє рівняння системи обмежень задачі на
(-1), в результаті приходимо до задачі знаходження максимального значення функції
F=2x1+3x2+5x5
при умовах
Взявши в якості базису вектори складаємо симплекс-таблицю (табл.4)
Таблиця 4.
і базис Cб P0 2 3 0 5 0
P1 P2 P3 P4 P5
1 P3 0 -12 2 -1 1 0 0
2 P4 5 10 1 2 0 1 0
3 P5 0 -18 -3 2 0 0 1
4 50 3 7 0 0 0
В четвертому рядку табл. 4 не має від'ємних чисел. З цього випливає, що якщо в стовбці вектора Р0 не було від'ємних чисел, то в табл.4 був би записаний оптимальний план. Оскільки у вказаному стовбці від'ємні числа є і вони є наявні в відповідних рядках, переходимо до нової симплекс-таблиці (табл. 4). Для цього виключаємо із базису вектор Р5 і введемо в базис вектор Р1. В результаті отримаємо псевдо-план X=(6;0;-24;43;0)
Таблиця 5.
і базис Сб Р0 2 3 0 5 0
Р1 Р2 Р3 Р4 Р5
1 Р3 0 -24 0 1/3 1 0 2/3
2 Р4 5 4 0 8/3 0 1 1/3
3 Р10 2 6 1 -2/3 0 0 -1/3
4 32 0 9 0 0 2/3
Так як в рядку вектора не має від'ємних чисел, то вихідна задача не має розв'язків.
Використана література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.:
КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти)
"Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л.Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.36-47.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: "Рута", 1998.-168 с
Loading...

 
 

Цікаве