Банк рефератов содержит более 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)

Курсовая работа: Решение транспортной задачи

Название: Решение транспортной задачи
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 18:17:10 15 декабря 2010 Похожие работы
Просмотров: 931 Комментариев: 2 Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать

ИНСТИТУТ ТРАНСПОРТА И СВЯЗИ

ФАКУЛЬТЕТ КОМПЬЮТЕРНЫХ НАУК И ЭЛЕКТРОНИКИ

Курсовая работа

Тема:"Решение транспортной задачи"

Выполнила: Долгополова Анастасия 4902BD

Рига

2010


Оглавление

1. Постановка задачи

2. Формулировка задачи

3. Теоретическое обоснование. Общие вопросы

4. Описание алгоритма нахождения потока минимальной стоимости

5. Решение индивидуального задания по шагам

6. Программа (Mathcad)

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

8. Результат программы

9. Конечные результаты

Вывод


1. Постановка задачи

Математическая постановка задачи. Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза k-пунктов отправления а12 ,…аi в m пунктов назначения b1 ,b2 ,…bj . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость всего груза, либо минимальное время его доставки. Данная транспортная задача была рассмотрена, где в качестве критерия оптимальности была взята минимальная стоимость перевозок все груза. Были введены следующие обозначения:

k – число поставщиков;

m– число потребителей;

i– индекс производителя i=1,к

j– индекс потребителя j= 1,m

а1 – возможности i-ro производителя

bj– спрос j-ro потребителя

сi , j – транспортные издержки (расходы) за доставку продукции от i к j.

xi , j – объемы перевозок от i к j.

Требуется составить план перевозок для которого:

1. все потребители удовлетворены

2. общие транспортные расходы минимальны

Требуется минимизировать функцию:

Ограничения по производству:


Общая сумма производимой продукции больше или равна спросу:

Следовательно ci , j тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через ai – запасы груза в i-м пункте отправления, черезbj – потребности в грузе в j-м пункте назначения, а через хi , j – количество единиц груза, переводимого из i-го пункта определений в j-й пункт назначения. Тогда математическая постановка транспортной задачи состоит в определении минимального значения функции.

2. Формулировка задачи

Число производителей

k=3

а1 =38

Объем производимой продукции

а2 =45

а3 =97

Число потребителей

m=4

b1 =42

b2 =35

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

b3 =63

B4 =15

Производители Потребители
j=1 j=2 j=3 j=4
i=1 10 11 18 32
i=2 16 14 20 25
i=3 26 28 22 30

Рис. 1

На рисунке 1 представлен исходный граф, который иллюстрирует транспортную задачу. Для решения данной задачи требуется использовать стандартную форму фиксированного источника и стока. Каждый производитель связан с каждым потребителем. Источник не может иметь связи с потребителем, но зато каждый потребитель, в свою очередь, связан с фиктивным стоком. В обозначении дуги присутствует два параметра. Первый параметр указывает пропускную способность дуги, второй параметр показывает стоимость пересылки единицы потока на дуге. Так, например, из источника выходят дуги содержащие ограничения по пропускной способности, т.к. данная величина характеризует производительную возможность каждого поставщика, стоимость данной дуги равна нулю, т.к. источник – фиксированный элемент нашего графа. Такая же ситуация обстоит с дугами, которые втекают в сток. Дуги, которые выходят из i-ых вершин (производители) и входят j-ые вершины (потребители), т.е. соединяющие поставщика со складок, характеризуются тоже двумя параметрами. Только в этом случае, для данных дуг, в качестве первого параметра берется пропускная способность дуги равная бесконечности, а второй показатель – стоимость пересылки единицы потока.

3. Теоретическое обоснование. Общие вопросы

Сеть (транспортная сеть) – частный случай ориентированного графа. Транспортная сеть G=( V,E) – ориентированный граф, в котором каждое ребро имеет неотрицательную пропускную способность. Выделяются две вершины: источник v и сток u такие, что любая другая вершина сети лежит на пути из v в u. v – это единственная вершина (v – источник ), которая не содержит входящих дуг , а содержит только выходящие дуги. u – это единственная вершина (u - сток), которая не содержит выходящих дуг. Все остальные вершины – промежуточные вершины. Для любой промежуточной вершины существует путь из источника в сток. Сеть не содержит контуров. Если для сети указаны пропускные способности, то такая сеть называется транспортной сетью.

Поток – это определенная величина на дуге е. Поток в сети G=( V,E) – это функция f, заданная на дугах сети, значение на дуге е – это величина на дуге е. Для всех промежуточных вершин соответствует сумма величин потоков на дугах входящих в вершину w, которая равна выходящему из вершины потоку.

Величина потока в сети.

Величина всего потока в сети модуля равна сумме величин потока выходящих из источника или сумме входящих величин потока входящих в сток.

Поток минимальной стоимости – задача о потоке минимальной стоимости состоит в нахождении самого дешевого способа передачи определенного количества потока через транспортную сеть.

Обозначения:

Для всех дуг имеется пропускная способность:

Стоимость пересылки единицы потока по дуге e: C(e)

Накладываются следующие условия:

1. Ограничение пропускной способности . Поток не может превысить пропускную способность.

2. Антисимметричность: . Поток из u в v должен быть противоположен потоку из v в u.

