Graphic Method, Simplex Method (including Big M method)

Graphical and Simplex Methods of Solving LP Problems

Linear Programming (LP) models can be addressed using various methods, with the graphical method and the simplex method being two of the most common approaches.

Graphical Method

The graphical method is a visual technique used for solving linear programming problems with two decision variables. This method involves plotting constraints on a graph, identifying the feasible region, and finding the optimal solution by evaluating the objective function at the vertices (corner points) of the feasible region.

Example Problem:

A workshop uses three types of machines (A, B, and C) to produce two products (1 and 2). The hours required for each product per machine, total available hours per machine per week, and profit per unit sold are summarized in the table below:

Machine	Product 1 (hours)	Product 2 (hours)	Total Available Hours (per week)
A	2	1	100
B	1	3	150
C	2	1	100

Profit per unit:

• • Product 1: $40
  • Product 2: $30

Formulation:

Decision Variables:

• $x_1$: Units of Product 1 to be produced weekly.
• $x_2$: Units of Product 2 to be produced weekly.

Objective Function:

Maximize profit $Z$:

$$Z=40x_1+30x_2$$

Constraints:

• Machine A:

  $$2x_1+x_2\le 100$$

• Machine B:

  $$x_1+3x_2\le 150$$

• Machine C:

  $$2x_1+x_2\le 100$$

(This constraint is identical to Machine A.)

• Non-negativity:

  $$x_1,x_2\ge 0$$

Graphical Solution:

1. Plot the Constraints:

   • For $2x_1 + x_2 \leq 100$:

     • When $x_1 = 0$, $x_2 = 100$
       
     • When $x_2 = 0$, $x_1 = 50$
       

   • For $x_1 + 3x_2 \leq 150$:

     • When $x_1 = 0$, $x_2=50$
     • When $x_2 = 0$, $x_1 = 150$
       

   • For $2x_1 + x_2 \leq 100$:

     • This constraint is the same as for Machine A.

2. Identify the Feasible Region:

   The feasible region is where all constraints overlap, and both $x_1$ and $x_2$ are non-negative.

3. Evaluate the Objective Function at the Vertices of the Feasible Region:

   Find the vertices of the feasible region by solving the system of equations formed by the constraints.

4. Find the Optimal Solution:

   Calculate $Z = 40x_1 + 30x_2$ at each vertex to identify the maximum profit.

Simplex Method

The simplex method is an iterative procedure for solving linear programming problems with more than two decision variables. It systematically explores the vertices of the feasible region to find the optimal solution.

Steps of the Simplex Method:

1. Convert Inequalities to Equations:

   Introduce slack variables to turn inequalities into equalities.

2. Set Up the Initial Simplex Tableau:

   Arrange the objective function and constraints in a tabular format.

3. Identify the Pivot Element:

   • Select the most negative value in the bottom row (excluding the rightmost column) to choose the entering variable.
   • Determine the pivot row by finding the minimum positive ratio of the rightmost column to the pivot column (ignoring negative or zero values).

4. Perform Row Operations:

   Adjust the tableau to make the pivot element equal to 1 and all other elements in the pivot column equal to 0.

5. Iterate Until Optimality:

   Repeat the process of identifying pivot elements and performing row operations until there are no negative values in the bottom row.

6. Interpret the Final Tableau:

   The final tableau displays the solution to the linear programming problem, including the values of the decision variables and the optimal value of the objective function.

Example Problem:

Using the previous problem setup:

Objective Function:

Maximize $Z$:

$$Z=40x_1+30x_2$$

Constraints:

• Machine A:

  $$2x_1+x_2+s_1=100$$

• Machine B:

  $$x_1+3x_2+s_2=150$$

• Machine C:

  $$2x_1+x_2+s_3=100$$

• Non-negativity:

  $$x_1,x_2,s_1,s_2,s_3\ge 0$$

Initial Simplex Tableau:

Iteration Process:

Continue iterations by selecting the most negative value in the objective row, performing pivot operations, and updating the tableau until the optimal solution is found.

Conclusion:

The graphical method is effective for problems with two decision variables, offering an intuitive approach to visualize constraints and feasible regions. The simplex method, on the other hand, is a powerful tool for larger and more complex problems, systematically finding optimal solutions through iterative adjustments. Both methods are essential in operations research for solving linear programming problems and making optimal decisions.