Министерство образования и  науки Украины

Национальный  технический университет Украины

«Киевский политехнический институт»

Учебно-научный  комплекс

«Институт прикладного системного анализа»

Кафедра математических методов системного анализа

 

Курсовая  работа

по  курсу «Теория  принятия решений»

 

Тема  №4: «Иследование транспортнои задачи по критериям стоимости и времени»  
 
 
 
 

  
 
 
 

Руководитель                                             Выполнила                 

д.т.н. проф. Зайченко Ю.П.                             Чесниший И.А.                

Допущен  к зщите                                           студент 4 курса группы КА-75

“___ ”___________2010г.                                 зачетная книжка

Защищено с оценкой                                        № 7525

_____________________                                     
 
 
 
 
 
 

Киев-2010

РЕФЕРАТ

     Курсовая  работа 29 страниц, 12 таблиц. Было использовано 6 источников.

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Содержание

 

     Введение

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

     1 Постановка задачи

     

     ИСЛЕДОВАНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ ПО КРИТЕРИЯМ СТОИМОСТИ И ВРЕМЕНИ

     Тема  14. Вариант № 1

     Условие задачи

     Имеется m пунктов отправления, в каждом из которых сосредоточено определенное количество единиц однородного продукта, предназначенного к отправке: в первом пункте отправления иметься а1 единиц этого продукта, во втором а2, в i-м – ai единиц, и , наконец в m-м пункте am единиц.

       Этот продукт следует отправить  в  n пунктов назначения, причем в первый следует отправить b1 единиц, во второй - b2 и так далее. Каждый пункт отправления соединен с каждым пунктом назначения некоторым маршрутом (число таких маршрутов равно m x n), причем известна удельная стоимость Cij перевозки одной единицы продукта из i-го пункта отправления в j-й пункт назначения. Общая стоимость перевозки по любому маршруту пропорциональна количеству перевозимого продукта. Известно также время Tij перевозки продукта, причем это время не зависит от количества перевозимого груза.

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

     

       
 

Матрица затрат на перевозку

Таб.1

 

Матрица времени  перевозок

Таб.2

      2. Аналитическое решение

     Введем  необходимые обозначения:

      -  количество перевозимого продукта из Аi в Bj;

      -  время на перевозку продукта из Аi в Bj;

      -  минимальные затраты на перевозку; 

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

            

     При ограничениях

         

         

      

          
 
 

     

     

Задача на дооптимизацию по времени перевозки при заданных минимальных затратах 

          

     При ограничениях

     

         

         

        

     3. Алгоритм решения  задачи

       3.1.   Выбор метода

     Задача  о нахождении оптимального плана  перевозок с минимальными затратами  это типичная транспортная задача. Потому, для ее решения можно воспользоваться одним из  методов:

1. метод потенциалов;
2. венгерский метод;

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

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

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

     Алгоритм  решения Т-задачи, основанный на венгерском методе, состоит из предварительного этапа и конечного числа однотипных итераций.

     

     В результате предварительного этапа  вычисляют матрицу

элементы которой удовлетворяют следующим условиям:

         (1)

          (2)

     Если  в условиях (1), (2) строгие равенства, то матрица  является решением Т-задачи. Матрицу, построенную в результате k-й итерации, обозначим . Обозначим также

       (3)

     Величина  называется суммарной невязкой для матрицы . Она характеризует близость  к искомому плану Т-задачи. Итерации проводятся до тех пор, пока величина не станет равна нулю.

     

     3.2.1 Общая схема венгерского  метода

Предварительный этап.

     В каждом из столбцов матрицы транспортных издержек отыскивают минимальный элемент, который вычитают из всех элементов этого столбца. Получают матрицу С'. Далее в каждой строке матрицы С' выбирают минимальный элемент и вычитают его из всех элементов рассматриваемой строки. Приходят к матрице С0 (С0 ~ C), все элементы которой неотрицательны, причем в каждой строке и столбце С0 имеем по крайней мере, один нуль. Строят матрицу Х0 так, чтобы ее ненулевые элементы были расположены в позициях нулей матрицы С0. Пусть - номер строки, в которой расположен k-й нуль j-го столбца матрицы С0. Тогда элементы первого столбца матрицы Х0 определяют по рекуррентной формуле

     Если  , то - оптимальный план Т-задачи. Иначе переходим к первой итерации.

     (k+1)-я  итерация.

     Перед началом итерации выделяют знаком '+' те столбцы матрицы  , для которых невязки по столбцам равны нулю.

     Первый  этап.

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

Возможен  один из двух случаев: 1) , 2) . В первом случае i-ю строку Сk отмечают знаком '+' справа  от нее, а сам невыделенный нуль отмечают штрихом. Далее просматривают элементы i-й строки, которые лежат в выделенных столбцах и ищут среди

них существенные нули.

       Если таким существенным нулем  оказался элемент  ,  а сам столбец m - выделен, то знак выделения '+' над столбцом m уничтожают, а сам этот нуль отмечают звездочкой.  Затем просматривают m-й столбец и отыскивают в нем нуль (нули), расположенные в отличных от i-й строках. Если такой нуль имеется, то отмечают его штрихом и анализируют невязку его строки. Далее процесс поиска нулей и выделение их (штрихами или звездочками) продолжается аналогично, и за несколько шагов он заканчивается одним из следующих исходов:

1. найдем очередной невыделенный нуль матрицы Сk, для которого невязкая в строке .  Тогда отметив его штрихом, переходим ко второму этапу;
2. все нули матрицы Сk оказались выделенными, причем для каждого из нулей, выделяемых штрихом, невязка . Тогда переходим к третьему этапу.

Во втором случае, отметив этот нуль штрихом, сразу переходим к третьему этапу.

         Второй этап.

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

     

     

     Таким образом, -минимальный элемент среди совокупности четных элементов цепочки, невязки строки, где начинается цепочка, и столбца, где она заканчивается.Вычисляем невязку . На этом (k+1)-я итерация заканчивается.

     Третий  этап.

     Пусть , где минимум выбирают из всех невыделенных элементов матрицы Сk. Тогда из всех элементов невыделенных строк матрицы Сk вычитают h, а ко всем элементам выделенных столбцов прибавляют h. В результате получают матрицу С'k(С'k ~ Ck), в которой все существенные нули матрицы Сk остаются нулями, и кроме того, появляются новые невыделенные нули. 
 

    

      
 

     3.3 Метод запрещенных  клеток

     

Задача на дооптимизацию по времени перевозки при заданных минимальных затратах 

          

     При ограничениях

     

         

         

      

     Алгоритм  решения базируется на идеях венгерского  метода для классической транспортной задачи и элементарном здравом смысле. Предварительно выбирается минимальное  значение и запрещаются к рассмотрению все клетки, время которых превышает выбранное ( < ). Тогда пытаются найти план, минимизирующий затраты на перевозку при разрешенных клетках. Если такой план найти не удается или же затраты не равны , то увеличиваем , расширяя таким образом множество клеток доступных для рассмотрения. Наличие запрещенных клеток не повлияет на алгоритм второго этапа венгерского метода, потому он останется без изменений. Остальные же должны учитывать ограничение по . 
 
 

Предварительный этап.

     В каждом из столбцов матрицы транспортных издержек отыскивают минимальный элемент в клетках с , который вычитают из всех элементов этого столбца для которых . Получают матрицу С'. Далее в каждой строке матрицы С' выбирают минимальный элемент в клетках с и вычитают его из всех элементов рассматриваемой строки для которых .  Приходят к матрице С0 (С0 ~ C), все элементы которой неотрицательны. Строят матрицу Х0 так, чтобы ее ненулевые элементы были расположены в позициях нулей матрицы С0. Пусть - номер строки, в которой расположен k-й нуль j-го столбца матрицы С0. Тогда элементы первого столбца матрицы Х0 определяют по рекуррентной формуле

     Если  , то - оптимальный план Т-задачи. Иначе переходим к первой итерации.

     (k+1)-я  итерация.

     Перед началом итерации выделяют знаком '+' те столбцы матрицы  , для которых невязки по столбцам равны нулю.

     Первый  этап.

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

Возможен  один из двух случаев: 1) , 2) . В первом случае i-ю строку Сk отмечают знаком '+' справа  от нее, а сам невыделенный нуль отмечают штрихом. Далее просматривают элементы i-й строки, которые лежат в выделенных столбцах и не в запрещенных клетках, и ищут среди них существенные нули.

       Если таким существенным нулем  оказался элемент  ,  а сам столбец m - выделен, то знак выделения '+' над столбцом m уничтожают, а сам этот нуль отмечают звездочкой.  Затем просматривают m-й столбец и отыскивают в нем нуль (нули), расположенные в отличных от i-й строках и не в запрещенных клетках. Если такой нуль имеется, то отмечают его штрихом и анализируют невязку его строки. Далее процесс поиска нулей и выделение их (штрихами или звездочками) продолжается аналогично, и за несколько шагов он заканчивается одним из следующих исходов:

3. найдем очередной невыделенный нуль матрицы Сk, для которого невязкая в строке .  Тогда отметив его штрихом, переходим ко второму этапу;
4. все нули матрицы Сk оказались выделенными, причем для каждого из нулей, выделяемых штрихом, невязка . Тогда переходим к третьему этапу.

Во втором случае, отметив этот нуль штрихом, сразу переходим к третьему этапу.

Второй  этап.

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

 

     

     

     Таким образом, -минимальный элемент среди совокупности четных элементов цепочки, невязки строки, где начинается цепочка, и столбца, где она заканчивается.Вычисляем невязку . На этом (k+1)-я итерация заканчивается.

     Третий  этап.

     Пусть ,  где минимум выбирают из всех невыделенных элементов матрицы Сk и которые не находятся в запрещенных клетках. Если такой элемент нельзя найти (все не запрещенные клетки выделены), то увеличиваем время , сбрасываем счетчик итераций и идем на предварительный этап. Тогда из всех элементов невыделенных строк матрицы Сk, для которых , вычитают h, а ко всем элементам выделенных столбцов, для которых , прибавляют h. В результате получают матрицу С'k(С'k ~ Ck), в которой все существенные нули матрицы Сk остаются нулями, и кроме того, появляются новые невыделенные нули. 

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

4. Описание программы

     4.1 Основные функции 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4.2 Листинг программы 

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

5. Анализ результатов

Параметры: 

Матрица затрат на перевозку

Таб.1