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

Задача коммивояжера и ее интерпретации

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

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

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

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

Пусть i=0,1,2,...,m - номера городов, i=0 - номер выделенного города (начало и окончание маршрута).

Обозначим через

R= r(i,j) - (m+1)(m+1) матрицу расстояний, элемент которой r(i,j) - расстояние между городом с номером i и городом с номером j.

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

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

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

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

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

u(i) - u(j) + m x(i,j) m-1, i=1,2,...,m, j=1,2,...,m, i j., (3)

x(i,j) {0,1}. (4)

Здесь условия (1) означают, что коммивояжер ровно один раз въедет в каждый город (кроме города с номером 0); условия (2) означают, что коммивояжер ровно один раз выедет из каждого города (кроме города с номером 0), ограничения (3) означают существование лишь одного цикла, начинающегося в городе с номером 0, проходящего через все города и завершающегося в городе с номером 0; ограничения (4) являются естественными условиями на введенные переменные.

Покажем, что условия (3) являются необходимыми и достаточными условиями существования лишь одного цикла.

Действительно, пусть это не так и найдется подцикл с числом городов k<m, не проходящий через город с номером 0. Складывая все неравенства (3) при условиях, что x(i,j)=1 по городам подцикла, получим mk (m-1)k (все u(i) и u(j) взаимно уничтожаются), что противоречит существованию подцикла длины k<m.

С другой стороны, покажем, что для цикла, проходящего через все города, начинающегося и заканчивающегося в городе с номером 0, найдутся величины u(i), удовлетворяющие условиям (3).

Положим u(i)=p, если город с номером i будет посещен коммивояжером p-ым по порядку, p=1,2,...,m.

Пусть x(i,j) = 0. Тогда условия (3) примут вид:

u(i) - u(j) m-1, что верно, так как p<m+1 и p>0.

Пусть x(i,j) = 1. Тогда, так как если u(i) = p, то u(j)=p+1 (это следует из того, что город с номером j будет следующим в маршруте коммивояжера после города с номером i). Получим:

u(i) - u(j) + m x(i,j) = p - (p+1) +m = m - 1, что и доказывает правомочность присутствия в модели ограничений (3).

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

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

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

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

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

- задача минимизации времени переналадок уникального оборудования;

- задача развозки готовой продукции по потребителям;

- задача управления работой снегоочистительных машин и др.

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

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

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

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

Пусть 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)

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

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

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

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

Дата добавления: 2017-02-01; Просмотров: 66; Нарушение авторских прав?; Мы поможем в написании вашей работы!