Linear programming-introduction
Ing.J.Skorkovský,CSc.


USE
•Slitting and Levelling of material (coils, bars, sheets)-Cutting material, trimming,…
•Blending - blending, diet, feeding rations for animals, ..
•Transport problems - material flow from stock to the destination and route planning - shortest
route
•Assignment of resources with limited capacities  - CCR
•Sources : Operation Management, Quality and Competitiveness in a global environment, Russel and
Taylor (ESF library
•

Formulation of the model
Product
Description
Work /hour
Material/pcs
Return/pcs
Dish
x1
1
4
40
Mug
x2
2
3
50

Which combination of products will have the greatest return
at the limits of maximum production capacity type = 40 hours
and the amount of material that is limited to 120 kg of clay?
Note: A similar task in terms of flow was solved in the P&Q example
(only valid for Czech student), where the limitation in resource
 B and with a maximum capacity of 2400 minutes)

Basic structures and used terminology
•We minimize our target function in the form of:
•
•        Z = c1*x1+c2*x2+…..+cn*xn  with respect to the matrix of restrictive conditions:
•              (in our case c1=40 and c2=50)
•A11*x1 + A12*x2+ …+ A1n*xn    (<>=) B1
•A22*x1 + A22*x2+ …+ A2n*xn    (<>=) B2
•
•Am1*x1 + Am2*x2+ …+ Amn*xn (<>=) B2
•
•It is classical system of linear equations je  Ax=B
•The solving of such a linear equation system, e.g. By use of GAUSS-JORDAN algorithm is not
required with the help of Excel Solver.
•xij  : decision variable= level of operation activity specified by this variable
•Bi   : restrictive conditions , allowed deviations from the norm (in time and  material)
•cj   :  coefficient of the target function (in our case returns, meaning 40 and 50 )
•Aij  : restrictive coefficients  : work and material for one unit (pcs) of the product
•
•

Example I (introduction to the problem – practical demonstration )
Target function:  Z= 40*x1+50*x2, which we must maximize
Maximal production capacity = 40 hours and Maximal quantity of material =120 kg
Specifications of task restrictions by use of 2x2 matrix:
1*x1   +   2*x2 =40    (work- no more than 40 hours)
4*x1   +   3*x2 =120  (material=kg of clay in our case)->x1=(40-2x2)+3x2=120….
Manual solving : -> x1=24 a x2=8  and after substitution od variables
in target function  we will get
                                           Z=40*24+50*8=1360
(optimal Return meets the point B – see next slide)
Z = c1*x1+c2*x2+…..+cn*xn  (classical equation from)
Product
Description
Work /hour
Material/pcs
Return/pcs
Dish
x1
1
4
40
Mug
x2
2
3
50

Graphical solution



Use of Solver (Czech EXCEL)
Excel setup
Solver
Comlements
Supplement
Solver
Solver

Use o solver (see  actual Excel formulas  on one of the the next  slides)

Dish
Mug
Total
Capacity
Variables  (x1, x2)
0
0


Return
40
50
0






Material
4
3
0
120
Work
1
2
0
40
x1=Dish , x2=Mug, max  40 hod (B1), max 120 kg (B2)
Target function  Z = x1*c1 + x2*c2 = 40*x1+50*x2
Z
4 * x1   +   3 *x2 =120 - capacity restrictions= max quantity of material =B1
1 * x1   +   2 *x2 =   40  -capacity resrictions by max work capacity=B2
x1
x2
Assignment
Assignment
entered in table
Product
Description
Work /hour
Material/pcs
Return/pcs
Dish
x1
1
4
40
Mug
x2
2
3
50

Solver start



Use of Solver (Czech- not for MOH_AOPR )
Z = x1*c1 + x2*c2 = 40*x1+30*x2
E7=C7*C4+D7*D4=4*x1+3*x2=120
E8=C8*C4+D8*D4=x1+2*x2=40

Use of solver (ENG)
Z = x1*c1 + x2*c2 = 40*x1+30*x2
F10=D10*D6+E10*E6=4*x1+3*x2=120
F11=D11*D6+E11*D6=x1+2*x2=40
Solve it
Target
Variables
Restrictions

Využití Řešitele (use of Solver)



Use of Solver (English)
New  Excel List


Změna úlohy- jiné výnosy jiná omezení typu práce na dvou strojích a jejich kapacitní omezení
(Change of parameters- not necessary fro MPH_AOPR !!!!!)


OK ?