[PDF] Advanced Operations Research Techniques IE316 Lecture 4

View - Download Advanced Operations Research Techniques IE316 Lecture 4

Previous PDF

Next PDF

Advanced Operations Research Techniques

IE316

Lecture 4

Dr. Ted Ralphs

IE316 Lecture 41Reading for This Lecture

Bertsimas 2.2-2.4

1 IE316 Lecture 42The Two Crude Petroleum Example Revisited

Recall the

Two Crude Petroleum

example. We showed graphically that the optimal solution was an extreme point How did we figure out the coordinates of the optimal point? 2

IE316 Lecture 43Binding Constraints

Consider a polyhedron

P=fx2RnjAx¸bg

Definition 1.

If a vector

ˆx satisfies a

Tiˆx=bi

, then we say the corresponding constraint is binding

Theorem 1.

Let

ˆx2Rn

be given and let

I=fijaTiˆx=big

represent the set of constraints that are binding at ˆx . Then the following are equivalent:

There exist

n vectors in the set faiji2Ig that are linearly independent.

The span of the vectors

faiji2Ig is R n

The system of equations

a

Tix=bi;i2I;x2Rn

has the unique solution ˆx

If the vectors

fajjj2Jg for some

Jµ[1;m]

are linearly independent, we will say that the corresponding constraints are also linearly independent. 3

IE316 Lecture 44Basic Solutions

Consider a polyhedron

P=fx2RnjAx¸bg

and let

ˆx2Rn

be given.

Definition 2.

The vector

ˆx is a basic solution with respect to P if there exist n linearly independent, binding constraints at ˆx

Definition 3.

If ˆx is a basic solution and

ˆx2 P

, then ˆx is a basic feasible solution

Theorem 2.

If P is nonempty and

ˆx2 P

, then the following are equivalent: ˆx is a vertex. ˆx is an extreme point. ˆx is a basic feasible solution. 4

IE316 Lecture 45Adjacent Basic Solutions

Two distinct basic solutions

x and y are adjacent if there are n¡1 linearly independent constraints that are binding at both x and y If two adjacent basic solutions are also feasible, then the line connecting them is called an edge of the polyhedron. Note that the first algorithms we will study move through the polyhedron along its edges. 5

IE316 Lecture 46Some Observations

Note the immediate consequences of the previous results: 6

IE316 Lecture 47Polyhedra in Standard Form

For the next few slides, we consider the

standard form polyhedron

P=fx2RnjAx=b;x¸0g

Recall that any linear program can be expressed in this form.

We will assume that the rows of

A are linearly independent )m·n

Later, we will show that

any polyhedron in standard form can be reduced to this form What does a basic feasible solution look like here? 7 IE316 Lecture 48Basic Feasible Solutions in Standard Form In standard form, the equations are always binding.

To obtain a basic solution, we must set

n¡m of the variables to zero (why?).

We must also end up with a set of

linearly independent constraints Therefore, the variables we pick cannot be arbitrary.

Theorem 3.

Consider a polyhedron

P in standard form with m linearly independent constraints. A vector

ˆx2Rn

is a basic solution with respect to P if and only if

Aˆx=b

and there exist indices

B(1);:::;B(m)

such that:

The columns

A

B(1);:::;AB(m)

are linearly independent, and If i6=B(1);:::;B(m) , then

ˆxi= 0

8 IE316 Lecture 49Basic Feasible Solutions in Standard Form As a consequence of the previous theorem, we now know how to construct basic solutions for polyhedra in standard form. If the resulting solution is also nonnegative, then it is a basic feasible solution 9

IE316 Lecture 410Some Terminology

If ˆx is a basic solution, then

ˆxB(1);:::;ˆxB(m)

are the basic variables

The columns

A

B(1);:::;AB(m)

are called the basic columns Since they are linearly independent, these columns form a basis for R m

A set of basic columns form a

basis matrix , denoted B . So we have, x B=2 4x

B(1)...

x B(m)3 5 10

IE316 Lecture 411Basic Solutions and Bases

Given a basis matrix

quotesdbs_dbs21.pdfusesText_27

[PDF] adjacent vertices in graph theory

[PDF] adjacent vertices meaning in hindi

[PDF] adjectif possessif et demonstratif exercice pdf

[PDF] adjectif possessif french exercise pdf

[PDF] adjectif pour décrire le caractère d'une personne

[PDF] adjectif qualificatif exercice

[PDF] adjectif qualificatif pdf exercice

[PDF] adjectif verbal et participe présent

[PDF] adjectif verbal exercices

[PDF] adjectifs démonstratifs et pronoms démonstratifs exercices

[PDF] adjectifs démonstratifs exercices

[PDF] adjectifs et pronoms démonstratifs exercices pdf

[PDF] adjectifs possessifs et démonstratifs exercices

[PDF] adjective and adverb clauses worksheets with answers

[PDF] adjective and preposition list pdf