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

Quote
Change will not come if we wait for some other person, or if we wait for some other time
Barack Obama
Categories
Archive ↓