Автор работы: Пользователь скрыл имя, 20 Ноября 2011 в 18:12, контрольная работа
Информация о проекте задана перечнем работ, их продолжительностью и последовательностью.
Повторим пункт 9.
| + | + | + | + | ||||
| 1 | 1 | 0* | 5 | 5 | 7 | 4 | |
| 0* | 2 | 2 | 4 | 1 | 3 | 0’ | + |
| 10 | 2 | 6 | 0* | 1 | 6 | 3 | |
| 7 | 0 | 2 | 0 | 0* | 6 | 0’ | + |
| 8 | 3 | 6 | 1 | 5 | 0* | 6 | |
| 11 | 0* | 2 | 2 | 1 | 1 | 5 | |
| 8 | 6 | 5 | 0 | 5 | 1 | 6 |
10. Среди невыделенных элементов нулей нет. Минимальный элемент h=1. Вычтем h из всех невыделенных элементов матрицы (которые не относятся к выделенным столбцам и строкам), и прибавим h к элементам, находящимся на пересечении выделенных столбцов и строк.
| + | + | + | + | ||||
| 0 | 1 | 0* | 5 | 4 | 7 | 3 | |
| 0* | 2 | 2 | 4 | 1 | 3 | 0’ | + |
| 9 | 2 | 6 | 0* | 0 | 6 | 2 | |
| 7 | 0 | 2 | 0 | 0* | 6 | 0’ | + |
| 7 | 3 | 6 | 1 | 4 | 0* | 5 | |
| 10 | 0* | 2 | 2 | 0 | 1 | 4 | |
| 7 | 6 | 5 | 0 | 4 | 1 | 5 |
Повторим пункт 9.
| + | + | ||||||
| 0’ | 1 | 0* | 5 | 4 | 7 | 3 | + |
| 0* | 2 | 2 | 4 | 1 | 3 | 0’ | + |
| 9 | 2 | 6 | 0* | 0’ | 6 | 2 | + |
| 7 | 0 | 2 | 0 | 0* | 6 | 0’ | + |
| 7 | 3 | 6 | 1 | 4 | 0* | 5 | |
| 10 | 0* | 2 | 2 | 0 | 1 | 4 | |
| 7 | 6 | 5 | 0 | 4 | 1 | 5 |
Повторим пункт 9.
| + | + | ||||||
| 0’ | 1 | 0* | 5 | 4 | 7 | 3 | + |
| 0* | 2 | 2 | 4 | 1 | 3 | 0’ | + |
| 9 | 2 | 6 | 0* | 0’ | 6 | 2 | + |
| 7 | 0 | 2 | 0 | 0* | 6 | 0’ | + |
| 7 | 3 | 6 | 1 | 4 | 0* | 5 | |
| 10 | 0* | 2 | 2 | 0 | 1 | 4 | |
| 7 | 6 | 5 | 0’ | 4 | 1 | 5 | + |
0* в одной строке с 0’ нет.
11. Построим цепочку, начиная с последнего 0’, в которой будут чередоваться 0* и 0’. Причем, переход от 0’ к 0* – по столбцу, а от 0* к 0’ – по строке.
| + | + | ||||||
| 0’ | 1 | 0* | 5 | 4 | 7 | 3 | + |
| 0* | 2 | 2 | 4 | 1 | 3 | 0’ | + |
| 9 | 2 | 6 | 0* | 0’ | 6 | 2 | + |
| 7 | 0 | 2 | 0 | 0* | 6 | 0’ | + |
| 7 | 3 | 6 | 1 | 4 | 0* | 5 | |
| 10 | 0* | 2 | 2 | 0 | 1 | 4 | |
| 7 | 6 | 5 | 0’ | 4 | 1 | 5 | + |
Проведем замену в цепочке 0’ на 0* и наоборот. Произошло увеличение количества независимых нулей на 1. Выполним проверку оптимальности плана.
| 0 | 1 | 0* | 5 | 4 | 7 | 3 | |
| 0* | 2 | 2 | 4 | 1 | 3 | 0 | |
| 9 | 2 | 6 | 0 | 0* | 6 | 2 | |
| 7 | 0 | 2 | 0 | 0 | 6 | 0* | |
| 7 | 3 | 6 | 1 | 4 | 0* | 5 | |
| 10 | 0* | 2 | 2 | 0 | 1 | 4 | |
| 7 | 6 | 5 | 0* | 4 | 1 | 5 |
7.
Проверим, равно ли число независимых
нулей размерности задачи. Количество
независимых нулей – 7 (размерность задачи
– 7). Оптимальный план найден.
Найдем
значение целевой функции.
ЗАДАЧА №6 (вариант 6)
Составить план передачи типовых сообщений от четырех информационных центров (ИЦ) на четыре центра обработки информации (ЦО), если известны: наличие требующих обработки сообщений в каждом ИЦ, возможность каждого ЦО по обработке сообщений и матрица стоимости (затрат) передачи сообщений от ИЦ к ЦО.
– целевая функция,
; – каждая задача может решаться только в одном центре,
; – каждый центр может обрабатывать не более одной задачи,
– матрица решения (план),
– матрица стоимости закрепления,
- наличие сообщений в i-том ИЦ (правый столбец таблицы),
- возможность j-того ЦО по обработке сообщений (нижняя строка)
| 3 | 3 | 9 | 2 | 10 | |
| 7 | 8 | 7 | 4 | 13 | |
| 8 | 6 | 3 | 2 | 27 | |
| 4 | 6 | 7 | 7 | 31 | |
| 13 | 22 | 25 | 21 |
Решение.
1.
Построим начальный план. Для
этого в каждом столбце
Аналогичную
операцию проведем для строк.
В нулевые элементы матрицы стоимости методом северо-западного угла назначим перевозки и запишем их в матрицу Х (начиная с левого верхнего угла, назначаются максимальные перевозки).
| Х= | 10 | . | . | |
| 13 | ||||
| 25 | 2 | |||
| 3 | . |
Вычислим невязки по строкам и столбцам.
| Х= | 10 | . | . | 0 | |
| 13 | 0 | ||||
| 25 | 2 | 0 | |||
| 3 | . | 28 | |||
| 0 | 22 | 0 | 6 |
Оптимальный план не найден.
3.
Выделим столбцы в матрице
С, где невязка
| + | + | |||
| С= | 0 | 0 | 6 | 0 |
| 2 | 3 | 2 | 0 | |
| 5 | 3 | 0 | 0 | |
| 0 | 2 | 3 | 4 |
Информация о работе Контрольная работа по "Проектирование АСОиУ"