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

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

Размещено на

Размещено на

КОНТРОЛЬНА РОБОТА

«ДОСЛІДЖЕННЯ ОПЕРАЦІЙ»

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

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

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

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

a?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).

Задача

Для задач 2.0-2.29 наведена таблиця 1, де вказані оцінки часу виконання робіт сітьового графіку, надані виконавцями та експертами.

№ п/п	Робота (i, j)	Оцінки часу виконання робіт, доба
		Оптимістична	Песимістична	Найбільш імовірна
1	(1, 2)	5+N	9+N	6+N
2	(1,3)	2+N	7+N	5+N
3	(1,4)	4+N	10+N	8+N
4	(3,4)	9+N	14+N	11+N
5	(2,5)	7+N	12+N	10+N
6	(4,5)	1+N	4+N	3+N

Тривалість виконання роботи задається двома оцінками - мінімальна і максимальна.

Мінімальна оцінка tmin (i, j) характеризує тривалість виконання роботи при найбільш сприятливих обставинах, а максимальна tmax (i, j) - при найбільш несприятливих умовах.

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

Такі оцінки називаються імовірнісними, і їх очікуване значення tоч (i, j) оцінюється за формулою:

tоч(i,j)=(3 tmin(i,j)+2 tmax(i,j))/5

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

S2(i,j)=0,04(tmax(i,j)-tmin(i,j))2

tоч(1,2)=(3*19+2*15)/5=16,6

tоч(1,3)=(3*17+2*12)/5=14

tоч(1,4)=(3*20+2*14)/5=16,4

tоч(3,4)=(3*24+2*19)/5=21

tоч(2,5)=(3*22+2*17)/5=19

tоч(4,5)=(3*14+2*11)/5=12,2

S2(1,2)=0,04*(19-15)2=0,64

S2(1,3)=0,04*(17-12)2=1

S2(1,4)=0,04*(20-14)2=1,44

S2(3,4)=0,04*(24-19)2=1

S2(2,5)=0,04*(24-19)2=1

S2(4,5)=0,04*(14-11)2=0,36

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

Робота (i,j)	tmin(i,j)	tmax(i,j)	Очікувана тривалість tоч(i,j)	Дисперсія S2(i,j)
1,2	15	19	16.6	0.64
1,3	12	17	14	1
1,4	14	20	16.4	1.44
3,4	19	24	21	1
2,5	17	22	19	1
4,5	11	14	12.2	0.36

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

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

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

Так, для роботи (4,5) до графи 1 поставимо число 2, т.к. на номер 4 закінчуються 2 роботи: (1,4), (3,4).

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

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

...