This example examines the effect of changing some of the arc costs. The backorder penalty costs are increased by 20 percent. The sales profit of 25-inch TVs sent to the shops in May is increased by 30 units. The backorder penalty costs of 25-inch TVs manufactured in May for April consumption is decreased by 30 units. The production cost of 19-inch and 25-inch TVs made in May are decreased by 5 units and 20 units, respectively. How does the optimal solution of the network after these arc cost alterations compare with the optimum of the original network?
These SAS statements produce the new NODEDATA= and ARCDATA= data sets:
title2 'Minimum Cost Flow problem- Altered Arc Data'; data arc2; set arc1; oldcost=_cost_; oldfc=_fcost_; oldflow=_flow_; if key_id='backorder' then _cost_=_cost_*1.2; else if _tail_='f2_may_2' then _cost_=_cost_-30; if key_id='production' & mth_made='May' then if diagonal=19 then _cost_=_cost_-5; else _cost_=_cost_-20; run;
proc intpoint bytes=100000 printlevel2=2 nodedata=node0 arcdata=arc2 conout=arc3; run;
proc print data=arc3; var _tail_ _head_ _capac_ _lo_ _supply_ _demand_ _name_ _cost_ _flow_ _fcost_ oldcost oldflow oldfc diagonal factory key_id mth_made; /* to get this variable order */ sum oldfc _fcost_; run;
The following notes appear on the SAS log:
NOTE: Number of nodes= 20 . |
NOTE: Number of supply nodes= 4 . |
NOTE: Number of demand nodes= 4 . |
NOTE: Total supply= 4350 , total demand= 4150 . |
NOTE: Number of arcs= 64 . |
NOTE: The following messages relate to the equivalent Linear Programming problem |
solved by the Interior Point algorithm. |
NOTE: Number of <= constraints= 0 . |
NOTE: Number of == constraints= 21 . |
NOTE: Number of >= constraints= 0 . |
NOTE: Number of constraint coefficients= 136 . |
NOTE: Number of variables= 68 . |
NOTE: After preprocessing, number of <= constraints= 0. |
NOTE: After preprocessing, number of == constraints= 20. |
NOTE: After preprocessing, number of >= constraints= 0. |
NOTE: The preprocessor eliminated 1 constraints from the problem. |
NOTE: The preprocessor eliminated 9 constraint coefficients from the problem. |
NOTE: 0 columns, 0 rows and 0 coefficients were added to the problem to handle |
unrestricted variables, variables that are split, and constraint slack or |
surplus variables. |
NOTE: There are 48 sub-diagonal nonzeroes in the unfactored A Atranspose matrix. |
NOTE: The 20 factor nodes make up 8 supernodes |
NOTE: There are 27 nonzero sub-rows or sub-columns outside the supernodal triangular |
regions along the factors leading diagonal. |
Iter Complem_aff Complem-ity Duality_gap Tot_infeasb Tot_infeasc Tot_infeasd |
0 -1.000000 193775969 0.894415 66024 25664 0 |
1 37797544 24594220 0.918149 4566.893212 1775.179450 0 |
2 4408681 1844606 0.590964 0 0 0 |
3 347168 312126 0.194113 0 0 0 |
4 145523 86002 0.060330 0 0 0 |
5 43008 38240 0.027353 0 0 0 |
6 31097 21145 0.015282 0 0 0 |
7 9308.807034 4158.399675 0.003029 0 0 0 |
8 1710.832075 752.174595 0.000549 0 0 0 |
9 254.197112 47.755299 0.000034846 0 0 0 |
10 5.252560 0.010692 7.8017564E-9 0 0 0 |
NOTE: The Primal-Dual Predictor-Corrector Interior Point algorithm performed 10 |
iterations. |
NOTE: Optimum reached. |
NOTE: Objective= -1285086.442. |
NOTE: The data set WORK.ARC3 has 64 observations and 17 variables. |
NOTE: There were 64 observations read from the data set WORK.ARC2. |
NOTE: There were 8 observations read from the data set WORK.NODE0. |
The solution is displayed in Output 4.2.1.
Output 4.2.1: CONOUT=ARC3
Minimum Cost Flow Problem- Altered Arc Data |
_tail_ | _head_ | _capac_ | _lo_ | _SUPPLY_ | _DEMAND_ | _name_ | _cost_ | _FLOW_ |
---|---|---|---|---|---|---|---|---|
fact1_1 | f1_apr_1 | 600 | 50 | 1000 | . | prod f1 19 apl | 78.60 | 540.000 |
f1_mar_1 | f1_apr_1 | 50 | 0 | . | . | 15.00 | 0.000 | |
f1_may_1 | f1_apr_1 | 20 | 0 | . | . | back f1 19 may | 33.60 | 0.000 |
f2_apr_1 | f1_apr_1 | 40 | 0 | . | . | 11.00 | 0.000 | |
fact1_2 | f1_apr_2 | 550 | 50 | 1000 | . | prod f1 25 apl | 174.50 | 250.000 |
f1_mar_2 | f1_apr_2 | 40 | 0 | . | . | 20.00 | 0.000 | |
f1_may_2 | f1_apr_2 | 15 | 0 | . | . | back f1 25 may | 49.20 | 15.000 |
f2_apr_2 | f1_apr_2 | 25 | 0 | . | . | 21.00 | 0.000 | |
fact1_1 | f1_mar_1 | 500 | 50 | 1000 | . | prod f1 19 mar | 127.90 | 340.000 |
f1_apr_1 | f1_mar_1 | 20 | 0 | . | . | back f1 19 apl | 33.60 | 20.000 |
f2_mar_1 | f1_mar_1 | 40 | 0 | . | . | 10.00 | 40.000 | |
fact1_2 | f1_mar_2 | 400 | 40 | 1000 | . | prod f1 25 mar | 217.90 | 400.000 |
f1_apr_2 | f1_mar_2 | 30 | 0 | . | . | back f1 25 apl | 38.40 | 30.000 |
f2_mar_2 | f1_mar_2 | 25 | 0 | . | . | 20.00 | 25.000 | |
fact1_1 | f1_may_1 | 400 | 50 | 1000 | . | 90.10 | 115.000 | |
f1_apr_1 | f1_may_1 | 50 | 0 | . | . | 12.00 | 0.000 | |
f2_may_1 | f1_may_1 | 40 | 0 | . | . | 13.00 | 0.000 | |
fact1_2 | f1_may_2 | 350 | 40 | 1000 | . | 113.30 | 350.000 | |
f1_apr_2 | f1_may_2 | 40 | 0 | . | . | 18.00 | 0.000 | |
f2_may_2 | f1_may_2 | 25 | 0 | . | . | 13.00 | 0.000 | |
f1_apr_1 | f2_apr_1 | 99999999 | 0 | . | . | 11.00 | 20.000 | |
fact2_1 | f2_apr_1 | 480 | 35 | 850 | . | prod f2 19 apl | 62.40 | 480.000 |
f2_mar_1 | f2_apr_1 | 30 | 0 | . | . | 18.00 | 0.000 | |
f2_may_1 | f2_apr_1 | 15 | 0 | . | . | back f2 19 may | 30.00 | 0.000 |
f1_apr_2 | f2_apr_2 | 99999999 | 0 | . | . | 23.00 | 0.000 | |
fact2_2 | f2_apr_2 | 680 | 35 | 1500 | . | prod f2 25 apl | 196.70 | 680.000 |
f2_mar_2 | f2_apr_2 | 50 | 0 | . | . | 28.00 | 0.000 | |
f2_may_2 | f2_apr_2 | 15 | 0 | . | . | back f2 25 may | 64.80 | 0.000 |
f1_mar_1 | f2_mar_1 | 99999999 | 0 | . | . | 11.00 | 0.000 | |
fact2_1 | f2_mar_1 | 450 | 35 | 850 | . | prod f2 19 mar | 88.00 | 290.000 |
f2_apr_1 | f2_mar_1 | 15 | 0 | . | . | back f2 19 apl | 20.40 | 0.000 |
f1_mar_2 | f2_mar_2 | 99999999 | 0 | . | . | 23.00 | 0.000 | |
fact2_2 | f2_mar_2 | 650 | 35 | 1500 | . | prod f2 25 mar | 182.00 | 635.000 |
f2_apr_2 | f2_mar_2 | 15 | 0 | . | . | back f2 25 apl | 37.20 | 0.000 |
f1_may_1 | f2_may_1 | 99999999 | 0 | . | . | 16.00 | 115.000 | |
fact2_1 | f2_may_1 | 250 | 35 | 850 | . | 128.80 | 35.000 | |
f2_apr_1 | f2_may_1 | 30 | 0 | . | . | 20.00 | 0.000 | |
f1_may_2 | f2_may_2 | 99999999 | 0 | . | . | 26.00 | 335.000 | |
fact2_2 | f2_may_2 | 550 | 35 | 1500 | . | 181.40 | 35.000 | |
f2_apr_2 | f2_may_2 | 50 | 0 | . | . | 38.00 | 0.000 | |
f1_mar_1 | shop1_1 | 250 | 0 | . | 900 | -327.65 | 150.000 | |
f1_apr_1 | shop1_1 | 250 | 0 | . | 900 | -300.00 | 250.000 | |
f1_may_1 | shop1_1 | 250 | 0 | . | 900 | -285.00 | 0.000 | |
f2_mar_1 | shop1_1 | 250 | 0 | . | 900 | -297.40 | 250.000 | |
f2_apr_1 | shop1_1 | 250 | 0 | . | 900 | -290.00 | 250.000 | |
f2_may_1 | shop1_1 | 250 | 0 | . | 900 | -292.00 | 0.000 | |
f1_mar_2 | shop1_2 | 99999999 | 0 | . | 900 | -559.76 | 0.000 | |
f1_apr_2 | shop1_2 | 99999999 | 0 | . | 900 | -524.28 | 0.000 | |
f1_may_2 | shop1_2 | 99999999 | 0 | . | 900 | -475.02 | 0.000 | |
f2_mar_2 | shop1_2 | 500 | 0 | . | 900 | -567.83 | 500.000 | |
f2_apr_2 | shop1_2 | 500 | 0 | . | 900 | -542.19 | 400.000 | |
f2_may_2 | shop1_2 | 500 | 0 | . | 900 | -491.56 | 0.000 | |
f1_mar_1 | shop2_1 | 250 | 0 | . | 900 | -362.74 | 250.000 | |
f1_apr_1 | shop2_1 | 250 | 0 | . | 900 | -300.00 | 250.000 | |
f1_may_1 | shop2_1 | 250 | 0 | . | 900 | -245.00 | 0.000 | |
f2_mar_1 | shop2_1 | 250 | 0 | . | 900 | -272.70 | 0.000 | |
f2_apr_1 | shop2_1 | 250 | 0 | . | 900 | -312.00 | 250.000 | |
f2_may_1 | shop2_1 | 250 | 0 | . | 900 | -299.00 | 150.000 | |
f1_mar_2 | shop2_2 | 99999999 | 0 | . | 1450 | -623.89 | 455.000 | |
f1_apr_2 | shop2_2 | 99999999 | 0 | . | 1450 | -549.68 | 235.000 | |
f1_may_2 | shop2_2 | 99999999 | 0 | . | 1450 | -460.00 | 0.000 | |
f2_mar_2 | shop2_2 | 500 | 0 | . | 1450 | -542.83 | 110.000 | |
f2_apr_2 | shop2_2 | 500 | 0 | . | 1450 | -559.19 | 280.000 | |
f2_may_2 | shop2_2 | 500 | 0 | . | 1450 | -519.06 | 370.000 |
Minimum Cost Flow Problem- Altered Arc Data |
Obs | _FCOST_ | oldcost | oldflow | oldfc | diagonal | factory | key_id | mth_made |
---|---|---|---|---|---|---|---|---|
1 | 42444.01 | 78.60 | 600.000 | 47160.00 | 19 | 1 | production | April |
2 | 0.00 | 15.00 | 0.000 | 0.00 | 19 | 1 | storage | March |
3 | 0.00 | 28.00 | 0.000 | 0.00 | 19 | 1 | backorder | May |
4 | 0.00 | 11.00 | 0.000 | 0.00 | 19 | . | f2_to_1 | April |
5 | 43625.00 | 174.50 | 550.000 | 95975.00 | 25 | 1 | production | April |
6 | 0.00 | 20.00 | 0.000 | 0.00 | 25 | 1 | storage | March |
7 | 738.00 | 41.00 | 15.000 | 615.00 | 25 | 1 | backorder | May |
8 | 0.00 | 21.00 | 0.000 | 0.00 | 25 | . | f2_to_1 | April |
9 | 43486.02 | 127.90 | 344.999 | 44125.43 | 19 | 1 | production | March |
10 | 672.00 | 28.00 | 20.000 | 560.00 | 19 | 1 | backorder | April |
11 | 400.00 | 10.00 | 40.000 | 400.00 | 19 | . | f2_to_1 | March |
12 | 87160.00 | 217.90 | 400.000 | 87160.00 | 25 | 1 | production | March |
13 | 1152.00 | 32.00 | 30.000 | 960.00 | 25 | 1 | backorder | April |
14 | 500.00 | 20.00 | 25.000 | 500.00 | 25 | . | f2_to_1 | March |
15 | 10361.47 | 95.10 | 50.001 | 4755.06 | 19 | 1 | production | May |
16 | 0.00 | 12.00 | 50.000 | 600.00 | 19 | 1 | storage | April |
17 | 0.00 | 13.00 | 0.000 | 0.00 | 19 | . | f2_to_1 | May |
18 | 39655.00 | 133.30 | 40.000 | 5332.04 | 25 | 1 | production | May |
19 | 0.00 | 18.00 | 0.000 | 0.00 | 25 | 1 | storage | April |
20 | 0.00 | 43.00 | 0.000 | 0.00 | 25 | . | f2_to_1 | May |
21 | 220.00 | 11.00 | 30.000 | 330.00 | 19 | . | f1_to_2 | April |
22 | 29952.00 | 62.40 | 480.000 | 29952.00 | 19 | 2 | production | April |
23 | 0.00 | 18.00 | 0.000 | 0.00 | 19 | 2 | storage | March |
24 | 0.00 | 25.00 | 0.000 | 0.00 | 19 | 2 | backorder | May |
25 | 0.00 | 23.00 | 0.000 | 0.00 | 25 | . | f1_to_2 | April |
26 | 133755.99 | 196.70 | 680.000 | 133755.99 | 25 | 2 | production | April |
27 | 0.00 | 28.00 | 0.000 | 0.00 | 25 | 2 | storage | March |
28 | 0.00 | 54.00 | 15.000 | 810.00 | 25 | 2 | backorder | May |
29 | 0.00 | 11.00 | 0.000 | 0.00 | 19 | . | f1_to_2 | March |
30 | 25520.00 | 88.00 | 290.000 | 25520.00 | 19 | 2 | production | March |
31 | 0.00 | 17.00 | 0.000 | 0.00 | 19 | 2 | backorder | April |
32 | 0.00 | 23.00 | 0.000 | 0.00 | 25 | . | f1_to_2 | March |
33 | 115570.01 | 182.00 | 645.000 | 117389.96 | 25 | 2 | production | March |
34 | 0.00 | 31.00 | 0.000 | 0.00 | 25 | 2 | backorder | April |
35 | 1840.00 | 16.00 | 100.000 | 1600.01 | 19 | . | f1_to_2 | May |
36 | 4508.00 | 133.80 | 35.000 | 4683.00 | 19 | 2 | production | May |
37 | 0.00 | 20.00 | 15.000 | 299.99 | 19 | 2 | storage | April |
38 | 8710.00 | 26.00 | 0.000 | 0.00 | 25 | . | f1_to_2 | May |
39 | 6349.00 | 201.40 | 35.000 | 7049.00 | 25 | 2 | production | May |
40 | 0.00 | 38.00 | 0.000 | 0.00 | 25 | 2 | storage | April |
41 | -49147.54 | -327.65 | 154.999 | -50785.56 | 19 | 1 | sales | March |
42 | -75000.00 | -300.00 | 250.000 | -75000.00 | 19 | 1 | sales | April |
43 | -0.01 | -285.00 | 0.000 | 0.00 | 19 | 1 | sales | May |
44 | -74350.00 | -297.40 | 250.000 | -74349.99 | 19 | 2 | sales | March |
45 | -72499.96 | -290.00 | 245.001 | -71050.17 | 19 | 2 | sales | April |
46 | 0.00 | -292.00 | 0.000 | 0.00 | 19 | 2 | sales | May |
47 | 0.00 | -559.76 | 0.000 | 0.00 | 25 | 1 | sales | March |
48 | -0.01 | -524.28 | 0.000 | -0.01 | 25 | 1 | sales | April |
49 | -0.06 | -475.02 | 25.000 | -11875.64 | 25 | 1 | sales | May |
50 | -283915.00 | -567.83 | 500.000 | -283915.00 | 25 | 2 | sales | March |
51 | -216875.92 | -542.19 | 375.000 | -203321.08 | 25 | 2 | sales | April |
52 | 0.00 | -461.56 | 0.000 | 0.00 | 25 | 2 | sales | May |
53 | -90685.00 | -362.74 | 250.000 | -90685.00 | 19 | 1 | sales | March |
54 | -75000.00 | -300.00 | 250.000 | -75000.00 | 19 | 1 | sales | April |
55 | 0.00 | -245.00 | 0.000 | 0.00 | 19 | 1 | sales | May |
56 | -0.01 | -272.70 | 0.000 | 0.00 | 19 | 2 | sales | March |
57 | -78000.00 | -312.00 | 250.000 | -78000.00 | 19 | 2 | sales | April |
58 | -44849.99 | -299.00 | 150.000 | -44850.00 | 19 | 2 | sales | May |
59 | -283869.94 | -623.89 | 455.000 | -283869.94 | 25 | 1 | sales | March |
60 | -129174.80 | -549.68 | 535.000 | -294078.78 | 25 | 1 | sales | April |
61 | 0.00 | -460.00 | 0.000 | 0.00 | 25 | 1 | sales | May |
62 | -59711.32 | -542.83 | 120.000 | -65139.47 | 25 | 2 | sales | March |
63 | -156573.27 | -559.19 | 320.000 | -178940.96 | 25 | 2 | sales | April |
64 | -192052.13 | -489.06 | 20.000 | -9781.20 | 25 | 2 | sales | May |
-1285086.44 | -1281110.34 |