Архів якісних рефератів

Знайти реферат за назвою:         Розширений пошук

Меню сайту

Головна сторінка » Математика

Відповіді на питання з предмету "Методи прийняття управлінських рішень" (шпора)

1. Загальні поняття. Класифікація методів управління. Основні поняття математичного моделювання соціально-економічних систем. Класифікація економіко-математичних методів і моделей.

2. Управлінські рішення: природа процесу прийняття рішення, підходи до прийняття управлінських рішень, виробка та реалізація рішень. Управлінські рішення: методи обґрунтування рішень.

3. Постановки та розв'язок транспортної задачі закритого та відкритого типу з різними обмеженнями на пропускну здатність.

4. Приклади задач, які зводяться до звичайної транспортної задачі.

5. Постановка та розв'язання транспортної задачі за критерієм часу. Транспортні задачі з кількома критеріями та їх розв'язання.

6. Розподільні задачі та їх класифікація. Постановка та розв'язання задач щодо призначення на максимум та на мінімум угорським методом та методом потенціалів.

7. Узагальнена задача щодо призначення закритого та відкритого типу з

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

8. Розв'язання задач ЛП табличним симплекс-методом та двоїстим

симплекс-методом.

9. Теорія двоїстості. Математичні моделі, економічний зміст двоїстих задач.

Економічний аналіз оптимальних планів двоїстих задач. Статус ресурсів. Рентабельність видів продукції.

10. Постановка задачі лінійного цілочислового програмування та її
розв'язання геометричним способом, методом Гоморі та методом гілок і
меж.

11. Постановка задач: про розкрій матеріалу, про ранець, про перевезення
неподільного вантажу, задача комівояжера.

12. Задача комівояжера, її математична постановка. Розв'язання задачі
комівояжера методом редукції рядків та колонок.

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

14. Методи кількісної оцінки якісних показників (методи експертних оцінок): загальні поняття, узгодженість думок експертів, класифікація експертних методів.

15. Методи експертних оцінок: парного та повного парного порівняння. їх

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


 

16. Методи Дельфі та анкетування. Творче мислення і неформальні методи

рішень.

17. Елементи теорії матричних ігор. Верхня та нижня ціни гри, сідлова точка,
значення гри. Рішення ігор у мішаних стратегіях. Формули розв'язання
матричної гри 2x2 у мішаних стратегіях. Геометрична інтерпретація
матричної гри 2x2 у мішаних стратегіях. Розв'язання задач 2хn та mх2.
Домінуючі стратегії.

18. Приведення матричної гри до задачі лінійного програмування та її
розв'язання. Загальні висновки розв'язання задач теорії ігор.

19. Прийняття рішень в умовах визначеності, ризику та невизначеності.
Основні критерії теорії статистичних рішень.

20. Ризик, основні поняття, міри ризику. Багатоетапні рішення, дерево
рішень. Ігри з ненульовою сумою, позиційні ігри.

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

22. Задачі багатокритеріальної оптимізації: постановка, область компромісів,
основні проблеми, основні методи розв'язку.

23. Багатокритеріальний вибір, основні проблеми, види згорток, аналіз
альтернатив управлінських рішень за кількома критеріями.

24. Кількісні методи прогнозування: аналіз часових рядів (методи плинного

середнього, експоненціального згладжування, проекціювання тренда); каузальні методи.

25. Якісні методи прогнозування. Основні етапи експертного прогнозування.
Трендові моделі на основі кривих зростання. Метод найменших
квадратів.


 

4.Приклади задач, які зводяться до звичайної ТЗ.

1. Задача, про задоволення потреб найбільш важливих пунктів споживання.

Припустимо маємо m-постачальників та n-споживачів, причьому запаси вантажу менше за потреби на них,т. б. Не всі споживачі будуть задоволені, але ж тереба задовольняти найбільш важливі пункти споживання. де dj – збитки від недостачання одиниці вантажу j-му споживачеві.

де

 

Така задача зводиться до звичайної ТЗ, для цього треба ввести фіктивного (m+1) постачальника Am+1 з запасами am+1:

Обмеження: ; ; ; все записати у фігурних дужках!!! (!!!)

2. ТЗ з ускладненнями.

В реальних умовах можуть бути різні ускладнення при перевезенні вантажу:

1.Від Аi-постачальника Вj-споживачеві взагалі не можна перевозити вантаж. ТЗ розв'язується методом потенціалів. При розв'язку такої задачі треба блокувати клітинку (і,j) великим тарифом М, тоді сюди ніколи вантаж ставитися не буде.

2.Від Аi-постачальника Вj-споживачеві треба перевезти певну фіксовану кілкість вантажу. Тоді треба у відповідну клітинку (і,j) поставити цю кількість вантажу і блокувати її великим тарифом М. Далі при розв'язку вона вважається вільною. ТЗ розв'язується методом потенціалів.

3.Від Аi-постачальника Вj-споживачеві треба перевезти не менше ніж αij кількості вантажу. Тоді треба у Аi-постачальника зменшити кількість запасів на αij,т.б. аі – αij.А у Вj-споживачеві – кількість потреб,т.б. bj – αij. Потім ТЗ розв'язується методом потенціалів і до останього оптимального плану в клітинці (і,j) добавляють значення αij.

4.Від Аi-постачальника Вj-споживачеві треба перевезти не більше αij кількості вантажу. Тоді треба добавити (n+1) стовпець з потребами, які дорівнюють різниці bj – αij, а для j-го стовпчика потреби залишаються рівними αij. В (n+1) стовпчику всі тарифи відповідають тарифам j-го стовпчика, тільки в клітинці з номером (i,n+1) ставиться тариф дуже великий М. Далі задача розв'язується, як звичайна, методом потенціалів. І в кінці після отримання розв'язку значення (n+1) стовпчика добавляється до значення j-го стовпчика.

