Problem 4.
1-1: Graphical Solution and CPF Analysis
Problem Statement
Maximize Z=x 1+2 x 2,
subject to:
{ )
x1 ≤ 2
x2 ≤ 2
x1 + x2 ≤ 3
x 1 ≥ 0 , x 2 ≥ 0.
(a) Plot the Feasible Region and Identify CPF Solutions
Step 1: Graph the Constraints
1. x 1 ≤ 2
o Vertical line at x 1=2.
o Feasible region: Left side of the line.
2. x 2 ≤ 2
o Horizontal line at x 2=2.
o Feasible region: Below the line.
3. x 1+ x2 ≤3
o Line from ( 0 , 3 ) to ( 3 , 0 ) .
o Feasible region: Below the line.
4. Non-negativity constraints:
o x 1 ≥ 0, x 2 ≥ 0.
Step 2: Identify the Feasible Region
The feasible region is a polygon bounded by the intersection of all constraints.
Step 3: Find Corner-Point Feasible (CPF) Solutions
Intersection points of the constraints:
a. ( 0 , 0 ) : Origin.
b. ( 0 , 2 ): Intersection of x 1=0 and x 2=2.
c. ( 1 , 2 ): Intersection of x 2=2 and x 1+ x2 =3.
d. ( 2 , 1 ): Intersection of x 1=2 and x 1+ x2 =3.
e. ( 2 , 0 ): Intersection of x 1=2 and x 2=0.
(b) Constraint Boundary Equations for Each CPF Solution
CPF Solution Boundary Equations
( 0 , 0) x 1=0 , x 2=0
( 0 , 2) x 1=0 , x 2=2
( 1 , 2) x 2=2, x 1+ x2 =3
( 2 , 1) x 1=2, x 1+ x2 =3
( 2 , 0) x 1=2, x 2=0
(c) Solve Algebraically for CPF Coordinates
1. ( 0 , 0 ) :
o Directly satisfies x 1=0, x 2=0 .
2. ( 0 , 2 ):
o Solve x 1=0 and x 2=2.
3. ( 1 , 2 ):
o Solve:
$$\left. \left\{ \begin{matrix} {x_{2} = 2} \\ {x_{1} + x_{2} = 3} \end{matrix} \right.\
text{\:\,}\Longrightarrow\text{\:\,}x_{1} = 1,\ x_{2} = 2. \right.$$
4. ( 2 , 1 ):
o Solve:
$$\left. \left\{ \begin{matrix} {x_{1} = 2} \\ {x_{1} + x_{2} = 3} \end{matrix} \right.\
text{\:\,}\Longrightarrow\text{\:\,}x_{2} = 1. \right.$$
5. ( 2 , 0 ):
o Solve x 1=2, x 2=0 .
(d) Adjacent CPF Solutions
CPF Solution Adjacent CPF Solutions
( 0 , 0) ( 0 , 2 ), ( 2 , 0 )
( 0 , 2) ( 0 , 0 ), ( 1 , 2 )
( 1 , 2) ( 0 , 2 ), ( 2 , 1 )
( 2 , 1) ( 1 , 2 ), ( 2 , 0 )
( 2 , 0) ( 0 , 0 ), ( 2 , 1 )
(e) Shared Constraint Boundaries for Adjacent CPF Pairs
Adjacent CPF Pair Shared Constraint Boundary
( 0 , 0 ) –( 0 , 2 ) x 1=0
( 0 , 0 ) –( 2 , 0 ) x 2=0
( 0 , 2 )–( 1 , 2 ) x 2=2
( 1 , 2 )–( 2 , 1 ) x 1+ x2 =3
( 2 , 1 )–( 2 , 0 ) x 1=2
Optimal Solution
Calculate Z=x 1+2 x 2 for each CPF solution:
( 0 , 0 ) : Z=0
( 0 , 2 ): Z=4
( 1 , 2 ): Z=5
( 2 , 1 ): Z=4
( 2 , 0 ): Z=2
Conclusion: The optimal solution is ( 1 , 2 ) with Z=5.
Problem 4.1-3: Simplex Method Application
(a) Calculate Total Profit for Each CPF Solution
Given:
Unit profit: x_1 = \1,000 , x_2 = $2,000 $.
Objective: Z=1000 x1 +2000 x 2.
CPF Solution Calculation Total Profit ( Z )
( 5 , 5) 1000 ( 5 ) +2000 ( 5 ) $15,000
(6 , 4 ) 1000 ( 6 ) +2000 ( 4 ) $14,000
( 8 , 0) 1000 ( 8 ) +2000 ( 0 ) $8,000
Optimal Solution: ( 5 , 5 ) with Z = \15,000 $.
(b) Simplex Method Sequence
1. Start at ( 8 , 0 ) ( Z = \8,000 $).
2. Move to ( 6 , 4 ) ( Z = \14,000 $).
3. Move to ( 5 , 5 ) ( Z = \15,000 $).
Final Sequence:
( 8 , 0 ) → ( 6 , 4 ) → (5 , 5 ) . )
Key Takeaways
Graphical Method: Used to visualize constraints and identify CPF solutions.
Simplex Method: Iteratively moves to adjacent CPF solutions to maximize profit.
Optimality: Achieved when no adjacent CPF solution improves the objective function.