J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C icon

J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C




НазваJ (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C
Дата11.09.2012
Розмір47.1 Kb.
ТипЗадача

4. Задача о назначениях


4.1. Формулировка задачи

Требуется распределить среди m исполнителей n заданий (работ). Работа j (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) Cij. Задача состоит в таком распределении работ среди исполнителей, которому соответствует минимум суммарных затрат. Причем, каждому исполнителю поручается только одна работа. Такая задача и называется задачей о назначениях Ее можно рассматривать как частный случай транспортной задачи. Здесь исполнители могут представлять “пункты отправления”, а виды работ - “пункты назначения” и наоборот. Предложение и спрос в каждом пункте отправления и пункте назначения равен единице. Если какую-либо работу нельзя поручить какому-то исполнителю, то соответствующая стоимость Cij берется равной очень большому числу М.


^ 4.2. Математическая модель задачи о назначениях.

Пусть xij - неизвестные переменные. Очевидно, что

0 - если j-я работа не поручена і-му исполнителю; 1 - если j-я работа поручена і-му исполнителю;

Тогда необходимо минимизировать целевую функцию

,

при ограничениях

, j=1, n;

, i=1, m;

xij=0 или 1.

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


^ 4.3. Решение задачи о назначениях

Свойство. Оптимальное решение задачи о назначениях не изменится, если к любой строке или столбцу матрицы стоимостей вычесть (или прибавить) постоянную величину. Действительно, если из і-й строки вычесть постоянную рі, из j-го столбца - gi, то новые стоимости будут иметь вид



Тогда новая целевая функция



Так как , то . Отсюда следует, что минимизация исходной целевой функции L приводит к такому же решению, как и минимизация L’.

Используя приведеное выше свойство, можно построить матрицу стоимости с нулевыми элементами. И если эти нулевые элементы матрицы стоимостей соответствуют допустимому решению, то такое решение будет оптимальным, поскольку стоимость не может быть отрицательной.

Покажим, как реализуется этот прием на следующем примере: a=||1,1,1||; b=||1,1,1||; .

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



Вычитая g3=2 из третьего столбца, получаем матрицу с² вида

,

g3=2.

Квадратами в матрице с” отмечены элементы, соответствующие допустимому (а поскольку эти элементы нулевые, то и оптимальному) решению: x112332=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). Этот элемент вычитается их каждого невычеркнутого элемента и прибавляется к каждому елементу, стоящему на пересечении проведенных прямых. В результате получаем матрицу



В матрице с’’’ отмечены элементы, соответствующие допустимому и, следовательно, оптимальному решению: х11233244=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 iconJ (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C
Предложение и спрос в каждом пункте отправления и пункте назначения равен единице. Если какую-либо работу нельзя поручить какому-то...
J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C iconJ (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C
Предложение и спрос в каждом пункте отправления и пункте назначения равен единице. Если какую-либо работу нельзя поручить какому-то...
J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C iconJ (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C
Предложение и спрос в каждом пункте отправления и пункте назначения равен единице. Если какую-либо работу нельзя поручить какому-то...
J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C iconJ (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C
Предложение и спрос в каждом пункте отправления и пункте назначения равен единице. Если какую-либо работу нельзя поручить какому-то...
J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C iconJ (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C
Предложение и спрос в каждом пункте отправления и пункте назначения равен единице. Если какую-либо работу нельзя поручить какому-то...
J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C iconНадежно хранить информацию
Выполнить все это очень трудоемкая задача, к тому же требует больших затрат времени. Поэтому для решения этих задач необходимо воспользоваться...
J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C iconАфанасьева Е. Ю., ассистент Полоцкий государственный университет классификация затрат на качество продукции пчеловодства в системе концепции экологического управления
Определение состава и классификационных признаков систематизации затрат на качество является начальным этапом внедрения системы менеджмента...
J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C iconН., Дубовец А. Н. Экспресс методы формирования воображения у студентов постановка проблемы
Поэтому предъявляются очень жесткие требования к уровню персонала, обслуживающего данные технологии. Старые знания и навыки быстро...
J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C icon1. Оформление документов, отчетов
Автоматизированная система перекладывает ра­боту по выписке документов на «плечи» компьютера, работа требует времени в де-сятки раз...
J (j=1,n), выполняемая i-м исполнителем, требует затрат (оплаты, времени) C iconОценка эффективности методики обучения пилотов ведению радиообмена на английском языке в условиях дефицита времени
Известно, что профессия пилота находится в тесной зависимости от времени. Дефицит времени, зависящий от физиологических возможностей...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи