Экономико-математическое моделирование на транспорте

2

ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ПУТЕЙ СООБЩЕНИЯ

(МИИТ)

Российская открытая академия транспорта

Экономический факультет

Кафедра: «Экономика, финансы и управление на транспорте»

Контрольная работа№1,2

по дисциплине:

Экономико-математическое моделирование на транспорте

Воронеж 2012

Содержание

Контрольная работа №1

Задача 1

Задача 2

Задача 3

Контрольная работа №2.

Задача 1

Задача 2

Задача 3

Задача 4.

Контрольная работа №1

Задача 1

Центральной задачей оптимизации перевозок грузов на железнодорожном транспорте является прикрепление постав­щиков к потребителям с тем, чтобы общая сумма затрат на транспортировку грузов была минимальной. Такую задачу принято называть «транспортной».

Задание

1.              Построить оптимальный план перевозок каменного угля
с пяти станций A. (i - 1, 2, 3, 4, 5), до девяти крупных потребителей, имеющих подъездные пути В. (/ = 1, 2,...,9).

В контрольной работе для задачи № 1 привести две заполненные матрицы: с началь­ным планом перевозки и с оптимальным планом перевозки.

На обеих матрицах записываются ресурсы станций отправ­ления и потребности станций назначения.

2.                 Определить объем тонно-километровой работы начального и оптимального планов перевозки грузов.

Исходные данные

Данные о наличии ресурсов на пяти станциях отправления Ai, данные о размерах прибытия груза Вj. на девять станций назначения . Расстояние пере­возки от каждой i-й станции отправления до каждой i-й стан­ции назначения указано в правом верхнем углу каждой клет­ки матрицы. В левом верхнем углу ряда клеток мат­рицы указаны ограничения пропускной способности.

Ресурсы станций отправления Ai :

А1=130

А2=120

А3=400

А4=160

А5=190

Итого=1000

Объем потребности Вj получателя:

В1=185

В2=90

В3=80

В4=75

В5=105

В6=105

В7=95

В8=175

В9=90

Итого=1000

Решение

1. Порядок решения задачи следующий:

2. Предварительно записывают условия решения задачи в матричной форме. В строке Аi указыва­ют размер ресурсов у отправителей, а в столбце Вj — размер потребностей у получателей. В верхнем правом углу каждой клетки указано значение Сij — критерия оптимальности пере­возки грузов от i поставщика к j потребителю. В решении за­дачи принято, что Сij означает расстояние перевозки от i-го поставщика до j-го потребителя. Условием задачи установ­лено, что размер всех ресурсов у отправителей равен общей потребности получателей:        ∑ Аi=∑ Вj

В ряде случаев, если поставка i-го ресурса j-му получате­лю не должна превышать величины dij, то величина грузо­потока хij в клетке ij должна удовлетворять условию хij = dij. В этом случае говорят о том, что клетка ij имеет ограничение «пропускной способности», а в левом верхнем углу клетки указывается число dij .

С учетом полученных условий необходимо найти такие неотрицательные значения величин объемов перевозок хij, при которых сумма произведений значений критерия Сij на размер перевозок будет минимальной, т.е.   ∑ ∑ Сij* хij→min

Базисный план

F=30*50+50*60+120*10+100*90+75*80+175*40+50*60+90*5+30*30+40*20+65*15+80*10+45*20=41225

V4=C1,4-U1= 210
V5=C1,5-U1= 250
V7=C1,7-U1= 160
U4=C4,4-V4= 180
U3=C5,3-V5= 160
U5=C7,5-V7= 140
V6=C3,6-U3= 240
V8=C3,8-U3= 200
V9=C3,9-U3= 220
V2=C4,2-U4= 185
V1=C5,1-U5= 155
V3=C5,3-U5= 150
U2=C1,2-V1= 145

H11=155-90-100=-35

H31=155-20-160=-25

H41=155-50-180=-75

H12=185-30-100=55

H22=185-40-145=0

H32=185-35-160=-10

H52=185-25-140=20

H13=150-100-100=-50

H23=150-45-145=-40

H33=150-20-160=-30

H24=210-50-145=15

H34=210-160-160=-110

H54=210-35-140=35

H25=250-25-145=80

H45=250-120-180=-50

H55=250-25-140=85

H26=240-70-145=25

H46=240-40-180=20

H56=240-80-140=20

H27=160-15-145=0

H37=160-70-160=-70

H47=160-75-180=-95

H57=160-20-140=0

H18=200-80-100=20

H28=200-30-145=25

H48=200-30-180=-10

H58=200-70-140=-10

H19=220-90-100=30

H29=220-30-145=45

H49=220-20-180=20

H59=220-90-140=-10

max |H|55

r{5;45}=5

план перевозки

Целевая функция F=40800

Значение изменилось на 425 единиц по сравнению с предыдущим этапом.

Оптимальный план перевозки

Целевая функция F=36475

Задача 2

Задание.

Решить задачу линейного программирования графическим методом. Все переменные в задаче неотрицательные.

Целевая функция:

Ограничения:             

Решение:

