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

Оглавление.

 

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. Проверка полученного распределения ресурсов на оптимальность

Этап 3. Если полученное распределение  ресурсов не является оптимальным, то ресурсы перераспределяются, снижая стоимость транспортировки.

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

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

 

 

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

 

 

Задача 1. Из трех холодильников Ai, i=1..3, вмещающих мороженную рыбу в  количествах ai т, необходимо последнюю доставить в пять магазинов Bj, j=1..5 в количествах bj т. Стоимости перевозки 1т рыбы из холодильника Ai в магазин Bj заданы в виде матрицы Cij, 3x5.

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

        

 

 

 

H

Решение.

Составим математическую модель задачи. Пусть x_i,j - количество т рыбы, перевозимой из холодильника (поставщика) A_i в магазин (потребитель) B_j. Тогда задача заключается в минимизации общих транспортных расходов

 

при ограничениях

 

Задача имеет  закрытый тип, т.к. запасы груза 320+280+250 = 850 т равны суммарным потребностям магазинов 150+140+110+230+220 = 850 т.

Составим опорный план по правилу минимального элемента.

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	20 0	23 0	20 0	15 0	24 0	320
A2	29 0	15 0	16 0	19 0	29 0	280
A3	6 0	11 0	10 0	9 0	8 0	250
Потребн.	150	140	110	230	220

Введем некоторые обозначения: Ai* - излишек нераспределенного груза  от

поставщика Ai, Bj* - недостача  в поставке груза потребителю Bj.

Находим незанятую клетку с минимальным тарифом: (3,1). Помещаем туда меньшее из чисел A3*=250 и B1*=150.

Находим незанятую клетку с минимальным тарифом: (3,5). Помещаем туда меньшее из чисел A3*=100 и B5*=220.

Находим незанятую клетку с минимальным тарифом: (1,4). Помещаем туда меньшее из чисел A1*=320 и B4*=230.

Находим незанятую клетку с минимальным тарифом: (2,2). Помещаем туда меньшее из чисел A2*=280 и B2*=140.

Находим незанятую клетку с минимальным тарифом: (2,3). Помещаем туда меньшее из чисел A2*=140 и B3*=110. Находим незанятую клетку с минимальным тарифом: (1,5).

Помещаем туда меньшее  из чисел A1*=90 и B5*=120.

Находим незанятую клетку с минимальным тарифом: (2,5). Помещаем туда меньшее из чисел A2*=30 и B5*=30

Пришли к  таблице:

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	20	23 0	20 0	15 230	24 90	320
A2	29 0	15 140	16 110	19 0	29 30	280
A3	6 150	11 0	10 0	9 0	8 100	250
Потребн.	150	140	110	230	220

Транспортные  расходы составят z = 12040.

Решим задачу методом  потенциалов. Т.к. m+n-1=7 и имеем 7 загруженных  клеток, план ацикличный. Пусть Ui и Vj - потенциалы i-го склада и j-го магазина соответственно.

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения U_i+V_j=C_i,_j, просматривая все занятые клетки. Получим:

Для свободных  клеток определим значения оценок (разностей между прямыми и косвенными тарифами).

Имеем две клетки с отрицательными оценками – (1,1) и (2, 4). Выбираем клетку с наименьшей оценкой (1, 1) и строим для нее цикл.

 

 

 

 

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	+         20	23	20	15 230	-           24 90	320
A2	29	15 140	16 110	19	29 30	280
A3	-             6 150	11	10	9	+            8 100	250
Потребн.	150	140	110	230	220

Перемещаем по циклу  груз величиной в 90 единиц, прибавляя  эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	20 90	23	20	15 230	24	320
A2	29	15 140	16 110	19	29 30	280
A3	6 60	11	10	9	8 190	250
Потребн.	150	140	110	230	220

Целевая функция (транспортные расходы) z = 11860. Значение целевой функции изменилось на 180 единиц по сравнению с предыдущим этапом.

Проверим полученный план на оптимальность. Подсчитаем потенциалы.

Определяем  значения оценок S_i,j=C_i,j-(U_i+V_j) для всех свободных клеток:

Имеем клетку (2, 4) с отрицательной оценкой, план не оптимален. Строим для этой клетки цикл.

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	+          20 90	23	20	-           15 230	24	320
A2	29	15 140	16 110	+          19	-           29 30	280
A3	-            6 60	11	10	9	+           8 190	250
Потребн.	150	140	110	230	220

Перемещаем  по циклу груз величиной в 30 единиц, прибавляя эту величину к грузу  в клетках со знаком «плюс» и отнимая ее от груза в клетках со знаком «минус». В результате перемещения по циклу получим новый план:

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	20 120	23	20	15 200	24	320
A2	29	15 140	16 110	19 30	29	280
A3	6 30	11	10	9	8 220	250
Потребн.	150	140	110	230	220

Целевая функция (транспортные расходы) z= 11770, значение уменьшилось на 90 единиц по сравнению с предыдущим этапом.

Проверим полученный план на оптимальность. Подсчитаем потенциалы.

Определяем  значения оценок для всех свободных  клеток:

Так как все  оценки S_i,j>=0, то полученный план является оптимальным, минимальные транспортные расходы равны 11770. Оптимальный план перевозок представлен ниже.

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	20 120	23	20	15 200	24	320
A2	29	15 140	16 110	19 30	29	280
A3	6 30	11	10	9	8 220	250
Потребн.	150	140	110	230	220

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Сетевые задачи.

 

 

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

Ориентированным графом  называется тройка (I, D, G), в которой I – непустое множество вершин, D – множество дуг и G – отображение, которое каждой дуге d принадлежащей к D ставит в соответствие упорядоченную пару вершин (i, j), где i, j  принадлежит I. 

Неориентированным графом называется тройка (I, D, G), в которой I – непустое множество вершин, D – множество ребер и G – отображение, которое каждому ребру d принадлежащей к D ставит в соответствие неупорядоченную пару вершин [i, j], где i, j принадлежит I. 

Граф (I, D, G) называется конечным, если множества I и D конечны. 

 

Геометрически граф может  быть представлен в виде множества точек (изображающих вершины) и соединяющих их линий (со стрелками), соответствующих ребрам (дугам) (рис. 3.3, 3.4). Очевидно, что с каждым ориентированным графом можно однозначно связать неориентированный, заменив дуги на ребра. Если любые две вершины графа соединяются не более чем одной дугой (ребром), то граф называется простым и может быть задан с помощью пары (I, D). В этом случае каждая дуга (ребро) d полностью определяется парой соединяемых вершин (i, j), что условно записывается в виде: d=(i,j). Упорядоченная пара вершин (i, j), которая ставится в соответствие некоторой дуге d, задает ее ориентацию: i называется началом дуги, а j – ее концом, а сама дуга считается инцидентной данным вершинам.

Путем длины π в ориентированном графе (I, D) называется упорядоченная последовательность различных дуг (d1, d2,..., dn), для которых начало каждой последующей совпадает с концом предыдущей. Конечный путь, у которого начальная вершина совпадает с конечной, называется контуром.

Для неориентированного графа аналогом понятия путь является цепь, а контура – цикл.

Если две любые вершины неориентированного графа могут быть соединены цепью, то он называется связным. Ориентированный граф называется связным, если ему отвечает связный неориентированный граф.

Связный неориентированный граф, не содержащий циклов, называется деревом.

Если Y D, а отображение GY является сужением отображения G на множество Y, то граф (I, Y, GY) называют частичным графом (реберным подграфом) графа (I, D, G).