Лабораторная работа по предмету: «Моделирование социально-экономических систем»

Санкт-Петербургский Государственный Университет

ЛАБОРАТОРНАЯ РАБОТА

ПО ПРЕДМЕТУ

«МОДЕЛИРОВАНИЕ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ СИСТЕМ»

Преподаватель:

Работу выполнила: студентка IV курса

Ледовская Вероника

Группа № 000

СПб 2010 г.

Парадокс Браесса

Честь открытия данного парадокса принадлежит немецкому математику Дитриху Браессу. Суть его сводится к тому, что добавление дополнительных возможностей к сети (компьютерной, транспортной и т. п.) при независимом («эгоистическом») распределении нагрузки на ее элементы может в некоторых случаях уменьшать эффективность ее работы, поскольку равновесие такой измененной сети необязательно оптимальное.

В своей статье Über ein Paradox der Verkerhsplannung, Dietrich Braess, Unternehmenstorchung 12:258-, Браесс привел пример транспортной сети, в которой увеличились затраты путешествия, когда к сети была добавлена дуга. Он использовал общее предположение, что движение распределяется согласно принципу пользовательского равновесия Вардропа. Альтернативный способ рассмотрения этого примера состоит в том, чтобы рассмотреть сеть с дополнительной существующей дугой (связью, ссылкой) и отметить, что удаление дуги (или, что эквивалентно, блокировка её путем введения больших затрат на дуге) улучшает транспортные расходы. Обобщением этого является определение парадокса Браесса, происходящего в любое время, если существует дополнительное распределение транспортного потока, при котором некоторые путешественники увеличивают свои выигрыши и ни у кого из участников выигрыш не становится хуже, чем в равновесии. Это обобщение охватывает все примеры парадокса Браесса, описываемого в литературе.

При равновесном распределении потоков в транспортной сети, обобщенный Парадокс Браесса возникает, если существует некоторое другое распределение потоков, для которых некоторые путешественники улучшили затраты путешествия, и ни у кого затраты не стали больше, чем в ситуации равновесия.

Характеристика обобщенного парадокса Браесса: установлено, что обобщенный парадокс Браесса имеет место тогда и только тогда, когда равновесное распределение потоков не является оптимальным для задачи оптимизации Браесса.

Далее рассмотрим две задачи, для которых определим условие равновесия и в приложении рассчитаем возможные ситуации равновесия в сетях.

Задача № 1.

В сети из восьми дуг двенадцать водителей должны проехать из пункта s в пункт t. В этом примере, система оптимального распределения потоков не демонстрирует наличие парадокса Браесса. Существует обобщенный парадокс Браесса. Он свидетельствует снижение потока на обеих дугах. Кроме того, можно удалить одну из поперечных дуг, но не обе, чтобы продемонстрировать наличие классического парадокса Браесса.

Решение.

Рассмотрим 4 пути, по которым могут проехать машины, и составим систему уравнений, чтобы найти решение, соответствующее равновесию по Нэшу. Составим таблицу, в которой распишем возможные пути.

Номер пути	Номера дуг, входящих в путь
1	1 – 4 – 7
2	1 – 3 – 5 – 6 - 7
3	2 – 5 – 6 - 7
4	2 – 5 – 8

Время, необходимое на преодоление каждого сегмента зависит от количества машин в данном сегменте. Пусть x1, x2, x3, x4 – количество водителей, выбравших соответствующий индексу путь. Тогда соответственно, время, затраченное на каждый путь можно записать так:

● – для первого маршрута

● – для второго маршрута

● – для третьего маршрута

● – для четвертого маршрута

После упрощения получим следующие выражения:

1.

2.

3.

4.

Для равновесия по Нэшу все эти значения должны быть равны (иначе некоторым водителям будет выгодно выбрать другой маршрут), это приводит к системе уравнений:

При этом знаем, что , тогда составим и решим следующую систему уравнений:

Используя метод Гаусса, получим решение вида:

При подстановке полученного решения в исходную систему вычислим общее время в пути, которое будет равно 288.

Задача № 2.

В сети из тринадцати дуг восемь водителей должны проехать из пункта s в пункт t.. Определить ситуацию равновесия по Нэшу.

Решение.

Рассмотрим 8 путей, по которым могут проехать машины, и составим систему уравнений, чтобы найти решение, соответствующее равновесию по Нэшу. Составим таблицу, в которой распишем возможные пути.

Номер пути	Номера дуг, входящих в путь
1	1 – 5 – 11
2	1 – 6 – 7 – 8 – 13
3	1 – 6 – 7 – 10
4	2 – 11
5	3 – 9 – 13
6	3 – 12
7	4 – 7 – 8 – 13
8	4 – 7 – 10

Время, необходимое на преодоление каждого сегмента зависит от количества машин в данном сегменте. Пусть x1, x2… x8 – количество водителей, выбравших соответствующий индексу путь. Тогда соответственно, время, затраченное на каждый путь можно записать так:
путь №1:

путь №2:

путь №3:

путь №4:

путь №5:

путь №6:

путь №7:

путь №8:

После упрощения получим следующие выражения:

1.

2.

3.

4.

5.

6.

7.

8.

Для равновесия по Нэшу все эти значения должны быть равны (иначе некоторым водителям будет выгодно выбрать другой маршрут), это приводит к системе уравнений:

При этом знаем, что , тогда составим и решим следующую систему уравнений:

Используя метод Гаусса, получим решение вида:

При подстановке полученного решения в исходную систему вычислим общее время в пути, которое будет равно 94.

Приложение

К лабораторной работе прилагаются расчеты, сделанные с помощью Excel.

К задаче №1.

Задача №1	количество машин на дуге
текущие значения	равновесие	значение оптимальное для Браесса
ячейки с изменяемыми значениями:
	поток на дуге 2	5,333	4,000	4,667
	поток на дуге 4	6,667	4,000	5,333
	поток на дуге 8	5,333	4,000	4,667
результат
	затраты системы	3456,000	3456,000	3418,667
	макс. затраты на путь	288,000	288,000	288,000

К задаче №2.

Задача № 2	Количество машин на дуге
Равновесие	Оптимальная система	Сниженные системные затраты 1	Сниженные системные затраты 2
Изменяемые ячейки:
	поток на дуге 3	4,00	2,72	4,00	2,00
	поток на дуге 4	0,00	2,55	0,00	2,00
	поток на дуге 5	4,00	2,31	0,00	4,00
	поток на дуге 9	4,00	2,31	4,00	0,00
	поток на дуге 10	0,00	2,55	2,00	0,00
	поток на дуге 11	4,00	2,72	2,00	4,00
Результат:
	Затраты системы	752,00	636,76	712,00	712,00
	Макс. затраты на путь	94,00	107,66	94,00	94,00