Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 43
Текст из файла (страница 43)
в. Фабрика 3 отправляет 650 стульев в Нью-йорк, 100 стульев — в Остин и 250 стульев — в Сан-Франциско. г. Фабрика 4 отправляет 250 стульев в Сан-Франциско. Оптимальное решение данной задачи производственного планирования было получено посредством решения эквивалентной ей двойственной задачи и обратного перехода к соответствующим прямым переменным. С теоретической и практической точки зрения интересно дать экономическую интерпретацию двойственным переменным.
Напомним, что в алгоритме дефекта,используются условия дополняющей нежесткости двойственной задачи линейного программирования и, в частности, двойственные переменные ап и бц ~выбираются так, что 13, 41 ам=шах[0, пу-я,— с;,], ВМ тпах10, и,— Я)+001. 2 й 3 4 5 б 7 8 9 10 11 12 13 14 15 16 1230 1200 1230 1420 1440 1420 1420 3230 2930 2930 3330 .3230 3030 3430 3230 1230 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 16 17 18 800 1700 500 300 0 0 0 450 1000 250 500 750 1000 250 о 0 0 500 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 750 0 0 0 650 100 250 О 0 0 250 0 1400 100 500 500 2500 Алгоритм дефекта Используя найденное решение и рис. 3.17, можно построить сле- дующий сегмент сети, содержащий узлы 1, 2, З,и 5.
Для данной сети имеют место следующие результаты: дуга (1, 2) — ~ззз — я,(сзз=з-1зз=1зз, дуга (2, 5) -~ззз — яз=сзз=з 1зз~~зз =(7зь дуга (1, 3) — ьтз — ззз=сзз= Езз(Ь~ ь7зз, дуга (3, 5) — +ззз — пз=сзз~1.зз~(Гзз~((7зз. Как следует из рис. 3.18, значения двойственных переменных, соответствующих дуге (1, 2), равны азз=тах[0, 1200 — 1230— я, = З200 и, -З440 Из = З230 яз = !230 71г = 800 1зз = 300 .т,.з = ЗЗ00 узз = 450 с,з =0 сзз = 240 сзз =0 сзз =2!0 Рис. ЗА 8. Подсеть. — 01 =О, бгз=гпах10, 1230 — 1200+0)=30 центов.
Поскольку двойственные переменные а соответствуют ограничениям на по. ток сверху в прямой задаче, а двойственные переменные 6 соответствуют ограничениям на поток снизу, то выражение бзз=0,30 долл. означает, что в результате уменьшения нижней границы потока по дуге (1, 2) (и самогб потока по этой дуге) на 1 единицу будет сэкономлено 0,30 долл. в расчете на один стул. Это следует из того, что в результате уменьшения потока из узла 1 в узел 2 на 1 единицу будет сэкономлено 0,00 долл. Уменьшение потока из узла 2 в узел 5 на 1 единицу даст экономию 2,40 долл. Для сохранения потока, вытекающего из узла 1 н втекающего в узел 5, следует увеличить на 1 единицу поток из узла 1 в узел 3 и из узла 3 в узел 5. В первом случае затраты на увеличение составят 0,00 долл., во втором— 2,10 долл.
Следовательно, чистый выигрыш составит 0,30 долл., как было получено при исследовании двойственной переменной 6з з. В качестве второго примера рассмотрим следующий сегмент сети. 2бб Глава 3 Для данной сети имеют место следующие результаты: дуга (9, 13) — ьвз1з — пв(се,1з=е.1е,зз=1е,1з, дуга (13, 16) — евт1в — а1з си, зв 1зз, и=А~в, и, дуга (9, 15) — ьпи — па=се,1в $ ля зв~(1в за~~Уз 1в, дуга (15, 16) — +звзв — п1в(сзв,1в=ь11в, зв= [зв, зв. Яе = 2930 Ии =123О Яи =3230 се и = б00 с ~э. и = -1500 се,!5 = 300 си.!6 = -1800 Уе,!3 = 0 53, !в= 100 3е, „= 300 Ьп~в= 500 Рас.
3.19. Вторая подсеть. Как следует из рис. 3.19, значения двойственных переменных, соответствующих дуге (9, 13), равны ав = гпах [О, 3030 — 2930 — 600[ = О, 5, „= ивах[0, 2930 — 3030+600[=500 центов. Для дуги (9, 15): а, и шах[0, 3230 — 2930 — 300[=0, 8, и — — шах[0> 2930 — 3230+300[=0. Для дуги (13, 16): св,з зв —— пзах [О, 1230 — 3030 — ( — 1500)[= О, Ь„и, — — шах [О, 3030 — 1230+( — 1500)[= 300 центов.
Для дуги (15, 16): свез зв = взад [О, 1230 — 3230 — ( — 1800)[= О, б„,си — — шах [О, 3230 — 1230+( — 1800)[ 200 центов. Из этих соотношений для двойственных переменных следует, что в результате уменьшения нижних границ потока по дугам (9, 13) и (13, 16) на 1 единицу чистый выигрыш составит 800 центов в расчете на один стул. С другой стороны, для со- хранения потока в узлах 9 и 16 потоки по дугам (9, 15) и (15, 16) следует увеличить на 1 единицу.
Соответствующие затраты 267 Алгоритм дефекта составят 200 центов (еслн уменьшение потока на 1 единицу дает выигрыш в 200 центов, то увеличение потока на 1 единицу приводит к дополнительным затратам, равным 200 центам). Следовательно, в результате одновременного уменьшения нижних границ потока по дугам (9, 13) и (13, 16) на 1 единицу будет сэкономлено 600 центов.
Этот результат может быть получен другим способом. В результате уменьшения потоков по дугам (9, 13) и (13, 16) на 1 единицу будет сэкономлено 600 центов и дополнительно затрачено 1500 центов соответственно. Аналогично в результате увеличения потоков по дугам (9, 15) и (15, 16) на 1 единицу будет дополнительно затрачено 300 центов и получена прибыль 1800 центов. Чистый выигрыш при этом составляет (600 — 1500 — 300+ 1800) =600 центов.
Такая зкономическая интерпретация двойственных переменных в случае, когда стоимости дуг выражены в долларах или центах, явилась причиной того, что двойственные переменные часто называют векторами иек. ЗАЭ. ЗАКЛЮЧЕНИЕ Алгоритм дефекта применим к любой задаче, которая может быть сформулирована в виде задачи о циркуляции минимальной стоимости. При этом не требуется, чтобы в самом физическом процессе присутствовала циркуляция. Например, в транспортной задаче товар транспортируется только из источников в пункты назначения.
Циркуляция образуется в результате построения «возвратной дуги» (г, з), поток по которой может не иметь физического смысла. Не обязательно также, чтобы поток в задаче присутствовал явно. Например, задача о назначениях и задача о кратчайшей цепи являются комбинаторными, а не потоковыми. Циркуляция же используется как средство нахождения оптимального решения. Читателю следует внимательно изучить задачи, в которых поток или циркуляция не присутствуют явно и которые могут быть решены с помощью алгоритма дефекта.
Ключом к решению задачи с помощью алгоритма дефекта является сеть. С помощью сетей, поевндимому, может быть описано так много задач, что читатель скорее столкнется с необходимостью исправлять ошибки при применении этого алгоритма, чем искать задачи, где он может быть использован. Следует помнить, что единственным средством моделирования для применения алгоритма дефекта является построение ориентированной сети.,Каждая дуга описывается тремя числами: стоимостью единицы потока, нижней границей потока и верхней границей потока.
Если заданы некоторые дополнительные условия, связывающие потоки по различным дугам (исклю- Глава 8 чая условие сохранения потока), то для решения задачи алгоритм дефекта не может быть использован. Часто такие задачи могут быть описаны в виде задач линейного программирования н решены с помощью соответствующих программ. Кроме того, онн могут быть сведены к задачам, для которых применим алгоритм дефекта.
Алгоритм дефекта может быть использован для решения широкого класса задач, и поэтому будущим инженерам следует вооружиться активными знаниями в области теории,и программной реализации этого алгоритма. ЧАСТЫП. ПРИЛОЖЕНИЯ АЛГОРИТМА ДЕФЕКТАП '3.20. ПРОБЛЕМА УЗКИХ МЕСТ В ЗАДАЧЕ О НАЗНАЧЕНИЯХ В качестве первого примера рассмотрим задачу, которую в исследовании операций часто называют проблемой узких мест в задаче о назначенияхм. Опишем вначале наиболее часто встречающуюся задачу о назначениях.
Имеются группа рабочих и некоторое количество станков. Известна эффективность работы каждого рабочего за каждым станком. Задача заключается в том, чтобы назначить на каждый станок ровно одного рабочего (или назначить рабочих на рабочие места, распределить учителей по классам и т. д.) и при этом максимизировать суммарную эффективность выполнения работ.
Отметим, что, просто назначая каждого рабочего на тот станок, на котором эффективность его работы максимальна, мы, вообще говоря, не получим решения задачи, поскольку на одном и том же станке с наибольшей эффективностью могут работать несколько рабочих, а по условию задачи требуется, чтобы на каждый станок был назначен ровно один рабочий. Таким образом, возможен случай, когда при максимизации суммарной эффективности некоторые рабочие будут назначены на станки, на которых эффективность их работы не является максимальной.
Как показано в равд. 3.12, эта задача может быть сформулирована и решена как потоковая задача. Оптимальный поток определит назначение, которое макоимизирует суммарную эффективность. На рис. 3.20 изображена сеть, описывающая все возможные варианты назначения трех человек на три станка. Узлы 1, 2 и 3 соответствуют рабочим, а узлы 4, 5 и 6 — станкам. и В части ГП использован материал, опубликованный в 1пбизтгГа! Епдтпввгтпд с разрешения Американского института инженеров-технологов. Примеры предложены Суонсоиом, Вулсеем и Хиллисом [1Ц.
ы Далее проблему узких мест в задаче о назначениях будем называть Кратко задачей на узкие места.— Прим двд. Лкеоритн дейекта Перейдем теперь к задаче на узкие места, которая отличается от только что рассмотренной задачи о назначениях лишь тем, что в ней требуется максимизировать минимальную эффек- . тивность, определяемую назначением. Такая постановка является вполне реалистичной. Например, для линии последовательной сборки рабочий с минимальной производительностью (узкое место) определяет эффективность всего конвейера. Поэтому Рнс.
3.20. Сеть а задаче о назначевннх. в данном случае в отличие от задачи нахождения назначения, максимизирующего суммарную эффективность, было бы желательно м1вхсимизировать минимальную,производительность, что определяет оптимальное назначение в данной задаче на узкие места. Задача на узкие места является сетевой и может быть решена последовательным решением соответствующих задач о назначении. Алгоритм описывается следующим образом: 1.
Решить исходную задачу на узкие места как обычную задачу о назначениях. Это может быть легко сделано с помощью алгоритма дефекта. Поскольку алгоритм дефекта является минимизируюи(им, то следует минимизировать суммарную неэффективность (отрицательную эффективность), что эквивалентно максимизации эффективности. 2. Рассматривая оптимальное решение, полученное на шаге 1, определить назначение с максимальной неэффективностью (минимальной эффективностью). Если существует несколько таких назначений, то выбрать одно из них произвольным образом.
3. Исключить из сети, использованной на шаге 1, дуги, каждой из которых соответствует неэффективность (затраты), не меньшая неэффективности, определенной на шаге 2 (т. е. наименьшей эффективности, или наибольшей неэффективности, назначения,аюлученного на шаге 1). 2ТО Глава 3 4. Перейти на шаг 1, используя новую сеть, построенную нэ шаге 3. 5. Продолжать данный процесс до тех пор, пока нельзя будет произвести нужное число назначений (в результате того, что из исходной сети периодически исключается некоторое число дуг).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
