Определение рационального варианта размещения производственно-хозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжераРефераты >> Математика >> Определение рационального варианта размещения производственно-хозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжера
Затраты на транспортировку 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 = S S Cij * xij
i=1 j=1
Ограничения:
n
n S xij = ai i=1, , m
j=1
весь продукт ai имеющийся у i-го поставщика должен быть вывезен потребителю.
m
n S xij = bj j=1, , n
i=1
спрос j-го потребителя должен быть полностью удовлетворен
n xij ³ 0 i=1, , m; j=1, , n
xij – объем перевозок от 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 bj = 360 – 225 = 135 тыс.т/год
В верхний правый угол клеток вносится суммарная величина приведенных затрат на приготовление и транспортировку 1т аб, Сpi + E*Kpi + Cij
С помощью правила минимального элемента вносим в таблицу перевозки xij.
Проверяем план на вырожденность:
m + n - 1 = 8 = 8 (занятых клеток), следовательно план является невырожденным.
Строим систему потенциалов поставщиков и потребителей. Для этого потенциал столбца или строки с наибольшим кол-вом занятых клеток приравниваем нулю, в данном случае это потенциал столбца Bф, остальные потенциалы определяем исходя из условия оптимальности для занятых клеток (Ui + Vj = Сpi + E*Kpi + Cij).
Проверяем план на оптимальность:
· число занятых клеток не должно превышать величину m + n – 1
· для каждой занятой клетки сумма потенциалов должна равняться суммарной величине затрат на приготовление и транспортировку 1т аб.
· для каждой свободной клетки должно выполняться неравенство :
Ui + Vj < Сpi + E*Kpi + Cij
Все три условия выполняются, следовательно план является оптимальным с точки зрения транспортной задачи.
Определяем значения коэффициентов интенсивности.
Ki = S xij / xi
S xij – cуммарный объем поставок i-го АБЗ реальным потребителям
xi – мощность i-го АБЗ
Так как ни один Ki не равен нулю или единице, то рассматриваемый вариант размещения АБЗ соответствующей мощности не есть наилучший, поэтому необходимо его улучшить.