USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Minimization problems

Minimization problems. An identical procedure is followed for solving the minimization problems. Since the objective is to minimize rather than maximize, a negative (Cj – Zj) value indicates potential improvement. Therefore, the variable associated with largest negative (Cj – Zj) value would be brought into the solution first. Additional variables are brought in to set up such problems. However, such problems involve greater than or equal to constraints, which need to be treated separately from less than or equal to constraints, which are typical of maximization problems. In order to convert such inequalities, the following procedure may be adopted.

Where S1 is a slack variable. However, this will create a difficulty in the simplex method because of the fact that the initial simplex solution starts with slack variables and a negative value (-1S1) would be in the solution, a condition which is not permitted in linear programming. To overcome this problem, the simplex procedure requires that another variable known as artificial variable be added to each equation in which a slack variable is subtracted. An artificial variable may be thought of as representing a fictitious product having very high cost which though permitted in the initial solution to a simplex problem, would never appear in the final solution. Defining A as an artificial variable, the constraint equation can be written as:

3X1 + 2X2-S1 + 1A1 = 1200

Assuming the objective function is to minimize cost, it would be written as :

10X1 + 20X2 + 0S1 + MA1 to be minimised

Where M is assumed to be very large cost (say, 1 million). Also S1 is added to the objective function even though it is negative in constraint equation. An artificial variable is also added to constraint equations equality signs, e.g. if the constraint equation is

3X1 + 2X2 = 1200

then, in simplex it would change to

3X1 + 2X2 + 1A1 = 1200

to satisfy simplex requirement and would be reflected as MA in the objective unction.

Example 3.2 ABC company manufactures and sells two products P1 and P2. Each unit of P1 requires 2 hours of machining and 1 hour of skilled labour. Each unit of P2 requires 1 hour of machining and 2 hours of labour. The machine capacity is limited to 600 machine hours and skilled labour is limited to 650 man hours. Only 300 units of product P1 can be sold in the market. You are required to

a)     Develop a suitable model to determine the optimal product mix.

b)    Find out the optimal product mix and the maximum contribution. Unit contribution from product P1 is Rs 8 and from product P2 is Rs 12.

c)     Determine the incremental contribution/unit of machine-hours, per unit of labour and per unit of product P1.

Sol.

Step 1. Formulation of LP model

Let X1 and X2 be the number of units to be manufactured of the two products P1 and P2 respectively. We are required to find out the number of units of the two products to be manufactured to maximise contribution, i.e., profits when individual contribution of the two products are given. LP model can be formulated as follows:

Step 2. Converting constraints into equations

LP problem has to be written in a standard form, for which the inequalities of the constraints have to be converted into equations. For this purpose, we add a slack variable to each constraint equation. Slack is the unused or spare capacity for the constraints to which it is added. In less than  (≤)

type of constraint, the
slack variable denoted by S, is added to convert inequalities into equations. S is always a non-negative figure or 0. If S is negative, it may be seen that the capacity utilised will exceed the total capacity, which is absord. The above inequalities of this problem can be rewritten by adding suitable slack variables and converted into equations as shown below.

2X1 + X2 + S1= 600

X1 + 2X2 + S2 = 650

X1+S3=300

X1, X2, S1, S2, S3 > 0

Slack variables S1, S2 and S3 contribute zero to the objective function since they represent only unused resources. Let us include these slack variables in the objective function. Then maximize

2 = 8X1 + 12X2 + 0S1 + 0S2+ 0S3

Step 3. Set up the initial solution

Let us recollect that the computational procedure in the simplex method is based on the following fundamental property.

“The optimal solution to a Linear Programming problem always occurs at one of three comer points of the feasible solution space”.

It means that the comer points of the feasible solution region can provide the optimal solution. Let the search start with the origin which means nothing is produced at origin (0, 0) and the value of decision variable X1 and X2 is zero. In such a case, S1 = 600, S2 = 650, S3 = 300 are the spare capacities as nothing (0) is being produced. In the solution at origin we have two variables X1 and X2 with zero value and three variables (S1, S2 and S3) with specific values of 600, 650 and 300. The variables with non-zero values, i.e., S1, S2 and S3 are called the basic variables where as the other variables with zero values i.e. X1, X2 and X3 are called non-basic variables. It can be seen that the number of basic variables is the same as the number of constraints equations (three in the present problem). The solution with basic variables is called basic solution which can be further divided into Basic Feasible Solution and Basic Infeasible Solution. The first type of solutions are those which satisfy all the constraints. In Simplex Method, we search for basic feasible solution only.

