Someone recently bought our

students are currently browsing our notes.

X

Or202.2 Mathematical Programming Course Notes

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.

More Mathematical Programming Samples