Определение оптимального плана перевозок однородного груза из k-пунктов отправления в m-пункты назначения. Описание алгоритма нахождения потока минимальной стоимости. Решение транспортной задачи вручную и в среде MathCad, сравнение полученных результатов.
Аннотация к работе
Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза k-пунктов отправления а1,а2,…аі в m пунктов назначения b1,b2,…bj. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость всего груза, либо минимальное время его доставки. Данная транспортная задача была рассмотрена, где в качестве критерия оптимальности была взята минимальная стоимость перевозок все груза.Для решения данной задачи требуется использовать стандартную форму фиксированного источника и стока. Каждый производитель связан с каждым потребителем. Источник не может иметь связи с потребителем, но зато каждый потребитель, в свою очередь, связан с фиктивным стоком. Первый параметр указывает пропускную способность дуги, второй параметр показывает стоимость пересылки единицы потока на дуге. Так, например, из источника выходят дуги содержащие ограничения по пропускной способности, т.к. данная величина характеризует производительную возможность каждого поставщика, стоимость данной дуги равна нулю, т.к. источник - фиксированный элемент нашего графа.Выделяются две вершины: источник v и сток u такие, что любая другая вершина сети лежит на пути из v в u. v - это единственная вершина (v - источник ), которая не содержит входящих дуг , а содержит только выходящие дуги. u - это единственная вершина (u - сток), которая не содержит выходящих дуг. Если для сети указаны пропускные способности, то такая сеть называется транспортной сетью. Поток в сети G=( V,E) - это функция f, заданная на дугах сети, значение на дуге е - это величина на дуге е. Для всех промежуточных вершин соответствует сумма величин потоков на дугах входящих в вершину w, которая равна выходящему из вершины потоку. Величина всего потока в сети модуля равна сумме величин потока выходящих из источника или сумме входящих величин потока входящих в сток.Идея: Каждая итерация ставит своей целью увеличить поток в сети. Для этих целей предназначен инкрементальный граф, который позволяет увеличить поток на некоторую фиксированную величину. Наличие прямых дуг позволяет увеличить поток на соответствующей дуге сети. Алгоритм заканчивается когда в инкрементальном графе нет пути от источника к стоку. Прямые дуги имеются, если поток на этой дуге меньше, чем пропускная способность: Обратные дуги (дуги противоположны по отношению к ориентации прямых дуг) имеются, если на дугах имеется поток.Рис. Рис.3. Увеличения потока в сети Увеличение потока в сети Увеличение потока в сетиПотребитель b1 получает от поставщика a1 38 единиц товара Потребитель b1 получает от поставщика a2 4 единиц товара Потребитель b2 получает от поставщика a2 35 единиц товара Потребитель b4 получает от поставщика a2 6 единиц товара Потребитель b3 получает от поставщика a3 63 единиц товараПо окончанию данной работы я могу сказать, что данная работа была для меня как интересной, так и полезной. Подводя итоги данной работы, я убедилась, что задача была решена, верно, так как решение совпадает.
План
Оглавление
1. Постановка задачи
2. Формулировка задачи
3. Теоретическое обоснование. Общие вопросы
4. Описание алгоритма нахождения потока минимальной стоимости
5. Решение индивидуального задания по шагам
6. Программа (Mathcad)
7. Исходные данные
8. Результат программы
9. Конечные результаты
Вывод
1. Постановка задачи
Вывод
По окончанию данной работы я могу сказать, что данная работа была для меня как интересной, так и полезной. Благодаря ней я лучше научилась разбираться в транспортных задачах, в потоках и сетях. Сама задача мне не показалась достаточно сложной, при ее выполнение особых проблем не возникало. Также в данном курсе нас познакомили с такой средой как MATHCAD. Одной из главных задач данной работы было решение и сравнение транспортной задачи вручную и в среде MATHCAD. Подводя итоги данной работы, я убедилась, что задача была решена, верно, так как решение совпадает. Но стоит сказать, что решение данной задачи вручную мне понравилось гораздо больше, так как здесь пришлось анализировать различные факторы при нахождении минимального пути. Я надеюсь, что данная работа помогла мне лучше разобраться в данной теме.