Решение транспортной задачи - Программирование, компьютеры и кибернетика курсовая работа

Определение оптимального плана перевозок однородного груза из k-пунктов отправления в m-пункты назначения. Описание алгоритма нахождения потока минимальной стоимости. Решение транспортной задачи вручную и в среде MathCad, сравнение полученных результатов.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
ФАКУЛЬТЕТ КОМПЬЮТЕРНЫХ НАУК И ЭЛЕКТРОНИКИ
Тема: "Решение транспортной задачи"
Выполнила: Долгополова Анастасия 4902BD
3. Теоретическое обоснование. Общие вопросы
4. Описание алгоритма нахождения потока минимальной стоимости
5. Решение индивидуального задания по шагам
Математическая постановка задачи. Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза k-пунктов отправления а 1 ,а 2 ,…а i в m пунктов назначения b 1 ,b 2 ,…b j . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость всего груза, либо минимальное время его доставки. Данная транспортная задача была рассмотрена, где в качестве критерия оптимальности была взята минимальная стоимость перевозок все груза. Были введены следующие обозначения:
а 1 - возможности i-ro производителя
с i , j - транспортные издержки (расходы) за доставку продукции от i к j.
x i , j - объемы перевозок от i к j.
Требуется составить план перевозок для которого:
2. общие транспортные расходы минимальны
Общая сумма производимой продукции больше или равна спросу:
Следовательно c i , j тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через a i - запасы груза в i-м пункте отправления, через b j - потребности в грузе в j-м пункте назначения, а через х i , j - количество единиц груза, переводимого из i-го пункта определений в j-й пункт назначения. Тогда математическая постановка транспортной задачи состоит в определении минимального значения функции.
На рисунке 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)
Выход: максимальный поток с минимальной стоимостью.
Идея: Каждая итерация ставит своей целью увеличить поток в сети. Для этих целей предназначен инкрементальный граф, который позволяет увеличить поток на некоторую фиксированную величину. Наличие прямых дуг позволяет увеличить поток на соответствующей дуге сети. Обратная дуга уменьшает поток. Алгоритм заканчивается когда в инкрементальном графе нет пути от источника к стоку.
Данный шаг осуществляется только один раз. Вначале мы присваиваем всем дугам нулевой поток:
Для текущего потока строится инкрементальный граф. Прямые дуги имеются, если поток на этой дуге меньше, чем пропускная способность:
Обратные дуги (дуги противоположны по отношению к ориентации прямых дуг) имеются, если на дугах имеется поток.
Каждой дуге переписываем стоимость дуги. Если е прямая, то длинна, равна стоимости пересылки, если е обратная, то ее длинна - это стоимость, но при отрицательном значении.
Назначаем длины дуг для инкрементального графа:
Нахождение кратчайшего пути в инкрементальном графе из источника v в сток u. Если такого пути нет, то происходит конец алгоритма. Найденный путь является максимальным.
Нахождение минимального Д. Просматриваем дуги кратчайших путей в инкрементальном графе. Для каждой дуги определяем величину Д.
Величина, на которую можно увеличить поток. Находим минимальное значение на всех этих дугах.
Наращивание потока в сети. Корректируем поток на дугах в соответствии последнего пути в инкрементальном графе.
На этих дугах, поток изменяется по правилам:
Алгоритм завершается, если заданная величина потока достигнута.
5. Решение индивидуального задания по шагам
Рис. 16. Увеличение потока в сети. Конец алгоритма.
· Заданная величина потока Givenflof =155
Пропускная способность дугСтоимость пересылки по дугам
Где, P - поток в сети; Tekflow - текущая величина потока, Givenflofw - заданная величина потока, Vect - величина на данной дуге, L -метки
Данная программа была решена двумя способами: в ручную и в среде MathCad. Результаты решения обеих вариантов совпадают, значит, можно сделать вывод о том, что поставленная транспортная задача, была решена, верно. По результатам вычислений, можно составить следующий план перевозок:
Потребитель b1 получает от поставщика a1 38 единиц товара
Потребитель b1 получает от поставщика a2 4 единиц товара
Потребитель b2 получает от поставщика a2 35 единиц товара
Потребитель b4 получает от поставщика a2 6 единиц товара
Потребитель b3 получает от поставщика a3 63 единиц товара
Потребитель b4 получает от поставщика a3 9 единиц товара
У поставщика а3 осталось 25 единиц товара не реализовано
Из выше перечисленного следует следующая реализация единиц ресурсов:
Потребители, которые получают от соответствующего поставщика ресурсы
Из приведенной таблицы видно, что два первых поставщика (а1 и а2) полностью реализуют поставки выделенных ресурсов. У третьего поставщика (а3) в наличии еще 25,77% единиц не реализованной продукции.
С() = 38*10 + 4*16 + 35*14 + 6*25 + 63*22 + 9*30 = 380 + 64 + 490 + 150 + 1386 + 270 = 2740
По окончанию данной работы я могу сказать, что данная работа была для меня как интересной, так и полезной. Благодаря ней я лучше научилась разбираться в транспортных задачах, в потоках и сетях. Сама задача мне не показалась достаточно сложной, при ее выполнение особых проблем не возникало. Также в данном курсе нас познакомили с такой средой как MathCad. Одной из главных задач данной работы было решение и сравнение транспортной задачи вручную и в среде MathCad. Подводя итоги данной работы, я убедилась, что задача была решена, верно, так как решение совпадает. Но стоит сказать, что решение данной задачи вручную мне понравилось гораздо больше, так как здесь пришлось анализировать различные факторы при нахождении минимального пути. Я надеюсь, что данная работа помогла мне лучше разобраться в данной теме.
Особенности решения транспортной задачи распределительным методом и анализ результатов. Построение математической модели, алгоритма. Создание программы для решения транспортной задачи распределительным методом в программной среде Borland Delphi 7. курсовая работа [1000,7 K], добавлен 23.06.2012
Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения. курсовая работа [2,0 M], добавлен 12.02.2013
Основные этапы решения транспортной задачи, использование метода потенциалов. Алгоритм решения методом аппроксимации Фогеля. Процедура построения цикла. Планирование перевозок из конечного числа пунктов отправления в конечное число пунктов назначения. контрольная работа [32,6 K], добавлен 26.04.2011
Стандартная и каноническая форма записи задачи линейного программирования. Ее запись на листе MS Excel. Математическая модель транспортной задачи, состоящей в определении оптимального плана перевозок некоторого однородного груза, результаты ее решения. контрольная работа [1,1 M], добавлен 25.01.2016
Сущность и постановка транспортной задачи для n переменных, их виды, применение и пример решения в MS Excel. Управляющие структуры ветвления Maple языка (if предложение). Решение транспортной задачи в векторных координатах для двух и трёх матриц. дипломная работа [109,3 K], добавлен 12.01.2011
Математическая постановка транспортной задачи открытой модели методом потенциалов при известных показателях запаса груза поставщика и потребности потребителя; ее решение ручным способом и с помощью компьютерной программы, написанной в среде Delphi. курсовая работа [167,2 K], добавлен 16.01.2011
Расчеты по таблице перевозок грузов между отдельными регионами. Решение задачи управления процессами перевозок в среде Pascal. Решение задачи средствами MS Excel. Исходные данные и итоги по строкам и столбцам. Решение задачи средствами MATHCAD. курсовая работа [1,8 M], добавлен 25.03.2015
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Решение транспортной задачи курсовая работа. Программирование, компьютеры и кибернетика.
Реферат по теме Методы толкования конституции в деятельности Верховного суда США
Реферат: Изготовление резного кубка. Скачать бесплатно и без регистрации
Реферат по теме Психологическая мотивация деятельности в юридической отрасли
Реферат по теме Реально ли бессмертие
Форма (виды) государственного долга.
Смешные Сочинения Детей 1 2 Классов
Реферат по теме Литература и искусство в годы Великой Отечественной войны
Курсовая работа: Реконструкция картины мира человека сталинской эпохи
Курсовая работа по теме Таблоїдний формат українського телевізійного контенту на прикладі телеканалу СТБ
Реферат: Дорошенко, Пётр Дорофеевич
Қазақ Хандығының Эссе
Контрольная работа по теме Устройство преобразования аналоговых сигналов
Статья На Тему Incorporation Of [2,3,4,5,6-2h5]Phenylalanine, [3,5-2h2]Tyrosine, And [2,4,5,6,7-2h5]Tryptophan Into The Bacteriorhodopsin Molecule Of Halobacterium Halobium
Курсовая Работа Про Грипп
Курсовая работа по теме Анализ экономических показателей предприятия
Контрольная работа по теме Особенности и порядок начисления трудовой пенсии по инвалидности
Сочинение Про Тюменскую Область
Основные Требования К Квалификации Экспертов Реферат
Горизонтальный Анализ Прибыли Курсовая
Реферат: Анализ доходов и расходов федерального бюджета Российской Федерации
Состав коровьего, грудного и козьего молока - Кулинария и продукты питания реферат
Анализ системы управления в ООО "Гермес Продукт" - Менеджмент и трудовые отношения отчет по практике
Анатомо-фізіологічні особливості нервової системи в дітей. Нервово-психічний розвиток дитини - Медицина реферат