Page 86 - DCOM303_DMGT504_OPERATION_RESEARCH

Unit 3: Linear Programming Problem – Simplex Method

Notes
Figure 3.7: The Reddin Problem—Infeasibility

10000
X 2
9000
Processing Constraint
8000

7000
Demand Constraint
6000
5000

4000 Combined Machine
Feasible Region
3000
2000
Assembly Constraint
1000

1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
X 1
The graphical presentation of the Reddin Problem in Figure shows that the combined machine
feasibility region does not permit the production of 6,500 units of product A. Thus, the demand
constraint and the machine capacity constraints are mutually conflicting, resulting in infeasibility.
Let us try to solve this problem by the simplex method. It is formulated below in the standard
simplex form.
Row 1: P- 5x – 4x -50a = 0
1 2 1
Row 2: 2x + 1x + s = 10,000
1 2 1
3
Row 3: 2x + x + s = 12,000
1 2 2 2
Row 4: x + a = 6,500
1 1
Artificial variable a1 has been assigned a coefficient of 50 in the objective function.
Towards The First Basis

Row 4 × 50: 50x + 50a = 325,000
1 1
Old Row 1: Z – 5x – 4x - 50a = 0
1 2 1
New Row 1: Z + 45x – 4x = 325,000
1 2
Table 3.2: The First Basis
Row 1: P + 45x – 4x = 325,000
1 2
Row 2: 2x + x + s = 10,000
1 2 1
Row 3: 2x + x +s = 12,000
1 2 2
Row 4: x +a = 6,500
1 1

LOVELY PROFESSIONAL UNIVERSITY 81