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

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

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:
    1. Set n - m variables equal to zero. These variables are called non‐basic variables (N.B.V).
    2. Solve the system for the m remaining variables. These variables are called basic variables (B.V.)
    3. The vector of variables obtained is called the basic solution (it contains both basic and non‐basic variables).

Related Searches to Courier Service System - Simplex Algorithm