Search:

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

Реферати » Математика » Зв’язок між розв’язками прямої і двоїстої задач. Геометрична інтерпретація двоїстих задач

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

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

(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) обидві задачі мають плани; 2) плани має тільки одна задача; 3) для кожної задачі двоїстої пари безліч планів порожньо

1. Для задачі, що складає у визначенні максимального значення функції F = 2x1+7x2 при умовах

- 2 x1 + 3x214,

x1 + x2 8,

x1, x20,

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

Рішення. Двоїстою задачею стосовно вихідного є задача, що складається у визначенні мінімального значення функції F*=14y1 + 8y2 при умовах

- 2y1 + y2 2

3y1 + y2 7,

y1, y2 0.

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

Як видно з мал. 1., максимальне значення цільова функція вихідної задачі приймає в крапці В Отже, Х* = (2; 6) є оптимальним планом, при якому Fmax= 46.

Перейти на сторінку номер:
 1  2  3 


Подібні реферати:

Використання програмних засобів навчання та інтернет ресурсів у вивченні початкового курсу математики

ЗМІСТ ВСТУП……………………………………………………………………………3 РОЗДІЛ 1. Теоретичні аспекти використання програмних засобів та мережі Інтернет у початковому курсі математики………………6 1.1 Аналіз існуючих навчальних програм та методів їх використання у початковому курсі математики……………………………………… 6 1.2 Аналіз Інтернет-ресурсів та методів їх використання на уроках математики в початкових класах…………………………………… .9 1.3 Роль програмних засобів у вивченні математики у початковій школі ………………………………………………………………………….11 РОЗДІЛ 2. Методика використання ...

Задачі нелінійного програмування

У задачах лінійного програмування, які розглядалися раніше, всі невідомі входили як до системи обмежень, так і до цільової функції, у першому степені. Тому ці задачі були досить простими у постановці і за методами розв'язування. Зрозуміло, що ряд економічних задач допускають такі ма­тематичні моделі, до яких невідомі або деяка їх частина вхо­дять нелінійно. Наприклад, нехай критерієм оптимальності є собівартість одиниці виробленої продукції. Очевидно, що вона залежить від розміру підприємства. Так, із збільшен­ням ...

Доведення теорем Перрона-Фробеніуса та Маркова для матриць другого порядку

Відомо [[1]-[10]], яку важливу роль відіграють невід’ємні матриці в математичних моделях економіки, біології, теорії ймовірностей тощо. Одними з основоположних фактів теорії цих матриць є теореми Перрона. Перрона-Фробеніуса та Маркова. Доведення цих теорем в загальному випадку потребує застосування теорем з таких неелментарних розділів математики, як теорія екстремумів функції багатьох змінних, жорданова нормальна форма тощо. Мета роботи дати елементарне доведення вищезгаданих теорем Перрона, Перрона-Фробеніуса та Маркова ...