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






Скачать 419.77 Kb.
НазваниеКурсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения
страница3/7
Дата публикации01.11.2013
Размер419.77 Kb.
ТипКурсовой проект
top-bal.ru > Спорт > Курсовой проект
1   2   3   4   5   6   7
^

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



При решении любой конкретной задачи применение методов исследования операций заключается в следующем:

  • построение математических, экономических и статистических моделей для задач принятия решений и управления в сложных ситуациях в условиях неопределенности (наличие случайных факторов);

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

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

1.     ^ Ориентация на принятие решений. Основные результаты анализа должны иметь непосредственное и полностью определенное отношение к выбору способа действий (стратегии или тактики);

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

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

4.     ^ Необходимость использования ЭВМ. Это условие отнюдь не является лишь желательным, оно скорее необходимо. Это обуславливается сложностью используемых математических моделей и большим объемом исходных данных. Вычисления могут быть громоздкими – необходимо использовать ЭВМ; а могут быть несложными, но в больших объемах (статистические модели).
 Основные этапы применения метода ИО:

1.     определение цели;

2.     составление плана разработки проекта;

3.     формулировка проблемы;

4.     построение модели;

5.     разработка вычислительного метода;

6.     разработка технического задания на программирование, само программирование и отладка программы;

7.     сбор данных;

8.     проверка модели;

9.     реализация результатов, то есть принятие решения.
Задачи маршрутизации.

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

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

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

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

2. ТРАНСПОРТНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ




2.1. Постановка задачи



Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов. Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).

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

       прикрепление потребителей ресурса к производителям;

       привязка пунктов отправления к пунктам назначения;

       взаимная привязка грузопотоков прямого и обратного направлений;

       отдельные задачи оптимальной загрузки промышленного оборудования;

       оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются m пунктов отправления груза и объемы отправления по каждому пункту a1, a2 ,...,am . Известна потребность в грузах b1, b2 ,...,bn по каждому из n пунктов назначения. Задана матрица стоимостей доставки по каждому варианту cij , . Необходимо рассчитать оптимальный план перевозок, т.е. определить, сколько груза должно быть отправлено из каждого i-го пункта отправления (от поставщика) в каждый j-ый пункт назначения (до потребителя) xij с минимальными транспортными издержками.

В общем виде исходные данные представлены в табл. 3.1. Строки транспортной таблицы соответствуют пунктам отправления (в последней клетке каждой строки указан объем запаса продукта ai ), а столбцы — пунктам назначения (послед­няя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о пе­ревозке из i-го пункта в j-й: в правом верхнем углу находится цена перевозки единицы продукта, а в левом нижнем — значе­ние объема перевозимого груза для данных пунктов.
Исходные данные Таблица 3.1


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

(3.1)

Если такого равенства нет (потребности выше запасов или наоборот), запасу называют открытой, т.е.:

(3.2)

Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнении.

Все грузы из i-х пунктов должны быть отправлены, т.е.:

, (3.3)

Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:

, (3.4)

Суммарные объемы отправления должны равняться суммарным объемам назначения (3.1). Должно выполняться условие неотрицательности переменных: , , . Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):

(3.5)

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

       потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

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

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

Транспортным задачам присущи следующие особенности:

  • распределению подлежат однородные ресурсы;

  • условия задачи описываются только уравнениями;

  • все переменные выражаются в одинаковых единицах измерения;

  • во всех уравнениях коэффициенты при неизвестных равны единице;

  • каждая неизвестная встречается только в двух уравнениях системы ограничений.

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

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

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

1   2   3   4   5   6   7

Похожие:

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconРабочая учебная программа по дисциплине Теория информации и кодирования
«Теория информации и кодирования». Теория информации исследует общие закономерности информационных процессов, позволяет оценить качество...

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconРабочая программа дисциплины Теория оптимальных процессов Направление...
Дисциплина «Теория оптимальных процессов» (годовой спецкурс) является частью математического цикла ооп. Дисциплина реализуется на...

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconМетодические рекомендации по написанию курсовой работы по дисциплине «Экономическая теория»
Невская, Н. А. Методические рекомендации по написанию по написанию курсовой работы по дисциплине «Экономическая теория» для студентов...

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

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения icon08. 00. 01 Экономическая теория
Микроэкономическая теория: теория потребительского спроса; теория фирмы; теория организации рынков; теория конкуренции и антимонопольного...

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

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

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconКурс. 01;Мпк. 01;3 методическое пособие по курсовой работе теория перевода
Методическое пособие предназначено для студентов, обучающихся по направлениям “Лингвистика” 031100. 62, руководителей курсовых работ...

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconУчебно-методический комплекс по дисциплине теория алгоритмов
Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать...

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconУчебно-методический комплекс по дисциплине теория алгоритмов
Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать...



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


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

Поиск