The Linear Programming Solver

Example 5.1 Diet Problem

Consider the problem of diet optimization. There are six different foods: bread, milk, cheese, potato, fish, and yogurt. The cost and nutrition values per unit are displayed in Table 5.5.

Table 5.5 Cost and Nutrition Values
	Bread	Milk	Cheese	Potato	Fish	Yogurt
Cost	2.0	3.5	8.0	1.5	11.0	1.0
Protein, g	4.0	8.0	7.0	1.3	8.0	9.2
Fat, g	1.0	5.0	9.0	0.1	7.0	1.0
Carbohydrates, g	15.0	11.7	0.4	22.6	0.0	17.0
Calories	90	120	106	97	130	180

The following SAS code creates the data set fooddata of Table 5.5:

data fooddata;
infile datalines;
input    name $  cost  prot  fat  carb  cal;
datalines;                      
         Bread   2     4     1    15    90
         Milk    3.5   8     5    11.7  120
         Cheese  8     7     9    0.4   106
         Potato  1.5   1.3   0.1  22.6  97
         Fish    11    8     7    0     130
         Yogurt  1     9.2   1    17    180
;

The objective is to find a minimum-cost diet that contains at least 300 calories, not more than 10 grams of protein, not less than 10 grams of carbohydrates, and not less than 8 grams of fat. In addition, the diet should contain at least 0.5 unit of fish and no more than 1 unit of milk.

You can model the problem and solve it by using PROC OPTMODEL as follows:

proc optmodel;
   /* declare index set */
   set<str> FOOD;
   
   /* declare variables */
   var diet{FOOD} >= 0;
   
   /* objective function */
   num cost{FOOD};
   min f=sum{i in FOOD}cost[i]*diet[i];
   
   /* constraints */
   num prot{FOOD};
   num fat{FOOD};
   num carb{FOOD}; 
   num cal{FOOD};
   num min_cal, max_prot, min_carb, min_fat;
   con cal_con: sum{i in FOOD}cal[i]*diet[i] >= 300;
   con prot_con: sum{i in FOOD}prot[i]*diet[i] <= 10;
   con carb_con: sum{i in FOOD}carb[i]*diet[i] >= 10;
   con fat_con: sum{i in FOOD}fat[i]*diet[i] >= 8;
   
   /* read parameters */
   read data fooddata into FOOD=[name] cost prot fat carb cal;
   
   /* bounds on variables */
   diet['Fish'].lb = 0.5;
   diet['Milk'].ub = 1.0;
   
   /* solve and print the optimal solution */
   solve with lp/printfreq=1; /* print each iteration to log */
   print diet;

The optimal solution and the optimal objective value are displayed in Output 5.1.1.

Output 5.1.1 Optimal Solution to the Diet Problem

The OPTMODEL Procedure

Problem Summary
Objective Sense	Minimization
Objective Function	f
Objective Type	Linear

Number of Variables	6
Bounded Above	0
Bounded Below	5
Bounded Below and Above	1
Free	0
Fixed	0

Number of Constraints	4
Linear LE (<=)	1
Linear EQ (=)	0
Linear GE (>=)	3
Linear Range	0

Constraint Coefficients	23

Solution Summary
Solver	Dual Simplex
Objective Function	f
Solution Status	Optimal
Objective Value	12.081337881
Iterations	4

Primal Infeasibility	8.881784E-16
Dual Infeasibility	0
Bound Infeasibility	0

[1]	diet
Bread	0.000000
Cheese	0.449499
Fish	0.500000
Milk	0.053599
Potato	1.865168
Yogurt	0.000000