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

      Методические указания разработали 

 проф. Скороходов А.Н., доц. Уваров В..П. 

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

Задание. Производственную ситуацию, соответствующую Вашему варианту, выберите из таблицы1.

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

1. Типы инженерных задач при организации перевозок сельскохозяйственных грузов

Интенсификация сельскохозяйственного производства предполагает возрастание роли транспорта. На долю транспортных операций приходится 30-40 % всех затрат денежных средств, необходимых для производства сельскохозяйственной продукции.

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

- при организации перевозок : зерна, картофеля, свеклы, силоса, сена. соломы и т.д. с полей к местам хранения или складирования продукции;

- транспортировка органических или минеральных удобрений от ферм или мест складирования на поля и т.д.

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

Пусть имеется m пунктов сосредоточение однородного груза, который необходимо перевезти на n пунктов назначения. Количество груза на i- ом пункте отправления (i=1,2,3…m) равно Q_i тонн. Потребность j-го пункта назначения в этом грузе (j=1,2,3…n) составляет В_j тонн. Расстояние между каждым пунктом отправления и назначения груза известно. Для перевозки груза используются однотипные транспортные средства (тракторные тележки, бортовые автомобили, самосвалы и т.д.).

Таблица 1

Производственная ситуация

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

Соотношение количества груза во всех пунктах его отправления ( ) и потребностей в нем всех пунктов назначения ( ) и потребностей в нем всех пунктов назначения ( ) может быть различным, а именно: 

=    (1)

>         (2)

<       (3)

Первое условие означает, что общие потребности пунктов назначения в грузе равны его запасам на пунктах отправления. Неравенство (2) означает, что запасы груза превалируют над его потребностями, а неравенство (3) выражает обратное условие.

Транспортная задача, содержащая условие (1), называется задачей закрытого типа. Если же условие задачи отвечает соотношению (2) или (3), то она относится к числу транспортных задач открытого типа.

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

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

2. Математическая формулировка транспортной задачи

Обозначим через х  искомое количество груза., перевозимого с i-го пункта на j-ый. Общая величина грузоперемещений Z, которую предстоит сделать при транспортировке всего заданного объема груза будет

Z= X .   (4)

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

Z= X =min               (5)

Уравнение (5) выражает основное условие задачи, цель поиска, поэтому его называют функцией цели.

При минимизации уравнения (5) из всего множества значений х , должны быть выбраны только определенные значения, которые удовлетворяют остальным требованиям задачи. Прежде всего диапазон возможных значений х ограничен областью положительных чисел. Это следует из физического существа величины х . Отрицательное значение х  означало бы транспортировку уже перевезенного груза в обратном направлении, т.е. с j-го пункта на i-ый, что противоречит смыслу задачи.

Это ограничение может быть записано так

х 0 i=1, m,   j=1, .   (6)

Кроме того из условия задачи следует, что общее количество груза, перевозимого с i-го пункта отправления во все пункты назначения, равно запасам груза на этом пункте, т.е.

=Q           i=1, .                      (7)

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

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

= B j=1, .                      (8)

Суммирование здесь происходит по всем возможным маршрутам, заканчивающимся в  j-ом пункте, а их число потенциально равно m.

Равенства (7) и (8) обусловлены тем, что по условию задачи общие запасы груза на пунктах отправления равны общим потребностям в нем всех пунктов назначения.

Других ограничений, кроме отмеченных, которые было бы необходимо соблюсти при решении задачи, в ее условии нет.

Таким образом, математическая формулировка транспортной задачи закрытого типа ( = ) имеет вид:

Найти минимум функций цели

Z= X =min.

При следующих ограничениях:

1. х 0

2. =Q

3. =B

В открытой модели транспортной задачи запасы груза на пунктах отправления не равны потребностям в нем пунктов назначения,

≠ .

В соответствии с условием уравнение функции цели для транспортной задачи обоих типов одинаково.

В тех случаях, когда в пунктах отправления грузов имеется больше, чем требуется в пунктах назначения, т.е. =  система уравнений оказывается несовместной, так как часть груза должна оставаться на пунктах отправления. Поэтому условие задачи (7) следует писать так:

≤ Q        i=1, .   (9)

В этом случае с i-го пункта может быть вывезен или весь груз или только часть его.

