Контрольная работа по дисциплине Методы оптимальных решений часть 1 (название дисциплины)

• Название: Контрольная работа по дисциплине Методы оптимальных решений часть 1 (название дисциплины)
• Дата: 02.11.2018
• Размер: 392.5 Kb.
• Имя файла: zadachi_1.doc
• Тип: Контрольная работа; #55227
• страница: 4 из 4

Минимальный элемент сокращенной матрицы (min(290, 590, 140, 210, 480, 90, 390, 770, 240) = 90) вычитаем из всех ее элементов:

0	0	300	210	390
200	0	520	500	50
120	450	0	390	0
300	40	0	680	150
0	10	10	0	0

Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:

0	90	390	210	390
200	0	520	500	50
120	450	0	390	0
300	40	0	680	150
0	100	100	0	0

1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент.
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 1). Другие нули в строке 1 и столбце 1 вычеркиваем. 
Фиксируем нулевое значение в клетке (2, 2). Другие нули в строке 2 и столбце 2 вычеркиваем. 
Фиксируем нулевое значение в клетке (3, 5). Другие нули в строке 3 и столбце 5 вычеркиваем. 
Фиксируем нулевое значение в клетке (4, 3). Другие нули в строке 4 и столбце 3 вычеркиваем. 
Фиксируем нулевое значение в клетке (5, 4). Другие нули в строке 5 и столбце 4 вычеркиваем. 
В итоге получаем следующую матрицу:

[0]	90	390	210	390
200	[0]	520	500	50
120	450	[-0-]	390	[0]
300	40	[0]	680	150
[-0-]	100	100	[0]	[-0-]

Количество найденных нулей равно k = 5. В результате получаем эквивалентную матрицу Сэ:

0	90	390	210	390
200	0	520	500	50
120	450	0	390	0
300	40	0	680	150
0	100	100	0	0

4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.

[0]	90	390	210	390
200	[0]	520	500	50
120	450	[-0-]	390	[0]
300	40	[0]	680	150
[-0-]	100	100	[0]	[-0-]

Cmin = 200 + 310 + 200 + 200 + = 910