Batch Planning and Resource Allocation Master MDE

BATCH PLANNING AND RESOURCE ALLOCATION
Master MDE
Lesson 2
Conf. Virginia Ecaterina OLTEAN
Evaluation:
50% - the activity during the semester (homeworks)
50% - the final examination

An introductory example (continuation from Lesson 1)
The optimal decision of the manufacturer, concerning the optimal size of the batch of PROD1 and PROD 2,
with the manufacturing process using as resources the machines of types M1 and M2, is modelled by the
LP primal problem:
P : max cT x
s.t. Ax  b, x  0
x 
where x1  0 and x2  0 are the quantities of PROD1 and PROD2, respectively, and x   1 
 x2 
cT  [1 1] f : R 2  R , f ( x)  cT x is the income, representing the objective to be maximized
1 2
A  the constraints matrix
1 0
Remark: the number of rows in A =the number of resource types and the number of
columns in A =the number of decision variables
6 
b  the limits on available quantities of resources M1 and M2, expressed in time units;
 3
Remark: each resource can be occupied a time up to the time limit
BPRA C2_S2, conf. V.E.Oltean 2
STEP1. The accountant wants to evaluate the resources at a minimum cost, constrained that the
production has to be sustained, so his decision is modelled by the
LP dual problem
D : min T b
s.t. AT   c,   0
 
where:    1  is the vector of dual decision variables. Remark: their optimal values are “shadow prices”
 2 
1 [mu/1 time unit used to occupy M1] is the unit price of the resource M1
 2 [mu/1 time unit used to occupy M2] is the unit price of the resource M2,
The dual problem can be formulated as follows: what are the optimal values of the unit prices of resources
M1 and M2, that is the optimal price paid to occupy/use each resource for a time unit (tu), such that:
a) the overall cost of resources f ' ()  6  1  3   2 is minimized, f ': R 2  R and
b) the production is sustained

A more detailed explanation:
P : max( 1 x1  1 x2 ) , x1 , x2 - quantities of PROD1,2 D : min( 6  1  3   2 )
M1: 1 x1  2  x2  6 [time units for M1] PROD1: 1 1  1  2  1 [money units income from pu1]
M2: 1 x1  0  x2  3 [time units for M2] PROD2: 2  1  0   2  1[money units income from pu2]
THE PRIMAL PROBLEM THE DUAL PROBLEM
a a  1 2  b1  6
With symbolic notations, for A   11 12     , b       and cT  [c1 c2 ]  [1 1] :
a21 a22  1 0 b2  3
 The dual objective is f ' ()  b11  b2 2  T b  bT  and

 The first dual constraint is
a111  a21 2  c1 [money /pu1]

   
the value of using M1 and M2 for a unit of PROD1 the unit incomecontribution of PROD1
and similarly for the second dual constraint.

STEP2. The geometric approach in solving the dual problem
Classroom exercise:
   
Draw in the (1,  2 ) -plane the feasibility set    1   R 2 : 1   2  1, 21  1, 1, 2  0 . Hint: draw the
 2  
frontier lines (1): 1   2  1 and (2): 21  1.
Analysis: Show that    so the dual problem is feasible (that is there are solutions).
Geometric solution: Draw the dual objective line f ' ()  6 with f ' ()  6  1  3   2 .
 f ' 
   6
Draw the direction of the gradient   f '   1     . The value of the dual objective (cost of resources)
 f '  3
  2 
  6
decreases in the direction of the anti-gradient    f '    . Show that the minimum cost f ' (*)  4.5 is
  3
1 1
attained for *1  and *2  , when the dual objective line reaches the point D(1 / 2,1 / 2) =(1)(2).
2 2

Step 2’. Numerical approach. Write a program in Octave to compute the optimal solution of the dual
problem
D : min bT 
s.t. AT   c,   0
T T
b  a a21  1 2 1 1   c1  1
where b   1   [6 3] , AT   11
T

 1 0   2 0 , c  c   1 .
b
 2 a
 12 a 22       2  
Hint: set the glpk routine for a min problem.
https://math.stackexchange.com/questions/91504/shadow-price-in-linear-programming for shadow prices

explanation

Batch Planning and Resource Allocation Master MDE

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Batch Planning and Resource Allocation Master MDE

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Batch Planning and Resource Allocation Master MDE

Uploaded by

Copyright:

Available Formats

BATCH PLANNING AND RESOURCE ALLOCATION

Conf. Virginia Ecaterina OLTEAN

50% - the activity during the semester (homeworks)

50% - the final examination

cT  [1 1] f : R 2  R , f ( x)  cT x is the income, representing the objective to be maximized

a) the overall cost of resources f ' ()  6  1  3   2 is minimized, f ': R 2  R and

b) the production is sustained

BPRA C2_S2, conf. V.E.Oltean 3

P : max( 1 x1  1 x2 ) , x1 , x2 - quantities of PROD1,2 D : min( 6  1  3   2 )

 The dual objective is f ' ()  b11  b2 2  T b  bT  and

a111  a21 2  c1 [money /pu1]

and similarly for the second dual constraint.

BPRA C2_S2, conf. V.E.Oltean 4

BPRA C2_S2, conf. V.E.Oltean 5

Hint: set the glpk routine for a min problem.

https://math.stackexchange.com/questions/91504/shadow-price-in-linear-programming for shadow prices

BPRA C2_S2, conf. V.E.Oltean 6

You might also like