Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 24
Текст из файла (страница 24)
Шаг 4. Корректировка потоков по базисным маршрутам. Величина, на которую мы можем уменьшить или увеличить эти потоки, определяется потоком по маршруту, исключенному из базиса. Для определения новых потоков нужно прибавить эту Таблица 2.30. Новое базисное допустимое решение (оптимельное) 3 4 5 б Глава 2 величину к потокам по получающим маршрутам и вычесть эту же величину из потоков по отдающим маршрутам. При выполнении данной процедуры строится новое базисное решение, для которого не нарушаются ограничения, задаваемые предложением и спросом.
Двигаясь по ступенчатому пути, мы просто переносим единицы потока из одних клеток в другие. После выполнения шага 4 в рассматриваемом нами примере получено новое решение, записанное в табл. 2.30. Теперь следует возвратиться на шаг 2, с тем чтобы проверить, удовлетворяет ли данное решение условию оптимальности. Можно проверить, что решение является оптимальным, и на этом алгоритм завершает работу. 2.10.3. СЕТЕВАЯ ИНТЕРПРЕТАЦИЯ СИМПЛЕКСНОГО АЛГОРИТМА РЕШЕНИЯ ТРАНСПОРТНОИ ЗАДАЧИ В настоящем разделе мы покажем, как можно описать симплексный алгоритм для транспортной задачи, пользуясь только сетевыми понятиями.
Некоторым читателям, по-видимому, может показаться, что при изложении данного материала мы Рис, 2.41. Сетевое представление начального решения, полученного с по- мощью ПМФ. больше апеллируем к здравому смыслу, так как снмплексный метод будет описан не с помощью стандартных таблиц (равд. 2.10.2), а с помощью сети. При описании алгоритма мы воспользуемся примером из предыдущего раздела. Сеть, изображенная на рис. 2.41, представляет собой начальное решение, полученное с помощью ПМФ. Числа, приписанные дугам сети, равны соответствующим потокам.
14З Детерминированнме нотони в сетях Можно показать, что число дуг с положительным потоком равно 9 и что у данной сети две не связанные между собой компоненты. Первая компонента соответствует подсети 6~ = (1З1П А1), ГдЕ ХЗ= (ЗЬ ЗЗ, ЗЗ, З4, ем уя, 14, (З, ув) И А,=((ЗЬ 1~) (зь гз), (зз, гз), (зз, ге), (зз, гз), (зз, гз), (зм гз), (зе ге)). ВтоРаЯ компонента соответствует подсети ба= ()З(з, Аз), где Хз=(зз, уз) и Аз— - ((зз, 1з)).
Для того чтобы сеть, изображенная на Рнс. 2.42. Связная сеть, соответствующая начальному решению, полученно- му с помощью ПМФ. рис. 2.41, состояла ровно из одной связной компоненты, необходимо ввести еще одну дугу, соединяющую источник зз с любым стоком Гь 1~3, или любой источник зь'14=5 со стоком сз.
Как и в разд. 2.10.2, введем дугу (зю гз) с бесконечно малым потоком в так, что ограничения сетевой модели, задаваемые предложением и спросом, не будут нарушены. Образованная при этом связная сеть изображена на рис. 2.42. Вообще, для того чтобы сеть была связной (состояла из одной компоненты), необходимо и+и — 1 дуг. Вырожденность эквивалентна тому, что сеть состоит из двух или более не связанных между собой компонент. лз+п — 1 дуг соответствует «независимым клеткам», При анализе полезности внебазисных маршрутов, проводимом на шаге 2 (равд. 2.10.2), было установлено, что следует использовать маршрут (з4, сз). Схема замены, представленная в табл.
2.29 в виде контура, соответствует циклу в рассматриваемой сети (рис. 2.43). Если, передвигаясь по данному циклу, мы будем обходить узлы в последовательности зз, 1ш зз, ге, з,, то вдоль дуг (з4, гз) и (зз, ге) мы будем двигаться по направлению, совпадающему с их ориентацией, а вдоль дуг (зз, 1з) и (з,, 14) — по направлению, противоположному их ориентации. Глава 2 поэтому потоки по дугам (ве, гв) и (вв, (,) увеличиваются, а потоки по дугам (ем гв) и (зе, 4е) уменьшаются. Легко проверить, что максимальная величина потока по дуге (зм 1в) рав- О Рис. 2.43. Сетевое.
представление схемы замены маршрутов в транспортной сети. Рис, 2.44. Сетевое представление оптимального решения рассматриваемой транспортной задачи. на 50. Все это является иллюстрацией основного результата, согласно которому отдающие клетки соответствуют дугам в цикле, потоки по которым уменьшаются, а получающие клетки — дугам, потоки по которым возрастают. На рис. 2.44 изображено новое решение, которое, как было показано в равд. 2.10.2, является оптимальным.
Я О О О Детерминированные потоки в сетях 2.!0.4. МОДЕЛЬ ПРОИЗВОДСТВΠ— РАСПРЕДЕЛЕНИЕ Фирма владеет четырьмя заводами, расположенными в различных местах. Каждый завод производит одну и ту же продукцию, причем ее себестоимость, а также цены иа сырье для различных заводов не одинаковые. В данном районе имеется пять пунктов сбыта продукции. В каждом из них установлены свои цены на продукцию. Требуется определить оптимальный план производства и распределения продукции для случая, описанного в табл. 2.31.
Таблица 2.31. Стоимостные данные о производстве н распределении продукции'> 1! Предполагается, что проиэаодственные мом ности заводов в рассматриваемом периоде планирования составляют 200, 26ц 326 и 160 ед. аоот. ввтствеино. макси мальныа товмэооборот пунктов сбыта составляет 120, 160, 200, 160 и 210 вд. соотватственно. цены на единицу продук ции, установленные в каждом нэ пунктов сбыте, составляют 4042 41 42 и 4! дола соответственно. Решение. Следует отметить некоторые особенности данной задачи.
Во-первых, в ней требуется максимизировать прибыль, а не минимизировать затраты. Этого можно достичь, если рассматривать прибыль как отрицательные затраты. Во-вторых, суммарная производственная мощность заводов превосходит общий спрос и поэтому необходимо ввести фиктивный пункт сбыта, куда поступала бы избыточная продукция, причем соответствующие транспортные затраты и прибыль равны нулю. В-третьих, если в пункты сбыта перевозить максимально допустимый объем продукции, то некоторые перевозки окажутся убыточными. Поэтому можно ввести фиктивный завод с производственной мощностью х, нулевой прибылью за сбыт продукции и нулевыми транспортными затратами и приписать этому заводу все перевозки, не приносящие прибыли. Если х достаточно большое число, то введение фиктивного завода не повлияет на перевозку продукции от действительных заводов к пунктам сбыта. Величину х можно выбрать равной минимуму между суммарной производственной мощностью заводов и сум- !Π— 1654 Глава 2 Таблица 2.22.
Матрица условий транспортной задачи для случая максимизации прибыли Пуиктмсбита из из из но из ик Рз Рз засоли р, Рз 200 250 325 150 850 !ЭО тбо 200 150 210 925 Итз и'з Источники И и'з иб Гзо 1бо 200 Г5О 210 925 Ьз 200 250 325 150 850 С помощью симплексного алгоритма решения транспортной задачи находится оптимальное решение для данной задачи, которое представлено матрицей 0 0 0 130 0 70 0 90 0' 0 0 0200 0 0 0 0 0150 0 0 0 35 0 175 0 250 0 0 675 Х = 1хаз1 = мой максимальных значений товарооборотов пунктов сбыта. В рассматриваемом примере х=850. В табл.
2.32 приводятся величины прибыли, получаемой за сбыт единицы продукции, и величины предложения и спроса для данной задачи. Фиктивный завод и фиктивный пункт сбыта обозначены через Рз и ира соответственно. Для того чтобы свести данную задачу максимизации к эквивалентной ей задаче минимизации, умножим каждый элемент матрицы условий на — ! и прибавим к нему 11 (максимальный элемент матрицы). Матрица условий соответствующей задачи минимизации приводится в табл. 2.33, где пункты сбыта названы источниками, а заводы — стоками. Таблица 2.22. Матрица условий транспортной задачи для случая минимизации затрат Стоки Рз Рз Рз Рк Рз ат 147 Дете мипироеаииае потоки е сетях Прибыль, получаемая при данной схеме перевозки, равна 4905 долл.
Из полученного решения следует, что ни из одного действительного источника продукция не поступает в сток Р„ т. е. со второго завода продукция никуда не перевозится. 2.11. ЗАДАЧА О ПЕРЕВОЗКАХ В транспортной задаче предполагается, что ни в одном маршруте, соединяющем источник с некоторым стоком, другие источники и стоки не могут быть использованы в качестве промежуточных пунктов. Если считать допустимой перевозку груза из источника в сток через другие источники и стоки, то возникает новая задача, которая может быть сведена к обычной транспортной задаче. Безусловно, в данном случае возрастет объем вычислений, поскольку в сеть будут включены дополнительные маршруты, соединяющие каждый источник со всеми другими источниками и каждый сток со всеми другими стоками.
Будем предполагать, что транспортные затраты, соответствующие дополнительным маршрутам, известны. Тогда задача о перевозках может быть сведена к модифицированной транспортной задаче, в которой величины предложения и спроса, соответствующие дополнительным маршрутам, заданы таким образом, что они не влияют на выбор маршрутов, осуществляемый в основном алгоритме. Выполнение последнего требования необходимо по той причине, что ограничения на поток по дополнительным маршрутам, задаваемые предложением н спросом, являются фиктивными и вводятся только для вспомогательных целей.
Пусть 1 — минимальная из величин Бас и ХЬА т. е. 1 †э величина реального потока, протекающего по модифицированной сети. Тогда очевидно, что величину «спроса» Ь; 1-го исходного источника и величину «предложения» пг 1-го исходного стока можно положить равными 1. Иными словами, весь поток может протекать через один источник или через один сток. Поскольку Ьс=а1=1, то исходные величины предложения и спроса должны быть увеличены на 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
