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

КУРСОВАЯ РАБОТА

по дисциплине: Математические методы

на тему: «Решение транспортной задачи с ограничениями»

Выполнил студент 3 курса

Ситкин Н.В.

Проверила: Герасимова А.В.

 

 

Димитровград 2012

Содержание.

Введение. 3

 

Решение транспортных задач с ограничениями. 4

 

Пример решения задачи с использованием приложения Microsoft Excel. 8

 

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

Введение.

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

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

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

 

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

Имеется ряд пунктов производства А₁, А₂ , …, А_m с объемами производства в единицу времени (месяц, квартал), равными соответственно а₁, а₂,..., а_m, и пункты потребления В_1, В_2, ..., В_n, потребляющие за тот же промежуток времени соответственно b₁, b_2, ..., b_n продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех m пунктах-поставщиках равна сумме объемов потребления на всех n пунктах-получателях:

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

Тогда наиболее рациональным прикреплением поставщиков к потребителям будет такое, при котором суммарные затраты на транспортировку будут наименьшими:

При этом каждый потребитель получает нужное количество продукта:

,

и каждый поставщик отгружает весь произведенный им продукт:

.

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

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

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

Вслучае превышения запаса над заявками вводится фиктивный (n+1) пункт назначения с потребностью , соответствующие тарифы считаются равными нулю C_{i,n+1=0 i=1..m.} При вводится фиктивный (m+1) пункт отправления с запасом груза и соответствующие тарифы принимаются равными нулю C_{m+1, j} = 0, j=1..п.

Алгоритм построения первого опорного плана методом наи­меньшей стоимости включает следующие этапы:

а) среди тарифов находится наименьший;

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

в) из оставшихся тарифов вновь находится наилучший (наи­меньший), и процесс продолжается до тех пор, пока не будет рас­пределен весь груз.

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

Дальнейшее улучшение первого опорного плана и получе­ние оптимального плана производим методом потенциалов, кото­рый основан на теории двойственности.

План Х=(х_ij) транспортной задачи будет являться оптималь­ным, если существует система m+n чисел , называемых по­тенциалами, удовлетворяющая условиям:

для занятых клеток, где x_ij>0,

для незанятых клеток, где x_ij=0.

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

Алгоритм оценки оптимальности плана методом потенциалов следующий:

1) Строят начальное опорное решение (методом минимальной стоимости или методом северо-западного угла).

2) Проверяют план на вырожденность. Потенциалы и , могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане меньше, чем (m + п -1), то не хватит количества уравнений для определения потенциалов, по­этому вносим ноль в одну из свободных клеток таблицы так, что­бы общее число занятых клеток стало равным (m + п -1). Ноль вводят в клетку с наименьшим тарифом, например в клетку одно­временно вычеркиваемых строки и столбца таблицы при состав­лении нового плана. При этом фиктивно занятая нулем клетка не должна образовывать замкнутого прямоугольного контура с дру­гими клетками таблицы.

3) Строят систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений + = при >0. Для того чтобы найти частное решение системы, одному из потенциалов задают произвольно некоторое значение (чаще ноль). Остальные потенциалы однозначно определяются по формулам = - при >0, если известен потенциал , и = - при >0, если известен потенциал .

4) Проверяют, выполняется ли условие оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам = + - и те оценки, которые больше нуля, записывают в левые нижние углы клеток. Если для всех свободных клеток 0, то вычисляют значение целевой функции, и решение задачи заканчивается, так как полученное решение является оптимальным. Если же имеется хотя бы одна клетка с положительной оценкой, то опорное решение не является оптимальным.

5) Переходят к новому опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка max{ }= . Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют перераспределение груза по циклу на величину = . Клетка со знаком «-», в которой достигается , остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным m+n-1. Далее возвращаемся к пункту 3 алгоритма.