Batch Planning and Resources Allocation

Lecture 3

14x2=28C, 14x1=14S

Conf.dr.ing. Virginia Ecaterina OLTEAN

Departamentul de Automatică şi Informatică Industrială

021-4029269

Remark: in fact, “resource allocation” or “allocation of resources”

Part I. Generalities concerning mathematical models of economic processes

Lecture 2
2. Special types of mathematical programming models – some interpreted examples. First LP theoretical results

 Further LP examples and economic interpretation of duality

o The diet problem and its dual – economic interpretation, competitive prices
o Optimality criterion (lema and
Lecture 3
o theorem) and Theorem of duality – statement
o Network models - The transportation problem and its dual

Later:
 Production models as input-output models (static Leontieff models) and related problems

 Price equilibrium (theorem of equilibrium and its reformulation as complementary slackness from Lecture
1) and economic interpretation for
 the production problem and for
 the transportation problem
in Lecture 4

_________________________________________________________________________________________________________________________
Conf.. V.E. Oltean / BPRA. Part I- Generalities. 2. Special types of mathematical programming models. L3 2/11
Recall from Lecture 2:
the definition of a STANDARD LINEAR PROGRAMMING (LP) PROBLEM:
P: given A  R mn , c  R n and b  R m (usually m  n )
find x  R n (called decision variables or activities)
so that
1. the value of the objective function f : R n  R , f ( x)  c T x is maximized (or minimized) and
2. x  R n is required to satisfy the set of linear inequalities Ax  b , x  0 .

n
X  { x  R : Ax  b, x  0} is the feasible set of P and x  X is a feasible solution of P. P is feasible if X
is nonempty. A feasible solution x * s.t. f ( x*)  max c T x is called an optimal solution and f (x*) is the
xX
value of the linear program.
The dual problem of P is
D: given A  R mn , c  R n and b  R m
find λ  R m (called dual variables or shadow prices)
so that
T
1. the value of the objective function f ' : R n  R , f ' (λ )  λ b is minimized (or minimized)
and
2. λ  R m is required to satisfy the set of linear inequalities AT λ  c , λ  0 .

m
Lema 1. Let x  X be a feasible solution of P and let λ  R be a feasible solution of D. Then

c T x  λT Ax  λT b (1)

_________________________________________________________________________________________________________________________
Conf.. V.E. Oltean / BPRA. Part I- Generalities. 2. Special types of mathematical programming models. L3 3/11
 Proof. In Ax  b premultiply by λ T   ) Ax   ) b  λ T Ax  λ T b (a). In AT λ  c , premultiply by x T 
T T

x T AT λ  x T c  c T x (b). From (a) and (b) results (1). 

Theorem 1 (optimality criterion, necessity). If there exist

(a) x a feasible solution for P and λ a feasible solution for D and
(b) c T x  λ T b (P and D have the same value),
then they are optimal solutions of the respective problems,
i.e. x  x * with c T x*  max c T x and λ  λ * with λ T b  min λ T b (2)
Axb, x 0 A λc , λ0
T

Proof. Assume x' X , x'  x any distinct feasible solution for P. From Lema 1 it results that c T x'  λ T b . But
from (b) c T x  λ T b , hence c T x'  c T x and x is optimal for P. Simetrically for D.

The converse of Theorem 1 is also true, giving
____________________________________________________________________
The FUNDAMENTAL DUALITY THEOREM OF LP (firstly stated by John von Neumann).
Denote P a standard maximum (or minimum) LP problem and D its dual.
If P and D are both feasible then
1. P and D have both optimal solutions ( x * and λ * , respectively) and
2. P and D have the SAME value.
If either problem is NOT feasible, then NEITHER has an optimal solution.

Hence
Theorem 1 (necessity for optimality) states: feasibility + equal feasible problem values  optimality
Duality theorem states: problem feasibility  existence of optimal solutions + equal optimal problem values

Further aspects on duality are discussed in the examples below.

_________________________________________________________________________________________________________________________
Conf.. V.E. Oltean / BPRA. Part I- Generalities. 2. Special types of mathematical programming models. L3 4/11
Example 2. THE TRANSPORTATION PROBLEM AND ITS DUAL – economic interpretation, a
first network model and a numerical application of the duality theorem
1) The primal problem
Let a commodity (say steel) be produced at each of m plants P1 , …, Pm .
Pi produces a i units of steel/year, i  1 : m , (the supply).
The steel is required at each of n markets, M 1 , …, M n and
the annual demand at the jth market is b j units of steel/year.
Denote c ij the cost of shipping 1 unit of steel Pi  M j .
cij
Pi Mj
The ACTOR is the steel manufacturer ant the problem is
to determine a shipping schedule consisting of the numbers x ij of units of steel delivered from Pi to M j such
that:
1. the demand b j at the market M j will be satisfied, j  1 : n (1)
2. the supply a i at the plant Pi will not be exceeded, i  1 : m , (2) and
3. the TOTAL SHIPPING COST will be miminized (3)
i.e.
m
 xij  b j , j  1: n (1)
i 1
n
 xij  ai , i  1 : m (2)
j 1

_________________________________________________________________________________________________________________________
Conf.. V.E. Oltean / BPRA. Part I- Generalities. 2. Special types of mathematical programming models. L3 5/11
 n m
