# CS计算机代考程序代写 matlab algorithm Analysis of Algorithms

Analysis of Algorithms

V. Adamchik CSCI 570 Spring 2020

Lecture 11

University of Southern California

Linear Programming

Reading: chapter 8

Linear Programming

In this lecture we describe linear programming that is used to express a wide variety of different kinds of problems. LP can solve the max-flow problem and the shortest distance, find optimal strategies in games, and many other things.

We will primarily discuss the setting and how to code up various problems as linear programs.

Solving by Reduction

Formally, to reduce a problem Y to a problem X (we write Y ≤p X) we want a function f that maps Y to X such that:

• f is a polynomial time computable

• ∀instance y ∈ Y is solvable if and only if f(y) ∈ X is solvable.

A Production Problem

A company wishes to produce two types of souvenirs: type-A will result in a profit of $1.00, and type-B in a profit of $1.20.

To manufacture a type-A souvenir requires 2 minutes on machine I and 1 minute on machine II.

A type-B souvenir requires 1 minute on machine I and 3 minutes on machine II.

There are 3 hours available on machine I and 5 hours available on machine II.

How many souvenirs of each type should the company make in order to maximize its profit?

A Production Problem

Type-A

Type-B

Time Available

Profit/Unit Machine I Machine II

$1.00 2 min 1 min

$1.20 1 min 3 min

180 min 300 min

A Linear Program

We want to maximize the objective function subject to the system of inequalities:

200 100

A Production Problem y

2x + y ≤ 180 x +3y ≤ 300 x≥ 0

y ≥0

100 200 300

x

A Production Problem

We want to find the feasible point that is farthest in the “objective” direction P=x + 1.2 y

We can see that P is maximized at the vertex C(48, 84) and has a value of 148.8

y 200

100

S

2x + y ≤ 180 x + 3y ≤300 x≥ 0

y ≥ 0

x +3 y = 300

x

C(48, 84)

100

P = x + 1.2 y

200 300

2 x + y = 180

Fundamental Theorem

If a linear programming problem has a solution, then it must occur at a vertex, or corner point, of the feasible set S associated with the problem.

If the objective function P is optimized at two adjacent vertices of S, then it is optimized at every point on the line segment joining these vertices, in which case there are infinitely many solutions to the problem.

Existence of Solution

Suppose we are given a LP problem with a feasible set S and an objective function P. There are 3 cases to consider

Standard LP form

We say that a maximization linear program with n variables is in standard form if for every variable xk we have the inequality xk ≥ 0 and all other m linear inequalities. A LP in standard form is written as

max (c1x1 + … + cnxn )

subject to

a11x1 + … + a1nxn ≤ b1

am1x1 + … + amnxn ≤ bm x1 ≥ 0, …, xn ≥ 0

…

Standard LP in Matrix Form

The vector c is the column vector (c1, . . . , cn).

The vector x is the column vector (x1, . . . , xn).

The matrix A is the n × m matrix of coefficients of the left-hand sides of the inequalities, and

b= (b1, . . . , bm) is the vector of right-hand sides of the inequalities.

subject to

x≥0

max(cT x)

Ax≤ b

Exercise: Convert to Matrix Form

max(x1 + 1.2 x2) 2×1 +x2 ≤180

x1 + 3×2 ≤ 300 x1 ≥ 0

x2 ≥ 0

Algorithms for LP

The standard algorithm for solving LPs is the Simplex Algorithm, due to Dantzig, 1947.

This algorithm starts by finding a vertex of the polytope, and then moving to a neighbor with increased cost as long as this is possible. By linearity and convexity, once it gets stuck it has found the optimal solution.

Unfortunately simplex does not run in polynomial time it does well in practice, but poorly in theory.

Algorithms for LP

In 1974 Khachian has shown that LP could be done in polynomial time by something called the Ellipsoid Algorithm (but it tends to be fairly slow in practice).

In 1984, Karmarkal discovered a faster polynomial-time algorithm called “interior-point”. While simplex only moves along the outer faces of the polytope, “interior- point” algorithm moves inside the polytope.

MATLAB

https://www.mathworks.com/help/optim/ug/linprog.html

Discussion Problem 1

A cargo plane can carry a maximum weight of 100 tons and a maximum volume of 60 cubic meters. There are three materials to be transported, and the cargo company may choose to carry any amount of each, up to the maximum available limits given below.

Material 1

Material 2 Material 3

Density

2 tons/m3

1 tons/m3 3 tons/m3

Volume

40 m3

30 m3 20 m3

Price

$1,000 per m3

$2,000 per m3 $12,000 per m3

Write a linear program that optimizes revenue within the constraints.

Discussion Problem 2

There are n people and n jobs. You are given a cost matrix, C, where cij represents the cost of assigning person i to do job j. You need to assign all the jobs to people and also only one job to a person. You also need to minimize the total cost of your assignment. Write a linear program that minimizes the total cost of your assignment.

