J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C
Скачати 48.38 Kb.
|
Зміст 4.2. Математическая модель задачи о назначениях.4.3. Решение задачи о назначениях |
|
|
4. Задача о назначениях 4.1. Формулировка задачи Требуется распределить среди m исполнителей n заданий (работ). Работа j (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) Cij. Задача состоит в таком распределении работ среди исполнителей, которому соответствует минимум суммарных затрат. Причем каждому исполнителю поручается только одна работа. Такая задача и называется задачей о назначениях. Ее можно рассматривать как частный случай транспортной задачи. Здесь исполнители могут представлять “пункты отправления”, а виды работ - “пункты назначения” и наоборот. Предложение и спрос в каждом пункте отправления и пункте назначения равен единице. Если какую-либо работу нельзя поручить какому-то исполнителю, то соответствующая стоимость Cij берется равной очень большому числу М. ^ Пусть xij - неизвестные переменные. Очевидно, что  0 - если j-я работа не поручена і-му исполнителю; 1 - если j-я работа поручена і-му исполнителю;Тогда необходимо минимизировать целевую функцию  ,при ограничениях  , j=1, n; , i=1, m;xij=0 или 1. Как видно из полученных ограничений, отличие задачи о назначениях от транспортной задачи заключается в том, что правые части всех ограничений равны единице, а переменные могут принимать значения только 1 или 0. Задачу о назначениях можно решать как транспортную задачу, однако специфическая структура задачи о назначениях позволила разработать более простые приемы ее решения. ^ Свойство. Оптимальное решение задачи о назначениях не изменится, если к любой строке или столбцу матрицы стоимостей вычесть (или прибавить) постоянную величину. Действительно, если из і-й строки вычесть постоянную рі, из j-го столбца - gi, то новые стоимости будут иметь вид  .Тогда новая целевая функция  .Так как  , то  . Отсюда следует, что минимизация исходной целевой функции L приводит к такому же решению, как и минимизация L’.Используя приведеное выше свойство, можно построить матрицу стоимости с нулевыми элементами. И если эти нулевые элементы матрицы стоимостей соответствуют допустимому решению, то такое решение будет оптимальным, поскольку стоимость не может быть отрицательной. Покажим, как реализуется этот прием на следующем примере: a=||1,1,1||; b=||1,1,1||;  .В матрице с’ нулевые элементы получены вычитанием наименьшего элемента в каждой строке из всех элементов этой строки:  ,Вычитая g3=2 из третьего столбца, получаем матрицу с вида  ,g3=2. Квадратами в матрице с” отмечены элементы, соответствующие допустимому (а поскольку эти элементы нулевые, то и оптимальному) решению: x11=х23=х32=1, min L=c11+c23+c32=5+12+13=30. Заметим, что эта стоимость равна p1+p2+p3+g3=30. К сожалению, не всегда удается определить допустимое решение столь просто, как в приведенном примере. Поэтому требуются дополнительные приемы для нахождения оптимального решения. Эти приемы проиллюстрируем на следующем примере: a=||1,1,1,1||; b=||1,1,1,1||;  .Выполняя те же начисленные шаги, что и в предыдущем примере, имеем:  Матрица с” не позволяет найти допустимое решение, состоящее их нулевых элементов. Дальнейшая процедура состоит в проведении минимального числа прямых через некоторые строки и столбцы, с тем чтобы все нули оказались вычеркнутыми:    .На следующем шаге выбирается наименьший невычеркнутый элемент (х32=1). Этот элемент вычитается их каждого невычеркнутого элемента и прибавляется к каждому елементу, стоящему на пересечении проведенных прямых. В результате получаем матрицу  В матрице с’’’ отмечены элементы, соответствующие допустимому и, следовательно, оптимальному решению: х11=х23=х32=х44=1. min L=c11+c23+c32+c44=1+10+5+5=21. Если на последнем шаге оптимальное решение не достигнуто, то процедуру проведения прямых следует повторить до тех пор, пока не будет получено допустимое решение. Как и для случая транспортной задачи, если в задаче о назначениях  , то задачу нужно сбалансировать.ТЕСТЫ (верно или неверно) 4.1. Задачу о назначениях можно решить методом, используемым для решения транспортной задачи. 4.2. Если к любой строке (столбцу) матрицы платежей задачи о назначениях прибавить (вычесть) одну и ту же постоянную величину, то оптимальное решение не изменится. 4.3. В задаче о назначениях допускается одному исполнителю поручать несколько работ. 4.4. Допустимость решение задачи о назначениях заключается в том, что в каждой строке и каждом столбце только одно значение xij равно единице. 4.5. Любое базисное решение задачи о назначениях является вырожденным. ЗАДАЧИ Решите следующие задачи о назначениях 4.1. a=||1,1,1,1||; b=||1,1,1,1||  4.2. a=||1,1,1,1,1||; b=||1,1,1,1,1||  4.3. a=||1,1,1,1||; b=||1,1,1,1,1||  4.4. a=||1,1,1,1,1||; b=||1,1,1,1||  4.5. a=||1,1,1,1,1||; b=||1,1,1,1,1||  4.6. a=||1,1,1,1,1||; b=||1,1,1,1,1||  4.7. a=||1,1,1,1,1,1||; b=||1,1,1,1||  4.8. a=||1,1,1,1,1||; b=||1,1,1,1,1||  4.9. a=||1,1,1,1,1||; b=||1,1,1,1,1||  4.10. a=||1,1,1,1||; b=||1,1,1,1||  4.11. a=||1,1,1,1,1||; b=||1,1,1,1,1,1|| 4.12. a=||1,1,1,1||; b=||1,1,1,1,1||  4.13. a=||1,1,1,1,1||; b=||1,1,1,1||  4.14. a=||1,1,1,1,1||; b=||1,1,1,1,1||  4.15. a=||1,1,1,1||; b=||1,1,1,1,1||  4.16. a=||1,1,1,1,1||; b=||1,1,1,1,1||  4.17. a=||1,1,1,1,1||; b=||1,1,1,1,1||  4.18. a=||1,1,1,1||; b=||1,1,1,1||  4.19. a=||1,1,1,1,1||; b=||1,1,1,1,1||  4.20. a=||1,1,1,1,1||; b=||1,1,1,1||  4.21. a=||1,1,1,1,1||; b=||1,1,1,1,1||  4.22. a=||1,1,1,1||; b=||1,1,1,1,1||  |
Схожі:
 | J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C Предложение и спрос в каждом пункте отправления и пункте назначения равен единице. Если какую-либо работу нельзя поручить какому-то... | | J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C Предложение и спрос в каждом пункте отправления и пункте назначения равен единице. Если какую-либо работу нельзя поручить какому-то... |
