Scribd
Upload
188 views47 pages

Linear Programming

Linear programming is an optimization technique used to maximize or minimize a linear objective function subject to linear constraints. It can be applied to problems in business and engineering to determine how to maximize profits or efficiencies given constraints on available resources. Examples show how to find the minimum and maximum values of objective functions over defined constraint regions by analyzing the vertices. Key concepts include standard form, duality, and solution methods like the simplex method which uses pivot operations to iteratively transform the initial tableau into the optimal solution.

Uploaded by

Okibe Jeffery Ifere
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
188 views47 pages

Linear Programming

Linear programming is an optimization technique used to maximize or minimize a linear objective function subject to linear constraints. It can be applied to problems in business and engineering to determine how to maximize profits or efficiencies given constraints on available resources. Examples show how to find the minimum and maximum values of objective functions over defined constraint regions by analyzing the vertices. Key concepts include standard form, duality, and solution methods like the simplex method which uses pivot operations to iteratively transform the initial tableau into the optimal solution.

Uploaded by

Okibe Jeffery Ifere
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 47

Linear Programming

An optimisation problem of maximizing or


minimizing a linear objective function subject to
linear constraints

Linear Programming An
introduction
Businesses (engineers) use linear
programming to find out how to
maximize profit (efficiencies, traffic
flows) or minimize costs (losses,
congestions, etc). Most have
constraints on what they can use or
buy.

Linear programming
Examples

I1 , .I5 0

Linear programming
Examples

Linear programming
Examples

Find the minimum and maximum


value of the function f(x, y) = 3x - 2y.
We are given the constraints:

y2

1 x 5

yx+3

Linear Programming
Find the minimum and maximum
values by graphing the inequalities
and finding the vertices of the polygon
formed.
Substitute the vertices into the function
and find the largest and smallest
values.

1 x 5

8
7
6
5
4
3

yx+3

y2

2
1

Linear Programming
The vertices of the quadrilateral
formed are:
(1, 2) (1, 4) (5, 2) (5, 8)
Plug these points into the
function f(x, y) = 3x - 2y

Linear Programming
f(x, y) = 3x - 2y
f(1, 2) = 3(1) - 2(2) = 3 - 4 = -1
f(1, 4) = 3(1) - 2(4) = 3 - 8 = -5
f(5, 2) = 3(5) - 2(2) = 15 - 4 = 11
f(5, 8) = 3(5) - 2(8) = 15 - 16 = -1

Linear Programming
f(1, 4) = -5 minimum
f(5, 2) = 11 maximum

Find the minimum and maximum value


of the function f(x, y) = 4x + 3y
We are given the constraints:
y -x + 2
1
y
x+2
4
y 2x -5

y 2x -5

6
5

y -x + 2

3
2
1
1

1
x2
4

Vertices
f(x, y) = 4x + 3y
f(0, 2) = 4(0) + 3(2) = 6
f(4, 3) = 4(4) + 3(3) = 25

f( , - ) = 4( ) + 3(- ) =
7
3

1
3

7
3

1
3

28
3

-1 =

25
3

Linear Programming
f(0, 2) = 6 minimum
f(4, 3) = 25 maximum

Linear programming
Concepts and terminology

Linear programming problems may


not be solved easily

Many variables and constraints,


inequalities and equalities , nonnegativity, etc
Two special classes:

Standard maximum problem and


Standard minimum problem

All variables are constrained to ne nonnegative


All major constraints are inequalities

Linear programming
Concepts and terminology

Linear programming
Concepts and terminology

Linear programming
Concepts and terminology

Conversion to standard
form

All linear problems can be converted to standard


form as follows:
A minimum problem can be converted into standard
maximum problem by multiplying the OF by -1
Similarly, constraints of the form
can be changed to a form
Two other problems arise:

(1) some constraints may be equalities

May be removed by solving for some xj, where aij 0 and subsitute in
thr other constraints equations
This removes one constraint and one variable

(2) Some variables may not ne restricted to be


non-negative

An restricted variable xj, may be replace by two


restricted non-negative variables, such that
This adds one variable and two non-negativity
constraints

From computational point of view, situation (2)


should be avoided

Duality

To every linear problem there is a dual to


which it is intimately connected.

Theorems

Duality theorem

The pivot operation

The pivot operation

In tableu

Note: matrix A is transpose of


the numbers as they appear in
the original equations

Is like exchanging the positions of the


dependent and independent variables (from top
to bottom and vice versa)

If pivoting is continued, the inverse of the


matrix can be obtained

The simplex method

The simplex tableu may be written


as

The simplex method

The dual simplex method

The simplex method for the minimum problem

You might also like