Courier Service System - Simplex Algorithm
What is Simplex Algorithm ?
- The simplex method, in mathematical optimization, is a well-known algorithm used for linear programming.
- The simplex method uses a systematic strategy to generate and test candidate vertex solutions to a linear program.
Simplex Algorithm
1. Slack and surplus variables
- Before the simplex algorithm can be used to solve a linear program, the problem must be written in standard form.
- Constraints of type (≤) : for each constraint i of this type, we add a slack
variable ei, such that ei is nonnegative.
Example: 3x1 + 2x2 ≤ 2 translates into 3x1 + 2x2 + e1 = 2, e1 ≤ 0 - Constraints of type (≤) : for each constraint i of this type, we add a surplus
variable ei, such that ei is nonnegative.
Example: 3x1 + 2x2 ≤ 2 translates into 3x1 + 2x2- e2 = 2, e2 ≤ 0
A linear program that contains (technological) constraints of the type ≤ is abbreviated as (LP). A linear program that contains mixed (technological) constraints (≤, ≤, =) is abbreviated as (GP). A linear program (LP) resp. (GP) converted into standard form is abbreviated as (PL=) resp. (PG=).
Sluck and Surplus variable
2. Basic and non‐basic variables
- Consider a system of equations with n variables and m equations where n ≤ m. A basic solution for this system is obtained in the following way:
- Set n - m variables equal to zero. These variables are called non‐basic variables (N.B.V).
- Solve the system for the m remaining variables. These variables are called basic variables (B.V.)
- The vector of variables obtained is called the basic solution (it contains both basic and non‐basic variables).