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

Сентябрь 12, 2022

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

Содержание

2. Аналізу параметричної чуттєвості Післяоптимізаційний аналіз, або аналіз чуттєвості полягає у зв’язуванні впливу структурних, параметричних та структурно-параметричних
3. Рис. 1. Графічна ілюстрація алгоритму визначення меж зміни співвідношення між c1 та c2 у виразі для
4. проходитиме через кутову точку із координатами Це забезпечує максимальне значення показника ефективності. Невизначеність.
5. З фізичної точки зору означає відповідно недоцільність випуску супутників зв’язку, або навігаційних супутників. При зміні співвідношення
6. Зрозуміло, що взагалі зміна будь-якого параметра математичної моделі задачі лінійного програмування (об’єм ресурсів та їх вартість),
7. Для дослідження впливу властивостей задачі лінійного програмування на її оптимальне за вихідною постановкою рішення в загальному
8. Ідея фізичного змісту побудови математичної моделі двоїстої задачі лінійного програмування Було поставлено за мету отримати максимальний
9. Задача лінійного програмування із змінними u1,2,3 формулюється так: якою повинна бути вартість кожного окремого ресурсу для
10. Загальна постановка і правила побудови двоїстої задачі
11. Кожній задачі лінійного програмування можливо поставити у відповідність задачу, яку називають двоїстою до неї. Припустимо, що
12. Задача двоїста до основної задачі – будується за наступними правилами: 1. Виконується впорядкування вихідної задачі до
13. 4. Матриця коефіцієнтів двоїстої задачі може бути отримана транспонуванням матриці A= ||ai,j||m×n, складеної із коефіцієнтів при
14. Пряму і двоїсту задачі лінійного програмування можливо записати у вигляді: Пряма та двоїста задача. Розглянемо двоїсту
15. Після перетворення, можемо записати: Висновок: 1) Двоїста задача лінійного програмування до двоїстої задачі лінійного програмування є
16. Приклад 1. Необхідно побудувати двоїсту задачу лінійного програмування. Приведемо задану задачу лінійного програмування до вигляду (1).
18. Двоїста ЗЛП набуває вигляду:
19. Побудувати двоїсту задачу. Приклад 2. Приведемо пряму задачу до стандартного вигляду.
20. Двоїста задача набуває вигляду:
21. Побудувати задачу двоїсту до заданої задачі лінійного програмування. Приклад 3.
22. Основні теореми двоїстості Теорема 1. Зауваження 1. Якщо показник ефективності однієї із задач необмеженний, то інша
23. Наслідок 1.
24. Теорема 2. Зауваження 2. Теорема 2 ще має назву «умова доповняльної нежорсткості» і формально записується у
25. Теорема 3.
26. Покажемо, що при зміненні правих частин bi(i=1,m) обмежень прямої задачі невідомі двоїстої задачі можливо інтерпретувати як
27. 2. Пряма та двоїста відповідно. Вимога, яка полягає в тому, що ΔB → 0 , означає,
29. Скачать презентацию

Слайд 2

Аналізу параметричної чуттєвості
Післяоптимізаційний аналіз, або аналіз чуттєвості полягає у
зв’язуванні впливу структурних,

параметричних та структурно-параметричних змін у математичній моделі (математичній постановці) задачі на отриманий оптимальний розв’язок для тієї постановки задачі лінійного програмування, яка вважається вихідною.
Розглянемо, в якому було з’ясовано, що для отримання максимального прибутку необхідно випустити продукцію типу A (супутники зв’язку) x1= 17*1/7≈ 17 та типу B (навігаційні супутники) x2= 23*4/7≈ 23. Оптимальний розв’язок було отримано за умови, що вартість виробів A та B складає відповідно 40 та 50 умовних одиниць. У зв’язку зі змінами, що відбуваються в світовій економіці, керівнику фірми (особі, що приймає рішення) важливо знати, як вплине зміна вартості продукції A та B (питомий прибуток) на запланований випуск продукції x1,2 (рис. 1).

Слайд 3

Рис. 1. Графічна ілюстрація алгоритму визначення меж зміни співвідношення між c1

та c2 у виразі для обчислення показника ефективності, при яких оптимальний розв’язок (x1, x2) залишається незмінним.

Як бачимо, при умові

оптимальний план випуску продукції не зміниться, тому що «основна пряма»

Слайд 4

проходитиме через кутову точку із координатами
Це забезпечує максимальне значення показника ефективності.
Невизначеність.

Слайд 5

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

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

Оптимальна точка

Слайд 6

Зрозуміло, що взагалі зміна будь-якого параметра математичної моделі задачі лінійного програмування

(об’єм ресурсів та їх вартість), норми витрат ресурсів на виготовлення одиниці продукції впливатиме на оптимальне рішення і значення показника ефективності. Кількісне дослідження цих змін і виконується в процесі аналізу чутливості математичної моделі задачі лінійного програмування. Наведений простий приклад аналізу чутливості оптимального рішення задачі лінійного програмування та значення показника ефективності до зміни параметрів математичної моделі має ілюстративний характер і для використання у багатовимірному випадку (n≥3, де n– кількість змінних) стає громіздким.

Слайд 7

Для дослідження впливу властивостей задачі лінійного програмування на її оптимальне за

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

Слайд 8

Ідея фізичного змісту побудови математичної моделі двоїстої задачі лінійного програмування
Було поставлено

