Someone recently bought our

students are currently browsing our notes.

X

## Mg211.2 Mathematical Programming Notes This is an extract of our Mg211.2 Mathematical Programming document, which we sell as part of our Operational Research Methods (MG211) Notes collection written by the top tier of London School Of Economics students.

The following is a more accessble plain text extract of the PDF sample above, taken from our Operational Research Methods (MG211) Notes. Due to the challenges of extracting text from PDFs, it will have odd formatting:

MG211: Operational Research Methods

MG211.2: MATHEMATICAL PROGRAMMING Lecture 1: Examples of Linear Programs Mathematical Programming: Using mathematical tools for optimally allocating and using limited resources when planning (programming) activities (e.g. how to invest in a portfolio of stocks while maximising profits and keeping risk under threshold; assigning nurses optimally in a hospital to maximise coverage/minimise total staff needed) Linear Programming:

* Simplest of mathematical programming models

* Hundreds of practical applications

* Started around World War 2 to model centrally managed Soviet economy and model logistics problems arising from the war effort and subsequent industrial developments in the US

* The Simplex Algorithm is the first effective algorithm fro solving linear programming problems Example 1: A Production Problem (Steps hold for all formulations) Maximise profit from producing computers subject to:
- Number of components used does not exceed availability
- Production does not exceed estimated demand
- Orders already placed are satisfied 1) Decide on units and decision variables
- Profit measured in millions of PS; numbers of computers and components are measured in thousands
- Decisions variables defined as xj = number of thousands of laptops of type j to be produced; j = 1,....,5) 2) Derive objective function
- 2x1 + 1.4x2 + x3 + 0.8x4 + 0.5x5 3) Define constraints (can distinguish between resource and non-negative constraints)
- CPU Constraint: x1 + x2 + x3 + x4 + x5 [?] 8
- SSD Constraint: x1 + 0.7x2 + 0.3x4 [?] 3
- Memory Board Constraint: 6x1 + 4x2 + 4x3 + 2x4 + 2x5 [?] 14
- Estimated Demand: x1 + x2 [?] 5; x3 + x4 + x5 [?] 4
- Orders: x2 [?] 0.7; x5 [?] 0.7
- Non-Negativity Constraint: x1 + x2 + x3 + x4 + x5 [?] 0 (i.e. cannot produce a negative number of computers) 4) Solve using linear programming solver (must ensure result is feasible realistically i.e. positive integer) Example 2: Fixed Income Portfolio Maximise expected return subject to 3 constraints:
- The worse case return of the portfolio must [?] 8%
- The average duration of the portfolio must be at most 6
- Because of diversification requirements, at most 40% of the total amount invested can be invested into a single bond 1) Decision variables defined as xj = fraction of total budget invested in Bond j (j = 1,...,4); e.g. x1 = 0.2 means PS20,000 in bond 1 2) Maximise Expected Returns: 0.13x1 + 0.08x2 + 0.12x3 + 0.14x4 3) Constraints:
- Budget Constraint: x1 + x2 + x3 + x4 [?] 1

MG211: Operational Research Methods

- Worst Case Constraint: 0.06x1 + 0.08x2 + 0.10x3 + 0.09x4 [?] 0.08
- Duration Constraint: 3x1 + 4x2 + 7x3 + 9x4 [?] 6
- Diversification Constraint: x1/(x1 + x2 + x3 + x4) [?] 0.40 however this is not a linear function should be written as 0.6x1 - 0.4x2 - 0.4x3 + 0.4x4 [?] 0 (re-write for all bonds) 4) Solve using linear programming solver (must ensure result is feasible realistically i.e. positive integer) Assumption of LP Model:

* Variables represent quantities that are homogenous and infinitely divisible

* No (dis)economies of scale LP formulation requires choosing appropriate decision variables however choose not unique - different decision variables lead to different formulations

MG211: Operational Research Methods

Lecture 2: Feasibility, Optimality, Unboundedness Feasible Points: A point x* is feasible for a linear program if it satisfies all its constraints Feasible Region: Set of all feasible points of a linear programming problem Optimal Solution: If maximisation problem - feasible point whose value is the largest possible among all feasible points; if minimisation problem - feasible point whose value is the smallest possible among all feasible points Drawing the Feasible Region 1) Check for non-negativity (usually the case) - if non-negative indicate (using dashes) negative quadrants are not being considered 2) Draw line of first constraint (i.e. for constraint 2x1 + x2 < 10; 2x1 + x2 = 10) 3) Decide which side of line feasible region is part of; indicate which side is not being considered 4) Draw all further constraints; shade in area which remains feasible Objective function can be represented by contour lines i.e. if function is 2x1 + 8x2, contour lines are 2x1 + 8x2 = 8 (x1 = 4; x2 = 0), 2x1 + 8x2 = 16 (x1
= 8; x2 = 0) etc. infinite number of parallel contour lines Finding the Optimal Solution 1) Draw feasible region 2) Draw contours 3) Slide contour upwards in direction of increase of objective function (dependent until whether its a maximisation/minimisation problem); highest/lowest point where it still intersects feasible region ---> optimal solution Multiple Optima: A problem which has more than one optimal solution Infeasible Problem: A problem with no optimal solution Unbounded Problems: There exist feasible solutions arbitrarily large value in the object function - practically normally means there is a mistake in problem (missing constraint) All LP Problems either: 1) Have an optimal solution 2) Infeasible 3) Unbounded Basic Solutions and Extreme Points Independent Constraints: Given system of n linear inequalities in n variables, n inequalities independent if there exists a unique solution satisfying all n of them at equality In two dimensions a corner point is one at the intersection of 2 non-parallel inequalities Basic Point: A point satisfying at equality n independent constraints from the system (given system of constraints in n variables) Extreme Points: A point that is both basic and feasible for a system of linear constraints
Whenever an LP admits an optimal solution, there exists some optimal solutions that is an extreme points in the feasible region
Some non-extreme points may also have optimal value but there is always at least an extreme point on the optimal contour

MG211: Operational Research Methods

Lecture 3: Optimality To prove optimality must prove that ever feasible solution satisfies derived inequality Creating Derived Inequality to Prove Optimality 1) Ensure constraints are uniform by checking all are the same type (all [?] or [?] etc.) 2) If constraints are not uniform, multiply by -1 to make uniform 3) Given 'uniform constraints' obtain derived inequality by multiplying first row in brackets (x1 terms) with y terms, then x2 terms with y terms to creative 2 inequalities
Derived inequality satisfied by all points satisfying original constraints
Derived constraint should pass through intersection of initial constraints 4) Solve inequality - if all values of yi* are non-negative then optimality is proved (given constraint is [?] for maximisation problem - refer to table below!); otherwise try different combination of n inequalities defining x* (if none work then x* is not optimal) For = type constraints, free multipliers can be used (positive, negative or 0) Dual Variables: Variable yi associated to constraints are dual variables, for maximisation problems dual variables must follow conditions below:

Buy the full version of these notes or essay plans and more in our Operational Research Methods (MG211) Notes.