Maximization Problem

20/01/2009

Applied Quantitative Analysis

Problem Klein Chemicals , Inc., produces a special oil-base material that is currently in short supply. Four of Klein’s customers have already placed orders that together exceed the combined capacity of Klein’s two plants. Klein’s management faces the problem of deciding how many units it should supply to each customer. Because the four customers are in different industries, different prices can be charged based on the various industry pricing structures. However, slightly different production costs at the two plants and varying transportation costs between the plants and customers make a “sell to the highest bidder “ strategy questionable. After considering price , production costs , and transportation costs, Klein has established the following profit per unit for each plantcustomer alternative.

Applied Quantitative Analysis- Transportation maximization problem

1

20/01/2009

Applied Quantitative Analysis

Background The problem given to us is one of a Profit maximization problem. The question provides details of 2 sources with their supply to 4 destinations & their respective demands. It is an unbalanced transportation problem with demand exceeding the supply. So it is compensated with a dummy supply origin with costs of transportation in the row accounted for as 0. It is the reverse of a normal transportation problem which involves minimization of cost. However, to solve the same we first need to convert the given problem into a minimization one by subtracting all the profit figures from the highest given figure & carry on as a normal one Assumptions Let, X11 denote the number of units shipped from origin 1 (Clifton Springs) to destination 1 (D1), X12 denote the number of units shipped from origin 1 (Clifton Springs) to destination 2 (D2), and so on. There are 2 (m) origins and 4 (n) destinations, hence there are 2*4 (m*n) = 8 decision variables. The objective of the transportation problem is to maximize the total profit, the profit expressions would be as follows:

Profit for units shipped from Clifton Springs = 32 X11 + 34 X12 + 32 X13 + 40 X14 Profit for units shipped from Danville

= 34 X21 + 30 X22 + 28 X23 + 38 X24

With 2 plants, Klein Chemicals Inc. has two supply constraints.

X11 + X12 + X13 + X14 <= 5000

Clifton Springs supply

X21 + X22 + X23 + X24 <= 3000

Danville supply

With 4 distribution centers, Klein Chemicals Inc. has four demand constraints.

X11 + X21 = 2000

D1 demand

X12 + X22 = 5000

D2 demand

X13 + X23 = 3000

D3 demand

X14 + X24 = 2000

D4 demand

Combining the objective function and constraints into one model provides a 8-variable, 6constraint linear programming formulation of the Klein Chemicals Inc Transportation problem.

Applied Quantitative Analysis- Transportation maximization problem

2

20/01/2009

Applied Quantitative Analysis

MAX 32 X11 + 34 X12 + 32 X13 + 40 X14 + 34 X21 + 30 X22 + 28 X23 + 38 X24 Subject to (s.t) X11 + X12 + X13 + X14 <= 5000

Clifton Springs supply

X21 + X22 + X23 + X24 <= 3000

Danville supply

X11 + X21 = 2000

D1 demand

X12 + X22 = 5000

D2 demand

X13 + X23 = 3000

D3 demand

X14 + X24 = 2000

D4 demand

Xij >= 0 for i=1, 2; j=1, 2, 3, 4

Input Table

Applied Quantitative Analysis- Transportation maximization problem

3

20/01/2009

Applied Quantitative Analysis

Northwest corner method

This method achieves the optimal solution in the 6th iteration. It satisfies the property of m+n-1 that is, 3+4-1=6. There is no degeneracy. The initial iteration of the north west corner method is given in the table below which is further improved to get the solution in the 6th or the last table.

Applied Quantitative Analysis- Transportation maximization problem

4

20/01/2009

Applied Quantitative Analysis

Optimal solution

The maximum profit is calculated by seeing the final solution table & multiplying the amounts shipped from various origins to the different destinations with their respective profits which can be done so as follows:4000*34 + 1000*40 + 2000*34 + 1000*38 = $ 282000

Applied Quantitative Analysis- Transportation maximization problem

5

20/01/2009

Applied Quantitative Analysis

Least cost method

This method achieves the optimal solution in the 4th iteration. Again the property of m+n-1 is satisfied & poses no problems of degeneracy. The table which is further improved to get the final optimal solution is as follows:-

Applied Quantitative Analysis- Transportation maximization problem

6

20/01/2009

Applied Quantitative Analysis

Optimal solution

The maximum profit is calculated by seeing the final solution table & multiplying the amounts shipped from various origins to the different destinations with their respective profits which can be done so as follows:4000*34 + 1000*40 + 2000*34 + 1000*38 = $ 282000

Applied Quantitative Analysis- Transportation maximization problem

7

20/01/2009

Applied Quantitative Analysis

Vogel’s approximation method

The method achieves the solution in the 3rd iteration itself. It has the least number of iterations. There is no degeneracy in this method as well. The initial table is as follows:-

Applied Quantitative Analysis- Transportation maximization problem

8

20/01/2009

Applied Quantitative Analysis

Optimal solution

The maximum profit is calculated by seeing the final solution table & multiplying the amounts shipped from various origins to the different destinations with their respective profits which can be done so as follows:4000*34 + 1000*40 + 2000*34 + 1000*38 = $ 282000

The solution achieved by all the 3 methods is the same with the same allocations only the number of iterations differ in number from method to method as described individually in all the methods above.

Applied Quantitative Analysis- Transportation maximization problem

9

20/01/2009

Applied Quantitative Analysis

Final Solution:

Interpretation:

Since the given problem was one of maximization of profits we first converted it into one of minimization of opportunity cost by subtracting all profit figures from the largest figure present. Thus the problem became one of the minimization of opportunity cost which after the respective iterations in the different methods came out to be $ 38000 in all cases.

The maximum profit is calculated by seeing the final solution table & multiplying the amounts shipped from various origins to the different destinations with their respective profits which can be done so as follows:4000*34 + 1000*40 + 2000*34 + 1000*38 = $ 282000 The Clifton Springs & Danville plants both should produce their total plant capacity of 5000 & 3000 units respectively in order to maximize their profits.

The demand of destinations D1 & D4 are completely met whereas that of D2 falls short by 1000. Also the demand of D3 is completely left unmet due to capacity constraints. The above allocation & amounts shipped to the destinations ensure the optimal profit of $ 282000.

Applied Quantitative Analysis- Transportation maximization problem

10