Chapter Contents
Chapter Contents
Previous
Previous
Next
Next
Introduction to Optimization

Exploiting Model Structure

Another example helps to illustrate how the model can be simplified by exploiting the structure in the model and by using the NETFLOW procedure.

Recall the chocolate transshipment problem discussed earlier. The solution required no production at factory_1 and no storage at warehouse_2. Suppose this solution, although optimal, is unacceptable. An additional constraint requiring the production at the two factories to be balanced is required. Now, the production at the two factories can differ by, at most, 100 units. Such a constraint might look like

-100 <= (factory_1_warehouse_1 + factory_1_warehouse_2 -
         factory_2_warehouse_1 - factory_2_warehouse_2) <= 100

The network and supply and demand information is saved in the two data sets.

   data network;
      format from $16. to $16.;
      input  from $ to $ cost ;
      datalines;
factory_1  warehouse_1  10 
factory_2  warehouse_1   5
factory_1  warehouse_2   7
factory_2  warehouse_2   9
warehouse_1 customer_1   3
warehouse_1 customer_2   4
warehouse_1 customer_3   4
warehouse_2 customer_1   5
warehouse_2 customer_2   5
warehouse_2 customer_3   6
   ;

   data nodes;
      format node $16. ;
      input node $  supdem;
      datalines;
customer_1 -100
customer_2 -200
customer_3  -50
factory_1   500
factory_2   500                       
   ;

The factory balancing constraint is not a part of the network. It is represented in the sparse format in a data set for side constraints.

   data side_con;
      format _type_ $8. _row_ $16. _col_ $21. _coef_ 8.;
      input  _type_     _row_      _col_      _coef_   ;
      datalines;
eq       balance   .                         .
.        balance  factory_1_warehouse_1      1
.        balance  factory_1_warehouse_2      1
.        balance  factory_2_warehouse_1     -1
.        balance  factory_2_warehouse_2     -1
.        balance  diff                      -1
lo       lowerbd  diff                    -100
up       upperbd  diff                     100
   ;

It contains an equality constraint that sets the value of DIFF to be the amount that factory 1 production exceeds factory 2 production. It also contains implicit bounds on the DIFF variable. Note that the DIFF variable is a nonarc variable.

   proc netflow 
     conout=con_sav
     arcdata=network nodedata=nodes condata=side_con 
     sparsecondata ;

     node node;
     supdem supdem;   

     tail from; 
     head to; 
     cost cost;

     run;

   proc print;
      var from to _name_ cost _capac_ _lo_ _supply_ _demand_  
          _flow_ _fcost_ _rcost_;
      sum _fcost_;
      run;

The solution is saved in the con_sav data set (Figure 1.20).

Obs from to _NAME_ cost _CAPAC_ _LO_ _SUPPLY_ _DEMAND_ _FLOW_ _FCOST_ _RCOST_
1 warehouse_1 customer_1   3 99999999 0 . 100 100 300 .
2 warehouse_2 customer_1   5 99999999 0 . 100 0 0 1.0
3 warehouse_1 customer_2   4 99999999 0 . 200 75 300 .
4 warehouse_2 customer_2   5 99999999 0 . 200 125 625 .
5 warehouse_1 customer_3   4 99999999 0 . 50 50 200 .
6 warehouse_2 customer_3   6 99999999 0 . 50 0 0 1.0
7 factory_1 warehouse_1   10 99999999 0 500 . 0 0 2.0
8 factory_2 warehouse_1   5 99999999 0 500 . 225 1125 .
9 factory_1 warehouse_2   7 99999999 0 500 . 125 875 .
10 factory_2 warehouse_2   9 99999999 0 500 . 0 0 5.0
11     diff 0 100 -100 . . -100 0 1.5
                    3425  

Figure 1.20: PROC NETFLOW solution

Notice that the solution now has production balanced across the factories; the production at factory 2 exceeds that at factory 1 by 100 units.

intromp3.gif (2492 bytes)

Figure 1.21: Constrained Optimum for the Transshipment Problem

Chapter Contents
Chapter Contents
Previous
Previous
Next
Next
Top
Top

Copyright © 1999 by SAS Institute Inc., Cary, NC, USA. All rights reserved.