|
|
Модели распределения транспортных потоковМодели распределения транспортных потоков относятся к классу моделей, используемых для решения задач по оптимизации перевозок. В них, как правило, разыскивается оптимальный план перевозок между некоторой совокупностью производителей L и потребителей S однородного продукта. Предполагается, что каж- дый поставщик l ÎL способен поставить в транспортную сеть не более чем l b единиц продукта, а каждый потребитель sÎS должен получить не менее чем s a единиц. Критерии могут быть различ- ными, но наиболее часто минимизируется сумма транспортных за- трат. Существуют две основные формулировки этой задачи: в мат- ричной и сетевой формах. При постановке в матричной форме за- дача распределения транспортных потоков сводится к транспорт- ной задаче линейного программирования. При сетевой постановке задачи ее условия определяются на ориентированном мультиграфе с множествами узлов L и ориентированных дуг G с тем условием, что не пусты подмножества G+ l всех дуг, входящих в узел l и G- l - всех дуг, выходящих из узла l. Такая система называется транс- портной сетью. Через l x обозначим величину потока на дуге g ÎG в соответ- ствии с ее ориентацией и через cg - коэффициент транспортных за- 81 трат. Тогда транспортная задача в сетевой форме описывается со- отношениями Σ g ÎG min cg xg, (4.1.) l x x a l l Σ - Σ ³ ÎG+ g ÎG- g g g, xg ³ 0, l ÎL (4.2.) Для разрешимости задачи необходимо 0 £ Σ lÎL l a. (4.3.) Говорят, что величиной l a при положительном знаке опреде- ляется мощность стока, а при отрицательном – мощность источни- ка. Кроме того, в сети могут быть транзитные узлы, для которых = 0 l a. В случаях, когда неравенство (4.3.) выполняется строго, мо- дель называется открытой, при выполнении же (4.3.) как равенства – закрытой (замкнутой). Присоединяя к открытой задаче сток с мощностью Σ Î = - l L l a a, и соединяя его ориентированными дугами со всеми источниками, можно перейти от открытой задачи к за- крытой. Для их эквивалентности достаточно потребовать, чтобы на всех дополнительных дугах коэффициенты транспортных за- трат были равны нулю. Иногда тот же прием используют и в несо- вместной задаче, присоединяя ко всем ее стокам источник с мощ- ностью -a. Затраты на дополнительных дугах в этом случае должны вводится из экономических соображений. Например, вследствие высокой стоимости приобретения продукта со сторо- ны. Модели распределения транспортных потоков в сетевой по- становке с одним источником и одним стоком единичной мощно- сти, расположенными в некоторых вершинах сети l ¹ s, представ- ляется задачу о минимальном маршруте. Иногда – при отождествлении величины cg с расстояниями на дугах rg - говорят также о маршрутах минимальной длины. Если сеть моделирует реальную структуру перевозок, то транспортные затраты должны рассчитываться в соответствии с тарифами. Обычно тариф представляет функцию j (r), монотонно не убывающую с ростом дальности перевозок r и субаддитивную, т.е., если 1 2 r = r + r, то имеет место равенство () () () 1 2 j r <j r +j r. (4.4.) 82 В силу (4.4.) нельзя определить на дугах сети никакой систе- мы коэффициентов транспортных затрат с тем, чтобы сумма их на любой последовательности дуг соответствовала тарифу. Поэтому модели распределения транспортных потоков обычно решается в два этапа. На первом в реальной конфигурации сети определяют мар- шрут минимальной длины между всеми возможными парами по- ставщик – потребитель и по полученному набору дальностей – та- рифные стоимости перевозок. Затем на втором этапе ставится транспортная задача в мат- ричной форме. В сетевой задаче обычно существует много различных мар- шрутов, связывающих пару узлов сети. Поэтому она допускает ог- раничения на пропускные способности дуг xg £ dg (4.5.) Отмечая на сети два узла l ¹ s, можно дополнить условия (4.2.), (4.5.) равенствами 0 = -Σ - ÎGl u x g g, 0 = - Σ + ÎG x u g s g и заменить критерий (4.1.) требованием max u. Эта модель известна как задача о максимальной пропускной способности сети. Простейшая задача размещения на сети – это математиче- ская формализация, используемая в процессе принятия решения по выбору пунктов размещения предприятий, производящих од- нородную продукцию для удовлетворения заданного спроса. Пусть имеется m возможных пунктов размещения предприятий и n пунктов потребления (точек спроса), m £ n, расположенных в узлах сети G(V,U), где { } n V v,,v 1 = K - множество вершин, { } p U u,, u 1 = K - множество ребер сети. Заданы величины j b, j =1,K,n; 0 i q, i = 1,K,m; () i j c,, i = 1,K,m, j = 1,K,n, где o j b = спрос в пункте потребления j; o 0 i q - затраты на ввод в действия предприятия i; o i c - стоимость производства единицы продукции в пункте размещения i; 83 o i j c, - затраты на доставку единицы продукции из пункта производства i в пункт потребления j. Считается, что каждый потребитель обслуживается одним предприятием. Целевая функция задачи – суммарные затраты на размещение предприятий и обслуживание спроса – должна дос- тигнуть минимума. Простейшая задача размещения на сети запи- сывается в виде [ ] min min 1,, , 1 0 m i j n i j i i q q ÎÂ = ÎÂ ÂÌ K Σ +Σ ®, где () i, j i i i, j q = b c + c, i = 1,K,m, j = 1,K, n. Простейшие задачи размещения на сети относят к числу трудноразрешаемых (сложность задач дискретной оптимизации). Для некоторых классов простейших задач размещения на сети по- строены эффективные точные алгоритмы. Наиболее известными являются задачи со связанными и с квазивыпуклыми матрицами (i j q,). Матрица (i j q,) квазивыпукла, если для всяких j = 1,K, n и £ i < i < i £ m 1 2 3 1, { } i j i j i j q q q,,, 2 1 3 £ max;. Матрица (i j q,) связана, если для всяких 1 £ i, k £ m разность () i, j k, j q - q меняет знак не более одного раза при монотонном из- менении j = 1,K, n. В общем случае для решения простейших за- дач размещения на сети хорошо себя зарекомендовали методы ветвей и границ. Для простейших задач размещения на сети играет важную роль при построении математических методов решения математической теории стандартизации задачи. Для нелинейной простейшей задачи размещения на сети про- изводственная функция () i i q V - затраты на размещение предпри- ятия i зависят от суммарного объема спроса i V, обслуженного из этого предприятия. В случае кусочно-линейной, растущей, вогну- той, производственной функции нелинейная задача размещения сводится к простейшей задаче размещения на сети. К распределительным относятся такие широко распростра- ненные задачи, как транспортная задача линейного программиро- вания, задача о назначениях и многие другие. Обозначим: 84 ¨ ij c - затраты на перевозку 1единицы однородного груза вида i к пункту j, ¨ ij x - количество этого груза i к пункту j, ¨ i d - располагаемое количество груза вида i. ¨ ij a - цена за единицу груза вида i; ¨ j b - объем продаж в стоимостном выражении в пункте i. Задача заключается в составлении плана перевозок, обеспе- чивающего удовлетворение спроса во всех пунктах в этих грузах наиболее эффективным способом. Формально задача записывается так. Требуется найти минимум линейной формы ΣΣ = = = n j m i ij ij F x c x 1 1 () при выполнении условий Σ= = = m i ij ij j a x b j n 1 , 1,2K,, (5.1) Σ= £ = n j ij i x d i m 1 , 1,2,K,, (5.2) x i m j n ij ³ 0, =1,, =1,. (5.3.) Линейная форма F(x) определяет суммарные транспортные издержки на перевозку грузов. Ограничения (5.1) означают, что объем доставленного в каждый пункт потребления груза должен удовлетворять сложившийся там спрос. Условия (5.2) означают, что количество, направляемого во все пункты потребления груза i, не должен превышать располагаемой величины i d. В распределительной задаче нередко возникает необходи- мость учитывать двусторонние ограничения на переменные моде- ли. В терминах задачи, приведенной выше, двусторонние ограни- чения переменных могут истолковываться, например, как ограни- чения пропускных способностей коммуникаций и нецелесообраз- ность перевозок недогруженным транспортом. В этом случае ог- раничения (5.3) примут вид ij ij ij x £ x £ x (5.4.) Задача (5.1.)-(5.3.), (5.4.) называется распределительной зада- чей с двусторонними ограничениями. 85 Сам термин распределительная задача, по видимому, связан со следующей задачей распределения m видов изделий между n предприятиями. Задачи распределения могут решаться в статической (одно- кратной) и в динамической постановке. В последнем случае часто применяют методы стохастического программирования, в которых принятие решений основано на вероятностных оценках будущих значений параметров. Контрольные вопросы 1. Приведите содержательные примеры задач распредели- тельного типа. 2. Сформулируйте критерий задачи распределения. ЗАКЛЮЧЕНИЕ Предлагаемый курс лекций дисциплине «Методы и модели в экономике» призван дать студентам первоначальную подготовку в области построения математических моделей и их применения для решения практических задач управления. Успешное освоение предлагаемых тем позволит, перейти студентам к изучению спе- циализированных учебных курсов, предусмотренных программой обучения. ПРИМЕРЫ ТЕСТОВЫХ ЗАДАНИЙ Тест 1 1.Математическое моделирование – это · математическая дисциплина, занимающаяся изучением экс- тремальных задач и разработкой методов их решения. · метод исследования, предполагающий построение некоторой модели реального объекта, эксперименты с моделью, анализ ре- зультатов эксперимента, применение к реальному объекту · реализация экономической задачи с помощью современных информационных технологий. 2. Агрегирование - преобразование исходной модели в модель с меньшим числом переменных и/или ограничений? 1. да; 2. нет. 86 3. Взаимная задача строится с использованием следующего пра- вила: · матрица коэффициентов ограничений взаимной задачи явля- ется транспонированной матрицей коэффициентов ограничений исходной задачи; · целевая функция исходной задачи во взаимной задаче стано- вится ограничением, правая часть которого задается экспертным путем или на основании опыта ЛПР (лица, принимающего реше- ние); · все ответы верны; · нет правильного ответа. 4. В модели МОБ I квадрант описывает: Перераспределение доходов и расходов; Потребление конечного продукта; Структуру добавочной стоимости; Производственное потребление; Нет правильного варианта. 5. По матрице оценок выберите вариант решения многокритери- альной задачи: (оценки строятся как отношение значения целевой функции к ее максимальному значению) f1(x) f2(x) f3(x) Решение по первому критерию I 1 0,5 0,7 1 ˆx Решение по второму критерию II 0,6 1 0,6 2 ˆx Решение по третьему критерию III 0,5 0,7 1 3 ˆx 1 ˆx; 2. 2 ˆx; 3. 3 ˆx; 4. Однозначный выбор сделать нельзя. 6. По отчету об устойчивости определите ресурс дополнитель- ная единица которого даст наибольший прирост целевой функции Ограничения   Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...  ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|