Introduction

Formulign the objective Example: maximise the total weekly profit from factory A and B You need to be spefic and give units Define the individual terms Factory A profit = 300*x Factory B profit = 100*y Formulate constraints Physical limits Non-negativity constraint

Implied relationship restrictions 30% of total has to be from factory A

Bulidn linear programming models

Ratio’s need to be changed from non-linear to a linear format. Take the denominator and put it on top. You can also make the demonintor called D and reaggrange it then reveal what D is.

Solving linear pgoramms Fesible is when the solution is possible

Slacks and surpluses 3x1 + 5x2 >= 10 3x1 + 5x2 = 10 + y1

Y1>=0

Y1 represetns slack Non-zero varalbes are called basic variables Zero varalbes are called non-basic variables

Simplex algorithm

????

Snesivty and paramtric anlysis What happens when the object and cosntta change The constants next to the decision variables are called object ceoefficnet Constiants are called right hand side

Constant*F

Final Value: there are no F’s

What is reduced cost??

Objective coefficnet: is the constant next to F

Allowable increase: this is the amount the objective coefficnet can increase without having to resolve the program,

Allowable decrease: this is the amount the objective coefficnet can decrease without having to resolve the program

Remember if objective coeffeint is still with in the range it the solution is opimial, then we don’t need to resolve. But because the objective coeffient has changed then the Constant*F has changed value and needs to be reculated. This can affect the objective function

If two objective coeffient change then we have to resolve but if they change by the same amount then its still opitmial as they are the same xontours for the object function ?? in exam

The constraint coeffient can’t change without resolve the system,

2x + 1y <= 230

2 and 1 and constraint coefficnet , the 230 is the right hand side

Shadow prices and right and side Difference between final value and costiant R.H side?? Need to add the shadow price * (new right hadn side value- old rigt hand side value)

In exam

Change formulation If you buy 2 big macs then a discount -.7bmS , this is what is put into the objective function The constraint used so you only have this discount on every two big macs 2BMS <= XBM BMS >= 0, integer

Summation notation need to see assignment 2

Aggreated planning page 5.18, need electronic book Flows can be past on from prevous weeks Orders also need to be accounted for

Interger linear programming

Brandch and bound to solve integer programs The system is solved using non interger Then constiant are apply to the variables ot make it intger Eg x= 1.5 , x<1 and x>2 Thes psobliear exhuasive as they do not exlude any possible vlues for X1. This creates two new linear programs, the are nodes on a search tree All the nodes are then solved and the opimital solution is found Bouding is used to identify optimality

Staffing problem Remember to consider when people can start Remember people are interger

Cutting stock problem The solution is fesiable if the number ordered is <= total produced A solution is better if is using the least number of rolls

Example

Xj =number of times use cut using pattern J , where J = {1,2,3,4,5}

Objective function: min

5 cms rolls = 2*x2 + 5x3

Pattern 2 results in 2 5cms rolls every cut and pattern 3 rusults in 5 cms rolls for each cut

X1, x2>0 , interger

If we can make money from surplus rolls then

5 cms rolls = 2*x2 + 5x3 – y1 = 150

150 is the order

We then add into the objective function

2x1 -.25*y1

Interger is used, upper and lower bound Xss <= 0 if z=0 20 <= Xss <=100 if z=1 20z <= Xss <= 100z, z=0,1 This is what you actually write Xss >= 20z Xss <= 100z Z=0,1

If only a lower bound 20z <= Xss <= 99999999999999999z, z=0,1

Ask if in tutorial for alogriym to find the but way