Контрольная работа по "Проектирование АСОиУ"

lign="justify">       Распределить  семь функциональных задач по сем  центрам обработки информации, если известно время решения каждой задачи в каждом центре обработки (матрица стоимости распределения).

       Математическая  постановка задачи:

  – целевая функция, 

m, n – количество задач и центров обработки соответственно,

; – каждая задача может решаться только в одном центре,

; – каждый центр может обрабатывать не более одной задачи,

 –  матрица решения о распределении  задач по центрам,

 –  матрица стоимости распределения.

       Для решения задачи составить программу  для заполнения матрицы С случайными целыми числами, распределенными по равномерному закону на интервале (26, 34).  

       Решение.

       Текст программы для заполнения матрицы  С случайными целыми числами, распределенными  по равномерному закону на интервале (26, 34).

 

       Итак,  

       1. В каждом столбце матрицы С найдем минимальный элемент и вычтем его из элементов столбца. 

       В каждой строке матрицы найдем минимальный  элемент и вычтем его из элементов строки. 

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

       2. Проверим, равно ли число независимых  нулей размерности задачи. Количество независимых нулей – 5 (размерность задачи – 7). Оптимальный план не найден.

       3. Отметим столбцы, содержащие независимые нули плюсиком:

       4. Среди невыделенных элементов  найдем минимальный (h=0).

       5. Выделим ноль, соответствующий h, штрихом. В одной строке с ним есть 0*. Отметим соответствующую строку плюсиком, а со столбца выделение снимем.

       Повторим  пункты 4 и 5.

       0* в одной строке с 0’ нет.

       6. Построим цепочку, начиная с  последнего 0’, в которой будут  чередоваться 0* и 0’. Причем, переход  от 0’ к 0* – по столбцу, а  от 0* к 0’ – по строке.

       Проведем  замену в цепочке 0’ на 0* и наоборот. Произошло увеличение количества независимых нулей на 1. Выполним проверку оптимальности плана.

       7. Проверим, равно ли число независимых  нулей размерности задачи. Количество независимых нулей – 6 (размерность задачи – 7). Оптимальный план не найден.

       8. Отметим столбцы, содержащие независимые  нули плюсиком:

 

       9. Среди невыделенных элементов найдем минимальный (h=0). Выделим ноль, соответствующий h, штрихом (0’). В одной строке с ним есть 0*. Отметим соответствующую строку плюсиком, а со столбца выделение снимем.

 
 
 
 

       Повторим  пункт 9.