 |
|
| The INTPOINT Procedure |
Example 4.5 Nonarc Variables in the Side Constraints
You can verify that the FACT2 MAR GIZMO constraint has a left-hand-side activity of 3,470, which is not equal to the _RHS_ of this constraint. Not all of the 3,750 chips that can be supplied to factory 2 for March production are used. It is suggested that all the possible chips be obtained in March and those not used be saved for April production. Because chips must be kept in an air-controlled environment, it costs one dollar to store each chip purchased in March until April. The maximum number of chips that can be stored in this environment at each factory is 150. In addition, a search of the parts inventory at factory 1 turned up 15 chips available for their March production.
Nonarc variables are used in the side constraints that handle the limitations of supply of Gizmo chips. A nonarc variable called f1 unused chips has as a value the number of chips that are not used at factory 1 in March. Another nonarc variable, f2 unused chips, has as a value the number of chips that are not used at factory 2 in March. f1 chips from mar has as a value the number of chips left over from March used for production at factory 1 in April. Similarly, f2 chips from mar has as a value the number of chips left over from March used for April production at factory 2 in April. The last two nonarc variables have objective function coefficients of 1 and upper bounds of 150. The Gizmo side constraints are
3*prod f1 19 mar + 4*prod f1 25 mar + f1 unused chips = 2615 3*prod f2 19 apl + 4*prod f2 25 apl + f2 unused chips = 3750 3*prod f1 19 apl + 4*prod f1 25 apl - f1 chips from mar = 2600 3*prod f2 19 apl + 4*prod f2 25 apl - f2 chips from mar = 3750 f1 unused chips + f2 unused chips - f1 chips from mar - f2 chips from mar >= 0
The last side constraint states that the number of chips not used in March is not less than the number of chips left over from March and used in April. Here, this constraint is called CHIP LEFTOVER.
The following SAS code creates a new data set containing constraint data. It seems that most of the constraints are now equalities, so you specify DEFCONTYPE=EQ in the PROC INTPOINT statement from now on and provide constraint type data for constraints that are not "equal to" type, using the default TYPEOBS value _TYPE_ as the _COLUMN_ variable value to indicate observations that contain constraint type data. Also, from now on, the default RHSOBS value is used.
title2 'Nonarc Variables in the Side Constraints'; data con6; input _column_ &$17. _row_ &$15. _coef_ ; datalines; prod f1 19 mar FACT1 MAR GIZMO 3 prod f1 25 mar FACT1 MAR GIZMO 4 f1 unused chips FACT1 MAR GIZMO 1 _RHS_ FACT1 MAR GIZMO 2615 prod f2 19 mar FACT2 MAR GIZMO 3 prod f2 25 mar FACT2 MAR GIZMO 4 f2 unused chips FACT2 MAR GIZMO 1 _RHS_ FACT2 MAR GIZMO 3750 prod f1 19 apl FACT1 APL GIZMO 3 prod f1 25 apl FACT1 APL GIZMO 4 f1 chips from mar FACT1 APL GIZMO -1 _RHS_ FACT1 APL GIZMO 2600 prod f2 19 apl FACT2 APL GIZMO 3 prod f2 25 apl FACT2 APL GIZMO 4 f2 chips from mar FACT2 APL GIZMO -1 _RHS_ FACT2 APL GIZMO 3750 f1 unused chips CHIP LEFTOVER 1 f2 unused chips CHIP LEFTOVER 1 f1 chips from mar CHIP LEFTOVER -1 f2 chips from mar CHIP LEFTOVER -1 _TYPE_ CHIP LEFTOVER 1 back f1 19 apl TOTAL BACKORDER 1 back f1 25 apl TOTAL BACKORDER 1 back f2 19 apl TOTAL BACKORDER 1 back f2 25 apl TOTAL BACKORDER 1 back f1 19 may TOTAL BACKORDER 1 back f1 25 may TOTAL BACKORDER 1 back f2 19 may TOTAL BACKORDER 1 back f2 25 may TOTAL BACKORDER 1 _TYPE_ TOTAL BACKORDER -1 _RHS_ TOTAL BACKORDER 50 ;
The nonarc variables f1 chips from mar and f2 chips from mar have objective function coefficients of 1 and upper bounds of 150. There are various ways in which this information can be furnished to PROC INTPOINT. If there were a TYPE list variable in the CONDATA= data set, observations could be in the form
_COLUMN_ _TYPE_ _ROW_ _COEF_ f1 chips from mar objfn . 1 f1 chips from mar upperbd . 150 f2 chips from mar objfn . 1 f2 chips from mar upperbd . 150
It is desirable to assign ID list variable values to all the nonarc variables:
data arc6;
input _tail_ $ _head_ $ _cost_ _capac_ _lo_ diagonal factory
key_id $10. mth_made $ _name_&$17.;
datalines;
fact1_1 f1_apr_1 78.60 600 50 19 1 production April prod f1 19 apl
f1_mar_1 f1_apr_1 15.00 50 . 19 1 storage March .
f1_may_1 f1_apr_1 33.60 20 . 19 1 backorder May back f1 19 may
f2_apr_1 f1_apr_1 11.00 40 . 19 . f2_to_1 April .
fact1_2 f1_apr_2 174.50 550 50 25 1 production April prod f1 25 apl
f1_mar_2 f1_apr_2 20.00 40 . 25 1 storage March .
f1_may_2 f1_apr_2 49.20 15 . 25 1 backorder May back f1 25 may
f2_apr_2 f1_apr_2 21.00 25 . 25 . f2_to_1 April .
fact1_1 f1_mar_1 127.90 500 50 19 1 production March prod f1 19 mar
f1_apr_1 f1_mar_1 33.60 20 . 19 1 backorder April back f1 19 apl
f2_mar_1 f1_mar_1 10.00 40 . 19 . f2_to_1 March .
fact1_2 f1_mar_2 217.90 400 40 25 1 production March prod f1 25 mar
f1_apr_2 f1_mar_2 38.40 30 . 25 1 backorder April back f1 25 apl
f2_mar_2 f1_mar_2 20.00 25 . 25 . f2_to_1 March .
fact1_1 f1_may_1 90.10 400 50 19 1 production May .
f1_apr_1 f1_may_1 12.00 50 . 19 1 storage April .
f2_may_1 f1_may_1 13.00 40 . 19 . f2_to_1 May .
fact1_2 f1_may_2 113.30 350 40 25 1 production May .
f1_apr_2 f1_may_2 18.00 40 . 25 1 storage April .
f2_may_2 f1_may_2 13.00 25 . 25 . f2_to_1 May .
f1_apr_1 f2_apr_1 11.00 . . 19 . f1_to_2 April .
fact2_1 f2_apr_1 62.40 480 35 19 2 production April prod f2 19 apl
f2_mar_1 f2_apr_1 18.00 30 . 19 2 storage March .
f2_may_1 f2_apr_1 30.00 15 . 19 2 backorder May back f2 19 may
f1_apr_2 f2_apr_2 23.00 . . 25 . f1_to_2 April .
fact2_2 f2_apr_2 196.70 680 35 25 2 production April prod f2 25 apl
f2_mar_2 f2_apr_2 28.00 50 . 25 2 storage March .
f2_may_2 f2_apr_2 64.80 15 . 25 2 backorder May back f2 25 may
f1_mar_1 f2_mar_1 11.00 . . 19 . f1_to_2 March .
fact2_1 f2_mar_1 88.00 450 35 19 2 production March prod f2 19 mar
f2_apr_1 f2_mar_1 20.40 15 . 19 2 backorder April back f2 19 apl
f1_mar_2 f2_mar_2 23.00 . . 25 . f1_to_2 March .
fact2_2 f2_mar_2 182.00 650 35 25 2 production March prod f2 25 mar
f2_apr_2 f2_mar_2 37.20 15 . 25 2 backorder April back f2 25 apl
f1_may_1 f2_may_1 16.00 . . 19 . f1_to_2 May .
fact2_1 f2_may_1 128.80 250 35 19 2 production May .
f2_apr_1 f2_may_1 20.00 30 . 19 2 storage April .
f1_may_2 f2_may_2 26.00 . . 25 . f1_to_2 May .
fact2_2 f2_may_2 181.40 550 35 25 2 production May .
f2_apr_2 f2_may_2 38.00 50 . 25 2 storage April .
f1_mar_1 shop1_1 -327.65 250 . 19 1 sales March .
f1_apr_1 shop1_1 -300.00 250 . 19 1 sales April .
f1_may_1 shop1_1 -285.00 250 . 19 1 sales May .
f2_mar_1 shop1_1 -297.40 250 . 19 2 sales March .
f2_apr_1 shop1_1 -290.00 250 . 19 2 sales April .
f2_may_1 shop1_1 -292.00 250 . 19 2 sales May .
f1_mar_2 shop1_2 -559.76 . . 25 1 sales March .
f1_apr_2 shop1_2 -524.28 . . 25 1 sales April .
f1_may_2 shop1_2 -515.02 . . 25 1 sales May .
f2_mar_2 shop1_2 -567.83 500 . 25 2 sales March .
f2_apr_2 shop1_2 -542.19 500 . 25 2 sales April .
f2_may_2 shop1_2 -491.56 500 . 25 2 sales May .
f1_mar_1 shop2_1 -362.74 250 . 19 1 sales March .
f1_apr_1 shop2_1 -300.00 250 . 19 1 sales April .
f1_may_1 shop2_1 -245.00 250 . 19 1 sales May .
f2_mar_1 shop2_1 -272.70 250 . 19 2 sales March .
f2_apr_1 shop2_1 -312.00 250 . 19 2 sales April .
f2_may_1 shop2_1 -299.00 250 . 19 2 sales May .
f1_mar_2 shop2_2 -623.89 . . 25 1 sales March .
f1_apr_2 shop2_2 -549.68 . . 25 1 sales April .
f1_may_2 shop2_2 -500.00 . . 25 1 sales May .
f2_mar_2 shop2_2 -542.83 500 . 25 2 sales March .
f2_apr_2 shop2_2 -559.19 500 . 25 2 sales April .
f2_may_2 shop2_2 -519.06 500 . 25 2 sales May .
;
data arc6; set arc5; drop oldcost oldfc oldflow _flow_ _fcost_ ; run;
data arc6_b; input _name_ &$17. _cost_ _capac_ factory key_id $ ; datalines; f1 unused chips . . 1 chips f2 unused chips . . 2 chips f1 chips from mar 1 150 1 chips f2 chips from mar 1 150 2 chips ;
proc append force base=arc6 data=arc6_b; run; proc intpoint bytes=1000000 printlevel2=2 nodedata=node0 arcdata=arc6 condata=con6 defcontype=eq sparsecondata conout=arc7; run;
The following messages appear on the SAS log:
| Production Planning/Inventory/Distribution |
| Nonarc Variables in the Side Constraints |
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: Number of nonarc variables= 4 . |
NOTE: Number of <= side constraints= 1 . |
NOTE: Number of == side constraints= 4 . |
NOTE: Number of >= side constraints= 1 . |
NOTE: Number of side constraint coefficients= 24 . |
NOTE: The following messages relate to the equivalent Linear Programming problem |
solved by the Interior Point algorithm. |
NOTE: Number of <= constraints= 1 . |
NOTE: Number of == constraints= 25 . |
NOTE: Number of >= constraints= 1 . |
NOTE: Number of constraint coefficients= 160 . |
NOTE: Number of variables= 72 . |
NOTE: After preprocessing, number of <= constraints= 1. |
NOTE: After preprocessing, number of == constraints= 24. |
NOTE: After preprocessing, number of >= constraints= 1. |
NOTE: The preprocessor eliminated 1 constraints from the problem. |
NOTE: The preprocessor eliminated 9 constraint coefficients from the problem. |
NOTE: 2 columns, 0 rows and 2 coefficients were added to the problem to handle |
unrestricted variables, variables that are split, and constraint slack or |
surplus variables. |
NOTE: There are 78 sub-diagonal nonzeroes in the unfactored A Atranspose matrix. |
NOTE: The 26 factor nodes make up 18 supernodes |
NOTE: There are 101 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 210688061 0.904882 69336 35199 4398.024971 |
1 54066756 35459986 0.931873 5967.706945 3029.541352 935.225890 |
2 10266927 2957978 0.671565 0 0 36.655485 |
3 326659 314818 0.177750 0 0 3.893178 |
4 137432 83570 0.053111 0 0 0.852994 |
5 41386 26985 0.017545 0 0 0.204166 |
6 12451 6063.528974 0.003973 0 0 0.041229 |
7 2962.309960 1429.369437 0.000939 0 0 0.004395 |
8 352.469864 233.620884 0.000153 0 0 0.000297 |
9 115.012309 23.329492 0.000015331 0 0 0 |
10 1.754859 0.039304 2.5828261E-8 0 0 0 |
NOTE: The Primal-Dual Predictor-Corrector Interior Point algorithm performed 10 |
iterations. |
NOTE: Optimum reached. |
NOTE: Objective= -1295542.717. |
NOTE: The data set WORK.ARC7 has 68 observations and 14 variables. |
NOTE: There were 68 observations read from the data set WORK.ARC6. |
NOTE: There were 8 observations read from the data set WORK.NODE0. |
NOTE: There were 31 observations read from the data set WORK.CON6. |
The optimal solution data set, CONOUT=ARC7, is given in Output 4.5.1.
proc print data=arc7;
var _tail_ _head_ _name_ _cost_ _capac_ _lo_
_flow_ _fcost_;
sum _fcost_;
run;
The optimal value of the nonarc variable f2 unused chips is 280. This means that although there are 3,750 chips that can be used at factory 2 in March, only 3,470 are used. As the optimal value of f1 unused chips is zero, all chips available for production in March at factory 1 are used. The nonarc variable f2 chips from mar also has zero optimal value. This means that the April production at factory 2 does not need any chips that could have been held in inventory since March. However, the nonarc variable f1 chips from mar has value of 20. Thus, 3,490 chips should be ordered for factory 2 in March. Twenty of these chips should be held in inventory until April, then sent to factory 1.
| Production Planning/Inventory/Distribution |
| Nonarc Variables in the Side Constraints |
| Obs | _tail_ | _head_ | _name_ | _cost_ | _capac_ | _lo_ | _FLOW_ | _FCOST_ |
|---|---|---|---|---|---|---|---|---|
| 1 | fact1_1 | f1_apr_1 | prod f1 19 apl | 78.60 | 600 | 50 | 540.000 | 42444.00 |
| 2 | f1_mar_1 | f1_apr_1 | 15.00 | 50 | 0 | 0.000 | 0.00 | |
| 3 | f1_may_1 | f1_apr_1 | back f1 19 may | 33.60 | 20 | 0 | 0.000 | 0.00 |
| 4 | f2_apr_1 | f1_apr_1 | 11.00 | 40 | 0 | 0.000 | 0.00 | |
| 5 | fact1_2 | f1_apr_2 | prod f1 25 apl | 174.50 | 550 | 50 | 250.000 | 43625.01 |
| 6 | f1_mar_2 | f1_apr_2 | 20.00 | 40 | 0 | 0.000 | 0.00 | |
| 7 | f1_may_2 | f1_apr_2 | back f1 25 may | 49.20 | 15 | 0 | 0.000 | 0.00 |
| 8 | f2_apr_2 | f1_apr_2 | 21.00 | 25 | 0 | 25.000 | 525.00 | |
| 9 | fact1_1 | f1_mar_1 | prod f1 19 mar | 127.90 | 500 | 50 | 338.333 | 43272.81 |
| 10 | f1_apr_1 | f1_mar_1 | back f1 19 apl | 33.60 | 20 | 0 | 20.000 | 672.00 |
| 11 | f2_mar_1 | f1_mar_1 | 10.00 | 40 | 0 | 40.000 | 400.00 | |
| 12 | fact1_2 | f1_mar_2 | prod f1 25 mar | 217.90 | 400 | 40 | 400.000 | 87159.99 |
| 13 | f1_apr_2 | f1_mar_2 | back f1 25 apl | 38.40 | 30 | 0 | 30.000 | 1152.00 |
| 14 | f2_mar_2 | f1_mar_2 | 20.00 | 25 | 0 | 25.000 | 500.00 | |
| 15 | fact1_1 | f1_may_1 | 90.10 | 400 | 50 | 116.667 | 10511.68 | |
| 16 | f1_apr_1 | f1_may_1 | 12.00 | 50 | 0 | 0.000 | 0.00 | |
| 17 | f2_may_1 | f1_may_1 | 13.00 | 40 | 0 | 0.000 | 0.00 | |
| 18 | fact1_2 | f1_may_2 | 113.30 | 350 | 40 | 350.000 | 39655.00 | |
| 19 | f1_apr_2 | f1_may_2 | 18.00 | 40 | 0 | 0.000 | 0.00 | |
| 20 | f2_may_2 | f1_may_2 | 13.00 | 25 | 0 | 0.000 | 0.00 | |
| 21 | f1_apr_1 | f2_apr_1 | 11.00 | 99999999 | 0 | 20.000 | 220.00 | |
| 22 | fact2_1 | f2_apr_1 | prod f2 19 apl | 62.40 | 480 | 35 | 480.000 | 29952.00 |
| 23 | f2_mar_1 | f2_apr_1 | 18.00 | 30 | 0 | 0.000 | 0.00 | |
| 24 | f2_may_1 | f2_apr_1 | back f2 19 may | 30.00 | 15 | 0 | 0.000 | 0.00 |
| 25 | f1_apr_2 | f2_apr_2 | 23.00 | 99999999 | 0 | 0.000 | 0.00 | |
| 26 | fact2_2 | f2_apr_2 | prod f2 25 apl | 196.70 | 680 | 35 | 577.500 | 113594.25 |
| 27 | f2_mar_2 | f2_apr_2 | 28.00 | 50 | 0 | 0.000 | 0.00 | |
| 28 | f2_may_2 | f2_apr_2 | back f2 25 may | 64.80 | 15 | 0 | 0.000 | 0.00 |
| 29 | f1_mar_1 | f2_mar_1 | 11.00 | 99999999 | 0 | 0.000 | 0.00 | |
| 30 | fact2_1 | f2_mar_1 | prod f2 19 mar | 88.00 | 450 | 35 | 290.000 | 25520.00 |
| 31 | f2_apr_1 | f2_mar_1 | back f2 19 apl | 20.40 | 15 | 0 | 0.000 | 0.00 |
| 32 | f1_mar_2 | f2_mar_2 | 23.00 | 99999999 | 0 | 0.000 | 0.00 | |
| 33 | fact2_2 | f2_mar_2 | prod f2 25 mar | 182.00 | 650 | 35 | 650.000 | 118300.00 |
| 34 | f2_apr_2 | f2_mar_2 | back f2 25 apl | 37.20 | 15 | 0 | 0.000 | 0.00 |
| 35 | f1_may_1 | f2_may_1 | 16.00 | 99999999 | 0 | 115.000 | 1840.00 | |
| 36 | fact2_1 | f2_may_1 | 128.80 | 250 | 35 | 35.000 | 4508.00 | |
| 37 | f2_apr_1 | f2_may_1 | 20.00 | 30 | 0 | 0.000 | 0.00 | |
| 38 | f1_may_2 | f2_may_2 | 26.00 | 99999999 | 0 | 0.000 | 0.00 | |
| 39 | fact2_2 | f2_may_2 | 181.40 | 550 | 35 | 122.500 | 22221.50 | |
| 40 | f2_apr_2 | f2_may_2 | 38.00 | 50 | 0 | 0.000 | 0.00 | |
| 41 | f1_mar_1 | shop1_1 | -327.65 | 250 | 0 | 148.333 | -48601.35 | |
| 42 | f1_apr_1 | shop1_1 | -300.00 | 250 | 0 | 250.000 | -75000.00 | |
| 43 | f1_may_1 | shop1_1 | -285.00 | 250 | 0 | 1.667 | -475.01 | |
| 44 | f2_mar_1 | shop1_1 | -297.40 | 250 | 0 | 250.000 | -74350.00 | |
| 45 | f2_apr_1 | shop1_1 | -290.00 | 250 | 0 | 250.000 | -72500.00 | |
| 46 | f2_may_1 | shop1_1 | -292.00 | 250 | 0 | 0.000 | -0.05 | |
| 47 | f1_mar_2 | shop1_2 | -559.76 | 99999999 | 0 | 0.000 | 0.00 | |
| 48 | f1_apr_2 | shop1_2 | -524.28 | 99999999 | 0 | 0.000 | 0.00 | |
| 49 | f1_may_2 | shop1_2 | -515.02 | 99999999 | 0 | 347.500 | -178969.34 | |
| 50 | f2_mar_2 | shop1_2 | -567.83 | 500 | 0 | 500.000 | -283914.98 | |
| 51 | f2_apr_2 | shop1_2 | -542.19 | 500 | 0 | 52.500 | -28465.09 | |
| 52 | f2_may_2 | shop1_2 | -491.56 | 500 | 0 | 0.000 | 0.00 | |
| 53 | f1_mar_1 | shop2_1 | -362.74 | 250 | 0 | 250.000 | -90684.99 | |
| 54 | f1_apr_1 | shop2_1 | -300.00 | 250 | 0 | 250.000 | -75000.00 | |
| 55 | f1_may_1 | shop2_1 | -245.00 | 250 | 0 | 0.000 | -0.00 | |
| 56 | f2_mar_1 | shop2_1 | -272.70 | 250 | 0 | 0.000 | -0.01 | |
| 57 | f2_apr_1 | shop2_1 | -312.00 | 250 | 0 | 250.000 | -78000.00 | |
| 58 | f2_may_1 | shop2_1 | -299.00 | 250 | 0 | 150.000 | -44850.00 | |
| 59 | f1_mar_2 | shop2_2 | -623.89 | 99999999 | 0 | 455.000 | -283869.90 | |
| 60 | f1_apr_2 | shop2_2 | -549.68 | 99999999 | 0 | 245.000 | -134671.54 | |
| 61 | f1_may_2 | shop2_2 | -500.00 | 99999999 | 0 | 2.500 | -1250.00 | |
| 62 | f2_mar_2 | shop2_2 | -542.83 | 500 | 0 | 125.000 | -67853.77 | |
| 63 | f2_apr_2 | shop2_2 | -559.19 | 500 | 0 | 500.000 | -279594.99 | |
| 64 | f2_may_2 | shop2_2 | -519.06 | 500 | 0 | 122.500 | -63584.94 | |
| 65 | f1 chips from mar | 1.00 | 150 | 0 | 20.000 | 20.00 | ||
| 66 | f1 unused chips | 0.00 | 99999999 | 0 | 0.001 | 0.00 | ||
| 67 | f2 chips from mar | 1.00 | 150 | 0 | 0.000 | 0.00 | ||
| 68 | f2 unused chips | 0.00 | 99999999 | 0 | 280.000 | 0.00 | ||
| -1295542.72 |
|
|
Copyright © SAS Institute, Inc. All Rights Reserved.