47621

МАТЕМАТИЧНІ МЕТОДИ ДОСЛІДЖЖЕННЯ ОПЕРАЦІЙ. НАВЧАЛЬНИЙ ПОСІБНИК

Книга

Информатика, кибернетика и программирование

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

Украинкский

2013-12-01

831 KB

5 чел.

НАЦІОНАЛЬНИЙ ТРАНСПОРТНИЙ УНІВЕРСІТЕТ

Кафдра інформаційних систем і технологій

Гавриленко В.В., Цуканов І.М.

МАТЕМАТИЧНІ МЕТОДИ ДОСЛІДЖЖЕННЯ ОПЕРАЦІЙ

Навчальний посібник

Київ 2008


Зміст

[1] План курсу

[2] Лекція 1. Вступ. Цілі, критерії, обмеження.

[3] Лекція 2. Лінійне програмування: графічний метод і розробка моделі.

[4] Лекція 3. Транспортна задача.

[5] Лекція 4. Транспортна задача: алгоритм вирішення.

[6] Лекція 5. Симплекс-метод.

[7] Лекція 6. Динамічне програмування.Розподілення капіталовкладень.

[8] Лекція 7. Динамічне програмування. Прокладення траси.

[9] Лекція 8. Сіткове планування та управління (СПУ). Сіткові графіки.

[10] Лекція 9. Сіткове планування та управління (СПУ). Аналіз та оптимізація.

[11] Лекція 10. Управління запасами.

[11.1] N

[11.2] с2 b

[11.3] 2с1

[12] Лекція 11. Складні системи. Класифікація задач прийняття рішень і прийняття рішень в умовах невизначеності.

[13] Питання до курсу

[14] Типи задач.

[15] Література.

[16] W

[17] Час


Анотація 

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

Дисципліна “Методи дослідження операцій в економіці та менеджменті” вивчається студентами економічних спеціальностей. Обсяг курсу становить 22 год. лекцій, 10 год. лабораторних занять, 16 год. практичних занять.

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

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

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


План курсу 

Теми і лекції.

Тема 1.

  1.  Вступ. Цілі, критерії, обмеження.

Тема 2.

  1.  Лінійне програмування: графічний метод і розробка моделі.

Тема 3.

  1.  Транспортна задача.

Транспортна задача: алгоритм вирішення.

Тема 4.

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

Тема 5.

  1.  Динамічне програмування. Розподілення капіталовкладень.

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

Тема 6

  1.  Сіткове планування та управління. Сіткові графіки.

Сіткове планування та управління. Аналіз та оптимізація сіткових графіків.

Тема 7.

  1.  Управління запасами.

Тема 8.

  1.  Класифікація задач прийняття рішень і прийняття рішень в умовах невизначеності. Підсумки.

Лабораторні роботи.

  1.  Транспортна задача (геометричний метод).

Лінійне програмування (Excel).

Динамічне програмування.

Сіткові графіки.

ДП. Задача розподілу про”єму робіт між обладнанням.

Практичні заняття.

  1.  Транспортна задача (розподільчий метод).

Транспортна задача (розподільчий метод).

Геометрична задача лінійного програмування.

Динамічне програмування.

Динамічне програмування (закінчення). Сіткові графіки.

Сіткові графіки (продовження).

Сіткові графіки (закінчення).

Управління запасами.

Тема 1.

Лекція 1. Вступ. Цілі, критерії, обмеження.

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

Керування – це усякий вплив на об'єкт керування, що переслідує досягнення визначених цілей.

Ціль – бажаний стан об'єкта керування.

Планування – визначення цілей керування і засобів досягнення цих цілей.

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

Цілі, критерії, обмеження.

Ціль – це якісна категорія керування, що характеризує загальну спрямованість діяльності.

Засобом формалізації  математичного опису мети є критерії й обмеження.

Критерії й обмеження формуються на базі показників якості керування.

Система характеризується множиною параметрів x1, x2, … xn, алі не усі з цих параметрів можуть вважатися показниками якості.

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

  1.  З ростом xі  якість системи монотонно поліпшується.

З ростом xі  якість системи монотонно погіршується.

З ростом xі  якість системи незмінна.

З ростом xі  якість системи немонотонно змінюється.

До показників якості можна віднести тільки ті параметри, що описані в 1-ом і 2-ом випадках тобто

Показник якості – це кількісна міра якості, пов'язана з якістю системи строго монотонною залежністю. При проектуванні системи сукупність вихідних даних поділяється на:

  1.  сукупність навколишніх розумів (діапазон температур, вологість, тиск і ін.);

сукупність обмежень на структуру і параметри системи – нежорсткі (багатоканальна, лінійна),  жорсткі;

сукупність показників якості;

сукупність обмежень на показники якості.

Система, що задовольняє умовам 1) і 2) називається припустимою.

Система, що задовольняє всім умовам,  називається строго припустимою.

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

Приклад. Розглянемо задачу поліпшення послуг МТС.

Усі крапки від А1 до В1 і від А2 до В2 відповідають припустимим рішенням.

Крапки А1 і А2 відповідають найбільш дешевому обслуговуванню, алі з невисокою якістю обслуговування.

Крапки В1 і В2 відповідають добрій якості, алі більшій вартості.

Від припустимих рішень перейдемо до строго припустимого.

Введемо обмеження на показники якості.

Строго припустимим рішенням відповідають крапки від U1 до W1 і від А2 до U2.

I. Для того, щоб вибрати найкраще рішення виберемо критерієм переваги вартість З=Сmin, а на другий показник якості введемо обмеження t t0. Рішення U1.

II. Критерій переваги t = tmin. На вартість введемо обмеження: З C0. Рішення U2.

Наведені на мал. 1.1 Криві називаються діаграмами обміну.

Мал. 1.1.

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

Оптимізація – надання об'єкту  найкращої, заздалегідь установленої якості.

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

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

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

При рішенні прямої задачі шукають рішення, що гарантує мінімальну вартість при заданій ефективності, тобто  З=Сmin,  Э Эо.

При рішенні оберненої задачі – шукають рішення, що забезпечує максимальну ефективність при заданій вартості, тобто Э=Эmin,  CCo.

Значення дослідження операцій.

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

Під операцією розуміють захід, об'єднаний єдиним задумом і спрямованим на досягнення визначеної мети.

При рішенні конкретної задачі керування застосування методів дослідження операцій припускає:

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

Методами теорії дослідження операцій вирішуються такі задачі:

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

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

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

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

Задачі упорядкування – мається на увазі, що існує деяка кінцева послідовність робіт, виконуваних у визначеному порядку. Для рішення цієї задачі використовуються сітконі методи планування і управління (СПУ).

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

Між змістовною стороною  задач і методами їхнього рішення  немає взаємооднозначної відповідності. Усі методи рішення задач дослідження операцій поділяються на аналітичні і чисельні.

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

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

Основними математичними методами дослідження операцій є методи лінійного, нелінійного і динамічного програмування. Програмування – означає отут планування чи проектування, а не складання програм.

Тема 2.

Лекція 2. Лінійне програмування: графічний метод і розробка моделі.

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

  1.  математичні моделі великої кількості практичних задач лінійні щодо шуканих змінних;
  2.  ці типи задач у даний година найбільш вивчені і для них розроблені стандартні програми їх вирішення на комп'ютерах.

В области электросвязи методами линейного программирования решаются такие задачи:

  1.  отыскание местоположения узла или станции на сети;

распределение емкости существующих АТС между новыми районами застройки;

выбор оптимальных направлений потоков сообщений;

распределение работников по операциям и т.д.

Основна задача лінійного програмування (ОЗЛП).

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

Є ряд змінних х1, х2, … хn. Потрібно знайти такі невід’ємні  значення цих змінних, котрі задовольняють системі рівнянь:

a11x1+a12x2+…+a1nxn = b1;

a21x1+a22x2+…+a2nxn = b2;

. . . . . . . . . . . . . . . . . . . . .

am1x1+am2x2+…+amnxn=bm;(2...1)

і перетворювали в мінімум функцію

W = c1x1+c2x2+…+cnxn,де х1 ≥0;  х2≥0; … хn≥0.

яка називається цільовою функцією задачі.

Припустимим рішенням називається сукупність невід’ємнних х, що задовольняють рівнянням системи.

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

Задачі лінійного програмування вирішуються в два етапи:

  1.  знаходження припустимих рішень;

пошук оптимальних рішень серед припустимих.

Властивості припустимих рішень.

При розгляді властивостей рішень систем лінійних рівнянь виду (2.1) можливі три випадки: m=n, m>n, m<n.

Якщо число рівнянь m дорівнює числу перемінних n, і визначник системи (2.1) не дорівнює 0, то система має єдине рішення. Якщо  всі змінні системи невід’ємнні, те це рішення буде припустимим. Оскільки таке рішення єдине, те воно буде й оптимальним.

У класичних задачах лінійного програмування, як правило, m>n. У таких задачах, якщо система сумісна, те існує нескінченна множина її рішень. При цьому m-n змінним можна надавати довільні значення в рамках обмежень, і такі змінні називаються вільними. Інші m змінних можуть бути виражені через вільні і називаються базисними. Базисні змінні вибираються за допомогою спеціального алгоритму.

Якщо число вільних змінних не більш 2-х, те задачу можна вирішити графічно.

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

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

Розробка моделей лінійного програмування.

Термін «розробка» означає побудову моделей лінійного програмування для практичних задач. Розробка моделі містить у собі три етапи:

  1.  Визначення перемінні задачі.

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

Завдання лінійної цільової функції, що підлягає чи мінімізації максимізації.

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

Для побудови мережі телевізійного віщання на території площею 30 000 тис. кв. км пропонується використовувати телевізійні станції 2-х типів із загальною споживаною потужністю не більш 125 квт. Загальна чисельність штату на всіх станціях не винна перевищувати 24 шт. од.

Параметри станцій наведені в таблиці.

Тип  станції

1

2

Площа, що обслуговується, кв. км.  

500

10 000

Чисельність штату, шт. од.

0,15

8

Споживана потужність, квт

0,63

55

Приведені витрати, тис. грн.

15

200

Задана площа обслуговування враховує деяке взаємне перекриття зон обслуговування.

Потрібно визначити оптимальне число станцій типів 1 і 2 при, якому приведені витрати на всю мережу будуть найменшими.

Рішення.

Шукане число станцій 1 і 2 приймаємо за керовані змінні х1 і х2 відповідно
Х = (х1,х2). Сумарні витрати на мережу W(X) = 15x1 + 200x2.

Оптимізаційна математична модель: знайти невід’ємнні значення зінних х1 і х2,  при яких цільова функція

W(х1,х2) = 15x1 + 200x2   min                  (2.2)

і задовольняють обмеженням:

500 х1 + 10000х2 ≥ 30000

0,15 х1 + 8х2  ≤ 24

0,63 х1 + 55х2  ≤ 125

Задача вирішується методом лінійного програмування (ЛП). Приводимо її до ОЗЛП у такий спосіб:

в усіх нерівностях перенесемо в ліві частини постійні величини і дві останніх нерівності помножимо на –1, помінявши знаки нерівностей:

500 х1 + 10000х2  -  30000 ≥  0

- 0,15 х1 - 8х2  + 24 ≥  0

- 0,63 х1 - 55х2  + 125 ≥  0

введемо нові невід’ємнні  змінні х3, х4, х5:

х3  = 500 х1 + 10000х2  -  30000 ≥  0

х4  = - 0,15 х1 - 8х2  + 24 ≥  0

х5  = - 0,63 х1 - 55х2  + 125 ≥  0                           (2.3)

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

Розглянута задача являє собою класичну задачу лінійного програмування, де загальне число змінних n=5, кількість базисних змінних   m=3, кількість вільних змінних k=n-m=2. Оскільки k=2 , то рішення задачі можна знайти графічно.

Умови невід’ємності змінних обмежують область їхніх припустимих значень першим квадрантом (тобто частиною площини, розташованої над віссю х1 і зправа від осі х2). Інші границі простору не відбиті на площині Х1, Х2. Прямі лінії будуються по рівняннях системи (2.3).

Надамо базисним змінним найменшого можливого значення х345=0 і побудуємо відповідні прямі.

Для рівняння х3=0 відрізки відтинаються прямої на осях координат складуть відповідно:

при х2=0      х1=30000/500=60

при х1=0      х2=30000/10000=3

З одному боку від необмеженої прямої (вправо нагору) значення змінної х3 будуть позитивними, з іншого - негативними.

Нанесемо на малюнок відрізки, що відповідають припустимим (позитивним) значенням змінних. Ту ж процедуру проробимо для рівнянь х4 = 0 і х5 = 0.

Для х4 = 0 при х2 = 0   х1 = 160;      при х1 = 0      х2 = 3.

Для х5 = 0 при х2 = 0   х1 = 198,41; при х1 = 0      х2 = 2,27.

Частина площини, що задовольняє всім обмеженням, називається областю припустимих рішень (ОПР). Шукана область припустимих рішень показана на малюнку. На малюнку ця область заштрихована; її вершини позначені буквами ABCD (Мал.2.1).

Після завершення 1-го етапу рішення (побудови ОПР) необхідно знайти таку крапку цієї області, що забезпечить виконання  умови (2.2), тобто є рішенням задачі. Для цього цільову функцію представимо у вигляді додаткового обмеження:

W - 15x1 - 200x2 ≥ 0.

Зобразимо його прямою W:

W - 15x1 - 200x2 = 0.                 (2.4)

Мінімальне значення W прийме, якщо пряма, що її представляє, торкнеться ОПР у самій лівій її частині - у точці А чотирикутника ABCD. При збільшенні W (2.4) пряма  переміщається вправо. Крапку торкання прямої W (2.4) можна визначити вирішивши систему рівнянь для
х3  = 0 і х5 = 0 з (2.3). У результаті  одержуємо х1  = 20  і  х2 = 2. Звідси випливає, що
W = 700. Координати крапки А (20; 2) і є рішенням задачі. У розглянутому випадку оптимальне рішення – єдине.

При W < 700 пряма W лежить поза ОПР, тобто жодна з її точок не є рішенням.

Мал. 2.1.

Можливі й інші ситуації.

Якби пряма W збіглася з прямою AD,  мі малі б нескінчену множину рішень відповідних крапкам, що лежати на відрізку AD (включаючи крапку А). З іншого боку, деякі задачі можуть і не мати рішення через несумісність обмежень (2.3) – для них відсутня ОПР.

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

Зауважимо, що змінні х1 і х2 реально можуть мати тільки цілочислові рішення. У дійсності припустимі рішення відповідають дискретній множині крапок в ОПР. У подібних випадках точні рішення дають спеціальні методи ЛП.  

Тема 3.

Лекція 3. Транспортна задача.

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

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

Транспортну задачу в загальному вигляді можна сформулювати так:

є n пунктів відправлення А1, А2, … Аm;

є m пунктів призначення 1, 2, … n.....

У пунктах відправлення є деяка кількість однорідного вантажу (потужність постачальника): Q1, Q2, … Qm..... 

Споживи пунктів призначення у вантажі (попит) складають q1, q2, … qn.....

Витрати (коефіцієнт витрат) на перевезення від постачальника  i до споживача j : сij.

Потрібно знайти обсяги перевезень хij  з і в j, таким чином, щоб:

  1.  потужності всіх постачальників були реалізовані;

попит усіх споживачів був задоволений;

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

Цільова функція:

            (3.1)

Шуканий обсяг перевезення від і-го постачальника до j-му споживача хij назвемо постачанням клітки (i, j). Задані потужності постачальників і попити споживачів накладають обмеження на значення  невідомих хij.

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

х11 + х12 + … + х1n = Q1

(3.2)

хm1 + хm2 + … + хmn = Qm

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

х11 + х21 + … + хm1 = q1

(3.3)

х1n + х2n + … + хmn = qn

Очевидно, що обсяг перевезеного вантажу не може бути від’ємним, тому слід додатково ввести обмеження: хij  ≥ 0.

Ця задача може бути вирішена за допомогою симплекс-методу.

Властиві цій задачі специфічні особливості дозволяють отримати рішення більш простим способом шляхом заповнення спеціальної транспортної  таблиці.

А1

c11

х11

c12

х12

c1n

х1n

Q1

возможности

А2

c21

х21

c22

х22

c2n

х2n

Q2

.

.

.

. . . . . . . . . . . . .

.

.

.

Am

cm1

хm1

cm2

хm2

cmn

хmn

Qm

n

1

2

n

Qj

 пункты назначения

qi

q1

q2

qn

 потребности пунктов назначения

Особливості економіко-математичної моделі транспортної задачі:

  1.  система обмежень являє собою систему лінійних рівнянь;
  2.  коефіцієнти при перемінні системи обмежень рівні 1 і 0;
  3.  кожна перемінна входить у систему обмежень два рази:

один раз - у систему рівнянь (3.2), і один раз - у систему рівнянь (3.3).

Лекція 4. Транспортна задача: алгоритм вирішення.

Приклад.

На території міста є три телефонні станції: А, В, С. Є три нових райони забудови, що мають потребу в телефонізації. Незадіяна ємність:

станція А – 5 тис.

станція В – 3 тис.

станція С – 4 тис.

Потреби нових районів у телефонних номерах:

1-й – 3 тис.

2-й – 4 тис.

3-й – 5 тис.

Відома вартість прокладки і будівництва лінійних споруджень від діючих АТС до нових районів.

Потрібно знайти такий розподіл ємності АТС між новими районами, щоб сумарні витрати на прокладку лінійних споруджень були мінімальними.

.

Рішення розбивається на 2 етапи.

1-й етап: здійснюється пошук припустимого рішення (первинного базисного рішення, опорного рішення, опорного плану);

2-й етап: знаходиться оптимальне рішення (якщо воно існує).

1-й етап. Пошук первинного базисного рішення.

Існує два методи знаходження припустимого рішення (первинного базисного рішення).

  1.  Метод «північно-західного кута».

Пошук рішення починається з визначення змінної хА1 лівого стовпця верхнього рядка («північно-західний кут»), якій надається максимально можливе  значення, чи іншими словами, максимально можливе постачання в клітку (А, 1): хА1= min{5тис;3тис}=3тис. Після цього попит 1-го споживача (району) буде цілком задоволений, у результаті чого перший стовпець таблиці постачань випаде з наступного розгляду.  

У таблиці постачань знайдемо новий «північно-західний кут» - клітку (А, 2) і надамо їй максимально можливого значення. З огляду на те, що А-й постачальник (АТС) вже віддав 3тис номерів, то в нього залишилося тільки 2тис=5тис-3тис. Одержуємо
хА2 = min{5тис; 3тис}=2тис. Після цього потужність першого постачальника (АТС) цілком реалізована і з розгляду випадає перший рядок таблиці постачань.

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

А

4

7

6

0

В

12

0

15

11

С

13

0

7

0

10

n

1

2

3

Qj

q

Істотним недоліком методу «північно-західного кута» є те, що він не враховує значень коефіцієнтів витрат.

W = 3т*4 + 2т*7 + 2т*15 + 1т*11 + 4т*10 = 107 т.

  1.  Метод «найменшого елемента» (найменших витрат).

Цей метод є модифікацією методу «північно-західного кута» і дозволяє враховувати витрати (коефіцієнт витрат) на постачання при відшуканні опорного рішення.

Це дає можливість одержати рішення, як правило, більш близьке до оптимального.

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

Розподілимо ємність АТС А між районами з найменшими витратами відповідно до потреб цих районів, починаючи з найменших витрат. Це (А, 1) і (А,3). Повторюємо пошук і заповнення  кліток, що залишилися, аналогічним чином. Одержимо:

А

4

7

0

6

В

12

0

15

0

11

С

13

0

7

10

0

n

1

2

3

Qj

q

W = 3т*4 + 2т*6 + 3т*11 + 4т*7 = 85.

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

2-й етап.  Пошук оптимального  рішення (поліпшення планів перевезень).

Цикл перерахунку.

На другому етапі перевіряється - чи є базисне рішення оптимальним.

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

У транспортній задачі змінна хij ототожнюється з вмістом відповідної клітки (i, j) таблиці постачань. Позначимо bij коефіцієнт біля вільної змінної хij  у виразі для лінійної функції цілі W (3.1) через вільні змінні; bij називається оцінкою вільної клітки (i, j).

При даному базисному розподілі постачань клітка (i, j) - вільна (змінна хij - вільна),   bij - оцінка клітки (i, j)  чи коефіцієнт у виразі лінійної функції W(3.1) через вільні змінні:

W = W0 + bij хij + …          (3.4)

де трикрапкою позначені доданки, що відповідають вільним змінним, відмінним від хij, W0 – сумарні витрати на даний розподіл  постачань.

Тоді з (3.4) випливає, що оцінка bij вільної (i, j) клітки  дорівнює зміні сумарних витрат ΔW на постачання при переведенні в клітку (i, j) одиничного постачання (збільшення змінної хij  від 0 до 1), тобто: bij  = ΔW = Wп – Wн, де Wн - первинні витрати на постачання;
Wп - витрати на постачання після перерозподілу. Передбачається, що у всіх вільних клітках відмінних від клітки (i, j), постачання залишиться нульовим.  Очевидно, що ΔW > 0  якщо
bij > 0; ΔW < 0  якщо bij < 0. Останнє непряме визначення оцінки вільної клітки називають економічним змістом оцінки вільної клітки.

Знайдемо оцінку вільної клітки А3. Для цього дамо в клітку А3 одиничне постачання. При цьому буде потрібно змінити постачання в заповнених  клітках так, щоб зберігся баланс по рядках і стовпцям (передбачається, що у всіх вільних клітках відмінних від клітки А3, постачання залишиться нульовим). Так, щоб 3-й район як і раніше одержав 5 тис. номерів, постачання в клітці  В3 варто зменшити на 1тис. Для того, щоб АТС В як і раніше поставила 3тис. номерів, постачання в клітці В2 збільшуємо на 1тис. 2-му району необхідно тільки 4тис. номерів, тому постачання в клітці А2 варто зменшити на 1тис. З'єднавши один по одному зазначені клітки A3  B3  B2  A2  A3 одержимо замкнутий контур (цикл).

