Задачи выбора маршрута или сетевые задачи

Оглавление.

 

1. Введение           2
2. Задачи выбора маршрута или сетевые задачи     3
3. Транспортные задачи         3
4. Алгоритм решения транспортной задачи      7
5. Пример решения транспортной задачи      7
6. Сетевые задачи                 13
7. Алгоритм решения сетевой задачи              19
1. Нахождение минимального остова в графе с примером решения задачи                 19
2. Нахождения кратчайшего пути в графе с примером решения задачи                 21       
8. Примеры решения задач в пакетах Microsoft Office Excel 2003 и Mathcad 2001i Professional               24       
9. Заключение                 31
10. Список литературы                32    

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

 

 

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

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

Сегодня несомненна необходимость  применения математических знаний и  математического мышления врачу, лингвисту, историку, и людям других специальностей. Но особенно знание математики необходимы людям точных профессий – финансистам, экономистам. Таким образом, математика и математическое образование нужны для подготовки к будущей профессии.

Один из классов математических моделей являются задачи линейного программирования. Одной из задач линейного программирования является транспортная задача – задача составления оптимального плана перевозок, позволяющего минимизировать суммарный километраж.

Цель данной курсовой работы по курсу «Теория информационных процессов и систем» является разбор теоретической части, полученных на лекционном курсе и самостоятельное применение на практике теоретических знаний к решению задач по исследованию систем.

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

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

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

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

 

 

  Задачи выбора маршрута или сетевые задачи.

 

Типичной задачей выбора маршрута является нахождение некоторого маршрута проезда из одного города в другой, при наличии множества путей через различные промежуточные пункты. Задача состоит в определении наиболее экономичного маршрута по критерию времени, расстояния или стоимости проезда.

При рассмотрении ряда маршрутов вводятся следующие ограничения:

-  запрещается возвращаться в уже пройденный пункт,

- в пунктах сети возможны задержки (например, из-за ограниченной пропускной способности). Задержки носят случайный характер.

Критерии оптимизации: минимизация общего времени прохождения маршрута или минимизация общих затрат.

Одним из примеров таких  задач может служить задача коммивояжера.

Задача коммивояжёра (бродячий торговец) является одной  из самых известных задач комбинаторной  оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.

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

Общая постановка задачи, впрочем, как и большинство её частных случаев, относится к  классу NP-сложных задач.

Так или иначе, все  сводится к решению транспортной задачи.

 

 

Транспортные задачи.

 

 

Транспортная задача, как и задача линейного программирования, была впервые поставлена советским  экономистом А.Н.Толстым в 1930 году. Разработка общих методов решения задачи линейного программирования и их математическое исследование связано с именем советского ученого Л.В.Канторовича. В 1939 году методам решения задачи линейного программирования посвящено также большое число работ зарубежных ученых. Основной метод решения задачи линейного программирования –симплекс метод – был опубликован в 1949 году Дандигом. Симплекс метод дает решение любой задачи линейного программирования, но если переменных очень много, то решение весьма затруднительно и для более сложных задач симплекс метод стали модифицировать.

Транспортная задача делится на два вида: транспортная задача по критерию стоимости –  определение плана перевозок, при  котором стоимость груза была бы минимальна; транспортная задача по критерию времени – более важным является выигрыш по времени.

Транспортная задача по критерию стоимости является частным  случаем задачи линейного программирования и может быть решена симплексным  методом. Однако в силу особенностей задачи, она решается намного проще.

Данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты потребления (║xi,j║mxn), который минимизирует целевую функцию

на множестве допустимых планов

 

при соблюдении условия  баланса

Транспортная задача является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения.

Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (m+n) х mn. Матрицы систем уравнений в ограничениях (3.2) и (3.3) имеют ранги, равные соответственно m и n. Однако, если, с одной стороны, просуммировать уравнения (3.2) по m, а с другой – уравнения (3.3) по n, то в силу (3.5) получим одно и то же значение. Из этого следует, что одно из уравнений в системе (3.2)-(3.3) является линейной комбинацией других. Таким образом, ранг матрицы транспортной задачи равен m+n-1, и ее невырожденный базисный план должен содержать m+n-1 ненулевых компонент.

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

Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта аi), а столбцы – пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем – значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (хi,j = 0), называют свободными, а ненулевые – занятыми (xi,j >0). 

По аналогии с другими  задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного  плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного, удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются аi(q), а текущих неудовлетворенных потребностей – bj(q). Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем аi(0) = аi, bj(0) = bj. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: xi,j = min{аi(q), bj(q)}. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:

 

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: аi(q+1)=0 или bj(q+1)=0 . Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i+1, т. е. переместиться к следующей клетке вниз по столбцу. Если же bj(q+1)=0, то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.

Основываясь на условии баланса запасов и потребностей (3.5), нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же условия число шагов алгоритма не может быть больше, чем m+n-1, поэтому всегда останутся свободными (нулевыми) mn-(m+n-1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (аi(q) = bj(q)). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана. 

Рассмотрим применение метода северо-западного угла на конкретном примере. Транспортная таблица 3.1 содержит условия некоторой задачи, а в табл. 3.2 показан процесс поиска допустимого плана, включая последовательное изменение объема нераспределенных запасов и неудовлетворенных потребностей. Стрелки отражают траекторию перехода по клеткам транспортной таблицы, а цифры, находящиеся за ее пределами, – текущие нераспределенные остатки после назначения объема для очередной клетки.

Особенностью допустимого  плана, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далекое от оптимального. Это происходит потому, что при его построении никак не учитываются значения сi,j. В связи с этим на практике для получения исходного плана используется другой способ – метод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наименьшими ценами.

 

Алгоритм решения транспортной задачи.

 

 

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

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

2. Запас продуктов  в каждом пункте производства должен быть известен.

3. Потребности в продуктах  в каждом пункте потребления  должны быть известны.

4. Общее предложение  должно быть равно общему спросу.

 

Алгоритм решения транспортной задачи состоит из четырех этапов:

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

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