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




Назва3. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач
Сторінка1/7
Дата конвертації17.07.2013
Розмір0.77 Mb.
ТипДокументы
skaz.com.ua > Географія > Документы
  1   2   3   4   5   6   7
Тема 3. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач
Зміст

1. Економічна інтерпретація прямої та двоїстої задач лінійного програмування.

2. Правила побудови двоїстих задач.

3. Основні теореми двоїстості та їх економічний зміст.

4. Аналіз лінійних моделей економічних задач.

1. Економічна інтерпретація прямої та двоїстої задач лінійного програмування

Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею.

Економічну інтерпретацію кожної з пари таких задач розглянемо на прикладі виробничої задачі (§ 2.1).

Пряма задача: max F = c1x1 + c2x2 + … + cnxn (3.1)

за умов: (3.2)

. (3.3)

Необхідно визначити, яку кількість продукції кожного j-го виду необхідно виготовляти в процесі виробництва, щоб максимізувати загальну виручку від реалізації продукції підприємства. Причому відомі: наявні обсяги ресурсів — ; норми витрат і-го виду ресурсу на виробництво одиниці j-го виду продукції —, а також — ціни реалізації одиниці j-ої продукції.

Розглянемо тепер цю саму задачу з іншого погляду. Допустимо, що за певних умов доцільно продавати деяку частину чи всі наявні ресурси. Необхідно визначити ціни ресурсів. Кожному ресурсу поставимо у відповідність його оцінку . Умовно вважатимемо, що — ціна одиниці і-го ресурсу.

На виготовлення одиниці j-го виду продукції витрачається згідно з моделлю (3.1)—(3.3) m видів ресурсів у кількості відповідно . Оскільки ціна одиниці і-го виду ресурсу дорівнює , то загальна вартість ресурсів, що витрачаються на виробництво одиниці j-го виду продукції, обчислюється у такий спосіб:

.

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

.

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

.

Отже, в результаті маємо двоїсту задачу:

(3.4)

за умов: (3.5)

(3.6)

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

Зауважимо, що справжній зміст величин — умовні ціни, що виражають рівень «цінності» відповідного ресурсу для даного виробництва. Англійський термін «shadow prices» у літературі перекладають як «оцінка» або «тіньова, неявна ціна». Академік Л. В. Канторович назвав їх об’єктивно обумовленими оцінками відповідного ресурсу.

Задача (3.4)—(3.6) є двоїстою або спряженою до задачі (3.1)—(3.3), яку називають прямою (основною, початковою). Поняття двоїстості є взаємним. По суті мова йде про одну і ту ж задачу, але з різних поглядів. Дійсно, не важко переконатися, що двоїста задача до (3.4)—(3.6) збігається з початковою. Тому кожну з них можна вважати прямою, а іншу — двоїстою. Симетричність двох таких задач очевидна. Як у прямій, так і у двоїстій задачі використовують один набір початкових даних: , ; . Крім того, вектор обмежень початкової задачі стає вектором коефіцієнтів цільової функції двоїстої задачі і навпаки, а рядки матриці А (матриці коефіцієнтів при змінних з обмежень прямої задачі) стають стовпцями матриці коефіцієнтів при змінних в обмеженнях двоїстої задачі. Кожному обмеженню початкової задачі відповідає змінна двоїстої і навпаки.

Початкова постановка задачі та математична модель може мати вигляд як (3.1)—(3.3), так і (3.4)—(3.6). Отже, як правило, кажуть про пару спряжених задач лінійного програмування.

2. Правила побудови двоїстих задач

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

Якщо пряма задача лінійного програмування подана в стандартному вигляді, то двоїста задача утворюється за такими правилами:

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

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

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

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

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

6. Матриця

,

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



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

Процес побудови двоїстої задачі зручно зобразити схематично:



Рис. 3.1. Схема побудови двоїстої задачі до прямої

Пари задач лінійного програмування бувають симетричні та несиметричні.

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

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

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

Пряма задача

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

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


max F = CX

AX  B

 0

min Z = BY

AT C

 0

min F = CX

AX  B

 0

max Z = BY

AT C

 0
  1   2   3   4   5   6   7

Схожі:

3. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconПитання до екзамену з курсу «Аналіз даних»
Обчислювальні проблеми оцінювання нелінійних регресійних моделей І аналіз алгоритмів для однофакторних моделей
3. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconСистеми лінійних рівнянь, визначники
Предметом розгляду лінійної алгебри для економістів є насамперед теорія систем лінійних рівнянь, які в загальному вигляді можна подати...
3. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconЛекція 2 17 лекція 31 тема 4 обґрунтування господарських рішень та оцінювання їх ефективності 49
Вивчення дисципліни передбачає наявність знань з наступних дисциплін: «Теорія ймовірностей та математична статистика», «Теорія статистики»,...
3. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconЛекція №12 Тема: Характеристика І типи облікових задач, що підлягають...
Мета: Ознайомитись з типами облікових задач; оглянути розділи опису постановки задач
3. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconПравила формування контуру моделі Тому що більшість моделей будуються...
...
3. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconРоботи: “ Робота у середовищі програмування Turbo Pascal. Програмування лінійних алгоритмів. ”
Мета роботи: дати навички студентам складати програми лінійних обчислювальних процесів
3. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач icon"Рішення задач моделювання засобами Excel"
Мета роботи: використовуючи засоби Excel, провести графічний аналіз певних екологічних явищ
3. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач icon2. Якщо диполь, що створює електрополе знаходиться в центрі рівностороннього,...
В якості моделей використовують електричні диполі. Електричний диполь – система з двох рівних, але протилежних за значенням зарядів...
3. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconЛекція №13 Тема: Особливості побудови лінійних та розгалужених програм мовою qbasic
Мета: Навчити основним службовим словам та командам мови qbasic для побудови лінійних та розгалужених програм
3. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач iconРозмежувати завдання лінійних керівників І служби персоналу в менеджменті...
...
Додайте кнопку на своєму сайті:
Школьные материалы


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