Математические методы в организации транспортного процесса

СЕВЕРО-ЗАПАДНЫЙЗАОЧНЫЙ ТЕХНИЧЕСКИЙУНИВЕРСИТЕТ

­­­­­­­­­­­­­­­__________________________________________________

Содержание.

1.Задача №2…………………………………………………………3

2.Задача №3…………………………………………………………7

3.Списоклитературы……………………………………………...12

ЗАДАЧА 2 Вариант –18

1. Условиезадачи.

Требуетсяперевезтитовары с трёхскладов в четыремагазина. Дан­ныео наличии товаровна складе, спросна него в магазинах,а также стои­мостиперевозкиединицы грузамежду складамии магазинамиприведены втаблице. Составитьплан перевозки,чтобы затратыбыли минимальными.

2. Построениематематическоймодели.

ПустьX ij– количестводеталей, отправленныхсо склада iв магазин j,а C ij– стоимостьперевозки однойдетали со складаi вмагазин j.Очевидно, чтоX ij> 0 и Cij> 0.

Всилу ограниченийна возможностьпоставки товарасо склада испрос в магазинахвеличина Xijдолжна удовлетворятьследующимусловиям:

X11+ X 12+ X 13+ X 14= 25

X21+ X 22+ X 23+ X 24= 45 (1)

X31+ X 32+ X 33+ X 34= 30

X11+ X 21+ X 31= 30

X12+ X 22+ X 32= 10 (2)

X13+ X 23+ X 33= 30

X14+ X 24+ X 34= 30

Общаястоимостьперевозокравна:

Z = C ijX ij = 21* X 11+ 36* X 12 + 28* X 13+ 21* X 14 + 25* X 21+

35*X 22+ 26* X 23+ 25* X 24+ 23* X 31+ 21* X 32+ 27* X 33+ 21* X 34,

т.е. Z = C ijX ij. (3)

Необходимоопределитьтакие неотрицательныезначения переменныхX ij,которые удовлетворяютограничениям(1) и (2) и обращаютв минимум целевуюфункцию Z(3). В такойпостановкезадача являетсятранспортнойзадачей линейногопрограммирования.

Необходимыми достаточнымусловием разрешимоститранспортнойзадачи являетсяусловие баланса:

Si = M j

Где, Si = Xij– cуммарноеколичестводеталей наскладах;

Mj = X ij– суммарноеколичестводеталей, требуемоев

магазинах.

Вданной задачеSi = Mj = 100,

Следовательно,задача с балансом.

3. Решениезадачи.

Решениезадачи состоитиз двух этапов:

1. Определениедопустимогорешения.

2. Определениеоптимальногорешения путёмпоследовательногоулучшениядопустимогорешения методомпотенциалов.

Определениедопустимогорешения методомнаименьшейстоимости.

Наоснове исходнойтаблицы построимвспомогательнуютаблицу (в

верхнемправом углукаждой клеткибудем записыватьстоимостиперевозки).Введём в таблицувспомогательнуюстроку и столбецдля записиостатков.

Определимнаименьшуюстоимостьперевозки:

X14= min (25, 30) = 25

X32= min (30, 10) = 10

X34= min (20, 5) = 5

X31= min (15, 15) = 15

X21= min (45, 15) = 15

X23= min (30, 30) = 30

Стоимостьперевозки Z= 25*21 + 25*15 + 30*26 + 15*23 + 10*21 + 5*21 = 2340 усл.ед.

Последовательноеулучшениедопустимогорешения методомпотенциалов.

ВыберемвспомагательныепеременныеU iи Vj, обращающиев нули коэффициентыпри базисныхпеременных,то есть

Cij– U i– V j= 0 (4)

Такиепеременныеназываютсяпотенциалами.Выполним следующиедействия:

1. Длявсех Xij> 0 (т. е. длявсех занятыхклеток) составимпотенциальныеуравнения:

C14– U 1– V 4= 0 21 – U 1– V 4= 0

C21– U 2– V 1= 0 25 – U 2– V 1= 0

C23– U 2– V 3= 0 26 – U 2– V 3= 0 (5)

C31– U 3– V 1= 0 23 – U 3– V 1= 0

C32– U 3– V 2= 0 21 – U 3– V 2= 0

C34– U 3– V 4= 0 21 – U 3– V 4= 0

