Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Техническое задание'
Поставка осуществляется с учетом Национальной образовательной инициативы «Наша новая школа», утвержденной Президентом России, Целевой программы Ханты-...полностью>>
'Публичный отчет'
Рынок литья для автомобилестроения: Общая емкость рынка в 2008 г. ~ 2100 тыс. тн. Доля ОАО «КАМАЗ-Металлургия» ~ 7,0 %. В 3 кв. произошло резкое сокр...полностью>>
'Программа'
диагностика заболеваний, прежде всего ранних и типичных проявлений болезни, а также малосимптомных и атипичных их вариантов течения заболевания на осн...полностью>>
'Документ'
ПРЕМИУМ 550 Массаж по «ЖАКЕ» с косметикой ПРЕМИУМ 350 Лечебный массаж по жаке 3 Пластический массаж лица и шеи 388 Маска парафиновая 3 Глубокое шелуше...полностью>>

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

Главная > Курсовой проект
Сохрани ссылку в одной из сетей:

Федеральное агентство по образованию

Уральский государственный технический университет – УПИ

имени первого Президента России Б.Н. Ельцина

Факультет дистанционного образования

Курсовой проект

по дисциплине: Теория информационных процессов и систем

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

Семестр № 7

Преподаватель Александров О.Е.

Студент гр. № ИТЗ–46011д Григорьева Н.А.

Номер зачётной книжки 18604304

Екатеринбург

2009


Курсовой проект по Теории информационных процессов и систем

№ записи в книге регистрации____________ дата регистрации _______________2009 г.

Преподаватель Александров О.Е.

Студент Григорьева Н.А. группа № ИТЗ-46011д

Деканат ФДО____________

Содержание:

Введение 4

1. Основные понятия исследования операций 5

2. Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения. 10

Метод потенциалов Т.З. 18

Построение начальных опорных планов 20

Распределительная задача 25

3. Программная реализация решения в пакете MathCAD 28

Задача 1 28

Задача 2 33

Задача 3 35

Мы видим, что маргинальная затрата составила -0,07. 38

Заключение 40

Литература 41

Введение

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

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

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

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

Необходимо решить следующие задачи:

1. Найти кратчайшие пути в транспортной сети.

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

3. Определить поток ресурсов минимальной стоимости.

1. Основные понятия исследования операций

Под «операцией» понимается любое мероприятие (или система действий), объединенное единым замыслом и направленное к достижению определенной цели.

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

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

Под эффективностью операции разумеется степень ее приспособленности к выполнению стоящей перед ней задачи. Чем лучше организована операция, тем она эффективнее. Любое исследование эффективности всегда предпринимается с некоторой целью.

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

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

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

Часто «условия» характеризуются не одной величиной, а двумя или более. В ряде случаев варианты условий различаются не количественно, а качественно (например, «наличие помех» и «отсутствие помех»).

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

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

Любая задача исследования операций, в сущности, сводится к задаче: как рационально использовать имеющиеся ресурсы. В каждой из них в явном иди скрытом виде имеется некоторое «дисциплинирующее условие» (или ряд таких условий), налагающее ограничения на круг решений, из которых может быть выбрано рациональное. Формулировка этого условия обычно и делает задачу определенной. Если такого условия нет, задача исследования операций становится «не поставленной» и теряет смысл.

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

Более или менее сложные задачи исследования операций всегда решаются не по одному единственному критерию, а на основе комплексного учета целой совокупности критериев. Любое принимаемое решение всегда представляет собой компромисс, в котором предпочтение отдается тому варианту, который, не являясь, может быть, оптимальным ни по одному критерию, оказывается приемлемым по ряду критериев. О компромиссном характере решения мы уже говорили в связи с оценкой эффективности в диапазоне условий; здесь этот компромисс еще углубляется, так как приходится удовлетворять требованиям не одного, а ряда критериев. На практике задача выбора решения почти никогда не сводится к простой математической задаче отыскания максимума (или минимума) одного числа, а есть задача несравненно более сложная. Исследование операций может только подготовить количественные данные, на основе которых может быть принято разумное компромиссное решение. Однако весь процесс принятия решения (по крайней мере, в настоящее время) не может быть полностью формализован: на некотором этапе всегда должно быть принято «волевое» или «командирское» решение, основанное не только на количественных данных, но и на опыте, здравом смысле и ряде дополнительных соображений, которые не могли быть учтены в расчетной схеме. С этой точки зрения исследование операций может рассматриваться не как наука о выборе решений, а как наука о количественном обосновании решений.

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

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

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

Наиболее известными и эффективными методами ИО являются методы линейного программирования, когда целевая функция и все ограничения являются линейными функциями. Для решения математических моделей других типов предназначены методы целочисленного программирования (если все переменные должны принимать только целочисленные значения), динамического программирования (где исходную задачу можно разбить на меньшие подзадачи) и нелинейного программирования (когда целевая функция и/или ограничения являются нелинейными функциями). Перечисленные методы составляют только часть из большого количества самых разнообразных доступных методов исследования операций.

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

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

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

Исследование операций как инструмент задачи принятия решения можно рассматривать и как науку, и как искусство. Наука здесь представлена всей мощью математических методов, а искусство — тем обстоятельством, что успех на всех этапах, предшествующих получению оптимального решения математической модели, в большей степени зависит от творчества и опыта всей команды, занимающейся решением задачи ИО. Уиллимейн (Willemain, [8]) утверждает, что "эффективная практика [ИО] требует нечто больше, чем только знания и компетентность. Она также требует, среди прочего, "технической" мудрости (т.е. понимания того, когда и как применять тот или иной метод или алгоритм) и определенного уровня коммуникабельности и организационных способностей".

Из-за "неуловимого" человеческого фактора трудно дать точные предписания для реализации теории исследования операций на практике. Можно попытаться показать только общую направленность такой реализации.

На практике реализация методов ИО должна включать следующие этапы.

1. Формализация исходной проблемы.

2. Построение математической модели.

3. Решение модели.

4. Проверка адекватности модели.

5. Реализация решения.

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

Формализация проблемы требует исследования той предметной области, где возникла рассматриваемая проблема. Это начальный этап работы любой команды аналитиков ИО. В результате такого исследования должны быть получены следующие три принципиальных элемента решаемой задачи:

1) описание возможных альтернативных решений,

2) определение целевой функции,

3) построение системы ограничений, налагаемых на возможные решения.

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

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

Проверка адекватности модели предполагает проверку ее правильности, т.е. определения того, соответствует ли поведение модели в конкретных ситуациях поведению исходной реальной системы. Но сначала команда аналитиков ИО должна удостовериться, что модель не содержит "сюрпризов". Другими словами, надо убедиться, что решение, полученное в рамках построенной модели, имеет смысл и интуитивно приемлемо. Формальным общепринятым методом проверки адекватности модели является сравнение полученного решения (поведение модели) с известными ранее решениями или поведением реальной системы. Модель считается адекватной, если при определенных начальных условиях ее поведение совпадает с поведением исходной системы при тех же начальных условиях. Конечно, это не гарантирует, что при других начальных условиях поведение модели будет совпадать с поведением реальной системы. В некоторых случаях в силу разных причин невозможно прямое сравнение модели с реальной системой или сравнение решений, полученных в рамках этой модели, с известными решениями (например, из-за отсутствия таких данных). В такой ситуации для проверки адекватности математической модели можно использовать имитационное моделирование, т.е. сравнивать поведение математической и имитационной моделей.

Реализация решения подразумевает перевод результатов решения модели в рекомендации, представленные в форме, понятной для лиц, принимающих решения, т.е. заказчиков. Бремя этой непростой задачи ложится непосредственно на плечи команды аналитиков ИО.

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

Задачи транспортного типа составляют специальный и довольно обширный класс задач линейного программирования. Объединяющим признаком этого класса служит наличие особого типа ограничений. Специфичность структуры матрицы условий таких задач делает неэффективным применение для их решения стандартного симплекс-метода и его математического обеспечения и требует использования специальных методов. Рассмотрим основные свойства задач линейного программирования (Л.П.)

Пусть дана задача ЛП в канонической форме: минимизировать линейную форму

(1)

при условиях

(2)

(2)

В векторно-матричной форме задача имеет вид

(1’)

(2’)

(3’)

Векторы Aj (j =1, 2,...,n) в матрице A называются векторами условий. Вектор x =(x1,x2,...,xn), удовлетворяющий условиям (1)-(3), называется планом задачи. Оптимальным планом задачи ЛП называется план, минимизирующий целевую функцию (1)

План x называется опорным, если векторы Aj, отвечающие его положительным компонентам, линейно-независимы. Невырожденный опорный план содержит m положительных компонент, вырожденный опорный план содержит более чем n − m нулевых компонент/

Система линейно-независимых векторов Aj, отвечающих положительным компонентам опорного плана, образует его базис. Можно считать, что базис любого опорного плана состоит из m линейнонезависимых векторов.

