Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Задачи о назначениях и их интерпретации.
Содержательное описание. Есть несколько исполнителей и несколько работ. Задана производительность каждого исполнителя по каждой работе. Необходимо так распределить исполнителей по работам, чтобы каждый исполнитель получил не более одной работы, каждая работа получила не более одного исполнителя и суммарная производительность от сделанных назначений была максимальна. Математическая модель. Исходные параметры модели. Пусть 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 году для решения задачи целочисленного линейного программирования. Для всей группы алгоритмов, вписывающихся в общую схему метода ветвей и границ, характерным является применение в их вычислительной схеме следующей основной идеи: последовательное использование конечности множества вариантов решений задачи и замена полного перебора сокращенным, направленным перебором. Полного перебора удается избежать за счет отбрасывания “неперспективных” множеств вариантов, т.е. таких, которые заведомо не могут содержать решения “лучшего”, чем решения, оставшиеся в неотброшенном множестве. В общей схеме метода эта идея реализуется путем последовательного разбиения всего множества допустимых решений на подмножества и построения оценок, позволяющих сделать вывод о том, какое из полученных подмножеств может быть отброшено без потери оптимального решения исходной задачи. Основные понятия метода ветвей и границ. Релаксация (переход в равновесное состояние) задачи - переход от исходной задачи к задаче с той же целевой функцией, но с другой областью допустимых решений, включающей в себя в качестве собственного подмножества множество допустимых решений исходной задачи. Свойства, связывающие исходную задачу с ее релаксацией: - если релаксация задачи не имеет решения, то и исходная задача решения не имеет, - если оптимальное решение релаксационной задачи принадлежит множеству допустимых решений исходной задачи, то это решение является оптимальным и для исходной задачи, - значение оптимума ( значение критерия на оптимальном решении) исходной задачи на минимум (максимум) не меньше (не больше) значения оптимума релаксационной задачи. Ветвление - разбиение всего множества допустимых решений на непересекающиеся подмножества. Кандидат - задача, для которой необходимо провести процедуру ветвления. Потомок - подзадача, полученная в результате ветвления кандидата. Стратегия - порядок выбора задач кандидатов. Рекорд -значение критерия, соответствующее наилучшему решению, полученному к данному этапу вычислений.
Популярное:
|
Последнее изменение этой страницы: 2016-04-11; Просмотров: 895; Нарушение авторского права страницы