XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 29
Текст из файла (страница 29)
А так как соответ- ствующие ограничения, задаваемые в табл. 5.9 (по строке и по столбцу), могут быть предстанлены следующим образом: ~> хь + хль = Ть + В, зЫ" (5.9) хм+ хц, = В, Е ~еу" (5.10) то, вычитая (5.10) из (5.9), получаем ограничение (5.8). Дока- зательство того, что рассматриваемая транспортная задача с промежуточными пунктами эквивалентна классической транс- портной задаче, можно считать завершенным. Осталось доказать эквивалентность (в смысле совпадения оптимальных решений) исходной транспортной задачи с промежуточными пунктами, представленной в табл.
5.8, соответствующей еи классической транспортной задаче, представленной в табл. 5.9. 207 В.З. Задача о назначениях х4з+ х4в+ х4т — хв4 = 2, ч п ~> 1 сх;. !=! уы! ч ч ;!,! с х! — ! т1п; !=11=! (5,11) 1-! х;,Е10, 1), ю=1,п, !=! ! =1,п. и ~> х; =1, у-! !=1,п, и х;„=1, 1=1,п, а=! 206 Б. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА В частности, для четвертого склада, являющегося промежуточным пунктом, ограничение (5,8) имеет вид а соответствующие ему ограничения (5.9), (5.10) могут быть представлены следующим образом: хлз+ х44+ х4я+ х4! = 14, х44+хя4 — — 12. Это вытекает из равенств Тл = 2 и В = 12 (см.
третий этап построения в табл. 5.9), 5.3. Задача о назначениях Предположим, что имеется и различных работ, каждую из которых может выполнить любой из п привлеченных исполнителей. Стоимость выполнения г-й работы у-м исполнителем известна и равна с; (в условных денежных единицах). Необходимо распределить исполнителей по работам (наэначить одного исполнителя на каждую работу) так, чтобы минимизировать суммарные затраты, связанные с выполнением всего комплекса работ.
В исследовании операций задача, сформулированная выше, известна как задача о назначено,ах. Введем переменные хсо где х; принимает значение 1 в случае, когда ю-ю работу выполняет у-й исполнитель, и значение 0 во всех остальных случаях, г, у = 1, п. Тогда ограничение гарантирует выполнение каждой работы лишь одним исполни- телем, ограничение гарантирует, что каждый из исполнителей будет выполнять лишь одну работу.
Стоимость выполнения всего комплекса работ равна Таким образом, задачу о назначениях можно записать следую- щим образом: Задача о назначениях (5.11) является частным случаем нлассичесной транспортной задачи (5.2), (5,4), в которой надо положить п = тп, о! = 1, ! = 1, и, Р, = 1, у = 1, п. При этом условие хо Е (О, 1), !', у = 1, п, означает выполнение требования целочисленности переменных х; . Это связано с тем, что мощности всех источников и стонов равны единице, откуда следует, что в допустимом целочисленном решении значениями переменных могут быть только 0 и 1.
Как частный случай классической транспортной задачи, задачу о назначениях можно рассматривать как задачу линейного программирования. Поэтому в данном случае используют терминологию и теоретические результаты линейного программирования. В задаче о назначениях переменное х! может принимать значение 0 или 1, При этом, согласно (5.11), в любом допустимом решении лишь и переменных могут принимать значения 1.
Таким образом, любое допустнимое базисное решение задачи о назначениях будет вырожденным. 209 з.л. Задача о назначениях 208 где и и ~~> ~~> с; х; — + шах, ! — 1 Ря1 (5.12) и и ( — с,,)х;, -+ ш1п 1=1 Зи1 (5.13) с*" = с;, + д1+ 1,, 1, у = 1, и, о и и ~> ~> ( — с,* )х„— + ш1п, ии! яи1 в которой 1н1 1=1 1=1,п, с,* = с; — шахе;,, 1=!,и и и з. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА На практике встречаются задачи о назначениях, в постановках которых параметр с; для 1, ! = 1, п понимается как В эффективность выполнения 1-й работы у-м исполнителем.
этих случаях нужно так распределить работы между исполнителями, чтобы суммарная эффективность их выполнения была бы максимальной, т.е. где максимум ищется при ограничениях, указанных ( . ). в (5.11). Параметры с;, 1, ! = 1, и, задачи о назначениях (5.11) удобно представлять матрицей С = (с;,) е М„(К), которую называют матприцеб стпоимоспзи.
Предположим, что С = (,*) = (с- ) — две матрицы стоимости, элементы которых связаны — (с; )— следующим образом: где д! ! = 1, п, и 1, 1= 1, и, — некоторые постоянные. Таким о образом, для получения матрицы С* нужно к элементам каждой 1-й строки матрицы С прибавить число 4, а к элементам ее каждого !хго столбца — число 1. В этом случае, если Х— допустимое решение, удовлетворяющее ограничениям нз (5.11), н Г(Х) = ~У ~~ с;.х;;, Т*(Х) = ~~~,~ сохб то с учетом ограничений из (5.11) типа равенства имеем е*(Х) ~~,'~, („, «д1«1)х; =)! ~с;х;+ 1=1 1=1 1н1 ни1 +Ед;(Е*')+Е1 Кх4 =У(Х)+7 1=1 1=1 1=1 яи1 Таким образом, для любого допустимого решения Х соответствующие ему значения функций !" и !"* будут отличаться на постоянную у, которая не зависит от Х.
Поэтому, если есть две задачи о назначениях с одним и тем же множеством С допустимых решений и целевыми функциями 1' и г"" соответственно, то их оптимальные решения совпадают. Нетрудно убедиться в наличии аналогичного свойства и у классической транспортной задачи. Если задача о назначениях является задачей максимизации, т.е. ищется максимум целевой функции на множестве С допустимых решений, которое задается системой ограничений из (5.11), то эквивалентную ей задачу минимизации формально нельзя отнести к задачам о назначениях, поскольку коэффициенты ее целевой функции не являются положитель- ными.
Это несоответствие можно преодолеть, заменив (5.13) эквивалентной задачей так как в этом случае для всех 1, у = 1, и имеет место неравенство — с! > О. Пример 5.5. Предположим, что небольшая компания получает заказ на выполнение четырех видов работ, для каждого иэ которых известна производительность четырех ее штатных 211 бль Задача выбора кратчайшего пути 210 б. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА сотруднйков. нйков. Производительносты-го сотрудника при выполнении им 4-й р оты о р аб пределяет соответствующий элемент с;, следуюшей матрицы С дневных доходов компании (матрицы стоимости): 1 8 4 1 5 7 6 5 3 5 4 2 3 1 6 3 Сформулируем задачу о распределении штатных сотрудников фирмы по видам работ, дающем максимальный суммарный дневной доход, как задачу о назначениях.
В данном случае 1з — шах сп — — 6, 1 = шахов =5, 1 14 — шахе,4 — 5. 1з = шах сея = 8, Таким образом, в (5.11) имеем и = 4, а коэффициенты при переменных модели в целевой функции представлены матрицей 4 0 2 4 0 1 0 0 2 3 2 3 2 7 0 2 -С* = ( — с,",) = — (с;, — 1,) = 5.4, Задача выбора кратчайшего пути Пусть задана некоторая сеть (рис. 5.3), каждой ориентированной дуге которой соответствует опр д р е еленное асстоянне. Необходимо найти кратчайший путь из 1-го узла сети в ее Обращаем внимание на то, что задачи о назначениях, возникающие в приложениях, как правил, о не имеют никакого отношения к оптимизации перевозок или к каким-либо другим транспортным операциям. сю Рвс.
ь.з заданный ~-й узел. К этой задаче, известной в исследовании операций как задача выбора крапачабшеео пути, сводятся такие практически важные задачи, как задача о замене оборудования, задача о календарном планировании комплекса работ и т.д. Как правило, в сети выделяют один узел, который является конечным (пункт или станция назначения, сток). Задача заключается в отыскании кратчайшего пути в этот конечный узел (на рис.
5.3 конечным является узел с номером 8) из некоторого другого узла сети (например, из первого узла сети на рис. 5.3). Величина с; определяет расстояние от 1-го узла сети до ее 1'-го узла. Величина с;„может измеряться в единицах, отличных от единиц длины. Так, например, с; может представлять собой стоимость проезда от 1-го до 1'-го узла сети. Тогда задача заключается в отыскании пути минимальной стоимости. Величина с; может также определять время переезда от 1-го до у-го узла сети.
При этом необходимо найти путь с минималь, ной продолжительностью переезда. При решении прикладных задач, сводящихся к задаче выбора кратчайшего пути, часто встречаются ситуации, когда с; ~ с ь Кроме того, как правило, не выполняется так назы- 5,4. Задача выбора кратчайшего пути 213 212 б. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА ваемое неравенство треугольника: с;, < с;ь+сь для всех или некоторых значений индексов 2, ?', (с. Существуют сети, содержащие цнклы, каждый из которых представляет собой замкнутый путь (путь, исходящий из некоторого узла сети и возвращающийся в него же).
Так, в сети, представленной на рис. 5.3, много циклов, один из них содержит узлы с номерами 2, 3, 5, б и 7. Как правило, в задачах исследования операций значения с; положительны и общая „длина" цикла является положительной. Следовательно, решение задачи выбора кратчайшего пути не может содержать циклов. Предположим, что для сети, представленной на рис. 5.3, необходимо найти кратчайший путь от узла с номером 1 (источник) до узла с номером 8 (сток).
Установим связь этой задачи с классической транспортной задачей. Рассмотрим транспортпную задачу с промежуточными пунктамн, сеть которой представлена на рис. 5.3. При этом предположим, что: а) в узле с номером 1 имеется избыточная единица товара; б) в узле с номером 8 имеется недостаток единицы товара; в) узлы с номерами 2 — 7 являются промежуточными пунктами с нулевыми чистыми запасами (потребность в дополнительных поставках товара равна нулю — см. пример 5.4).
Необходимо разработать план перевозок товара между узлами сети (складами), который при минимальных транспортных затратах позволит на каждом складе поддерживать нулевой чистый запас товара. Как и в примере 5.4, считаем, что каждой ориентированной дуге сети соответствует переменное модели х;, представляющее собой количество товара, которое должно быть отправлено с 2-го склада на у-й. Для каждого й-го промежуточного пункта вводим переменное хьь с соответствующим ему коэффициентом сьь = 0 в целевой функции, а величину чистого запаса обозначаем через Ть.
Если множество пар индексов (5, у'), соответствующих ориентированным дугам сети, представленной на рис. 5.3, обозначить через,У, то рассматриваемую задачу можно записать следующим образом: с; х; -+ пй'и; Е (0 1)ез хь — ~ хгв = Ты (ь, йез (0 й)ез Тг — — 1, Тв = — 1, Ть = О, й = 2, 7, (5.14) хб>0, (5,.))ЕХ Транспортнал таблица для задачи (5.14) (табл. 5.10) аналогична транспортной таблице из примера 5.4 (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
