Автор работы: Пользователь скрыл имя, 05 Января 2012 в 15:53, контрольная работа
На территории города имеется три телефонных станции А, Б и В. Незадействованные емкости станций составляют на станции А – 1000 номеров, Б – 400 номеров, В – 500 номеров. Потребности новых районов застройки города в телефонах составляют: 1 - 700, 2 - 600, 3 - 200, 4 - 400 номеров.
Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой за
Самый тяжелый ноль оказывается в клетке (Д, А)с массой 7.
Таким образом множество путей разбивается на 2 подмножества относительно ребра (Д, А). Проведем разбиение, заменив (А, Д) на М (бесконечность в данном контексте будет обозначена так) с целью исключения не-гамильтоновых циклов. Проводим повторную редукцию.
| А | Б | В | Г | Д | Е | ||
| A | М | 16 | 14 | 0 | 4 | 11 | 0 |
| Б | 10 | М | 7 | 0 | 3 | 1 | 0 |
| В | 13 | 14 | М | 0 | 11 | 10 | 0 |
| Г | 0 | 4 | 0 | М | 16 | 11 | 0 |
| Д | М | 7 | 7 | 11 | М | 8 | 7 |
| Е | 6 | 0 | 6 | 8 | 0 | М | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 |
После редукции:
| Б | В | Г | Д | Е | |
| A | 16 | 14 | 0 | М | 10 |
| Б | М | 7 | 0 | 3 | 0 |
| В | 14 | М | 0 | 11 | 9 |
| Г | 4 | 0 | М | 16 | 10 |
| Е | 0 | 6 | 8 | 0 | М |
Сумма констант приведения равна 8.
Повторим процедуру поиска весов нулей
| Б | В | Г | Д | Е | |
| A | 16 | 14 | 0 (10) | М | 10 |
| Б | М | 7 | 0 (0) | 3 | 0 (9) |
| В | 14 | М | 0 (9) | 11 | 9 |
| Г | 4 | 0 (10) | М | 16 | 10 |
| Е | 0 (4) | 6 | 8 | 0 (3) | М |
Два самых тяжелых нуля (А, Г) и (Г, В). Выберем ребро (А,Г) для продолжения процедуры.
Заменяем на М
| Б | В | Г | Д | Е | |
| A | 16 | 14 | М | М | 10 |
| Б | М | 7 | 0 (0) | 3 | 0 (9) |
| В | 14 | М | 0 (9) | 11 | 9 |
| Г | 4 | 0 (10) | М | 16 | 10 |
| Е | 0 (4) | 6 | 8 | 0 (3) | М |
Редуцируем:
| Б | В | Г | Д | Е | ||
| A | 16 | 14 | М | М | 10 | 10 |
| Б | М | 7 | 0 | 3 | 0 | 0 |
| В | 14 | М | 0 | 11 | 9 | 9 |
| Г | 4 | 0 | М | 16 | 10 | 0 |
| Е | 0 | 6 | 8 | 0 | М | 0 |
| 0 | 0 | 0 | 0 | 0 |
Сумма констант равна 19, после редукции и проставления веса:
| Б | В | Д | Е | |
| Б | М | 7 | 3 | 0 (3) |
| В | 5 | М | 2 | 0 (2) |
| Г | 4 | 0 (10) | 16 | 10 |
| Е | 0 (10) | 6 | 0 | М |
Выберем ребро (Г, В) для дальнейшего рассечения
| Б | В | Д | Е | |
| Б | М | 7 | 3 | 0 |
| В | 5 | М | 2 | 0 |
| Г | 4 | М | 16 | 10 |
| Е | 0 | 6 | 0 | М |
Вычеркиваем, редуцируем,
константа приведения 0:
| Б | Д | Е | |
| Б | М | 3 | 0 (3) |
| В | 5 | 2 | 0 (2) |
| Е | 0 (5) | 0 (2) | М |
Следующее ребро (Е, Б).
| Б | Д | Е | |
| Б | М | 3 | М |
| В | 5 | 2 | 0 (2) |
| Е | М | 0 (2) | М |
Вычеркиваем, редуцируем
| Д | Е | |
| Б | 3 | М |
| В | 2 | 0 (2) |
Следующее ребро (В, Е). Последним ребром остается (Б, Д).
Итого оптимальный Гамильтонов цикл:
Д, А
А, Г
Г, В
В, Е
Е, Б
Б, Д
Или: Д->А->Г->В->Е->Б->Д
Суммарный путь: 7+4+6+15+8+13=53
При нахождении пути почтальона целесообразно применять методы численного решения задачи Коммивояжера, желательно с использованием методов автоматизации расчетов и продвинутых алгоритмов (Дейкстра, к примеру, который уменьшает время расчета по сравнению с методом ветвей и границ или полного перебора).
На сетевом графике (рис.4.1) цифры у стрелок показывают в числителе - продолжительность работы в днях, в знаменателе - количество ежедневно занятых работников на её выполнение.
В распоряжении организации, выполняющей этот комплекс работ. Имеется 28 рабочих, которых необходимо обеспечить непрерывной и равномерной работой.
Используя имеющиеся запасы времени по некритическим работам, скорректируйте сетевой график с учётом ограничения по количеству рабочих.
|
Информация о работе Контрольная работа по дисциплине: "Экономико-математические методы и модели"