# Exam 3 part 2 Flashcards

What is linear programming?

General technique for solving optimization problems

What is the linear programming outline for max-flow problem?

input: G(V,E) with capacities ce > 0

m for every e in E

objective function: sum fsv

subject to:

for every e in E: 0 <= fe <= ce (flow has to be non negative and at most the edge capacity)

for every v in V - {s, t}

- sum wv in edge fwv = sum vz in edge fvz

(total flow into v has to equal the total flow out of v)

objective function is a max or a min of a linear function

And there are constraints on the variables

Give an example of a linear program

Company makes products A and B

How many of each to maximize profit?

- Each unit of A makes profit of $1

- Each unit of B makes profit of $6

Demand <= 300 units of A

Supply <= 700 hours working

A takes 1 hr to make

B takes 3 hr to make

x1 = units of A per day

x2 = units of B per day

So the linear program is expressed as the following:

max x1 + 6x2

s.t.

- 0 <= x1 <= 300

- 0 <= x2 <= 200

- x1 + 3x2 <= 700

The complete standard way:

max x1 + 6x2

s.t.

- x1 <= 300

- x2 <= 200

- x1 >= 0

- x2 >= 0

- x1 + 3x2 <= 700

we use this to construct a feasible region plotting the lines on a 2D graph with x1 being one axis and x2 being the other

We find the optimal point in this shaded region

How do we find the optimum in a linear program?

We find the maximum values of x1, x2, etc. all variables that result in the max or min value (check objective function) and satisfies the formula. We plot the resulting formula line through the credible region of the linear program given the constraints. We find the highest point on this line within the constraint region.

- optimum must lie at a vertex of the polygon shaded region

What are key issues or topics to remember with linear programs?

- integer points vs non integer points determine the optimum point
- LP vs ILP determine whether its P or not
- optimum points lie on corners or vertices of the polygon
- feasible region is convex and no nasty shapes

Provide a 3D example of a linear program

You can now make 3 products

A $1

B $6

C $10

demand:

A <= 300

B <= 200

C unlimited

Supply

<= 1000 total

A takes 1 hr

B takes 3 hrs

C takes 2 hrs

packaging <= 500 total

A takes none

B takes 1

C takes 3

Linear program:

max x1 + 6x2 + 10x3

s.t.

x1 <= 300

x2 <= 200

x1 + 3x2 + 2x3 <= 1000

x2 + 3x3 <= 500

x1, x2, x3 >= 0

What is the standard form?

n variables

x1 … xn

max x1c1 + x2c2 + …xncn

s.t.

a11x11 … a1nx1n < b1

am1x1 …amnxn < bm

x1..xn >= 0 (non negative)

Essentially

max c^T x

s.t.

Ax <= b

x >= 0

What is the equivalence you should remember for converting to standard form?

min c^Tx <=> max -c^Tx

a1x1 + … + anxn >= b <=> -a1x1 - … - anxn <= - b

What is the geometric region or view?

n vars -> n dimensions

n + m constraints

feasible region = intersection of n + m halfspaces = convex polyhedron

vertices = points satisfying n constraints with =

and

points satisfying m constraints with <=

What are polynomial algorithms for solving linear programs in polynomial time?

Ellipsoid algorithms and interior point methods

Simplex algorithm

- worst-case exponential time

- widely used on huge LPs

What is the Simplex algorithm?

We start at x = 0

look for neighboring vertex with higher objective value -> then move there and repeat

else output current vertex

ex) start at point (0,0,0)

keep moving to higher vertex values that result in higher profit from previous example

Explain the following:

max C^Tx

s.t.

- Ax <= b

- x >= 0

n variables

m constraints

This is a linear program in standard form where there are n variables and m constraints

x values that form the feasible region that satisfies the constraints forms a convex set

-> forms a convex polyhedron in m dimensions

m half spaces

What are the exceptions to an optimum being located at the vertex of the feasible region?

A) infeasible = feasible region is empty

ex) max 5x - 7y

s.t.

x + y <= 1

3x + 2y >= 6

x, y >= 0

(you have feasible regions that don’t intersect each other)

THIS DEPENDS ON THE CONSTRAINTS

B) unbounded = optimal is arbitrarily large

ex) max x + y

s.t.

x - y <= 1

x + 5y >= 3

x, y >= 0

The graph for the above is bounded at the bottom, but there is no line bounding the top and thus values in the feasible region can go up forever: we unbounded feasible points of x+y = c

BOUNDEDNESS DEPENDS ON THE OBJECTIVE FUNCTION

How do we check if an LP is feasible?

max C^Tx

s.t.

- Ax <= b

- x >= 0

Look at the LP in standard form

Ask, are there any x’s that satisfy the constraints? Or is the feasible region empty or not?

Make a new variable z

and add to

a1x1 + …anxn <= b

x1…xn >= 0

Take same constraint and z ->

a1x1 + …anxn + z <= b

x1…xn >= 0

There is always a solution to the above equation when z is added with a small enough z

But is there a solution when z >= 0?

We add new objective function where we maximize z

If the objective function original is optimized when z is negative, then we know that the original LP is infeasible

If we can optimize with z values greater than 0, then we know the original LP is feasible

Given the following:

max x1 + 6x2 + 10x3

s.t.

- x1 <= 300

- x2 <= 200

- x1 + 3x2 + 2x3 <= 1000

- x2 + 3x3 <= 500

- x1, x2, x3 >= 0

How do we check if the following is the upper bound?

(200, 200, 100) = 2400

We have the following:

y = (y1, y2, y3, y4)

given point (0, 1/3, 1, 8/3)

we do the following

y1x1 + y2x2 + y3x3 + y4x4 <=>

x1y1 + x2y2 + x1y3 + 3x2y3 + 2x3y3 + x2y4 + 3x3y4 <= 300y1 + 200y2 + 1000y3 + 500y4

you see we multiply the terms (y1, y2, y3, y4) with each of the contraints on both sides of the constrains equation and combine all results into 1 equation above

We know any feasible point x satisfies this inequality

x1y1 + x2y2 + x1y3 + 3x2y3 + 2x3y3 + x2y4 + 3x3y4 <= 300y1 + 200y2 + 1000y3 + 500y4

for any non negative y

we simplify to the following:

x1(y1 + y3) + x2(y2 + 3y3 + y4) + x3(2y3 + 3y4)

<= 300y1 + 200y2 + 1000y3 + 500y4

we plug in the given point (0, 1/3, 1, 8/3)

and get:

x1 + 6x2 + 10x3 <= 2400

this is exactly the objective function of the original LP

Therefore we’ve proven the upper bound

Once proving the upper bound for the LP, how do we find the constraints for the input y values?

We need the left hand side of the equation to be atleast the objective function

ex)

x1(y1 + y3) + x2(y2 + 3y3 + y4) + x3(2y3 + 3y4)

<= 300y1 + 200y2 + 1000y3 + 500y4

x1 + 6x2 + 10x3 <= 2400

thus for y:

y1 + y3 >= 1,

y2 + 3y3 + y4 >= 6 ,

2y3 + 3y4 >= 10

then we want to minimize

Min 300y1 + 200y2 + 1000y3 + 500y4