за мету отримати максимальний прибуток
від виробництва виробів A та B, але нічого не було сказано про вартість ресурсу, який використовувався для створення цих виробів, тобто нічого не було сказано про витрати, які необхідно мінімізувати, але таким чином, щоб не зменшити питомий прибуток (собівартість виробленої продукції).
Припустимо, що одиниця ресурсу C, D, E коштує відповідно u1, u2, u3. Тоді вартість виробів можливо обчислити за виразами відповідно:

Слайд 9

Задача лінійного програмування із змінними u1,2,3 формулюється так: якою повинна бути

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

Записана задача лінійного програмування має назву двоїстої по відношенню до задачі прикладу

Слайд 10

Загальна постановка і правила побудови двоїстої задачі

Слайд 11

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

двоїстою до неї. Припустимо, що загальна задача лінійного програмування (вихідна, або, як ще кажуть, пряма задача) задана у вигляді:

Двоїста (спряжена до неї) задача має вигляд:

Слайд 12

Задача двоїста до основної задачі – будується за наступними правилами:
1. Виконується

впорядкування вихідної задачі до виду (2), тобто
якщо цільова функція максимізується, то нерівності-обмеження повинні бути приведені до вигляду «≤», а якщо мінімізується, то до вигляду «≥». Досягти виконання потрібної орієнтації знаку обмежень можливо множенням обох його частин на (−1).
2. Якщо вихідна задача є задачею максимізації, то двоїста буде задачею мінімізації. При цьому вектор, який утворено із коефіцієнтів при невідомих в показнику ефективності вихідної задачі співпадає із вектором констант в правих частинах системи обмежень двоїстої задачі, і, навпаки, коефіцієнти при невідомих в показнику ефективності двоїстої задачі є відповідними правими частинами системи обмежень вихідної задачі.
3. Кожній змінній ui двоїстої задачі відповідає i-те обмеження вихідної задачі і навпаки, кожній змінній xj вихідної задачі відповідає j-те обмеження двоїстої задачі.

Слайд 13

4. Матриця коефіцієнтів двоїстої задачі може бути отримана транспонуванням матриці A=

||ai,j||m×n, складеної із коефіцієнтів при невідомих в системі обмежень вихідної задачі.
Задачі (1) та (2) утворюють симетричну пару взаємно двоїстих задач. Якщо використати позначення:

прямокутна матриця розміром m×n.

вектор-стовпець нулів розмірності k.

Слайд 14

Пряму і двоїсту задачі лінійного програмування можливо записати у вигляді:
Пряма та

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

Розглянемо двоїсту задачу лінійного програмування (2) як вихідну задачу лінійного програмування і, скориставшись правилами переходу до двоїстої задачі, отримаємо пряму задачу лінійного програмування:

Слайд 15

Після перетворення, можемо записати:
Висновок:
1) Двоїста задача лінійного програмування до двоїстої задачі

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

Слайд 16

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

до вигляду (1).

Слайд 17

Слайд 18

Двоїста ЗЛП набуває вигляду:

Слайд 19

Побудувати двоїсту задачу.
Приклад 2.
Приведемо пряму задачу до стандартного вигляду.

Слайд 20

Двоїста задача набуває вигляду:

Слайд 21

Побудувати задачу двоїсту до заданої задачі лінійного програмування.
Приклад 3.

Слайд 22

Основні теореми двоїстості
Теорема 1.
Зауваження 1. Якщо показник ефективності однієї із задач

необмеженний, то інша задача не має розв’язків.

Слайд 23

Наслідок 1.

Слайд 24

Теорема 2.
Зауваження 2. Теорема 2 ще має назву «умова доповняльної нежорсткості»

і формально записується у вигляді:

Слайд 25

Теорема 3.

Слайд 26

Покажемо, що при зміненні правих частин bi(i=1,m) обмежень прямої задачі невідомі

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

де Δbi – приріст i-ої правої частини прямої задачі.
Розглянемо дві двоїсті задачі:
1. Пряма та двоїста відповідно.

Слайд 27

2. Пряма та двоїста відповідно.
Вимога, яка полягає в тому, що ΔB

→ 0 , означає, що заміна B на B + ΔB у двоїстій задачі не призводить до зміни її оптимального розв’язку Uˆ2= Uˆ1. Тоді, відповідно до першої теореми двоїстості, можна записати для 1 і 2 пари задач відповідно:

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

Содержание

Аналізу параметричної чуттєвості Післяоптимізаційний аналіз, або аналіз чуттєвості полягає узв’язуванні впливу структурних,

Рис. 1. Графічна ілюстрація алгоритму визначення меж зміни співвідношення між c1

проходитиме через кутову точку із координатамиЦе забезпечує максимальне значення показника ефективності.Невизначеність.

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

Зрозуміло, що взагалі зміна будь-якого параметра математичної моделі задачі лінійного програмування

Для дослідження впливу властивостей задачі лінійного програмування на її оптимальне за

Ідея фізичного змісту побудови математичної моделі двоїстої задачі лінійного програмування Було поставлено

Задача лінійного програмування із змінними u1,2,3 формулюється так: якою повинна бути

Загальна постановка і правила побудови двоїстої задачі

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

Задача двоїста до основної задачі – будується за наступними правилами:1. Виконується

4. Матриця коефіцієнтів двоїстої задачі може бути отримана транспонуванням матриці A=

Пряму і двоїсту задачі лінійного програмування можливо записати у вигляді:Пряма та

Після перетворення, можемо записати:Висновок:1) Двоїста задача лінійного програмування до двоїстої задачі

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