Дляопределенияm + n потенциаловнеобходимо,чтобы было m+ n – 1 уравнений(где m –число строк,n – числостолбцов). Тогдаодному из потенциаловможно присвоитьлюбое значение,например равноенулю, а значениядругих потенциаловполучить, решаясистему уравнений(5).

Дляданной задачиm + n – 1 = 6 ичисло занятыхклеток равно6.

U1= -2

U2= 0

U3= -2

V1= 25 V 2= 23 V 3= 26 V 4= 23

2. Решимсистему уравнений4, присвоивзначение, равноенулю, наиболеечасто встречающемусянеизвестномуиндексу: U2= 0, тогда

V 1= 25; U 1= -2;

V 2= 23; U 2= 0;

V 3= 26; U 3= -2.

V 4= 23;

Занесёмданные в таблицувыше.

2. Длявсех небазисныхпеременных,т. е. для X ij= 0 (для пустыхклеток), определимневязки:

Gij= C ij– S ij, где Sij= U i+ V j.

G11= C 11– U 1– V 1; G 11= 27 – (-2) – 25 = 4;

G12= C 12– U 1– V 2; G 12= 36 – (-2) – 23 = 15;

G13= C 13– U 1– V 3; G 13= 28 – (-2) – 26 = 4; (6)

G22= C 22– U 2– V 2; G 22=35 – 0 – 23 = 12;

G24= C 24– U 2– V 4; G 24= 25 – 0 – 23 = 2;

G33= C 33– U 3– V 3; G 33= 27 – (-2) – 26 = 3.

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

Такимобразом, минимальнаястоимостьперевозок Zравна 2340усл. ед. и достигаетсяпри объёмахперевозок:

X14= 25, X 21= 15, X 23= 30, X 31= 15, X 32= 10, X 34= 5.

ЗАДАЧА 3

1. Условиезадачи.

Фирмадолжна наладитьперевозкупродуктов сбазы в 7 магазинов.Сеть дорог,связывающаябазу и магазинымежду собой,а также длиныучастков дорогимежду каждойпарой соседнихпунктов представленына рисунке.

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

Х 4

Х 1 Х 7 Х 5

Х 3

Х 2

Х8

Х 6

2. Построениематематическоймодели.

