Example 3.9: An Infeasible Problem

The LP Procedure

Example 3.9: An Infeasible Problem

This is an example of the Infeasible Information Summary that is displayed when an infeasible problem is encountered. Consider the following problem:

               max x + y + z + w

   subject to: x +3y +2z +4w <= 5
               3x + y +2z + w <= 4
               5x +3y +3z +3w  = 9

               x, y, z, w >=0

Examination of this problem reveals that it is unsolvable. Consequently, PROC LP identifies it as infeasible. The following program attempts to solve it:

   data infeas;
      input _id_ $6. x1-x4 _type_ $ _rhs_;
      datalines;
   profit   1    1    1    1    max  .
   const1   1    3    2    4    le   5
   const2   3    1    2    1    le   4
   const3   5    3    3    3    eq   9
   ;
   proc lp; run;

The results are shown in Output 3.9.1.

Output 3.9.1: The Solution of an Infeasible Problem

The LP Procedure

Problem Summary
Objective Function	Max profit
Rhs Variable	_rhs_
Type Variable	_type_
Problem Density (%)	77.78

Variables	Number

Non-negative	4
Slack	2

Total	6

Constraints	Number

LE	2
EQ	1
Objective	1

Total	4

ERROR: Infeasible problem. Note the constraints in the constraint summary
       that are identified as infeasible. If none of the constraints are 
       flagged then check the implicit bounds on the variables.

Output 3.9.1: (continued)

The LP Procedure

Solution Summary
Infeasible Problem
Objective Value	2.25

Phase 1 Iterations	2
Phase 2 Iterations	0
Phase 3 Iterations	0
Integer Iterations	0
Integer Solutions	0
Initial Basic Feasible Variables	4
Time Used (seconds)	0
Number of Inversions	2

Epsilon	1E-8
Infinity	1.797693E308
Maximum Phase 1 Iterations	100
Maximum Phase 2 Iterations	100
Maximum Phase 3 Iterations	99999999
Maximum Integer Iterations	100
Time Limit (seconds)	120

Output 3.9.1: (continued)

The LP Procedure

Variable Summary
Col	Variable Name	Status	Type	Price	Activity	Reduced Cost
1	x1	BASIC	NON-NEG	1	0.875	0
2	x2	BASIC	NON-NEG	1	1.375	0
3	x3	ALTER	NON-NEG	1	0	0
4	x4		NON-NEG	1	0	-0.25
5	const1		SLACK	0	0	-0.25
6	const2		SLACK	0	0	-0.25

Output 3.9.1: (continued)

The LP Procedure

Constraint Summary
Row	Constraint Name	Type	S/S Col	Rhs	Activity	Dual Activity
1	profit	OBJECTVE	.	0	2.25	.
2	const1	LE	5	5	5	0.25
3	const2	LE	6	4	4	0.25
INF	const3	EQ	.	9	8.5	0

Output 3.9.1: (continued)

The LP Procedure

Infeasible Information Summary
Infeasible Row	const3
Constraint Activity	8.5
Row Type	EQ
Rhs Data	9

Variable	Coefficient	Activity	Lower Bound	Upper Bound
x1	5	0.875	0	INFINITY
x2	3	1.375	0	INFINITY
x3	3	0	0	INFINITY
x4	3	0	0	INFINITY

Note the information given in the Infeasible Information Summary for the infeasible row CONST3. It shows that the equality constrained row CONST3 with right-hand-side 9 was found to be infeasible with activity 8.5. The summary also shows each variable that has a nonzero coefficient in that row and its activity level at the infeasibility. Examination of these model parameters might give you a clue as to the cause of infeasibility, such as an incorrectly entered coefficient or right-hand-side value.

Chapter Contents
Previous
Next
Top