3. Збільшення продуктивності автотранспорту за рахунок мінімізації порожнього пробігу.

Припустимо маємо m-постачальників, кожному з яких необхідно продати відповідно а1 … аm автотон вантажу і існує n-споживачів у кожного з яких існує відповідно b1 … bn потрібних автотон. Їх треба продати від постачальників до споживачів, що перевезти існуючий вантаж, при чьому мінімізувати пустий пробіг автотон. Припустимо, виконується умова балансу:

Задана матриця С=(l ji) nm, де l ji-відстані від j-го споживача до i-го постачальника. Треба мінімізувати загальні витрати. Вводять змінні y ij-кількість порожніх автогон, що подаються від від j-го споживача i-му постачальнику. Економіко-математична модель має вигляд:

Обмеження:
 
4.Оптимальне закріплення за автоматами операцій по перевірці деталей (вантажу).

Припустимо, мається m-автоматів А1 …Аm різних типів і відомий час перевезення вантажу а1 … аm. Ці автомати можуть виконувати n-операцій В1 …Вn, де b1 …bn – це час роботи кожної операції (виконання). І відома матриця С з елементами (Сij)mn, де Сij – це ефективність при виконанні i-м автоматом j-ї операції.

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

Вводиться цільова функція , де Xij - час виконання i-м автоматом j-ї операції. Обмеження:

 

Задача збалансована: .

 

5.Задача, щодо призначення.

Припустимо, існує m-автоматів та n-робіт.

Припустимо, що кількість митників = кількості робіт (m=n). При чьому відома матриця С: С=(Сij)nn, де Сij – ефективність виконання i-м митником j-ї роботи.

Поставимо матем. Модель данної задачі, для цього вводимо змінні

Xij= 1, якщо i-митник призначен на j-роботу.

0, якщо не призначен.

Будемо припускати, що на кожну роботу призначен 1 працівник і кожен працівник призначен на 1 роботу.

 

6. Задачі розміщення з обліком транспорних та виробничих витрат.

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

, де Ci – собівартість випуску продукції i-го постачальника. Cij'-вартість перевезення 1-ці вантажу від і-го постачальника j-му споживачеві.

Припустимо, потрібно скоротити випуск продукції, для цього зменшимо потреби у споживачів на данну кількість. Далі йде розв'язок задачі. Цю задачю робимо закритого типу. Той постачальник, який буде закріпленним за фіктивним споживачем і повинен зменшити обсяги випуску продукції.

