Оптимизация ресурсов, Пример 5. Транспортная задача на сети.

Транспортная задача на сети.

Типичные задачи: управление транспортными потоками, производственное планирование, составление расписания работ, выявление узких мест, назначение объектов одной группы объектам другой группы. Наглядность сети существенно облегчает подготовку исходных данных.

Сеть, это направленные дуги, несущие искомые потоки X и соединяющие узлы.

Для каждого узла задаются:

• тип, стоимость и интенсивность А запасов при А>0 или потребностей при A<0. Тип – это способность узла сохранять поток, то есть делать так, чтобы разность между суммой выходящих из узла SX2 и входящих SX1 в него потоков, была равна интенсивности узла SX2-SX1=A, - это узел типа 0, - или была бы равна или меньше его (условие уменьшения потока), - это узел типа 1, - или равна или больше его (условие увеличения потока), - это узел типа 2. Для каждой дуги задаются: - номера входящего и выходящего узлов, стоимость, пропускная способность и коэффициент потерь. Минимизируется или максимизируется стоимость потоков дуг и узлов. Равенство заменяется двумя неравенствами SX2(K)-SX1(K)<=A(0,K)+е; SX2(K)-SX1(K)>=A(0,K)-е, где е - заданное малое число. Если ограничения по диапазонам потоков несущественны и все стоимости дуг в каждой максимизируемой функции положительны или отрицательны, то условие сохранения потока можно смягчить на неравенство SX2-SX1<=A. Равенство будет достигаться при оптимизации. Разработана программа, где используются параметры дуг и узлов сети и формируются исходные данные для оптимизации. Иллюстрация 1. Задача о максимальном потоке (минимальном разрезе). Дана схема технологических операций, где дуги имеют параметры оборудования,- номер операции и производительность. Поток входит в 1-й узел, имеющий запас изделий, распределяется между дугами в пределах производительностей и выходит из 5-го узла. Узлы 2-5 имеют нулевую интенсивность (брака нет). Стоимости дуг одинаковы и равны 1. Стоимость потоков дуг максимизируется. {mosimage} Требуется определить "узкие места"(оборудование на пределе производительности, выделено на схеме двойными стрелками) и максимальный поток изделий. Ограничения на потоки по узлам имеют следующий вид: Узел 1. X1 + X2 + X3 <=100 Узел 2. X6 - X1 - X4 <= 0.001; X6 - X1 - X4 >= -0.001 Узел 3. X4 + X5 + X7 - X2 <= 0.001; X4 + X5 + X7 - X2 >= -0.001 Узел 4. X8 - X3 - X5 <= 0.001; X8 - X3 - X5 >= -0.001 Узел 5. X9 - X6 - X7 - X8 <= 0 Точность выполнения ограничений-равенств е=0.001. **************************************************************** Результаты расчетов *** Оптимизация ресурсов. optim.dat *** переменных 9 ограничений 8 функций 1 ** Значение 1-й функции: 147.006 *** переменные и ограничения *** **1 15 **10 56.999 **2 18 **11 0 **3 10.001 **12 0.0019989 **4 18.001 **13 0 **5 0 **14 0.0019989 **6 33.002 **15 0.0019989 **7 0 **16 0 **8 10 **17 0 **9 43.002 Предельная производительность достигается на дугах 1,2,8. Удаление этих дуг приводит к разрыву между входом и выходом. Поэтому эта задача называется также задачей о минимальном разрезе. К такой задаче приводят ситуации локализации распространения очагов болезни, пожара, миграции саранчи, и прочее. Максимальный поток равен потоку на дуге 9, это 43 изделия. Иллюстрация 2. Составление графика работ. Продукт в количестве 1000 ед. теряет 20 % своего количества за каждый месяц хранения, но его цена увеличивается соответственно на 30 %. В результате подработки удается восстановить 80 и 60 % продукта после 1-го и 2-го месяцев хранения. Затраты на подработку могут составлять 0.4, 0.6 и 0.8 р. за единицу продукта. Объем подработки может составлять 40 %, 60 %, 100% количества продукта. Продукт можно сдавать на переработку по вдвое меньшей цене. Цена продукта после 1-го месяца хранения составляет 10 р. Спрос составляет 100 ед. за каждый месяц. Схема работ. {mosimage} Узлы 1 и 4 – это хранение и переработка. Узлы 2,3 - это месяцы хранения-продаж с интенсивностью потребления -100 ед. и стоимостью 10 и 13 р. за единицу продукта. Дуги Х1, Х2 - хранение без подработки, Х4,Х5 - с подработкой. Коэффициенты потерь, соответственно 0.8;0.8;0.96;0.92, а стоимости - 0;0;-0.6;-0.6 р. Дуга Х3 - переработка со стоимостью 6.5 р. Тип узлов 1 и 4 - отток, а узлов 2 и 3 - сохранение потока. Параметры узлов Тип Интенсивность Стоимость Номер 1 1000 0 1 0 -100 10 2 0 -100 13 3 1 0 0 4 Параметры дуг Начальный Конечный Стоимость Коэффициент Дуга узел узел потерь 1 2 0 0.8 X1 2 3 0 0.8 X2 3 4 6.5 1 X3 1 2 -0.6 0.96 X4 2 3 -0.6 0.92 X5 Кроме учета потерь коэффициентом потерь можно изменять масштаб потока (переработка бревен в спички). Дополнительные ограничения объема подработки продукта: (объем подработки не больше 40 - 60 %) (X4 + X5) <= 0.4*(X1 + X2 + X4 + X5) (X4 + X5) <= 0.6*(X1 + X2 + X4 + X5) По этим данным соответствующая программа создает исходные данные для оптимизации. Вариация стоимости подработки плюс-минус 0.2р. создает еще 2 максимизируемые функции. *************************************************************** Результаты расчетов *** Оптимизация ресурсов. optim.dat *** переменных 5 ограничений 8 функций 3 ** Значение 1-й функции: 5604.96 *** переменные и ограничения *** хранение **1 273.547 **6 0 хранение **2 816.132 **7 0.200024 переработка **3 552.806 **8 0 подработка **4 726.453 **9 0.200026 подработка **5 0 **10 0 **11 552.806 **12 363.227 **13 0 ** Значение 2-й функции: 5459.67 *** переменные и ограничения *** **1 273.547 **6 0 **2 816.132 **7 0.200024 **3 552.806 **8 0 **4 726. **9 0.200026 **5 0 **10 0 **11 552.806 **12 363.227 **13 0 ** Значение 3-й функции: 5314.38 *** переменные и ограничения *** **1 273.547 **6 0 **2 816.132 **7 0.200024 **3 552.806 **8 0 **4 726.453 **9 0.200026 **5 0 **10 0 **11 552.806 **12 363.227 **13 0 График работ не зависит от затрат на подработку из-за небольшого объема подработки. Она производится в 1-й месяц. *** Оптимизация ресурсов. optim.dat *** переменных 5 ограничений 7 последнее ограничение на объем подработки снято функций 3 ** Значение 1-й функции: 5767.19 *** переменные и ограничения *** хранение **1 1.94127e-06 **6 0 хранение **2 743.96 **7 0.200024 переработка **3 601.733 **8 0 подработка **4 1000 **9 0.200025 подработка **5 115.94 **10 0 **11 601.733 **12 0 ** Значение 2-й функции: 5544 *** переменные и ограничения *** **1 1.94127e-06 **6 0 **2 743.96 **7 0.200024 **3 601.733 **8 0 **4 1000 **9 0.200025 **5 115.94 **10 0 **11 601.733 **12 0 ** Значение 3-й функции: 5323.13 *** переменные и ограничения *** **1 0 **6 0 **2 859.9 **7 0.200024 **3 587.82 **8 0 **4 1000 **9 0.200025 **5 0 **10 0 **11 587.82 **12 115.94 Полная подработка в 1-й месяц. При затратах подработки, меньших 0,8 р., подработка производится и во 2-й месяц. Увеличение затрат на подработку до 0,8 р. действует как ограничение объема подработки. *** Оптимизация ресурсов. optim.dat *** переменных 5 ограничений 6 снято еще одно ограничение на объем подработки функций 3 ** Значение 1-й функции: 6049.89 *** переменные и ограничения *** хранение **1 5.96046e-05 **6 0 хранение **2 0 **7 0.200024 переработка **3 691.008 **8 0 подработка **4 1000 **9 0.200023 подработка **5 859.9 **10 0 **11 691.008 ** Значение 2-й функции: 5677.91 *** переменные и ограничения *** **1 5.96046e-05 **6 0 **2 0 **7 0.200024 **3 691.008 **8 0 **4 1000 **9 0.200023 **5 859.9 **10 0 **11 691.008 ** Значение 3-й функции: 5323.13 *** переменные и ограничения *** **1 6.60114e-05 **6 0 **2 859.9 **7 0.200024 **3 587.82 **8 0 **4 1000 **9 0.200025 **5 0 **10 0 **11 587.82 Последовательное снятие последних ограничений изменяет объем подработки с 40 до 100 %. Результаты показывают оптимальное распределение объема подработки по времени. Основной объем работы приходится на 1-й месяц. С уменьшением стоимости подработки меньше 0,8 р. она переносится на 2-й месяц. Не следует увеличивать стоимость подработки свыше 0.6 р. Иллюстрация 3. Задача коммивояжера. Задача коммивояжера - это обход заданных пунктов с минимальными затратами. В традиционной постановке задают стоимости всех переездов из одного пункта в другой и вводят условия однократного посещения каждого пункта, что обеспечивает и непрерывность маршрута. При этом переменные принимают дискретные значения, - 1 - есть переезд из i-го пункта в j- й, 0 - нет. На сети такие условия чрезмерны, - есть пункты как неоднократного, так и необязательного посещения, например, перекрестки. Дробное значение переменной возникает при разветвлении маршрута и означает выгодность разделения одного маршрута на несколько, что является ценной информацией, так как принудительная дискретизация этой переменной приведет к увеличению затрат. Кроме того, использование сети резко упрощает подготовку исходных данных. Таким образом, целесообразно решать задачу коммивояжера на сети, причем, сначала с непрерывными переменными, а дискретизацию вводить по необходимости. Пункты (узлы сети) обязательного посещения выделяются среди других наличием потребности и стоимости узла. Но потребности не должны заметно изменять величину потока, так как в этой задаче стоимость относится не к единице груза, а к переезду между пунктами. Практически допустимы доли или единицы процентов изменения потока. Для удобства дискретизации величину потока зададим в пределах 0 - 1-SA, где SA<0 - сумма потребностей узлов. Стоимость пункта обязательного посещения может иметь реальное значение дохода или использоваться только для контроля количества посещенных пунктов. Непрерывность маршрута обеспечивается новым условием SX2 >= K*SX1, K=(1+A), K<=1, где, как и раньше SX1, SX2 - суммы потоков входных и выходных дуг узла. Это условие, вместе с условием сохранения потока в сети, требует увеличения суммарного входного потока узла в идеале до 1 аналогично условиям однократного посещения узла в традиционной постановке, однако, не мешая обнулению потока, если узел не используется. Схема дорог. {mosimage} Узлы 1 и 6,-исходный и конечный,- имеют запас 1.003 и потребность -1; узлы посещения 2,4,5 имеют потребность -0001 и стоимость 10000; узел 3- перекресток, потребность 0. Стоимость конечного узла равна 10. Дугам худшего случая назначим стоимость 4, а предпочтительным дугам 1. Рассмотрим типичные варианты предпочтительных марщрутов: 1.Последовательный обход пунктов посещения 2,5,4. 2.Петлеобразный маршрут через перекресток 3. 3.Комбинированный маршрут через перекресток 3 до пункта 5, затем петлеобразный обход пунктов 4 и 2 по дугам 16,15 и 14 с выходом по дуге 2. Параметры узлов Тип Интенсивность Стоимость Номер 1 1.003 0 1 0 -0.001 10000 2 0 0 0 3 0 -0.001 10000 4 0 -0.001 10000 5 1 -1 10 6 Параметры дуг по первому варианту Начальный Конечный Стоимость Дуга узел узел 1 2 -1 X1 2 6 -4 X2 1 3 -4 X3 3 6 -4 X4 1 4 -4 X5 4 6 -1 X6 3 2 -4 X7 2 3 -4 X8 3 5 -4 X9 5 3 -4 X10 3 4 -4 X11 4 3 -4 X12 2 5 -1 X13 5 2 -4 X14 4 5 -4 X15 5 4 -1 X16 Коэффициент потерь равен 1. Точность выполнения ограничений-равенств е=0.000001. Варианты 2 и 3 отличаются от 1-го только максимизируемой функцией. ************************************************************* Результаты расчетов *** Оптимизация ресурсов. optim.dat *** переменных 16 ограничений 14 функций 3 ** Значение 1-й функции: 305.948 *** переменные и ограничения *** **1 1.03 **17 0 **2 0 **18 1.90735e-06 **3 0 **19 0 **4 9.3032e-07 **20 0 **5 0 **21 1.90735e-06 **6 0.999999 **22 1.19209e-07 **7 0 **23 1.78814e-06 **8 0 **24 1.90735e-06 **9 0 **25 0 **10 0 **26 0 **11 0 **27 0.000298905 **12 0 **28 0.00010115 **13 1.02 **29 0.000198827 **14 0 **30 9.53674e-07 **15 0 **16 1.01 ** Значение 2-й функции: 302.008 *** переменные и ограничения *** **1 0 **17 0 **2 0 **18 1.90735e-06 **3 1.03 **19 0 **4 1 **20 0 **5 0 **21 1.90735e-06 **6 0 **22 1.90735e-06 **7 1.00011 **23 0 **8 0.990108 **24 1.19209e-07 **9 0.999938 **25 1.78814e-06 **10 0.989938 **26 0 **11 1.00006 **27 0 **12 0.990061 **28 0 **13 0 **29 0 **14 0 **30 9.53674e-07 **15 0 **16 0 ** Значение 3-й функции: 303.948 *** переменные и ограничения *** **1 0 **17 0 **2 1 **18 1.90735e-06 **3 1.03 **19 0 **4 0 **20 0 **5 0 **21 1.90735e-06 **6 0 **22 1.19209e-07 **7 0 **23 1.78814e-06 **8 0 **24 1.90735e-06 **9 1.03 **25 0 **10 0 **26 0 **11 0 **27 9.89152e-05 **12 0 **28 0 **13 0 **29 0.0101977 **14 1.01 **30 9.53674e-07 **15 0.989884 **16 0.999883 Для иллюстрации появления дробного значения переменной, указывающей на целесообразность разделения маршрута на два, увеличим стоимость дуг 15,16 по варианту 1 на порядок. ************************************************************* Результаты расчетов *** Оптимизация ресурсов. optim.dat *** переменных 16 ограничений 14 функций 1 ** Значение 1-й функции: 299.989 *** переменные и ограничения *** **1 0.0299384 **17 0 **2 0.00993818 **18 1.90735e-06 **3 0 **19 0 **4 7.72487e-07 **20 0 **5 1.00006 **21 1.90735e-06 **6 0.990061 **22 1.90735e-06 **7 0 **23 0 **8 0 **24 1.19209e-07 **9 0 **25 1.78814e-06 **10 0 **26 0 **11 0 **27 0.000197671 **12 0 **28 0 **13 0.999937 **29 0 **14 0.989938 **30 9.53674e-07 **15 0 **16 0 Появились дробные значения по дугам 1 и 2, что указывает на разделение маршрута на два,- по дугам 1,2,13,14 и по дугам 5,6. Пример иллюстрирует типичные ситуации задачи коммивояжера на сети. Иллюстрация 4. Динамическая транспортная задача. Также, как в динамической модели макроэкономики в дискретные моменты времени Т происходит распределение искомого продукта Y между N складами и M потребителями с заданными потребностями В и пополнение-поставка текущих запасов Z на заданные величины U. Затраты на доставку единицы продукта составляют C. Все величины зависят от времени, склада и потребителя. Минимизируется суммарная стоимость SC доставки при следующих очевидных условиях: - Z>=0, Y>= 0, - доставленный потребителю со всех складов продукт SY должен удовлетворить его потребность SY=B, - запас Z1 каждого склада на следующий период пополняется на U и уменьшается на продукт SY1, доставленный потребителям, Z1=Z-SY1+U. Начальный запас Z0 принят равным нулю. Максимизируемая функция F=-SC. Соответствующая сеть представляет собой соединения между складами и потребителями (схема дорог) в заданные моменты времени, - листы, - соединенные дугами между одноименными складами. Программа позволяет оптимально управлять потоками при изменениях потребностей, запасов и стоимостей. Иллюстрация. Требуется спланировать на 2 дня перевозки продукта с 2-х складов одному потребителю. Параметры объектов приведены в таблице. Время | 0 1 | 0 1 Потребности | 100 200 | | стоимости | запасы Склады 1 | 9 8 | 100 50 2 | 8 4 | 100 50 Упорядочим переменные Запас 1-го склада по оконч. 1-го периода X1 Z(1,1) Запас 1-го склада по оконч. 2-го периода X2 Z(1,2) Запас 2-го склада по оконч. 1-го периода X3 Z(2,1) Запас 2-го склада по оконч. 2-го периода X4 Z(2,2) Достав. в 1-й период продукт с 1-го склада X5 Y(0,1,1) Достав. в 1-й период продукт с 2-го склада X6 Y(0,2,1) Достав. в 2-й период продукт с 1-го склада X7 Y(1,1,1) Достав. в 2-й период продукт с 2-го склада X8 Y(1,2,1) Схема связей склад-потребитель {mosimage} Узлы 1 и 4 -склад 1, - 2 и 5 -склад 2; узлы 3 и 6 -потребитель в моменты 0 и 1. Параметры дуг: Начальный Конечный Стоимость Дуга узел узел 1 3 -9 X1 - лист 1 2 3 -8 X2 - лист 1 4 6 -8 X3 - лист 2 5 6 -4 X4 - лист 2 1 4 -0.0001 X5 2 5 -0.0001 X6 Ограничения по диапазонам переменных сделаем несущественными, а так как стоимости дуг имеют один и тот же знак, то ограничения-равенства заменяем неравенствами, то есть тип узлов будет 1. Параметры узлов: Тип Интенсивность Стоимость Номер 1 100 0 1 - 1 100 0 2 | - лист 1 1 -100 0 3 - 1 50 0 4 - 1 50 0 5 | - лист 2 1 -200 0 6 - *************************************************************** Результаты расчетов *** Оптимизация ресурсов. optim.dat *** переменных 6 ограничений 6 функций 1 ** Значение 1-й функции: -1900.01 *** переменные и ограничения *** **1 100 **7 0 **2 0 **8 0 **3 50 **9 0 **4 150 **10 0 **5 0 **11 0 **6 100 **12 0 Стоимость перевозок составляет 1900. При оптимальном планировании перевозок на каждый день отдельно стоимость составила бы 2200.