Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

Одно из возможных решений приведенной выше задачи выглядит следующим образом:

Назначить должность 1 работнику 2 - стоимость: $ 7

Назначить должность 2 работнику 3 - стоимость: $ 6

Назначить должность 3 работнику 1 - стоимость: $14

Назначить должность 4 работнику 4 - стоимость: $ 4

Общая стоимость этих назначений $31. Является ли эта стоимость наименьшей? Может быть, да, а может быть, и нет. В этом примере существует
24 возможных назначения (4!). Процедура, используемая в компьютерной модели, должна определять минимальную суммарную стоимость. Приведенная выше задача может быть сформулирована как задача линейного программирования и решена с использованием модуля линейного программирования. Однако, легче и эффективнее для решения задач подобного типа использовать метод назначений, который состоит из следующих четырех шагов.

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

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

3. "Линейный тест". В матрице назначений провести минимальное число линий (горизонталей (по строкам) и/или вертикалей (по столбцам)), вычеркивающих все нулевые ячейки матрицы. Если минимальное число вычеркнутых строк и столбцов равно n, оптимальное решение найдено, т.к. назначения должны быть произведены в "пункты", соответствующие нулевым ячейкам матрицы. В противном случае, если минимальное число вычеркнутых строк и столбцов< n, перейти к шагу 4.

4. Среди невычеркнутых строк и столбцов найти ячейку с наименьшим значением. Вычесть это значение из содержимого всех невычеркнутых ячеек и добавить это значение к содержимому всех ячеек, находящихся на пересечении линий. Повторить шаг 3.

Проиллюстрируем этот алгоритм на примере решения задачи о назначении 5 видов работ любой из 5 машин (n=5). Матрица стоимостей каждой комбинации работа/машина приведена в таблице 2-1.

Таблица 2-1. Матрица назначений, содержащая затраты на выполнение работ каждой машиной

|Машины |
|Работа |A |B |B |D |E |
|1 |$5 |$6 |$4 |$8 |$3 |
|2 |$6 |$4 |$9 |$8 |$5 |
|3 |$4 |$3 |$2 |$5 |$4 |
|4 |$7 |$2 |$4 |$5 |$3 |
|5 |$3 |$6 |$4 |$5 |$5 |

Процедура решения задачи приведена в таблице 2-2.

Таблица 2-2. Процедура решения задачи о назначениях

Шаг 1: приведение строк - наименьшее значение вычитается из содержимого всех ячеек в строке матрицы

|Машины |
|Работы |A |B |B |D |E |
|1 |$2 |$3 |$1 |$5 |$0 |
|2 |$2 |$0 |$5 |$4 |$1 |
|3 |$2 |$1 |$0 |$3 |$2 |
|4 |$5 |$0 |$2 |$3 |$1 |
|5 |$3 |$6 |$4 |$5 |$5 |

Шаг 2: приведение столбцов - наименьшее значение вычитается из содержимого всех ячеек в столбце матрицы

|Машины |
|Работы |A |B |C |D |E |
|1 |$2 |$3 |$1 |$3 |$0 |
|2 |$2 |$0 |$5 |$2 |$1 |
|3 |$2 |$1 |$0 |$1 |$2 |
|4 |$5 |$0 |$2 |$1 |$1 |
|5 |$0 |$3 |$1 |$0 |$2 |

Шаг 3: выполнение "линейного теста" - число линий, вычеркивающих все нулевые ячейки, равно 4; т.к.n=5, перейти к шагу 4.

|Машины |
|Работы |A |B |C |D |E |
|1 |$2 |$3 |$1 |$3 |$0 |
|2 |$2 |$0 |$5 |$2 |$1 |
|3 |$2 |$1 |$0 |$1 |$2 |
|4 |$5 |$0 |$2 |$1 |$1 |
|5 |$0 |$3 |$1 |$0 |$2 |

Шаг 4: Наименьшее значение среди содержимого невычеркнутых ячеек равно
1, 1 вычитается из содержимого всех невычеркнутых ячеек матрицы, 1 добавляется к содержимому ячеек, находящихся на пересечении линий

|Машины |
|Работы |A |B |C |D |E |
|1 |$1 |$3 |$0 |$2 |$0 |
|2 |$1 |$0 |$4 |$1 |$1 |
|3 |$2 |$2 |$0 |$1 |$3 |
|4 |$4 |$0 |$1 |$0 |$1 |
|5 |$0 |$4 |$1 |$0 |$3 |

Оптимальное решение, найденное с помощью "линейного" теста

|Машины |
|Работы |A |B |C |D |E |
|1 |$1 |$3 |$0 |$2 |$0 |
|2 |$1 |$0 |$4 |$1 |$1 |
|3 |$2 |$2 |$0 |$0 |$3 |
|4 |$4 |$0 |$1 |$0 |$1 |
|5 |$0 |$4 |$1 |$0 |$3 |

Рекомендуем скачать другие рефераты по теме: урок реферат, реферат планирование.



Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки