Транспортная задача

Условие:

Готовая продукция заводов ai (i=1-3) направляется на склады Bj (j=l-4). Заводы ai производят аi, тыс. изделий. Пропускная способность складов Bj за это время характеризуется величинами bj, тыс. изделий. Стоимость перевозки с завода ai, на склад Bj одной тысячи изделий равна Сij (ден.ед.).

 

с11	с12	с13	с14	а1		4	3	5	6	200
с21	с22	с23	с24	а2	=	8	1	9	7	500
с31	с32	с33	с34	а3		3	2	8	1	300
b1	b2	b3	b4	k		350	400	200	150	3

Требуется:

1) составить экономико-математическую модель задачи,  которая позволила бы найти план перевозки готовой продукции заводов на склады с минимальными затратами;

2)                 определить оптимальный план перевозки готовой продукции на склады при дополнительном условии, что на складе Вк (где k — дополнительные условия) созданы лучшие условия для хранения готовой продукции, а поэтому он должен быть загружен полностью;

3)                 найти величину fmin минимальных транспортных затрат;

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

 

Решение:

1. Запишем начальные условия задачи в форме табл. 1.

Табл.1

Мощности заводов Аi, (шт)	Склады и их спрос
	В1 (350 )	В2 ( 400 )	В3 (200  )	В4 (150 )
А1 ( 200)	4 X11	3 X12	5 X13	6 X14
А2 (500 )	8 X21	1 X22	9 X23	7 X24
А3 (300)	3 X31	2 X32	8 X33	1 X34

Обозначим через Хij (i = 1,3; j = 1,4) количество  изделий, кото­рое планируется перевезти с завода Аi, на склад bj, а через f - общие транс­портные затраты.

Целевая функция задачи запишется в виде:

f=   4 • X11 +   3• X12 +...+  1•X34 (min)                          (3.1)

Сравнивая суммарную мощность 200+500+300=1000 с потребностью  

складов bj   350+400+200+150=1100 , видим, что эти суммы не совпадают. Следовательно, данная транспортная задача обладает открытой моделью. Часть продукции ( 100 единиц) останется недопоставленной.

Переходя к ограничениям на переменные Хij, следует учесть, что ко­личество продукции, вывозимой из каждого завода Аi, не может превышать мощности производства на этом заводе, т.е.

X11 + X12 + X13+ X14  200

X21 + X22 + X23 + X24   500                                  (3.2)

 X31 + X32+ X33 + X34  300                                 

В то же время склады bj должны быть обеспечены полностью, т.е. сумма поставок, направляемых на каждый склад Bj со всех заводов Аi , должна равняться их потребности. Эти требо­вания можно выразить следующими равенствами:

X11 + X21 + X31 = 350

X12 + X22 + X32 = 400

 X13 + X23+ X33 = 200

X14 + X24+ X34  =  150                             (3.3)

Если исключить обратные перевозки, то должны выполняться условия

Хij  ≥0    (i=1,3; j=1,4)                                  (3.4)

Соотношения (3.1) - (3.4) образуют экономико-математическую модель рассматриваемой задачи.

Таким образом, математическая модель задачи: целевая функция (3.1), описывающая транспортные затраты, минимизируется при ограниче­ниях (3.2) - (3.4).

2. Введем в рассмотрение фиктивный завод А4  с мощностью производства, равной небалансу, т.е.

1100-1000=100  изделий с одинаковыми затратами на перевозку, равными нулю: C4j= 0 (j=1,4).

Однако по условиям задачи необходимо найти оптимальный план задачи    при дополнительном условии, что склад  В3 должен быть загружен полностью. Это ограничение будет соблюде­но в том случае, если в заключительной таблице с оптимальным планом клетки (4; 3) останутся свободными. Чтобы добиться этого на время решения условно завысим показатель критерия оптимальности в клетках (4 ;3), например, до значения

(+100). Понятно, что теперь занимать клетки (4; 3) будет явно невыгодно.

Приступая к составлению исходного опорного плана, устанавливаем, что в нашем случае любой опорный план должен «загружать» m+n-1=3+5-1-7  клеток.

 

Таблица 2

Мощности заводов Аi, (шт)	Склады и их спрос
	В1 (350 )	В2 ( 400 )	В3 (200  )	В4 (150 )	Ui
А1 ( 200)	4	3	5 200	6	U1= 0
А2 (500 )	8 100	1 400	9 0	7	U2= 4
А3 (300)	3 150	2	8	1 150	U3= -1
А4 (100)	0 100	0	+100	0	U4= -4
Vj	V1=4	V2=-3	V3=5	V4=2

 

Построим исходный опорный план методом минимального элемента.

Для исследования плана на оптимальность необходимо найти оценки свободных клеток. Для этого надо знать потенциалы Ui и Vj заводов  Аi и складов bj, которые опреде­ляются в результате решения системы уравнений

U1 + V3  = 5

U2 + V1 = 8

U2+ V2 = 1                               (3.5)

U2+ V3 = 9

U3+ V1 = 3

U3+ V4 = 1

U4+ V1 = 0

 составленных по заполненным клеткам. Это неопределенная система, т.к. неизвестных на одно больше числа уравнений. Придадим одному из неизвестных определенное числовое значе­ние, например, U1= 0. Тогда остальные неизвестные находятся из системы (3.5): Получаем: U1= 0, U2 = 7, U3 = -1, U4 = -4,  V1 = 4, V2 =  -3 ,V3 = 5 ,V4 = 2

Теперь можно найти оценки свободных клеток: S11= C11 - (U1 + V1  ) =  4- (0+4) = 0   , S12=6, S14=4, S24=1, S32=6, S33=4, S42=7, S44=2.

Поскольку в табл. 2 свободных клеток с отрицательными оценками

нет, то опорный план является оптимальным. Итак,  получен  оптимальный

план:

 

	0	0	200	0
X*=	100	400	0	0
	150	0	0	150

 

 

 

3. Значение целевой функции - минимальные транспортные затраты -по оптимальному плану составляют:

fmin=   200·5 + 100·8 + 400·1 + 150·3 + 150·1 =2800 ден.ед.

 

4. Склад В1  недополучит   продукции  в размере 100 ед..