77-7) 10 + (77-26) 15 + (77-28) 5 + (77-37) 20 + (77 - 40) 5 + (77-48) 25 + (77-60) 15 + (78-77) 30 + (86-77) 10 + (92-77) 65 = 4820 - Це значення на 10км більше за оптимальне. p> Порахуємо пробіг для 79км:
(79-7) 10 + (79-26) 15 + (79-28) 5 + (79-37) 20 + (79-40) 5 + + (79-46) 25 + (79-60) 15 + (79-78) 30 + (86-79) 10 + (92-79) 65 = 4860 - це значення аж на 50 кілометрів перевищує оптимальне.
Тема 2. Де розмістити бригади або задача про призначення
Завдання № 2
Фірма В«АвтотрансВ» в порядку підготовки до Євро 2012 готує маршрут В«Харків-ЯлтаВ», який обслуговують екіпажі або бригади автобусів. Серед численних проблем фірми В«АвтотрансВ» досить важлива проблема місця проживання бригад автобусів. При вирішенні її потрібно мінімізувати, враховуючи вимоги розкладу та загальний час перебування поза домом, при цьому виходять з абсолютно очевидних фінансових міркувань, так як оплата бригад не залежить від того чи знаходяться вони в дорозі або чекають свого повернення додому. Крім того, беруться до уваги міркування соціального характеру - не розлучати надовго главу сім'ї з іншими її членами. З іншого боку існують фізіологічні межі роботи: жодна з бригад не повинна пускатися в рейс, НЕ відпочивши в протягом хоча б чотирьох годин. Разом з тим бригада не повинна чекати рейсу більше ніж 24 години.
У цих умовах завдання може бути сформульована таким чином:
Де повинні жити бригади? Які рейси вони повинні обслуговувати, щоб сумарний час, який всі бригади втрачають на очікування зворотного рейсу, було б мінімальним, при обмеженні, що час очікування кожної бригади має бути більше 4 і менше 24 годин.
Для вирішення завдання необхідно знати передбачуване розклад фірми В«АвтотрансВ» за маршрутом В«Харків-ЯлтаВ» і В«Ялта-ХарківВ»
Харків - Ялта
Відправлення з Харкова
Позначення рейсу
Прибуття до Ялти
Час шляху 6 годин
06-00
a
12-00
07-30
b
13-30
11-30
c
17-30
19-30
d
01-00
00-30
e
06-30
Ялта - Харків
Прибуття до Харкова
Номер рейсу
Відправлення з Ялти
Час шляху 6 годин
11-30
1
05-30
15-00
2
09-00
21-00
3
15-00
00-30
4
18-30
06-00
5
00-00
Ітерація 1.
Припустимо, що всі бригади живуть у Харкові і обслуговують рейси, які йдуть на Ялту.
Табл. 1
1 2 3 4 5
17.5
21
3
6.5
12
a
16
19.5
1.5
5
10.5
b
12
15.5
21.5
1
6.5
c
4.5
8
14
17.5
13
d
23
2.5
8.5
12
17,5
e
Оскільки всі бригади живуть у Харкові, а рейси позначені з Харкова a, b, c, d, e то заповнення матричної таблиці проводиться по рядках.
Ітерація 2
Табл. 2 містить розрахунок, що базується на припущенні, що всі бригади живуть в Ялті. У цьому випадку рейси позначаються номерами (1, 2, 3, 4, 5) і варіанти: a, b, c, d, e. Отже, будемо заповнювати колонки. p> Табл.2
1
2
<...
