Моделирование транспортных процессов

ЗАДАЧИ, СВОДИМЫЕ К ТРАНСПОРТНОЙ. Курсовой

ЗАДАЧИ, СВОДИМЫЕ К ТРАНСПОРТНОЙ

СОДЕРЖАНИЕ

ВВЕДЕНИЕ................................................................................................................3

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

1.1 Общая характеристика транспортной задачи..........................................4

1.2 Постановка задачи. Методы решения......................................................6

2. МОДЕЛИ ЗАДАЧ, СВОДИМЫХ К ТРАНСПОРТНОЙ....................................9

2.1 Транспортная задача как разновидность методов и моделей в управлении экономическими системами.......................................................9

2.2 Задача о размещении производства........................................................10

2.3 Оптимальное распределение оборудования..........................................12

2.4 Формирование оптимального штата фирмы..........................................14

2.5 Транспортная задача в сетевой постановке...........................................15

2.6 Транспортная задача с ограничениями пропускной способности......15

2.7 Многопродуктовая транспортная задача...............................................16

ЗАКЛЮЧЕНИЕ........................................................................................................18

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ................................................19

ВВЕДЕНИЕ

Под моделированием понимается процесс построения, изучения и применения моделей. Оно тесно связано с такими категориями, как абстракция, аналогия, гипотеза и др. Главная особенность моделирования в том, что это метод опосредованного познания с помощью объектов-заместителей. Модель выступает как своеобразный инструмент познания, который исследователь ставит между собой и объектом и с помощью которого изучает интересующий его объект.

Темой курсовой работы являются '"Задачи, сводимые к транспортной'".

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

Необходимость использования метода моделирования определяется тем, что многие объекты (или проблемы, относящиеся к этим объектам) непосредственно исследовать или вовсе невозможно, или же это исследование требует много времени и средств.

Целью курсовой работы являются закрепление, систематизация и углубление полученных знаний; установка моделей задач, сводимых к транспортным; приобретение навыков системного проектирования прогрессивных технологий; умение пользоваться нормативно-справочной литературой.

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

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

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

1.1 Общая характеристика транспортной задачи

Необходимость использования метода моделирования определяется тем, что многие объекты (или проблемы, относящиеся к этим объектам) непосредственно исследовать или вовсе невозможно, или же это исследование требует много времени и средств.

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

Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера.

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

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

Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов.

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

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

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

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

Этапы построения модели транспортной задачи:

I. Определение переменных.

II. Проверка сбалансированности задачи.

III. Построение сбалансированной транспортной матрицы.

IV. Задание целевой функции.

V. Задание ограничений.

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

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

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

1.2 Постановка задачи. Методы решения.

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

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

Метод имитационного моделирования – основан на методе Монте-Карло (использование случайных чисел) и требует огромного количества вычислений, так как рассматривается очень много вариантов решений.

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

Классическую транспортную задачу можно решить симплекс-методом, в силу ряда особенностей можно решить проще (для задач малой размерности).

Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из Ai в Bj груза Xij>0, а в маленькие клетки — соответствующие тарифы Cij.

Итерационное улучшение плана перевозок

Нахождение опорного плана

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

Метод северо-западного угла (диагональный или улучшенный)

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

Метод наименьшего элемента

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

Алгоритм:

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

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

Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Итерации

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

- метод падающего камня

- метод потенциалов.

Решение с помощью теории графов

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

К верхней доле искусственно присоединяется исток. Пропускная способность рёбер из истока в каждый пункт производства равна запасу продукта в этом пункте. Цена за единицу потока у этих рёбер равна 0.

Аналогично к нижней доле присоединяется сток. Пропускная способность рёбер из каждого пункта потребления в сток равна потребности в продукте в этом пункте. Цена за единицу потока у этих рёбер тоже равна 0.

Дальше решается задача нахождения максимального потока минимальной стоимости (mincost maxflow). Её решение аналогично нахождению максимального потока в алгоритме Форда — Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширину, а алгоритм Беллмана — Форда. При возврате потока стоимость считается отрицательной.

Алгоритм «mincost maxflow» можно запускать и сразу — без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Выполнение алгоритма «mincost maxflow» происходит не более чем за O(v2e2) операций (e - количество рёбер, v - количество вершин.) При случайно подобранных данных требуется гораздо меньше - порядка O(ve) операций.

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

2. МОДЕЛИ ЗАДАЧ, СВОДИМЫХ К ТРАНСПОРТНОЙ

2.1 Транспортная задача как разновидность методов и моделей в управлении экономическими системами

Транспортные задачи – частный случай задач математического (линейного) программирования.

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

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

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

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

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

Существует несколько разновидностей экономических задач, сводящихся к транспортной модели:

оптимальное распределение оборудования;

формирование оптимального штата фирмы;

задача календарного планирования производства;

оптимальное исследование рынка;

оптимальное использование рабочих агентов;

задача размещения производства;

задача о назначениях.

2.2 Задача о размещении производства

Имеется 4 населённых пункта в каждом из которых может быть построено производственные предприятия. Все они предназначены для выпуска однородной продукции. Известны величины а1,а2, а3, а4 производственной мощности каждого из этих предприятий по выпуску пиломатериалов, а также себестоимость производства одной единицы продукции, которая будет производиться на каждом из этих предприятий:

С1 – себестоимость 1 м3 п/м, вырабатываемый на 1-м предприятии;

С2 - -1- на 2-м предприятии

С3 - -1- на 3-м предприятии

С4 - -1- на 4-м предприятии.

Выпускаемая продукция будет использоваться 5-ю потребителями, для каждого из которых задан объем его заявок:

b1 – объем заявок 1-го потребителя

b2 - -1- 2-го потребителя

b3 - -1- 3-го потребителя

b4 - -1- 4-го потребителя

b5 - -1- 5-го потребителя.

Известны транспортные затраты tij на перевозку единицы продукта от каждого поставщика каждому потребителю:

t11 t12 …..t15

t21 t22 …..t25

t31 t32 …..t35

t41 t42 …. t45

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

При этом должны выполняться следующие условия:

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

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

3. Заявки каждого из потребителей должны быть полностью выполнены.

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

Себестоимость всей производимой продукции будет равна

Стоимость перевозки всей продукции, как и в обычной транспортной задаче можно найти из формулы

(1)

В соответствии с этим целевая функция, минимизирующая суммарные затраты на производство и транспортировку продукции будет иметь вид:

+ →min (2)

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

Для этого в целевую функцию (2) подставим выражения для у1 у2 у3 у4 из ограничений. Тогда выражение (2) приобретает вид

' + →min '(3)

Или, в компактной форме:

+ →min '(4)

Это выражение является функцией элементов решения xij только одной второй группы, и не содержит элементы решения , , и .

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

' '(5)

Целевая функция (5) и ограничения cоответствуют транспортной задаче.

Принципиальное отличие целевой функции (5) от целевой функции обычной транспортной задачи в том, что ее коэффициенты учитывают не только транспортные но и производственные затраты.

2.3 Оптимальное распределение оборудования

Оборудование m-различных видов нужно распределить между n-рабочими участками. Производительность одной единицы оборудования i-го вида на j-м рабочем участке равна pij; ; . Потребность j -го участка в оборудовании составляет bj, . Запас оборудования i -го вида равен аi, . Найти распределение оборудования на рабочие участки, при котором суммарная производительность максимальная.

Решение

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

Обозначим через хij число единиц оборудования i -го вида, выделенное на j -и рабочий участок, ; .

Математическая модель задачи имеет следующий вид:

Построенная модель является сбалансированной.

В данной задаче требуется максимизировать целевую функцию Р, представляющую суммарную производительность. Для перехода к стандартной транспортной модели надо заменить функцию Р на противоположную функцию Р = -Р, которую нужно будет минимизировать.

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

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

В данной задаче требуется максимизировать целевую функцию Р, представляющую суммарную производительность.

Для перехода к стандартной транспортной модели надо заменить функцию Р на противоположную функцию Р = -Р, которую нужно будет минимизировать.

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

2.4 Формирование оптимального штата фирмы

'Фирма набирает штат сотрудников.

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

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

'Предположим, что общее число кандидатов соответствует числу вакантных должностей. Тогда данная задача соответствует транспортной модели. В роли поставщиков выступают группы кандидатов, а в роли потребителей — группы должностей. Предложением является число кандидатов в каждой группе, спросом – число вакансий в каждой группе должностей. В качестве тарифов на перевозки рассматриваются затраты на переобучение.

Математическая модель записывается в виде

Методы решения этой задачи такие же, как и транспортной задачи.

2.5 Транспортная задача в сетевой постановке

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

Задача решается слегка измененным методом потенциалов, практически тем же, что и классическая постановка.

2.6 Транспортная задача с ограничениями пропускной способности

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

Задача решается слегка усложненным методом потенциалов.

Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l к потребителю с номером m.

'Возможны ограничения двух типов: 1.'

xlm > а; 2.'

xlm < b, 3.'

xlm = k,

где а и b- постоянные величины.

1. Если xlm > a, то необходимо прежде, чем решать задачу, сократить (уменьшить) запасы l-го поставщика и запросы m-го потребителя на величину а (зарезервировать перевозку xlm = а). После решения задачи в оптимальном решении следует увеличить объем перевозки xlm на величину а.

2. Если xlm>1). После получения оптимального решения величины грузов, перевозимых к (n + 1)-му потребителю, прибавляются к величинам перевозок l-го потребителя. Так как cl(n+1)) = М - самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l, n+ 1) останется пустой, xl'n+1) = 0 и объем перевозки хlm не превзойдет b.

3. Если xlm = k, то необходимо уменьшить запасы и потребности для номеров l и m на величину k. Стоимость перевозки clm назначают М >> 1.

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

2.7 Многопродуктовая транспортная задача

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

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

Задача решается симплекс-методом (используется разложение Данцига-Вулфа, в качестве подзадач используются однопродуктовые транспортные задачи).

ЗАКЛЮЧЕНИЕ

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

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

Транспортная система – это совокупность реальных объектов и связей между ними, которые используются на определенной территории для выполнения перевозок.

Ряд экономических задач легко сводимы к транспортной задаче.

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

Оптимальное решение экономических задач может быть найдено с помощью транспортных моделей.

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Акулич И. Л. Математическое программирование в примерах и задачах М.: Высшая школа, 1993. — 319 с.

2. Аксенова Р.Н. Экономико-математические методы. Математические методы и модели в экономике. Учебный материал. — Владивосток: ДВГАЭУ, 2001. — 91с.

3. Алесинская Т.В. Учебное пособие по решению задач по курсу экономико-математические методы и модели. ' Таганрог: Изд-во ТРТУ, 2002. — 153 с.

4. Березкин О.И., Кулагина А.Г. Математическое программирование. Текст лекций для студентов экономических специальностей. Чебоксары. Изд.-во Чуваш. ун.-та, 2000. ' 164 c.

5. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. – М.: Наука, 1965.

6. Гусева Е.Н. Экономико-математическое моделирование. Учеб. пособие / Е. Н. Гусева .— 2-е изд., стер. — М.: МПСИ: ФЛИНТА, 2011. - 216 с.

7. Горюшкин А.А., Хуторецкий А.Б. Математические модели и методы исследования операций: курс лекций: Учеб. пос. Новосиб. национ. иссл. гос. ун-т / Новосибирск, ' 2013.

8. Гринберг А.С., Плющ О.Б., Шешолко В.К. Экономико-математические методы и модели: Курс лекций. ' Мн.: Академия управления при Президенте Республики Беларусь, 2003. – 228 с.

9. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. — Минск: Высшая школа, 1978. — 110 с.

10. Пантелеев А. В., Летова Т. А. Методы оптимизации в примерах и задачах. — М.: Высш. шк., 2002.

11. Хуторецкий А. Б. Модели исследования операций. ' Новосибирск, 2006.


Способ заказа и контакты