Циклом перерахунку базисної транспортної таблиці називається група кліток цієї таблиці, з'єднаних замкнутою ламаною лінією, що проходить через клітки зі змінюваним постачанням і в кожній клітці робить поворот на +900. Одна з вершин лежить у вільній клітці, інші - у заповнених. Кожен цикл має парне число вершин.

Позначимо знаком «+» ті вершини, у яких постачання (перевезення) збільшуються, а знаком « - » ті, у яких вони зменшуються.

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

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

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

Так, якщо після перерозподілу маємо bij=ΔW з від’ємною оцінкою, то вихідний базовий розподіл – не оптимальний і його можна поліпшити.

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

Якщо ціна дорівнює 0, то вартість постачань по цьому циклу не змінюється при переміщенні.

В отриманій базовій транспортній таблиці необхідно побудувати зазначені цикли перерахунку для усіх вільних кліток. У вихідній вільній клітці розміщаємо одну з вершин і приписуємо «+». Всі інші вершини перерахунку повинні спиратися на зайняті клітки.


А

4

7

6

0

В

12

0

15

11

С

13

0

7

0

10

n

1

2

3

Qj

q

А3: A3  B3  B2  A2  A3 bA3 = 6-11+15-7 = 3

B1: В1  А1  А2  В2  В1 bВ1 = 12-4+7-15 = 0

C1: С1  С3  В3  В2  А2  A1  C1 bС1 = 13-10+11-15+7-4 = 2

C2: С2  В2  В3  C3  C2 bС2 = 7-15+11-10 = -7

Для поліпшення рішення в розглянутій задачі можна виконати єдиний цикл перерахунку з від’ємною ціною bС2:

А

4

7

6

0

В

12

0

15-

11     +

С

13

0

7 +

0

10     -

n

1

2

3

Qj

q

Оптимізація рішення транспортної задачі (оптимізація розподілу постачань).

При переміщенні по циклу k одиниць ресурсу зміна вартості складе ΔW=kbij. При цьому значення ресурсу в клітках зі знаком «+» збільшиться на k, а в клітках зі знаком «-»  - зменшиться на k.

Значення k вибирається серед кліток циклу, що мають знак «-». Крім того, воно має мінімальне значення серед цих кліток, отже k = min{2,4} = 2, тобто це буде клітка B2. Для обнулення постачання в цій клітці по циклу слід передати 2 одиниці ресурсу. Постачання, передане по циклу, визначається як мінімум серед постачань у клітках циклу зі знаком «-». Після цього клітка В3 вважається заповненою, а клітка В2 - вільною. Одержали новий базисний розподіл постачань:

А

4

7   -

6     +

0

В

12

0

15

0

11    

С

13

0

7   +

10   -

n

1

2

3

Qj

q

Зміна витрат на новому розподілі складе ΔW(1) = -7  2 = -14. Загальний обсяг витрат при новому базисному розподілі складе: W(1) = W(0)  + ΔW(1) = 107-14 = 93.

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

A3: bA3 = 6-10+7-7 = - 4  по циклу A3C3C2 А2  A3.

B1: bB1 = 12-4+7-7+10-11 = 7 пo циклу B1A1A2C2C3В3В1.

В2: bB2 = 15-7+10-11 = 7 по циклу B2C2C3B3B2.

C1: bC1 = 13-4+7-7 = 9 по циклу C1A1A2C2C1.

Оскільки є вільні клітки з від’ємною оцінкою (b3 = - 4), то оптимальне рішення ще не знайдене. Для одержання чергового базисного розподілу використовуємо цикл перерахунку по A3. При цьому k = min{2,2} = 2; ΔW(2) = b3 x k(2) = - 4 x 2 = - 8; W(2)= W(1) + ΔW(2) = 93 - 8 = 85.

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

Як видно, при виконанні кожного чергового циклу перерахунку вільна клітка стає заповненою, а одна з заповнених – вільною.


А

4

7

0

6

В

12

0

15

0

11    

С

13

0

7

10

0

n

1

2

3

Qj

q

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

  1.  Для даного  базисного розподілу постачань підбираються потенціали рядків і стовпців таблиці постачань так, щоб коефіцієнти витрат заповнених кліток стали рівні 0.  Складається матриця оцінок.

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

Для обраної вільної клітки будується зазначений цикл перерахунку. Постачання k, передане по циклу, визначається як мінімум серед постачань у клітках зі знаком «-». Знайдене постачання пересувається по циклу. При цьому постачання в клітках зі знаком «+» збільшується на k, а в клітках зі знаком «-» зменшується на k. Клітка, постачання в який при цьому стане рівним 0, буде вважатися вільною, інші клітки циклу – заповненими. Таким чином, отримано базисний розподіл постачань.

Переходимо до п. 1 алгоритму.  

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

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

Тема 4.

Лекція 5. Симплекс-метод.

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

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

Ідея послідовного поліпшення рішення лягла в основу універсального методу рішення задач ЛП - симплекс-методу (симплексного методу). Для реалізації симплексного методу – методу послідовного поліпшення рішення – необхідно задати:

  1.  спосіб визначення первинного припустимого базисного рішення;

правила переходу до кращого (не гіршого) рішення;

критерій перевірки оптимальності знайденого рішення.

Для використання симплекс-методу задача ЛП повинна бути зведена до ОЗЛП. Нехай у задачі ЛП є n змінних і m незалежних рівнянь обмежень. Виберемо  k = n -m змінних у якості вільних. Тоді рівняння обмежень ОЗЛП можна записати в канонічному вигляді:

a11 х1 + a12 х2+ … + a1k хk + b1 = S1

a21 х1 + a22 х2+ … + a2k хk + b2 = S2

(4.1)

am1 х1 + am2 х2+ … + amk хk + bm = Sm

Прирівняємо до 0 усі вільні змінні: х1= 0, х2= 0, ... хk= 0. Тоді значення базисних змінних: S1 = b1, S2 = b2, … Sm = bm представляють первинне базисне рішення, що може бути або припустимим, або неприпустимим.

Рішення буде припустимим, якщо всі змінні (і вільні, і базисні) в отриманому рішенні невід’ємні. Якщо припустиме рішення вдається одержати одразу, то перший етап рішення задачі закінчується.

При переході до другого етапу рішення задачі аналізується значення цільової функції
W =   c1 х1 + c2 х2+ … + ck хk  для початкового базисного рішення. Якщо для даного базисного рішення у виразі для цільової функції W  хоча б один з коефіцієнтів від’ємний
(
ci < 0), то значення цільової функції можна зменшити, якщо відповідну змінну зробити відмінною від 0 (хi ≠ 0).

При цьому вільна змінна xi вважається базисною, а одна з базисних змінних Sj - вільною, тобто вільна і базисна змінні міняються місцями.

У тому випадку, коли у виразі для цільової функції W від’ємні коефіцієнти сi - відсутні, то рішення задачі завершується на першому етапі, тому що отримане базисне рішення є оптимальним.

При виборі базисних (основних) змінних на першому кроці можна скористатися таким правилом:

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

Основний алгоритм симплекса-методу.

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

Крок 1. Використовуючи стандартну (канонічну) форму запису ОЗЛП визначити початкове допустиме базисне рішення, прирівнюючи нулю k вільних змінних.

Крок 2. З числа вільних змінних вибирається змінна, що включається в новий базис, збільшення якої забезпечує поліпшення цільової функції W. Якщо такої змінної немає (ck>0) рішення завершується. В іншому випадку здійснюється перехід до кроку 3.

Крок 3. З числа базисних перемінних S1,.. Sm вибирається виключна змінна, котра повинна прийняти нульове значення (стати вільною змінною).

Крок 4. Знаходиться нове базисне рішення, що відповідає новому складу вільних і базисних змінних. Після виконання кроку 4 алгоритм повторюється, починаючи з кроку 2.

Приклад.

Підприємство виробляє дві моделі продукції. Для виготовлення однієї моделі потрібно 3 одиниці сировини, а для іншої - 4 одиниці. Загальна кількість сировини, що витрачається протягом місяця, не повинне перевищувати 1700 одиниць. Для виготовлення 1-ої моделі потрібно 12 хв., для виготовлення другий - 30 хв. Середня кількість робочих днів у місяці – 20. Тривалість робочого дня – 8 годин. Виріб першого типу приносить 2 г.о. прибутку, другого - 4 г.о. прибутку.

Скільки виробів другої моделі необхідно випускати на місяць, щоб дістати максимальний прибуток.

Складаються рівняння обмежень:

- по затрачуваній сировині:    3 x1 +   4 х2 ≤ 1700;

- по витратах часу: 12 x1 + 30 х2 ≤ 20 х 8 х 60;

  чи    2 x1 +   5 х2 ≤ 1600;

Цільова функція: W =  2 x1 + 5 х2   максимум

чи        W = - 2 x1  - 5 х2   мінімум.

Приведемо задачу до ОЗЛП канонічного виду.

3 x1 + 4 х2 + S1 = 1700

2 x1 + 5 х2 + S2 = 1600

чи

   S1 = 1700 - 3 x1 - 4 х2

   S2 = 1600 - 2 x1 - 5 х2

Крок 1.1. Покладемо x1 = 0; x2 = 0. Тоді S1 = 1700; S2 = 1600. Отримане початкове базисне рішення є припустимим, тому що S1 і S2 > 0.

Проаналізуємо цільову функцію. Для обраного початкового базисного рішення W=0. Оскільки у виразі для цільової функції обидва коефіцієнти при вільних змінних менші нуля
(
x1, x2 < 0), то рішення можна поліпшити, надавши одній із вільних змінних ненульове значення. Не рекомендується змінювати обидві вільні змінні одночасно.

Крок 2.1. Виберемо ту зі змінних, коефіцієнт при якій більше за модулем. Це змінна x2. Тоді, із системи обмежень ОЗЛП для S1 і S2 випливає; що при x1 = 0; x2 = 1700/4 = 425 і
x2 = 1600/5 = 320. З двох значень вибираємо мінімальне:

 x2 = min{425, 320} = 320.

Визначаємо значення цільової функції W для x1 = 0; x2 = 320.

Одержимо W = - 2 x 0 – 4 x 320 = -1280. Крім того, S1 = 420, S2 = 0.

Крок 3.1. З числа базисних змінних вибираємо ту, котра повинна стати вільною. Нехай це буде базисна змінна з найменшим значенням, тобто S2 = 1600. Вихідне рівняння, у якому буде виконуватися ця заміна, називається ведучим рівнянням. Формуємо нову систему рівнянь з нової вільної змінної S2. Нову систему можна сформувати, використовуючи, наприклад, стандартну процедуру виключення по методу Гаусса-Жордана.

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

Новий ведучий рядок = (старий ведучий рядок) : (ведучий елемент).

Ведучий елемент - це коефіцієнт при виключній змінній. Одержуємо:

S2

=

1600

-

2

x1 - x2

5

5

5

Після цього формуємо інші рівняння, включаючи рівняння для цільової функції W. Як видно в новому ведучому рівнянні коефіцієнт при x2 = 1. Користуючись методом виключення, забезпечимо рівність нулю коефіцієнтів при x2 у всіх рівняннях системи, крім ведучого. Одержимо:

      

3

x1

+

4

х2

+

S1

+

0

S2

=

1700

2

x1

+

х2

+

0

S1

+

1

S2

=

320

х (-4)

5

5

7

x1

+

0

х2

+

S1

-

4

S2

=

420

5

5

Крок 4.1.   Нова система рівнянь прийме такий вид:

2

x1

+

х2

+

1

S2

=

320

5

5

7

x1

+

S1

-

4

S2

=

420

5

5

де   x1, S2 - вільні змінні, x2, S1 - базисні змінні.

При x1 = 0 і S2 = 0:  x2 = 320, S1 = 420, тобто є новим базисним рішенням.

З виразу для цільової функції виключимо нові базисні змінні.

-2

x1

-

4

х2

=

W

2

x1

+

х2

+

1

S2

=

320

х (-4)

5

5

-

2

x1

+

4

S2

=

W + 1280

5

5

Отже одержали нове рівняння для цільової функції W. Повертаємося до кроку 2.

Крок 2.2. У виразі для цільової функції W, отриманому на попередньому кроці коефіцієнт при змінній x1від’ємний. Це означає, що якщо зробити змінну x1 базисною, то рішення можна поліпшити. Тому виконуємо наступну ітерацію, тобто приймаємо в якості базисної змінної змінну x1, а в якості вільної, замість x1 - S1. Ведуче рівняння:

x1

+

5

S1

-

4

S2

=

300

7

7

Крок 3.2. Система рівнянь:

x1

+

5

S1

-

4

S2

=

300

7

7

-

5

х2

+

5

S1

-

14

S2

=

- 500

2

7

15

Крок 4.2. При S1, S2 = 0 одержуємо чергове базисне рішення: x1 = 300, x2 = 200. Використовуючи ведуче рівняння, одержуємо цільову функцію у вигляді:

W 

=

2

S1

+

4

S2

- 1400.

7

7

Таким чином, останнє базисне рішення є оптимальним рішенням задачі.

Висновок. Симплекс-метод дозволяє одержати оптимальне рішення задачі за мінімальну кількість кроків.

Завдання. Перевірити отримане рішення графічним методом.

Тема 5.

Лекція 6. Динамічне програмування.Розподілення капіталовкладень. 

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

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

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

Моделі ДП застосовуються при рішенні таких задач:

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

У загальному вигляді задачу ДП можна сформулювати в такому вигляді. Розглядається керований процес. У результаті керування система (об'єкт керування) S переводиться з початкового стану s0  у стан s’. Припустимо, що керування можна розбити на n кроків, тобто рішення приймається послідовно на кожному кроці, а керування, що переводить систему S з початкового стану в кінцевий являє собою сукупність n покрокових управлінь.

Позначимо через Хk керування на k-ому кроці (k=1, 2, ... n). Змінні Хk задовольняють деяким обмеженням, тобто є припустимими. Нехай Х(Х1, Х2, … Хn) – керування, що переводить систему S зі стану s0 у стан s’. Позначимо через sk стан системи після k-го кроку керування. Одержимо послідовність станів s0, s1, … sk-1, sk, …, sn-1, sn = s’...

Показник ефективності розглянутої керованої операції – цільова функція – залежить від початкового стану і керування:  Z = F(s0, X).

Задача покрокової оптимізації (задача ДП) формулюється так: визначити таке припустиме керування Х, що переводить систему S зі стану s0 у стан s’, при якому цільова функція приймає найбільше (найменше) значення.

Модель ДП. має такі особливості:

  1.  Задача оптимізації інтерпретується як n-кроковий процес керування.

Цільова функція дорівнює сумі цільових функцій кожного кроку.

Вибір керування на k-ому кроці залежить тільки від стану системи до цього кроку, не впливає на попередні кроки (немає зворотного зв'язку).

Стан sk після k-го кроку керування залежить тільки від попереднього стану sk-1 і керування Хk (відсутність післядії).

На кожному кроці керування Хk залежить від кінцевого числа керуючих перемінних, а стан sk – від кінцевого числа параметрів.

Замість загальної постановки задачі ДП із фіксованим числом кроків n і початковим станом s0 розглянемо послідовність задач задаючи послідовно n = 1, 2, … при різних  s - однокрокову, двокрокову і т.ін. – використовуючи принцип оптимальності, сформульований Р. Беллманом у 1953 р.

Принцип оптимальності:

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

Уведемо деякі додаткові позначення.

На кожному кроці будь-якого стану системи sk-1 рішення Хk потрібно вибирати з урахуванням того, як цей вибір впливає на наступний стан sk і подальший процес керування, що залежить від sk, тому що це випливає з принципу оптимальності.

Однак є крок, останній, котрий  можна планувати оптимально для будь-якого стану sn-1 , виходячи тільки з міркувань цього кроку.

Розглянемо n-й крок:  sn-1- стан системи до початку  n - го кроку,  sn = s’ - кінцевий стан,  Хn - керування на  n -му кроці,  fn(sn-1, Хn)- цільова функція (виграш)  n - го кроку.

Відповідно до принципу оптимальності, Хn потрібно вибирати так, щоб для будь-яких станів sn-1 одержати максимум (мінімум) цільової функції на цьому кроці.

Позначимо через Z*n (sn-1) максимум цільової функції - показника ефективності  n-го кроку за умови, що до початку останнього кроку система S була в довільному стані  sn-1, а на останньому кроці керування було оптимальним.

Z*n (sn-1) називається умовним максимумом цільової функції на n-му кроці. Очевидно, що

Z*n (sn-1) = max fn(sn-1, Хn)             (5.1)

n}

Максимізація ведеться по всіх припустимих керуваннях Хn.

Рішення Хn, при якому досягається Z*n (sn-1), також залежить від sn-1 і називається умовним оптимальним керуванням на n-му кроці. Воно позначається через  Х*n (sn-1).

Вирішивши одномірну задачу локальної оптимізації по рівнянню (5.1), знайдемо для всіх можливих станів sn-1 дві функції: Z*n (sn-1) і Х*n (sn-1).

Розглянемо тепер двокрокову задачу: приєднаємо до n-го кроку  (n-1)-й.

Для будь-яких станів sn-2, довільних керувань Хn-1 і оптимальному керуванні на  n-му кроці значення цільової функції на двох останніх кроках дорівнює:

fn-1(sn-2, Хn-1) + Z*n (sn-1)              (5.2)

Відповідно до принципу оптимальності для будь-яких sn-2 рішення потрібно вибирати так, щоб воно разом з оптимальним керуванням на останньому (n-му) кроці приводило б до максимуму цільової функції на двох останніх кроках. Отже, потрібно знайти максимум виразу (5.2) по всіх припустимих керуваннях Хn-1. Максимум цієї суми залежить від sn-2, позначається через Z*n-1 (sn-2) і називається умовним максимумом цільової функції при оптимальному керуванні на двох останніх кроках. Відповідне керування Хn-1 на (n-1)-му кроці позначається через Х*n-1 (sn-2) і називається умовним оптимальним керуванням на (n-1)-му кроці.

Z*n-1 (sn-2) = max {fn-1 (sn-2, Хn-1) + Z*n (sn-1)}         (5.3)

{Хn-1}

У результаті максимізації тільки за однією змінною відповідно до рівняння (5.3) знову виходять дві функції: Z*n-1 (sn-2) і Х*n-1 (sn-2).

Далі розглядається трикрокова задача: до двох останніх кроків приєднується
(n - 2)-й і т.д.

Позначимо через Z*k (sk-1) умовний максимум цільової функції, отриманої при оптимальному керуванні на  n-k+1 кроках, починаючи з к-го до кінця, за умови, що до початку к-го кроку система знаходився в стані sk-1. Фактично ця функція дорівнює

n

Z*k (sk-1) = max      fi (si-1, Хi)

{(xk,…xn)} i=k

Тоді

n

Z*k+1 (sk) =    max       fi (si-1, Хi)

{(xk+1,…xn)}   i=k+1

 

Мал. 5.1.

Цільова функція на n-k останніх кроках при довільному керуванні Хk на  k-му кроці й оптимальному керуванні на наступних n-k кроках дорівнює

fk(sk-1, Хk) + Z*k+1 (sk)

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

Z*k (sk-1) = max {fk (sk-1, Хk) + Z*k+1 (sk)}         (5.4)

{Хk}

k = n-1, n-2, … 2, 1.

Рівняння (5.4) називається рівнянням Беллмана.

Керування Хk на  k-м кроці, при якому досягається максимум у (5.4), позначається через Х*k (sk-1) і називається умовним оптимальним керуванням на k -му кроці.

Якщо з (5.1) знайти Zn*(sn-1), то при k = n-1 з (5.4) можна визначити вираз для
Zn-1*(sn-2) і відповідні Х*n-1 (sn-2) вирішивши задачу максимізації для всіх можливих значень sn-2. Після цього з Zn-1*(sn-2) з використанням (5.4) знаходяться рівняння станів.

Процес рішення рівнянь (5.1) і (5.4) називається умовною оптимізацією.

У результаті умовної оптимізації виходять дві послідовності.

  1.  Умовних максимумів цільової функції на останньому, на двох останніх, на …, на n кроках:

Zn*(sn-1), Zn-1*(sn-2), …, Z2*(s1), Z1*(s0).

  1.  Умовних оптимальних керувань на n-ому, (n-1) – ому, … 1-му кроках:

Хn*(sn-1), Хn-1*(sn-2), …, Х2*(s1), Х1*(s0).

Цей спосіб відповідає рішенню задачі ДП по «зворотній схемі» (алгоритм «зворотного прогону»), коли рішення починається з завершального етапу. Помінявши n-й і 1-й  кроки місцями, одержимо «пряму схему» (алгоритм «прямого прогону») рішення задачі ДП.

Використовуючи ці послідовності, можна знайти рішення задачі ДП при даних n і s0. За визначенням (5.1) Z1*(s0) – умовний максимум цільової функції за n кроків за умови, що до початку 1-го кроку система була в стані s0, тобто

Zmax = Z1*(s0).

Після цього, використовуючи послідовність умовно оптимальних керувань, при фіксованому s0 одержуємо Х1* = Х1*(s0), потім, з огляду на відсутність післядії, знаходимо s*1 і підставляємо цей стан у послідовність умовних оптимальних керувань і т.д. Одержуємо:

Х1* = Х1*(s0)  s*1   Х*2 = Х2*(s1) s*2  …   s*n-1   Х*n= Хn*(sn-1).

Одержуємо оптимальне рішення задачі ДП:

Х*(Х*1, Х*2, … Х*n).

Загальна схема застосування методу ДП має такий вид.

  1.  Вибрати спосіб розподілу процесу керування на кроки.

Визначити параметри стану sk і змінні керування Хk на кожному кроці.

Записати рівняння станів.

Увести цільові функції k-го кроку і сумарну цільову функцію.

Ввести в розгляд умовні максимуми (мінімуми) Zk* (sk-1)  і умовне оптимальне керування на k-ому кроці: Хk*(sk-1), k=n, n-1, … 2, 1...

Записати основні рівняння (Беллмана) для обчислювальної схеми ДП для Zn*(sn-1) і Zk* (sk-1),   k = n-1, … 2, 1...

Вирішити послідовно рівняння (Беллмана)  (умовна оптимізація) і отримати дві послідовності функцій: {Zk* (sk-1)} і {Хk*(sk-1)}.

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

а)  Zmax = Z1*(s0)  і

б) по ланцюжку s0  Х*1  s*1   Х*2  s*2  …  Х*n-1  s*n-1   Х*n  s*n    оптимальне керування: Х*(Х*1, Х*2, … Х*n).

Приклад 1. Задача розподілу капіталовкладень.    

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

Планується здійснити капіталовкладення в розмірі 3 мільйонів гр.о.

Знайти такий розподіл капіталовкладень, щоб дістати максимальний прибуток від реалізації всіх проектів.

1 млн.

2 млн.

3 млн.

1

140

250

350

2

200

320

400

3

300

350

450

4

180

270

330

Рішення. Дану задачу можна вирішити шляхом прямого перебору всіх можливих варіантів рішення. Однак такому способу притаманні недоліки:

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

Метод ДП дозволяє в значній мірі позбутися цих недоліків. В основу методу покладена ідея поступової покрокової оптимізації. Дана задача розбивається на 4 етапи. Свідомо неоптимальні рішення, отримані на проміжних етапах, відкидаються. Використання інформації про ряд рішень дозволяє в значній мірі скоротити обсяг обчислень.

Задача вирішується з застосуванням сіткової моделі.

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

I етап. Засоби вкладаються тільки в перший проект.

II етап. Засоби вкладаються в перший і другий проекти разом.

III етап. Засоби вкладаються в перший, другий, третій проекти разом.

IV етап. Засоби вкладаються в усі чотири проекти.

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

Х1 – обсяг капіталовкладень розподілених на етапі 1;

Х2 – обсяг капіталовкладень розподілених на етапах 1 і 2;

Х3 – обсяг капіталовкладень розподілених на етапах 1, 2 і 3;

Х4 – обсяг капіталовкладень розподілених на етапах 1, 2, 3 і 4.

На кожному етапі знаходиться умовно оптимальне рішення.

Умовно оптимальний виграш для вершини 1 II етапу:

Z2* (1) = max {0+200; 140+0} = 200.

Дуги другого етапу характеризуються величинами Х1 і Х2. Різниця ΔХ2 = Х1 - Х2 - інвестиції в другий проект.

Умовно оптимальний виграш для вершини 2 II етапу:

Z2* (2) = max {0+320; 140+200; 250+0} = 340.

Найкраще рішення для II етапу:

Z2* (Х2) = max { Z1* (Х1) + П2}.

Найкраще рішення для III етапу:

Z3* (Х3) = max { Z2* (Х2) + П3}.

ΔХ1 = 0; ΔХ2 = 1; ΔХ3 = 1; ΔХ4 = 1.

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

Лекція 7. Динамічне програмування. Прокладення траси.

Приклад 2. Задача прокладення траси.    

Нехай є мережа пунктів, які можна зв'язати між собою відрізками траси (лінійними спорудженнями) із заданими витратами на прокладку траси між сусідніми пунктами.

Знайти оптимальну трасу прокладки лінійних споруджень з пункту А в пункт В таким чином, щоб вартість лінійних споруджень була мінімальною.

Рішення. Схему розташування пунктів можна подати у вигляді сіткової моделі прямокутної форми, вузлами якої є пункти, що з'єднуються, а над дугами вказуються вартості прокладки ділянок траси між сусідніми пунктами. Отже на сітковій моделі ділянки траси можуть розташовуватися в двох напрямках (Y і Z).

Рішення задачі розбивається на 5 послідовних етапів.


 

При рішенні використовується алгоритм «зворотного прогону» від кінцевого пункту В до початкового пункту А. Під рішенням на кожному етапі розуміється вибір напрямку, по якому прокладається чергова ділянка траси. Вартість прокладки називається виграшем. Умовно оптимальний виграш позначається W*. Значення W* будемо записувати у відповідні вершини (вузли), а обрані напрямки – позначати стрілками.

Етап 5.  Вершина (2, 2) Х*=Y W*=6

Вершина (3, 1) Х*=Z W*=10

Етап 4.  Вершина (1, 2) Х*=Y W*=11

Вершина (2, 1) Х*=Z W*=17

Вершина (3, 0) Х*=Z W*=18

Етап 3.  Вершина (1, 1) Х*=Z W*=23 -суміжна

Вершина (0, 2) Х*=Y W*=26

Вершина (2, 0) Х*=Z W*=22

Етап 2.  Вершина (0, 1) Х*=Y W*=26

Вершина (1, 0) Х*=Y W*=30

Етап 1.  Вершина (0, 0) Х*=Z W*=37 – оптимальний виграш.

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

А(0, 0)  (0, 1)  (1, 1)  (1, 2)  (2, 2)  B(3, 2)

Тема 6.

Лекція 8. Сіткове планування та управління (СПУ). Сіткові графіки.

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

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

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

Перші системи, що використовують сіткові графіки, були розроблені і застосовані в США в 50-х роках ХХ ст. Наприклад, система СРМ (Critical Path Method – метод критичного шляху) застосовувалася при керуванні будівельними роботами; система PERT (Program Evaluation and Review Technology – метод оцінки й огляду програм) – при  створенні систем «Поларис».

СПУ дозволяє:

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

Головними елементами сіткової моделі є події і роботи.

Термін робота використовується в СПУ в декількох змістах.

По-перше, це дійсна робота – протяжний у часі процес, що вимагає витрат ресурсів (праці, матеріальних ресурсів, часу).

По-друге, це очікування – протяжний у часі процес, що не вимагає витрат праці (наприклад, сушіння після фарбування, твердіння бетону й ін.).

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

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

Серед подій сіткової моделі виділяють вихідна і завершальна події. Вихідна подія не має попередніх робіт і подій. Завершальне подія не має наступних робіт і подій.

Події на сітковому графіку (чи на графі), зображуються колами (вершинами графа), а роботи – стрілками (орієнтованими дугами), що показують зв'язок між роботами. Фрагмент сіткового графіка наведений на мал.6.1.

Мал. 6.1.

Порядок і правила побудови сіткових графіків.

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

При побудові сіткового графіка необхідно дотримувати наступні правила:

  1.  у сітковій моделі не повинно бути «тупикових» подій, тобто подій з який не виходить жодна робота, за винятком завершального події;

у сітковому графіку не повинно бути «хвостових» подій (крім вихідного), яким не передує хоча б одна робота;

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

будь-які дві події повинні бути безпосередньо зв'язані не більш ніж однією роботою-стрілкою;

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

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

Упорядкування сіткового графіка полягає в такому розташуванні подій і робіт, при якому для будь-якої роботи попередня їй подія розташована лівіше і має менший номер у порівнянні з завершальною для цієї роботи подією. Іншими словами, в упорядкованому сітковому графіку всі стрілки-роботи спрямовані зліва направо: від подій з меншими номерами до подій з більшими номерами.

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

Часові параметри сіткових графіків.

Часові параметри подій.

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

t pj = max { t pi + tij }, де tij - тривалість роботи i-j.

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

t пi = min { t пj - tij }, де tij - тривалість роботи i-j.

  1.  Резерв часу події дорівнює різниці пізнього і раннього термінів його здійснення:

R i = t пi - t pj.

Часові параметри подій зводяться в таблицю.


Часові параметри робіт.

  1.  Ранній термін початку роботи дорівнює ранньому терміну здійснення попередньої події: t pпij = t pi.

Ранній термін закінчення роботи дорівнює сумі раннього терміну здійснення попередньої події і тривалості самої роботи: t ij = t pi + tij.

Пізній термін закінчення роботи дорівнює пізньому терміну здійснення її завершальної події: t пзij = t пj.

Пізній термін початку роботи дорівнює різниці між пізнім терміном її закінчення і тривалості самої роботи: t ппij = t пj - tij.

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

R ij = t пj - t pi - tij ; чи R ij = t ппij - t pпij ; чи R ij = t пзij - t ij.

  1.  Частковий резерв часу роботи першого виду – це частина повного резерву часу роботи, на яку можна збільшити її тривалість без зміни пізнього терміну здійснення її початкової події: R1(i,j) = t пj - t пi - tij ; чи R1(i,j) = R(i,j) - R(i).

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

Rв(i,j) = t рj - t рi - tij ; чи  Rв(i,j) = R(i,j) - R(j).

  1.  Частковий резерв часу роботи третього чи виду незалежний резерв часу – це частина повного резерву часу роботи, отриманий для випадку, коли всі попередні роботи закінчуються в пізній термін, а всі наступні роботи починаються в ранній термін:

Rн(i,j) = t рj - t пi - tij ; чи Rн(i,j) = R(i,j) - R(i) - R(j) ; чи Rн(i,j) = Rс(i,j) - R(i).

Часові параметри робіт зводяться в таблицю.

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

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

Зауваження:

  1.  частковий резерв часу першого виду може бути використаний для збільшення тривалості даної і наступної робіт;
  2.  вільний резерв часу використовується для збільшення тривалості даної і попередніх робіт;
  3.  незалежний резерв часу використовується для збільшення тривалості тільки розглянутої роботи.

Мал. 6.2.

Лекція 9. Сіткове планування та управління (СПУ). Аналіз та оптимізація.

Аналіз і оптимізація сіткового графіка.

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

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

Коефіцієнтом напруженості Кн роботи (i,j) називається відношення тривалості відрізків шляху, які не співпадають між собою і розміщених між одними й тими самими подіями, одним із яких є шлях максимальної тривалості, що проходить через дану роботу, а іншим – критичний шлях:

Кн(i,j) =

t (Lmax) – t ‘кр

(6.1)

t кр -- t ‘кр

де t (Lmax) -  тривалість максимального шляху, що проходить через роботу;

t кр  - тривалість (довжина) критичного шляху;

t‘кр  - тривалість відрізка розглянутого шляху, що збігає з критичним шляхом.

Формулу (6.1)можна легко привести до виду:

Кн(i,j) = 1 -

R(i,j)

(6.2)

t кр -- t ‘кр

де R(i,j) – повний резерв часу роботи (i,j).

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

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

Оптимізація сіткового  графіка в залежності від повноти розв'язуваних задач  може бути умовно розділена на часткову і комплексну. Видами часткової оптимізації сіткового графіка є:

  1.  мінімізація часу виконання комплексу робіт при заданій його вартості;
  2.  мінімізація вартості комплексу робіт при заданому часі виконання проекту.

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

Оптимізація сіткового графіка методом «час – вартість».

При використанні методу «час – вартість» передбачається, що зменшення тривалості роботи пропорційне зростанню її вартості. Кожна робота (i,j) характеризується тривалістю t(i,j), що може знаходитися в межах

a(i,j) ≤ t(i,j) ≤ b(i,j) (6.3)

де a(i,j) – мінімально можлива (екстренна) тривалість роботи (i,j), яку можна здійснити в умовах розробки;