1. Найдем область допустимых решений, при этом изменим, знак неравенства на знак равенства, тогда будет найдено уравнение прямой границы полуплоскости.

2. Рассмотрим первое ограничение:

3. Рассмотрим второе ограничение:

4. Рассмотрим третье ограничение:

Построим систему координат и проведем прямые ограничивающие область допустимых решений(ОДР), построив их, соответственно, по неравенствам системы ограничений.

Чтобы построить прямую нужно знать координаты двух точек.
Координаты точек прямых соответствующих неравенствам:

Построим вектор целевой функции F(1;3).

Рис.1:График области допустимых решений.

Как видно из графика, максимальной вершиной области допустимых значений будет вершина (1;0).

В данной вершине значение целевой функции равно:
F(max)=1*1+3*0=1ед.
 

Ответ: F (max) =1ед.

Задача 3

Задание.

Все переменные в задаче неотрицательные

Целевая функция:             

Ограничения:              

Решение.

1)              Задача на минимум, введем функцию, которую будем минимизировать с прежними ограничениями.

2)              Перейдем от ограничений неравенств к ограничениям равенств. Для этого введем новые переменные х4 и х5 по следующим формулам:

3)              Получим следующую основную задачу линейного программирования:

4)              Найдем вид канонической зада

чи линейного программирования. Для этого выразим в первом уравнении х1 через другие неизвестные и подставим это его выражение в остальные уравнения, а также в выражение для функции g. Получим:

5) Шаг симплекс-алгоритма. Из полученного выражения для целевой функции q видно, что для ее уменьшения следует уменьшать неизвестное х2. Все неизвестные неотрицательные.

Разрешающим элементом является число 1. Выразим х2 из х1, получим:

6) Проверка:

Ответ: целевая функция f(x) равна 30. Это решение является оптимальным при х1=0, х2=30, х3=0, т.к. коэффициенты при всех свободных переменных в целевой функции неотрицательны.

Контрольная работа №2.

Задача 1

Задание.

Требуется найти оптимальную трассу участка железнодорожного пути между пунктами А и В, из которых второй лежит к северу-востоку от первого. Местность, по которой пройдет магистраль, является пересеченной и включает  лесистые зоны, холмы болота, реку. Поэтому стоимость строительства равных по длине участков пути может быть различной, требуется так провести дорогу из А в В, чтобы суммарные затраты на сооружение участка были минимальными.

Решение:

Задача решается методом динамического программирования, последовательно двигаясь от конца трассы В к ее началу А при этом на каждом шаге процесса выбираем то направление трассы, которое делает меньшую стоимость ее строительства от рассматриваемого пункта А до пункта В.

Таблица 1

Исходные данные

Ответ: Суммарные затраты на строительство трассы участка железнодорожного пути между пунктами А и В равны 118 денежных единиц и является минимальными затратами.

Задача 2

Задание.

Предприятие имеет свободных К млрд руб. средств, кото­рые оно может вложить в пять различных производственных программ. При этом прибыль от каждой из программ зависит от объема инвестиций. Эти зависимости fx известны и имеют следующий вид:

f(x)=bx-ax2

f1(x1)=0,18x1-0,05x12

f2(x2)=0,16x2-0,04x22

f3(x3)=0,14x3-0,02x32

f4(x4)=0,12x4-0,02x42

f5(x5)=0,1x5-0,01x52 млрд руб.,

   где x1 х2, х3 х4, х5 — инвестиции в программы, млрд руб. Их общий объем К =х1 + х2 + х3 + х4 + х5 задан в исходных данных.

Исходные данные

Объем инвестиций, млрд руб. = 9,5

Требуется найти неотрицательные объемы инвестиций x1 х2, х3 х4, х5 соответствующие наибольшей общей прибыли

П=f1(x1)+f2(x2)+f3(x3)+f4(x4)+f5(x5)

Решение:

Эту задачу можно решить методами математического ана­лиза. Однако это приведет к рассмотрению большого числа вариантов. Поэтому следует предварительно отбросить за­ведомо неоптимальные варианты. Заметим, что коэффициен­ты при х убывают с возрастанием номера функции прибыли. Это говорит о том, что при малых объемах инвестиций первая программа имеет преимущество перед второй, вторая-перед третьей, третья -перед четвертой, а четвертая - пе­ред пятой. При значительных объемах инвестиций эти приоритеты могут измениться, но не может быть такой ситуа­ции, при которой программа с меньшим номером может быть не профинансирована, в то время когда программа с большим порядковым номером будет проинвестирована. Поэтому воз­можны следующие варианты: 1. Все средства передаются пер­вой программе; 2. Средства распределяются между первой и второй программами; 3. Средства распределяются между пер­вой, второй и третьей программами; 4. Средства распределя­ются между первой, второй, третьей и четвертой программа­ми; 5. Средства распределяются между первой, второй, тре­тьей, четвертой и пятой программами.

f(x1)=0,18x1-0,5x2

П=f(x1)+f2(x2)+f3(x3)+f4(x4)+f5(x5)→max

K=9,5 млрд.руб.

