Задача 2 Условие: Готовая продукция заводов a I (i=1-3) направляется на склады b j (j=l-4). Заводы a

Математическое программирование и исследование операций в экономике - решение задач, контрольных и курсовых работ.

Задача 2

Условие:

Готовая продукция заводов a_i (i=1-3) направляется на склады B_j (j=l-4). Заводы a_i производят а_i, тыс. изделий. Пропускная способность складов B_j за это время характеризуется величинами b_j, тыс. изделий. Стоимость перевозки с завода a_i, на склад B_j одной тысячи изделий равна С_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. 
   найти величину f_min минимальных транспортных затрат;
   
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 • X₁₁ + 3• X₁₂ +...+ 1•X₃₄ (min) (3.1)

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

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

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

X₁₁ + X₁₂ + X₁₃+ X₁₄  200

X₂₁ + X₂₂ + X₂₃ + X₂₄  500 (3.2)

X₃₁ + X₃₂+ X₃₃ + X₃₄  300

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

X₁₁ + X₂₁ + X₃₁ = 350

X₁₂ + X₂₂ + X₃₂ = 400

X₁₃ + X₂₃+ X₃₃ = 200

X₁₄ + X₂₄+ X₃₄ = 150 (3.3)

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

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

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

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

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

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

Однако по условиям задачи необходимо найти оптимальный план задачи при дополнительном условии, что склад В₃ должен быть загружен полностью. Это ограничение будет соблюде­но в том случае, если в заключительной таблице с оптимальным планом клетки (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

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

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

U₁ + V₃ = 5

U₂ + V₁ = 8

U₂+ V₂ = 1 (3.5)

U₂+ V₃ = 9

U₃+ V₁ = 3

U₃+ V₄ = 1

U₄+ V₁ = 0

составленных по заполненным клеткам. Это неопределенная система, т.к. неизвестных на одно больше числа уравнений. Придадим одному из неизвестных определенное числовое значе­ние, например, U₁= 0. Тогда остальные неизвестные находятся из системы (3.5): Получаем: U₁= 0, U₂ = 7, U₃ = -1, U₄ = -4, V₁ = 4, V₂ = -3 ,V₃ = 5 ,V₄ = 2

Теперь можно найти оценки свободных клеток: S₁₁= C₁₁ - (U₁ + V₁ ) = 4- (0+4) = 0 , S₁₂=6, S₁₄=4, S₂₄=1, S₃₂=6, S₃₃=4, S₄₂=7, S₄₄=2.

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

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

план:

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

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

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

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

Помощь на экзамене, зачете, тесте.