b(i,j) – нормальна тривалість виконання роботи (i,j).

При цьому вартість c(i,j) роботи (i,j) лежить в межах від cmin(i,j) (при нормальній тривалості роботи) до cmax(i,j) (при екстремальній тривалості роботи). Зміна тривалості
Δt(i,j) = b(i,j) - t(i,j) роботи (i,j) у межах (6.3) відповідає зміні вартості роботи Δc(i,j). Залежність зміни вартості Δc(i,j) від зміни тривалості роботи Δt(i,j) визначається коефіцієнтом витрат на прискорення роботи (див. мал. 6.3)

h(i,j) =

Δc(i,j)

=

cmax(i,j) - cmin(i,j)

(6.4)

Δt(i,j)

b(i,j) – a(i,j)

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

C =

i,j

c(i,j)

(6.5)

зменшиться на величину

ΔC =

i,j

Δc(i,j) =

i,j

[b(i,j) - t(i,j)] h(i,j) =

i,j

Δt(i,j) h(i,j)

(6.6)

Для проведення часткової оптимізації сіткового графіка крім тривалостей робіт t(i,j), необхідно знати їхні граничні значення a(i,j) і b(i,j), а також коефіцієнти витрат на прискорення робіт h(i,j), що обчислюються по формулі (6.4). Тривалість кожної роботи t(i,j) доцільно збільшити на величину резерву часу роботи так, щоб не змінити ранні  (очікувані) терміни настання  всіх подій сітки, тобто на  величину вільного резерву часу роботи Rв(i,j).


   

 

Мал. 6.3.

Тема 7.

Лекція 10. Управління запасами.

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

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

Моделі керування запасами характеризуються такими  параметрами.

Попит. Потреба в запасі. Попит на продукт, що запасається, може бути детермінованим (у найпростішому випадку - постійним у часі) чи випадковим. Випадковість попиту описується або випадковим моментом попиту, або випадковим обсягом попиту в детерміновані або випадкові моменти часу.

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

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

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

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

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

Штраф за дефіцит. Будь-який склад створюється для того, щоб запобігти дефіциту певного типу виробів у системі, що обслуговується. Відсутність запасу в потрібний момент приводить до збитків, пов'язаним із простоєм устаткування, неритмічністю виробництва і т.д. Ці збитки називаються штрафом за дефіцит.

Номенклатура запасу. У найпростіших випадках передбачається, що на складі зберігається запас однотипних чи виробів однорідного продукту. У більш складних випадках розглядається номенклатурний запас.

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

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

Введемо в розгляд функції:

А(t) – функцію поповнення запасів;

B(t) – функцію витрати запасів;

R(t) – функцію попиту на продукт, що запасається, за проміжок часу [0, t]. У моделях керування запасами використовуються  похідні цих функцій за часом:

a(t) – інтенсивність поповнення запасів;

b(t) – інтенсивність витрати запасів;

r(t) – інтенсивність попиту запасів.

У залежності від властивостей функцій інтенсивностей a(t), b(t), r(t) моделі керування запасами класифікуються в такий спосіб.

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

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

Якщо всі параметри моделі не міняються в часі, вона називається статичною, в іншому випадку – динамічною.

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

Рівень запасу в момент t визначається  основним рівнянням запасів

J(t) = J0 + A(t) - B(t), (7.1)

де J0 - початковий запас у момент часу  t = 0.

Рівняння (7.1) в інтегральній формі має вид:

 t t

J(t) = J0 +  a(t) dt -  b(t) dt. (7.2)

 0 0

Однопродуктова статична детермінована модель без дефіциту.

Припущення про те, що дефіцит не допускається, означає повне задоволення попиту на продукт, що запасається, тобто функції b(t) і r(t) збігаються.

Розглянемо деякий інтервал часу θ (наприклад рік). Загальне споживання запасів за який складає N. У найпростішому випадку передбачається, що витрата запасу відбувається безупинно з постійною інтенсивністю, тобто  b(t)= b. Ця інтенсивність визначається відношенням загального споживання продукту до часу, протягом якого він витрачається:

b =

N

(7.3)

θ

Поповнення запасу відбувається партіями однакового обсягу n через однакові відрізки часу Т. Оскільки інтенсивність витрати дорівнює b, то кожна партія буде використана за час Т

Т =

n

(7.4)

b

Таким чином функція a(t) не є безперервною:

a(t) =

0, t ≠ iT

n, t = iT, i = 0, 1,…

Іншими словами функція інтенсивності постачання a(t) є імпульсною, тобто запас поповнюється миттєво в моменти часу кратні T.

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

На часовому інтервалі [0, T] рівень запасу зменшується по прямої J(t) = n - bt від значення n до 0. Оскільки дефіцит не допускається, то в момент часу T рівень запасу миттєво поповнюється до колишнього значення n за рахунок надходження партії запасу.

Процес зміни J(t) повторюється на кожному часовому інтервалі тривалістю T. Графічно залежність рівня запасу від часу ілюструється мал. 7.1.

Мал. 7.1.

Таким чином, задача керування запасами полягає у визначенні такого обсягу партії n, при якому сумарні витрати на створення і збереження запасу були б мінімальними.

Позначимо через С сумарні витрати, витрати на створення запасу – через С1, витрати на збереження запасу – через С2, витрати на доставку однієї партії продукту, що не залежать від обсягу партії - с1, витрати на збереження однієї одиниці продукту в одиницю часу – с2. Оскільки за час θ необхідно запастися N одиницями продукту, що доставляється партіями обсягу n, то число таких партій k дорівнює:

k =

N

=

θ

(7.5)

n

T

Отже  С1 = с1k = с1N/n     (7.6)

Миттєві витрати на збереження запасу в момент часу t рівні с2 J(t). Тоді витрати на збереження за проміжок [0, T] складуть

 Т T

с2  J(t) dt = с2  (n-bt) dt

 0 0

або з урахуванням (7.4)

 Т

с2  J(t) dt =  

                      0 

с2

2

Середній запас за проміжок [0, T] дорівнює /2, тобто витрати на збереження всього запасу при лінійному часі його витрати дорівнюють витратам на збереження середнього запасу.

З урахуванням (7.5) одержуємо:

с2 =

с2

k =

с2 n θ

(7.7)

2

2

Відзначимо, що витрати С1 обернено пропорційні, а витрати С2 прямо пропорційні обсягу партії n.

З огляду на, що З = З1 + З2 сумарні витрати визначаються функцією витрат:

С =

с1 N

+

с2 θ n

(7.8)

n

2

Графіки залежностей С , С1, С2 зображені на мал. 7.2.

Мал. 7.2.

В точці минимума функції С(n) її похідна дорівнює 0:

С’(n) = -

с1 N

+

с2 θ

= 0

n2

2

Тоді

n =

n0 =

 

1 N

(7.9)

с2 θ

або, з урахуванням (7.3)

 

n0 =

 

1b

(7.10)

с2

Формула (7.10) називається формулою Уїлсона чи формулою найбільш економічного обсягу партії.

Зауважимо, що добуток С1С2 = 0,5с1с2θN є величина постійна. Як відомо сума двох співмножників приймає найменше значення, коли вони рівні між собою, тобто С1= С2 або

с1 N

=

с2 n θ

(7.11)

n

2

Рівність (7.11) легко перетворити до виду (7.9).

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

С0 = С(n0) =  

1 N

(7.12)

n

звідки з урахуванням (7.5) и (7.9), отримуєм С0 = √2с1с2θN або

С0 = θ

 

1 с1b 

(7.13)

Число оптимальних партій k0 за час θ з урахуванням (7.5), (7.9) і (7.3) дорівнює

 k0 =

N

=

 

с2 N θ

= θ

с2 b

n0

1

1

Час витрати оптимальної партії на підставі (7.4) з урахуванням (7.9) і (7.3) дорівнює

T0 =  

n0

= n0

θ 

(7.14)

b

N

T0 =

 

1 θ

=

1

(7.15)

с2 N 

с2 b

Приклад. Потреба складального підприємства в деталях деякого типу складає 120 000 деталей на рік, причому ці деталі витрачаються в процесі виробництва рівномірно і безупинно. Деталі замовляються раз на рік і постачаються партіями однакового обсягу, зазначеного в замовленні. Збереження деталі на складі коштує 0,35 гр.о. на добу, а постачання партії – 10 000 гр.о. Простоювання виробництва через відсутність деталей неприпустимо.

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

Рішення. За умовою витрати на одну партію складають с1 = 10 000 гр.о., витрати на збереження одиниці запасу в добу с2 = 0,35 гр.о. Загальний проміжок часу θ = 1 рік = 365 днів, а загальний обсяг запасу за цей період складає N = 120 000 деталей.

По формулі (7.9) визначається n0 ≈ 4335 деталей, а по формулі (7.14) T0 =13,2 ≈ 13 днів.

Відповідь. Найбільш економічний обсяг партії n0 ≈ 4335 деталей.

Оптимальний інтервал часу між постачаннями T0 ≈ 13 днів.

Однопродуктова статична детермінована модель без дефіциту з «розривами» цін.

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

Розглянемо однопродуктову статичну детерміновану модель без дефіциту, у якій ціна одиниці товару дорівнює ц1 при n < q і дорівнює ц2 при n ≥ q, причому ц1 > ц2 і q – розмір замовлення, при перевищенні якого надається знижка.

Сумарні витрати в одиницю часу при n < q з урахуванням  (7.8) і (7.3) рівні:

S1(n) = b ц1 + b

с1

+ n

с2 

(7.16)

n

2

Сумарні витрати в одиницю часу при n ≥ q з урахуванням  (7.8) і (7.3) рівні:

Sq(n) = b ц2 + b

с1

+ n

с2 

(7.17)

n

2

Мінімум функцій  S1(n) і Sq(n), відповідно до формули Уилсона, досягається в точці n0 (7.10). З аналізу графіків функцій S1(n) і Sq(n) (мал. 7.3) випливає, що оптимальний обсяг замовлення n* залежить від того, в якому місці відносно трьох показаних на мал.7.3 зон знаходиться точка розриву ціни q. Розташування зон визначається шляхом визначення невідомого q1 (при відомому з (7.10) n0) з рівняння S1(n0) = Sq(q1).

Тоді зони розподіляються в такий спосіб:

Зона 1: 0  ≤ q < n0;

Зона 2: n0q < q1;

Зона 3: q  ≥ q1.

У залежності від розташування крапки розриву ціни q, оптимальний розмір замовлення визначається в такий спосіб:

n* =

n0, якщо 0  ≤ q < n0 (зона 1)

q, якщо n0q < q1 (зона 2)

(18)

n0, якщо q  ≥ q1 (зона 3)

Мал. 7.3.

Алгоритм визначення n* можна подати в такому вигляді.

  1.  Визначити n0. Якщо q < n0 (зона 1), то рішення n* = n0 отримане й алгоритм завершується. В іншому випадку переходимо до кроку 2.

Визначити q1 з рівності S1(n0) = Sq(q1) і установити, де відносно зон 2 і 3 знаходиться значення q:

а) якщо n0 ≤ q < q1 (зона 2), то n* = q;

