Транспортная задача по "Математике"

Задача:

 

Заводы некоторой автомобильной  фирмы расположены в городах  А, В и С. Основные центры распределения продукции сосредоточены в городах D и E. Объемы производства указанных трех заводов равняются 1000, 1300 и 1200 автомобилей ежеквартально. Величины квартального спроса в центрах распределения составляют 2300 и 1400 автомобилей соответственно. Стоимости перевозки автомобилей по железной дороге по каждому из возможных маршрутов приведены в табл. 5.1.

 

Таблица 5.1 - «Стоимость перевозки, руб./шт.»

Заводы	Города		V, производства
	D	E
A	80	215	1000
B	100	108	1300
C	102	68	1200
Спрос	2300	1400

 

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

a Определение переменных

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

aПроверка сбалансированности задачи

Проверим равенство суммарного производства ПК и суммарного спроса:

(1000+1300+1200) < (2300+1400), 3500 шт./кв.<3700 шт./кв. 

откуда следует вывод - задача несбалансированна, поскольку спрос на автомобили превышает объем их производства. Для установления баланса введем дополнительный фиктивный завод с ежеквартальным объемом производства 200 шт. (3700-3500 = 200). Фиктивные тарифы с^ф приравняем к нулю (т.к. перевозки в действительности производиться не будут).

aПостроение транспортной матрицы

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

 

Таблица 5.2 - «Транспортная матрица задачи»

Заводы	Города		V, производства
	D	E
A	80	215	1000
B	100	108	1300
C	102	68	1200
Фиктивный завод	0	0	200
Спрос	2300	1400

 

aЗадание целевой функции

Суммарные затраты в  рублях на ежеквартальную перевозку автомобилей определяются по формуле:

L(x) = 80x₁₁ + 215x₁₂ + 100x₂₁ + 108x₂₂ + 102x₃₁ + 68x₃₂ + 0x₄₁ + 0x₄₂ à min  (5.1)

aЗадание ограничений

x₁₁ + x₁₂ = 1000; 
x₂₁ + x₂₂ = 1300; 
x₃₁ + x₃₂ = 1200; 
x₄₁ + x₄₂ = 200;   [шт./квартал] 
x₁₁ + x₂₁ + x₃₁ + x₄₁ = 2300; 
x₁₂ + x₂₂ + x₃₂ + x₄₂ = 1400; 
x_ij≥0. 

Таблица 5.3 - «Нахождение минимальной стоимости»

Заводы	Города		V, производства
	D	E
A	80	215	1000
B	100	108	1300
C	102	68	1200
Фиктивный завод	0	0	200
Спрос	2300	1400

 

В город Е направляем 1200 единиц автомобилей с завода С, там не остается больше запасов, но спрос этого города еще не удовлетворен.

 

 

 

 

Таблица 5.4 - «Следующий шаг алгоритма»

Заводы	Города		V, производства
	D	E
A	80	215	1000
B	100	108	1300
C	102	68	0
Фиктивный завод	0	0	200
Спрос	2300	200

 

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

Удовлетворяем спрос города D, направив туда 1000 единиц продукции с завода A. На заводе А не остается больше запасов, значит его исключаем. Также спрос города D еще не удовлетворен.

 

Таблица 5.5 - «Следующий шаг алгоритма»

Заводы	Города		V, производства
	D	E
A	80	215	0
B	100	108	1300
C	102	68	0
Фиктивный завод	0	0	200
Спрос	1300	200

 

Опять ищем минимальное значение, которому соответствует завод B и город D в таблице 5.6. Удовлетворяем спрос города D, направив туда ещё 1300 единиц продукции с завода В. На заводе B не остается больше запасов, значит его исключаем. Также спрос города D удовлетворен – значит, его также исключаем.

 

Таблица 5.6 - «Следующий шаг алгоритма»

Заводы	Города		V, производства
	D	E
A	80	215	0
B	100	108	1300
C	102	68	0
Фиктивный завод	0	0	200
Спрос	1300	200

 

Как видно из таблицы 5.7 больше автомобилей не осталось, кроме фиктивного завода, но с него уже перевозки не делаются так как всё будет равняться 0.

 

Таблица 5.7 - «Следующий шаг  алгоритма»

Заводы	Города		V, производства
	D	E
A	80	215	0
B	100	108	0
C	102	68	0
Фиктивный завод	0	0	200
Спрос	0	200

 

 

Расчет целевой функции (5.1):

L(x) = 68 ∙ 1200 + 80 ∙ 1000 + 100 ∙ 1300 + 0 ∙ 200 = 291600 рублей.