# Linear Programming Flashcards

How do you turn a max LP problem into a Min one(or vice versa?)

Just multiply the coefficients of the objective function by -1

How?

How to change an equality constraint into inequalities?

How to deal with a variable x that is unrestriced in sign?

How can a generic LP be expressed using matrices?

Describe the max flow problem in terms of a graph.

define its properties

What its relation to LP - what constraints we have?

- What does the simplex algorithm do?*
- where does it start and what it does with each iteration?*
- define the path from s to t, define its edges, how can each kind of edge increase the stream?*

It starts with zero flow.

With each iteration it tries to find a shortest path from s to t. then, it tries to maximize the stream.

This path is constisted of two kinds of edges (u,v):

(u,v) is in the original network and is not yet in max capacity

the reverse (v,u) is in the original netwrok, and there is some flow along it.

In the first case: f can be increased no more than c(u,v)-f(u,v)

In the second case: f can be increased up to f(v,u) additional units

Define an (s,t)-cut

prove

How can you turn a bipartite matching into a max flow program and then to a LP one?

*Write in matrix form the dual LP*

Write the Duality theorem

NOTE: in the dual, if we have **equality** in the primal, the y’s in the **dual** aren’t restricted to be non-negative.

Which property regarding to **zero games** is suprising?

Explain

How should Row choose its strategy if he nows Colums will choose the best **pure solution** he can?

*For fixed x1 and x2, write the LP of the attached image*

then how can Row maximize the minimal value of Column

Write the Max of Column if he chooses first the strategy