ПустьG(A, U)– граф, где A– множествовершин, означающихобъекты (базу– вершина 1, амагазины –вершины 2, 3, 4, 5, 6, 7,8), U– множестворёбер, означающихвозможную связьмежду двумявершинами.Каждому ребрупоставленов соответствиенекоторое числоL ij(i, j = 1, 2,…, 8 – весребра (расстояниемежду двумявершинами).

Задачаотысканиякратчайшегопути из вершиныi ввершину jзаключаетсяв минимизациицелевой функции:

Y = L iX ij,

гдеX ij= 1, если путьпроходит извершины iв вершину j,

Xij= 0, в противномслучае.

Даннаяфункция определяетдлину междузаданной начальнойи конечнойвершинами.

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

(Xij– X ji)= 0, i = 2, 3,…,m – 1

(т.е. для любойвершины i,исключаяначальную иконечную, числопутей, входящихв эту вершину,равно чисупутей, выходящихиз неё);

(X1j– X j1)= 1.

(т. е. в последнюювершину входитна один путьбольше, чемвыходит);

(Xmj– X jm)= 1.

(т. е.количествопутей, входящихв вершину 1,превышает наединицу числопутей, выходящихиз неё).

Необходимоопределитьтакие значенияX ij,равные 0 или 1,которые

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

Даннаязадача являетсязадачей о кратчайшемпути и можетбыть

решенаиндексно –матричнымметодом.

3. Решениезадачи.

Составимматрицу весовграфа, представленногона рисунке.Эле-

ментL ijэтой матрицыравен весуребра, есливершины iи jсвязаны междусобой ребром,и бесконечности– в противномслучае. Диагональныеэлементы такжеравны бесконечности,так как графбез петель. Длянаглядностив матрицу весовбесконечностизаписыватьне будем, оставляясоответствующиеим клетки пустыми.

Добавимк составленнойтаким образомматрице нулевуюстроку и

нулевойстолбец, в которыебудем записыватьсоответственноиндексы столбцови строк Uiи Vj(U i– расстояниеот вершины 1 довершины i,V j– расстояниеот вершины 1 довершины j).Тогда матрицавесов будетиметь вид,представленныйв таблице ниже.

Для вычисленияиндексов выполнимследующиедействия:

1. ПоложимU 1= V 1= 0/

2. Значениявсех заполненныхклеток первойстроки перенесёмна

соответствующиеместа индексовстолбцов Vjи строкU i, т. е. V 2= 8, V3= 10, V 4= 10, V 7= 12, U 2= V 2= 8, U3= V 3= 10, U 4= V 4= 10, U 7= V 7= 12 (смотритетаблицу ниже)

3. Определимнедостающиеиндексы Vj.В нашем примереэто индексы

V5,V 6и V 8.Для этого вкаждом столбце,соответсвующемнеизвестномуиндексу V j,просмотримзаполненныеклетки и вычислимнедостающиеиндексы поформуле V j= U i+ L ij,если дляних известныиндексы Ui.

Длястолбца, соответствующегоиндексу V5,этими элементамибудут L 4,5 = 16и L 7,5 = 25. ЗначенияU 4и U 7известны: U 4= 10, U 7= 12.

Следовательно,

V5= min(U 4+ L 4,5 = 10 + 16 = 26; U 7+ L 7,5 = 12 + 25 = 37) = 26.

Длястолбца, соответствующегоиндексу V6,ими будут L 2,6 = 7, L 3,6 = 17, L 7,6 = 18. Значенияиндексов U 2,U 3,U 7известны: U 2= 8, U 3= 10, U 7= 12. Следовательно,

V6= min(U 2+ L 2,6 = 8 + 7 = 15; U 3+ L 3,6 = 10 + 17 = 27;

U7+ L 7,6 = 12 + 18 = 30) = 15.

Длястолбца, соответствующегоиндексу V8,ими будут L 5,8 = 17, L 6,8 = 13, L 7,8 = 19. Значенияиндексов U 5,U 6,U 7известны: U 5= 26, U 6= 15, U 7= 12. Следовательно,

V8= min(U 5+ L 5,8 = 26 + 17 = 43; U 6+ L 6,8 = 15 + 13 = 28;

U7+ L 7,8 = 12 + 19 = 31) = 28.

Запишемих в строку V i(смотритетаблицу ниже).

4. Всеиндексы найдены.Проверим полученноерешение на

оптимальность,т. е. выполнениеусловия Lij>= V j– U iдля каждойзаполненнойклетки матрицы.

Длявсех заполненныхклеток условиеL ij>= V j– U iсоблюдается.Полученноерешение являетсяоптимальным.Следовательно,минималь­нымирасстояниямиот вершины 1 довсех остальныхбудут:

V2= 8, V 3= 10, V 4= 10, V 5= 26, V 6= 15, V 7= 12, V 8= 28.

Определимкратчайшийпуть от вершины1 до вершины 5.Для этого встолбце 5 найдёмэлемент, значениекоторого равноразности индексовстолбца и строкиL ij= V j– U i:

L 4,5 = V 5– U 4= 26 – 10.

L 4,5 – последнеезвено пути и,соответственно, вершина4 – предпоследняя.

Идалее, в столбце4 определим:

L1,4 =V 4– U 1= 10 – 0 = 10.

L 1,4 – первоезвено пути, таккак вершина1 является начальнойфиксированной.

Такимобразом, имеемминимальныйпуть от вершины1 до вершины 5,проходящийчерез вершины1, 4, 5, длинакоторого равна26.

----11 ----

СЕВЕРО-ЗАПАДНЫЙЗАОЧНЫЙ ТЕХНИЧЕСКИЙУНИВЕРСИТЕТ

­­­­­­­­­­­­­­­__________________________________________________­­­­­­­­­­­­­­­­­­­­­­

КАФЕДРАИНФОРМАТИКИИ ВЫЧИСЛИТЕЛЬНОЙМАТЕМАТИКИ

КУРСОВАЯРАБОТА

ПО

ВЫЧИСЛИТЕЛЬНОЙМАТЕМАТИКИ

Выполнил:

Студент2 курса заочногоотделения

КалинкинСтепан Валерьевич

Факультет:ЭМиАТ

Специальность:1502

Зачётнаякнижка: №96 – 0084

__________________________________________________

САНКТ-ПЕТЕРБУРГ2001