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

      СОДЕРЖАНИЕ 

Введение                        5 

1 Объект исследования       6

2 Математическое обеспечение                                                                                   8

2.1 Математическая  модель                                                                                       8

2.2 Выбор  метод составления опорного плана                                                         9

2.3 Нахождение  оптимального решения                                                                  11                        

3 Практическая  реализация                             13

4 Руководство пользователя                           17        

Заключение                                                                       19

Библиографический список                                                                                         20

Приложение  А. Блок-схема         21

Приложение  Б. Листинг программы                                                                           22 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ

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

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

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

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

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

     1 ОБЪЕКТ ИССЛЕДОВАНИЯ И ПОСТАНОВКА ЗАДАЧИ

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

• минимизирующий суммарную стоимость транспортировки,
• не превышающий объем производства в каждом пункте поставки,
• полностью покрывающий потребности в каждом пункте потребления,

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

      Транспортная  задача была впервые сформулирована Хитчкоком и с тех пор применяется  для решения практических задач  доставки и распределения однородных продуктов.

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

      В качестве задания транспортная задача имеет следующий вид:

      Таблица 1

      В таблице 1 приведены расходы на транспортировку  партий товаров с трех фабрик (А, Б и В) к четырем складам (Г, Д, Е и Ж). в ней также приведены  количество товара на каждой из фабрик и вместимость складов. Требуется определить маршруты, по которым следует направлять товары, чтобы минимизировать общие расходы. 
 
 
 
 
 
 
 
 
 
 
 

      2 МАТЕМАТИЧЕСКОЕ  ОБЕСПЕЧЕНИЕ 

      2.1 Математическая модель

      Имеется m пунктов поставки (поставщиков) и n пунктов потребления некого однородного продукта. Для каждого поставщика i = 1,...,m задан объем производства A_i, а для каждого потребителя j = 1,...,n задан объем потребления B_j и известна стоимость доставки единицы продукта C_i,j из пункта производства i в пункт потребления j. Управляемые параметры X_i,j характеризуют объем перевозки между каждым поставщиком i = 1,...,m и потребителем j = 1,...,n. В случае сбалансированного производства и потребления:

          A₁ + ... + A_m = B₁ + ... + B_n                                                                           (1)

      оптимальный план транспортировки соответствует  минимизации линейной целевой функции:

                                                            (2)

      при m линейных ограничениях по поставке:

          X_i,1 + ... + X_i,j + ... + X_i,n = A_i, i = 1,...,m                               (3)

      и n линейных ограничениях пo потреблению:

          X_1,j + ... + X_i,j + ... + X_m,j = B_j, j = 1,...,n,                                (4)

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

          , i = 1,...,m   и j = 1,...,n.                                            (5)

      2.2 Выбор метод составления опорного  плана

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

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

      Метод минимального элемента. Алгоритм метода минимального элемента состоит в следующем.     Просматривается вся матрица тарифов перевозок,  и  из  нее  выбирается позиция с наименьшим значением тарифа  C,  затем  просматриваются  значения наличия запасов на складе  A и потребности у потребителя B, затем в данную клетку записывается величина D=MIN(A,B). Из запасов соответствующего склада и потребностей магазина  вычитается величина D.  Если  запас   товара  на складе исчерпан, то эта строка  исключается из  дальнейшего рассмотрения. Если потребность  магазина  в  товаре  удовлетворена  полностью,  то   этот столбец исключается из дальнейшего рассмотрения. Может быть случай,  когда одновременно  исключаются и строка  и столбец,  этот  случай  называется вырожденным. В дальнейшем весь процесс повторяется  до тех пор,  пока  не будет исчерпан весь запас товаров на  складах и не  будет удовлетворена потребность всех магазинов

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

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

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

      Метод северо-западного  угла. Просматривается матрица тарифов перевозок C, начиная с левого верхнего угла (клетки). В эту клетку записывается величина D=MIN(A,B). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс опять повторяется для левой верхней клетки оставшейся матрицы и так до тех пор пока весь запас товаров не будет исчерпан.

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

      2.3 Нахождение оптимального решения задачи

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