При избытке груза на пунктах его отправления, по сравнению с общим объемом перевозок во все пункты назначения, на j-ый пункт поступит точно B  тонн груза. Следовательно, условие (8) останется неизменным.

При недостатке запасов груза, т.е. при общее количество груза, перевозимого с i-го пункта отправления во все пункты назначения, равно запасам груза на этом пункте, т.е. условие (7) останется неизменным.

Соотношение общего объема груза, поступившего на j-ый пункт по всем маршрутам, и потребностей этого пункта при дефиците в запасах (условие 8) следует записать

≤B j=1, . (10)

Таким образом, математическая формулировка транспортной задачи открытого типа ( ≠ ) имеет вид :

Найти минимум функции цели

Z= X =min.

При следующих ограничениях

для случая                                           для случая

>                                                   <       

 1)  х 0 ;                                                          1) х 0 ;

 2)  ≤ Q ;                                        2)    =Q ;

  3)       = B .                                             3) ≤B .

Открытую модель транспортной задачи при недостатке запасов можно свести к закрытой модели. Для этого необходимо ввести еще один фиктивный пункт отправления (m+1)-й, для которого положим

Q = - .            (11)

   Стоимость (расстояние) перевозки от фиктивного пункта отправления до каждого пункта потребления положим равной нулю.

   В случае превышения запасов над потреблением введем фиктивного потребителя (n+1) мощностью

B = - .                                (11а)

   Стоимость перевозок по фиктивным маршрутам также положим равной нулю.

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

   При решении транспортных задач встретиться ряд дополнительных ограничений.

   ПЕРВОЕ ДОПОЛНИТЕЛЬНОЕ ОГРАНИЧЕНИЕ- отсутствие транспортной связи между каким-либо поставщиком и потребителем. То есть x =0.В данном случае оценка переменной искусственно завышается на большую величину, так что направление груза по этому маршруту будет невыгодным, так как функция цели всегда стремится к минимуму.

   ВТОРОЕ ДОПОЛНИТЕЛЬНОЕ ОГРАНИЧЕНИЕ- наличие частной заранее фиксированной связи между поставщиками и потребителями, то есть x =q, искомый объем перевозок от i-го поставщика к j-му потребителю должен быть строго равен величине q. В этом случае до начала решения задачи от соответствующего маршрута вычитается величина q, затем оценка данного маршрута искусственно завышается и задача решается обычным порядком.

   ТРЕТЬЕ ДОПОЛНИТЕЛЬНОЕ ОГРАНИЧЕНИЕ заключается в том, что x ≥q, то есть искомый объем перевозок от i-го поставщика к j-му потребителю должен быть не меньше величины q.В этом случае до начала решения от соответствующего поставщика и потребителя вычитают величину q, затем задачу решают обычным путем.

3.Методы решения транспортной задачи

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

   Для решения транспортной задачи составим опорный или начальный план При этом опорным или начальным планом задачи будет такой, для которого все базисные (m+n-1) переменные будут больше нуля. А свободные равны нулю. Методику решения транспортной задачи рассмотрим на конкретном примере.

   ПРИМЕР. Имеется три поля: 1,2,3, валовый сбор картофеля на которых соответственно 100,130 и 170 тонн. В хозяйстве имеется также четыре картофелехранилища в которые нужно доставить картофель. Расстояние от каждого поля до каждого хранилища, а также их емкость представлена в таблице 2.

Таблица 2.

Исходные данные по условию задачи

№№ полей	Валовый сбор картофеля т.	Расстояние от полей до картофелехранилищ, км
		1	2	3	4
1	100	3 х	5 х	7 х	11 х
2	130	1 х	4 х	8 х	3 х
3	170	6 х	8 х	12 х	7 х
Емкость картофелехранилищ, т		150	120	80	50

Необходимо составить оптимальный план перевозок с полей в картофелехранилища (однотипными транспортными средствами),обеспечив

