Linear Programming: Problems, Simplex Method, and LINGO Resolution

Unit 6: Linear Programming

Mathematics II. Grado Administración y Dirección de Empresas.

1. Linear programming problems.
2. Basic results.
3. The simplex method.
4. Finding an initial basic feasible solution.Linear Programming

Koopmans, Dantzig and Kantorovich (1970).

ER DE SE U u

Mathematical Elements of the XX Century

One of the most important mathematical elements of the XX century. Originated in 1947.

Precedents in Linear Programming

Precedents: Linear systems of inequalities (Fourier 1926). Fundamental theorems of duality (von Neumann and Morgenstern, 1928, 1944). Kantorovich (1939) (five-year plans of the Soviet Union). Dantzig (1947) The simplex method Nobel 1975 to Kantorovich and Koopmans "for their contributions to the theory of optimum allocation of resources Khachian (1979), Karmarkar (1984): ellipsoid method.A production problem

AD DE SEVILLA

Production Planning Problem

You want to plan production in a certain area. The labor, energy, and capital needs, as well as the unit profits, appear in the following table. You have 1,000 units of energy and 600 units of capital available, and you need to employ at least 500 units of labor.

Production Problem Data

	Sector 1	Sector 2	Limitation
Labor	4	2	500
Energy	2	5	1000
Capital	2	2	600
Unit profit	1	2

X1: production units in sector 1. X2: production units in sector 2.

Profit Maximization Formulation

The profit maximization problem: Max ×1 + 2×2 s.t. 4×1 + 2×2 ≥ 500 2×1 + 5×2 ≤ 1000 2×1 + 2×2 ≤ 600 X1, X2 ≥0Problem Formulation

General Problem Formulation

Max z(x) = C1X1 + C2×2 + . . . + CnXn s.t. a11×1 + a12×2 + .. . + ainXn ≤ b1 a21×1 + a22×2+ ... + a2nXn ≤ b2 . . . . . . ... a1X1 + ai2x2 + ... + ainXn < bi . ... . . . am1X1 + am2X2 + ... + amnXn < bm X1, X2, . . . , Xn ≥0

Matrix Notation for Linear Problems

Max ctx s.t. Ax < b A E Mmxn x ≥ 0 c E IR": the vector of coefficients of the objective function. AE Mmxn: the matrix of technical coefficients. b E IRm: the vector of independent terms of the constraints (RHS, Right-Hand-Side coefficients).

Example Problem in Matrix Form

Max ×1 + 2×2 4×1 + 2×2 ≥ 500 2×1 + 5×2 ≤ 1000 2×1 + 2×2 ≤ 600 X1, X2 ≥0 Max (1 2) ( X1 X2 -4 -2 - s.t. 2 2 5 2 ≤ ) ( X1 X2 -500 1000 600 - X1, X2 ≥0 ER n DE SE u s.t.ER DE SE U u

Canonical and Standard Forms

Canonical Form

Canonical form: Max cx s.t. Ax ≤ b x ≥ 0 Min cx s.t. Ax > b x ≥0

Standard Form

Max (Min) cx s.t. Ax = b x ≥ 0

Transformations for Standard Form

Transformations: ai1x1 + . . . + ainXn ≤ bi >a;1x1 + ... + ainXn + h; = bi, with hi ≥ 0. a1X1 + ... + ainXn > bi >> ai1X1 + ... + ainXn - hi = bi, with hi > 0. hi: slack variables. a;1x1 + ... + ainXn = bi ⇐⇒ ai1x1 + · · · + ainXn ≥ bi a;1×1 + · · · + ainXn ≤ bi > xi ≤ 0 } Xi = - yi with yi ≥0. free xi > Xi = yi - Zi with yi, zi ≥0. Standard form:ER AD UNI 1 DE SEVILLA

Example: Standard and Canonical Forms

Example For the problem: Max ×1 + 2×2 s.t. 4×1 + 2×2 ≥ 500 2×1 + 5×2 ≤ 1000 2×1 + 2×2 ≤ 600 X1, X2 2 0

Standard Form Conversion

Standard form: Max x1 + 2×2 s.t. 4×1 + 2×2 - X3 = 500 2×1 + 5×2 + ×4 = 1000 2×1 + 2×2 + ×5 = 600 X1, X2, X3,X4, X5 ≥0

Canonical Form Conversion

Canonical form: Max ×1 + 2×2 s.t. -4×1 - 2×2 ≤ -500 2×1 + 5×2 ≤ 1000 2×1 + 2×2 ≤ 600 X1, X2 ≥0 ER n DE SE u

Characteristics of Linear Problems

What is special about linear problems? Regarding convexity: The objective function is both convex and concave. The feasible set is convex (it consists of the intersection of half-spaces and/or hyperplanes). K-T points provide the global optima. It is possible that an optimal solution may not exist. It is possible that optimal solutions may not be unique. Vz(x) = c for all x € IRn. The optima lie on the boundary of the feasible sets (vertices, edges, facets ... of the feasible polytope).Graphical resolution

