Иследование транспортнои задачи по критериям стоимости и времени

Автор: Пользователь скрыл имя, 12 Декабря 2011 в 02:11, курсовая работа

Описание работы

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

Содержание

Введение 3
1 Постановка задачи 4
2 Аналитическое решение 6
3 Алгоритм решения задачи 8
3.1 Выбор метода 8
3.2 Венгерский метод 9
3.2.1 Общая схема венгерского метода 10
3.3 Метод запрещенных клеток 13
4 Описание программы 17
4.1 Основные функции 17
4.2 Листинг программы 18
4.3 Руководство пользователя 24
5 Анализ полученных результатов 25
Список литературы 29

Работа содержит 1 файл

tpr.docx

— 213.61 Кб (Скачать)

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

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

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

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

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

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

 

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

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

  
 
 
 

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

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

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

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

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

_____________________                                     
 
 
 
 
 
 

              Киев-2010

РЕФЕРАТ

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

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Содержание

 
 

Введение

3
1

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

4
2

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

6
3

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

8
3.1 Выбор метода 8
3.2 Венгерский  метод 9
3.2.1 Общая схема  венгерского метода 10
3.3 Метод запрещенных  клеток 13
4

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

17
4.1 Основные функции 17
4.2 Листинг программы 18
4.3 Руководство пользователя 24
5

Анализ  полученных результатов

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

     Введение

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

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

     

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

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

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

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

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

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

     

       
 

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

Таб.1

Ai βj
B1 B2 B3 B4 B5 B6 B7 B8 B9 aj
A1 9 18 16 2 3 16 11 15 17 180
A2 16 5 7 20 21 2 7 14 11 140
A3 36 7 10 19 3 9 17 10 14 50
A4 2 19 16 6 12 20 8 12 15 150
A5 15 16 3 11 6 11 18 20 6 80
A6 7 3 12 6 18 8 20 14 8 40
A7 21 10 16 21 16 17 15 14 5 70
bj 50 80 10 10 40 100 130 100 150  
 

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

Таб.2

Ai βj
B1 B2 B3 B4 B5 B6 B7 B8 B9
A1 6 9 3 1 7 4 10 3 2
A2 14 17 16 19 8 11 19 3 14
A3 22 11 12 23 6 18 17 29 4
A4 1 9 13 10 14 4 3 7 10
A5 13 17 10 15 25 5 8 23 2
A6 33 13 2 6 8 4 13 15 11
A7 21 9 12 21 3 3 12 15 24

      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)-я  итерация.

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

Информация о работе Иследование транспортнои задачи по критериям стоимости и времени