Курсовая: Математические методы в организации транспортного процесса - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

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

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Архив Zip, 90 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!

Узнайте стоимость написания уникальной работы

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

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




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









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


ПО


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








Выполнил:


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


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


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


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


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





























Содержание.


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


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


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





































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


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


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





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


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

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


X 11 + X 12 + X 13 + X 14 = 25

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

X 31 + X 32 + X 33 + X 34 = 30


X 11 + X 21 + X 31 = 30

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

X 13 + X 23 + X 33 = 30

X 14 + X 24 + X 34 = 30


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


Z = C ij X 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 ij X ij. (3)

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

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

S i = M j


Где, S i = X ij – cуммарное количество деталей на складах;



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


магазинах.


В данной задаче S i = M j = 100,


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


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


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

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

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


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


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

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



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

X 14 = min (25, 30) = 25

X 32 = min (30, 10) = 10

X 34 = min (20, 5) = 5

X 31 = min (15, 15) = 15

X 21 = min (45, 15) = 15

X 23 = min (30, 30) = 30


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


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


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

C ij – U i – V j = 0 (4)

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

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

C 14 – U 1 – V 4 = 0 21 – U 1 – V 4 = 0

C 21 – U 2 – V 1 = 0 25 – U 2 – V 1 = 0

C 23 – U 2 – V 3 = 0 26 – U 2 – V 3 = 0 (5)

C 31 – U 3 – V 1 = 0 23 – U 3 – V 1 = 0

C 32 – U 3 – V 2 = 0 21 – U 3 – V 2 = 0

C 34 – U 3 – V 4 = 0 21 – U 3 – V 4 = 0

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

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

U 1 = -2


U 2 = 0


U 3 = -2


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


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


V 1 = 25; U 1 = -2;

V 2 = 23; U 2 = 0;

V 3 = 26; U 3 = -2.

V 4 = 23;

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

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

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


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

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

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

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

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

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


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

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


X 14 = 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


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


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

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


Y = L i X ij ,


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

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

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

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


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

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


(X 1j – X j1) = 1.


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


(X mj – X jm) = 1.


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

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

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

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

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


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


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

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

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

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












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

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

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

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



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

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

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

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


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


Для столбца, соответствующего индексу V 6, ими будут 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. Следовательно,


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

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


Для столбца, соответствующего индексу V 8, ими будут 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. Следовательно,


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

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


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

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

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



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


V 2 = 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 определим:


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


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


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

__________________________________________________


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


1Авиация и космонавтика
2Архитектура и строительство
3Астрономия
 
4Безопасность жизнедеятельности
5Биология
 
6Военная кафедра, гражданская оборона
 
7География, экономическая география
8Геология и геодезия
9Государственное регулирование и налоги
 
10Естествознание
 
11Журналистика
 
12Законодательство и право
13Адвокатура
14Административное право
15Арбитражное процессуальное право
16Банковское право
17Государство и право
18Гражданское право и процесс
19Жилищное право
20Законодательство зарубежных стран
21Земельное право
22Конституционное право
23Конституционное право зарубежных стран
24Международное право
25Муниципальное право
26Налоговое право
27Римское право
28Семейное право
29Таможенное право
30Трудовое право
31Уголовное право и процесс
32Финансовое право
33Хозяйственное право
34Экологическое право
35Юриспруденция
36Иностранные языки
37Информатика, информационные технологии
38Базы данных
39Компьютерные сети
40Программирование
41Искусство и культура
42Краеведение
43Культурология
44Музыка
45История
46Биографии
47Историческая личность
 
48Литература
 
49Маркетинг и реклама
50Математика
51Медицина и здоровье
52Менеджмент
53Антикризисное управление
54Делопроизводство и документооборот
55Логистика
 
56Педагогика
57Политология
58Правоохранительные органы
59Криминалистика и криминология
60Прочее
61Психология
62Юридическая психология
 
63Радиоэлектроника
64Религия
 
65Сельское хозяйство и землепользование
66Социология
67Страхование
 
68Технологии
69Материаловедение
70Машиностроение
71Металлургия
72Транспорт
73Туризм
 
74Физика
75Физкультура и спорт
76Философия
 
77Химия
 
78Экология, охрана природы
79Экономика и финансы
80Анализ хозяйственной деятельности
81Банковское дело и кредитование
82Биржевое дело
83Бухгалтерский учет и аудит
84История экономических учений
85Международные отношения
86Предпринимательство, бизнес, микроэкономика
87Финансы
88Ценные бумаги и фондовый рынок
89Экономика предприятия
90Экономико-математическое моделирование
91Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
День св. Валентина 2016:
- Милый, давай поужинаем сегодня в панорамном ресторане на высоте?!
- Давай по чебуреку. И подпрыгнем.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

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

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2017
Рейтинг@Mail.ru