![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Задачи о назначениях и их интерпретации.
Содержательное описание. Есть несколько исполнителей и несколько работ. Задана производительность каждого исполнителя по каждой работе. Необходимо так распределить исполнителей по работам, чтобы каждый исполнитель получил не более одной работы, каждая работа получила не более одного исполнителя и суммарная производительность от сделанных назначений была максимальна. Математическая модель. Исходные параметры модели. Пусть i=1, 2,..., m - номера исполнителей, j=1, 2,..., n - номера работ. Обозначим через R= Варьируемые параметры. Обозначим через X= Ограничения математической модели.
x(i, j)
Здесь ограничения (1) означают, что каждая работа будет назначена не более чем одному исполнителю, ограничения (2) означают, что каждый исполнитель может быть назначен не более чем на одну работу, а условия (3) являются естественными ограничениями на введенные переменные. Постановка оптимизационной задачи. Критерий оптимальности для задачи о назначениях имеет вид: F(X) = Задача (1) - (4) называется задачей о назначениях с аддитивным критерием оптимальности. Если в качестве критерия оптимальности выбрать функционал F(X) = max r(i, j) x(i, j) где max берется по всем i=1, 2,..., m и всем j=1, 2,...n, то такая задача (1)-(3) называется минимаксной задачей о назначениях. Если в качестве критерия оптимальности выбрать функционал F(X) = min r(i, j) x(i, j) то задача (1)-(3), (6) называется максиминной задачей о назначениях. Замечание. Нетрудно показать (введением фиктивных исполнителей или фиктивных работ), что математическая модель (1)-(3) эквивалентна математической модели (7)-(9):
x(i, j) где m=n. Рассмотрим следующие условия на введенные переменные: 0 Исходя из того, что матрица ограничений условий (7) - (8) является абсолютно унимодулярной ( целочисленная матрица называется абсолютно или вполне унимодулярной, если любой ее минор равен 1, -1 или 0), то любой опорный план математической модели (7), (8), (10) является целочисленным, отсюда вытекает эквивалентность математических моделей (1)-(3) и (7)-(9). Кроме того, так как из условий (7) и (8) и условий неотрицательности переменных, автоматически следует, что переменные не могут быть больше 0, исходная математическая модель (1) -(3) эквивалентна ( с точки зрения поиска оптимального решения задачи о назначениях) математической модели с ограничениями (7), (8), условиями m=n и ограничениями 0
С помощью рассмотренной математической модели описываются следующие прикладные задачи: - задача назначения исполнителей по работам с целью максимизации суммарной производительности по выполняемым работам; - задача о конвейре - распределение исполнителей по работам на конвейре так, чтобы время перемещения конвейера было минимально; - задача распределения вознаграждения в наихудшем случае и др. Задача целочисленного линейного программирования в общей постановке. Математическая модель включает в себя систему линейных алгебраических ограничений, которые в матричной форме имеют вид (1) -(3):
Ax 0
x(i ) где A nm матрица ограничений задачи, x - m мерный вектор столбец неизвестных, b - n мерный вектор строка правых частей или свободных членов, Z - множество целых чисел. В качестве критерия оптимальности выберем F( x )= ( c, x ) Здесь c - m мерный вектор коэффициентов целевой функции, ( c, x ) -скалярное произведение векторов с и x. Задача (1) - (4) называется задачей целочисленного линейного программирования в общей постановке в матричной форме.
Метод ветвей и границ. Впервые этот метод был предложен в 1960 году для решения задачи целочисленного линейного программирования. Для всей группы алгоритмов, вписывающихся в общую схему метода ветвей и границ, характерным является применение в их вычислительной схеме следующей основной идеи: последовательное использование конечности множества вариантов решений задачи и замена полного перебора сокращенным, направленным перебором. Полного перебора удается избежать за счет отбрасывания “неперспективных” множеств вариантов, т.е. таких, которые заведомо не могут содержать решения “лучшего”, чем решения, оставшиеся в неотброшенном множестве. В общей схеме метода эта идея реализуется путем последовательного разбиения всего множества допустимых решений на подмножества и построения оценок, позволяющих сделать вывод о том, какое из полученных подмножеств может быть отброшено без потери оптимального решения исходной задачи. Основные понятия метода ветвей и границ. Релаксация (переход в равновесное состояние) задачи - переход от исходной задачи к задаче с той же целевой функцией, но с другой областью допустимых решений, включающей в себя в качестве собственного подмножества множество допустимых решений исходной задачи. Свойства, связывающие исходную задачу с ее релаксацией: - если релаксация задачи не имеет решения, то и исходная задача решения не имеет, - если оптимальное решение релаксационной задачи принадлежит множеству допустимых решений исходной задачи, то это решение является оптимальным и для исходной задачи, - значение оптимума ( значение критерия на оптимальном решении) исходной задачи на минимум (максимум) не меньше (не больше) значения оптимума релаксационной задачи. Ветвление - разбиение всего множества допустимых решений на непересекающиеся подмножества. Кандидат - задача, для которой необходимо провести процедуру ветвления. Потомок - подзадача, полученная в результате ветвления кандидата. Стратегия - порядок выбора задач кандидатов. Рекорд -значение критерия, соответствующее наилучшему решению, полученному к данному этапу вычислений.
Популярное:
|
Последнее изменение этой страницы: 2016-04-11; Просмотров: 895; Нарушение авторского права страницы