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