складаються обмеження
,
а також допоміжні таблиці значень функції
В
Для кожного значення вибирається мінімальне значення і відповідне йому значення;
в) для k = 3: складаються обмеження
, (причому),
а також таблиця значень функції
В
3. Виконується В«прямий хідВ»:
а) для визначають, з балансового рівняння
висловлюють;
б) знаючи, з таблиці значень визначають, а з балансового рівняння
висловлюють;
) знаючи, з таблиці значень визначають;
г) сумарні витрати за весь період.
Завдання планування на мережах
Граф геометрично являє собою безліч точок, називаних вершинами, з'єднаних лініями: а) спрямованими, які називаються дугами і позначаються стрілками, або б) ненаправленими, які називаються ребрами.
Граф без петель можна задати матрицею інціденцій A, рядки якої відповідають вершинам, а стовпці - дуг, причому елементи матриці A визначаються за формулою
В
Граф можна задати матрицею суміжності вершин S, рядки і стовпці якої відповідають вершинам графа, причому елементи матриці s ij дорівнюють числу дуг/ребер, що йдуть з х i в х j .
Графічний спосіб упорядкування вершин (алгоритм Фалкерсона)
1. Знаходяться вершини графа, в які не входить жодна дуга. Такі вершини утворюють першу групу. p align="justify">. Вершини і виходять з них дуги встановленої групи виключаються з подальшого розгляду. p align="justify">. Встановлюється наступна група вершин, в які не входить жодна дуга. p align="justify">. Якщо процес упорядкування не закінчений, то перехід п. 2. p align="justify">. В отриманому графі, Ізоморфне вихідного, перенумеровуються вершини. p align="justify"> Алгоритм розв'язання задачі про максимальний потік
. Побудувати початковий потік
В
2. На основі заданої мережі побудувати нову мережу:
а) кожна дуга, для якої залишається у новій мережі з первісної rij;
б) кожна дуга, для якої, замінюється на дві: одна - того ж напрямку з пропускною здатністю rij-; а друга - противоположенного напрямки з пропускною здатністю.
. Якщо в новій мережі можна знайти ненульовий потік з I в S, то цей потік додається до початкового. У результаті виходить новий потік і переходять до п. 2. Якщо ненульовий потік знайти неможливо, то потік максимальної потужності побудований. br/>
Алгоритм розрахунку параметрів мережного графіка
В
1) Зобразити події мережевого графіка чотирьохсекторної колами;
) переміщаючись по мережевому графіку від витоку до стоку за зростанням номерів подій, знайти всі ранні терміни настання подій за формулами:
(джерело) і, де
3) переміщаючись по мережевому графіку від стоку до витоку в міру спадання номерів подій, знайти пізні терміни настання подій
(стік) і,
4) визначити резерв часу кожної події;
) виділити критичний шлях - послідовність робіт і подій, які не мають резервів часу;
) обчислити вільний резерв часу і повний резерв часу кожної роботи.