4. Описание алгоритма нахождения потока минимальной стоимости

Вход: транспортная сеть G=( V,E)с пропускной способностью дуг B(e)

Выход: максимальный поток с минимальной стоимостью.

Идея: Каждая итерация ставит своей целью увеличить поток в сети. Для этих целей предназначен инкрементальный граф, который позволяет увеличить поток на некоторую фиксированную величину. Наличие прямых дуг позволяет увеличить поток на соответствующей дуге сети. Обратная дуга уменьшает поток. Алгоритм заканчивается когда в инкрементальном графе нет пути от источника к стоку.

Алгоритм:

Шаг 0

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

Шаг 1

Для текущего потока строится инкрементальный граф. Прямые дуги имеются, если поток на этой дуге меньше, чем пропускная способность:

Обратные дуги (дуги противоположны по отношению к ориентации прямых дуг) имеются, если на дугах имеется поток.

Каждой дуге переписываем стоимость дуги. Если е прямая, то длинна, равна стоимости пересылки, если е обратная, то ее длинна – это стоимость, но при отрицательном значении.

Назначаем длины дуг для инкрементального графа:

· Для прямой дуги: e:C(e)

· Для обратной дуги: e: - C(e)

Шаг 2

Нахождение кратчайшего пути в инкрементальном графе из источника vв сток u. Если такого пути нет, то происходит конец алгоритма. Найденный путь является максимальным.

Шаг 3

Нахождение минимального Δ. Просматриваем дуги кратчайших путей в инкрементальном графе. Для каждой дуги определяем величину Δ.

Для каждой прямой дуги:

Для каждой обратной дуги:

Величина, на которую можно увеличить поток. Находим минимальное значение на всех этих дугах.

Шаг 4

Наращивание потока в сети. Корректируем поток на дугах в соответствии последнего пути в инкрементальном графе.

На этих дугах, поток изменяется по правилам:

Для прямых дуг:

Для обратных дуг:

Алгоритм завершается, если заданная величина потока достигнута.

Переход к шагу 1.


5. Решение индивидуального задания по шагам

Рис. 2. Нулевой поток.

Рис.3. Инкрементальный граф


Рис. 4. Увеличения потока в сети

Рис.5. Инкрементальный граф


Рис. 6. Увеличение потока в сети

Рис.7. Инкрементальный граф


Рис. 8. Увеличение потока в сети

Рис.9. Инкрементальный граф


Рис. 10. Увеличение потока в сети

Рис.11. Инкрементальный граф


Рис. 12. Увеличение потока в сети

Рис.13. Инкрементальный граф


Рис. 14. Увеличение потока в сети

Рис.15. Инкрементальный граф


Рис. 16. Увеличение потока в сети. Конец алгоритма.

6. Программа ( Mathcad )

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

· Число вершин n=9

· Очень большое число q=∞

· Заданная величина потока Givenflof=155

Пропускная способность дугСтоимость пересылки по дугам

Где, P – поток в сети; Tekflow – текущая величина потока, Givenflofw– заданная величина потока, Vect –величина на данной дуге, L -метки


7. Результаты программы

Величина потока


Стоимость потока

Price – стоимость

8. Конечный результат программы

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

Рис. 17. Конечный результат


Потребитель b1 получает от поставщика a1 38 единиц товара

Потребитель b1 получает от поставщика a2 4 единиц товара

Потребитель b2 получает от поставщика a2 35 единиц товара

Потребитель b4 получает от поставщика a2 6 единиц товара

Потребитель b3 получает от поставщика a3 63 единиц товара

Потребитель b4 получает от поставщика a3 9 единиц товара

У поставщика а3 осталось 25 единиц товара не реализовано

Из выше перечисленного следует следующая реализация единиц ресурсов:

Поставщики (реализованные ресурсы) Потребители, которые получают от соответствующего поставщика ресурсы
а1 – 100% b1
а2 – 100% b1, b2, b4
а3 – 74,22% b3, b4

Из приведенной таблицы видно, что два первых поставщика (а1 и а2) полностью реализуют поставки выделенных ресурсов. У третьего поставщика (а3) в наличии еще 25,77% единиц не реализованной продукции.

Общая стоимость:

С() = 38*10 + 4*16 + 35*14 + 6*25 + 63*22 + 9*30 = 380 + 64 + 490 + 150 + 1386 + 270 = 2740


9. Вывод

По окончанию данной работы я могу сказать, что данная работа была для меня как интересной, так и полезной. Благодаря ней я лучше научилась разбираться в транспортных задачах, в потоках и сетях. Сама задача мне не показалась достаточно сложной, при ее выполнение особых проблем не возникало. Также в данном курсе нас познакомили с такой средой как MathCad. Одной из главных задач данной работы было решение и сравнение транспортной задачи вручную и в среде MathCad. Подводя итоги данной работы, я убедилась, что задача была решена, верно, так как решение совпадает. Но стоит сказать, что решение данной задачи вручную мне понравилось гораздо больше, так как здесь пришлось анализировать различные факторы при нахождении минимального пути. Я надеюсь, что данная работа помогла мне лучше разобраться в данной теме.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений07:39:49 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
08:12:40 29 ноября 2015

Работы, похожие на Курсовая работа: Решение транспортной задачи

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

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



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

Рейтинг@Mail.ru