min   cij xij . (3)
i 1 j 1

Remark. A necessary feasibility condition is that

“the TOTAL SUPPLY is at least as large as the TOTAL DEMANDED STEEL”
i.e.
m n
 ai   b j (4)
i 1 j 1


Rewrite the problem (1), (2), (3) above as the primal 2) The dual problem. Consider m  n nonnegative
problem with the same signum of the constraints numbers (dual variables),  i , i  1 : m , ' j , j  1 : n such
inequalities,
m n
that
P: min   cij xij (5)  n m 
i 1 j 1 D: max  ' j b j    i ai  (6)
 j 1 
m  i 1 
subject to  xij  b j , j  1: n subject to ' j   i  cij , i  1 : m , j  1 : n
i 1
n  i , ' j  R  , i  1 : m , j  1 : n
  xij  a i , i  1 : m
j 1
xij  R  , i  1 : m , j  1 : n

_________________________________________________________________________________________________________________________
Conf.. V.E. Oltean / BPRA. Part I- Generalities. 2. Special types of mathematical programming models. L3 6/11
 Economic interpretation. Recall that c ij , i  1 : m , j  1 : n , are the established transportation costs which
confront the steel manufacturer (say Mittal) who is in the act of trying to decide a shipping schedule (the primal
problem).
The 2nd ACTOR is a representative of a Transportation Company who proposes to the 1st ACTOR:
 to buy all the steel paying  i (money units) for each unit steel produced at plant Pi , i  1 : m ,
 guaranteeing to deliver the steel to the markets M j in quantities b j , j  1 : n and
 to resell the steel back to the manufacturer (to retrieve its costs), charging ' j for each unit at M j ,
j  1 : n , s.t. ' j   i  cij , i  1 : m , j  1 : n , meaning that the manufacturer will pay NO MORE than he
would pay for normal shipping (problem P)
hence
n m
  j b j    i ai
'
 THE TOTAL PROFIT OF THE TRANSPORTATION COMPANY (7)
j 1 i 1

and
P: a problem of minimizing the shipping cost
D: a problem of maximizing the transport profit

Remark. 1) Once again, like in Example 1 (the diet problem), the dual variables are prices, and the decision
variables are costs.
2) In D, the manufacturer doesn’t save money, but he is saved the trouble of calculating the shipping cost.


_________________________________________________________________________________________________________________________
Conf.. V.E. Oltean / BPRA. Part I- Generalities. 2. Special types of mathematical programming models. L3 7/11
 An interpreted toy numerical example (Gale, 1960). Consider the transportation problem depicted below, with
m  2 plants and n  3 markets.
M1 b1=2 Define the cost matrix
1
2 M1 M 2 M 3
 1 2 3  c1T 
a1=4 P1 2 M b =3 P1 1 2 3 , i.e. C     (cij )1i 2   T  (8)
2 2  2 4 6  1 j 3  c2 
4 P 2 2 4 6

a2=7 P2 3
M3 b3=5
6
Consider a feasible solution (we do not know yet how to compute it systematically)
 0 0 4   x1T 
X *  ( xij )1i 2      T  (9)
1 j 3  2 3 1   x2 
which, with (8) and (3), gives the shipping cost

f ( X *)  c1T x1  c 2T x 2  34 (10)

_________________________________________________________________________________________________________________________
Conf.. V.E. Oltean / BPRA. Part I- Generalities. 2. Special types of mathematical programming models. L3 8/11
 In order to prove that this is a minimum, consider the feasible prices for the dual problem:

buying prices at plants: 1  3 ,  2  0 ( i  1,2 ) (11.1)

reselling prices from markets: '1  2 , '2  4 , '3  6 ( j  1 : 3 ) (11.2)

and check their feasibility, ' j   i  cij , i  1 : 2 , j  1 : 3 , using the following figure:

'1  2 '2  4 '3  6

1  3 1 2 3
2  0 2 4 6

Compute with (11) the transportation profit (7), i.e.

n m
for  ' j b j    i ai  THE TOTAL PROFIT OF THE TRANSPORTATION COMPANY (7)
j 1 i 1
it results:
3 2
 ' j b j    i ai  34 ,
j 1 i 1
and, since it is the same as the shipping cost (10), it follows, from the duality theorem (see above), that the
solution is optimal.

_________________________________________________________________________________________________________________________
Conf.. V.E. Oltean / BPRA. Part I- Generalities. 2. Special types of mathematical programming models. L3 9/11
 The solution can be written as a shipping matrix (9):

M1 M2 M3
P1 0 0 4 , where, recall that the ijth entry is x ij .
P2 2 3 1

The optimal shipping schedule is represented below,

M1 b1=2
2

a1=4 P1 4 2 M2 b2=3
2 4
3
a2=7 P2 3
1 M3 b3=5
6
Fig.1. The optimal shipping schedule.

with the remark that P1 delivers only to M 3 and the cheapest route, P1  M 1 is NOT used, but the most
expensive route P2  M 3 is used.

_________________________________________________________________________________________________________________________
Conf.. V.E. Oltean / BPRA. Part I- Generalities. 2. Special types of mathematical programming models. L3 10/11
 

_________________________________________________________________________________________________________________________
Conf.. V.E. Oltean / BPRA. Part I- Generalities. 2. Special types of mathematical programming models. L3 11/11