Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Математические методы в организации транспортного процесса
Раздел: Рефераты по математике
Тип: реферат Добавлен 03:08:46 26 августа 2005 Похожие работы
Просмотров: 131 Комментариев: 2 Оценило: 2 человек Средний балл: 2.5 Оценка: неизвестно     Скачать
Пояснительная записка.

Тема: Математические методы в организации транспортного процесса.
Раздел: Вычислительная математика.
Назначение: Курсовая работа.
Формат: WinWord.
Автор: Калинкин Степан; E-mail: stepan12@chat.ru
Использование: 2001 - Северо-Западный Государственный Заочный Технический Университет - Санкт-Петербург
Кафедра информатики и вычислительной математики; Преподаватель: Петухова Наталья Михайловна
Оценка: 4 (хорошо).
Примечания: Работа содержит две транспортных задачи с подробным описанием их решения.

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

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


Содержание.


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.


---- 11 ----



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

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


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


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


ПО


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


Выполнил:


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


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


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


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


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



__________________________________________________


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


Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений22:22:35 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
11:53:33 24 ноября 2015

Работы, похожие на Реферат: Математические методы в организации транспортного процесса

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150051)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru