Лабораторная работа по дисциплине «Теория транспортных процессов и систем »

ПЕРВОЕ ВЫСШЕЕ ТЕХНИЧЕСКОЕ УЧЕБНОЕ ЗАВЕДЕНИЕ РОССИИ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«НАЦИОНАЛЬНЫЙ МИНЕРАЛЬНО-СЫРЬЕВОЙ УНИВЕРСИТЕТ «ГОРНЫЙ»

_____________________________________________________________________________   

 

 

 

 

 

 

 

 

                                            Лабораторная работа

                                                       по дисциплине

                                 «Теория транспортных процессов и систем »

                                                     

                                                     

                                

 

 

 

 

 

 

 

                                                                Выполнил: Шерстнёв В.В.

                                                                Группа: ОПУз-10

                                                                Шифр:1160031971

                                                                Дата  выполнения:

                                                                Дата  проверки:

                                                                Оценка:

                                                                Проверил: Доц,Беляев А.И.

 

 

 

 

                                            Санкт-Петербург 

                                           2013г.

 

                                         СОДЕРЖАНИЕ

 

 

Транспортная задача линейного программирования, метод потенциалов	4
Литература	11

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

  Потребителям В1, В2, В3 и В4 требуется песок в количестве 30, 70, 40 и 30 тонн. На складах поставщиков А1, А2 и А3 имеется соответственно 80, 50 и 40 тонн. Расстояния lij между ними указаны в таблице-матрице, которую составляем.

На основании исходных данных формируется матрица (табл.1).

Таблица 1

Матрица условий

Пункт отправ- ления		Пункт назначения				Налич. груза,  т
		В1	В2	В3	В4
		V1	V2	V3	V4
А1	U1	9	15	5	8	80
А2	U2	4	9	6	5	50
А3	U3	16	22	40	18	40
Потребность в грузе, т		30	70	40	30	170

Рассмотрим метод потенциалов.

Составляем допустимый исходный план следующим порядком.

Три ограничения, которые представлены в математической записи линейного программирования:

- полное обеспечение всех потребностей;

- полный вывоз всего груза;

- не отрицательность любой поставки.

1. Сначала планируем перевозки  с первого склада (А1) ближайшим потребителям.

2. Затем со второго склада (А2) ближайшим потребителям и так далее заполняем таблицу.

      Проводится это способом минимального элемента по строке следующим образом - вначале планируем перевозки грузов с первого склада, записывая их в клетки с ближайшим расстоянием к потребителю. Клетке А1-В3, которая находится на расстоянии 5 км от склада А1|, требуется 40 тонн, а на складе -80 тонн. Запрос удовлетворяется полностью на складе остаётся ещё 40 тонн, которые направляем к следующему ближайшему потребителю. Им оказывается потребитель В4, которому требуется 30 тонн груза. Полностью удовлетворяем запрос и этого потребителя, а на складе А1, остаётся 10 тонн, которые направляем к следующему ближайшему (последнему) потребителю В1 которому требуется 30 тонн груза, таким образом весь груз со склада А1вывезен полностью.

     Переходим к перераспределению груза со склада А2. В первую очередь, удовлетворяем ближайшего, ещё не удовлетворённого потребителя. Им является потребитель В1 (4 км), которому требуется 30 тонн груза (10 тонн было завезено со склада А1), поэтому со склада А2 мы можем поставить 20 тонн груза, полностью удовлетворив потребителя В1.

     На складе А2 осталось 30 тонн груза, следующий ближайший потребитель является В2, которому требуется 70 тонн груза. Оставшиеся 30 тонн получает потребитель В2. Со склада А3 направляем оставшиеся 40 тонн потребителю В2. Таким образом, потребности всех потребителей полностью удовлетворены, а со всех складов полностью вывезены все запасы груза.

     На этом этапе вычисления закончены.

3. Вычисляется транспортная работа, которая будет равна

Р=10*9+40*5+30*8+20*4+30*9+40*22=1760

     В табл.2 представлен исходный допустимый план перевозок.

 

 

 

 

 

 

 

 

Таблица 2

Исходный допустимый план перевозок

Пункт отправления	Строка   Столб.	Пункт назначения				Наличие груза,  т
		В1	В2	В3	В4
		V1=9	V2=14	V3=5	V4=8
А1	U1  =0	9 10	15	5 40	8 30	80
А2	U2 =-5	4 20	9 30	6	5	50
А3	U3   =8	16	22 40	40	18	40
Потребность в грузе, т		30	70	40	30	170

 

        Проверяем  заполненность матрицы, т. е. число заполненных клеток по критерию m+n-1. Если число клеток отличается от числа по критерию и матрица является вырожденной, по ней проводить дальнейшие расчёты невозможно.

       Проверка разработанного  плана на оптимальность состоит из двух этапов: на первом этапе вычисляются вспомогательные индексы - Ui и Vj, а на втором этапе исследуются незанятые клетки на потенциальность с целью определения суммы индексов - Ui+Vj ≥Lij. Рассчитываем на матрице специальные индексы U и V и заносим их в строку и столбец матрицы. Для определения индексов используются следующие правила:

- вспомогательный индекс U1 всегда равен нулю,

- для каждой занятой клетки  матрицы сумма, соответствующей  ей индексов U и V, равна расстоянию  в данной клетке, т. е.

Ui + Vj = Lij, где Lij - расстояние в клетке.

Это даёт возможность при известном одном индексе определить значение другого.                                   Ui = Lij  - Vj ;                                          (5)

                                               Vj = Lij  - Ui .

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

Lij  ≥Ui + Vj ,

т. е. расстояния должны быть больше или равны сумме индексов.

Запишем в матрицу (табл. 2) U1 = 0, тогда в соответствии с формулами:

V3=LI3 – U1=5 - 0=5;

V4=LI4 – U1=8 - 0=8;

V1=L11 – U1=9 - 0=8.

Далее

                                             U2=L21-V1 =4-9 = -5;

V2=L22 - U2= 9-(-5) = 14;

U3 =L32- V2 = 22 - 14= 8.

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

        Эта проверка заключается в сравнении расстояния каждой незанятой клетки матрицы с суммой соответствующих ей индексов с целью выявления Ui + Vj>Lij.

  A1B2(U1+V2) =0+14=14 <L12=15;

A2B3(U2+V3)= -5+5=0   <L23=6;

А2 B4(U2+V4)= -5+8=3  <L24=5;

А3 B1(U3+V1)=8+9=17  <L31=16;

А3 B3(U3+V3)=8+5= 13  <L33=10;

А3 B4 (U3+V4)=8+8=16 <L34=18.

        Проверка показывает, что у незанятых клеток А3 B1 и А3 B3 расстояние меньше суммы индексов, следовательно, составленный допустимый исходный план не является оптимальным и подлежит улучшению. Выявленные клетки являются резервом улучшения плана, и поэтому их называют потенциальными, почему и рассматриваемый метод называют "методом потенциалов".

Полученные потенциалы обозначим в матрице подчеркнутой цифрой  (цифра -превышение индекса над расстоянием).

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

- для клетки с наибольшим  потенциалом (в нашем случае А3 B3) строим замкнутую цепочку из горизонтальных и вертикальных линий так, чтобы одна её вершина лежала в потенциальной клетке, а все остальные вершины располагались бы в занятых клетках. Конфигурации цепочки могут быть разной формы, но только из вертикальных и горизонтальных клеток.

- составив цепочку, помечают знаком (+) её нечетные вершины (считая  первой в потенциальной клетке) и знаком (-) чётные вершины. Наименьшая  из чётных загрузок определяет  величину перемещаемой загрузки (в нашем случае 20 т).

- переместив эту загрузку из  клетки со знаком (-) в клетку  со знаком (+), получаем новый вариант  плана с меньшей транспортной  работой (табл.3). Величины новых перемещений представлены в квадратиках.

 

 

 

 

 

 

 

 

Таблица 3

Построение цепочки перемещений

Пункт  отправления	Строка   Столб.	Пункт назначения				Наличие груза,  т
		В1	В2	В3	В4
		V1=9	V2=14	V3=5	V4=8
А1	U1  =0	30          9        10+	15 <	20          5     -40	8 30	80
А2	U2 =-5	0            4 20	50          9  30      +	6 <	5 <	50
А3	U3   =8	16 1           >	20        22 40   -	20        10 3       +  >	18	40
Потребность в грузе, т		30	70	40	30	170