Задачи о назначениях и их интерпретации.

Содержательное описание.

Есть несколько исполнителей и несколько работ. Задана производительность каждого исполнителя по каждой работе. Необходимо так распределить исполнителей по работам, чтобы каждый исполнитель получил не более одной работы, каждая работа получила не более одного исполнителя и суммарная производительность от сделанных назначений была максимальна.

Математическая модель.

Исходные параметры модели.

Пусть i=1, 2,..., m - номера исполнителей, j=1, 2,..., n - номера работ. Обозначим через R= r( i, j) - mn матрицу производительностей, элемент которой r(i, j) - есть производительность исполнителя с номером i на работе с номером j.

Варьируемые параметры.

Обозначим через X= x(i, j) - mn матрицу неизвестных, элемент которой x(i, j) принимает значение 1, если исполнитель с номером i будет назначен на работу с номером j, и значение 0, в противном случае.

Ограничения математической модели.

x(i, j) 1, j=1, 2,..., n. (1)

 

x(i, j) 1, i=1, 2,...m. (2)

 

x(i, j) {0, 1}, i=1, 2,...m. j=1, 2,..., n. (3)

 

Здесь ограничения (1) означают, что каждая работа будет назначена не более чем одному исполнителю, ограничения (2) означают, что каждый исполнитель может быть назначен не более чем на одну работу, а условия (3) являются естественными ограничениями на введенные переменные.

Постановка оптимизационной задачи.

Критерий оптимальности для задачи о назначениях имеет вид:

F(X) = r(i, j) x(i, j) max. (4)

Задача (1) - (4) называется задачей о назначениях с аддитивным критерием оптимальности.

Если в качестве критерия оптимальности выбрать функционал

F(X) = max r(i, j) x(i, j) min, (5)

где max берется по всем i=1, 2,..., m и всем j=1, 2,...n, то такая задача (1)-(3) называется минимаксной задачей о назначениях.

Если в качестве критерия оптимальности выбрать функционал

F(X) = min r(i, j) x(i, j) max, (6)

то задача (1)-(3), (6) называется максиминной задачей о назначениях.

Замечание.

Нетрудно показать (введением фиктивных исполнителей или фиктивных работ), что математическая модель (1)-(3) эквивалентна математической модели (7)-(9):

 

x(i, j) =1, j=1, 2,..., n. (7)

 

x(i, j) =1, i=1, 2,...m. (8)

 

x(i, j) {0, 1}, i=1, 2,...m. j=1, 2,..., n, (9)

где m=n.

Рассмотрим следующие условия на введенные переменные:

0 x(i, j) 1, i=1, 2,..., m, j=1, 2,..., n. (10)

Исходя из того, что матрица ограничений условий (7) - (8) является абсолютно унимодулярной ( целочисленная матрица называется абсолютно или вполне унимодулярной, если любой ее минор равен 1, -1 или 0), то любой опорный план математической модели (7), (8), (10) является целочисленным, отсюда вытекает эквивалентность математических моделей (1)-(3) и (7)-(9). Кроме того, так как из условий (7) и (8) и условий неотрицательности переменных, автоматически следует, что переменные не могут быть больше 0, исходная математическая модель (1) -(3) эквивалентна ( с точки зрения поиска оптимального решения задачи о назначениях) математической модели с ограничениями (7), (8), условиями m=n и ограничениями

0 x(i, j), i=1, 2,..., m, j=1, 2,..., n. (11)

 

С помощью рассмотренной математической модели описываются следующие прикладные задачи:

- задача назначения исполнителей по работам с целью максимизации суммарной производительности по выполняемым работам;

- задача о конвейре - распределение исполнителей по работам на конвейре так, чтобы время перемещения конвейера было минимально;

- задача распределения вознаграждения в наихудшем случае и др.

Задача целочисленного линейного программирования в общей постановке.

Математическая модель включает в себя систему линейных алгебраических ограничений, которые в матричной форме имеют вид (1) -(3):

 

Ax b, (1)

0 x, (2)

 

x(i ) Z, i=1, 2,..., m, (3)

где A nm матрица ограничений задачи, x - m мерный вектор столбец неизвестных, b - n мерный вектор строка правых частей или свободных членов, Z - множество целых чисел.

В качестве критерия оптимальности выберем

F( x )= ( c, x ) extr. (4)

Здесь c - m мерный вектор коэффициентов целевой функции, ( c, x ) -скалярное произведение векторов с и x.

Задача (1) - (4) называется задачей целочисленного линейного программирования в общей постановке в матричной форме.

 

Метод ветвей и границ.

Впервые этот метод был предложен в 1960 году для решения задачи целочисленного линейного программирования.

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

Полного перебора удается избежать за счет отбрасывания “неперспективных” множеств вариантов, т.е. таких, которые заведомо не могут содержать решения “лучшего”, чем решения, оставшиеся в неотброшенном множестве.

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

Основные понятия метода ветвей и границ.

Релаксация (переход в равновесное состояние) задачи - переход от исходной задачи к задаче с той же целевой функцией, но с другой областью допустимых решений, включающей в себя в качестве собственного подмножества множество допустимых решений исходной задачи.

Свойства, связывающие исходную задачу с ее релаксацией:

- если релаксация задачи не имеет решения, то и исходная задача решения не имеет,

- если оптимальное решение релаксационной задачи принадлежит множеству допустимых решений исходной задачи, то это решение является оптимальным и для исходной задачи,

- значение оптимума ( значение критерия на оптимальном решении) исходной задачи на минимум (максимум) не меньше (не больше) значения оптимума релаксационной задачи.

Ветвление - разбиение всего множества допустимых решений на непересекающиеся подмножества.

Кандидат - задача, для которой необходимо провести процедуру ветвления.

Потомок - подзадача, полученная в результате ветвления кандидата.

Стратегия - порядок выбора задач кандидатов.

Рекорд -значение критерия, соответствующее наилучшему решению, полученному к данному этапу вычислений.

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. I. Предмет и задачи дидактики
2. II. Предполагаемые союзники и их задачи
3. III. Целевые установки, задачи и направления обеспечения транспортной безопасности
4. Алгоритм решения транспортной задачи
5. Анализ подходов и методов решения задачи
6. Анализ современного состояния АПК в России: задачи и экономическая стратегия развития
7. БИЛЕТ 1. Цели, задачи и основные принципы православной педагогики. Сотериологический характер педагогических воззрений Святых Отцов Церкви
8. БИЛЕТ 9. Вопрос 2. Психолого-педагогические задачи процесса духовно-нравственного становления личности на этапе вхождения в мир (наследство, зачатие, внутриутробное развитие, роды, новорожденность).
9. Бухгалтерский учет: его задачи, функции и
10. ВВЕДЕНИЕ. ЗАДАЧИ И ПРОБЛЕМЫ ГИСТОЛОГИИ.
11. Введение. Сущность , основные задачи, субъекты и объекты менеджмента.
12. Виды профессиональной деятельности и решаемые задачи