Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач




Скачати 467.82 Kb.
НазваТеорія двоїстості та аналіз лінійних моделей оптимізаційних задач
Сторінка1/5
Дата конвертації15.10.2013
Розмір467.82 Kb.
ТипДокументы
mir.zavantag.com > Математика > Документы
  1   2   3   4   5
Розділ 4. теорія двоїстості та аналіз лінійних моделей оптимізаційних задач.
4.1. Правила побудови двоїстих задач

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

Двоїста обернена задача – це задача лінійного програмування, сформульована безпосередньо із умов прямої задачі за допомогою певних правил, таким чином, що розв’язок однієї з пари взаємодвоїстих задач одночасно є розв’язком іншої задачі.

Розглянемо узагальнену процедуру формування двоїстої задачі, що є застосовною для довільної форми прямої задачі лінійного програмування. Так як основним методом розв’язку задач лінійного програмування є симплексний метод, то формулювання двоїстої задачі вимагає зведення прямої задачі до стандартного виду.

Вважають, що задача лінійного програмування подана у стандартному вигляді, якщо для знаходження максимального значення цільової функції система обмежень задачі містить лише нерівності виду «», а для задачі на визначення мінімального значення цільової функції — до виду «».

Наприклад, маємо пряму задачу лінійного програмування у стандартній формі:

(4.1)
Для побудови двоїстої задачі виконують симетричні структурні перетворення умов прямої задачі за наступними правилами:

1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.

2. Кожній змінній прямої задачі відповідає обмеження двоїстої задачі, причому кількість обмежень двоїстої задачі дорівнює кількості невідомих прямої задачі.

3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі — на визначення найменшого значення (min), і навпаки.

4. Коефіцієнтами при змінних у цільовій функції двоїстої задачі є вільні члени системи обмежень прямої задачі.

5. Матриця

,

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



утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків — рядками.

6. Правими частинами системи обмежень двоїстої задачі є коефіцієнти при змінних у цільовій функції прямої задачі.

7. Ситему обмежень двоїстої задачі записують у вигляді нерівностей, що за змістом протилежні нерівностям системи обмежень прямої задачі.

8. Якщо змінна прямої задачі додатня (xi ≥ 0), то і–те обмеження двоїстої задачі є нерівністю, якщо xi - будь-яке число, то і-те обмеження двоїстої задачі буде рівнянням.

9. Якщо j–те обмеження прямої задачі є нерівністю, то відповідна змінна уj ≥ 0, якщо j–те обмеження прямої задачі є рівнянням, то змінна двоїстої задачі уj – будь-яке число.

З урахуванням вищезазначених правил двоїстою задачею лінійного програмування до задачі (4.1) буде задача виду:

(4.2)

Задача (4.2) є двоїстою, оберненою або спряженою до задачі (4.1) яку називають прямою, основною, або початковою. Поняття двоїстості є взаємним. По суті мова йде про одну і ту ж задачу, але з різних поглядів. Тому будь-яку них можна вважати прямою, а іншу — двоїстою, симетричність двох спряжених задач очевидна. Як у прямій, так і у двоїстій задачі використовують один набір початкових даних. Крім того, вектор обмежень початкової задачі є вектором коефіцієнтів цільової функції двоїстої задачі і навпаки, а рядки матриці А (матриці коефіцієнтів при змінних в обмеженнях прямої задачі) стають стовпцями матриці коефіцієнтів при змінних в обмеженнях двоїстої задачі. Кожному обмеженню початкової задачі відповідає змінна двоїстої і навпаки.

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

У симетричних задачах обмеження прямої та двоїстої задач є лише нерівностями, а змінні обох задач можуть набувати лише невід’ємних значень.

^ У несиметричних задачах деякі обмеження прямої задачі можуть бути рівняннями, а двоїстої — лише нерівностями. У цьому разі відповідні рівнянням змінні двоїстої задачі можуть набувати будь-яких значень, не обмежених знаком.

Всі можливі форми прямих задач лінійного програмування та відповідні їм моделі двоїстих задач у матричній формі наведено нижче.

Пряма задача

Двоїста задача

^

Cиметричні задачі


max F = CX

AX B

X 0

min Z = BY

ATY C

Y 0

Пряма задача

Двоїста задача


min F = CX

AX B

X 0

max Z = BY

ATY C

Y 0
  1   2   3   4   5

Схожі:

Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconЗадача визначення оптимального плану виробництва
Основним завдання математичного програмування, як наукової дисципліни є розробка математичних методів розв’язку І побудова моделей...
Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconТема: Розв’язування систем лінійних рівнянь
Проте у тому випадку, коли система лінійних рівнянь невироджена, тобто її визначник відмінний від нуля, використовують матричний...
Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconЗатверджено
Методи розв’язування задач з багатьма цільовими функціями, їх порівняльний аналіз
Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconТема 1 Сутність, функції та види грошей
Вивчення сутності грошей, функцій, що виконують гроші, аналіз їхнього розвитку та, впливу грошей І грошової політики на стан економіки...
Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач icon3 Опис лінійних дискретних систем у частотній області
Такий спосіб зображення лінійних систем знайшов досить широке застосування при їх аналізі І синтезі. Зауважимо, що далі в цьому підрозділі...
Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconЛекція №2 «математичне моделювання як метод наукового пізнання економічних явищ І процесів»
Та апостеріорної інформації. Статистична база економетричних моделей. Змінні та рівняння в економетричних моделях. Макро- І мікроекономічні...
Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconЛекція №3 «загальна лінійна економетрична модель»
Поняття коефіцієнтів, їх визначення й застосування в економетричному аналізі. Побудова моделей на сонові покрокової регресії. Найпростіші...
Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconПрактическая работа : Изготовление моделей: кухонная лопатка, разделочная доска «бабочка»
Ознакомление с содержанием образовательной программы и учебно-тематическим планом на учебный год. Демонстрация моделей, выполненных...
Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconРозділ I ii. Елементи математичної статистики
Ці дані носять не абсолютний, а ймовірнісний характер, тому їх аналіз вимагає широкого використання методів теорії ймовірностей....
Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач icon18. Этапы подготовки и решения задач на компьютере
Компьютер предназначен для решения разнообразных задач: научно-технических, инженерных, разработки системного программного обеспечения,...
Додайте кнопку на своєму сайті:
Школьные материалы


База даних захищена авторським правом © 2013
звернутися до адміністрації
mir.zavantag.com
Головна сторінка