4.4 Linear programming dual Write the dual of the following linear program min 2x 2 + x 3 − 3x 4 x 1 − x 2 + 2x 4 ≥ 2 2x 2 + x 3 = 4 2x 1 − x 3 + x 4 ...

0 downloads 8 Views 50KB Size

Loading...

4.4

Foundations of Operations Research

Prof. E. Amaldi

Linear programming dual

Write the dual of the following linear program min

2x2 + x3 − 3x4 x1 −

+ 2x4

x2

≥

2

=

4

x4

≤

1

x1

≥

0

x2

≥

0

2x2 + x3 2x1

− x3 +

x3 , x4 unrestricted

4.5

Dual of the transportation problem and its economic interpretation

A company produces a single type of good in m factories and stores it in n warehouses. Suppose that the factory i, with i ∈ {1, . . . , m}, has a production capacity of bi units, and the warehouse j, with j ∈ {1, . . . , n}, requires dj units. Let cij be the unit transportation cost from factory i to warehouse j. Consider the problem of determining a transportation plan that minimizes the (transportation) costs, while satisfying the factory capacities and the warehouse demands. If xij denotes the quantity of product transported from factory i to warehouse j, we have the following Linear Programming formulation: Pm Pn min i=1 j=1 cij xij P − nj=1 xij ≥ −bi i ∈ {1, . . . , m} Pm j ∈ {1, . . . , n} i=1 xij ≥ dj xij

≥0

i ∈ {1, . . . , m} j ∈ {1, . . . , n}.

Pm Without loss of generality, we assume that the total production capacity satisfies i=1 bi = Pn Pm Pn Indeed, ifP i=1 bi > j=1 dj , we can introduce a dummy (n + 1)-th warehouse with j=1 dj .P n demand m j=1 dj and zero transportation costs. i=1 bi − Determine the dual of the above Linear Programming formulation and provide an economic interpretation of the dual.

Document prepared by L. Liberti, S. Bosio, S. Coniglio, and C. Iuliano. Translation to English by S. Coniglio

1

ex-4.4-4.6

4.6

Prof. E. Amaldi

Foundations of Operations Research

Complementary slackness conditions

Given the linear programm (P)

max 2x1

+

x1

+

2x2 ≤ 14

2x1

−

x2 ≤ 10

x1

−

x2 ≤

3

x1 ,

x2 ≥

0

x2

a) write its dual, 11 b) check that x ¯ = ( 20 3 , 3 ) is a feasible solution of (P),

c) show that x ¯ is also an optimal solution (P) by applying the complementary slackness conditions, d) derive an optimal solution of the dual.

Document prepared by L. Liberti, S. Bosio, S. Coniglio, and C. Iuliano. Translation to English by S. Coniglio

2

ex-4.4-4.6

Foundations of Operations Research

Prof. E. Amaldi

Solution 4.4 Linear programming dual The dual of the given linear program is max

2y1 + 4y2 +

y3

+ 2y3 ≤ 0

y1 −y1 + 2y2

≤ 2

y2 − 2y1

+

y3 = 1 y3 = −3 y1 ≥ 0 y2

unrestricted

y3 ≤ 0. 4.5 Dual of the transportation problem and its economic interpretation Let ui and vj , with i ∈ I and with j ∈ J, be the dual variables associated to the two classes of constraints. Since in each column of the constraint matrix of the primal problem there are exactly two non-zero entries, with value -1 and +1, appearing in rows corresponding to the fist and, respectively, the second class of constraints, we have the following dual problem: (D1 )

max −

m X i=1

bi u i +

n X

dj v j

j=1

vj − ui ≤ cij

i ∈ {1, . . . , m} j ∈ {1, . . . , n}

ui ≥ 0, vj ≥ 0

i ∈ {1, . . . , m} j ∈ {1, . . . , n}

Economic interpretation. We suppose that the production company (company A) hires a logistics company to handle the transportation business (company B). This company buys all the products from the different factories, paying a unit cost of ui Euro at factory i. Then, it sells the products to the warehouses at a unit cost of vj Euro for warehouse j. The objective of company B is clearly to maximize the profit, that is max −

m X i=1

bi u i +

n X

dj v j .

j=1

Company B has to decide the prices ui and vj . These prices must clearly be competitive, that is, vj − ui ≤ cij for each pair i, j. Indeed, if for any pair i, j the prices are such that vj − ui > cij , the company A will not hire company B and will take care of the transportation directly.

Document prepared by L. Liberti, S. Bosio, S. Coniglio, and C. Iuliano. Translation to English by S. Coniglio

3

ex-4.4-4.6

Prof. E. Amaldi

Foundations of Operations Research

4.6 Complementary slackness conditions a) The dual of the given linear program is (D2 )

min 14y1 +

10y2

+

3y3

y1 +

2y2

+

y3 ≥ 2

2y1 −

y2

−

y3 ≥ 1

y1 , y2 , y3 ≥ 0 11 b) x ¯ = ( 20 3 , 3 ) is feasible, as it satisfies the constrains of (P2 ).

c-d) According to the complementary slackness theorem, if x ¯ = (x1 , x2 ) is feasible for the primal and y¯ = (y1 , y2 , y3 ) is feasible for the dual, and they satisfy yi (aTi x − bi ) = 0 (cj − y T Aj )xj = 0

∀i ∀j

then they are optimal for the respective problems. The complementary slackness conditions for the problem at hand are y1 (x1 + 2x2 − 14) = 0

(1)

y2 (2x1 − x2 − 10) = 0

(2)

y3 (x1 − x2 − 3) = 0

(3)

x1 (y1 + 2y2 + y3 − 2) = 0

(4)

x2 (2y1 − y2 − y3 − 1) = 0.

(5)

11 ¯ . Since x ¯ = ( 20 We obtain y¯ by substituting for x 3 , 3 ) satisfies as equations Constraints, but not the second one, we deduce y2 = 0. Since x1 > 0 and x2 > 0, we obtain

y1 + 2y2 + y3 − 2 = 0

(6)

2y1 − y2 − y3 − 1 = 0

(7)

y2 = 0

(8)

By solving the system, we obtain y¯ = (1, 0, 1), which satisfies the dual constraints of D2 . Since x ¯ is primal feasible and y¯ is dual feasible, the primal/dual pair (¯ x, y¯) satisfies the complementary slackness constraints and, therefore, x ¯ is an optimal solution to the primal and y¯ is an optimal solution to the dual. To double check, note that the objective function values in the respective problems of the two solutions are equal, namely, we have cT x = y T b.

Document prepared by L. Liberti, S. Bosio, S. Coniglio, and C. Iuliano. Translation to English by S. Coniglio

4