Scribd
Upload
16 views8 pages

Optimality Conditions in Linear Programming

The document discusses optimality conditions for linear programming problems. It introduces the concepts of feasible directions, basic directions using the basis matrix, and reduced costs. It states that a basic solution is optimal if the reduced costs are all non-negative, and that an optimal basis must have a non-negative inverse and non-negative reduced costs.

Uploaded by

Astha Lohia
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views8 pages

Optimality Conditions in Linear Programming

The document discusses optimality conditions for linear programming problems. It introduces the concepts of feasible directions, basic directions using the basis matrix, and reduced costs. It states that a basic solution is optimal if the reduced costs are all non-negative, and that an optimal basis must have a non-negative inverse and non-negative reduced costs.

Uploaded by

Astha Lohia
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Optimality Condition

Optimization Methods and Applications

Minati De

Department of Mathematics, Indian Institute of Technology Delhi, India.

Lecture 8: Towards The Simplex Method

M. De Optimization Methods and Applications


Optimality Condition

Table of Contents

1 Optimality Condition

M. De Optimization Methods and Applications


Optimality Condition

Feasible Direction

Minimize c T x
Subject to Ax = b
x ≥ 0.

Feasible Direction
Let x be an element of a polyhedron P = {x ∈ Rn |Ax = b, x ≥ 0}.
A vector d ∈ Rn is said to be a feasible direction at x, if there
exists a positive scalar θ for which x + θd ∈ P.
Example: ?

M. De Optimization Methods and Applications


Optimality Condition

jth basic direction

dj = 1, di = 0, ∀i ∈
/ B, i 6= j
−1
dB = −AB Aj .
How do you obtain this?
Does it always guarantee that x + θd is a feasible solution?

M. De Optimization Methods and Applications


Optimality Condition

Reduced cost

Let x be a basic solution, let AB be an associated basis matrix,


and let cB be the vector of costs of the basic variables.
Reduced cost cˆj
For each j, we define the reduced cost cˆj of the variable xj
according to the formula

cˆj = cj − cBT A−1


B Aj

M. De Optimization Methods and Applications


Optimality Condition

Reduced Cost

For each basic variable xb(i) what is the reduced cost cB(i)
ˆ ?

M. De Optimization Methods and Applications


Optimality Condition

Optimality Condition

Theorem
Consider a basic solution x associated with a basis matrix AB , and
let ĉ be the vector of reduced costs.
(a) If ĉ ≥ 0, then x is optimal.
(b) If x is optimal and nondegenerate, then ĉ ≥ 0.
Proof?

M. De Optimization Methods and Applications


Optimality Condition

Optimal Basis

Optimal Basis
A basis matrix AB is said to be optimal if:
(a)
A−1
B b ≥ 0,

and
(b)
ĉ T = c T − cBT A−1
B A ≥ 0.

M. De Optimization Methods and Applications

You might also like