Реферат: Определение рационального варианта размещения производственно-хозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжера

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

Затраты на приготовление аб, руб

мощность АБЗ		Приведенные затраты на приготов-е 1т аб АБЗ, располож-м в пункте, руб, Cp i + E*Kp i уд
т/час	тыс. т/год	1	2	3	4
10	18	484	489	495	481
25	45	423	428	435	420
50	90	405	410	416	401

Затраты на транспортировку 1т аб потребителям, С_ij , руб

Пункт размещения	Зона-потребитель
1	28,3	60,3		45,3	90,3
2	61,3	30,3		93,3	48,3
3	50,3	95,3		33,3	62,3
4	99,3	54,3		65,3	36,3

Математическая модель транспортной задачи:

m n

min z = SSC_ij * x_ij

i=1 j=1

Ограничения:

n

-Sx_ij = a_i i=1, ......, m

j=1

весь продукт a_i имеющийся у i-го поставщика должен быть вывезен потребителю.

m

-Sx_ij = b_j j=1, ......, n

i=1

спрос j-го потребителя должен быть полностью удовлетворен

- x_ij ³ 0 i=1, ...., m; j=1, ...., n

x_ij – объем перевозок от i-го поставщика j-му потребителю

Транспортная таблица:

Мощность АБЗ	Спрос зон-потребителей, тыс.т/год
тыс.т/год	B1 =50	B2 =60	B3 =45	B4 =70	Bф =135	Ui	Ki
433,3	440,3 < 465,3	449,3 < 450,3	437,3 < 495,3	0
X1 =90	50	40	0	5/9
433,3 < 471,3	440,3	449,3 < 503,3	437,3 < 458,3	0
X2 =90	60	30	0	6/9
433,3 < 466,3	440,3 < 511,3	449,3	437,3 < 478,3	0
X3 =90	45	45	0	½
433,3 < 500,3	440,3 < 455,3	449,3 < 466,3	437,3	0
X4 =90	70	20	0	7/9
Vj	433,3	440,3	449,3	437,3	0

Так как задача не сбалансирована, то определяем спрос фиктивного потребителя:

В_ф =Sа_i - S b_j = 360 – 225 = 135 тыс.т/год

В верхний правый угол клеток вносится суммарная величина приведенных затрат на приготовление и транспортировку 1т аб, С^p _i + E*K^p _i + C_ij

С помощью правила минимального элемента вносим в таблицу перевозки x_ij .

Проверяем план на вырожденность:

m + n - 1 = 8 = 8 (занятых клеток), следовательноплан является невырожденным.

Строим систему потенциалов поставщиков и потребителей. Для этого потенциал столбца или строки с наибольшим кол-вом занятых клеток приравниваем нулю, в данном случае это потенциал столбца B_ф , остальные потенциалы определяем исходя из условия оптимальности для занятых клеток(U_i + V_j = С^p _i + E*K^p _i + C_ij ).

Проверяем план на оптимальность:

· число занятых клеток не должно превышать величину m + n – 1

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