Транспортная задача. Метод Монте-Карло. Методика изучения.

13. Транспортная задача. Имеются m пунктов отправления A1,A2,…,Am, в которых сосредоточены запасы каких-то однородных грузов в количестве a1,a2,…,am единиц соответственно. Имеются n пунктов назначения B1,B2,…,Bn, подавших заявки на b1,b2,…,bn единиц груза. Сумма всех заявок равна сумме всех запасов

i=1mai=j=1nbj (1)

Известны стоимости cij перевозки единицы груза от каждого пункта отправления Ai до каждого пункта назначения Bj (i=1,m, j=1,n)

c11c12…c1nc21c22…c2n…cm1…cm2………cmn

Считается, что стоимость перевозки нескольких единиц груза пропорциональна их числу. Требуется составить план таким образом, чтобы сумма затрат на перевозки была минимальной. Поставим эту задачу, как задачу линейного программирования. Обозначим через xij- количество единиц груза, отправленного из i-го пункта отправления Ai в j-ый пункт назначения Bj. Совокупность чисел

x11x12…x1nx21x22…x2nxm1xm2…xmn

будем называть планом перевозки, а сами величины xij- перевозками. Эти неотрицательные переменные должны удовлетворять следующим условиям:

суммарное количество груза, направленного из каждого пункта отправления во все пункты назначения, должно быть равно запасу груза в данном пункте. Это дает m условий равенств:

x11+x12+…+x1n=a1x21+x22+…+x2n=a2…xm1+xm2+…+xmn=am (2)

суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно заявке, поданной данным пунктом. Это дает n условий равенств:

x11+x21+…+xm1=b1x12+x22+…+xm2=b2…x1n+x2n+…+xmn=bn (3)

суммарная стоимость всех перевозок, т.е.

f=i=1mj=1ncijxij→min (4)

Таким образом, перед нами задача линейного программирования с условиями-равенствами (2), (3) и минимизируемой функцией (4). Особенностью этой задачи является то, что все коэффициенты в условиях (2), (3) равны 1, и это позволяет решить задачу не только симплекс-методом, но и более простыми способами. Рассмотрим один из них: заметим, что условия-равенства (2), (3) не являются линейно-независимыми, т.к. правые части связаны равенством (1). Число линейно-независимых уравнений среди уравнений (2), (3) равно не числу уравнений m+n, а равно m+n-1. Общее число переменных xij в нашей задаче равно m*n. как бы не разрешать уравнения (2), (3), число базисных неизвестных будет равно

k=m*n-m+n-1=m-1n-1, т.е.

в нашем случае для оптимального плана по крайней мере m-1(n-1) неизвестных должны быть равны нулю. Будем называть любой план перевозок допустимым, если он удовлетворяет условиям (2), (3). Допустимый план буде называть опорным, если в нем отличны от нуля не более, чем m+n-1 базисных перевозок. Остальные перевозки равны нулю. План будем называть оптимальным, если он среди всех допустимых планов приводит к минимальной суммарной стоимости перевозок.

Пункт назначения (ПН)

Пункт отправления (ПО)

Потребитель 1 (B1)

Потребитель 1 (B2)

Потребитель 1 (B3)

Потребитель 1 (B4)

Запасы на каждом складе

Склад 1

A1

2

5

4

5

60

Склад 2

A2

1

2

1

4

80

Склад 3

A3

3

1

5

2

60

Потребности потребителей

50

40

70

40

200

Обозначим через

1

2

3

4

1

x11

x12

x13

x14

2

x21

x22

x23

x24

3

x31

x32

x33

x34

Эти переменные должны удовлетворять следующим условиям:

x11+x12+x13+x14=60x21+x22+x23+x24=80x31+x32+x33+x34=60

x11+x21+x31=50x12+x22+x32=40x13+x23+x33=70x14+x24+x34=40

f=2x11+5x12+4x13+5x14+x21+2x22+x23+4x24+3x31+x32+5x33+2x34

Составим I-й опорный план, для этого воспользуемся методом северо-западного угла:

ПН

ПО

B1

B2

B3

B4

Запасы

A1

50

2

10

5

4

5

60

A2

1

30

2

50

1

4

80

A3

3

1

20

5

40

2

60

Потребности

50

40

70

40

200

m-1n-1*3-1*4-1=6

δ13=4-5+2-1=0- изменится стоимость перевозок

δ14=5-5+2-1+5-2=4

δ24=4-1+5-2=6

δ21=1-2+5-2=2

δ31=3-5+1-2+5-2=0

δ32=1-5+1-2=-5

ПН

ПО

B1

B2

B3

B4

Запасы

A1

50

2

10

5

4

5

60

A2

1

10

2

70

1

4

80

A3

3

20

1

5

40

2

60

Потребности

50

40

70

40

200

f=50*2+10*5+30*2+50+20*5+40*2=440

f=50*2+10*5+70+10*2+20+40*2=340

δ13=4-5+2-1=0

δ14=5-5-2+1=-1

δ21=1-2+5-2=2

δ24=4-2+1-2=1

δ31=3-1-2+5=5

δ33=5-1+2-1=5

ПН

ПО

B1

B2

B3

B4

Запасы

A1

50

2

5

4

5

60

A2

1

10

2

70

1

4

80

A3

3

30

1

5

30

2

60

Потребности

50

40

70

40

200

δ12=5-5+2-1=1

δ13=4-5+2-1+2-1=1

δ21=1-2+1-2+5-2=1

δ24=4-2+1-2=1

δ31=3-2+5-2=4 δ33=5-1+2-1=5

14. Метод Монте-Карло. Методика изучения.

Событие называется случайным, если оно достоверно и непредсказуемо. Когда случайность полезна: 1. Сложное вычисление, результат зависит от множества факторов; можно сократить объем вычислений за счет случайных значений значащих цифр; 2. В теории эволюции случайность – это конструктивный позитивный фактор; 3. В теории эволюции случайность проявляется в множественности ее результатов, обеспечивая гибкость реакции организмов на изменение внешней среды. Генератор псевдослучайных чисел (ГПСЧ): генерирует случайные числа по определенному алгоритму. При математическом моделировании случайных процессов, нельзя обойтись без наборов случайных чисел, удовлетворяющих некоторому закону распределения. Рассмотрим в начале генерацию чисел, равновероятно распределенных на некотором отрезке. Имеем начальное значение, которое используется для нахождения последующего и т.д. Метод вычетов или линейный конгруэнтный метод: xn=axn-1+cmodm, где a, c и m – натуральные числа. Наибольший период равен m (зависит от a и c). xnm∈0;1→x∈[a,b] rnd – функция, randomize timer – генератор запуска случайных чисел (x=a+(b-a+1)*rnd – для типа real; x=a+(b-a)*rnd – для типа integer) Метод отбора-отказа: ωx=fmax Допустим необходимо сгенерировать случайные числа с некоторой функцией распределения f(x) на интервале (a;b). Введем функцию сравнения ωx=const. Обычно ωx=fmax, ω≥f(x). Т.к. площадь под кривой f(x) для отрезка [x,x+dx] равна вероятности попадания x в этот интервал, то можем следовать процедуре проб и ошибок: генерируем два случайных числа, определяющие координаты точки в прямоугольнике ABCD. x=a+b-a*ry=ω*r. Если точка M(x;y) не попадает под фигуру f, мы ее отбрасываем, а если попадает, то оставляем. Множество координат x оставленных точек оказывается распределенными в соответствии с плотностью вероятности f(x). Этот метод особенно эффективен, когда ω близка к функции f. ω- ступенчатая функция, для max приближения к функции f. Моделирование случайных процессов в системах массового обслуживания. Агнер Краруп Эрланг (нач. XX в.) – датский ученый, основоположник теории массового обслуживания. Типичные задачи: 1. Очередь к одному продавцу: а) случайная последовательность прихода покупателей; б) длительность обслуживания каждого. 2. Ремонтный пункт в автохозяйстве и автобусы, которые сошли с маршрутов из-за поломки. 3. Травмопункт и больные с травмами. 4. Телефонная линия с одним входом и абоненты, которые выстраиваются в очередь, если он занят. 5. Сервер локальной сети и персональные компьютеры на рабочих местах. Другие примеры моделирования случайных процессов: вычисление площадей методом Монте-Карло:

Создатели Нейман и Улам.

91694011303000Задача: 1 этап. Постановка задачи. Найти площадь круга радиуса r. Круг вписан в кв.

Решение: пусть a=r. а- половина длины стороны кв. Тогда, S1=2a*2a (пл. Кв.). Случ. образом выбираем точку, принадлежащую квадрату. Точка принадлежит квадрату, если вып-ся соотн-я: -a<=x<=a, -a<=y<=a

Или -r<=x<=r, -r<=y<=r

Точка принадлежит кругу, если справедливо неравенство:

x2+y2<=r2 или x2+y2<=a2

найти случ число из [a,b], используя ф-лу:

x=(b-a)*rnd+a

для нашего случая: x=2a*rnd-a; y=2a*rnd-a

rnd выдает случ числа от 0 до 1

x=rnd x принадлежит [0;1).

3,4 этапы Алгоритмизация решения задачи и созд-е комп. Модели.

rem MonteKarlo

screen 12

randomize timer

window (-320,-240)-(320,240)

input “Введите сторону квадрата”;a

input “Введите количество точек”;k

line (-a/2,-a/2)-(a/2,a/2),15,b

circle (0,0),a/2,9

for i=1 to k

x=rnd*a-a/2

y=rnd*a-a/2

pset (x,y),14

if x^2+y^2<=(a^2)/4 then n=n+1

for j=1 to 10000

next j

next i

S=n*a^2/k

print “Приближенная площадь S = ”;S

print “Точная площадь = ”; atn(1)*4*a^2/4

end

← Предыдущая
Страница 1
Следующая →

Имеются m пунктов отправления, в которых сосредоточены запасы каких-то однородных грузов в количестве единиц соответственно. Событие называется случайным, если оно достоверно и непредсказуемо.

У нас самая большая информационная база в рунете, поэтому Вы всегда можете найти походите запросы

Искать ещё по теме...

Похожие материалы:

Метаболизм липидов

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

Основы идеологии

Основы идеологии белорусского государства. Ответы. Идеологический механизм государства и формы правления Республики Беларусь, совокупность идей. Идеологические центры и учреждения Республики Беларусь РБ.

Клерикальная литература Высокого Средневековья

Основные теории мотивации

Типологии мотивации. Мотивация - одна из важнейших функций менеджмента. Она подразумевает систему факторов (побудительных сил), способствующих выполнению определенной задачи, направленной на достижение целей предприятия.

Задание на выполнение дипломного проекта (работы)

Кафедра Математика и информационные технологии

Сохранить?

Пропустить...

Введите код

Ok