Operational Research Notes > Lse Operational Research Notes > Mathematical Programming Notes

Or202.2 Mathematical Programming Course Notes

This is a sample of our (approximately) 21 page long Or202.2 Mathematical Programming Course Notes notes, which we sell as part of the Mathematical Programming Notes collection, a 1st Class package written at LSE in 2011 that contains (approximately) 42 pages of notes across 10 different documents.

Learn more about our Mathematical Programming Notes

Or202.2 Mathematical Programming Course Notes Revision

The following is a plain text extract of the PDF sample above, taken from our Mathematical Programming Notes. This text version has had its formatting removed so pay attention to its contents alone rather than its presentation. The version you download will have its original formatting intact and so will be much prettier to look at.

Lecture 1: Introduction to Linear Programming 06 October 2010

Topics

• Introduction to linear programming

• General mathematical structure of a linear program

• Defined upper bound constraints

• Assumptions of linear programming

Reading

• Taha (Chapter 2.1)

Introduction to Linear Programming

• Linear programming refers to planning rather than software programming

• We ask some questions to construct the linear programming solution:

• Who owns the problem?

• What is the objective of the owner of the problem?

• What restricts the profit of the owner?

• What can the owner decide to do?

• A linear programming problem is to determine the values of the variables that maximise or minimise a linear objective function

• Non-Negativities = The constraints that ensure that a negative amount can not be produced

General Mathematical Structure of a Linear Program Linear Programming Problem in Terms of Linear Relations

• A linear programming problem can be expressed in terms of linear relations:


= The number of variables
□ There are non-negativity constraints
□ There are upper bound constraints
 The value of the upper bound might be infinity
= The number of resource constraints means a mixture of all inequality constraints

Linear Programming Problem in Terms of Matrix Algebra
 A linear programming problem can also be expressed in terms of matrix algebra:

is an -vector of the coefficients of the objective function is an -vector of the variables is an matrix of the resource constraints means a mixture of all inequality constraints is an vector of the coefficients of the right hand sides of the resource constraints is an vector of the coefficients of the upper bounds

is a vector of zeros





Defined Upper Bound Constraints
 Upper Bound Constraint = Special kind of resource constraint which has the form of the inequality Assumptions of a Linear Programming Problem
 There are 3 assumptions a linear programming problem makes:
 The variables are continuous
 The resources are homogeneous and infinitely divisible
 There are no economies or diseconomies of scale

Course Notes Page 1

Key Points

• Constructing linear programming problems

• Mathematical structure of problems

• Assumptions of linear problems (3)

Definitions

• Non-Negativities = The constraints that ensure that a negative amount can not be produced

• Upper Bound Constraint = Special kind of resource constraint which has the form of the inequality

Lecture 2: Feasibility 13 October 2010

Topics

• Feasible regions

• Is a point feasible?

• Multiplying a constraint by -1

• Equality constraints

• Extreme points

• Effective constraints

Reading

• Taha (Chapter 2.2)

Feasible Regions
○ Feasible Region = All the points that satisfy the conditions
○ We can graph the constraints so that we can see the feasible region
○ Redundant constraints are difficult to detect without graphs
○ But they are not relevant and we don't need to test for them
○ We can take a point and test to find which side of the line is the feasible region Is A Point Feasible?
○ For a point to be feasible, it must satisfy all the constraints
○ An LP can have:
○ No solution
○ 1 solution
○ Many (infinite) solutions
○ Because we have a continuous space Multiplying A Constraint By -1
○ We can multiply a >= constraint by -1 to convert it to a <= constraint so that all constraints have the same inequality Equality Constraints
○ An equality constraint can be expressed as two constraints, one of which can be multiplied by -1 so that we have two <= constraints Extreme Points
○ Extreme points are also known as corner solutions
○ Basic Point = A point of an n-dimensional space which is the point of intersection of n independent equalities
○ Extreme Point = A feasible basic point Is a Point an Extreme Point?
○ An LP can be solved by only checking the extreme points
○ Convexity = A region is convex if all the lines joining any two feasible points in the region are all feasible Effective Constraints
○ Effective Constraint = Resource constraints that define a basic point

Course Notes Page 2

Key Points

• Redundant constraints

• Finding feasible region

• Is a point feasible?

• Solutions of LP (3)

• Multiplying constraints by -1

• Extreme points

• Basic points

• Convexity

• Effective constraints

****************************End Of Sample*****************************

Buy the full version of these notes or essay plans and more in our Mathematical Programming Notes.