Транспортная задача

Содержание

Введение

1. Основные понятия  транспортных задач

2. Методы определения  первоначального опорного плана

2.1 Метод вычеркивания

2.2 Метод северо-западного  угла

2.3 Метод минимальной  стоимости

24 Переход от одного  опорного решения к другому

3. Распределительный  метод

4. Венгерский метод

5. Метод решения  задачи об оптимальных перевозках  средствами Ms Excel

6. Решение транспортной  задачи

6.1 Постановка транспортной  задачи

6.2 Решение задачи

Заключение

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

Введение

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

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

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

1. Основные понятия  транспортных задач

Под названием “транспортная  задача” объединяется широкий круг задач с единой математической моделью. В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с m баз A1,A2,…Am n потребителям B1,B2,…Bn, не превышающий объем производства в каждом пункте поставки. Транспортная задача была впервые сформулирована Хитчкоком и с тех пор применяется для решения практических задач доставки и распределения однородных продуктов.

Различают два типа транспортных задач Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г., с.56:

по критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию);

по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).

Обозначим количество груза, имеющегося на каждой из m баз (запасы), соответственно a1,a2,…,am, а общее количество имеющегося в наличии груза a = = a1+a2+…+am; заказы каждого из потребителей (потребности) обозначим соответственно b1,b2,…,bn, а общее количество потребностей b = b1+b2+…+bn.

Тогда при условии  a = b мы имеем сбалансированную задачу (закрытая модель), а при условии a ? b - несбалансированную (открытая модель).

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

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

План перевозок  с указанием запасов и потребностей удобно записывать в виде следующей  таблицы, называемой таблицей перевозок  Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. - М.: Высшая школа, 1986, 175с.:

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

Для решения транспортной задачи необходимо кроме запасов  и потребностей знать также и  тарифы cij, т. е. стоимость перевозки единицы груза с базы Aj потребителю Bj. Совокупность тарифов cij также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:

Сумма всех затрат, т. е. стоимость реализации данного  плана перевозок, является линейной функцией переменных xij:

Требуется в области  допустимых решений системы уравнений (*) найти решение, минимизирующее линейную функцию (**):

Далее считаем, что  задача сбалансированная. Таким образом, математическую модель задачи можно  записать так Гончаров Е.Н., Ерзин А.И., Залюбовский В.В. Исследование операций. Примеры и задачи: Учеб. Пособие / Новосиб. Гос.ун-т. Новосибирск, 2005. с.10:

, (1)

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

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

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

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

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

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

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

(7) =, (8) , i=1,…,m, j=1,…,n (9)

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

Опорным решением транспортной задачи называется любое допустимое решение, для которого вектора-условия, соответствующие положительным  координатам, линейно независимы Павлова  Т.Н., Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002., с.47.

Ввиду того, что ранг системы векторов-условий транспортной задачи равен m+n-1, опорное решение  не может иметь отличных от нуля координат более m+n-1. Число отличных от нуля координат невырожденного опорного решения равно m+n-1,а для вырожденного опорного решения меньше m+n-1.

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

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

Циклом называется такая последовательность клеток таблицы  транспортной задачи (i1,j1), (i1,j2), (i2,j2), … , (ik,j1), в которой две и только две соседние клетки расположены  в одной клетке или столбце, причем первая и последняя клетки также  находятся в одной строке или  столбце Павлова Т.Н., Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002., с.50.

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

2.1 Метод вычеркивания

Метод вычеркивания позволяет проверить, является ли данное решение транспортной задачи опорным.

Пусть допустимое решение  транспортной задачи, которое имеет m+n-1 отличную от нуля координату, записано в таблицу. Чтобы данное решение  было опорным, векторы-условия, соответствующие  положительным координатам, должны быть линейно независимы. Для этого  занятые решением клетки таблицы  должны быть расположены так, чтобы  из них нельзя было образовать цикл.

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

 “вычеркиваемое”  “невычеркиваемое”

Существует ряд  методов построения начального опорного решения.

2.2 Метод северо-западного  угла Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г., с.69

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

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

если , то и исключается поставщик с номером i, , k=1, 2, …, n, kj, ;

если , то и исключается потребитель с номером j, , k=1, 2, …, m, ki, ;

если , то и исключается либо i-й поставщик, , k=1, 2, …, n, kj, , либо j-й потребитель, , k=1, 2, …, m, ki,

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

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

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

2.3 Метод минимальной  стоимости Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г.

Метод минимальной  стоимости прост, он позволяет построить  опорное решение, достаточно близкое  к оптимальному, так как использует матрицу стоимостей транспортной задачи С=(), i=1,2,,…,m, j=1,2,…,n. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости min {}, и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). В транспортной задаче переход от одного опорного решения к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решений. По этому циклу перераспределяются объемы перевозок. Перевозка загружается в выбранную свободную клетку и освобождается одна из занятых клеток, получается новое опорное решение.