# Multistage Planning

Linear Programming: Multistage Planning Problem

# Linear Programming: Multistage Planning Problem

Reference:
Book: Applied Mathematical Programming
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 to

1. 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 !`