Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Решение транспортной задачи распределительным методом




 

В общем виде транспортная задача формулируется следующим образом. Имеется mi поставщиков (А1, А2, А3, … Аm), располагающих определенным количеством некоторого продукта ai (где i = 1, 2, … m). Указанный продукт потребляется в пунктах В1, В2, …Вn, причем объемы потребления составляют bj (где j = 1, 2, … n) единиц, а затраты на перевозку единицу продукта из пункта i в пункт j выражены эквивалентным параметром стоимости – расстояния между двумя пунктами lij.

 

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

 


Условия задачи могут быть представлены в виде матрицы (табл. 1).

Математически транспортная задача описывается следующим образом. Первое условие задачи состоит в том, чтобы по оптимальному варианту от каждого поставщика планировалось к поставке то количество продукции, которым он располагает. Это условие записывается в виде следующей системы уравнений:

Х11 + Х12 + Х13 + … + Х1n = а1;

Х21 + Х22 + Х23 + … + Х2n = а2;

Х31 + Х32 + Х33 + … + Х3n = а3;

××××××××××××××××××××××××××××××××××××××××××××××××××;

Хm1 + Хm2 + Хm3 + … + Хmn = аm.

Второе условие предусматривает поставку каждому потребителю продукции в пределах его потребности:

Х11 + Х21 + Х31 + … + Хm1 = b1;

Х12 + Х22 + Х32 + … + Хm2 = b2;

Х13 + Х23 + Х33 + … + Хm3 = b3;

××××××××××××××××××××××××××××××××××××××××××××××××××;

Х1n + Х2n + Х3n + … + Хmn = bn.

Кроме этого должно соблюдаться условие неотрицательности переменных Хij ³ 0.

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

P = l11×X11 + l12×X12 + … + lm1×Xm1 + lm2×Xm2 + … + lmn×Xmn = min.

Приведенная модель соответствует условию .

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

1) , т.е. ресурсы превышают потребность. Задача сводится к тому, чтобы определить, у кого из поставщиков и какое количество продукции следует оставить с точки зрения минимизации суммарных транспортных задач;

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

В первом случае математическая модель будет иметь вид

при условии (i = 1, 2, … m),
  (j = 1, 2, … n).

Во втором случае

при условии (i = 1, 2, … m),
  (j = 1, 2, … n).

Решение указанных условий транспортной задачи рассмотрим на конкретном примере.

Имеется mi предприятий на определенном удалении друг от друга с годовой производственной программой выпуска продукции (табл. 2) и предприятий-потребителей, расположенных в различных районах, спрос на продукцию которых полностью удовлетворяется. Расстояния между потребителями и поставщиками (lij, км) приведены в исходной матрице (табл. 2.)

Если общие ресурсы предприятий-поставщиков превышают суммарный спрос потребителей, то в таблицу отдельным столбцом следует ввести условного (фиктивного) потребителя, на долю которого и падает превышение ресурсов над спросом.

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

Таблица 2

Поставщики, mi Предприятия-потребители, nj Объем производства, тыс. т
B1 B2 B3 B4
A1
A2
A3
Объем потребления, тыс. т  

 

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

Для этого требуется составить первоначальный план перевозки продукции и определить транспортные затраты.

2. 1. Способ «северо-западного угла»

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

Первоначальное распределение по методу «северо-западного угла» показано в таблице 3.

Таблица 3

Предприятия-поставщики, mi Предприятия-потребители nj Объем производства, тыс. т
B1 B2 B3 B4
А1
   
А2
   
А3
   
Объем потребления, тыс. т  

 

Если план перевозок по правилу «северо-западного угла» составлен верно, то в результате получается ступенчатая фигура, начинающаяся в первом верхнем углу таблицы. Число клеток равно числу m + n – 1. В процессе

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

Для устранения вырожденности число занятых клеток необходимо увеличить до m + n – 1. С этой целью одну из свободных клеток условно загружают нулевой загрузкой (0) и считают ее занятой. В качестве условно занятой выбирается клетка, которой соответствует наименьшая длина участка lij.

Транспортная работа при таком способе распределения

Р = 800×280 + 400×220 + 800×190 + 400×330 + 600×340 + 800×300 =

= 1040000 тыс.км.

 

2. 2. Способ выбора минимальной длины участка lij

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

Покажем использование этого способа на нашем примере (таблица 4).

Таблица 4

Предприятия-поставщики, mi Предприятия-потребители nj Объем производства, тыс. т
B1 B2 B3 B4
А1  
   
А2  
   
А3
   
Объем потребления, тыс. т  
               

 

Транспортная работа при составлении плана по способу выбора минимальной стоимости

Р = 200×280 + 1000×170 + 400×190 + 800×180 + 600×390 + 800×210 =

= 848000 тыс. км.

 

 


Поделиться:

Дата добавления: 2015-09-13; просмотров: 117; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты