Контрольная работа №2

Контрольная работа №2

Вариант №26

Задача №4

Разместить четыре датчика на четырех объектах таким образом, чтобы стоимость такого размещения была минимальной.

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

В каждом столбце вычитаем минимальный элемент соответствующего столбца, получим:

Рассмотрим сначала строки матрицы стоимости . Строки 2,3 и 4 имеют по одному нулю. Взяв эти строки в порядке возрастания их номеров, произведем вначале назначение, соответствующее элементу и вычеркнем нулевой элемент , т. к. в 3-ем столбце может быть только один нулевой элемент. Затем проведем назначение, соответствующее элементу Рассмотрим столбцы матрицы стоимости назначений с учетом вычеркнутых нулевых элементов по строкам. Второй и четвертый столбцы содержат по одному нулевому элементу, проведем третье назначение, соответствующее элементу . В четвертом столбце назначение невозможно, т. к. нулевой элемент стоит в первой строке, а назначение в ней уже выполнено. В результате матрица стоимостей приняла следующий вид:

Поскольку полного назначения нулевой стоимости не может быть получено, необходимо провести дельнейшую модификацию редуцированной матрицы стоимости.

Получим новые нулевые элементы. Определим для редуцированной матрицы стоимостей минимальное множество строк и столбцов, содержащих нулевые элементы, и найдем минимальный элемент вне данного множества по следующему плану:

1) Определим количество нулей в строках и столбцах матрицы стоимости : соответственно имеем: 3,1,1,1 ­ – в строках и 2,1,2,1 – в столбцах;

2) Максимальное число нулей содержит строка 1– три нуля и столбец 3– два нуля. Удаляем элементы строки 1.

3) Число оставшихся нулей после удаления строки 1 равно 1,1 и 1 в строках 2, 3 и 4 соответственно. Для столбцов число оставшихся нулей равно 2, 1, 2, 1, выбираем столбец 3 и удаляем его элементы. Остался только один нуль элемент поэтому удаляем строку 4 и получаем следующую матрицу-таблицу:

4) Минимальным элементом полученной матрицы-таблицы является 2. Вычитая его из всех оставшихся элементов, получаем новую матрицу таблицу:

Прибавляя значение 2 ко всем элементам матрицы ,расположенными на пересечении вертикальной и двух горизонтальных штриховых линий, получаем новую редуцированную матрицу:

Новая матрица содержит еще один нуль, элемент .

Повторяем с пункта 1.

1) количество нулей в строках и столбцах матрицы : 3,1,2,1 – в строках и 2,2,2,1 – в столбцах.

2) Максимальное число нулей содержит строка 1, удаляем ее элементы.

3) Число нулей, оставшихся после удаления строки 1 равно 1,2,1 в строках, и 1,1,2 в столбцах. Выбираем столбец 3 и удаляем его элементы. Осталось еще два нуля в строках 3 и 4. удаляем их элементы. Получим следующую матрицу таблицу:

4) Минимальным элементом полученной матрицы является 4. Вычитаем его из всех оставшихся элементов получаем новую матрицу-таблицу:

Прибавляем значение 4 ко всем элементам матрицы , расположенными на пересечении штриховых линий, получаем новую матрицу:

Проведем назначение согласно матрице , соответствующее элементу и зачеркнем нули и . Затем проведем назначение элементу и зачеркнем , и назначим и .

Получим оптимальное решение:

,

Вычислим минимальное значение целевой функции: