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






Скачать 412.8 Kb.
НазваниеЗадачи выбора маршрута или сетевые задачи 3
страница1/3
Дата публикации18.12.2013
Размер412.8 Kb.
ТипДокументы
top-bal.ru > Математика > Документы
  1   2   3


Оглавление.


  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

Решение.

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


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




Задача имеет закрытый тип, т.к. запасы груза 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




Транспортные расходы составят
  1   2   3

Добавить документ в свой блог или на сайт

Похожие:

Задачи выбора маршрута или сетевые задачи 3 iconМетодическая разработка по теме «Задачи на проценты на уроках и в жизни»
Приложение. Несколько общих рекомендаций. Задачи, связанные с изменением цены. Задачи о вкладах и займах. Задачи на смеси и сплавы...

Задачи выбора маршрута или сетевые задачи 3 icon«Задачи на переливание»
Рассмотреть задачи на получение некоторого количества жидкости из большого или бесконечного по объему сосуда, водоема или источника...

Задачи выбора маршрута или сетевые задачи 3 iconТематическое планирование № Тема занятия Оборудование
Количественные, качественные, экспериментальные задачи. Задачи – оценки. Задачи – парадоксы. Задачи на смекалку

Задачи выбора маршрута или сетевые задачи 3 iconРоссийской Федерации Муниципальное образовательное учреждение- маметьевская...
Программа элективного курса применима для различных групп школьников, независимо от выбора их будущей професии. В основной школе...

Задачи выбора маршрута или сетевые задачи 3 iconСтруктура программы
Технология выбора образовательного маршрута обучающимися и основание для его изменения

Задачи выбора маршрута или сетевые задачи 3 icon«сказочные» задачи по генетике
Хоть задачи и сказочные, все в них подчиняется известным генетическим законам. Решать такие задачи интереснее, чем обычные о горохе...

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

Задачи выбора маршрута или сетевые задачи 3 iconЗадачи со спичками
Игры и задачи со спичками — хорошая гимнастика для ума. Они тренируют логическое мышление, комбинаторные способности, умение увидеть...

Задачи выбора маршрута или сетевые задачи 3 iconУроки математики, но и занятия математических кружков; предложить...
Портал Math ru: библиотека, медиатека, олимпиады, задачи, научные школы, учительская, история математики

Задачи выбора маршрута или сетевые задачи 3 iconЧисленное решение
Отличие краевой задачи от задачи Коши (задачи с начальными условиями) состоит в том, что решение дифференциального уравнения должно...



Школьные материалы


При копировании материала укажите ссылку © 2018
контакты
top-bal.ru

Поиск