Модели распределения транспортных потоков

Модели распределения транспортных потоков относятся к

классу моделей, используемых для решения задач по оптимизации

перевозок. В них, как правило, разыскивается оптимальный план

перевозок между некоторой совокупностью производителей 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. По отчету об устойчивости определите ресурс дополнитель-

ная единица которого даст наибольший прирост целевой функции

Ограничения

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: