Создан заказ №3021925
16 мая 2018
Задача о назначениях Фирма получила заказы на разработку пяти программных продуктов
Как заказчик описал требования к работе:
Первые две задачи. n = 7 Еще какойто экономический анализ должен быть этих задач.
Фрагмент выполненной работы:
Задача о назначениях
Фирма получила заказы на разработку пяти программных продуктов. Для выполнения этих заказов решено привлечь пятерых наиболее опытных программистов. Каждый из них должен написать одну программу. В таблице приведены оценки времени (в человеко-днях), необходимого программистам для выполнения каждой из этих работ. Распределение работы между программистами так, чтобы общее количество человеко-дней, затраченное на выполнение всех пяти заказов, было минимальным.
Программа
Программист 1 2 3 4 5
Иванов 53 66 31 69 74
Петров 54 63 39 62 77
Сидоров 51 59 26 68 67
Нефедов 54 66 24 71 80
Галкин 50 72 27 67 82
Решение:
Решим задачу Венгерским методом.
Проводим редукцию матрицы по строкам. (работа была выполнена специалистами author24.ru) В исходной матрице минимальные элементы по строкам находятся в третьем столбце:
53 – 31 66 – 31 31 – 31 69 – 31 74 – 31
54 – 39 63 – 39 39 – 39 62 – 39 77 – 39
51 – 26 59 – 26 26 – 26 68 – 26 67 – 26
54 – 24 66 – 24 24 – 24 71 – 24 80 – 24
50 – 24 72 – 24 27 – 24 67 – 24 82 – 24
Получаем матрицу:
22 35 0 38 43
15 24 0 23 38
25 33 0 42 41
30 42 0 47 56
23 45 0 40 55
Затем такую же операцию редукции проводим по столбцам и получаем матрицу:
7 11 0 15 5
0 0 0 0 0
10 9 0 19 3
15 18 0 24 18
8 21 0 17 17
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 3). Другие нули в строке 1 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 1), (2; 2), (2; 4).
Фиксируем нулевое значение в клетке (2, 5). Другие нули в строке 2 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 1), (2; 2), (2; 4).
В итоге получаем следующую матрицу:
7 11 [0] 15 5
[0] [0] [0] [0] [0]
10 9 [0] 19 3
15 18 [0] 24 18
8 21 [0] 17 17
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 2), то решение недопустимое.
Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 2, столбец 3. Получаем сокращенную матрицу:
7 11 0 15 5
0 0 0 0 0
10 9 0 19 3
15 18 0 24 18
8 21 0 17 17
Минимальный элемент сокращенной матрицы:
min{7, 11, 15, 5, 10, 9, 19, 3, 15, 18, 24, 18, 8, 21, 17, 17}=3
вычитаем из всех ее элементов и складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
4 8 0 12 2
0 0 3 0 0
7 6 0 16 0
12 15 0 21 15
5 18 0 14 14
Проводим редукцию матрицы по строкам и столбцам. После вычитания минимальных элементов получаем полностью редуцированную матрицу.
Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 3). Другие нули в строке 1 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (3; 5), (2; 1), (2; 2), (2; 4).
Фиксируем нулевое значение в клетке (2, 5). Другие нули в строке 2 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (3; 5), (2; 1), (2; 2), (2; 4).
В итоге получаем следующую матрицу:
4 8 [0] 12 2
[0] [0] 3 [0] [0]
7 6 [0] 16 [0]
12 15 [0] 21 15
5 18 [0] 14 14
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 2), то решение недопустимое.
Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 2, столбец 3, строку 3. Получаем сокращенную матрицу:
4 8 0 12 2
0 0 3 0 0
7 6 0 16 0
12 15 0 21 15
5 18 0 14 14
Минимальный элемент сокращенной матрицы
min{4, 8, 12, 2, 12, 15, 21, 15, 5, 18, 14, 14}=2
вычитаем из всех ее элементов и затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
2 6 0 10 0
0 0 5 0 0
7 6 2 16 0
10 13 0 19 13
3 16 0 12 12
Проводим редукцию матрицы по строкам и столбцам. После вычитания минимальных элементов получаем полностью редуцированную матрицу.
Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 1 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 1), (2; 2).
Фиксируем нулевое значение в клетке (2, 4). Другие нули в строке 2 и столбце 4 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 1), (2; 2).
В итоге получаем следующую матрицу:
2 6 [0] 10 [0]
[0] [0] 5 [0] [0]
7 6 2 16 [0]
10 13 0 19 13
3 16 0 12 12
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 2), то решение недопустимое.
Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 2, столбец 3, столбец 5. Получаем сокращенную матрицу:
2 6 0 10 0
0 0 5 0 0
7 6 2 16 0
10 13 0 19 13
3 16 0 12 12
Минимальный элемент сокращенной матрицы
min{2, 6, 10, 7, 6, 16, 10, 13, 19, 3, 16, 12}=2
вычитаем из всех ее элементов и затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
0 4 0 8 0
0 0 7 0 2
5 4 2 14 0
8 11 0 17 13
1 14 0 10 12
Проводим редукцию матрицы по строкам и столбцам. Затем методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 1 и столбце 5 вычеркиваем...Посмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
20 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
17 мая 2018
Заказ завершен, заказчик получил финальный файл с работой
5
Задача о назначениях
Фирма получила заказы на разработку пяти программных продуктов.jpg
2018-05-20 12:39
Последний отзыв студента о бирже Автор24
Общая оценка
5
Положительно
Автор очень хороший. Помог с самостоятельной работой, все сделано было раньше срока, и качественно, от преподавателя никаких замечаний по сам. работе не было. Спасибо вам!
Хочешь такую же работу?
300 ₽
