Решение транспортных задач

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

" МОСКОВСКИЙ ПЕДАГОГИЧЕСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"

КУРСОВАЯ РАБОТА По дисциплине: МАТЕМАТИЧЕСКИЕ МОДЕЛИ В ЭКОНОМИКЕ На тему: «РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ»

Москва

Содержание Введение

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

1.1 Формулировка транспортной задачи

1.2 Математическая модель транспортной задачи

2. Графы: определение, виды и их применение

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

3. Решение задач Заключение Список литературы Введение Каждый человек в определенный момент времени сталкивается с проблемой: как получить наибольший эффект, обладая ограниченными средствами. Актуальность этой работы состоит в том, что на сегодняшний день множество предприятий занимаются перевозкой продукции для ее дальнейшей реализации. Поэтому большое значение имеет процесс оптимизации грузоперевозок с целью минимизации затрат на доставку грузов. Этим вопросом занимается линейное программирование, точнее такое его направление, как решение транспортной задачи. Временем рождения линейного программирования принято считать 1939 г., когда была напечатана брошюра Леонида Витальевича Канторовича «Математические методы организации и планирования производства». Поскольку методы, изложенные Л. В. Канторовичем, были мало пригодны для ручного счета, а вычислительных машин в то время не существовало, работа Л. В. Канторовича осталась почти не замеченной.

Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов программирования. В 1975 году академик Л. В. Канторович и профессор Т. Купманс получили Нобелевскую премию по экономическим наукам за «вклад в разработку теории и оптимального использования ресурсов в экономике» .

В автобиографии Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда, поэтому простой перебор вершин не годился. Леонид Витальевич писал: «оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения». И уже летом 1939 года была сдана в набор книга Л. В. Канторовича «Математические методы организации и планирования производства», в которой закладывались основания того, что сейчас называется математической экономикой. Однако линейным программированием занимался и американский математик А. Данциг, который разработал весьма эффективный конкретный метод численного решения задач линейного программирования, получивший название симплекс метода.

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

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

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

1.1 Формулировка транспортной задачи

Однородный груз сосредоточен у m поставщиков в объемах. Данный груз необходимо доставить n потребителям в объемах. Известны, i=1,2,…, m, j=1,2,…, nстоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.

Исходные данные транспортной задачи обычно записываются в таблице (таб1.1).

Таблица 1.1

Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков А=(, вектора запросов потребителей

В=() и матрицы стоимостей .

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

1.2 Математическая модель транспортной задачи

Переменными (неизвестными) транспортной задачи являются i=1,2,…, m, j=1,2,…, n — объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок

.

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

.

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

i=1,2,…, m.

Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей:

j=1, 2, …, n.

Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:

(1)

i=1,2,…, m, (2)

j=1, 2, …, n, (3)

i=1,2,…, m, j=1,2,…, n (4)

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

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

Математическая формулировка транспортной задачи такова: найти переменные задачи, i=1,2,…, m, j=1,2,…, n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).

Математическая модель транспортной задачи может быть записана в векторном виде. Для этого рассмотрим матрицу, А системы уравнений-ограничений задачи (2), (3):

А =

Сверху над каждым столбцом матрицы указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы ограничений. Каждый столбец матрицы А, соответствующий переменной, является вектором-условием задачи и обозначается через. Каждый вектор имеет всего m+n координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора стоит на i-м месте, а вторая — на (m+j)-м месте, т. е.

Обозначим через вектор ограничений (правых частей уравнений (2), (3)) и представим систему ограничений задачи в векторном виде. Тогда математическая модель транспортной задачи запишется следующим образом:

(7)

=, (8)

i=1,2,…, m, j=1,2,…, n (9)

2. Графы: определение, виды и их применение

Теория графов — один из фундаментальных разделов дискретной математики. Сведения из этого раздела традиционно включались в курсы кибернетики, а затем и информатики, поскольку графы оказались очень продуктивным средством информационного (математического) моделирования структур систем и процессов, представления задач информационного характера. Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т. п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, информационных систем, химических и генетических структур, электрических цепей и других систем сетевой структуры. Обычно теорию графов относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин.

Геометрическое представление графа — это схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.

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

a) Нулевой граф с 5 вершинами

b) Неполный граф с 5 вершинами Рис 1.

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

Определение.

Графом G называется пара (V (G), E (G)), где V (G) — непустое конечное множество элементов, называемых вершинами, а E (G) — конечное семейство неупорядоченных пар элементов из V (G) (необязательно различных), называемых ребрами. Употребление слова «семейство» говорит о том, что допускаются кратные ребра. Будем называть V (G) множеством вершин, а E (G) — семейством ребер графа G. О каждом ребре вида {v, w} говорят, что оно соединяет вершины v и w. Каждая петля {v, v} соединяет вершину v саму с собой. При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными; длины отрезков и расположение точек произвольны.

Ориентированный граф (или сокращенно орграф) — граф, в котором связи изображены дугами. Дуга представима в виде упорядоченной пары вершин (v, w), где вершина v называется началом, а w — концом дуги. На рисунке 2 показан орграф с четырьмя вершинами и пятью дугами.

Рис 2.

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

a) сильно связный

b) слабо связный

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

Неориентированный граф G (V, E) состоит из конечного множества вершин V и множества ребер E. В отличие от ориентированного графа, здесь ребро (v, w) соответствует неупорядоченной паре вершин: если (v, w) — неориентированное ребро, то (v, w) = (w, v). Неориентированный граф без петель называется полным, если каждая его вершина смежна со всеми остальными вершинами. Многое из терминологии ориентированных графов применимо к неориентированным графам.

Неориентированный граф G=(V, X), v1 — висячая вершина, v5 — висячая вершина

Неориентированный граф G называется связным, если каждая пара вершин v_i и v_j в графе связана цепью. Любой максимальный связный подграф (то есть не содержащийся в других связных подграфах) графа G называется компонентой связности. Несвязный граф имеет, по крайней мере, две компоненты связности.

Так, например, граф на рисунке 3 распадается на три компоненты связности: (1, 6), (2, 7, 5, 4), (3).

Рис 3.

Если граф имеет простой цикл, содержащий все вершины графа (по одному разу), то такой цикл называется гамильтоновым циклом. Гамильтонова цепь (путь, цикл, контур) — простая цепь (путь, цикл, контур), проходящая через все вершины. Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется Эйлеровым циклом. Эйлерова цепь (путь, цикл, кон-тур) — цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.

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

Рис 4.

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

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

Рассматривается двудольный граф, в котором пункты производства находятся в верхней доле, а пункты потребления — в нижней. Пункты производства и потребления попарно соединяются рёбрами бесконечной пропускной способности и цены за единицу потока C_ij. К верхней доле искусственно присоединяется исток. Пропускная способность рёбер из истока в каждый пункт производства равна запасу продукта в этом пункте. Цена за единицу потока у этих рёбер равна 0. Аналогично к нижней доле присоединяется сток. Пропускная способность рёбер из каждого пункта потребления в сток равна потребности в продукте в этом пункте. Цена за единицу потока у этих рёбер тоже равна 0. Дальше решается задача нахождения максимального потока минимальной стоимости. Её решение аналогично нахождению максимального потока в алгоритме Форда — Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширину, а алгоритм Беллмана — Форда. При возврате потока стоимость считается отрицательной. Алгоритм можно запускать и сразу — без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Выполнение алгоритма происходит не более чем за O (v²e²) операций. (e — количество рёбер, v — количество вершин.) При случайно подобранных данных обычно требуется гораздо меньше — порядка O (ve) операций. При решении несбалансированной транспортной задачи применяют приём, позволяющий сделать ее сбалансированной. Для этого вводят фиктивные пункты назначения или отправления. Выполнение баланса транспортной задачи необходимо для того, чтобы иметь возможность применить алгоритм решения, построенный на использовании транспортных таблиц.

3. Решение задач

3.1 Задача с неразличимыми поставщиками и потребителями