Сформулируем основные теоремы ЛП, отражающие свойства планов задачи.

Теорема. Если множество планов задачи (1)–(3) не пусто, то среди них имеется хотя бы один опорный план.

Теорема. Если множество планов задачи (1)–(3) не пусто и целевая функция ограничена снизу на этом множестве, то задача имеет хотя бы один оптимальный опорный план.

Методы анализа и решения задач ЛП существенно опираются на теорию двойственности. Задача, двойственная к (1)–(3), формулируется следующим образом: найти вектор y =(y1,y2,...,ym)T , максимизирующий линейную форму

(4)

при условиях

(5)

или в векторно-матричной форме

Задачи (1)–(3) и (4)–(5) называют парой двойственных (сопряженных) задач.

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

Пара условий: xj ≥ 0,  aij yi ≥ cj, j =1, 2,...,n называются сопряженными парами условий для задач (1)–(3) и (4)–(5).

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

Перечисленные свойства задач ЛП широко используются для анализа задач транспортного типа.

Рассмотрение начнем с простейших моделей. К их числу относится модель следующего типа:

при условиях

В этой задаче система ограничений, кроме ограничений на знак переменных, состоит из одного уравнения. Поэтому опорный план содержит одну положительную компоненту, а оптимальный опорный план легко находится. Действительно, пусть min{cj} = cj0 , тогда компоненты оптимального опорного плана

К этой задаче приводится следующая:

при условиях

Замена переменной yj = ajxj приводит нас к предыдущей модели. Таким образом, решение одноиндексных транспортных задач (Т.З.) тривиально.

Простейшие двухлинейные Т.З. также не вызывают серьезных трудностей при анализе: найти набор X = ||xij|| , минимизирующий линейную форму

при условиях

Эта задача распадается на m одноиндексных задач, решение которых тривиально. Оптимальный план исходной задачи формируется из оптимальных решений частных задач. Другой простейшей двухидексной задачей транспортного типа является задача: найти набор X = ||xij||, минимизирующий

при условиях

Эта задача сводится к уже рассмотренной простой нумерацией множества пар индексов (i, j) одним индексом k =1, 2,...,m · n.

Более сложной из известных двухиндексных Т.З. является следующая. Пусть в пунктах A1,A2,...,Am производится (или хранится) некоторый однородный продукт, причем объем производства в пункте Ai составляет ai единиц. Указанный продукт потребляется в пунктах B1,B2,...,Bn, причем объем потребления в пункте Bi равен bi единиц. Допустим, что транспортные издержки, приходящиеся на единицу продукта при перевозке его из i-ого пункта производства в j-ый пункт потребления составляют cij денежный единиц. Требуется найти такой план перевозок (распределение продукта по потребителям), при котором потребности всех потребителей будут удовлетворены, весь продукт будет вывезен и при этом суммарные транспортные затраты будут минимальны.

Пусть xij — количество продукта, транспортируемое из пункта Ai в пункт Bj , математическая модель такой задачи имеет вид

(6)

при условиях

(7)

(8)

(9)

Равенства (7) гарантируют полный вывоз продукта из всех пунктов производства, равенства (8) означают полное удовлетворение потребителей, условия (9) естественны. Т.З. в такой постановке определяется заданием вектора объемов производства a =(a1,a2,...,am)T , вектора объема потребления b=(b1,b2,...,bn)T ) и матрицы транспортных издержек



Скачать документ

Похожие документы:

  1. Курсовой проект по дисциплине "Теория информационных систем" тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения

    Курсовой проект
    Формирование исследования операций как самостоятельной ветви прикладной математики относится к периоду 40-х и 50-х годов. Последу­ющие полтора десятилетия были отмечены широким применением полу­ченных фундаментальных теоретических
  2. Курсовой проект по курсу «Теория информационных процессов и систем» (2)

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

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

    Методические указания
    Цель курсового проекта по курсу «Теория информационных процессов и систем»  закрепление теоретических знаний, полученных в лекционном курсе и приобретение навыков самостоятельного применения теоретических знаний к решению практических
  5. Рабочая программа дисциплины Теория информационных процессов и систем  Рекомендована методическим Советом Урфу для специальностей и направлений подготовки: Специальности (направления)

    Рабочая программа
    Программа составлена в соответствии с Государственным образовательным стандартом высшего и среднего профессионального образования по направлению подготовки 230200 –ИНФОРМАЦИОННЫЕ СИСТЕМЫ, степень (квалификация) БАКАЛАВР ИНФОРМАЦИОННЫХ

Другие похожие документы..