Решение транспортных задач - Курсовая работа

Каждый человек в определенный момент времени сталкивается с проблемой: как получить наибольший эффект, обладая ограниченными средствами. Этим вопросом занимается линейное программирование, точнее такое его направление, как решение транспортной задачи. Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича "Математические методы организации и планирования производства". Поскольку методы, изложенные Л.В.Канторовичем, были мало пригодны для ручного счета, а вычислительных машин в то время не существовало, работа Л.В.Канторовича осталась почти не замеченной. В 1975 году академик Л.В.Канторович и профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за "вклад в разработку теории и оптимального использования ресурсов в экономике".Под названием "транспортная задача" объединяется широкий круг задач с единой математической моделью.Однородный груз сосредоточен у m поставщиков в объемах . Данный груз необходимо доставить n потребителям в объемах . Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.Так как произведение определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны . Система ограничений задачи состоит из двух групп уравнений. Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей: , j=1, 2, … , n. Такая задача называется задачей с правильным балансом, а ее модель - закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель - открытой.Эта последовательность начинается и кончается вершиной, в которой каждое ребро инцидентно двум вершинам. Графом G называется пара (V (G), E(G)), где V (G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V (G) (необязательно различных), называемых ребрами. Дуга представима в виде упорядоченной пары вершин (v, w), где вершина v называется началом, а w - концом дуги. Путем (маршрутом) в орграфе называется конечная чередующаяся последовательность смежных вершин и дуг, соединяющих эти вершины. Сетью называется граф, в котором некоторые вершины выделены; эти вершины называют полюсами.Рассматривается двудольный граф, в котором пункты производства находятся в верхней доле, а пункты потребления - в нижней. Пункты производства и потребления попарно соединяются ребрами бесконечной пропускной способности и цены за единицу потока Cij. К верхней доле искусственно присоединяется исток. Пропускная способность ребер из истока в каждый пункт производства равна запасу продукта в этом пункте. Дальше решается задача нахождения максимального потока минимальной стоимости.При этом подразумевается, что продукция перемещается от поставщика к потребителю. Например, продукция от одного поставщика может перемещаться к другому поставщику, от потребителя к потребителю. Таким образом, при таком перемещении продукции поставщик и потребитель выступают сразу в двух ролях, то есть нет различий между поставщиками и потребителями. Таким образом, при заданных условиях начальная транспортная таблица будет иметь вид: Решение это транспортной задачи с измененными тарифами приводит к следующему оптимальному плану перемещения продукции: Результаты расчета представим в виде графа: Из графа видно, что поставщик B поставляет продукцию потребителю E транзитом через поставщика C. Исходные данные для задачи представим в виде графа: В рассматриваемой задаче имеются: пять пунктов отправления продукции (A, B, C, D, F), четыре пункта назначении (C, D, F, E) и три транзитных пункта (C, D, F), через которые проходит транзитом продукция в объеме (100 200) = 300 ед.Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки.

Содержание

Введение

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

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

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

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

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

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

Заключение

Список литературы

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

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

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

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

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

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

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

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

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

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

Размещено на .ru