Принятие проектных решений в задачах производственного и операционного менеджмента
Курсовой проект - Экономика
Другие курсовые по предмету Экономика
столбцов найти ячейку с наименьшим значением. Вычесть это значение из содержимого всех невычеркнутых ячеек и добавить это значение к содержимому всех ячеек, находящихся на пересечении линий. Повторить шаг 3.
Проиллюстрируем этот алгоритм на примере решения задачи о назначении 5 видов работ любой из 5 машин (n=5). Матрица стоимостей каждой комбинации работа/машина приведена в таблице 2-1.
Таблица 2-1. Матрица назначений, содержащая затраты на выполнение работ каждой машиной
МашиныРаботаABBDE1$5$6$4$8$32$6$4$9$8$53$4$3$2$5$44$7$2$4$5$35$3$6$4$5$5
Процедура решения задачи приведена в таблице 2-2.
Таблица 2-2. Процедура решения задачи о назначениях
Шаг 1: приведение строк - наименьшее значение вычитается из содержимого всех ячеек в строке матрицы
МашиныРаботыABBDE1$2$3$1$5$02$2$0$5$4$13$2$1$0$3$24$5$0$2$3$15$3$6$4$5$5
Шаг 2: приведение столбцов - наименьшее значение вычитается из содержимого всех ячеек в столбце матрицы
МашиныРаботыABCDE1$2$3$1$3$02$2$0$5$2$13$2$1$0$1$24$5$0$2$1$15$0$3$1$0$2
Шаг 3: выполнение "линейного теста" - число линий, вычеркивающих все нулевые ячейки, равно 4; т.к.n=5, перейти к шагу 4.
МашиныРаботыABCDE1$2$3$1$3$02$2$0$5$2$13$2$1$0$1$24$5$0$2$1$15$0$3$1$0$2
Шаг 4: Наименьшее значение среди содержимого невычеркнутых ячеек равно 1, 1 вычитается из содержимого всех невычеркнутых ячеек матрицы, 1 добавляется к содержимому ячеек, находящихся на пересечении линий
МашиныРаботыABCDE1$1$3$0$2$02$1$0$4$1$13$2$2$0$1$34$4$0$1$0$15$0$4$1$0$3
Оптимальное решение, найденное с помощью "линейного" теста
МашиныРаботыABCDE1$1$3$0$2$02$1$0$4$1$13$2$2$0$0$34$4$0$1$0$15$0$4$1$0$3
Оптимальные назначения и их стоимости
работа 1 - машине E $3 работа 4 - машине D $5
работа 2 - машине B $4 работа 5 - машине A $3
работа 3 - машине C $2 Суммарная стоимость $17
Нематематическое логическое обоснование метода назначения - минимизировать потери прибыли. Например, при назначении работы 1 машине A вместо машины E убыток составит $2 ($5-$3). Программа, реализующая метод назначений, эффективно выполняет сравнения стоимостей для всего множества альтернативных назначений посредством приведения строк и столбцов.
Метод решения задачи назначений требует, чтобы количество должностей и кандидатов было равным. Если это условие не выполняется, компьютер должен увеличить матрицу так, чтобы она стала квадратной. Например, если 5 работников претендуют на 4 должности, компьютер дополнит матрицу до размера 5*5 за счет введения фиктивной должности. Все значения стоимостей для фиктивной должности должны полагаться равными нулю, как показано в таблице 3. Заметим, что стоимость назначения работника 5 должна быть определена и включена в соответствующие ячейки матрицы.
Если имеется больше должностей, чем работников (кандидатов), компьютер также должен увеличить матрицу, чтобы она стала квадратной. Предположим, что имеется 6 должностей и только 4 работника (кандидата). Компьютер дополнит матрицу до размера 6*6, как показано в таблице 4. Заметим, что работники 5 и 6 являются фиктивными и стоимости назначений для фиктивных работников полагаются равными нулю.
Таблица 3. Расширенная матрица назначений - 4 должности для 5 кандидатов
Должности12345116914170Канди-27198140даты315691004191711405141118160
Замечание: Ячейки содержат стоимости назначений.
Таблица 4. Расширенная матрица назначений - 6 должностей для 4 кандидатов
Должности12345611691417811Канди-27198141318даты31569101754191711491450000006000000
ИНСТРУКЦИЯ ПО ИСПОЛЬЗОВАНИЮ ПОДСИСТЕМЫ "МЕТОД НАЗНАЧЕНИЙ" ПРОГРАММЫ DSSPOM
ПРИМЕР 1 - ЗАДАЧА НАЗНАЧЕНИЯ РАБОТНИКОВ НА ДОЛЖНОСТИ
В этом примере используется программа назначений для решения задачи назначения работника на должность. Цель - назначить четыре должности четырем работникам так, чтобы минимизировать суммарную стоимость назначений. Стоимости назначений для этой задачи представлены в таблице 1.
Загрузите программу DSSPOM в компьютер и выберите Assignment Method в главном меню. Через несколько секунд компьютер загрузит программу назначений и высветит Assignment Menu. Передвиньте указатель на опцию INPUT и нажмите клавишу , чтобы ввести следующий параметр.
Следующим входным параметром является "тип цели". Так как задача состоит в назначении должностей работникам и поэтому содержит стоимости, целью является минимизация стоимости. Напечатайте MIN и нажмите для продолжения. Заметим, что в это поле программа может принять только "MIN" или "MAX". Никакие другие значения не принимаются и поэтому программа в случае неправильного ввода не сможет продолжить выполнение. Во время ввода данных при помощи нажатия клавиши "Стрелка вверх" можно вернуться к предыдущему полю, чтобы исправить его значение.
Для продолжения ввода данных нажмите клавишу "Стрелка вправо" и напечатайте "4" для количества кандидатов. Нажмите . Максимальная размерность задачи - 30 на 30, стоимости назначений должны быть в диапазоне от 0 до 9999. Заполненный экран исходных данных показан ниже.
Problem title: