# Multistage Planning

# Linear Programming: Multistage Planning Problem

**Reference:**

Book: Applied Mathematical Programming

Author(s): Bradley, Hax and Magnanti

Publication: Addison-Wesley

Year: 1977

Chapter: 5

An automobile tire company has the ability to produce both nylon and fiberglass tires. During the next three months they have agreed to deliver tires as follows

Date | Nylon (No. of Tires) | Fiberglass (No. of Tires) |

June 30 | 4000 | 1000 |

July 31 | 8000 | 5000 |

August 31 | 3000 | 5000 |

The company has two presses, a wheeling machine and a regal machine, and appropriate moulds that can be used to produce these tires, with the following production hours available in the upcoming months

Month | Wheeling Machine (Hours) | Regal Machine (Hours) |

June | 700 | 1500 |

July | 300 | 400 |

August | 1000 | 300 |

The production rates (hours per tire) for each machine and tire combination are as follows:

Wheeling Machine (Hours/tire) | Regal Machine (Hours/tire) | |

Nylon | 0.15 | 0.16 |

Fiberglass | 0.12 | 0.14 |

The variable costs of producing tires are $5.00 per operating hour, regardless of which machine is being used or which tire is being produced. There is also an inventory-carrying charge of $0.10 per tire per month. How should the production be scheduled in order to meet the delivery requirements at minimum costs? This problem constitutes 16 decision variables, 6 inequality and 6 equality linear constraints. The default termination criteria for linprog solver are kept unchanged for solving this problem.

Mathematical Formulation:The following notations are too be followed

= Number of nylon tires to be produced on the Wheeling machine during month t

= Number of nylon tires to be produced on the Regal machine during month t

= Number of fiberglass tires to be produced on the Wheeling machine in month t

= Number of fiberglass tires to be produced on the Regal machine in month t

= Number of nylon tires put into inventory at the end of month t

= Number of fiberglass tires put into inventory at the end of month t.

Minimize Subject to1. Capacity constraint (Production hours available)

2. Demand constraints

3. Non-negative constraint

clc; nProducts = 2; nMachines = 2; nPeriods = 3; Demand = [4000 1000;8000 5000; 3000 5000]; AvailMachineTime = [700 1500;300 400; 1000 300]; ProdRate = [0.15 0.16;0.12 0.14]; OperatingCost = 5; InventoryCost = 0.1; nVar = nProducts*nMachines*nPeriods + (nPeriods-1)*nProducts; // Dimension of the problem is determined // Linear equality constraints // Demand constraints nEqConstraints = nProducts*nPeriods Aeq = zeros(nEqConstraints,nVar); // Demand constraints for period 1 Aeq1 = zeros(nProducts,nVar); for i = 1:nProducts index1 = (i-1)*nProducts+1:i*nProducts; Aeq1(i,index1) = 1; index2 = nMachines*nProducts+i; Aeq1(i,index2) = -1; beq1(i,1) = Demand(1,i); end // Demand constraints for period 2 to (nPeriods-1)th period Aeq2 = zeros(nProducts,nVar); for i = 2:nPeriods-1 for j = 1:nProducts index3 = (i-1)*(nProducts*nMachines+nProducts)+(j-1)*nMachines+1:(i-1)*(nProducts*nMachines+nProducts)+(j-1)*nMachines+nMachines; Aeq2(j,index3) = 1; index4 = (i-1)*(nProducts*nMachines+nProducts) - nProducts+j; Aeq2(j,index4) = 1; index5 = i*(nProducts*nMachines+nProducts)- nProducts+j Aeq2(j,index5) = -1; beq2(j,1) = Demand(i,j); end end // Demand constraints for last period Aeq3 = zeros(nProducts,nVar); for i = 1:nProducts index6 = (nProducts*nMachines+nProducts)*(nPeriods-1)+(i-1)*nProducts+1:(nProducts*nMachines+nProducts)*(nPeriods-1)+i*nProducts Aeq3(i,index6) = 1; index7 = (nProducts*nMachines+nProducts)*(nPeriods-1) - nProducts+i; Aeq3(i,index7) = 1; beq3(i,1) = Demand(nPeriods,i); end Aeq = [Aeq1;Aeq2;Aeq3]; beq = [beq1;beq2;beq3]; // Linear inequality constraints // Machine time constraints for i = 1:nPeriods for j = 1:nProducts Cindex = (i-1)*(nProducts*nMachines+nProducts)+j:nProducts:(i-1)*(nProducts*nMachines+nProducts)+nMachines+j; Rindex = (i-1)*nProducts+j; A(Rindex,Cindex) = ProdRate(:,j)'; b(Rindex,1) = AvailMachineTime(i,j); end end // Objective function TotalProductionCost = []; for j = 1:nProducts TotalProductionCost = [TotalProductionCost ProdRate(j,:)*OperatingCost]; end for i = 1:nPeriods index = (i-1)*(nProducts*nMachines+nProducts)+1:(i-1)*(nProducts*nMachines+nProducts)+nProducts*nMachines; nindex = length(index); cost(index,1) = TotalProductionCost'; cost(index(nindex)+1:index(nindex)+nProducts,1) = InventoryCost; end cost(nVar+1:nVar+nProducts,1) = []; lb = zeros(1,nVar); [xopt,fopt,exitflag,output,lambda]=linprog(cost, A, b, Aeq, beq, lb,[]); //Result representation if exitflag == 0 then disp(" Optimal Solution Found") M = [" "]; for m = 1:nMachines M = [M strcat(["Machine",string(m)])]; end P = []; for p = 1:nProducts P = [P;strcat(["Product ",string(p)])]; end for i = 1:nPeriods Sol = []; for j = 1:nProducts Ind1 = (i-1)*(nProducts*nMachines + nProducts)+(j-1)*nProducts+1:(i-1)*(nProducts*nMachines + nProducts)+j*nProducts; Sol = [Sol;xopt(Ind1)']; end disp(strcat(["Production schedule for the Period ", string(i)])); disp([M; [P string(Sol)]]); end for i = 1:nPeriods-1 ind = i*(nProducts*nMachines+1:nProducts*nMachines+nProducts); inventory = xopt(ind); disp(strcat(["Inventory at the Period ", string(i)])); disp([P string(inventory)]); end disp(["The optimal cost is ", string(fopt)]) elseif exitflag == 1 then disp("Primal Infeasible") else disp("Error encountered") end |

Expected Output:

Optimal Solution. Optimal Solution Found Production schedule for the Period 1 ! Machine1 Machine2 ! ! ! !Product 1 1866.6667 7633.3333 ! ! ! !Product 2 3500 0 ! Production schedule for the Period 2 ! Machine1 Machine2 ! ! ! !Product 1 0 2500 ! ! ! !Product 2 2500 0 ! Production schedule for the Period 3 ! Machine1 Machine2 ! ! ! !Product 1 2666.6667 333.33333 ! ! ! !Product 2 5000 0 ! Inventory at the Period 1 !Product 1 5500 ! ! ! !Product 2 2500 ! Inventory at the Period 2 !Product 1 0 ! ! ! !Product 2 0 ! !The optimal cost is 19173.333 ! |