Or202.2 Mathematical Programming Course Notes

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 boundsis 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 

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