Step 4 Developing initial simplex table

The initial decision can be put in the form of a table which is called a Simplex Table or Simplex Matrix. The details of the matrix are as follows.

  1. Row I contains Cj or the contribution to total profit with the production of one unit of each product P1 and P2 Under column I (Cj) are listed the profit coefficients of the basic variables. In the present problem, the profit coefficients of S1, S2 and S3 are zero.
  2. In the column labeled Solution Mix or Product Mix-are listed the variables S1, S2 and S3 their profits are zero and written under column I (Cj) as explained above.
  3. In the column labeled ‘contribution unit quantity’ are listed the values of basic variables included in the solution. We have seen in the initial solution S1 = 600, S2 = 650 and S3 = 300. These values are listed under this column on the right side as shown in table 3.5. Any variables not listed under the solution-mix column are the non-basic variables and their values are zero.
  4. The total profit contribution can be calculated by multiplying the entries in column Cj and column ‘contribution per unit quantity’ and adding them up. The total profit contribution in the present case is 600 × 0 + 650 × 0 + 300 × 0 = 0.
  5. Numbers under X1 and X2 are the physical ratio of substitution. For example, number 2 under X1 gives the ratio of substitution between X1 and S1. In simple words if we wish to produce 2 units of product P1 i.e., X1, 2 units of S1 must be sacrificed. Other numbers have similar interpretation. Similarly, the number in the ‘identity matrix’ columns S1, S2 and S3 can be interpreted as ratios of
    exchange. Hence the numbers under the column S1 represents the ratio of exchange between S1 and the basic variables S1, S2 and S3.
  6. Zj and Cj – Zj are the two final rows. These two rows provide us the total profit and help us in finding out whether the solution is optimal or not Zj and Cj – Zj can be found out in the following

Zj = Cj of S1 (0) × coefficients of X1 in S1 row (2) + Cj of S2 (0) × coefficients of X1 in S2 row(1)+Cj of S3(0) × coefficient X1 in Sj row(1)=0 × 2+0 × 1 +0 × l =0

Cj

Solution mix

8

12

0

0

0

Contribution unit quantity

X1

X2

S1

S2

S3

(Solution values)

0

S1

2

1

1

0

0

600

0

S2

1

2

0

1

0

650

0

S3

1

0

0

0

1

300

Cj

0

0

0

0

0

(Cj-Zj)

8

12

0

0

0

 

Using the same procedure Zj for all the other variable columns can be worked out as shown in the completed first Simplex Table given in Table 3.5.

The number in the (Cj – Zj) row represent the net profit that will result from introducing 1 unit of each product or variable into the solution. This can be worked out by subtracting, Zj total for each column from the Cj values at the top of that variable’s column. For example, Cj – 2j number in the X1 column will 8 – 0 = 8, in the X2 column it will be 12 – 0 = 12 etc.

The value of the objective function can be obtained by multiplying the elements in Cj column with the corresponding elements in the Cj rows i.e. in the present case Z = 8 × 0 + 12 × 0 = 0

Table 3.6

Cj

Solution mix

8

12

0

0

0

Contribution unit quantity (Solution values)

X1

X2

S1

S2

S3

0

S1

2

1

1

0

0

600

0

S2

1

2

0

1

0

650

0

S3

1

0

0

0

1

300

Cj

0

0

0

0

0

(Cj-Zj)

8

12

0

0

0

 

By examining the number in the (Cj – Zj ) row, we can see that total profit can be increased by Rs 8 for each unit of product X1 added to the product mix or by Rs 12 for each unit of product X2 added to the product mix. A positive (Cj – Zj) indicates that profits can still be improved. A negative number of (Cj _ Zj) would indicate the amount by which the profits would decrease, if one unit of the variable was added to the solution. Hence, optimal solution is reached only when there are no positive numbers in (Cj – Zj) row.

Step 5 Test for optimality

Now we must test whether the results obtained are optimal or it is possible to carry out any improvements. It can be done in the following manner.

  1. Selecting the entering variable. We have to select which of the variables, out of the two non-basic variables X1 and X2, will enter the solution. We select the one with maximum value of Cj – Zj. Variable X1 has a (Cj – Zj) value of 8 and X2 has a (Cj – Zj) value of 12. Hence, we select variable X1 as the variable to enter the solution mix and identify the column in which it occurs as the key column with help of a small arrow.
  2. Selecting the variable that leaves the solution. As a variable is entering the solution, we have to select a variable which will leave the solution. This can be done as follows:
    1. Divide each number in the solution value or contribution unit quantity column by corresponding number in the key column i.e., divide 600, 650 and 300 by 1, 2, 0.

Cj

0

0

0

Solution mix

S1

S2

S3

8

X1

2

1

1

12

X2

1

2

0

0

S1

1

0

0

0

S2

0

1

0

0

S3

0

0

1

Solution values

600

650

300

Minimum ratio

600

325

Zf

0

0

0

0

0

(Cj-Zj)

8

12

0

0

0

 

  1. Select the row with smallest non negative ratio as the row to be replaced, in present example the ratios are

S1 row, 600/1 = 600 unit of X2

S2 row, 650/2 = 325 units of X2

S3 row, 300/0 =  units of X2

It is clear that S2 (with minimum ratio) is the departing variable. This row is called the key row.

  1. The number at the intersection of key row and key column is called the key number which is 2 in the present case and is circled in the table.

Step 6 Developing second simplex table

Now we can develop the second simplex table by the following method.

(a)             Determine new values for the key row. To revise the key rows, divide the values in the key row (S2) by the value of the key element (2) and replace departing variable (S2) by the entering variable
(X2).

(b)             Determine new values for other remaining rows. This is done as follows:

New row = old raw number – [Corresponding number in key row] × [corresponding fixed ratio] where fixed ratio = old row number in key column key number.

Now the new S1 and S3 rows are

Row S1 = 600 – 650 × 1/2 = 275

2-1×1/2=1.5

1-2×1/2=0

1-0×1/2=1

0-1×1/2=0

Row S2 = 300 – 650 × 0/2 = 300

1-1×0/2=1

0-2×0/2=0

0-0×0/2=0

0-1×0/2=0

1-0×0/2=1

Key row S2 is replaced by X2 with the following elements

1/2, 1,0, 1/2, 0, 325

Value of Cj and Cj – Zj rows can be calculated as explained earlier. The new revised and improved solution table is shown below.

Table 3.8

Second simplex Table

Cj

Solution mix

8

12

0

0

0

Solution values

Minimum ratio

X1

X2

S1

S2

S3

0

S1

1.5

0

1

0

0

275

0

X2

½

1

0

½

0

325

325

0

S3

1

0

0

0

1

300

Zj

0

0

0

0

0

(Cj-Zj)

8

12

0

0

0

 

Zj values are Z = 0 × 1.5 + 0 × ½ × 0 × 1 = 0 etc.

Minimum ratios by dividing 275, 325 and 300 by corresponding element in the key column i.e., 0, 1, 0.

We find that the value of objective function has been improved from 0 to . But the correct solution is not optimal as there are positive values (12) and (8) in the (Cj – Zj) row. Also, since minimum ratio is 325, we select X2 row to leave the solution as X2 (key column) will enter the solution. The new X2 (key) row will remain same as its elements 1/2, 1, 0, 1/2, 0 and 325 have to be divided by key element, i.e., (shown circled in the above table). However, row S1 and S3 elements will undergo change Row S1 = old row number – [corresponding number in key row 1 × [corresponding fixed ratio]

Fixed ratio = old row number in key column key number = 0

It can be concluded that this problem does not have a optimal solution as X2 row is to be replaced by X2 row.

Example 3.3. Following data is available for a manufacturing company engaged in production of three items X. Y and Z

Product

Time required in hours

Total contribution (Rs.)

Machining

Finishing

X

12

3

1000

Y

6

8

800

Z

8

6

400

Conpany’s capacity

3000

1500

 

You are required to present the above data in the form of LPP to maximize the profit from the production and solve the problem using simplex method.

Now let us construct the first Simplex table as below

Table 3.9

Solution mix

1000

800

400

0

0

Solution values

Min ratio

X1

X2

X3

S1

S2

S1

12

6

8

1

0

3000

250

S2

3

8

6

0

1

1500

500

Zj

0

0

0

0

0

0

(Cj-Zj)

1000

800

400

 

X1 is the key column S1 is the key row and 12 is the key element (circled in the table).

Also it can be seen X1 is the entering variable and S1 is the variable leaving the solution.

Row (1) new = 1/12 Row (1) old, i.e., 1, 1/2, 2/3, 1/12, 0, 250

Row (2) new = Row (2) old – 3 row (1) new

First element =3-3×1=0

Second element =6-3×1/2=13/2

Third element =6-3×2/3=4

Fourth element = 0-3×1/12=-1/4

Fifth element = 1-3 × 0 = 1

Sixth element = 1500 – 3 × 250 = 750

Hence row 1 (S1) will be replaced by 1, 1/2, 2/3, 1/12, 0, 250 and row 2 (S2) will be replaced by 0, 13/2, 4, 1/4, 1, 750.

Second simplex table can now be constructed

Table 3.10

Second simplex table

Cj

Solution mix

1000

800

400

0

0

Solution values

Minimum Ratio

X1

X2

X3

S1

S2

1000

x1

1

0

250

500

0

S2

0

4

1

750

115.4

Zj

1000

500

667

83.3

0

2,50,000

(Cj-Zj)

0

300

-267

-83.3

0

 

It may be seen that the value of objective function has increased from 0 to 2,50,000. But there is a positive entry (300) in the (Cj – Zj) hence this solution is not optimal.

It can also be seen that entering variable is X2 and departing variable is S2.

Third simplex table can now be constructed as follows:

Table 3.11

Third simplex table (optimal solution)

Cj

Solution mix

1000

800

400

0

0

Solution value

X1

X2

X3

S1

S2

1000

x1

1

0

800

x2

0

1

Zj

2,84,615

1000

800

(Cj-Zj)

0

0

 

Since all the entries in (Cj – Zj) row are either zero or negative, this is the optimal solution.

Maximum value of Z, 2,84,615 occurs at x1 = 192 x2 = 115 and x3 = 0.

Example 3.4 ABC Ltd produces four products P1, P2, P3 and P4. Each one of these products has to be processed on three machines X, Y, Z. The capacity of the machines and the time required to manufacture one of each type of products are shown in the table below:

The profit contribution/unit of products P1, P2, P3 and P4 are Rs. 8, 6, 4, 2 respectively.

You are required to formulate the above as a LPP and determine the optimal product mix by using simplex method.

Let X1, X2, X3 and X4 be the number of units of product P1, P2, P3 and P4 respectively.
The mathematical model is as follows

Maximise Z = 8x1 + 6x2 + 4x3 + 2x4

After introducing slack variables S1, S2 and S3 the problem can be rewritten as

Maximise Z = 8x1 + 6x2 + 4x3 + 2x4 + 0S1 + 0S2 + 0S3

Subject to the constraints

2x1+3x2+4x3 +3x4+S1=800

4x1 + 2x2 + x3 + 2x4 + S2 = 600

3x1 + x2 + 2x3 + x4 + S3 = 420

x1, x2, x3, x4, S1, S2 , S3  0

Initial feasible solution can be obtained by purring

x1=x2=x3=x4=0 so that S1=800, S2=600, S3=420 and Z=0.

Now first simplex table can be constructed.

Table 3.12

Cj

Solution mix

8

6

4

2

0

0

0

Solution value

Minimum Ratio

x1

x2

x3

x4

S1

S2

S3

0

S1

2

3

4

3

1

0

0

800

400

0

S2

4

2

1

2

0

1

0

600

150

0

S3

3

1

2

1

0

0

1

420

140

Key row

Zj

0

0

0

0

0

0

0

(Cj-Zj)

8

6

4

2

0

0

0

x1 is the key column.

S3 is the key row.

and 3 is the key number (circled in the table)

Also x1 is the entering variable and S3 is the outgoing variable.

We use the following row operations to get second simplex table by entering x1 in to the solution and removing S3 variable.

Cj

Solution mix

8

6

4

2

0

0

0

Solution value

Minimum Ratio

x1

x2

x3

x4

S1

S2

S3

0

S1

-1

3

2

2

1

0

-1

380

126.7

0

S2

2

0

1

320

240

8

x1

1

0

0

140

46.7

Zj

1120

8

0

0

(Cj-Zj)

0

0

0

It can be seen that Z has improved from 0 to 1120 but since there is still a positive value in (Cj – Zj) it is not optimal solution.

It is now clear that x2 is the entering variable and x1 the departing variable.

Now the third simplex table is to be constructed

We now use the following row operations to get a new solution by entering variable x2 and removing x1 variable.

Table 3.14

Third simplex table

Cj

Solution mix

8

6

4

2

0

0

0

Solution Mix

x1

x2

x3

x4

S1

S2

S3

0

S1

-1

2

2

2

1

0

-1

380

0

S2

0

Zj

10

-4

0

(Cj-Zj)

-2

4

0

 

The student should further attempt this problem to get the optimal solution. The present solution is not the optimal solution as positive values exist in Cj -Zj.