UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75834
останнє поновлення: 2016-11-29
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваЗв’язок між розв’язками прямої і двоїстої задач. Геометрична інтерпретація двоїстих задач (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1009
Скачало209
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Зв’язок між розв’язками прямої і двоїстої задач. Геометрична

інтерпретація двоїстих задач.

 

Розглянемо кілька двоїстих задач, утворену основною задачею лінійного

програмування і двоїстої до неї.

 

Вихідною задачею є: найти максимум функції

 

(1)

 

при умовах

 

(2)

 

(3)

 

Двоїста задача: знайти мінімум функції

 

(4)

 

при умовах

 

(5)

 

Кожна з задач двоїстої пари (1) — (3) і (4), (5) фактично є самостійною

задачею лінійного програмування і може бути вирішена незалежно одна від

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

однієї з задач тим самим знаходиться рішення й інша задача.

 

Існуючі залежності між рішеннями прямої і двоїстої задач

характеризуються сформульованими нижче лемами і теоремами подвійності.

 

F*(Y)

 

Лемма 1.2. Якщо F(X*) = F*(Y*) для деяких планів X* і Y* задач (1) — (3)

і (4), (5), те X* — оптимальний план вихідної задачі, a Y* — оптимальний

план двоїстої задачі

 

.

 

Якщо ж цільова функція однієї з пари двоїстих задач не обмежена (для

вихідної (1) — (3) —зверху, для двоїстої (4), (5) — знизу), то інша

задача взагалі не має планів.

 

виконується рівність

 

 

Геометрична інтерпретація двоїстих задач. Якщо число перемінних у прямій

і двоїстої задачах, що утворять дану пару, дорівнює двом, то,

використовуючи геометричну інтерпретацію задачі лінійного програмування,

можна легко знайти рішення даної пари задач При цьому має місце один з

наступних трьох взаємно виключають один одного випадків: 1) обидві

задачі мають плани; 2) плани має тільки одна задача; 3) для кожної

задачі двоїстої пари безліч планів порожньо

 

1. Для задачі, що складає у визначенні максимального значення функції F

= 2x1+7x2 при умовах

 

14,

 

8,

 

0,

 

скласти двоїсту задачу і знайти рішення обох задач.

 

Рішення. Двоїстою задачею стосовно вихідного є задача, що складається у

визначенні мінімального значення функції F*=14y1 + 8y2 при умовах

 

2

 

7,

 

0.

 

Як у вихідної, так і в двоїстій задачі число невідомих дорівнює двом.

Отже, їхнє рішення можна знайти, використовуючи геометричну

інтерпретацію задачі лінійного програмування (рис. 1. і 2.)

 

Як видно з мал. 1., максимальне значення цільова функція вихідної задачі

приймає в крапці В Отже, Х* = (2; 6) є оптимальним планом, при якому

Fmax= 46.

 

Мінімальне значення цільова функція двоїстої задачі приймає в крапці Е

(мал. 4.). Виходить, Y* = (1; 4) є оптимальним планом двоїстої задачі,

при якому Fmin=46 Таким чином, значення цільових функцій вихідної і

двоїстої задач при їхніх оптимальних планах рівні між собою.

 

Одночасно, як видно з мал. 2., значення цільової функції двоїстої задачі

при будь-якому її плані не менше 46. Таким чином, при будь-якому плані

вихідної задачі значення цільової функції не перевершує значення

цільової функції двоїстої задачі при її довільному плані.

 

2. Знайти рішення двоїстої пари задач.

 

Вихідна задача:

 

 

6,

 

0.

 

Двоїчна задача:

 

 

-2,

 

-3,

 

0.

 

Рішення. Як вихідна, так і двоїста задача містять по двох перемінні.

Тому їхнє рішення знаходимо, використовуючи геометричну інтерпретацію

-----> Page:

0 [1]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