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


USE-Využití
•Slitting and Levelling of material (coils, bars, sheets)-Cutting material, trimming,… (dělení
materiálu)
•Blending - blending, diet, feeding rations for animals, .. (míchání krmných směsi podle receptu
veterináře,..)
•Transport problems - material flow from stock to the destination and route planning - shortest
route (optimalizace dopravních tras)
•Assignment of resources with limited capacities  - CCR=Capacity Constraint Resource – přiřazení
zdrojů s omezenou kapacitou
•Sources : Operation Management, Quality and Competitiveness in a global environment, Russel and
Taylor (ESF library),…
•

Formulation of the model- Formulace modelu
Výrobek
Popis
Práce/hod
Materiál/ks
Výnos/ks
Dish (Miska)
x1
1
4
40
Mug (Hrnek)
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 (jíl)?
Note: A similar task in terms of flow was solved in the P&Q example based on TOC
(only valid for Czech student), where the limitation was in resource
B and with a maximum capacity of 2400 minutes)
Při které kombinaci vyráběných produktů (miska a hrnek) budeme mít největší výnos
když máme možnost pracovat  maximálně 40 hodin (limit kapacity) a nemůžeme
využít více jak 120 kg jílu (hrnčířské hlíny) – omezení materiálové

Basic structures and used terminology
Základní rovnice a termiologie
Systém lineárních rovnic => Ax=B

Example I (introduction to the problem – practical demonstration )
Target function:  Z= 40*x1+50*x2, which we must maximize (maximalizovat
cílovou funkci)
Maximal production capacity = 40 hours and Maximal quantity of material =120 kg
(jsou to dva prvky matice B (40,120) – omezení
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 (vyřešení 2 lineárních rovnic
o 2 neznámých)
in target function  we will get
                                           Z=40*24+50*8=1360 (maximální výnos)
(optimal Return meets the point B – see next slide)
Z = c1*x1+c2*x2+…..+cn*xn  (classical equation from) Z = co největší výnos)
Výrobek
Popis
Práce/hod
Materiál/ks
Výnos/ks
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 restrictions 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 MPH_AOPR )
Z = x1*c1 + x2*c2 = 40*x1+50*x2
E5=C4*C5+ D4*D5
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 ?