Linear Programming

LINEAR PROGRAMMING

ADVANCED FINANCIAL MATHEMATICS

Introduction

Classification

Linear and Non-linear  Static and Dynamic  Deterministic and Stochastic  Continuous and Discrete



Definition



Linear programming is a mathematical technique designed to help managers plan and make decisions relative to the tradeoffs necessary to allocate resources.

Examples

Scheduling school buses;  Allocating police patrol units;  Scheduling tellers at banks;  Selecting the product mix in a factory;  Determining the distribution system;  Developing a production schedule.



Properties





 

LP problems seek to maximize or minimize some quantity (usually profit or cost). We refer to this property as the objective function; The presence of restrictions, or constraints, limits the degree to which we can pursue our objective; There must be alternative courses of action to choose from; The objective and constraints must be expressed in terms of linear equations or inequalities.

The Problems

Formulating the problem

A simple case

Variables • x1 = number of Walkmans to be produced • x2 = number of Watch-TVs to be produced  Objective function (to be maximized) • profit = $7 x1 + $5 x2  First constraint (hours of electronic time) • 4 x1 + 3 x2 ≤ 240  Second constraint (hours of assembly time) • 2 x1 + 1 x2 ≤ 100  Nonnegativity constraints • x1, x2 ≥ 0



Formulating the problem

A general max case - Longhand



Maximize   c1 x1  c2 x2  ...  cn xn Subject to a11 x1  a12 x2  ...  a1n x n  b1 a21 x1  a22 x2  ...  a2n x n  b2 ...

am1 x1  am2 x2  ...  amn x n  bm





and

x j  0 ( j  1,2,...,n)

Formulating the problem

A general min case - Longhand





Minimize C  c1 x1  c2 x2  ...  cn xn Subject to a11 x1  a12 x2  ...  a1n x n  b1 a21 x1  a22 x2  ...  a2n x n  b2 ...

am1 x1  am2 x2  ...  amn x n  bm



and

x j  0 ( j  1,2,...,n)

Formulating the problem

A...