б) якщо q  ≥ q1 (зона 3), то n* = n0.


Тема 8.

Лекція 11. Складні системи. Класифікація задач прийняття рішень і прийняття рішень в умовах невизначеності.

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

Термін "теорія систем" відноситься до різних аспектів дослідження систем. Її основними частинами є

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

Найбільш близьке до терміна "системний аналіз" поняття - "дослідження операцій", що позначає математичну дисципліну, що охоплює дослідження математичних моделей для вибору величин, що оптимізують задану математичну конструкцію (критерій)

Опора системного аналізу на дослідження операцій приводить до таких його математизованих розділів, як

  1.  постановка задач ухвалення рішення;
  2.  опис безлічі альтернатив;
  3.  дослідження багатокритеріальних задач;
  4.  методи рішення задач оптимізації;
  5.  обробка експертних оцінок;
  6.  робота з макромоделями системи.

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

  1.  принцип кінцевої мети – абсолютний пріоритет кінцевої мети;

принцип єдності – спільний розгляд системи як цілого і як сукупності елементів;

принцип пов’язяності – розгляд будь-якої частини разом з її зв'язками з оточенням;

принцип модульної побудови – виділення модулів у системі і розгляд її як сукупності модулів;

принцип ієрархії – введення ієрархії елементів і(або) їх ранжирування;

принцип функціональності – спільний розгляд структури і функції з пріоритетом функції над структурою;

принцип розвитку – врахування змінюваності системи, її здатності до розвитку, розширенню, заміні частин, накопиченню інформації;

принцип децентралізації – поєднання в прийнятих рішеннях і керуванні централізації і децентралізації;

принцип невизначеності – врахування невизначеностей і випадковостей у системі.

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

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

Ці моделі можна класифікувати як задачі мінімізації (максимізації) M-векторного векторного показника ефективності Wm(x), m=1,2,...,M, N-мірного векторного аргументу x=(x1,x2,...,x), компоненти якого задовольняють системі обмежень-рівностей hk(x)=0, k = 1, 2 ... K, обмежень-нерівностей gj(x)>0, j=1,2,...J, обласним обмеженням xli<xi<xui, i=1,2...N.

Усі задачі прийняття оптимальних рішень можна класифікувати відповідно до виду функцій і розмірністю Wm(x), hk(x), gj(x) і розмірністю і змістом вектора x:

  1.  одноцільове прийняття рішень - Wm(x) - скаляр;
  2.  багатоцільове прийняття рішень - Wm(x) - вектор;
  3.  прийняття рішень в умовах визначеності – вихідні дані – детерміновані (методи математичного програмування);
  4.  прийняття рішень в умовах невизначеності – вихідні дані – випадкові.

Усі рішення приймаються завжди на основі інформації, якою володіє особа, що приймає рішення (ОПР).

Кожна задача у своїй постановці повинна відбивати  структуру і динаміку знань ОПР про множину припустимих рішень і про показник ефективності. У ряді задач прийняття рішення вдається побудувати задовільну математичну модель. Тоді критерієм вибору того чи іншого оптимального рішення служить обчислене значення цільової функції. У реальних умовах просту математичну модель вдається відшукати не завжди.

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

Прийняття рішень в умовах ризику

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

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

Таким чином, інформаційні стани ОПР можуть по-різному характеризувати його фізичний стан:

  1.  якщо інформаційний стан складається з єдиного фізичного стану, то задача називається визначеною;
  2.  якщо інформаційний стан містить кілька фізичних станів і ОПР крім їх множини знає ще й імовірності кожного з цих фізичних станів, то задача називається стохастичною (частково невизначеною);
  3.  якщо інформаційний стан містить кілька фізичних станів, але ОПР крім їх множини нічого не знає про імовірність кожного з цих фізичних станів, то задача називається невизначеною.

Прийняття рішень в умовах невизначеності

Постановка задачі

Більшість реальних задач містить у тому чи іншому виді невизначеність. Можна навіть затверджувати, що рішення задач з урахуванням різного виду невизначеностей є загальним випадком, а прийняття рішень без їхнього обліку - часткою. В даний час не існує єдиного методологічного підходу до рішення таких задач. Проте, накопичена досить велика кількість методів формалізації постановки і прийняття рішень з урахуванням невизначеностей. При використанні цих методів варто мати на увазі, що усі вони мають рекомендаційний характер і вибір остаточного рішення завжди залишається за людиною (ОПР).

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

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


Урахування невизначених пасивних умов

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

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

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

Невизначені фактори, закон розподілу яких невідомий, є найбільш характерними при дослідженні якості адаптивних систем. Методичне врахування таких факторів базується на формуванні спеціальних критеріїв, на основі яких приймаються рішення. Критерії Вальда, Севіджа, Гурвіца і Лапласа вже давно і міцно ввійшли в теорію прийняття рішень.

Критерій Вальда (максимінний).

Відповідно до цього критерію в якості оптимальної вибирається та стратегія, при якій вибирається максимальний з мінімальних виграшів.

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

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

Обране в такий спосіб рішення цілком виключає ризик. Це означає, що ОПР не може зіштовхнутися з гіршим результатом, ніж той, на який він орієнтується. Які б умови Vj не зустрілися, відповідний результат не може виявитися нижче W. Ця властивість дозволяє вважати критерій Вальда одним з фундаментальних. Тому в практичних задачах він застосовується найчастіше як свідомо, так і неусвідомлено. Однак у практичних ситуаціях зайвий песимізм цього критерію може виявитися дуже невигідним.

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

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

Критерій Севіджа (мінімаксний).

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

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

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

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

Відповідне критерію Севіджа правило вибору таке: кожен елемент матриці рішень [Wij] віднімається від найбільшого результату max Wij відповідного стовпця. Різниці утворять матрицю залишків. Ця матриця поповнюється стовпцем найбільших різниць Wir. Вибирається той варіант, у рядку якого стоїть найменше значення.

Критерій Гурвіца.

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

де r - коефіцієнт песимізму, обираний в інтервалі [0,1].

Правило вибору відповідно до цього критерію таке: матриця рішень [Wij] доповнюється стовпцем, що містить середні зважені найменшого і найбільшого результатів для кожного рядка. Вибирається той варіант, у рядках якого стоять найбільші елементи Wir цього стовпця.

При r =1 критерій Гурвіца перетворюється в критерій Вальда (песиміста), а при r=0 – у критерій азартного гравця. Звідси ясно, яке значення має ваговий множник r. У практичних  аплікаціях правильно вибрати цей множник буває так само важко, як правильно вибрати критерій. Тому найчастіше ваговий множник r=0.5 приймається як середня точка зору.

Критерій Гурвіца пред'являє до ситуації, у якій приймається рішення, такі вимоги:

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

Елементи теорії ігор.

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

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

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

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

< U, V, W1, W2, R1, R2 >,

де U – множина стратегій сторони, що оперує, (конструктора);

V  – множина стратегій сторони, що опонує, (технолог і природа);

W1 і W2 – показники якості гравців;

R1 і R2 – системи переваг гравців.

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

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

Другий принцип говорить, що раціональним вибором будь-якого гравця вважається така стратегія u$ (чи v$), для якої ситуація (u$, v$) взаємовигідна: будь-яке відхилення від даної ситуації гри не є вигідним ні для одного з гравців.

Вирішується парна матрична гра з нульовою сумою (виграш однієї сторони дорівнює програшу іншої) на основі розгляду платіжної матриці, що являє собою сукупність значень U і V (пари стратегій (u,v) U  V називається ситуацією гри) а також виграшів Wij при парному сполученні всіх можливих стратегій сторін.

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

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

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

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

Оптимальними стратегіями гри наведеної в табл. 8.1 будуть для A – 2, для B – 2. Ціна гри дорівнює 5. Відзначимо, що у випадку наявності сідлової точки жоден із гравців не може поліпшити стратегію, і стратегії такі називаються чистими. Відзначимо, що гра з чистими стратегіями може існувати тільки при наявності повної інформації про дії супротивника.

Таблиця 8.1

Стратегії

A

Стратегії B

min

рядків

1

2

3

4

1

8

2

9

5

2

2

6

5

7

18

5

3

7

3

-4

10

-4

max

стовпців

8

5

9

18

 

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


P<n>=<p1, p2, ..., pn> - для гравця A, де

;

Q<m>=<q1, q2, ..., qn>  - для гравця B, де

.

При цьому гравець A вибирає стратегію відповідно до принципу максиміну за виразом:

а гравець B за принципом мінімаксу

Розглянемо приклад: нехай розглядається прийняття рішення в грі 22, де гравець A знає імовірність стратегії 1, тобто p1, тоді очевидно імовірність стратегії 2 буде 1-p, відповідно стратегії гравця B будуть q1 і 1-q1. Платіжна матриця буде мати вигляд:

 

 

B

 

(8.1)

 

 

q1

1-q1

A

p1

a11

a12

 

1-p1

a21

a22

На підставі матриці (8.1) і наведених вище виразів складається таблиця:

Таблиця 8.2

Чисті стратегії гравця В

Очікувані виграші гравця А

1

(a11-a21)p1 + a21

2

(a12-a22)p1 + a22

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

<p*1, p*2>,

тобто гравцю A вигідно застосовувати стратегію 1 з частотою (імовірністю) – p1, а стратегію 2 з частотою p2.

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

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

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

  1.  оцінки можливих втрат ефективності у випадку реалізації чистої стратегії;
  2.  визначення додаткових витрат на їхню компенсацію за допомогою "гнучких" рішень;
  3.  оцінки імовірності розглянутих стратегій протидії;
  4.  визначення можливості реалізації компромісних варіантів і т.ін.

Для аналізу конфліктної ситуації потрібно на основі математичної моделі операції побудувати платіжну матрицю [Wmn] = [Wij], де Wij характеризує якість вибору при виборі
i-го варіанта реалізації і при j-му варіанті протидії супротивника.

Рішення може бути отримане в чистих стратегіях, коли є сідлова точка. Умова сідлової точки має вигляд

(8.2)

де ліва частина виразу – нижня ціна гри, права – верхня ціна гри.

Якщо умова

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

Рішення в змішаних стратегіях полягає в реалізації чистих стратегій з різними імовірностями, що задаються розподілом:

для шуканого вибору – у в идгляі вектора-стовпця

G = {gi}, де i = 1,2 ...m;

;

для протидії – у вигляді вектора-рядка

F = {fj}, де j = 1,2 ...n;

,

де  gi – імовірність вибору стратегії ui;

fj – імовірність вибору стратегії vj.

Платіжну функцію запишемо в токому вигляді:

де індексом "т" позначена процедура транспонування.

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

Послідовність вирішення гри така:

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

Перевіряється наявність сідлової точки за умовою (8.2).

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

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

  1.  Визначеність. Кожна альтернатива приводить до єдиного рішення (усі розглянуті раніше задачі відносяться до цього класу).

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

Найбільш складні задачі – це задачі, що вирішуються в умовах невизначеності. У таких задачах відомий набір результатів, але не відомі імовірності їхньої появи. Для рішення задач в умовах невизначеності використовуються спеціальні критерії: Вальда, Севіджа, Гурвіца.


Питання до курсу

Тема 1.

  1.  Поняття про дослідження операцій. Типи задач дослідження операцій.

Задачі управління. Цілі. Критерії. Обмеження. Показники якості. Оптимальне рішення.

Тема 2.

  1.  Основна задача лінійного програмування. Вільні і базисні змінні. Допустиме рішення. Оптимальне рішення.

Розробка моделі лінійного програмування.

Графічний метод вирішення задачі лінійного програмування. Область допустимих рішень. Оптимальне рішення.

Тема 3.

  1.  Розподільчі задачі. Транспортна задача. Постановка і особливості транспортної задачі.

Розподільчі задачі. Транспортна задача. Початкове рішення. Метод “південно-західного кута”.

Розподільчі задачі. Транспортна задача. Початкове рішення. Метод “найменшого елементу” (найменших витрат).

Розподільчі задачі. Транспортна задача. Цикл перерахунку. Оцінка вільної клітинки. Ціна циклу. Оптимізація розподілення поставок.

Розподільчі задачі. Транспортна задача. Загальний алгоритм вирішення транспортної задачі.

Тема 4.

  1.  Симплекс-метод вирішення задач лінійного програмування.

Допустиме рішення.

Базисні і вільні змінні.

Основний алгоритм симлекс-методу.

Тема 5.

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

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

Тема 6.

  1.  Сіткове планування і управління (СПУ). Сіткові моделі і сіткові графіки. Задачі, що вирішуються методами СПУ. Події і роботи. Фіктивна робота.

Сіткове планування і управління (СПУ). Сіткові моделі і сіткові графіки. Порядок і правила побудови сіткових графіків. Упорядкування сіткового графіку.

Часові параметри сіткових графіків. Часові параметри подій.

Часові параметри сіткових графіків. Часові параметри робіт. Терміни виконання робіт.

Часові параметри сіткових графіків. Часові параметри робіт. Резерви часу робіт.

Часові параметри сіткових графіків. Часові параметри робіт. Довжина шляху. Повний шлях. Критичний шлях.

Оптимізація сіткового графіку. Коефіцієнт напруженості робіт. Часткова і комплексна оптимізація. оптимізація сіткового графіку за критерієм “час-вартість”.

Тема 7.

  1.  Задача управління запасами. Основні поняття.

Задача управління запасами. Постановка задачі. Класифікація задач управління запасами.

Задача управління запасами. Постановка задачі. Одно продуктова статична детермінована модель без дефіциту. Формула Уілсона.

Задача управління запасами. Постановка задачі. Одно продуктова статична детермінована модель без дефіциту з “розривами цін”. Алгоритм вибору рішення.

Тема 8.

  1.  Поняття про складну систему. Системний аналіз. Принципи системного підходу.

Задачі прийняття рішень. Класифікація задач прийняття рішень.

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

Задачі прийняття рішень. Критерії для вирішення задач прийняття рішень. Критерій Вальда.

Задачі прийняття рішень. Критерії для вирішення задач прийняття рішень. Критерій Севіджа.

Задачі прийняття рішень. Критерії для вирішення задач прийняття рішень. Критерій Гурвіца.

Типи задач.

Задачі до теми 2.

  1.  Графічним методом вирішити задачу побудови мережі зв’язку, що складається із каналів зв’язку двох типів.

Задачі до теми 3.

  1.  Вирішити транспортну задачу методом “північно-західного кута”.

Вирішити транспортну задачу методом “найменшого елементу”.

Задачі до теми 5.

  1.  Вирішити задачу розподілу капіталовкладень методом динамічного програмування.

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

Задачі до теми 6.

  1.  Побудувати і упорядкувати сітковий графік. Обчислити часові параметри подій.

Побудувати і упорядкувати сітковий графік. Обчислити часові параметри робіт.

Задачі до теми 7.

  1.  Вирішити задачу управління запасами.

Вирішити задачу управління запасами з розривом ціни.

Література. 

  1.  Вентцель Е.С. Исследование операций. М: Сов.радио,1972

Зайченко Ю.П. Исследование операций – Учебник. Киев: Вища школа – 1986.

Горелик В.А., Ушаков И.А. Исследование операций. М.: Машиностроение, 1986.

Исследование операций в экономике: Учебн. Пособие для вузов/ Под ред. проф. Н.Ш.Кремера. – М.: ЮНИТИ, 2000.- 407с.

Акоф Р., Сосиени Н. Основы исследования операций. (ИСО) М.:Мир, 1971.

Аоки М. Введение в методы оптимизации. М.: Наука, 1977.

Хлытчиев С.М., Тарасова Н.П., Лившиц В.М. Теоретические основы почтовой связи:  Учебник для вузов – 2-е изд.- М.: Радио и связь, 1990. – 280с.

Барсук В.А., Губин Н.М., Батый А.Р. Экономико-математические методы и модели в планировании и управлении в отрасли связи. М: Радио и связь, 1984.

Черчмен Ч., Акоф Р., Арноф Л. Введение в исследование операций. М: Наука, 1967, 488с.


За
мовна система обслуговування

Швидка (автоматична)

t

t0

tmin

A1

U1

W1

B1

Cmin

C0

X5

X4

X3

W

A(20;2)

B

C

D

sk-1

sk

s’

Хk

Хk+1*(sk)

Хn*(sn-1)

fk (sk-1, Хk)

Значення цільової функції k-го

кроку при довільному керуванні Хk та стані sk-1.

Zk+1*(sk)

fk (sk-1, Хk) + Zk+1*(sk)

Умовно оптимальний 

виграш на k-ому кроці

26

11

6

15

5

6

В

26

23

17

10

3

7

12

37

30

22

18

10

8

5

А

0

1

2

3

0

1

2

Y

Z

10

11

12

11

10

20

5

8

s0

s1

s2

s3

s4

s5

i

j

k

i-j, j-k – роботы

i-k – фіктивна робота

i

i

j

R(i)

5.

j

R(j)

tp(i)

tп(i)

tp(j)

tп(j)

Час

t (i,j)

R (i,j)

tpп(i,j)

tп(j)

R (i,j)

tp(i)

t (i,j)

tпз(i,j)

6.

t (i,j)

R1(i,j)

t (i,j)

tп(j)

R1(i,j)

tпз(i,j)

tпп(i,j)

tпп(i,j)

7.

t (i,j)

Rв(i,j)

t (i,j)

tp(j)

Rс(i,j)

рз(i,j)

tpп(i,j)

tp(i)

8.

Rн(i,j)

t (i,j)

Rн(i,j)

tп(i)

tp(j)

t (i,j)

С

t

cmax(i,j)

c(i,j)

cmin(i,j)

0

a(i,j)

t(i,j)

b(i,j)

Δc(i,j)

α

b

b

b

3T

2T

T

t

0

n

J(t)

n0

С2

С1

С

ЅС0

С0

n

0

С

q

3

n* = n0

2

1

q1

n0

Sq

S1

0

С

n

q

2

n* = q

3

1

q1

n0

Sq

S1

0

С

n

n

С

0

S1

Sq

n0

q1

1

2

3

q

n* = n0


 

А также другие работы, которые могут Вас заинтересовать

23180. Філософський зміст категорії матерія 37 KB
  Якщо для філософів стародавнього світу матерія це матеріал з якого складаються тіла предмети а кожний предметтіло складається з матерії та форми як духовного першопочатку то для Р.Ньютон додає до Декартового визначення матерії як субстанції ще три атрибути: протяжність непроникність непорушна цілісність тілаінертність пасивність нездатність самостійно змінювати швидкість згідно із законами динаміки; вага зумовлена дією закону всесвітньої гравітації. Причому інертність та вага потім об'єднуються ним у поняття маси яка виступає...
23181. Рух, як спосіб простір та час як форми існування матерії 37 KB
  Рухяк спосіб простір та час як форми існування матерії Простір і час це філософські категорії за допомогою яких позначаються основні форми існування матерії. Філософію цікавить насамперед питання про відношення простору і часу до матерії тобто чи є вони реальними чи це тільки абстракціїфеномени свідомості. Сучасна наука розглядає простір і час як форми існування матерії. Матеріалізм підкреслює об'єктивний характер простору і часу невіддільність від руху матерії: матерія рухається у просторі і часі.
23182. Онтологія 128.5 KB
  Поняття онтологія не має однозначного тлумачення у філософії. Існує принаймні три значення цього поняття: Поперше під онтологією розуміють ту частину філософії яка з'ясовує основні фундаментальні принципи буття першоначала всього сутнісного. Саме поняття онтологія у перекладі з грецької мови означає вчення про суще сутнісне найважливіше онто суще сутнісне логія вчення. Подруге у марксистській філософії поняття онтологія вживається для з'ясування сутності явищ що існують незалежно від людини її свідомості та...
23183. Визначальні категоріальні характеристики світу 40 KB
  Визначальні категоріальні характеристики світу. Визначення змісту поняття світ можливе і дійсне тільки у системі відношення людина світ . Іншими словами світ є все те що відмінне від людини і що одночасно органічно має людину в собі. Отже на противагу об'єктивно існуючому світу є внутрішній світ людини .
23184. Поняття природи 115 KB
  природаангл. В побуті слово природа часто вживається у значенні природне середовище в якому живе людина все що нас оточує за винятком створеного людиною. 4 Друга природа створені людиною матеріальні умови її існування. У широкому розумінні природа органічний і неорганічний матеріальний світ Всесвіт у всій сукупності і зв'язках його форм що є об'єктом людської діяльності і пізнання основний об'єкт вивчення науки включно з тим що створене діяльністю людини.
23185. Народонаселення як природне явище 45.5 KB
  Народонаселення як природне явище Насе́лення лю́дність сукупність людей що постійно живуть в межах якоїсь конкретно вказанної територіїрайоні місті області частини країни країні континенту чи всієї земної кулі тощо. Наука яка вивчає розмір структури динаміку руху і розвиток населення зветься д е мо г ра фі я. Сукупність людей які здатні до самовідтворення та саморозвитку й проживають на певній територіїкраїна регіон континент чи будьяка інша частина планети називають населенням або народонаселенням. Населення в...
23187. Поняття глобалізаціїї та форми її існування 43 KB
  Поняття глобалізаціїї та форми її існування. Історичні етапи глобалізації: Сучасна глобалізація підготовлена багатьма історичними процесами: 1. Деякі дослідники вважаютьщо початковими формами глобалізації була торгівля та захоплення нових територій5 тис.Інші знаходять елементи глобалізації в епоху античності а саме у створенні імперії Олександра Македонського 1V ст.
23188. Глобальні проблеми сучасності 53 KB
  В загальному вигляді всі ці ресурси можна умовно віднести до трьох груп: матеріальніповітря вода їжа одяг засоби виробництва пересування матеріали для житла та ін. енергетичнірізноманітні форми енергії що дозволяють перетворювати матеріальні ресурси та інформаційнімова знання досвід тощо. Всі ці ресурси людина в своїй повсякденній та виробничій діяльності отримує з навколишнього середовища яке по суті є системою що включає природний антропогеннийстворений людиною та соціальнийприродноантропогенний компоненти....