| J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C Предложение и спрос в каждом пункте отправления и пункте назначения равен единице. Если какую-либо работу нельзя поручить какому-то... | | J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C Предложение и спрос в каждом пункте отправления и пункте назначения равен единице. Если какую-либо работу нельзя поручить какому-то... |
| J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C Предложение и спрос в каждом пункте отправления и пункте назначения равен единице. Если какую-либо работу нельзя поручить какому-то... | | Надежно хранить информацию Выполнить все это очень трудоемкая задача, к тому же требует больших затрат времени. Поэтому для решения этих задач необходимо воспользоваться... |
| Афанасьева Е. Ю., ассистент Полоцкий государственный университет классификация затрат на качество продукции пчеловодства в системе концепции экологического управления Определение состава и классификационных признаков систематизации затрат на качество является начальным этапом внедрения системы менеджмента... | | Н., Дубовец А. Н. Экспресс методы формирования воображения у студентов постановка проблемы Поэтому предъявляются очень жесткие требования к уровню персонала, обслуживающего данные технологии. Старые знания и навыки быстро... |
| 1. Оформление документов, отчетов Автоматизированная система перекладывает работу по выписке документов на «плечи» компьютера, работа требует времени в де-сятки раз... | | Оценка эффективности методики обучения пилотов ведению радиообмена на английском языке в условиях дефицита времени Известно, что профессия пилота находится в тесной зависимости от времени. Дефицит времени, зависящий от физиологических возможностей... |