Лекція 4.2 Математичне забезпечення. Типові задачі

Лекція 4.1 Забезпечуючи підсистеми

1.4.5. Мережеве планування

Методи мережевого планування розроблені в 60-і рр. двадцятого сторіччя. Методи мережевого планування відносяться до одного з розділів сучасної теорії управління великими системами і призначені для складання і спостереження за виконання проектів виробництва або досліджень. Вперше мережеві методи планування були оформлені в США у вигляді системи ПЕРТ або методу критичного шляху («Critical Path Scheduling»). Математичною основою цих методів служить теорія графів, яка є, у свою чергу, частиною теорії множин.

Розглянемо множину, що складається з кінцевого числа елементів, які ми позначатимемо буквами , ,…, , а сама множина буквою Х. Запишемо це символічно: X = {, ,…, }.

Кожному елементу , що належить X, поставимо у відповідність нуль, один або декілька елементів з X. Тоді ми побудуємо, користуючись термінологією теорії множин, деякий «граф». Позначимо через Г закон, що надає дану відповідність, і запишемо граф символічно G = (X, Г).

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

Для прикладу розглянемо множину з 5 елементів: X = {A, B, C, D,E}.

Хай закон Г, що визначає відповідність між елементами цієї множини, визначений таким чином: ГА = {B, C, D}, ГB = {B}, ГC = {D, E}, ГD = {A, C}, ГE = О, де символ О означає порожню множину. На рис 1.14 представлено графічне зображення цього графа, а в таблиці мал. 1.15 – його табличне завдання.

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

Вершиною графа називається елемент множини, створюючої граф. На мал. 1.14 вершин графа, які часто також називають крапками, це елементи безлічі A, B, C, D, E.

Дугою графа називається орієнтована пара вершин графа. На мал. 1.14 дугами є пари: (A, B), (A, C), (C,D) і так далі.

Шляхом називається послідовність зчеплених дуг, що дозволяють пройти з однієї вершини в іншу. На мал. 1.14 шляхів: (A, C, E), (A, C, D), (D, C, B) і тому подібне

Контуром називається шлях, початкова вершина якого співпадає з кінцевою. На мал. 1.14 контуром є шлях (A, C, D, A).

Петлею називається дуга, початок і кінець якої співпадають (B, B).

Ребром називається неорієнтована дуга, тобто дуга, у якої не вказаний напрям руху.

Ланцюгом називається зчеплена послідовність ребер.

Мал. 1.14 Мал. 1.15

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

Предком деякої вершини називається вершина, з якої виходить дуга, що входить в дану вершину.

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

Надалі розглядатимемо зв'язні графи без контурів.

Для зв'язного графа без контурів виникає і вирішується завдання розбиття його вершини на шари так, щоб:

а) всі елементи даного шару не мали предків в наступному шарі, а елементи останнього – нащадків;

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

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

Розглянемо зв'язний граф без контурів, представлений на мал. 1.16.

Вершина А не має предків. Вона утворює перший шар.

Мал. 1.16

Викреслимо вершину А і дуги, які з неї виходять (мал. 1.17).

На отриманому графові вершини, які не мають предків, - C, D, B, вони утворюють другий шар.

Мал. 1.17

Викреслимо ці вершини і дуги, витікаючі з них. Отримаємо граф мал. 1.18.

Наступний шар утворює вершина G.

Далі, застосовуючи цей алгоритм, отримуємо мал. 1.19.

Третій шар складають вершини E і F.

Далі - мал. 1.20.

Наступний шар складають вершини H і L.

Далі:

Наступний шар – вершині К.

І нарешті, шар – вершині М.

Мал. 1.18

Мал. 1.19

Мал. 1.20

Мал. 1.21

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

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

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

Проект може бути представлений мережею.

Розглянемо мережу деякого проекту (мал. 1.22).

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

Мал. 1.22

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

Припустимо, мережевий графік відповідає проекту будівництва деякого об'єкту. Тоді наприклад, подія № 8 може трактуватися як «початок закладки фундаменту», а роботи, передуючі цій події: (4,8) - «риття котловану під фундамент»; (6,8) - «підвозка залізобетонних блоків для фундаменту».

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

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

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

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

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

Ранній термін настання події визначається по формулах:

= 0,

t = ), j = 2, 3, …n, (1. 70)

де - час початку виконання проекту;

- ранній термін настання j – ї події;

- тривалість виконання операції (i, j), що йде з вершини i у вершину j;

- підмножина дуг, що входять у вершину j.

Граничний термін настання події визначається по формула

* = ), j = 2, 3, …n - 1,

* = , (1. 71)

= 0,

де - час початку виконання проекту;

- термін завершення проекту;

- пізній (граничний) термін настання j – го події;

- тривалість виконання операції (i, j), що йде з вершини i у вершину j;

- підмножина дуг, витікаючих з вершини j.

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

Резерви подій і операцій визначаються наступними співвідношеннями.

Резерв часу i – ї події:

= * - . (1. 72)

Повний резерв часу операції:

= * -- . (1. 73)

Вільний резерв часу операції:

= -- . (1. 74)

Незалежний резерв часу операції:

= * -- . (1. 75)

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

Алгоритм Форда

1. Відзначити кожну вершину індексом . Покласти все = 0.

2. Знайти таку дугу (i, j), що - < , і замінити на = + > .

Відмітимо, що > 0, якщо j ≠ 1.

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

Існує вершина така, що - = , оскільки монотонно зростає в перебігу процедури 2) – 3) і вершина є останньою вершиною, використаною для збільшення .

Так само хай вершина така, що - = , і так далі.

Оскільки послідовність , , , … є такою, що строго убуває, то в деякий момент часу отримаємо = .

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

Зауваження

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

Питання по темі

Що називається графом і які бувають види графів?

Які основні елементи графа?

Що називається мережевим графіком проекту?

Який шлях в мережевому графіку називається критичним і чому?

Які бувають і як визначаються резерви часу подій і робіт в мережевому графіку?

У чому полягає алгоритм Форда?

Теми семінарських занять

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

Стохастичні мережеві графіки проектів.

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

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

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

¹ Інтріллігатор М. Математічеськие методи оптимізації і економічна теорія. — М.: Прогрес, 1975.

² Bellman| Ст.|ст|, Dynamic| Programming|, Princeton|, N. J., Princeton| University| Press|, 1957.

Стосовно дискретних умов планування|планерування|, які з’являются| в економічних завданнях|задачах|, динамічне програмування — метод багатокрокової оптимізації.

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

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

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

Визначаються функції, що виражають зміну стану ^.системы під впливом управління . на i-м кроці процесу: .

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

Визначається умовно-оптимальний ефект (виграш) для останнього п-го кроку даного процесу: Wn(Sn), а також відповідне йому умовно-оптимальне управління .

Визначаються умовні оптимальні виграші (ефекти) і відповідаючі| цим ефектам управління для передостаннього, пред-предостаннього| і так далі до першого кроків процесу:

,

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

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

Приклад|зразок|

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

Початкові|вихідні| дані завдання|задачі|

Визначення об'єму|обсягу| будівельно-монтажних робіт на об'єкті по кварталах планового року складає: 2 млн крб. на перший квартал, 5 млн| крб. на другий, 3 млн крб. на третій і 1 млн крб. на четвертий. Підрядна організація планує|планерує|, які виробничі потужності мають бути на об'єкті. Робота ведеться у дві зміни, але|та| при необхідності може бути організована і третя зміна. Якщо знадобиться зменшити виробничі потужності на об'єкті, то витрати|затрати| по (X перекиданню на інші об'єкти складуть 70 тис. крб. на кожен млн крб. виконуваного об'єму|обсягу| робіт. Якщо потрібно буде ввести|запроваджувати| нові виробничі потужності, то витрати|затрати| на це складуть 100 тис. крб. по кожному млн крб. виконуваного об'єму|обсягу| робіт. Якщо на об'єкті знаходитимуться|перебуватимуть| невживані виробничі потужності, то на кожний| млн крб. об'єму|обсягу| втрати складатимуть 80 тис. крб. При браку|нестачі| потужностей і організації додаткової третьої зміни буде додатково| витрачатися 110 тис. крб. Перед початком планового періоду| на об'єкті є|наявний| стільки виробничих потужностей, скільки потрібно для виконання робіт об'ємом|обсягом| 2 млн крб.

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

1-й етап. Опис системи.

Позначимо виробничі потужності, що є на початку г'-го кварталу (i = 1, 2,3,4). За одиницю приймемо виробничі потужності для виконання об'єму робіт в один млн крб. Позначимо через т. необхідну кількість виробничих потужностей для виконання заданого в грамі-м кварталі об'єму робіт (т1 = 2, т2 = 5, т3 = 3, m4 = 1). Стан системи Si, таким чином, визначається величиной Xi. Управління Ui.состоит, по-перше, в перекиданні виробничих потужностей з даного об'єкту на яких-небудь інші або, навпаки, з яких-небудь об'єктів на даний об'єкт, по-друге, в організації додаткової третьої зміни при браку потужностей. Витрати при оптимальному управлінні мають бути мінімальними. Природним тимчасовим кроком процесу управління є квартал планового року.

2-й етап. Визначення функцій ефекту для i-го| кроку.

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

При зміні (перекиданню потужностей) функцію витрат|затрат| за умовами завдання|задачі| можна записати таким чином:

а при незмінному X. (збереженні рівня потужності):

Загальна функція витрат має вигляд:

3-й етап|. Визначення функції зміни стану|достатку| системи (вирибничих| потужностей) на i-му| кроці.

В кінці|у кінці| г-го| кроку виробничі потужності мають дорівнювати потужностям на початку (i + 1) -го кроку. Тому функцію зміни сис­теми| на (i + 1) -му кроці запишемо:

Si*-Xi* + Xi+1*.

4-й етап. Запис основного рекурентного співвідношення динамичн­кого| програмування.

Воно має вигляд|вид|:

Тут Wi(Xi) і Wi+1(Xi+1) — оптимальні витрати відповідно на i-м і (i + 1) -м кроках.

5-й етап. Визначення умовних оптимальних витрат|затрат| на останньому четвертому кроці:

W4(X4)= min{f4(X4)+ (₄(X4)}.

У цій формулі:

а при незмінному Xi|. (збереженні|зберіганні| рівня потужності):

де Х3 і Х4 — виробничі потужності в 3-му і 4-му кварталах.

Можна припустити|передбачати|, що виробничі потужності в третьому кварталі відсутні або складають 1, 2, 3,4, 5 одиниць.

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

При Х3 = 0 і Х4 = Про, W4(X4) - 0 + 110(1 - 0) =110 тис. крб.

і Х4 = 1, W4(X4) = 100(1 - 0)+ 0 = 100 тис. крб.

і Х4 = 2, W4(X4) = 100(2 - 0)+ 80(2 - 1)= 280 тис. крб.

Далі, очевидно, що W4(X4) ростиме, тому немає сенсу продовжувати розрахунки. Найменші витрати складають 100 тис. крб.

При Х3 = 1 і Х4 = 0, W4(X4) = 70(1 - 0)+ 110(1 - 0) =180 тис. крб.

І Х4 = 1, W4(X4)= 0 + 0 = 0

і Х4 = 2, W4(X4)= 100(2 - 1)+ 80(2 - 1)= 180 тис. крб. і так далі

При Х3 = 2 і Х4 = 0, W4(X4) = 70(2 - 0)+ 110(1 - 0)= 250 тис. крб.

і Х4 = 1, W4(X4)= 70(2 - 1)+ 0 = 70 тис. крб.

і Х4 = 2, W4(X4)= 0 + 80(2 - 1)= 80 тис. крб. і так далі

При Х3 = 3 і Х4 = 0, W4(X4) = 70(3 - 0)+ 110(1 - 0)= 320 тис. крб.

І Х4 = 1, W4(X4)= 70(3 - 1)+ 0 =140 тис. крб.

і Х4 = 2, W4(X4) = 70(3 - 2)+ 80(2 - 1) =150 тис. крб.

і Х4 = 3, W4(X4)= 0 + 80(3 - 1)= 160 тис. крб. і так далі

При Х3 = 4 і Х4 = 0, W4(X4) = 70(4 - 0)+ 110(1 - 0)= 390 тис. крб.

І Х4 = 1, W4(X4) = 70(4 - 1)+ 0 = 210 тис. крб.

і Х4 = 2, W4(X4)= 70(4 - 2)+ 80(2 - 1)= 220 тис. крб. і так далі

При Х3 = 5 і Х4 = 0, W4(X4)= 70(5 - 0)+ 110(1 - 0) =450 тис. крб.

І Х4 = 1, W4(X4)= 70(5 - 1)+ 0 = 280 тис. крб.

иХ4 = 2, W4(X4) = 70(5 - 2)+ 80(2 - 1)= 290 тис. крб. і так далі

Відберемо всі мінімальні (умовно-оптимальні) значення витрат|затрат| в четвертому кварталі і відповідні ним величини виробничих| потужностей (управління) в таблиці. 1.19.

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

Для третього кварталу (передостанній крок процесу) рекурентне співвідношення має вигляд|вид|:

Таблиця 1.19

Виробничі потужності в 3-му кварталі	Мінімальні витрати 4-го кварталу	Умовно-оптимальні виробничі потужності (управління)
	W4(X)

Де

і

Припустимо, що виробничі потужності в другому кварталі можуть мати рівень від 0 до 5 одиниць. Розрахуємо витрати при цих припущеннях. Значення W4₍X4₎ братимемо з табл.1.19

При Х2 - 0 і Х3 = 0, W3(X3) = 0+110(3 - 0)+ 100 =430 тис. крб.

і Х3 = 1, W3(X3) - 100(1 - 0)+ 110(3 - 1)+ 0 = 320 тис. крб.

і Х3 = 2, W3(X3) = 100(2 - 0)+ 110(3 - 2)+ 70 =380 тис. крб.

і так далі

При Х2 = 1 і Х3 = 0, W3(X3) - 70(1 - 0)+ 110(3 - 0)+ 100 =500 тис. крб.

і Х3 = 1, W3(X3) = 0 + 110(3 - 1)+ 0 =220 тис. крб.

і X3 = 2, W3(X3) =100(2 - 1)+ 110(3 - 2)+ 70 - 280 тис. крб. і так далі

При Х2 = 2 і Х3 = 0, W3(X3)=70(2-0) + 110(3 -0)+ 100=70тыс.руб.

і Х3 = 1, W3(X3) = 70(2 - 1)+ 110(3 - 1)+ 0 = 290 тис. крб.

і Х3 = 2, W3(Х3)= 0 + 110(3 - 2)+ 70 = 180 тис. крб.

иХ3 = 3, W3(X3) =100(3 - 2)+ 0 + 140 = 240 тис. крб. і так далі

При Х2 = 3 і Х3 = 0, W3(X3) - 70(3 - 0)+ 110(3 - 0)+ 100 = 640 тис. крб.

І Х3 = 1, W3(X3) = 70(3 - 1)+ 110(3 - 1)+ 0 =360 тис. руб

і Х3 = 2, W3(X3) =70(3 - 2)+ 110(3 - 2)+ 70 =250 тис. крб.

і Х3= 3, W3(X3)= 0 + 0 + 140 = 140 тис. крб.

і Х3 = 4, W3(X3) = 100(4 - 3)+ 80(4 - 3)+ 210 = 390 тис. крб.

і так далі

Далі, учитывая/что починати з Х3 = 0 немає сенсу, продовжимо розрахунки.

При Х2 = 4 і Х3 = 2, W3(X3)= 70(4 - 2)+ 110(3 - 2)+ 70 =320 тис. крб.

і Х3 = 3, W3(X3) = 70(4 - 3)+ 0 + 140 = 210 тис. крб.

і Х3 = 4, W3(X3) = 0 + 80(4 - 3)+ 210 = 290 тис. крб.

і так далі

При Х2 = 5 і Х3 = 2, W3(X3)= 70(5 - 2)+ 110(3 - 2)+ 70 = 390 тис. крб.

і Х3 = 3, W3(X3) =70(5 - 3)+ 0 + 140 =280 тис. крб.

і Х3 = 4, W3(X3)= 70(5 - 4)+ 80(4 - 3)+ 210 = 380 тис. крб. і так далі

Відберемо всі мінімальні (умовно-оптимальні) значення витрат|затрат| в третьому кварталі і відповідні ним величини виробничих| потужностей в 3-му і 4-му кварталах в таблиці. 1.20.

Таблиця 1.20

Виробничі потужності у 2-му кварталі	Мінімальні витрати|затрати| 3-го кварталу	Умовно-оптимальні потужності в 3-му кварталі	Умовно-оптимальні потужності в 4-му кварталі
хг	W3(Х3)	Х3	Х4

Другий квартал (передостанній процес)

W2(X2) = min {f2(X2) + jj2(X2)+ W3(X3)}.

Де

І

При Х1 = 0 і Х2 - Про, W2(X2) - Про + 110(5 - 0)+ 320 = 870 тис. крб.

І Х2 =1, W2(X2) = 100(1 -0)+ 110(5 - 1)+ 220 = 760тыс. крб.

і Х2 = 2, W2(X2) = 100(2 - 0)+ 110(5 - 2)+ 180 = 710 тис. крб.

і Х2 = 3, W2{X2) = 100(3 - 0)+ 110(5 - 3)+ 140 = 660 тис. крб.

і Х2 = 4, W2{X2) = 100(4 - 0)+ 110(5 - 4)+ 70 = 720 тис. крб.

і так далі

При Х1= 1 і Х2 = 2,№2(Х2)= 100(2-1)+ 110(5-2)+ 180 = 610тыс. крб.

і Х2 = 3, W2(X2) = 100(3 - 1)+ 110(5 - 3)+ 140 = 560 тис. крб.

і Х2 = 4, W2(X2) = 100(4 - 1)+ 110(5 - 4)+ 210 = 620 тис. крб. і так далі

При Х1= 2 і Х2 = 2, W2(X2)= 0 + 110(5 - 2)+ 180 = 510 тис. крб.

і X = 3, W2(X2)= 100(3 - 2)+ 110(5 - 3)+ 140 = 460 тис. крб.

і Х2 = 4, W2(X2)= 100(4 - 2)+ 110(5 - 4)+ 210 = 520 тис. крб.

і так далі

Пріх1 = Зіх2 = 2,1^(Х2)= 70(3-2)+ 110(5-2)+ 180 = 610тыс.руб.

і Х2 = 3, W2(X2)= 0 + 110(5-3)+ 140 = 360 тис. крб.

иХ = 4, W2(X2)= 100(4 - 3)+ 110(5 - 4)+ 2.10 - 420 тис. крб.

і так далі

ПРІХ = 4иХ2 = 2,№2(Х2)= 70(4-2)+ 110(5-2)+180 = 650 тис. крб.

і Х2 = 3, W2{X2) = 70(4 - 3)+ 110(5 - 3)+ 140 = 430 тис. крб.

і Х2 = 4 W2(X2)= 0+110(5 - 4)+ 210 = 320 тис. крб.

і Х2 = 5 W2{X2) = 100(5 - 4)+ 0 + 280 = 380 тис. крб.

і так далі

При X1= 5 і Х2 = 3, W2(Х2)= 70(5-3)+110(5-3) + 140 = 500 тис. крб.

І Х2 = 4, W2(X2) = 70(5 - 4)+ 110(5 - 4)+ 210 = 390 тис. крб.

і Х2 = 5, W2(X2)= 0 + 0 + 280 = 280 тис. крб. і так далі

Відберемо оптимальні витрати|затрати| і відповідні | потужності в таблиці. 1.21.

Для першого кварталу:

де

Таблиця 1.21

Проїзводствен­ниє потужності в 1-му кварталі	Мінімальні витрати в 1-му кварталі	Усл.-опт. потужності в 2-му кварталі	Усл.-опт. потужності у 3-му кварталі	Усл.-опт. потужності у 4-му кварталі
X2	W2 (X2)	X2	X2	X2

Оскільки Х0 задане за умовами завдання, знайдемо умовно оптимальні завдання тільки при Х0 = 2.

При Х0 = 2 і X1= 0, W1 (X1) = 70(2-0)+ 110(2-0)+ 660 = 1020тыс.руб.

І X1= 1, W1 (X1) = 70(2 - 1)+ 110(2 - 1)+ 560 = 740 тис. крб.

і X1= 2, W1 (X1) = 0 + 0 + 460 = 460 тис. крб.

і Х1 = 3, W1 (X1)= 100(3 - 2)+ 80(3 - 2)+ 360 - 540 тис. крб.

і так далі

Таким чином, умовно-оптимальні витрати на першому етапі процесу складають 460 тис. крб. при управлінні X= 2.

7-й етап. Визначення безумовно-оптимальних витрат|затрат| управлінь.

Для витрат в першому кварталі оптимальним є управління X1 = 2. Оскільки X1= Х0, витрати в першому кварталі дорівнюють 0. У другому кварталі оптимальним управлінням є Х2= 3, витрати складають 320 тис. крб. У третьому кварталі оптимальним також є управління Х3= 3, а витрати відповідно складають 0. Нарешті, в четвертому кварталі оптимальне управління Х4 = 1, при якому витрати складуть 140 тис. крб. Загальна сума витрат складе 460 тис. крб.

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

Дата добавления: 2013-12-14