The Classical Simplex Method and calc in R Science 23.09.2015

Introduction

Linear programming (LP) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. source

I.e. linear programming is a technique in which we maximize or minimize a function. Every linear programming problem can be written in the following standard form

subject to

Here is a vector of n unknowns, with n typically much larger than m, the coefficient vector of the objective function, and the expression signifies for . For simplicity, we assume that rank A = m, i.e., that the rows of A are linearly independent.

The Simplex Method (developed by George Dantzig in 1946) is the earliest solution algorithm for solving LP problems. It is an efficient implementation of solving a series of systems of linear equations. By using a greedy strategy while jumping from a feasible vertex of the next adjacent vertex, the algorithm terminates at an optimal solution.

Simplex method uses row operations to obtain the maximum or minimum values of function. The simplex method moves from one extreme point to one of its neighboring extreme point.

Typical uses of the simplex algorithm are to find the right mix of ingredients at the lowest cost (the goal). If the ingredients are food, the constraints would be having at least so many calories, so much protein, fats, carbohydrates, vitamins, minerals, etc.

Terminology

• the variables you set to 0 are called nonbasic variables
• the variables you solve for are called basic variables
• a solution is called a basic solution
• a solution that represents a corner point (no negative slacks) is called a basic feasible solution

Calculation

About R.

Maximize subject to the following constraints:

# install.packages("linprog")

library("linprog")

c = c(3,2)
b = c(30,60)
A = rbind(c(1,2), c(5,1))
res = solveLP(c, b, A, maximum=TRUE)
print(res)

Results of Linear Programming / Linear Optimization

Objective function (Maximum): 50 

Iterations in phase 1: 0
Iterations in phase 2: 2
Solution
  opt
1  10
2  10

Basic Variables
  opt
1  10
2  10

Constraints
  actual dir bvec free     dual dual.reg
1     30  <=   30    0 0.777778       18
2     60  <=   60    0 0.444444       45

All Variables (including slack variables)
    opt cvec min.c     max.c      marg marg.reg
1    10    3   1.0 10.000000        NA       NA
2    10    2   0.6  6.000000        NA       NA
S 1   0    0  -Inf  0.777778 -0.777778       18
S 2   0    0  -Inf  0.444444 -0.444444       45

Useful links

• How to maximize function by graph and simplex method, line by line.
• Example of the Simplex Method (How many souvenirs of each type should company make per day in order to maximize its profit?)
• Example of the Simplex Method (How to determine the best mix of three products should owner of a shop produces in order to maximize its profit?)
• Introduction to the Simplex Method
• Math for Business and Economics Lectures