Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment No 2- CS 538, S2023

Date Due: Feb 19th, 2023

1. Design the dual of the following Linear Problem:         max cT x

such that

ai(T)x ≤ bi ,   1 ≤ i ≤ m\

aj(T)x = bj ,   m\ + 1 ≤ j ≤ m

xk  ≥ 0, 1 ≤ k ≤ r

where x = (x1 ,x2 . . . xn ),x ∈ Rn

2. Show that all linear programs can be expressed as       min cT x

Ax = b

x ≥ 0

where x = (x1 ,x2 . . . xn ),,x ∈ Rn .

3. We consider an attacker on your flow network.   Consider a bipartite network N(E,d) where E  = {e1 ,e2 , ··· ,em } . We denote your (the designer’s) budget by BD . The flow design is represented by a vector f ∈ [0, 1]m  with the requirement 对 f[i] = 1, where f[i] is the flow amount on edge ei . For each edge ei  with flow amount f[i], the designer’s cost is d[i]f[i]. We say a design f is within budget if 对 d[i]f[i] ≤ BD .  An attack is a vector X ∈ [0, 1]m  indicating the attack on edges, where X[i] denotes the attack, or attack level, on edge ei , the fraction of flow captured on ei .

The adversary’s benefit is the sum of flow she captures over the bipartition and defined as 对j(k)=1 f[j] · X[j]. Your goal is to minimize the attacker’s benefit.

Given the adversary’s strategy X[j] as fixed and provided, describe a linear program to optimize the designer’s strategy and find its dual.

4. Set up a linear program for determining a shortest path in a weighted directed graph. Find the dual of this LP.

5. Complete the proof from Class: Compute the dual of linear program for the maximum flow problem using path structures instead of flow conservation at vertices.  Use variables for flows on s-t paths, where a path is the sequence of edges from s to t.  Explain how this can be used to prove the strong duality of the maximum flow problem.

6. A system Ax ≤ b,x ∈ Rn ,A ∈ Rm ×n  may be infeasible, i.e. has no solution. Show that this is true iff there exists a y ∈ Rm  such that AT y = 0,bT y < 0, and y ≥ 0.