минимум грузоперемещений при выполнении всего объема транспортных работ.

   Для составления первоначального (опорного) плана используем метод минимального элемента, который предусматривает рассмотрение всех C  таблицы 2 и выбор наименьших из них. Грузы будут перевозиться по тем маршрутам, где расстояние (стоимость) перевозки, т.е. величина C  будет минимальной.

   Заполнение таблицы 2 начинаем с маршрута 2,1,где С  равна 1 и является минимальной.

   Так как валовый сбор с поля 2 меньше ,чем потребности хранилища 1, то картофель с поля 2 полностью вывозится в хранилище 1.Хранилище 1 еще может вместить 150-180=20 тонн, которые могут быть доставлены с поля 1, так как после С  следующим по величине является элемент С  равный 3.Учитывая, что с поля 2 картофель полностью вывезен и хранилище 1 заполнено, выбираем следующий минимальный элемент. Он находится на маршруте 1,2 и равен 5. В хранилище 2 с поля 1 может быть доставлено 100-20=80 тонн картофеля. Следующим минимальным по величине в незаполненных строках и столбцах является элемент маршрута 3,4 равный 7. Хранилище 4 может быть полностью заполнено с поля 3.

   Следующий минимальный элемент находится на маршруте 3,2 и равен 8. В хранилище 2 с поля 3 может быть завезено 120-80=40 тонн. Оставшийся картофель с поля 8 в количестве 170-50-40=80 тонн может быть полностью помещен в хранилище 3.      

Таблица 3

Первоначальный план перевозок

   Суммарная величина грузоперемещений по этому плану составит

Z=3,20+5,80+1,130+8,40+12,80+7,50=2220 ткм.

   Улучшить решение задачи, полученное методом минимального элемента, можно, применив для этого метод потенциалов. Введем новые переменные ְα и β.

   Переменные α будут соответствовать строкам, а β- столбцам таблицы.

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

β - α = C               ( для всех х > 0 базисных клеток)     (12)

 β - α ≤ C              (i=1, ; j=1,  для свободных клеток) (13)

   Для транспортной задачи условия (12, 13) называются условиями потенциальности, а ְα и β потенциалами. Если эти условия выполняются, то решение задачи будет оптимальным.

   Для нашей задачи ранг матрицы (r =m+n-1) равен  r=4+3-1=6( заполнено 6 клеток). Составим для них уравнения вида (12).

Таблица 4

Первая итерация

№ хранилища   №№ полей	1	2	3	4	Валовый сбор картофеля, т	Потенциалы строк
1	3 20	5 _ 80	7      +	11	100	α =0
2	1 130	4	8	3	130	α =2
3	6	8 + 40	12 _ 80	7 50	170	α =3
Емкость картофелехранилища, т	150	120	80	50
Потенциалы столбцов	β =3	β =5	β =9	β =4

β - α =3        β - α =1          β - α =12

β - α =5      β - α =8         β - α = 7

   Так как число неизвестных превышает на единицу число уравнений, то одну из неизвестных полагаем равной произвольному числу, например α =0. Потенциалы остальных строк и столбцов найдем из уравнений (12).

   Составим ограничения вида (13) для свободных маршрутов таблицы 3 и проверим решение задачи на оптимальность:

1) β - α ≤ 7;        2) β - α  ≤ 11;        3) β - α  ≤ 4;

4) β - α ≤6;         5) β - α ≤ 3;           6) β - α ≤ 5;

1) 9 < 7;     2) 4 < 11;             3) 3 < 4;     4) 7 < 8;

5) 2 < 3;     6) 6=6.

   Наибольшее расхождение наблюдается в первом ограничении, т.е. для маршрута (1,3). Следовательно, условие потенциальности нарушено и полученный план перевозок не оптимален.

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

Базисные маршруты всегда образуют разомкнутую цепь и , чтобы образовать цикл, нужно присоединить свободный маршрут. Вершины цепи отмечают поочередно знаками «+» и «-», начиная со знака «+» и маршрута, в котором нарушено условие потенциальности.

   Среди маршрутов, отмеченных знаком «-» выбираем минимальное количество груза Q=x . Прибавляем его к маршрутам, отмеченным знаком «+», вычитаем из маршрутов, отмеченных знаком «-».

   В нашем примере отмечаем маршрут 1-3 знаком «+». (Нарушено условие потенциальности). Соединим его с базисным маршрутом 3-3 и отметим его знаком «-». Замкнем цепь, соединив между собой маршруты 3-2 и 1-2, отметив их соответствующим образом.

   В нашем отрицательном полуцикле выберем элемент Q=min {80=80}=80. Этот элемент прибавим и вычтем от соответствующих маршрутов и получим новый план решения задачи (таблица 5).

Таблица 5

Вторая итерация