Постановка задачи.
Пусть имеется пять предприятий-изготовителей и одиннадцать потребителей одинаковой продукции. Известны производственные мощности изготовителей и потребности потребителей. Суммарные мощности предприятий больше потребности потребителей.
Производственные мощности изготовителя составляют Ai. Потребность потребителя продукции равна Bj.
На выпуск единицы продукции изготовитель i расходует Ri затрат.
Известны затраты на доставку единицы продукции из пункта i в пункт j – Cij.
Издержки транспорта значительны и должны быть включены в целевую функцию.
Требуется составить такой план производства и поставок, чтобы суммарные расходы на производство и транспортировку были минимальны.
Математическая формулировка задачи.
Удовлетворение всех потребностей:
Xij = Bj
Неотрицательность грузовых потоков:
Xij >= 0
Соблюдение ограничений мощности:
Xij
Целевая функция:
(Ri + Cij)*Xij -> min
От обычной транспортной задачи поставленная задача отличается тем, что показатель оптимальности складывается из двух составляющих. Однако, общие затраты на производство и транспортировку определяются простым суммированием.
Таким образом, поставленная задача является открытой транспортной задачей.
Исходные данные
Предприятие А1 А2 А3 А4 А5
Производственные мощности 135 160 140 175 165
Затраты на ед. продукции в рублях 119 93 81 70 62
Потребители В1 В2 В3 В4 В5 В6 В7 В8 В9 В10
Спрос потребителей 30 45 60 50 45 65 79 87 44 30
Матрица транспортных затрат, руб.
(получена на основе данных по сети)
Потребители B1 B2 B3 B4 B5 B6 B7 B8 B9 B10
Отправители Номера вершин 3 12 24 35 19 30 16 9 31 5
A1 2 41 34 45 64 41 46 31 38 41 18
A2 33 47 22 12 21 13 7 12 36 2 36
A3 26 35 14 7 33 1 5 16 24 10 24
A4 21 40 40 38 39 31 37 42 29 42 51
A5 13 21 16 19 47 13 19 18 10 24 19
Суммированием затрат на производство и транспортных затрат в каждой клетке матрицы получаем расчетную матрицу.
Расчетная матрица стоимостных затрат.
Потребители B1 B2 B3 B4 B5 B6 B7 B8 B9 B10
Отправи тели Ресурсы
A1 135 160 153 164 183 160 165 150 157 160 137
A2 160 140 115 105 114 106 100 105 129 95 129
A3 140 116 95 88 114 82 86 97 105 91 105
A4 175 110 110 108 109 101 106 112 99 112 121
A5 165 83 78 81 109 75 81 80 72 86 81
Так как транспортная задача открытая, то мощности превышают потребности. Часть поставщиков в оптимальном плане остается недозагруженной. Для решения задачи в матричной форме вводится фиктивный потребитель – дополнительный столбец с потребностью, равной избытку ресурсов над реальными потребностями.
Решение транспортной задачи.
Исходные данные.
Потребители B1 B2 B3 B4 B5 B6 B7 B8 B9 В10 В11
Отправи тели Ресурсы 30 45 60 50 45 65 79 87 44 30 240
A1 135 160 153 164 183 160 165 150 157 160 137 0
A2 160 140 115 105 114 106 100 105 129 95 129 0
A3 140 116 95 88 114 82 86 97 105 91 105 0
A4 175 110 110 108 109 101 106 112 99 112 121 0
A5 165 83 78 81 109 75 81 80 72 86 81 0
Итого775
Решение
Потребители B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11
Отправи тели Ресурсы 30 45 60 50 45 65 79 87 44 30 240
A1 135 160 153 164 183 160 165 150 157 160 137 0
135
A2 160 140 115 105 114 106 100 105 129 95 129 0
49 44 67
A3 140 116 95 88 114 82 86 97 105 91 105 0
45 65 30
A4 175 110 110 108 109 101 106 112 99 112 121 0
20 87 30 38
A5 165 83 78 81 109 75 81 80 72 86 81 0
30 45 60 30
Итого 775
Для подтверждения правильности решения оптимальный план, полученный в данной таблице проверяется методом потенциалов на соблюдение условий оптимальности .
Условие оптимальности выглядит следующим образом:
Vij – Uij
Vij – Uij = Cij , если Xij > 0
Для всех клеток матрицы разность потенциалов столбца и строки меньше или равна показателю оптимальности, для занятых клеток точно равна его значению.
Первый потенциал может быть присвоен любой строке или столбцу. В данном случае первый потенциал присвоен базисной клетке, где затраты на транспортировку максимальны (А4 – В10).
Проверка решения методом потенциалов.
Потребители B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11
Отправител Ресурсы 30 45 60 50 45 65 79 87 44 30 240
A1 135 160 153 164 183 160 165 150 157 160 137 0 150
135
A2 160 140 115 105 114 106 100 105 129 95 129 0 150
49 44 67
A3 140 116 95 88 114 82 86 97 105 91 105 0 158
45 65 30
A4 175 110 110 108 109 101 106 112 99 112 121 0 150
20 87 30 38
A5 165 83 78 81 109 75 81 80 72 86 81 0 150
30 45 60 30
233 228 231 259 240 244 255 249 245 271 150
Потребители B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11
Отправител Ресурсы 30 45 60 50 45 65 79 87 44 30 240
A1 135 50 48 62 74 64 65 45 51 50 35 0
135
A2 160 30 10 3 5 10 0 0 30 0 27 0
30 79 44 7
A3 140 20 4 0 19 0 0 6 20 10 17 20
60 45 35
A4 175 0 5 6 0 5 6 7 0 17 19 0
50 27 98
A5 165 0 0 0 27 0 2 2 0 18 0 27
30 45 60 30
Далее следует сравнить Целевую функцию в решении задачи (F1) и целевую функцию, полученную при решении потенциалов (F2), если F1 > F2, то план оптимален.
Потребители B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11
Отправите Ресурсы 30 45 60 50 45 65 79 87 44 30 240
A1 135 160 153 164 183 160 165 150 157 160 137 0
135
A2 160 140 115 105 114 106 100 105 129 95 129 0
49 44 67
A3 140 116 95 88 114 82 86 97 105 91 105 0
45 65 30
A4 175 110 110 108 109 101 106 112 99 112 121 0
20 87 30 38
A5 165 83 78 81 109 75 81 80 72 86 81 0
30 45 60 30
Цел. Ф-ия (F1) 2490 3510 4860 5450 3690 5590 8055 8613 4180 3630 0
Цел. Ф-ия (F1) 50068
Потребители B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11
Отправител Ресурсы 30 45 60 50 45 65 79 87 44 30 240
A1 135 160 153 164 183 160 165 150 157 160 137 0
135
A2 160 140 115 105 114 106 100 105 129 95 129 0
30 79 44 7
A3 140 116 95 88 114 82 86 97 105 91 105 0
60 45 35
A4 175 110 110 108 109 101 106 112 99 112 121 0
50 27 98
A5 165 83 78 81 109 75 81 80 72 86 81 0
30 45 60 30
Цел. Ф-ия (F2) 2490 3510 5280 5450 3690 6010 8295 6993 4180 2430 0
Цел. Ф-ия (F2) 48328
Т.к. 50068 > 48328 , то план оптимален, т.е. условие оптимальности соблюдается во всех клетках матрицы, следовательно задача решена правильно.
Вывод.
Разработанный оптимальный план обеспечивает минимальные затраты на производство и транспортировку продукции из пяти пунктов производства в десять пунктов потребления.
На основе решения транспортной задачи определены поставки каждого пункта производства в пункты потребления, производственные программы по заводам изготовителям и резервы производственных мощностей.
Резерв производственной мощности на заводе А1 составляет 135 единиц (поставки фиктивному потребителю), на заводе А2 – 7 единиц, на заводе А4 – 98 единиц, остальные предприятия резервов не имеют.
Минимальные затраты на транспортировку и производство составили 48328 рублей. Затраты на производство продукции в составе суммарных затрат определяются умножением затрат на производство единицы продукции на производственную программу и составят:
119*0+93*153+81*140+70*77+62*165= 14229+11340+5390+10230=41189 рублей или 85,2%.
Затраты на транспортировку составляют 7139 рублей или 14,8%. Такую долю транспортных затрат для готовой продукции следует считать довольно высокой, хотя по отдельным видам дешевых массовых грузов эта доля может быть значительно выше.
Межотраслевой баланс производства и распределения
продукции в народном хозяйстве за 1989 год млн.руб.)
Промыш- Электро- Сельское Прочие виды Всего пот- Конечный Всего рас-
Отрасли ленность энэргетика хозяйство деятельности реблено продукт пределено
2 3 4 5 1 8 710 6 9 11 12
2
Промыш- 3 252191,1 21954,7 45395,5 57176,5 376718,0 231120,7 607838,7
ленность 4
5
Электро- 1 18907,2 56932,4 9573,1 8649,8 94062,5 169808,9 263871,4
энергетика 8
Сельское 7 16942,2 143080,6 141310,1 5660,2 306993,1 141847,3 448840,4
хоз-во 10
Прочие 6
виды 9 63792,8 29752,1 24192,9 90138,8 207876,6 208720,2 416596,8
деят-ти 11
12
Все матер.затраты 351833,7 251719,8 220471,6 161625,3 985650,2 751497,1 1737147
Вся чист.прод-ия 256005,7 12151,6 228368,8 254971,5 751497,6
Вся продукция 607838,4 263871,4 448840,4 416597,1 1737147
Межотраслевой баланс составлен в денежном выражении и состоит из разделов.
В первом разделе отражаются межотраслевые потоки продукции в процессе текущего производственного потребления. Этот раздел имеет одинаковую классификацию, что обеспечивает его шахматную структуру. Второй раздел содержит конечный продукт. В третьем разделе показывается вновь созданная стоимость.
На основе данных отчетного межотраслевого баланса рассчитываются коэффициенты затрат делением величины межотраслевых поставок на валовую продукцию отрасли.
Расчет коэффициентов прямых затрат
Расчет коэффициентов прямых затрат
Промыш- Электро- Сельское Прочие виды
Отрасли ленность энэргетика хозяйство деятельности
2 3 4 5 1 8 710 6 9 11 12
2
Промыш- 3 0,4149 0,0832 0,1011 0,1372
ленность 4
5
Электро- 1 0,0311 0,2158 0,0213 0,0208
энергетика 8
Сельское 7 0,0279 0,5422 0,3148 0,0136
хоз-во 10
Прочие 6
виды 9 0,1050 0,1128 0,0539 0,2164
деят-ти 11
Конечный продукт
Конечный Рост кон. Конечный продукт
продукт продукции с учетом прироста
231120,7 24% 55468,968
263871,4 26% 68606,564
448840,4 28% 125675,312
416596,8 25% 104149,2
Х1 - промышленность
Х2 - электроэнергетика
Х3 – сельское хозяйство
Х4 – прочие виды деятельности
Система линейных уравнений
Х1 = 0,4149*Х1+0,0832*Х2+0,1011*Х3+0,1372*Х4+55468,968
Х2 = 0,0311*Х1+0,2158*Х2+0,0213*Х3+0,0208*Х4+68606,564
Х3 = 0,0279*Х1+0,5422*Х2+0,3148*Х3+0,0136*Х4+125675,312
Х4 = 0,1050*Х1+0,1128*Х2+0,0539*Х3+0,2164*Х4+104149,2
Система линейных уравнений решается методом подстановок.
РЕШЕНИЕ:
Х1 - 0,4149*Х1 - 0,0832*Х2 - 0,1011*Х3 - 0,1372*Х4 = 55468,968
Х2 - 0,0311*Х1 - 0,2158*Х2 - 0,0213*Х3 - 0,0208*Х4 = 68606,564
Х3 - 0,0279*Х1 - 0,5422*Х2 - 0,3148*Х3 - 0,0136*Х4 = 125675,312
Х4 - 0,1050*Х1 - 0,1128*Х2 - 0,0539*Х3 - 0,2164*Х4 = 104149,2
1) 0,5851*Х1 - 0,0832*Х2 - 0,1011*Х3 - 0,1372*Х4 = 55468,968
- 0,0311*Х1 + 0,7842*Х2 - 0,0213*Х3 - 0,0208*Х4 = 68606,564
- 0,0279*Х1 - 0,5422*Х2 + 0,6852*Х3 - 0,0136*Х4 = 125675,312
- 0,1050*Х1 - 0,1128*Х2 - 0,0539*Х3 + 0,7836*Х4 = 104149,2
0,0832*Х2 + 0,1011*Х3 + 0,1372*Х4 + 55468,968
Х1=
0,5851
-0,05316*(0,0832*Х2+0,1011*Х3+0,1372*Х4+55468,968)+0,7842*Х2-0,0213*Х3-0,0208*Х4 = 68606,564
-0,004423*Х2 - 0,005377*Х3 - 0,007296*Х4 - 2948,885 + 0,7842*Х2 - 0,0213*Х3-0,0208*Х4 = 68606,564
0,7798*Х2 - 0,0267*Х3 - 0,0281*Х4 = 71555,45
-0,04763*(0,0832*Х2+0,1011*Х3+0,1372*Х4+55468,968)-0,5422*Х2+0,6852*Х3-0,0136*Х4 = 125675,312
-0,003964*Х2 -0,004818*Х3 - 0,006538*Х4 - 2642,411 - 0,5422*Х2 + 0,6852*Х3-0,0136*Х4 = 125675,312
-0,5462*Х2 + 0,6803*Х3 - 0,0201*Х4 = 128317,723
-0,17937*(0,0832*Х2+0,1011*Х3+0,1372*Х4+55468,968)-0,1128*Х2-0,0539*Х3+0,7836*Х4 = 104149,2
-0,014924*Х2 - 0,018141*Х3 - 0,024618*Х4 - 9949,522 - 0,1128*Х2 - 0,0539*Х3+ 0,7836*Х4 = 104149,2
-0,1277*Х2 - 0,0720*Х3 + 0,7590*Х4=114098,7
2) 0,7798*Х2 - 0,0267*Х3 - 0,0281*Х4 = 71555,45
-0,5462*Х2 + 0,6803*Х3 - 0,0201*Х4 = 128317,723
-0,1277*Х2 - 0,0720*Х3 + 0,7590*Х4=114098,7
0,0267*Х3 + 0,0281*Х4 + 71555,45
Х2=
0,7798
-0,700436*(0,0267*Х3 + 0,0281*Х4 + 71555,45) + 0,6803*Х3 - 0,0201*Х4 = 128317,723
-0,018702*Х3 – 0,019682*Х4- 50120,01+ 0,6803*Х3 - 0,0201*Х4 = 128317,723
0,6616*Х3 – 0,0398*Х4 = 178437,7368
-0,16376*(0,0267*Х3 + 0,0281*Х4 + 71555,45) - 0,0720*Х3 + 0,7590*Х4=114098,7
-0,004372*Х3 – 0,004602*Х4 – 11717,92 - 0,0720*Х3 + 0,7590*Х4=114098,7
-0,0764*Х3 + 0,7544*Х4 = 125816,6161
3) 0,6616*Х3 – 0,0398*Х4 = 178437,7368
-0,0764*Х3 + 0,7544*Х4 = 125816,6161
0,0398*Х4 + 178437,7368
Х3=
0,6616
-0,115478*(0,0398*Х4 + 178437,7368) + 0,7544*Х4 = 125816,6161
-0,004596*Х4-20605,57 + 0,7544*Х4 = 125816,6161
0,7498*Х4 = 146422,1830
Х4 = 195280,6132
0,0398*195280,6132 + 178437,7368
Х3=
0,6616
Х3 = 281453,9075
0,0267*281453,9075 + 0,0281*195280,6132 + 71555,45
Х2=
0,7798
Х2 = 108435,0533
0,0832*108435,0533 + 0,1011*281453,9075 + 0,1372*195280,6132 + 55468,968
Х1=
0,5851
Х1 = 204645,795
Результаты расчетов:
Х1 = 204645,7949 - промышленность
Х2 = 108435,0533 - электроэнергетика
Х3 = 281453,9075 – сельское хозяйство
Х4 = 195280,6132 – прочие виды деят-ти
Проверка:
Х1 = 0,4149*Х1+0,0832*Х2+0,1011*Х3+0,1372*Х4+55468,968
Х2 = 0,0311*Х1+0,2158*Х2+0,0213*Х3+0,0208*Х4+68606,564
Х3 = 0,0279*Х1+0,5422*Х2+0,3148*Х3+0,0136*Х4+125675,312
Х4 = 0,1050*Х1+0,1128*Х2+0,0539*Х3+0,2164*Х4+104149,2
Х1 = 84907,1860 + 9022,0428 + 28466,1114 + 26801,5835 + 55468,968
204645,7949=204645,7949
Х2 = 6365,6375 + 23395,7444 + 6002,9943 + 4054,6087 + 68606,564
108435,0533= 108435,0533
Х3 = 5704,0654 + 58797,4008 + 88611,1852 + 2653,2285 + 125675,312
281453,9075 = 281453,9075
Х4 = 1477,6300 + 12226,2986 +15170,6179 + 42252,71884 + 104149,2
195280,6132 = 195280,6132
По результатам решения составляется плановый межотраслевой баланс, в который сначала заносятся сведения о валовой продукции отраслей по строке “Валовая продукция” и сведения о конечном продукте в отраслях. Межотраслевые связи рассчитываются умножением величины валового продукта по отрасли на коэффициенты прямых затрат. Например, чтобы рассчитать размер промежуточного продукта промышленности для сельского хозяйства нужно валовую продукцию промышленности по плану умножить на соответствующий коэффициент прямых затрат. Чистая продукция определяется как разница валовой продукции и суммы промежуточных затрат.
Плановый межотраслевой баланс
Плановый межотраслевой баланс
Промыш- Электро- Сельское Прочие виды Всего пот- Конечный Валовая
Отрасли ленность энэргетик хозяйство деятельности реблено продукт продукция
2 3 4 5 1 8 7 10 6 9 11 12
2
Промыш- 3 84907,2 9022,0428 28466,1115 26801,6 149196,9 55468,97 204645,79
ленность 4
5
Электро- 1 6365,6 23395,7 6003,0 4054,6 39819,0 68606,56 108435,05
энергетика 8
Сельское 7 5704,1 58797,4 88611,2 2653,2 155765,9 125675,3 281453,91
хоз-во 10
Прочие 6
виды 9 21477,6 12226,3 15170,6 42252,7 91127,3 104149,2 195280,61
деят-ти 11
12
Все матер.затраты 118454,5 103441,5 138250,9 75762,1 435909,1 353900 789815,4
Чистый доход 86191,3 4993,6 143203,0 119518,5 353906,3
Валовая продукция 204645,79 108435,053 281453,908 195280,61 789815,4 Итого
Далее необходимо рассчитать коэффициенты полных затрат, для этого преобразуем формулу Х = аij*Xj + Yi следующим образом:
X – aij*Xj = Yi, полагая, что Xj = E*Xj
E*Xj – aij*Xj = Yi
X*(E – a) = Yi
X = (E – a) * Yi
Выражение (E – a) представляет из себя обратную матрицу.
1-а11 0-а12 … 0-а1n
E – a = … … … …
0-am1 0-am2 … 1-amn
0,5851 -0,0832 -0,1011 -0,1372
Е - а = -0,0311 0,7842 -0,0213 -0,0208
-0,0279 -0,5422 0,6852 -0,0136
-0,1050 -0,1128 -0,0539 0,7836
Решение системы связано с матрицей (Е – а), обозначим (Е – а) =А
А11 А12 … А1n
А = … … … …
Аm1 Аm2 … Аmn
Величины А – есть коэффициенты полных затрат.
1,81 0,452175 0,307179 0,3339
0,08 1,331012 0,057618 0,0507
0,14 1,078218 1,520649 0,0802
0,26 0,326235 0,154026 1,3336
X = A*Y
1,8076696 0,452174849 0,307179212 0,33390524 55468,97 204672,54
Х = 0,0826051 1,331012318 0,057617708 0,05073294 * 68606,56 = 108423,12
0,144143 1,078218311 1,520648538 0,08017912 125675,3 281426,89
0,2638982 0,326234601 0,154025841 1,33364524 104149,2 195275,33
Х1(А) = 204672,5352
Х2(А) = 108423,1202
Х3(А) = 281426,8885
Х4(А) = 195275,3261
Коэффициенты полных материальных затрат показывают сколько всего нужно произвести продукции i-той отрасли для выпуска в сферу конечного использования единицы продукции j-той отрасли.
Плановый межотраслевой баланс
с учетом полных затрат
Промыш- Электро- Сельское Прочие виды Всего пот- Конечный Валовая
Отрасли ленность энэргетика хозяйство деятельности реблено продукт продукция
2 3 4 5 1 8 7 10 6 9 11 12
2
Промыш 3 84918,3 9021,04994 28463,379 26800,9 149203,6 55468,97 204672,54
ленность 4
5
Электро- 1 6366,5 23393,2 6002,4 4054,5 39816,6 68606,56 108423,12
энергетика 8
Сельское 7 5704,8 58790,9 88602,7 2653,2 155751,6 125675,3 281426,89
хоз-во 10
Прочие 6
виды 9 21480,4 12225,0 15169,2 42251,6 91126,1 104149,2 195275,33
деят-ти 11
12
Все матер.затраты 118470,0 103430,1 138237,6 75760,1 435897,8 353900 789797,9
Чистый доход 86202,5 4993,0 143189,3 119515,2 353900,0
Валовая продукция 204672,54 108423,12 281426,89 195275,33 789797,9 Итого
Разработанный межотраслевой баланс определяет совокупный валовый продукт на плановый период, показывает межотраслевые связи и объемы промежуточного продукта, производимого каждой отраслью. По сравнению с отчетным балансом плановый баланс обеспечивает минимальный прирост валовой продукции, кроме отрасли промышленности, где прирост составляет 1%. Все данные показаны в таблице:
коэффициент коэффициент РАЗНИЦА
прямых затрат полных затрат
Х1 (а) 204645,795 Х1 (А) 204672,535 -26,740
Х2 (а) 108435,053 Х2 (А) 108423,12 11,933
Х3 (а) 281453,908 Х3 (А) 281426,889 27,019
Х4 (а) 195280,61 Х4 (А) 195275,326 5,287
Т.е. прирост конечной продукции в сельскохозяйственной деятельности на 0,63%, обеспечивается приростом валовой продукции, прирост сельскохозяйственной деятельности обеспечивается на 0,41%. Для увеличения конечного продукта в сфере промышленности необходимо увеличить прирост валового продукта на 0,34% , а прирост конечного продукта в прочих отраслях на 0,49% обеспечивается приростом валового продукта этих отраслей.