Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 68
Текст из файла (страница 68)
Этот результат гарантирует существование целочисленного оптимального решения в случае, когда т(2 или а 2 независимо от числа продуктов. Очевидно, что если т или н равно 1, то решение тривиальное. Однако когда н т, и и превосходят 1, то возникает более общая задача линейного программирования. Покажем, что в этом случае существует более простой метод решения. Вводя слабые переменные в ограничения на пропускные способности дуг, переформулируем многопродуктовую транспортную задачу (5.23) — (5.27) следующим образом: е в минимизировать лт', ~~)' ~~)' с",|х",| (5.35) в-|с-с |-с 417 Новые вопросы хаву+хам — — Ьву для всех 7', Ф, зи+вы — — и ~+им — ~~~~~Ьау дла всех !, двм!, ам~ )О для всех г, у, й. (5.46) Нетрудно заметить, что в равенствах (5.41) — (5.43) каждая из переменных хаз! и ззт появляется дважды: один раз со знаком плюс и один раз со знаком минус.
Поэтому матрица коэффициентов этих трех огранпчений имеет вид матрицы инциденций узел-дуга. Отметим также, что переменные дац и зц входят только в равенства (5.44) и (5.45) (со знаком плюс). Поэтому можно рассматривать эти переменные как слабые н исключить их, записав (5.44) и (5.45) в следующем виде: хм< Ьеу для всех ь Ф, зм ( иву+и 7 — ~~~~~ Ьву дла всех 7'. Величины, стоящие в правых частях равенств (5.4!) — (5.43), представляют собой предложение (если они положительные) и Спрос Предложение .! т! ! аз пт! а! ата и е 2 пи — Ха! г=! е=! Рнс, 5.27. Сеть в многопродуктовой транспортной задаче, сведенной к зада- че об однопродуктовом потоке.
и Ю х о о и Я л Ф о Ф Ф о о о .0 ) Ю н х л сс о с и и 'с к а! о ! Ф Ф ! о о о в с > 41З Глава б спрос (если отрицательные). Равенства (5.41) — (5.43) описывают транспортную модель, сетевая структура которой показана на рис. 5.27. Правые части равенств (5.44) и (5А5) представляют собой пропускные способности дуг, соответствующих пере- МЕННЫМ ХЛЗ1 И Зеп ДЛя рЕШЕНИя даННОй ЗадаЧИ МОЖНО ИСПОЛЬ- зовать алгоритм дефекта, который позволит определить оптимальные потоки хвм и зз;.
Затем из (5.44) и (5.45) могут быть найдены величины хап и зп. Данная формулировка была получена с помощью преобразования строк в исходных ограничениях аналогично тому, как это делалось прн рассмотрении задачи о календарном планировании трудовых ресурсов (равд. 2.1.7). Нетрудно показать, что эти две задачи эквивалентны. Интересно отметить, что исходная задача линейного программирования не имела форму сетевой задачи.
Однако с помощью преобразования ограничений нам удалось свести ее к сетевой задаче и тем самым существенно упростить решение. 5.19.1. ТРАНСПОРТИРОВКА КОРОБОК ПЕРЕДАЧ ДЛЯ АВТОМОБИЛЕЙ В распоряжении автомобилестроительной компании находятся два завода, производящие коробки передач; один из ннх — в Цинциннати, другой — в Сент-Луисе.
Собранные коробки пере- Таблица 5.!О, Входная информация для модельной задачи СТОИМОСТИ ТРАНСПОРТИРОВКИ ЕДИНИЦЫ ПРОДУКЦИИ 419 Новмв волросм дач должны быть перевезены на сборочные заводы, расположенные в Детройте, Далласе н Атланте. Производятся трн вида коробок передач: субкомпактные (СК), компактные (К) н средннх размеров (СР). Величины производительности, спроса н транспортных затрат для каждого вида коробок передач, а также пропускные способности дорог приводятся в табл. 5.10. На рнс.
5.28 изображена преобразованная сеть, для которой применнм алгоритм дефекта. гьп, н», сц' Рис. 5.28. Сеть, для которой применим алгоритм дефекта (все стоимости домножены на !00). 0.20. ПРИБЛИЖЕННОЕ РЕШЕНИЕ МНОГОПРОДУКТОВОИ ТРАНСПОРТНОИ ЗАДАЧИ МЕТОДОМ АГРЕГИРОВАНИЯ Нередко лицо, принимающее решение, удовлетворяют хорошне, хотя н субоптнмальные, решения сложных задач. Как правнло, это происходит в тех случаях, когда отсутствуют программы, позволяющие проводить точную оптимизацию, нлн когда использование таких программ требует слишком больших затрат нз-за циклического обращения к ннм, нлн же когда нет возможноств усовершенствовать основное программное обеспечение вследствие жестких ограничений на время ответа. Одним нз методов, позволяющих упростить решение задачи, является метод агрегирования, заключающнйся в замене мно- Глава о жества объектов (таких, как переменные, узлы сети и т.
п.) одним объектом. В этом случае сокращаются как время решения задачи, так и требуемая машинная память, однако полученное решение, как правило, не является оптимальным. В настоящем разделе, используя результаты, полученные в равд. 5.19, мы опишем метод решения многопродуктовых транспортных задач, основанный на агрегировании источников или стоков. А именно, мы рассмотрим случаи, когда сеть в агрегированной задаче содержит два источника и поэтому ее решение сводится к решению задачи об однопродуктовом потоке. Рнс. 5.29. Агрегирование источников в многопродуктовой транспортной задаче. Будем рассматривать многопродуктовую транспортную задачу с т источниками, л стоками и и продуктами.
Разобъем множество источников на два подмножества — Зг и Зз, и заменим эти подмножества узлов двумя «фиктивными узлами», как показано на рис. 5.29. Тем самым мы построили сеть с двумя источниками для агрегированной задачи. Далее, необходимо установить взаимосвязь между параметрами агрегированной и исходной задач. Кроме того, нужно описать способ построения допустимого решения исходной задачи с помощью решения агрегированной задачи. Поскольку каждый из двух фиктивных узлов представляет собой совокупность источников в исходной задаче, то величины предложения этих двух узлов естественно определить как йга = ~~)'а,а, (5.47) мз, где 1=1, 2.
Пусть де» вЂ” поток продукта й из узла 1 в узел 1 в агрегированной сети. Поскольку дуга (1, 1) получена в ре. Новые вввроеы с'ц= ~~~~~ с"ц(а",/а',). ~~в (5.49) Что касается пропускной способности агрегированной дуги ((, )), то на первый взгляд кажется разумным определить ее как сумму пропускных способностей исходных дуг из источников (~В~ в сток /. Однако в этом случае могут возникнуть трудности при построении допустимого решения исходной задачи. Поэтому мы воспользуемся следующим методом. Определим величины 5~ — — ппп (ав,!а',1 для К8г (5.50) Пусть далее иц т1п (б,иц]. 'езе Сформулируем агрегированную задачу в виде следующей задачи линейного программирования: е 2 в минимизировать ~~)' ")' ~~)'с'цу"ц (5.52) й 11-1 /-! при условии, что гт'увц —— Р~ для всех 1, й,1 е ~~~увц=а", для всех (,й, '~~~у"ц< иц для всех (,./, у"цЪО для всех 1,!,й.
(5.53) (5.54) (5.55) (5.56) зультате агрегирования дуг, ведущих из узлов (~8~ в сток ), то увц — — ~ хвц. (5.48) ~вас Теперь нужно решить вопрос о стоимостях и пропускных способностях агрегированных дуг. Существует несколько способов их задания. Метод, который будет нами использован, имеет ряд преимуществ по сравнению с другими методами. Для определения стоимостей мы воспользуемся понятием взвешенного агрегирования. Стоимости взвешиваются пропорционально величинам предложения источников, представленных фиктивными узлами: 422 Глава Ю Теперь необходимо построить решение исходной задачи, ис- пользуя оптимальное решение агрегированной задачи (5.52)— (5.56).
Определим величины х'и следующим образом: хв, = увц(а',/а'Д для (Р8п (5.57) Из (5.57) следует, что :Е'" = "'~Х'" 1" 3= ' ("7'")= "' мзу мзс ~~)~ ~~ ~~'с"пхвм=~~)~~ ~~~~ ~~с"цул„. (5.58) в ю у Иными словами, значение целевой функции в результате дезагрегирования с фиксированными весами не изменяется. Однако следует помнить, что в силу определения величин ип в агрегированной задаче может не существовать допустимого решения, даже если в исходной задаче оно существует. В этом случае можно попытаться воспользоваться другими методами агрегирования. 5.20З. ЗАДАЧА О ТРАНСПОРТИРОВКЕ ФРУКТОВ Перейдем к решению задачи о транспортировке фруктов, сформулированной во введении к настоящей части. Агрегируем источники 2 и 3.
Величины предложения, стоимости и пропускные способности для агрегированной задачи содержатся в табл. 5.11. Оптимальное решение исходной задачи содержится в табл. 5.12. Его стоимость равна 18570 долл. Стоимость оптимального решения агрегированной задачи (табл. 5.13) равна 18799,!О долл, и на 0,26% превосходит стоимость действительного оптимального решения. В качестве упражнения читателю предлагается найти дезагрегированное решение и проверить, что его стоимость равна стоимости агрегированного решения. что совпадает с равенством (5.48).
Процедура, определенная соотношением (5.57), называется дезагрегирозанием с фиксированными весами. С помощью несложных вычислений можно показать, что значения хлп образуют допустимое решение исходной задачи (величины ип были определены по формуле (5.51) с тем, чтобы не нарушались ограничения на пропускные способности дуг). Кроме того, Новые вопросы Таблица бяд Параметры агрегированной задачи ПРЕДЛОЖЕНИЯ СТОИМОСТИ ПРОПУСКНЫЕ СПОСОБНОСТИ 6.2П ГРАНИЦЫ ПОГРЕШНОСТИ ПРИ АГРЕГИРОВАНИИ' > Рассматривая двойственную задачу по отношению к агрегированной задаче (5.52) — (5.56), мы получим границу погрешности для дезагрегированного решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
