Дослідження операцій

Критерій вибору пріоритету конкуруючих за ресурсами робіт при визначенні порядку їх виконання

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

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

Даній залежності властивий обернено пропорційний зв’язок, тобто зменшення тривалості роботи пропорційне зростанню її вартості (рис.1). Для кожної роботи (i, j) має місце:

i, j≤i, j≤bi, j,

де а(i, j) - мінімальна (інтенсивна) тривалість роботи (i, j); b(i, j) - максимальна (екстенсивна) тривалість роботи (i, j).

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

При цьому вартість С(i,j) роботи (i,j) прийме значення C(i, j) [Cmin (i, j);Cmax (i, j)], де Cmin (i, j) - вартість при максимальній тривалості роботи (i, j), C max (i, j) - вартість при мінімальній тривалості роботи (i, j).

Рис. 1. Залежність вартості роботи від її тривалості.

Щоб провести криву, виконаємо апроксимацію по прямій і знайдемо зміну вартості роботи ΔC(i, j) при скороченні її тривалості на величину [b(i, j)− t(i, j)]:

ΔC(i, j) = [b(i, j)− t(i, j)]Ч k(i, j),

показує затрати на прискорення роботи (i, j) (у порівнянні з максимальною тривалістю) на одиницю часу; α- кут нахилу апроксимованої прямої.

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

У результаті, початкова вартість програми

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

Задача

У задачах 1.5-1.14 знайти глобальний екстремум функції z в області рішень системи нерівностей.

Розвязок. Область допустимих рішень - OAB. Лініями рівня є гіперболічна параболоїда. Глобальний мінімум знаходиться в точці O (0, 0). Максимальне значення цільова функція має в точці В(2,5, 3). Тому

Відповідь

Глобальний максимум, дорівнює 7,5, досягається в точці В(2,5, 3), глобальний мінімум, дорівнює нулю, - в точці O (0, 0).