Graphical Resolution of a Linear Problem

Max x1 + 2x2 s.t. 4×1 + 2×2 ≥ 500 2×1 + 5×2 ≤ 1000 2×1 + 2×2 ≤ 600 X1, X2 ≥0 Vz(X1, X2) = c = ( 2) 2 ER DE SE n u 2x1 + 5x2 ≤1000 S 2x1 + 2x2 ≤600 4x1 + 2x2 ≥ 500 +* S Optimal solutions: different cases

Optimal Solution Cases

ER n DE SE u v* r* ** S 1 y*

Types of Optimal Solutions

• Optimal solution: edge
• A unique optimal solution
• Optimal solution: edge
• Optimal solution: non-bounded edge
• There is no optimal solution
• There is no feasible solutionBasic results

Basic Results in Linear Programming

ER DE SE n u

Local and Global Optima

Proposition In a linear programming problem, a local optimum is always a global optimum. Proof: If x* is a local optimum, then it fulfils K-T necessary conditions. Since linear problems meet convexity conditions, it follows from the sufficient condition of global optimality that x* is a global optimum.Basic results

AD DE SEVILLA 1

Convexity of Optimal Solutions Set

Proposition The set of optimal solutions of a linear problem is a convex set. Proof: Consider a maximization linear programming problem, Max ctx s.t. x EX · The feasible set, X, is a polytope (intersection of half-spaces and/or hyperplanes). Denote by S* the set of optimal solutions of the problem. S* may be empty (the empty set is considered to be convex). If S* is non-empty, then x* E X exists such that ctx* = z* > ctx for all x E X. The set of all optimal solutions can be described as S* = {x EX : c'x = z*}. This set is a convex set since it is the intersection of X (which is convex) with the hyperplane ctx = z *.Extreme points

Extreme Points in Convex Sets

ER n DE SE u

Definition of Extreme Point

Definition Let S C IR" be a convex set. A point x* E S is an extreme point of S if #x, y € S, x, y / x* such that x* = Xx+ (1 - X)y with À € (0,1). Examples of extreme points. When the convex set is defined by linear equations and/or linear inequalities, the extreme points are also called vertices. Polytopes have a finite number of extreme points.Basic results

ER DE SE U u -L

Optimal Solutions and Extreme Points

Theorem If a linear programming problem has an optimal solution, then at least one of the extreme points of the feasible set is an optimal solution. This result is relevant since it permits us to narrow the search of optimal solutions to the extreme points of the feasible set. Polytopes have a finite number of extreme points. If it is possible to identify the extreme points of the feasible set, theoretically the problem should be solved. Since the set of optimal solutions is convex, then once the optimal extreme points are determined, the whole set of optimal solutions is identified. In practice, the identification of extreme points in a linear problem is not straightforward. Moreover, the number of extreme points considerably increases when the number of variables and the number of constraints increase.How to identify extreme points: Basic feasible solutions

Identifying Extreme Points: Basic Feasible Solutions

Consider a linear problem in standard form: ER UNI DE SE u Max (Min) s.t. Ax = b x ≥ 0 cx where A E Mmxn.

Basic Solution Definitions

Ax = b is a system of m linear equations in n variables (assume m < n, rank (A) = m). Definitions A basic solution to Ax = b is obtained by setting n - m variables equal to 0 and solving for the values of the remaining m variables. Any basic solution in which all the variables are nonnegative is a basic feasible solution (BFS). Any solution to Ax = b with non-negative variables is a feasible solution.

Example of Basic Feasible Solution

×1 + X2 + X3 = 6 ×2 + X4 = 3 X1, X2, X3, X4 ≥0 Indicate a basic feasible solution, a basic solution that is not feasible, and a feasible non-basic solution.Basic feasible solutions

ER AD UN DE SE

Basic Solutions and Matrices

Every basic solution x E IR" is associated to a square sub-matrix B E Mmxm with rank (B) = m. called a basic matrix. If B is formed of the first m columns of A, then A can be written as A = [B] N], where N E Mmx(n-m) . If x E IR" is a basic solution associated to B, then x = − XB XN , where xN = 0 and xB = B-1b. If x E IR" is a basic feasible solution associated to B then xB = B-1b > 0. A basic feasible solution, x E R", is called non-degenerated if xB > 0.

Illustrative Example with Columns of A

×1 + X2 + X3 = 6 ×2 + ×4 = 3 X1, X2, X3, X4 ≥0 ( 0 1 1 0 1 0 1 Denote by Pj, j = 1, ... , 4, the columns of A. B= ( 1 ) 1 is a basic matrix. 0 1 B = {P1, P2}. (3, 3, 0, 0) is the corresponding basic solution. {P1, P3} does not constitute a basis. 1 > B' = ( 1 0 1 ) is a basic matrix. B' = {P2, P4}. (0,6, 0, -3) is the corresponding basic solution. ) / A = 1Basic feasible solutions and extreme points

A UN DE SEV VILLA

Theorem: Extreme Points and BFS

Theorem A point in the feasible set of a linear programming problem is an extreme point if and only if it corresponds to a basic feasible solution. ×1 + ×2 ≤ 6 ×2 ≤ 3 ×2 + X4 = 3 X1, X2 ≥0 X1, X2, X3, X4 ≥0 ×1 + X2 + X3 = 6 X2 (3,3) (0,3) (6,0) x1 (0,0) Bases are formed of two columns. The basic feasible solutions are: (0,0,6,3), (6,0,0,3), (3,3,0,0), (0,3,3,0). They are all non-degenerated. (0, 6,0,-3) is a basic non-feasible solution. > (1,1,4,2), (3,0, 3,3) are feasible solutions that are non basic.Degenerate basic feasible solutions

Degenerate Basic Feasible Solutions

ER DE SE n u ×1 + ×2 ≤ 6 X2 < 3 ×2 + ×4 = 3 ×1 ≤ 6 ×1 + ×5 = 6 X1, X2 ≥0 X1, X2, X3, X4, X5 ≥0 X2 (3,3) (0,3) (6,0) x1 (0,0)| ×1 + X2 + X3 = 6 Bases are formed by three columns. Basic feasible solutions have 5 components, at least 2 are null: (0,0,6,3,6), (6,0,0,3,0), (3,3,0,0,3), (0,3,3,0,6). > (6,0,0,3,0) is a degenerate basic feasible solution. It can be associated to several bases: { P1, P2, P4}, {P1, P3, P4} and { P1, P4, P5}. Graphically, the extreme point (6,0) is the intersection of 3 hyperplanes (and only 2 are needed to determine a vertex).Example

AD DE SEVILLA

Example: Production Problem with Constraints

Max 3×1 + 2×2 s.t. 2×1 + ×2 ≤ 100 ×1 + ×2 ≤ 80 ×1 ≤ 40 X1, X2 2 0 21=40 (20,60) (40,20) (40) 2+22=80 2x1+2=100

Standard Form of the Example Problem

Standard form: Max 3×1 + 2×2 s.t. 2×1 + ×2 + X3 = 100 ×1 + ×2 + X4 = 80 ×1 + ×5 = 40 X1, X2, X3, X4, X5 ≥0 Basic solutions have 5 components, 3 of which are basic variables, and 2 of which non-basic. There are 10 different ways to select the columns of A to form a basis ( 5 =10). 3 ) 1 1 0 0 A = 1 01 0 1 2 1 0 0 0 1ER DAD UNIV DE SEVILLA

Analyzing Basic Solutions for the Example

The basic solution associated to B = { P1, P2, P3} is obtained setting xN = 0 (x4 = 0, x5 = 0) and XB = ( X1 X2 X3 ( 2 1 0 1 1 0 1 1 0 -1 100 80 40 =( 40 -20 40 . (40, 40, -20, 0, 0) is a basic non-feasible solution. It does not correspond to an extreme point of the feasible set. the basic solution associated to B = {P1, P2, P5} is obtained setting xN = 0 (x3 = 0, x4 = 0) and - X1 1 100 0 1 1 1 2 0 1 0 80 40 =( 20 20 60 . XB ( -1 X2 X5 = The basic solution associated to B = {P3, P4, P5} is obtained stating xN = 0 (x1 = 0, x2 = 0) and 1 0 1 0 80 40 100 0 1 0 0 0 40 100 80 = . XB = (0, 0, 100, 80, 40) is the basic feasible solution. (0,0) is the corresponding extreme point. To which basis does the extreme point (40, 0) correspond? (20, 60, 0, 0, 20) is a basic feasible solution. (20, 60) is the corresponding extreme point. - -1 ( X3 X4 X5 / = - =AD DE SEVILLA

Production Problem: Standard Form and Bases

A production problem Max X1 + 2×2 s.t. 4×1 + 2×2 ≥ 500 2×1 + 5×2 ≤ 1000 2×1 + 2×2 ≤ 600 X1, X2 ≥0 x2 = (125/4, 375/2) x= (500/3, 400, S x = (125,0)

Standard Form for Production Problem

Standard form: ×1 + 2×2 Max s.t. 4×1 + 2×2 - X3 = 500 2×1 + 5×2 + ×4 = 1000 2×1 + 2×2 + ×5 = 600 X1, X2, X3, X4, X5 ≥0 Basic solutions are 5-component vectors, 3 of which are basic variables and 2 of which are non-basic. There are 10 different ways to select the columns of A to form a basis ( 5 3 = 10). 4 A = 2 2 2 5 -1 0 0 0 1 0 2 0 0 1