Discussion Problem 3

Convert the following LP to standard form

max (5×1 − 2×2 + 9×3)

3×1 + x2 + 4×3 = 8 2×1 + 7×2 − 6×3 ≤ 4 x1 ≤ 0, x3 ≥ 1

Discussion Problem 4

Explain why LP cannot contain constrains in the form of strong inequalities.

max(7×1 – x2 + 5×3) x1 + x2 + 4×3 < 8 3x1 - x2 + 2x3 > 3 2×1 +5×2 -x3 ≤-7

x1, x2 ,x3 ≥ 0

Exercise: Max-Flow as LP

Write a max-flow problem as a linear program.

s

a3c

4

2 1

2 2b3d4

t

Exercise: Shortest Path as LP

Write a shortest st-path problem as a linear program.

2

1 11 9 5

4 5

S

86

2 4 13 3 11

t

du

dv

2

1 11 9 5

4 5

S

86

2 4 13 3 11

t

Discussion Problem 5

Write a 0-1 Knapsack Problem as a linear program.

Given n items with weights w1, w2, …, wn and values v1, v2, …, vn. Put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

m Givenw W

k m

k=1 optimizev →max

k k=1

Knapsack as LP

Knapsack as LP

Dual LP

To every linear program there is a dual linear program

Duality

Definition. The dual of the standard maximum problem

max cTx

Ax ≤ b and x ≥ 0

is defined to be the standard minimum problem

min bTy

ATy ≥ c and y ≥ 0

Exercise: duality

max(7×1 – x2 + 5×3) x1 + x2 + 4×3 ≤ 8 3×1 – x2 + 2×3 ≤ 3 2×1 + 5×2 – x3 ≤ -7

x1, x2 ,x3 ≥ 0

Write the dual problem.

Consider the LP:

max ( cT x)

Ax≤ b x≥0

min ( bT y)

AT y ≥ c y ≥0

primal LP

dual LP

From Primal to Dual

Consider the max LP constrains a11x1+…+a1nxn ≤ b1

am1x1+…+amnxn ≤ bm

1) Multiply each equation by a new variable yk ≥ 0. 2) Add up those m equations.

3) Collect terms wrt to xk.

4) Chooseyk inawaythatAT y≥c.

…

Weak Duality

max ( cT x)

Ax ≤b x ≥0

min ( bT y)

AT y ≥ c y ≥0

primal linear program

dual linear program

Weak Duality. The optimum of the dual is an upper bound to the optimum of the primal.

opt(primal) ≤ opt(dual)

Weak Duality

max ( cT x)

Ax ≤b x ≥0

min ( bT y)

AT y ≥ c y ≥0

Theorem (The weak duality).

Let P and D be primal and dual LP correspondingly.

If x is a feasible solution for P and y is a feasible solution for D, then cTx ≤ bTy.

Proof (in matrix form).

Weak Duality: opt(primal) ≤ opt(dual)

Corollary 1. If a standard problem and its dual are both feasible, then both are feasible bounded.

Corollary 2. If one problem has an unbounded solution, then the dual of that problem is infeasible.

Strong Duality

max ( cT x)

Ax ≤b x ≥0

min ( bT y)

AT y ≥ c y ≥0

Theorem (The strong duality).

Let P and D be primal and dual LP correspondingly. If P and D are feasible, then cTx = bTy.

The proof of this theorem is not as easy and beyond the scope of this course.

Possibilities for the Feasibility

max ( cT x)

Ax ≤b x ≥0

min ( bT y)

AT y ≥ c y ≥0

PD

F.B.

F.U.

I.

F.B.

F.U.

I.

feasible bounded – F.B. feasible unbounded – F.U. infeasible – I.

Consider the LP:

max(3×1 + 8×2 + x3)

x1 + 4×2 – 2×3 ≤ 20 x1 +x2 +x3 ≥7

x2 +x3 =3

x2 ≥ -1

x3 ≤ 5

Write the dual problem.

Discussion Problem 6

Knapsack as LP

Nonlinear Optimization

max f(x)

hi(x) ≤ 0, i = 1,2 , …, m. xk ≥ 0, k = 1,2 , …, n.

Here xT =(x1, x2, …, xn), f and/or h are nonlinear functions. The problem is solved using Lagrange multipliers.

Primal in x:

Dual in λ:

Lagrange Duality (KKT-1951)

max f(x) subject to

hk(x) ≤ 0

min g(λ) subject to

λk ≥ 0

L(x, λ) = f(x) + λ h (x)

g(λ)=min L(x,λ) x

Weak Duality:

Let P and D be the optimum of primal and dual problems respectively. Then opt(P) ≤ opt(D).

Equality (strong duality) holds for convex functions.

kk k