Operational Research Notes > Mathematical Programming Notes

This is an extract of our **Or202.2 Mathematical Programming Course Notes** document, which
we sell as part of our **Mathematical Programming Notes** collection written by the top tier of
LSE students.

* The following is a more accessble plain text extract of the PDF sample above, taken from our Mathematical Programming Notes.
Due to the challenges of extracting text from PDFs, it will have odd formatting:
*

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.*