7. Триіндексна ТЗ. Мається m пунктів постачання з напівфабрикатами у кількості аі, і=1,m. Фабрикат треба переробити і отримати продукцію по пунктах Дк, , і отриману продукцію у кількості bj(j=1,n) завести споживачеві Вj (j=1,n). Задані 2 матриці С1=(Сik') mp – вартість перевезення 1-ці вантажу і матриця С2=(Ckj'') pk. Кожен пункт переробляє не більше ніж dk, k=1,p напівфабрикатів. Треба задовольнити постачальників, споживачів, не перевищити можливості пунктів переробки і мінімізувати загальні витрати. Припустимо, що . Вводимо Xikj-кількість вантажу, що перевозяться від і-го постачальника j-му споживачеві, через k-тий пункт переробки. модель: Обмеження: 1) ; 2) ; 3) ; 4)
 
5. Постановка та розв”язання транспортної задачі (ТЗ) за критерієм часу. ТЗ з кількома критеріями та їх розв'язання.

Припустимо, що є m потачальників та n споживачів.

A1…Am – постачальники з запасами вантажу a1…am; B1…Bn – споживачі з потребами b1…bn.

Відомий час перевезення tij (i=1,m; j=1,n). Треба так організувати перевезення вантажу, щоб задовільнити всіх постачальників та споживачів при умові, що Sai=Sbj і час на перевезення вантажу буде мінімальним.

Така постановка ТЗ робиться тоді, коли треба враховувати в першу чергу час перевезення. Наприклад, при перевезенні швидкопсуючого вантажу або при перевезенні людей з зон лиха. В цих задачах загальна вартість перевезення носить другорядний характер. Для розв”язку цієї задачі вводяться змінні Xij – кількість вантажу, що перевозиться, від i-ого постачальника до j-ого споживача.

T(x)=max{tij}®min (T(x)-критерій якості; xij>0)

{Sxij=ai, i=1,m

{Sxij=bj, j=1,n

{xij>=0, i=1,m, j=1,n

Алгоритм розв”язку: Заповнуємо таблицю одним з методів (мін. вартості, подвійної переваги, Фогеля) отримаємо перший опорний план T(X1)=max{tij}=tL1K1.Знаходимо макс. час перевезення для зайнятих клітинок.

Ідея методу базується на розвантажувальних циклах. Позначаємо клітинку l1k1 "-" і створюємо замкнений цикл ("-”, "+", "-”,…). Всі клітинки з "-" повинні бути зайняті, а з "+” – не обов”язково. Найкращий варіант, якщо l1k1 має найменший. час перевезення серед "-" клітинок.

{xij+q (i,j) Îd+

x`ij= { xij-q (i,j) Îd- q=minxij (із d-)

{ xij

Всі вільні клітинки, які мають час перевезення >= tL1K1, викреслюємо, оскліьки вони безперспективні. Після побудови розвантажувального циклу (якщо існує), розвантажуємо клітинку l1k1. Після розвантаження знаходимо макс. значення часу зайнятих клітинок. T(X2)=max{tij}=tL2K2 і знову викреслюємо всі вільні клітинки, де час перевезення більше tL2K2. Так робимо до тих пір, доки можна створювати цикл.

ТЗ в багатокритеріальній постановці. В таких задачах треба знайти оптимальний компромісний розв'язок, який задовольняє кільком критеріям якості. Задачі:

1). F(X) = {T(x), L(X)} – opt; 2) F(X)={T(X), t(x)} – opt; 3) F(X)={L(X), t(x)} – opt;

4). F(X)={L(X), T(X), t(x)} – opt.

Для задачі 2 можна спочатку оптимізувати один з критеріїв, нпр знайти min по критерію загального вантажочасоперевезення методом потенціалів, при цьому для відповідного розв»язку знайти для оптимального плана по першому критерію значення другого. Потім, використовуючи алгоритм розвантажувальних циклів намагатися покращити значення другого критерія. Якщо значення другого критерія зменшиться, а значення 1-го не зміниться, то ми знайшли найкращий зв'язок по двум критеріям, а якщо значення 2-го критерія зменшиться, а 1-го збільшиться, то однозначно млжна сказати який розв'язок найкращий. Тоді використовуємо відносні прирости:


 

6.Розподільні задачі та їх класи-фікація. Постановка і розв'язання задач щодо призначення на максимум та на мінімум угорським методом, методом потенціалів.

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

Класифікація:

1.За критерієм якості: - лінійні, - нелінійні.

2. По потребним ресурсам, що маються в наявності: - збалансовані

- незбалансовані

3. За характером змінення змінної:

- неперервні(приймають довільні значення),

- цілочисельні,

- дискретні(обмежена кількість чисел).

4. За кількістю екстремумів функції:

- одноекстремальні, - багатоекстремальні.

5. За характером розподілу ресурсів:

- з врахуванням часу,

- без врахування часу.

ЗАДАЧА ЩОДО ПРИЗНАЧЕНЯ.

Припустимо, А – робітники, В – роботи. Матриця ефективності C=(Сij)mn, cij- ефективність від призначення і-го працівника на j-ту роботу.

Математична модель: Обмеження: 1)

2) ; 3) ; 4) Xij={0,1}; i=1,m; j=1,n

Це задачі відкритого типу зводяться до закритого. В обмеженнях (1,2) отримуємо «=». Цю задачу, хоч вона належить до бульового програмування, можна розв'язати як транспортну задачу методом потенціалів. Запаси та потреби дорівнюють 1.

Але ж більш ефективний спосіб – алгоритм Угорського методу. Це вибір якихось значень в матриці(у різних клітинах та стовпцях). Треба вибрати n елементів.

Треба вибрати так, щоб максимізувати або мінімізувати суму.

Дві матриці з точки зору Угорського методу називаються еквівалентними, якщо елементи матриці D dij = cij + li + mj/

До елементів довільного ряду може бути + або – одне й те саме значення(при чому воно може бути різне для різних стовпчиків та рядків).

Розв'язок задачі щодо призначення для двох еквівалентних матриць однаковий.

Завжди можна звести задачу на мін до задачі на макс. Мax f = -min –f. Для цього всі елементи матриці С множаться на (-1), а потім удобно перейти до невід'ємних значень матриці. Для цього треба прибавити кожному стовпчику макс значення даного стовпчика ( те ж саме, якщо для попередньої матриці С відняти від найбільшого елемента всі інші значення даного стовпчика, а потім віднімається найменше значення у кожному рядку).

АЛГОРИТМ УГОРСЬКОГО МЕТОДУ СКЛАДАЄТЬСЯ З 4 КРОКІВ :

1. Попередні перетворення для матриці С – одержання нулів.

А) для f на min віднімаємо від всіх елементів кожного рядка найменше значення даного рядка, а потім для кожного стовпчика віднімаємо найменше значення у даному стовпчику.

Б) Для задачі на максимум від максимального значення кожного стовпчику віднімаємо усі елементи даного стовпчика, а потім для отриманої матриці від усіх елементів даного рядка віднімаємо найменше значення у даному рядку. Після перетворень в кожному стовбці і рядку буде хоча б один 0.

2. Пошук оптимального розв'язку. Треба знайти рядок, у якому найменше нулів і відмітити один з нулів даного рядка.Всі інші нулі даного рядка і стовпчика викреслюються. Так робиться для усіх рядків. Потім знаходиться наступний рядок, де найменше нулів. Знову відмічаємо один з нулів, а всі інші нулі даного рядка та стовпчика викреслюємо. І так далі для інших рядків. Якщо кількість відмічених нулів = n, то задача вирішена, якщо менше, то переходимо до пункту 3.

3. Пошук мін. набору рядків та стовпчиків, які мають нулі.

А) Помічаються усі рядки, які не мають ні одного поміченого нуля.

Б).Для відмічених рядків через викреслені нулі відмічаємо стовпчики .

В). Для помічених стовбців через помічені нулі помічаємо рядки.

3.А. та 3.Б. можуть повторюватися циклічно. Після цього викреслюються усі непомічені рядки і усі помічені стовбці. (перевірка : всі нулі попадають під викреслення).

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

Переходимо до пункту 2.

Повторюємо до тих пір, поки кількість відмічених нулів не буде дорівнювати n.


 

7.Узаг. задача щодо призначення закритого та відкритого типу з можливим ускладненнями та її розв'язання методом потенціалів. Задачі щодо призначення у векторній постановці.

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

Аi не ® Bj деякі працівники не можуть працювати на даних роботах.

Аi ® Bj працівник призначається на визначену роботу. Аналогічно ТЗ і розв'язуються як ТЗ. Для цієї задачі ми маємо робітників , які можуть виконувати роботи з однаковою мірою ефективності і ці робітники розташовані в відповідних групах А1.......Аm з відповідною кількістю а1........а m і маємо категорії однакових робіт m- груп n- категорій В1...В n, де bn- кількість робіт. Задана матриця ефективності C= (Cij)mn, де Cij- продуктивність від виконання 1 виду роботи j-категорії.

C= (Cij)mn

å ai=å bj. Для мат.постановки вводимо змінні X=(X ij) mn , X ij - кількість робіт і-ї групи Аі, які виконують роботи j-категорії Bj.

ЦФ: f = ∑∑CijXij®max (min).

∑ Xij= ai, i=1,m.

∑ Xij= bj, j=1,n.

Xij >0, i=1,m; j=1,n, цілі.

Задачі на призначення можуть мати ускладнення ; , xij =0

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

F(X)= {f1(x),…fn(x)}―opt.

f1(x) – extr

F(x) =

fi (x) є [0,1].

 

8.Розвязання задач ЛП табличним симплекс-методом та двоїстим симплекс-методом

Табличний симплекс-метод. За допомогою алгоритма симплекс-методу ми рухаємося в пошуку оптимального плану цілоспрямовано, на кожному кроці покращуючи значення цільової фун-ції. f(A)<f(B)<f(C) знаходимо макс.

В

А / \ С Канонічна форма задачі ЛП :

Опорний розв”язок x0 ={b1'; bn';0...0} bj>=0; i=1..m

| | Базисні вектори А1= 1,0,0...0 (записать вертикально), Аm 0..0,1(записать вертикально)-базисні зм

Послідовність симплекс-методу:

1)Знаходиться 1-й опорний план в конан.формі.

2)За допомогою Жорданових перетворень отримується симплекс-таблиця.

3)Перевіряється умова закінчення.

i

базис

C базис

A0(с чертой)

bi

C1

С2

.

Cl

.

Cm

Cm+1

.

Cj

.

Ck

.

Cn

A1

А2

.

Al

.

Am

Am+1

.

Aj

.

Ak

.

An

1

A1

C1

X1

1

0

.

0

.

0

X1,m+1

.

X1j

.

X1k

.

X1n

2

A2

C2

X2

0

1

.

0

.

0

X2,m+1

.

X2j

.

X2k

.

X2n

.

.

.

.

.

.

.

.

 

.

.

.

.

.

.

.

.

l

Al

cl

xl

0

0

.

1

.

0

Xl,m+1

.

xij

.

xik

.

Xln

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

m

Am

Cm

xm

0

0

.

0

.

1

Xm,m+1

.

xmj

.

xmk

.

Xmn

M+1

Zj-Cj

 

z0

0

0

.

0

.

0

Zm+1-cm+1

.

Zj-cj

.

Zh-ch

.

Zn-Cn

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Розглянемо частинні випадки задач ЛП. Якщо в обмеженнях маємо всі відношення : праві частини ві 0, то таку задачу зводимо до канонічного вигляду додаванням невід'ємних змінних по діагоналі. Отримаємо канонічних вигляд і маємо 1-й опорний план.

Якщо маємо мішані обмеження, або перший опорний план знаходиться достатньо складно для задачі ЛП, то використовують метод штучного базису М-метод.

Двоїстий симплекс. Припустимо задача ЛП задана у канонічному вигляді і перші М-векторів одиничні.

, A1X1+..+AmXm+Am+1+Xm+1+..+AnXk=B.

Не всі елементи матриці В є невід'ємними. Псевдо план – це такий план, для якого усі оцінки дельта j 0. Для псевдоплана елементи можуть бути і від'ємні. Симплекс-таблиця будується аналогічно звичайній, але спочатку знаходиться номер напрямного рядка, який відповідає найменшому з від'ємних Ві. А потім номер напрямного стовпчика, який відповідає.

Перетворення робиться до тих пір, поки всі елементи стовпчика будуть невід'ємними.

9. Теорія двоїстості. Математичні моделі, економічний зміст двоїстих задач. Економічний аналіз оптимальних планів двоїстих задач. Статус ресурсів. Рентабельність видів продукції.

Економічний зміст: припустимо задана економіко-математична модель задачі використання ресурсів (1)

{ , i=1,m

j>=0, j= 1,n

Двоїста записується у вигляді: (2)

{ , j=1,n (3)

{ yi>=0, i=1,m (4)

Де yi- це оцінка (ціна) сировини і-го типу . При реалізації сировини, якщо продукція не виготовляється, покупець намагається мінім-ти витрати на її закупівлю. Це відповідає (2) і використовується (3,4) Обмеження відповідає тому, що вартість усіх ресурсів, які йдуть на виготовлення одиниці продукції не менше вартості одиниці цієї продукції .

Y*= Сбаз*Д-1 – оптимальний план другої двоїстої задачі .

Сбаз – дані з останньої симплекс-таблиці, Д-1 – обернена матриця.

Х*= Д-10 Використовують також теорему двоїстості для знаходження оптимальних планів і аналізу ресурсів. Якщо yi*>0 – ресурс дефіцитний і тим цінніший , чим більше у*. yi=0 – недефіцитний.

, .

Екон-ий аналіз проводимо графічно, якщо 2 змінних, а якщо більше – симплекс-методом (аналітично).

10.Постановка задачі ЛЦП та її розв'язання геом способом, Метод Гоморі та методом гілок та меж

Ідея метода Гоморі заключається у відсіканні областей, які не мають цілочислових. Припустимо, задана задача ЛЦП у вигляді

f=Scjxjgmax

Saijxj<=bi

xj>=0

xj-цілі

Спочатку розв'язується задача ЛП, не враховуючи умови цілочисельності, симплекс-методом. Якщо при розв'язанні задачі ЛП отримуємо цілочисловий розв'язок, то одночасно розв'язується і задача ЛЦП. Якщо є дробові значення в оптимальному плані, то робиться відсікання за методом Гоморі.

Припустимо, що остання симплекс-таблиця має такий вигляд

 

Оптимальний план задачі ЛП Х*=(х*1,...,х*м,0,...,0)

Продовжуємо розв'язувати. Причому, якщо існує таке дробове значення bi', що у відповідному і-му рядку симплекс-таблиці всі значення цілі, то задача ЛЦП розв'язку не має. Введемо qij=a'ij-[a'ij] – дробові частини. qi=bi' –[bi']. Вводимо наступне обмеження

 

Множимо обмеження на –1 і додаємо ще одну змінну. Вибираємо перше і-те обмеження, причому таке, яке відповідає найбільшій дробовій частині відповідної і-ї змінної. Далі це обмеження дописуємо до останньої симплекс-таблиці, яка збільшується на 1 рядок і на 1 стовпчик і розв'язується задача ЛП двоїстим симплекс-методом. Робимо Жорданові перетворення до тих пір, доки не отримаємо цілі значення. Відсікання Гоморі можна записати так:

 

, f*- оператор взяття дробової частини.

Методи розвязання задач:

графічний, якщо кількість змінних не перевищює 3-х. При розвязанні задачі ЛЦП з 2-ма змінними, аналогічно, як і для задачі ЛП.

A(x1*,x2*), x1*,x2*- нецілі, розвязок задачі ЛП.

B(x1b,x2b) – точка максимуму ЛЦП.

- метод гілок та меж

Відноситься до комбінаторних методів. ЛЦП, розвязуємо ослаблену задачу ЛП.

xi=xi* - нецілочислове значення, тоді цілочислових значень не буде для [xi*]<xi<[xi*]+1.

Задача ЛЦП розгалуджується на дві підзадачі з додатковими обмеженнями.

Якщо xi обмежене з верху та знизу vi<=xi<=wi, то ці обмеження приймають вигляд vi<xi<=[xi*] і wi>=xi>=[xi*]+1.

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

11. Постановка задач: про розкрій матеріалу, про ранець, про перевезення неподільного вантажу, задача комівояжера.

Існують наступні моделі задачі ЛЦП: 1) Задача щодо призначення, стандартна та узагальнена; 2) задачі щодо розкрою матеріалів; 3) задача про ранець або перевезення неподільного вантажу.

Задача про розкрій матеріалів (задача на мін. відходи). Припускається, що теоретично існує необмежена к-сть якогось мірного матеріалу, з якого виготовляється m типів заготовок і існує n способів розкрою. Позначимо через xj к-сть одиниць матеріалу, які розкроюють за j-м способом. Необхідна к-сть заготовок і-го виду - bi, і=1,..,m. Відходи з одиниці мірного матеріалу при j-му способі розкрою Сj, j=1,..,n. Задані елементи аij, і=1,..,m; j=1,..,n – кількість заготовок j-го типу, що отримуються з одиниці мірного матеріалу за j-м способом розкрою. Економіко-мат. модель має вигляд:

j=1n аij* xj≥ bi, і=1,..,m

xj≥0, j=1,..,n

Z= ∑j=1n cj*xj→min


Задача про ранець. Припустимо в ранець треба вкласти предмети n назв. Деякі предмети якоїсь назви можуть повторюватись. Припустимо задана матриця з елементами аij ,(А= (аij)mn), де аij означає і-ту характеристику предмета j-ї назви. Задані елементи матриці В= (bі)m, де bі - обмеження на і-ту характеристику предмета (довжину, об'єм тощо). Задані елементи матриці С= (сj)n ,де сj – вартість (цінність) предмета j-ї назви. Для формулювання економіко-мат. моделі вводяться змінні xj (Х= (xj) n, к-сть предметів j-ї назви. Мат. модель цієї задачі має вигляд:

Z= ∑j=1n cj*xj→mах

j=1n аij* xj≤ bi, і=1,..,m

xj≥0, цілі, j=1,..,n


 

Задача перевезення неподільного вантажу. Припустимо в деякому Т.З. є m відсіків місткістю b1,..,bn відповідно. Задані елементи аij матриці А, де аij – зайнятість і-го відсіку при перевезенні j-ї одиниці вантажу. Задана матриця С= (сj)n ,де сj – корисність 1-ці j-го неподільного вантажу. Треба так організувати перевезення вантажу, щоб отримати mах корисність рейсу. Для мат. моделі вводяться змінні xj – к-сть одиниць j-го типу вантажу. А економіко-мат. модель має вигляд, аналогічний вищерозглянутому.

Задача Комівояжера. Припустимо існує n міст (пунктів). Комівояжер, який виїжджає з 1-го міста, повинен по разу побувати в кожному місті і повернутися назад найкращим шляхом. Для економіко-мат. моделі вводяться змінні xіj, які можуть приймати значення 0 або 1. 0 – якщо з і-го міста комівояжер не переїжджає в j-те місто, 1 – переїжджає. Задані елементи матриці С= (сіj)mn, і≠j, де сіj – вартість, час або відстань від і-го пункта до j-го. Економіко-мат. модель записується у вигляді:

Z= ∑j=1nі=1n cіj*xіj→mіn

j=1n xіj =1, і=1,..,n

j=1n xіj =1, j=1,..,n

xij={0;1}, і≠ j, і=1,..,n, j=1,..,n


 

Крім того ще записуються обмеження на зв'язність (нерозривність) маршруту, які мають наступний вигляд: ui - uj + n*xіj n -1, де ui та uj означають номери пунктів або міст.

12. Методи розв'язання задач НЛП без та з обмеженнями (класичний м-д, геометричним м-д, м-д підстановки, м-д множників Лагранжа,узагальнений м-д множників Лагранжа)

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

Побудуємо функцію Лагранжа для цієї задачі, вона має вигляд:

Маємо систему n+m рівнянь з n+m невідомими.

Невідомі: , розв'язуємо систему.

Якщо означає прибуток від використання плана x= , а означають запаси ресурсів, то ціна або оцінка і-го ресурсу, яка характеризує змінення прибутку від змінення запасу ресурсів. При розв'язку системи знаходяться критична точка підозріла на екстремум, і додатково з'ясовується чи є ця точка екстремальною, інколи практично беруть інші точки, координати яких задовольняють обмеження (2) і порівнюють значення функції в т.x0 зі значеннями функцій вибраних точок.

Розглянемо функцію 2-х змінних в задачі (1,2) з одним обмеженням:

Будується визначник:

якщо, D>0, то т. =max

D<0, то т. =min

D=0, то т. =?

Метод підстановок та геометричний

Нехай .Область Д, скажімо, обмежена кількома лініями.

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

- знаходимо extr функції на границях;

- вибираємо max(min) значення функції з усіх одержаних.

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

з обмеженнями у вигляді рівностей.

Використаємо метод підстановок. Припустимо m змінних наприклад можна виразити через:

Тоді підставивши у цільову функцію, одержуємо: з кількістю змінних m-n. Розв'язуємо задачу і знаходимо точки

Задачу НЛП можна розв'язати геометрично: 1. Будуємо область визначення (обмежень) Д; 2. Будуємо гіперповерхні рівні 3. знаходимо гіперповерхню найбільшого або найменшого рівня для даної області Д; 4. Знаходимо точку області Д, через яку проходить поверхня max(min) рівня та обчислюємо значення функції в цій точці extr.


 

13.Наближені методи розв'язання задач нелінійного програмування без обмежень та з обмеженнями: метод сканування, метод покоординатного спуску, градієнтні методи, метод найшвидшого спуску, метод Ньютона, інші методи

Метод сканування.

Для знаходження екстремума ф-ї яка роозглядається на деякій області D. Область розв'язків покривається сіткою, і рахується значення ф-ї у вузлових точках.

Метод по координатного спуску.

Z=(x1.x2..xn), x1=x1o. x2=x2o…xn=xno.

Виходимо нв ф-ю однієї змінної. Через похідну знаходимо x11.

X1=(x11.x20 x30..xn0).

Градієнтні методи.

Xk+1=Xk+ Lk.

Xk+1=Xk+- F(Xk).

Xk-попередня точка, Xk+1 - слідуюча, Л-параметр, Lk-вектор натрямку.

М. найшвидшого градієнтного спуску.

Підбирається Л, для якого приріст F має найбільше значення,

F=F(Xk+1)-F(Xk). Xk+1= Xk+ Lk. F—max F(Xk)* F(Xk+1)=0. Ітераційний метод робиться до тих пір доки модуль F(Xk+1)<Є

М. град. спуску з дробленням кроку.

Нехай є функція двох змінних, Z=f(x,y)

1. Xk+1=Xk+- ,

2. Yk+1= Yk+-

Л- фіксоване число. Якщо ф-я покращується, то Л не змінюється. Коли буде погіршення ф-ї- повертаються на 1 крок назад і ділять Л навпіл.

Метод Н'ютона.

Xk+1=Xk+-[ 2F(Xk)]-1 * F(Xk). F(Xk)- градієнт, [ 2F(Xk)]-1 – матриця Гєссе-1.

Існують також метод множників Лагранжа, метод випадкового пошуку.


 

14. Методи кількісної оцінки якісних показників (методи експертних оцінок): загальні поняття, узгодженність думок експертів, класифікація експертних методів.

Якісними оцінками називаються такі оцінки, які не можна фізично виміряти(якість роботи працівника, техніка, артистизм т.д.). Наука, яка займається вимірюванням якісних показників – кваліметрія. Використовується для наступних задач: 1.визначення цілей якоїсь системи або об”єкта; 2. визначення альтернативних варіантів системи(об”єкта); 3.експертний прогноз розв”язку системи; 4.визначення рейтингу спеціалістів фірми, під-ва, країни тощо; 5.сценарії розвитку ситуації; 6.колектиане прийняття управлінського рішення.

Кваліметрія грунтується на 4 положеннях: 1.довільна якість може бути виміряна; 2.якість залежить від ряду властивостей(ознак), які створюють дерево якості; 3.кожна властивість(ознака) характеризується 2 числами: 1)Wi(бал ознаки); 2)Li(вага відповідної ознаки); 4. сума ai º 1

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

Експерт (від лат. expertus - досвідченний). Ним може бути спеціаліст з наступними ознаками: 1.високий рейтинг професіоналізма в даній сфері проведення експертиз; 2.критичне осмислювання сучасність, бачити перспективу, знати і правильно оцінювати, що відбулося раніше; 3.мати психологічну стійкість

Експертиза буває: індивідуальна і колективна.

Методика групової екс-зи включає наступні етапи: 1.відбір експертів для проведення екс-зи; 2.складання плану проведення екс-зи; 3.безпосереднє проведення екс-зи; 4.аналіз результатів.

Щоб оцінити ефективність діяльності експерта використовують абсолютний та відносний коефіцієнт ефективності екс-та.

К-т абс. ефективності – відношення кількості правильно проведенних екс-з до загальної кількості, в яких екс-т приймав участь.

К-т віднос. ефективності – відношення абс. ефективності кожного екс-та до середньої ефективності групи експертів.

Дуже важливий при проведенні експертизи ступінь узгодженності діяльності експертів. Для цього знаходять к-ти рангової кореляції при проведенні парної екс-зи та коеф-т конкордації при проведенні групової екс-зи.

Ранговий к-т кореляції Спірпяна рахується коли об”єктам, які досліджуються, можна поставити у відповідність

A1…….Am

1.r11…...r1m , rij=xj , dj = xj - yj, j=1,m

2.r21…...r2m, r2j=yj

m

rb = 1-[6ådj2]/ m(m2-1), вибірковий к-т

j=1 кореляції Спірмена

-1 <=rb<=1,

Для перевірки значущості к-та кореляції використовується крітерій X2:

1.| rb | менше Tкр Tкр= tкр(a; n=m-2)*Ö(1-rb2)/(m-2) tкр у таб. розп. Ст”юдента

2.| rb | більше Tкр де a-ступінь значущості, a=1-p

n-кількість ступенів вільності.

Якщо виконується 1., то к-т кореляції незначущий, якщо 2.- значущий.

Якщо експертів більше 2, то використовується к-т конкордації:

m

W=[ 12å(Ri-R)2]/ l2(m3-m) , де l-число

i=1 експертів; m-число об”єктів;

1

Ri=årij , i=1,m

j=1

rji – ранг, який дається i-му об”єкту j-м експертом,

m

R – середнє значення = åRi/m, WЄ|0;1|

i=1

Чим ближче до 1, тим більш узгодженні думки експертів.

При проведенні експертизи важливе значення має кіл-ть експертів. Якщо їх дуже мало – гіпертрофується роль кожного.

Існують різні методи оцінки об”єктів:

1.вербальна, числова; 2.шкала, яка відповідає встановленню рангів; 3. коли можна оцінити, на скільки відрізняється оцінка кожного об”єкта; 4.коли можна оцінити, у скільки разів відрізняються оцінки.

15. Методи експертних оцінок: парного та повного парного порівняння. Їх використання для знаходження матриці ефективностей в задачі щодо призначення. Методи Дельфи, анкетування та інш.

М-д парного порівняння:

Кожний експерт заповнює таблицю, в якій порівнює відповідні об”єкти екс-зи, у клітинці ставиться номер того об”єкта, який кращий з т.з. відповідного експерта. 

 

A1

….

Am

A1

X

 

 

….

 

 

 

Am

 

 

X

В м-ді парних порівнянь заповнюється тільки верхня частина, а в м-ді повни парних порівняь – і верхня, і нижня.

М-д повних парних порівнянь використовується коли треба перевірити якість роботи експерта.

Заповнюються стільки таблиць, скільки екс-ів.

Формули оцінки відповідних об”єктів:

l m l

Ci=(åMij) / (å åMij), i=1,m

j=1 i=1 j=1

m-об”єкти, l-експерти

Mij=Wij/I, Wij=fij/(m-1), I=(m(m-1))/2, де

fij – частота переваги i-го об”єкта з т.з. j-го експерта;

Wij – відносна частота i-го об”єкта з т.з. j-го експерта;

Mij - ранг і-го об”єкта з т.з. j-го експерта;

Ci – бал, який дається кожному об”єкту за даним м-ом з т.з. всіх екс-ів.

В м-ді ППП I в 2 рази більше

Wij =fij/2(m-1).

Цю теорію можна використати при проведенні різних екс-з, наприклад: в задачі щодо призначення при знаходженні коеф-ів матриці С=(Сіk), де Сіk – виконання робіт і-м працівником k-ї роботи.

Ці формули змінюються за рах. k

Сіk= åMij(k)/ååMij(k), Mij(k)= Wij (k)/I,

Wij (k)=fij (k)/(m-1), I=m(m-1)/2

М-д Дельфи базується на наступних положеннях:

- Він анонімний.

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

- Керованість процесу(є головний координатор, який управляє процесом екс-зи, може питати деяких екс-тів пояснити, чому вони провели ту чи інш. екс-зу.

- Контроль за проведенням екс-зи(екс-за проводиться до тих пір, доки не будуть отримані більш менш узгодженні думки екс-ів).

М-д анкетування:

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

При проведенні анкетування респондент заповнює анкету, відповідає на питання. Питання бувають відкриті та закриті; безумовні і умовні; непрямі і прямі.

Як правило, анкета починається з простих питань, які повинні цікавити респондента. В середині ставляться найважчі питання. В кінці – демографічні(якщо анкета не анонімна).

Часто отримана інф. використовується в експертних м-ах, імітаційних моделях та оптимізації при прийнятті упр. рішень.


 

16. Елементи теорії матричних ігор. …

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

При грі кожен гравець у відповідній ситуації приймає певне рішення і робить хід – вибирає стратегію.

Оптимальна стратегія – стратегія гравця, яка приносить найбільший середній виграш при великій кількості повторень гри.

Гра з нульовою сумою називається антагоністичною. В даній грі те, що виграє один гравець, програє інший. Сумарний виграш обох = 0. Мета гри – визначити оптимальну стратегію для кожного гравця. Результат гри – виграш чи програш.

Розглянемо парну скінчену гру. Гравцями виступають два партнери, які мають протилежні інтереси. Кожен гравець має обмежену кількість стратегій. 1-й гравець має m-стратегій А1...Аm, 2-й гравець n-стратегій В1...Вn. j1і, Вj) –виграш (програш) 1-го гравця, j2і, Вj) –виграш (програш) 2-го гравця, j1+j2=0

1-й гравець вибирає такі стратегії, щоб максимізувати свій виграш, а 2-й – щоб мінімізувати свій програш. Гра задається матрицею:

, - означає виграш першого гравця, якщо 1-й вибирає і-ту стратегію , а 2-й гравець j-ту. Розглянемо розв'язок гри чистих та мішаних стратегій. Якщо 1-й гравець вибирає якусь і-ту стратегію Аі, то він розуміє, що 2-й гравець на його стратегію найгіршою для першого гравця. Тому, ; a - нижня ціна гри

2-й гравець, обираючи якусь стратегію Вj, розуміє, що перший гравець відповість стратегією Аі , яка буде найгіршою для 2-го гравця. Тому, обираючи обережну стратегію , , j=1,n b - верхня ціна гри.

Ціна гри V знаходиться , a - гарантований виграш для першого гравця, якщо він обирає оптимальну стратегію, b- гарантований програш при оптимальній стратегії. Якщо нижня та верхня ціни гри співпадають, то V=a=b і антагоністична гра розв'язана, а стратегії відповідають оптимальним стратегіям 1-го та 2-го гравця.

Елементи Аіо, Вjо – є ціною гри. Така гра, коли Аіо= Вjо =V, називається грою з сідловою

точкою (якщо при мин. значення в рядку є макс. значенням у стовпчику). Мають місце слідуючі нерівності:

, де А, В – оптимальні стратегії 1-го та 2-го гравців.

Ігриз мішаними стратегіями виникають, коли b>a. Кожен з партнерів вибирає різні стратегії. А1...Аm, - стратегії 1-го гравця, Р1...Рm – ймовірності (відносні частоти), з якими 1-й гравець вибирає свої стратегії, SРі=1. Стратегія, для якої відповідна відносна частота Хі =0 – неактивна.

Аналогічно з т.з. 2-го гравця: В1...Вn,-стратегії, Y1…Yn – ймовірності, SYj=1

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

, j=1,n Аналогічно щодо 2-го гравця: , і=1,m

Скінчена гра в мішаних стратегіях має хоча б один розв'язок.


Розглянемо антогоністичну гру 2-х партнерів розміром 2х2.

B1 B2

A=A1 ( a11 a12 )

A2 ( a21 a22 ) Якщо 2-ий гравець обирає чисту стратегію В1, то ціна гри при виборі першим своїх оптимальних стратегій відповідно дорівнює: а11х1*+а21х2*=V

Аналогічно другу рівність: а12х1*+а22х2*=V , х1*+х2*=1.

Для першого гравця:

а11х1*+а21х2*=V (а11-а12)х1*+(а21-а22)х2*=0

а12х1*+а22х2*=V х1*+х2*=1

х1*+х2*=1

Звідки знаходимо х1*,х2* та V.

Аналогічно розкладається система гри для другого гравця: а11у1*+а12у2*=v,

а21у1*+а22у2*=v,

Можна розв”язати і графічно: у1*+у2*=1.

а12 В2 Р В1 а21 нижня

а11 В1 М границя

V В2 а22 гри

 

0 х2 х1 1

Знаходимо найвищу точку нижньої границі – т. Р, якій відповідають оптимальні мішані стратегії 1-ого гравця (х1*,х2*). Для знаходження оптим. стратегій 2-ого гравця опустимо перпендикуляр на вісь ординат (т. М)

y1*= MB2 y2*= MB1 .

MB2+MB1 MB2+MB1

Якщо підставити замість МВ1, МВ2 – х1*,х2* МВ1=а21-V MB2=V-a22

Для точного знаходження координат т. Р треба скласти рівняння двох прямих ліній, які проходять через дві точки і розв”язати систему. Розглянемо розв”язок антагоністичної гри двох гравців розмірами (2хn) та (mx2).

B1 B2 … Bn

A=A1 ( a11 a12 … a1n )

A2 ( a21 a22 … a2n )

Цю гру зведемо графічно до гри 2х2, знайшовши активні стратегії 2-го гравця. Припускаємо,що гра не має сідлової точки. Знаходимо нижню окаймляючу (рис. аналогічний попередньому тільки n ліній) та верхню її точку. Вона знаходиться на перетині двох активних стратегій, зводимо до 2х2 зі стовпчиками, яким відповідають ці стратегії. Аналогічно розв”язуємо задача розміром mx2. Знаходимо верхню окаймляючу і найнижчу точку, яка знаходиться на перетині двох активних стратегій, зводимо до 2х2 з рядками, яким відповідають ці стратегії.





Реферат на тему: Відповіді на питання з предмету "Методи прийняття управлінських рішень" (шпора)


Схожі реферати



5ka.at.ua © 2010 - 2016. Всі права застережені. При використанні матеріалів активне посилання на сайт обов'язкове.    
.