Linear optimization: Pivot selection rules 2

Introduction

During the 1940`s George Dantzig discovered that many practical restriction problems can be solved by linear programming. He differed the problem in an objective function and restrictions.
Later, during the 1990`s John Forrest and Donald Goldfarb achieved great progress in solving simplex algorithms by introducing the pivot selection rules.

Example

An organization produces two products: A, B with three different machines: X, Y, Z.
The proceeds of the sale are about 2000 MU (monetary units) per unit and causes direct costs of 1400 MU per unit. Product B generates benefits of 6000 MU per unit and creates direct costs of 5000 MU per unit.
The fixed costs of the production are about 72000 MU each month.
Machine X has a maximal capacity of 340 manufacturing hours per month, machine Y has a capacity about 300 manufacturing hours and machine Z is able to run 360 hours per month.
To fabricate product A, the machines X and Y both need two hours per unit. To build up product B machine X runs four hours, machine Y two hours and machine Z is used six hours per unit.

The objective function describes the aim of the optimization: we want to maximize the proceed less the costs per unit, so we try to find the point, at which the fixed costs are egalised.

e_j: proceed per unit
k_j: costs per unit
x_A: units of product A
x_B: units of product B

Objective function

Max DB = ∑_j (( e_j– k_j ) x_j ) - k_f = (2000 MU – 1400 MU) x_A + (6000 MU - 5000 MU) x_B = 600 x_A + 1000 x_B = 72000

Restrictions

2x_A + 4x_B ≤ 340

bzw. y₁ + 2x_A + 4x_B = 340

2x_A + 2x_B ≤ 300

bzw. y₂ + 2x_A + 2x_B = 300

6x_B ≤ 360

bzw. y₃ + 6x_B = 360

Summary of the algorithm

1. Selection of the pivot column: selection of the restriction variable which should be transformed

   • STEEPEST-UNIT-ASCENT: column including the absolute highest negative coefficient of the objective function
   • GREATEST-CHANGE: column including the absolute highest product of the most negative coefficient of the objective function and the lowest positive quotient of the right side and the element of the appropriate column

2. Selection of the pivot row: selection of the row including the smallest positive quotient of right side and the element of the pivot column
3. Pivot element: intersection of pivot row and pivot column
4. Exchange of non-basis-variable and basis-variable
5. Solving the simplex table by using calculation rules
6. Repeat step 1, if solution is not the optimum.

Calculation rules for simplex-tables

Pivot-element: ars* = 1/ars Pivot-row: arj* = arj/ars Pivot-column: ais* = - ais/ars Remaining elements: aij* = aij - arj*ais/ars =aij - ais arj*