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 (can be found easily in ESF library)
•
•
•CCR=Capacity Constraint Resource

CCR –additional information
•There are 3 categories of resources from the point of view of capacity:
•Bottleneck
•CCR – Capacity Constraint Resource
•Non-CCR
•
•
•

Formulation of the simple 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.
Moreover, 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)
Description x1 and x2 stands for variables, Material means e.g. 4 kg for one piece

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 which means return/pc)
•
• A11*x1 + A12*x2+ …+ A1n*xn    (<>=) B1
• A22*x1 + A22*x2+ …+ A2n*xn    (<>=) B2
•
• Am1*x1 + Am2*x2+ …+ Amn*xn (<>=)Bm
•
•It is a classical system of linear equations is  Ax=B
•The solving of such a linear equation system, e.g. By use of GAUSS-JORDAN algorithm is not
required if we will use 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 return 40 and 50 )
•Aij  : restrictive coefficients: work and material for one unit (pcs) of the product
•
•
Target function
Z=Cx

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
(B1 and B2 in our mathematical expression)
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 (24 pcs of Dish and 8 pcs of
Mug)
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
I apologize for the inappropriate graphic expression….


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

Use o solver (see  actual Excel formulas  on one of 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 hour (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 MHP_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
E5 =

      Use of solver (for MPH_AOPR)
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
F7 =

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 for MPH_AOPR !!!!!)


OK ?