1) П=f1(x1)=9*0,18-0,05*92<0

2) x1+x2=9,5

f1(x1)=0,18x1-0,05x12

f2(x2)=0,16x2-0,04x22

f1(x1)/Əx1=1*0,18*x11-1-2*0,05*x12-1=0,18-2*0,05x1

f2(x2)/Əx2=0,16-2*0,04x2

  x1+x2=9,5

  0,02-0,1x1=-0,08x2

2-10x1+8x2

x1=9,5-x2

2-95+10x2+8x2

x1=9,5- x2

18 x2=93

x2=5,2

x1=9,5-5,2

x1=4,3

П2=f1(x1)=f2(x2)=-0,40

Убыточно

3) x1+x2+x3=9,5

f1(x1)=0,18x1-0,05x12

f2(x2)=0,16x2-0,04x22

f3(x3)=0,14x3-0,02x32

Əf1(x1)/Əx1=0,18-2*0,05x1

Əf2(x2)/Əx2=0,16-2*0,04x2

Əf3(x3)/Əx3=0,14-2*0,02x3

  x1+x2+x3=9,5

  9-5x1=8-4x2

  8-4x2=7-2x3

2x3=7-8+4x2

2x3=-1+4x2

x3=-1+2x2

x3=4,421

x1+3,75x1-0,75=10,5

4,75x1=11,25

x1=2,368

4x2=-1+5x1

x2=2,711

П=f1(x1)+f2(x2)+f3(x3)=0,514

Прибыль

4) x1+x2+x3+x4=9,5

f1(x1)=0,18x1-0,05x12

f2(x2)=0,16x2-0,04x22

f3(x3)=0,14x3-0,02x32

f4(x4)=0,12x4-0,02x42

  x1+x2+x3+x4=9,5

  9-5x1=8-4x2

  8-4x2=7-2x3

  7-2x3=6-2x4

2x4=6-7+2x3

x4=x3-0,5

x4=2,724

   x1+x2+2x3=10

  9-5x1=8-4x2

  8-4x2=7-2x3

  7-2x3=6-2x4

2x3=4x2-1

x3=2x2-0,5

x3=3,224

x1+5x2=11

9-5x1=8-4x2

8-4x2=7-2x3

7-2x3=6-2x4

4x2=5x1-1

x2=1,25x1-0,25

x2=1,862

x1+6,25x1-1,25=11

7,25x1=12,25

x1=1,69

П=f1(x1)+f2(x2)+f3(x3)+f4(x4)=0,743

5) x1+x2+x3+x4+x5=9,5

f1(x1)=0,18x1-0,05x12

f2(x2)=0,16x2-0,04x22

f3(x3)=0,14x3-0,02x32

f4(x4)=0,12x4-0,02x42

f5(x5)=0,1x5-0,01x52

  x1+x2+x3+x4+ x5=9,5

  9-5x1=8-4x2

  8-4x2=7-2x3

  7-2x3=6-2x4

  6-2 x4=5+ x5

x5 =2 x4-1

x5 =2,633

  x1+x2+x3+3x4=10,5

  9-5x1=8-4x2

  8-4x2=7-2x3

  7-2x3=6-2x4

   x5 =2 x4-1

2 x4=2 x3-1

x4 = x3 -0,5

x4 =1,816

  x1+x2+4x3=12

  9-5x1=8-4x2

  8-4x2=7-2x3

  x4 = x3 -0,5

2 x3=4 x2+1

x3 =2 x2-0,5

x3 =2,316

  x1+8x2=14

  9-5x1=8-4x2

  x3 =2 x2-0,5

x2 =1,25x1-0,25

x2 =1,408

x1+11,25x1-2,25=14

12,25x1=16,25

x1=1,327

П=f1(x1)+f2(x2)+f3(x3)+f4(x4)+f5(x5)=0,859

Оптимальный план инвестиций получится согласно пятому случаю.

x1=1,327   x2=1,408  x3=2,316 x4=1,816              x5=2,633

Задача 3

Задание

1.      В связи с высокими требованиями, предъявляемыми к личностным свойствам руководителей, для эффективной ра­боты в коллективе возникает потребность профессионального отбора на конкурсной основе. С этой целью осуществляется предварительная оценка профессиональной пригодности кан­дидата на руководящую должность. Требуется методом экс­пертного ранжирования из группы кадрового резерва, вклю­чающего в себя семь кандидатов, отобрать наиболее достой­ного, по мнению коллектива, из 10 экспертов.

2.      После коллективного ранжирования экспертами степени подготовленности и личностных свойств всех представителей группы кадрового резерва и выбора лучшего из них опреде­лить степень согласованности мнений группы экспертов.

Исходные данные

Каждый Эi эксперт оценивает степень подготовленности каждого члена группы кадрового резерва, сопоставив ему целое число — его ранг k ij т.е. номер члена группы в порядке убывания оценки степени подготовленности. Первый ранг имеет тот, кто, по мнению эксперта, подготовлен лучше других, второй — менее подготовлен, но лучший из оставшихся.

Индивидуальные оценки экспертами подготовленности кандидатов из группы резерва