При постановке транспортной задачи присутствуют поставщики и потребители продукции. При этом подразумевается, что продукция перемещается от поставщика к потребителю. Вместе с тем возможны и другие маршруты перемещения продукции. Например, продукция от одного поставщика может перемещаться к другому поставщику, от потребителя к потребителю. Таким образом, при таком перемещении продукции поставщик и потребитель выступают сразу в двух ролях, то есть нет различий между поставщиками и потребителями. Для моделирования такой схемы перемещения вводится понятие буфера В. Буфер — это количество всей перевозимой продукции. Так, например, если имеются три поставщика А, B, C, которые поставляют продукцию в количестве соответственно 100 ед., 300 ед., 400 ед., то величина буфера должна быть равна B = 100 ед. + 300 ед. + +400 ед. = 800 ед. Такой же буфер должен присутствовать и у потребителя. При наличии двух потребителей D и E с объёмами потребления соответственно 250 ед. и 550 ед. B = 250 ед. + 550 ед. = 800 ед. Для отражения затрат на перемещение единицы продукции между всеми участниками транспортной схемы вводятся так называемые тарифы на перемещение. В данной рассматриваемой задаче естественно положить тариф на перемещение внутри каждого узла, равным нулю. Таким образом, при заданных условиях начальная транспортная таблица будет иметь вид:

Решение это транспортной задачи с изменёнными тарифами приводит к следующему оптимальному плану перемещения продукции:

Результаты расчёта представим в виде графа:

Из графа видно, что поставщик B поставляет продукцию потребителю E транзитом через поставщика C. В данном случае поставщик C выступает в роли потребителя. 3.2. Транспортная модель с промежуточными пунктами

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

В рассматриваемой задаче имеются: пять пунктов отправления продукции (A, B, C, D, F), четыре пункта назначении (C, D, F, E) и три транзитных пункта (C, D, F), через которые проходит транзитом продукция в объёме (100 + 200) = 300 ед. Поэтому в пункте D может присутствовать (300 + 50) = 350 ед., в пункте F (300 + 100) = 400 ед. Значения тарифов перемещения продукции изображены над дугами, соединяющими пункты транспортной сети. Для моделирования невозможности перемещения между пунктами, не соединёнными дугами, тарифы перевозок для них принимаются на несколько порядков больше, чем остальные тарифы. В этом примере их можно принять равными 100. Тариф перевозки внутри самого пункта принимается равным нулю. Метод решение этой задачи ничем не отличается от ранее рассмотренных задач.

Оптимальный опорный план имеет следующий вид:

Это решение представим в виде графа:

Из графа видно, что вся продукция (300 ед.) из транзитного пункта C поступает в пункт потребления D, в котором остаётся потребляемое количество 50 ед. Остаток в объёме 250 ед. поступает в пункт F, из которого 100 ед. остаются, оставшиеся 150 ед. идут на потребление в пункт E. Таким образом, используя понятия транзитного пункта и буфера, а также варьируя значениями тарифов перевозки, можно смоделировать и решить многочисленные транспортные задачи.

3.3 Задача из школьного курса информатики

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

Для решения данной задачи построим ее математическую модель. Неизвестными в данной задаче являются объемы перевозок. Пусть

X_ij — объем перевозок, а с_ij — стоимость перевозки единицы продукции с i-й фабрики на j-й склад соответственно. Функция цели — это суммарные транспортные расходы, которые следует минимизировать, т. е.:

min. (1)

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

j [1, 3], (2)

а потребности всех центров распределения должны быть полностью удовлетворены:

i [1, 5]. (3)

Объемы перевозок не должны быть отрицательными:

x_ij i [1, 3], j [1, 5]. (4)

Здесь а_i — объем производства на i-й фабрике, b_j — спрос в j-м центре распределения.

Рабочий лист Excel с введенными исходными данными для решения транспортной задачи:

Выберем команду Сервис/Надстройки, в появившемся диалоговом окне Надстройки установим флажок Поиск решения и щелкнем на кнопке ОК.

Таким образом, мы нашли решение рассматриваемой транспортной задачи. Общая стоимость перевозок будет минимальной и равна 15 730 ден. ед.

транспортный задача симплекс граф

Заключение

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

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

1. Золотарева М. А. Использование теории графов в разработке программных систем.

2. Орлов А. И. Основы теории принятия решений,-Москва, 2002.

3. Менеджмент/Информационные технологииОсновные понятия теории графов/[электронный ресурс]

4. Семериков А. В. Решение транспортных задач,-уч.пособие УГТУ, 2013.