|
Читайте также: |
Задача про призначення.
ЗАВДАННЯ. На підставі вихідних даних вирішити задачу про призначення, тобто установити оптимальне закріплення транспортних засобів за визначеними рейсами і порядок відправлення цих транспортних засобів.
Методичні вказівки.
Задача про призначення є однієї з приватних задач лінійного програмування. Ця задача в порівнянні зі звичайною транспортною задачею лінійного програмування має ту особливість, що постачання не можна розділити так, як це робиться в звичайній стандартній транспортній задачі. Подібна ситуація виникає в тих випадках, коли необхідно розподілити робочі місця між різними працівниками, коли необхідно зробити розподіл транспортних засобів і т.д. Якщо виникає подібне обмеження, то в подібних випадках можна використовувати особливий алгоритм рішення задачі про призначення.
У даному прикладі задачу необхідно вирішити для наступних умов. Між пунктами А і В здійснюються зустрічні перевезення, які можна умовно представити в наступній схематичній формі:
 |
Таблиця – Вихідні дані для практичної роботи № 2
| Варіант | Відправлення з пункту А | Відправлення з пункту В | t, година. | ||||||||
| I | II | III | IV | V | |||||||
| 5-00 | 6-00 | 7-30 | 14-30 | 16-30 | 0-30 | 9-30 | 16-00 | 18-30 | 20-30 | 5,5 | |
| 4-00 | 5-30 | 8-00 | 12-30 | 21-00 | 1-30 | 7-00 | 13-30 | 16-30 | 23-30 | 4,0 | |
| 3-30 | 5-00 | 8-30 | 13-30 | 21-30 | 3-30 | 6-00 | 12-30 | 17-30 | 23-00 | 5,5 | |
| 4-30 | 5-00 | 9-30 | 13-30 | 22-00 | 2-30 | 7-30 | 10-00 | 16-30 | 23-30 | 4,5 | |
| 5-00 | 6-30 | 9-30 | 18-00 | 23-30 | 4-30 | 8-00 | 16-30 | 17-00 | 21-30 | 6,0 | |
| 5-30 | 6-00 | 10-30 | 14-30 | 17-30 | 3-00 | 6-30 | 13-30 | 19-30 | 20-00 | 4,5 | |
| 4-00 | 6-30 | 10-30 | 15-00 | 21-00 | 3-30 | 7-00 | 11-30 | 18-30 | 22-00 | 6,0 | |
| 4-30 | 7-00 | 11-30 | 15-30 | 17-00 | 2-30 | 8-00 | 11-30 | 16-30 | 19-30 | 4,5 | |
| 3-00 | 5-30 | 11-30 | 15-00 | 19-30 | 5-30 | 7-00 | 12-30 | 22-00 | 23-30 | 5,5 | |
| 3-30 | 6-00 | 7-00 | 15-30 | 17-00 | 0-30 | 5-00 | 11-00 | 16-00 | 18-00 | 2,5 | |
| 4-00 | 6-30 | 7-30 | 16-00 | 17-30 | 1-00 | 5-30 | 11-30 | 16-30 | 18-30 | 3,0 | |
| 4-30 | 7-00 | 8-00 | 12-30 | 18-00 | 1-30 | 6-00 | 12-00 | 17-00 | 19-00 | 3,5 | |
| 5-00 | 5-30 | 8-30 | 13-00 | 18-30 | 2-00 | 6-30 | 12-30 | 17-30 | 19-30 | 4,0 | |
| 5-30 | 6-00 | 9-00 | 13-30 | 19-00 | 2-30 | 7-00 | 13-00 | 18-00 | 20-00 | 4,5 | |
| 1-00 | 6-30 | 9-30 | 14-00 | 19-30 | 3-00 | 7-30 | 13-30 | 18-30 | 20-30 | 5,0 | |
| 1-30 | 7-00 | 10-00 | 14-30 | 20-00 | 3-30 | 8-00 | 14-00 | 19-00 | 21-00 | 5,5 | |
| 2-00 | 4-00 | 10-30 | 15-00 | 20-30 | 4-00 | 8-30 | 14-30 | 18-30 | 21-30 | 6,0 | |
| 2-30 | 4-30 | 11-00 | 15-30 | 21-00 | 4-30 | 9-00 | 15-00 | 19-00 | 22-00 | 6,5 | |
| 3-00 | 5-30 | 11-30 | 16-00 | 21-30 | 5-00 | 9-30 | 15-30 | 19-30 | 22-30 | 1,5 | |
| 3-30 | 5-00 | 12-00 | 16-30 | 17-00 | 5-30 | 10-00 | 16-00 | 20-00 | 23-00 | 2,0 | |
| 4-00 | 6-30 | 7-00 | 12-30 | 17-30 | 0-30 | 10-30 | 16-30 | 20-30 | 23-30 | 2,5 | |
| 4-30 | 6-00 | 7-30 | 13-00 | 18-00 | 1-00 | 11-00 | 17-00 | 18-30 | 19-00 | 3,0 | |
| 5-00 | 7-30 | 8-00 | 13-30 | 18-30 | 1-30 | 5-00 | 17-30 | 19-00 | 19-30 | 3,5 | |
| 5-30 | 7-00 | 8-30 | 14-00 | 19-00 | 2-00 | 5-30 | 11-30 | 19-30 | 20-00 | 4,0 | |
| 1-00 | 4-30 | 9-00 | 14-30 | 19-30 | 2-30 | 6-00 | 12-00 | 20-00 | 20-30 | 4,5 | |
| 1-30 | 5-00 | 9-30 | 15-00 | 20-00 | 3-00 | 6-30 | 12-30 | 20-30 | 21-00 | 5,0 | |
| 2-00 | 5-30 | 10-00 | 15-30 | 20-30 | 3-30 | 7-00 | 13-00 | 16-30 | 21-30 | 5,5 | |
| 2-30 | 6-00 | 10-30 | 16-00 | 21-00 | 4-00 | 7-30 | 13-30 | 17-00 | 22-00 | 6,0 | |
| 3-00 | 6-30 | 11-00 | 12-30 | 17-00 | 4-30 | 8-00 | 14-00 | 17-30 | 22-30 | 1,5 | |
| 3-30 | 4-00 | 11-30 | 13-30 | 17-30 | 5-00 | 8-30 | 14-30 | 18-00 | 23-00 | 2,0 |
Відомий час відправлення кожного рейса, час руху з урахуванням часу на виконання операцій завантаження і вивантаження.
Основною задачею є закріпити наявні (чи орендовані) транспортні засоби за двома визначеними рейсами таким чином, щоб загальна тривалість простоїв транспортних засобів була мінімальною. Для рішення поставленої задачі варто виконувати визначені дії в наступній послідовності:
1. Відповідно до вихідних даних власного варіанта, представленими в таблиці, складається дві вихідні таблиці можливих простоїв транспортних засобів у залежності від того чи іншого закріплення рейсів та зведена таблиця простоїв. При цьому варто враховувати, що загальна тривалість простоїв не повинна перевищувати 24 години.
2. Робиться спроба (шляхом обведення та закреслення нулів) оптимального закріплення рейсів.
3. Відмічаються можливі строки та стовбці:
- відмічається кожна строка, яка не має обведених нулів;
- відмічається кожен стовбець, який має хоч один закреслений нуль в одній з відмічених строк;
- відмічається кожна строка, яка має хоч один обведений нуль в одному з відмічених стовбців;
- дії повторюються до тих пір, коли не будуть відмічені усі можливі строки та стовбці.
4. Викреслюються усі відмічені стовбці та невідмічені строки.
5. У частині таблиці, що залишилася невикресленою, знаходять мінімальне значення. Цю величину віднімають від усіх елементів невикреслених стовбців та прибавляють до усіх елементів викреслених строк. В результаті цієї операції у таблиці з’являються нові нулі.
6. Дії повторюються починаючи з пункту 2.
Дата добавления: 2015-07-11; просмотров: 144 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Варіанти завдань | | | Основні поняття |