Задача о назначениях - Особенности математического моделирования задач, связанных с календарным планированием производственных процессов
Задание. Рассматривается вычислительная система состоящая из n вычислительных машин. Имеется n задач. Задана матрица T определяющая время решения i-й задачи на j-м машине. Задачи решаются одновременно с некоторого момента t0. Найти такое распределение задач по вычислительным машинам, чтобы общее время решения всех задач было бы минимальным при условии что на одной машине может решаться только одна задача.
Решение. Исходная матрица имеет вид:
Табл. 9
5 |
5 |
M |
2 |
2 |
7 |
4 |
2 |
3 |
1 |
9 |
3 |
5 |
M |
2 |
7 |
2 |
6 |
7 |
8 |
Для устранения дисбаланса добавляем дополнительные строки.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Табл. 10
3 |
3 |
M |
0 |
0 |
2 |
6 |
3 |
1 |
2 |
0 |
1 |
7 |
1 |
3 |
M |
0 |
2 |
5 |
0 |
4 |
5 |
6 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
Табл. 11
3 |
3 |
M |
0 |
0 |
6 |
3 |
1 |
2 |
0 |
7 |
1 |
3 |
M |
0 |
5 |
0 |
4 |
5 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Табл. 12
3 |
3 |
M |
[0] |
[-0-] |
6 |
3 |
1 |
2 |
[-0-] |
7 |
1 |
3 |
M |
[-0-] |
5 |
[0] |
4 |
5 |
6 |
[-0-] |
[-0-] |
[-0-] |
[-0-] |
[0] |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 3), то решение недопустимое.
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 5, столбец 5, строку 1,столбец 2.
Получаем сокращенную матрицу:
Табл. 13
3 |
3 |
M |
0 |
0 |
6 |
3 |
1 |
2 |
0 |
7 |
1 |
3 |
M |
0 |
5 |
0 |
4 |
5 |
6 |
0 |
0 |
0 |
0 |
0 |
Минимальный элемент сокращенной матрицы (1) вычитаем из всех ее элементов:
Табл. 14
3 |
3 |
M |
0 |
0 |
5 |
3 |
0 |
1 |
0 |
6 |
1 |
2 |
M |
0 |
4 |
0 |
3 |
4 |
6 |
0 |
0 |
0 |
0 |
0 |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
Табл. 15
3 |
4 |
M |
0 |
1 |
5 |
3 |
0 |
1 |
0 |
6 |
1 |
2 |
M |
0 |
4 |
0 |
3 |
4 |
6 |
0 |
1 |
0 |
0 |
1 |
1. Проводим редукцию матрицы по строкам.
В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Табл. 16
3 |
4 |
M |
0 |
1 |
0 |
5 |
3 |
0 |
1 |
0 |
0 |
6 |
1 |
2 |
M |
0 |
0 |
4 |
0 |
3 |
4 |
6 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
Табл. 17
3 |
4 |
M |
0 |
1 |
5 |
3 |
0 |
1 |
0 |
6 |
1 |
2 |
M |
0 |
4 |
0 |
3 |
4 |
6 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Табл. 18
3 |
4 |
M |
[0] |
1 |
5 |
3 |
[0] |
1 |
[-0-] |
6 |
1 |
2 |
M |
[0] |
4 |
[0] |
3 |
4 |
6 |
[0] |
1 |
[-0-] |
[-0-] |
1 |
В результате получаем эквивалентную матрицу Сэ:
Табл. 19
3 |
4 |
M |
0 |
1 |
5 |
3 |
0 |
1 |
0 |
6 |
1 |
2 |
M |
0 |
4 |
0 |
3 |
4 |
6 |
0 |
1 |
0 |
0 |
1 |
4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
Табл. 20
3 |
4 |
M |
[0] |
1 |
5 |
3 |
[0] |
1 |
[-0-] |
6 |
1 |
2 |
M |
[0] |
4 |
[0] |
3 |
4 |
6 |
[0] |
1 |
[-0-] |
[-0-] |
1 |
Cmin = 2 + 2 + 2 + 2 + 0 = 8
Похожие статьи
-
Как известно, человечество в своем стремительном развитии старается все более расширить сферы своей деятельности, сталкиваясь при этом с множеством новых...
-
Календарный производственный программирование однооперационный Все существующие методы решения задач календарного планирования3 по степени достижения...
-
Как и каждый достаточно ярко выраженный класс экономико-математических моделей, совокупность моделей календарного планирования обладает рядом...
-
Изучив основные вопросы, связанные с календарным планированием, подведем итог. Задачи календарного планирования отражают процесс распределения во времени...
-
Задача Джонсона о двух станках Рассмотрим задачу последовательной обработки на двух машинах N различных деталей, если известно время Ai и Bi обработки...
-
К числу приближенных методов оптимизации задач календарного планирования относятся: частичный и направленный перебор, метод Монте-Карло,...
-
Программное управление Относительно просто может быть сформулирована так называемая задача программного управления. В ней предполагается, что управляющие...
-
Известно, что проблема замены старого парка машин новыми, устаревших орудий -- современными -- одна из основных проблем индустрии. Оборудование со...
-
Понятие календарного планирования В условиях оживления и развития отечественной промышленности существенно возрастает интерес к проблемам организации...
-
Табличное представление цен действий и состояний задачи имеет естественные ограничения по масштабируемости задачи на большую размерность. В дискретных...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
1. Л. В. Михайлова.- М-: ИТЦ МАТИ, 2002. Учебное пособие - С. 14-17. Формирование и оперативное управление производственными системами на базе...
-
A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Теоретическое обоснование математического моделирования - Математические методы и модели в экономике
Коммерческая деятельность в том или ином виде сводится к решению таких задач: как распорядиться имеющимися ресурсами для достижения наибольшей выгоды или...
-
С целью формализации задачи введем необходимые обозначения: I - код изделия (i = 1,...,n); ХI - искомый объем выпуска годовой программы по i-му изделию;...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
Для примера рассмотрим вытекающую из общей постановки (3),(4) двухкритериальную () многоэтапную динамическую задачу, с целевыми функциями дохода и потерь...
-
Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....
-
Обычно субъект экономической жизни стремится достичь сразу многих целей. Например, он стремится одновременно следовать и внутренним, и внешним целям, тем...
-
Метод Фогеля - Математическое моделирование в менеджменте и маркетинге
Этап I. Поиск первого опорного плана . 1. Используя метод Фогеля, построим первый опорный план транспортной задачи. Для каждой строки и столбца таблицы...
-
Пусть ограничения (4) не противоречивы, т. е. не пусто множество допустимых решений, а оптимальное решение достигается я в точке для каждой K -ой...
-
Метод конечных элементов - МАтематическое моделирование в экономике
- Метод конечных элементов: триангуляция - Метод конечных элементов ( МКЭ ) -- численный метод решения задач прикладной механики. - Широко используется...
-
Важнейшие математические модели обычно обладают важным свойством Универсальности : принципиально разные реальные явления могут описываться одной и той же...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
ПОСТАНОВКА ЗАДАЧИ - Задача коммивояжера
Пусть имеется п городов. Расстояния между любой парой городов (i, j) известны и составляют dij, где i=1, m; j=1, n; i?j. Если прямого маршрута...
-
Развитие методов многокритериальной оптимизации сложных систем обусловлено необходимостью повышения эффективности их функционирования на основе обобщения...
-
Методы построения решений по математическим моделям - Математическое моделирование в электромеханике
Системы дифференциальных уравнений, полученные для конкретных ти-пов электрических машин, содержат в скрытом виде исчерпывающую инфор-мацию о всех...
-
Метод северо-западного угла - Математическое моделирование в менеджменте и маркетинге
Этап I. Поиск первого опорного плана . 1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается...
-
Ответ: В педагогических исследованиях прикладная направленность математики, понимается как содержательная и методическая связь курса математики с...
-
Среди различных конфигураций искусственных нейронных сетей встречаются такие, при классификации которых по принципу обучения, строго говоря, не подходят...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Экономико-математические методы представляют собой совокупность математических методов (математического программирования, теории вероятностей, теории...
-
Для заданного региона обслуживания с помощью технологии ГИС предоставляется карта автомобильных дорог, на которой указаны пункты, соответствующие...
-
В данном случае анализируемые системы характеризуются не одним набором показателей эффективности, а несколькими: (18) Где - группа показателей...
-
Проникновение математики в экономическую науку связано с преодолением значительных трудностей. В этом отчасти была "по-винна" математика, развивающаяся...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Математическое моделирование - Основы научных исследований
Выше уже указывалось, что Математическое моделирование - это получение решений уравнений, составляющих математическую модель объекта, при изменении...
-
Моделирование процессов управления предполагает последовательное осуществление трех этапов исследования. Первый - от исходной практической проблемы до...
-
В 1930 году Дж. Биркгофом и Дж. фон Нейманом была сформулирована и доказана одна из основных эргодических теорем - теорема о предельных вероятностях:...
Задача о назначениях - Особенности математического моделирования задач, связанных с календарным планированием производственных процессов