Simplex Method
Created on: {{date}}
Tags: #concept
Course: Optimization
Definition
Simplex method is an iterative procedure for solving linear programming problems expressed in standard form.
Requirements for standard and canonical form
- RHS should be positive.
- All constraints should be an equality.
- All variable bounds should be greater than or equal to zero.
Slack Variables
- For $\le$ constraint, add slack variables to the equation.
- For $\ge$ constraint, subtract slack variables to the equation.
Artificial Variables
- For maximization problem, subtract the artificial variable.
- For minimization problem, add the artificial variable.
Optimality Condition: A basic feasible solution is optimal if the relative profits of its non-basic variables are
- In case of Maximization –> Negative or Zero
- In case of Minimization –> Positive or Zero
Relative Profit $\mathbf{\bar{c}}$ is given by the following formula,
\(\bar{C}_{j} = C_{j} - [C_{B}\,\, \cdot\,\, \text{Column corresponding to } x_{j}]\) Minimum Ratio Rule The constraints in which the non-basic variable has a positive coefficient, the value of $\theta$ is given as the ratio of the RHS to that of the positive coefficient, otherwise the value of $\theta$ is equal to $\infty$.
Algorithm
- Express the problem in standard form.
- Start with an initial basic feasible solution in canonical form and setup the initial tableau.
- Use the inner product rule to find the relative profit coefficients.
- If all the $\bar{C}{j}$ coefficients are non-positive (in case of maximization), the current solution is optimal. Otherwise, select the non-basic variable with the most positive $\bar{C}{j}$ value to enter the basis.
- Apply the minimum ratio rule to determine the basic variable to leave the basis.
- Perform the pivot operation to get the new tableau and the basic feasible solution.
- Compute the relative profit coefficients. Return to Step 4.
Possible Solution Cases
- Unique Optimal Feasible: $C_{j} - Z_{j} = 0$ for all basis variables.
- Multiple Optimal Feasible: Net improvement of the non-basic variables is 0 in the optimal simplex table.
- Infeasible Solution: If the final optimal table has an artificial variable in the basis vector.
- Unbounded Solution: In an simplex table which is an non-optimal, there is an entering variable but no leaving variable.
- Degeneracy: Tie between values of $\theta$.
Linked from
- No other published notes link here yet.