Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Описание района перевозок и формирование

Поиск

ВВЕДЕНИЕ

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

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

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

В данной курсовой работе производится определение наиболее опти-мального плана развоза 3-х видов груза в 6 магазинов города Гомеля.

Для планирования перевозок грузов необходимо решить следующие задачи:

¾ определить кратчайшие расстояния между пунктами транспортной сети;

¾ оптимизировать грузовые потоки;

¾ маршрутизировать перевозки грузов;

¾ выбрать подвижной состав для движения по маршрутам;

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

Описание района перевозок и формирование

Транспортной сети региона

В практике грузовых перевозок автомобильным транспортом исходными данными выступают: улично-дорожная сеть с указанием расположения пункта погрузки и пунктов выгрузки (приложение А); объемы поставки номенклатуры грузов каждому конечному потребителю (таблица 1.1); имеющийся парк грузовых автотранспортных средств (таблица 1.2).

Таблица 1.1Номенклатура и количества доставляемого груза

Наименование груза Класс груза Пункт назначения Масса, тонн
Молочные изделия в бумажных пакетах, затаренные в ящиках   М1 0,22
М2 0,25
М3 0,51
М4 0,28
М5 0,42
М6 0,47
Мясо кур в ящиках   М1 0,31
М2 0,32
М3 0,34
М4 0,29
М5 0,28
М6 0,26
Вода минеральная в полиэтиленовых ящиках   М1 0,15
М2 0,13
М3 0,16
М4 0,15
М5 0,1
М6 0,19

 

Таблица 1.2Имеющийся парк автомобильных транспортных средств

Марка автомобиля Грузоподъемность, тонн Количество, ед.
МАЗ 437040-020 4,7  
ЗИЛ 5301ВА 2,3  

 

Районом перевозок является Советский район города Гомеля. В транспортную сеть входят городские улицы и магазины. Крупнейшими улицами, входящими в состав транспортной сети, являются: ул. Бочкина, ул. Богдана Хмельницкого, ул. Барыкина. Средняя скорость движения по улицам транспортной сети 25 км/ч. Все улицы в данном районе имеют усовершенствованное покрытие.

В 1-ом пункте находится база (Б), из которой осуществляется поставка товаров в магазины. Магазины расположены в пунктах 1-6.

По транспортной сети осуществляется перевозка 3-х видов груза.

Молочные изделия в бумажных пакетах, затаренные в ящиках являются грузом третьего класса, имеет средний коэффициент использования грузоподъемности =0,6. Объем данного груза, предназначенный к перевозке - 2150 кг. Объем потребления данного груза в грузопоглащающих пунктах составляет: М1 - 220 кг; М2 - 250 кг; М3 - 510 кг; М4 - 280 кг; М5 - 420 кг; М6 -470 кг.

Второй вид груза – мясо кур в ящиках, является грузом первого класса использования грузоподъемности с коэффициентом использования грузоподъемности =1. Объем этого груза, предназначенный к перевозке – 1800кг. Объем потребления груза в грузопоглащающих пунктах составляет: М1 - 310 кг; М2 - 320 кг; М3 - 340 кг; М4 - 290 кг; М5 - 280 кг; М6- 260 кг.

Третий вид перевозимого груза – вода минеральная в полиэтиленовых ящиках. Данный груз является грузом второго класса со средним коэффициентом использования грузоподъемности = 0,8. Объем данного груза, предназначенный к перевозке – 1010 кг. Объем потребления груза 3-го типа в грузопоглащающих пунктах составляет: М1 - 150 кг; М2 - 130 кг; М3 - 160 кг; М4 - 150 кг; М5 - 100 кг; М6 - 190 кг.

Для выполнения перевозок могут использоваться автомобильные транспортные средства 2-х марок:

- МАЗ 437040-020, грузоподъемностью 4,7 т, в количестве 2 единиц;

- ЗИЛ 5301ВА, грузоподъемностью 2,3 т, в количестве 5 единиц.

На основании исходной схемы улично-дорожной сети строим транспортную сеть (рисунок 1.1).

 

 

Рисунок 1.1 – Транспортная сеть


Путей следования

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

Таблица 2.1 - Расстояния между пунктами транспортировки грузов

Звено Длина, м Звено Длина, м
Б-1   17-6  
1-7   6-18  
7-2   18-1  
2-8   1-29  
8-9   29-30  
9-10   30-31  
10-11   31-32  
11-3   32-33  
3-12   33-4  
12-4   29-34  
4-13   31-35  
13-14   32-36  
15-14   7-34  
5-15   34-35  
5-16   35-36  
16-17   36-37  
37-38   28-13  
34-8   18-23  
35-9   23-24  
36-10   24-25  
37-11   25-26  
23-29   26-27  
24-30   27-14  
25-31   20-24  
26-32   21-26  
27-28   17-19  
19-20   16-22  
20-21   22-15  
22-21      

 

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

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

1) метод потенциалов;

2) табличный метод;

3) определение кратчайших расстояний на ЭВМ.

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

Таблица 2.2 – Матрица кратчайших расстояний между пунктами транспортной

сети района

Начальный пункт Конечный пункт
Б М1 М2 М3 М4 М5 М6
Б -            
М1   -          
М2     -        
М3       -      
М4         -    
М5           -  
М6             -

Для работы на маршрутах

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

Таблица 3.19 Определение количества завозимого в каждый пункт груза

Пункт выгрузки Груз Масса груза, т Коэффициент использования грузоподъемности Масса груза с учетом коэффициента использования грузоподъемности, т Общая масса груза, то
М1 Молочные изделия в бумажных пакетах, затаренные в ящиках 0,22 0,6 0,367 0,865
Мясо кур в ящиках 0,31   0,31
Вода минеральная в полиэтиленовых ящиках 0,15 0,8 0,188
М2 Молочные изделия в бумажных пакетах, затаренные в ящиках 0,25 0,6 0,417 0,9
Мясо кур в ящиках 0,32   0,32
Вода минеральная в полиэтиленовых ящиках 0,13 0,8 0,163
М3 Молочные изделия в бумажных пакетах, затаренные в ящиках 0,51 0,6 0,85 1,39
Мясо кур в ящиках 0,34   0,34
Вода минеральная в полиэтиленовых ящиках 0,16 0,8 0,2
М4 Молочные изделия в бумажных пакетах, затаренные в ящиках 0,28 0,6 0,467 0,945
Мясо кур в ящиках 0,29   0,29
Вода минеральная в полиэтиленовых ящиках 0,15 0,8 0,188
  М5   Молочные изделия в бумажных пакетах, затаренные в ящиках   0,42   0,6   0,7   1,105
Мясо кур в ящиках 0,28   0,28
Вода минеральная в полиэтиленовых ящиках 0,1 0,8 0,125
М6   Молочные изделия в бумажных пакетах, затаренные в ящиках 0,47   0,6   0,783 1,281
Мясо кур в ящиках 0,26   0,26
Вода минеральная в полиэтиленовых ящиках 0,19 0,8 0,238
Итого - 4,83 - 6,486

 

Согласно исходным данным, перевозка может быть осуществлена автомобилями 4-х марок: ЗИЛ-5301АО, грузоподъемностью 3 т; ГАЗ-3302, грузоподъемностью 1,5 т.; ЗИЛ-5301ВА, грузоподъемностью 2,3 т; МАЗ 437040-020, грузоподъемностью 4,7 т. Из таблицы 3.19 видно, что общая масса доставляемого груза, с учетом коэффициента использования грузоподъемности составляет 6,486 т. Исходя из вышесказанного, можно утверждать, что в данном случае необходимо использовать 1 автомобиль марки ЗИЛ-5301ВА и 1 автомобиль марки МАЗ 437040-020. Во втором перевозим: молочные изделия в бумажных пакетах и воду, затаренные в ящиках, в первом: мясо кур в ящиках. Такое утверждение основано на следующих умозаключениях:

- должен быть перевезен весь груз;

- приоритет необходимо отдавать автомобилям большей грузоподъемности, при этом должно обеспечиваться максимальное значение степени использования грузоподъемности автомобилей;

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

 

Рассмотрим существующий маршрут перевозки грузов для первого автомобиля:

Рассчитаем транспортную работу для данного маршрута и автомобиля:

Рассмотрим существующий маршрут перевозки грузов для второго автомобиля:

Рассчитаем транспортную работу для данного маршрута и автомобиля:

79378 т м

Общая транспортная работа на двух автомобилях:

Р общ =

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

Рассчитаем транспортную работу для данного маршрута и автомобиля:

Рассмотрим существующий маршрут перевозки грузов для второго автомобиля:

 

Рассчитаем транспортную работу для данного маршрута и автомобиля в обратном направлении:

Общая транспортная работа на двух автомобилях в обратном направлении:

Р общ =

Исходя из того, что транспортная работа в обратном направлении больше чем в прямом, выбираем существующий маршрут в прямом направлении Б – М1 – М2 – М3 - М4 – М5- М6 - Б


ЗАКЛЮЧЕНИЕ

В ходе данной курсовой работы были определены кратчайшие расстояния между пунктами транспортной сети с использованием компьютерной программы NAKRA. Были оптимизированы грузовые потоки при развозе 3-х видов грузов по 6 магазинам города Гомеля, а также были составлены маршруты перевозки этих грузов. Был выбран подвижной состав для осуществления данных перевозок.

Кроме того, были рассчитаны основные технико-эксплуатационные показатели работы подвижного состава и был произведен сравнительный анализ существующего и предлагаемого вариантов маршрутов перевозок грузов. В результате чего был выбран предлагаемый маршрут с движением в прямом напрвлении Б – М1 – М2 – М3 – М4 – М5 – М6– Б, транспортная работа которого составляет 106,095 т-км, а общий пробег автомобилейработающих на данном маршруте 38,1 км, так как он является наиболее выгодным и целесообразным для данного района города Гомеля.


 

Литература

1 Автомобильные перевозки пассажиров и грузов. Практикум: учебное пособие / С.А. Аземша, С.В. Скирковский, С.В. Сушко; М-во образования Респ. Беларусь, Белорус. гос. ун-т трансп. - Гомель: БелГУТ, 2012. - 205 с.

2 Требования по оформлению отчетных документов самостоятельной работы студентов: учебно-методическое пособие / М.А. Бойкачев [и др.]; М-во образования Респ. Беларусь, Белорус. гос. ун-т трансп. - Гомель: БелГУТ, 2008. - 62 с.

3 http://www.uchimatchast.ru/aplication/litl0.php - ипользовали для решения задачи коммивояжера методом Литтла.

 

 

ПРИЛОЖЕНИЕ А

M (М1,Б) = М1 - Б; L = 3500 м

M (М2,Б) = М2 - 7 - М1 - Б; L = 8500 м

M (М3,Б) = М3 - 11 - М1 - 7 - М2 - 8 - 9 - 10 - Б; L = 12400 м

M (М4,Б) = М4 - 33 - М1 - 29 - 30 - 31 - 32 - Б; L = 7800 м

M (М5,Б) = М5 - 16 - М1 - 18 - 17 - М6 - Б; L = 14200 м

M (М6,Б) = М6 - 18 - М1 - Б; L = 10300 м

из/в Б М1 М2 М3 М4 М5 М6

Б ---- 3500 8500 12400 7800 14200 10300

М1 3500 ---- 5000 8900 4300 10700 6800

М2 8500 5000 ---- 3900 8800 15300 11800

М3 12400 8900 3900 ---- 5000 11500 14900

М4 7800 4300 8800 5000 ---- 6500 9900

М5 14200 10700 15300 11500 6500 ---- 3900

М6 10300 6800 11800 14900 9900 3900 ----

Начальный пункт Конечный пункт
Б М1 М2 М3 М4 М5 М6
Б -            
М1   -          
М2     -        
М3       -      
М4         -    
М5           -  
М6             -

 

ПРИЛОЖЕНИЕ Б

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

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

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

 

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

Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г1,2=3500, Г2,1=3500, Г2,5=300, Г3,4=1800, Г4,3=1800, Г5,2=700, Г6,7=5100, Г7,6=5100,
В результате сравнения мы получили 2 одинаковых максимальных Г=5100. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно.Рассмотрим вариант Г6,7=5100
Удалим из матрицы стоимости строку 6 и столбец 7, и присвоим элементу (7,6) значение бесконечности. Внесем в текущий ориентированный граф дугу (6,7)

В строке 7 и столбце 6 отсутствует элемент равный ∞. Присвоим элементу (7,6) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=27700
Нижняя граница равна сумме всех вычтенных элементов в строках и столбцах. Итоговое значение нижней границы должно совпасть с длиной результирующего контура.
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г1,2=3500, Г2,1=3500, Г2,5=300, Г3,4=1800, Г4,3=1800, Г5,2=0, Г5,6=5000, Г7,2=2300,
Максимальное значение имеет Г5,6=5000
Удалим из матрицы стоимости строку 5 и столбец 6. Внесем в текущий ориентированный граф дугу (5,6)


           
         
         
         
         
           


В строке 7 и столбце 5 отсутствует элемент равный ∞. Присвоим элементу (7,5) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=32800
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

 

           
         
         
         
         
         


То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

 

           
         
         
         
         
         


Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г1,2=3500, Г2,1=3500, Г2,5=300, Г3,4=6500, Г4,3=1800, Г7,2=3500,
Максимальное значение имеет Г3,4=6500
Удалим из матрицы стоимости строку 3 и столбец 4. Внесем в текущий ориентированный граф дугу (3,4)


         
       
       
         
       


В строке 4 и столбце 3 отсутствует элемент равный ∞. Присвоим элементу (4,3) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=32800
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

 

         
       
       
       
       


То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

 

         
       
       
       
       


Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г1,2=3500, Г2,1=3500, Г2,3=3500, Г2,5=0, Г4,5=4700, Г7,2=3500,
Максимальное значение имеет Г4,5=4700
Удалим из матрицы стоимости строку 4 и столбец 5. Внесем в текущий ориентированный граф дугу (4,5)


       
     
     
       


В строке 7 и столбце 3 отсутствует элемент равный ∞. Присвоим элементу (7,3) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=34600
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

 

 

       
     
     
     


То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

 

       
     
     
     


Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г1,2=3500, Г2,1=3500, Г2,3=3500, Г7,2=3500,
В результате сравнения мы получили 4 одинаковых максимальных Г=3500. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно.Рассмотрим вариант Г1,2=3500
Удалим из матрицы стоимости строку 1 и столбец 2, и присвоим элементу (2,1) значение бесконечности. Внесем в текущий ориентированный граф дугу (1,2)

 

     
     
   


В строке 2 и столбце 1 отсутствует элемент равный ∞. Присвоим элементу (2,1) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=34600
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=38100
Маршрут коммивояжера включает в себя дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (1, 2), (2, 3), (7, 1)
-------------------------------------------------------------------------
Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г7,2. Удалим из матрицы стоимости строку 2 и столбец 7. Внесем в текущий ориентированный граф дугу (7,2)

 

     
   
     


В строке 2 и столбце 3 отсутствует элемент равный ∞. Присвоим элементу (2,3) значение бесконечности чтобы избежать преждевременногог замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=38100
Маршрут коммивояжера включает в себя дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (7, 2), (1, 3), (2, 1)
-------------------------------------------------------------------------
Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г2,3. Удалим из матрицы стоимости строку 3 и столбец 2. Внесем в текущий ориентированный граф дугу (2,3)

 

     
   
     


В строке 7 и столбце 2 отсутствует элемент равный ∞. Присвоим элементу (7,2) значение бесконечности чтобы избежать преждевременногог замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=38100
Маршрут коммивояжера включает в себя дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (2, 3), (1, 2), (7, 1)
-------------------------------------------------------------------------
Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г2,1. Удалим из матрицы стоимости строку 1 и столбец 2. Внесем в текущий ориентированный граф дугу (2,1)

 

 

     
     
   


В строке 1 и столбце 2 отсутствует элемент равный ∞. Присвоим элементу (1,2) значение бесконечности чтобы избежать преждевременногог замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=38100
Маршрут коммивояжера включает в себя дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (2, 1), (1, 3), (7, 2)
-------------------------------------------------------------------------
Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г7,6. Удалим из матрицы стоимости строку 6 и столбец 7. Внесем в текущий ориентированный граф дугу (7,6)

 

             
           
           
           
           
           
             


В строке 6 и столбце 7 отсутствует элемент равный ∞. Присвоим элементу (6,7) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

 

             
           
           
           
           
           
           


То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

 

             
           
           
           
           
           
           

 

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г1,2=3500, Г2,1=3500, Г2,5=0, Г2,7=2300, Г3,4=1800, Г4,3=1800, Г5,2=700, Г6,5=5000,
Максимальное значение имеет Г6,5=5000
Удалим из матрицы стоимости строку 6 и столбец 5. Внесем в текущий ориентированный граф дугу (6,5)


           
         
         
         
         
           


В строке 5 и столбце 7 отсутствует элемент равный ∞. Присвоим элементу (5,7) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=32800
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

 

           
         
         
         
         
         


То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

 

           
         
         
         
         
         


Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г1,2=3500, Г2,1=3500, Г2,7=3500, Г3,4=1800, Г4,3=6500, Г5,2=700,
Максимальное значение имеет Г4,3=6500
Удалим из матрицы стоимости строку 4 и столбец 3. Внесем в текущий ориентированный граф дугу (4,3)


         
       
       
         
       


В строке 3 и столбце 4 отсутствует элемент равный ∞. Присвоим элементу (3,4) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=32800
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

 

         
       
       
       
       


То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

 

         
       
       
       
       


Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г1,2=3500, Г2,1=3500, Г2,7=3500, Г3,2=3500, Г5,2=0, Г5,4=4700,
Максимальное значение имеет Г5,4=4700
Удалим из матрицы стоимости строку 5 и столбец 4. Внесем в текущий ориентированный граф дугу (5,4)


       
     
     
       


В строке 3 и столбце 7 отсутствует элемент равный ∞. Присвоим элементу (3,7) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=34600
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

 

       
     
     
     


То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

 

       
     
     
     


Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г1,2=3500, Г2,1=3500, Г2,7=3500, Г3,2=3500,
В результате



Поделиться:


Последнее изменение этой страницы: 2016-08-16; просмотров: 237; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 52.14.219.203 (0.013 с.)