3.7.4 Branch and Bound Technique – Operations Research, 2nd Edition

TABLE 3.48

Since all zjcj ≥ 0, the current solution is optimum and the optimum integer solution is

 

x1 = 4, x2 = 3 with maximum of z = 55

Gomory’s Mixed Integer Method

In mixed integer programming problem only some of the variables are integer constrained, while the other variables may take integer or other real values. Like the pure integer problem, the mixed integer problem should be of the maximisation type and all the coefficients and constants should be integers.

The problem is first solved as a continuous LPP by ignoring the integerality condition. If the values of the integer constrained variables are integers, then the current solution is an optimum solution to the given mixed IPP. Otherwise, select the source row which corresponds to the largest fractional part fk among those basic variables which are constrained to be integers. Then, construct the Gomorian constraint (secondary constraint) from the source row.

From the source row

i.e.

in the form of

i.e.

i.e.

i.e.

where,

sk = Gomorian slack
J+ = {J/fkf ≥ 0}
J = {J/fkj < 0}

Add this secondary constraint at the bottom of the optimum simplex table and use dual simplex method to obtain the new feasible optimal solution. Repeat the procedure until the values of the integer restricted variables are integers in the optimum solution obtained.

Example 1

Solve the following mixed integer programming problem:

 

Maximise z = x1 + x2

subject to the constraints

2x1 + 5x2 ≤ 16
6x1 + 5x2 ≤ 30
x2 ≥ 0, x1 non-negative integer.

Solution: Ignoring the integer restriction, solve the problem by simplex method then the optimum simplex table is

 

TABLE 3.49

But x1 = 7/2 which is not an integer. Take the x1 equation and construct the Gomory’s constraint

i.e.

3 + 1/2 = x1 + 0x2 − 1/4 x3 + 1/4 x4

The Gomorian constraint is

i.e.

1/4s1 + 1/4s2 ≥ 1/2

i.e.

−1/4s1 − 1/4s2 + s3 = −1/2

where, s3 is the Gomorian slack. Add this constraint at the bottom of the above optimum simple table. Since the solution is infeasible apply dual simplex method.

 

TABLE 3.50

Since maximum which corresponds to the variable s1. Hence, s1 enters into the basis. The next iteration is

 

TABLE 3.51

Since all zjcj ≥ 0 and all XBi ≥ 0, the current solution is optimal and feasible. Since x1 = 4 which is an integer the condition is satisfied. The required optimum solution is

 

x1 = 4, x2 = 6/5 and maximum of z = 26/5

3.7.4 Branch and Bound Technique

This method is applicable to both pure (all) as well as mixed integer programming problems and involves the continuous version of the problem.

Branch and bound is a generic method for solving a class of optimization problems. The optimal solution is selected by successive partitioning of the set of all positive solutions into two mutually exclusive and exhaustive subsets, and establishing limit for each set such that all solutions in the set are worse than the limit. The first part of the procedure involving partitioning is called branching while the second part of establishing limit is referred to as bounding.

The branch and bound method first divides the feasible region into smaller subsets and then examines each of them successively until a feasible solution that gives optimal value of objective function is obtained. The iterative procedure is as follows:

Algorithm:

Step 1: Obtain an optimum solution to the given LPP ignoring the restriction of integers.

Step 2: Test the integerality of the optimum solution obtained in step 1. There are two cases:

  1. If the solution is in integers, the current solution is optimum to the given integer programming problem.
  2. If the solution is not in integers, go to next step.

Step 3: Considering the value of the objective function as upperbound, obtain the lowerbound by rounding off to integral values of the decision variables.

Step 4: Let the optimum value of the variable xj is not an integer. Then, subdivide the given LPP into two problems:

Sub-problem 1: Given LPP with an additional constraint ≤ [].

Sub-problem 2: Given LPP with an additional constraint ≤ [] + 1.

where [] is the integer part of .

Step 5: Solve the two sub-problems obtained in step 4.

There may arise three cases:

  1. If the optimum solution of the two sub-problems are integral, then the required solution is one that gives larger value of z.
  2. If the optimum solution of one sub-program is integral and other sub-program has no feasible optimum solution, the required solution is same as that of the subprogram having integer valued solution.
  3. If the optimum solution of one sub-program is integral while that of the other is not integral valued, then record the integral valued solution and repeat step 3 and 4 for the non-integer valued sub-problem.

Step 6: Repeat steps 3 to 5, until all integer valued solutions are recorded.

Step 7: Choose the solution amongst the recorded integer valued solutions that yields an optimum value of z.

Remark: The above method can be represented by an enumeration tree. Each node in the tree represents a sub-program to be evaluated. Each branch of tree creates a new constraint which is added to the original problem.

Example 1

Use branch and bound technique to solve the following integer programming problem:

 

Maximise z = 7x1 + 9x2

subject to

x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
x1 ≥ 0, x2 ≤ 7
x1, x2 are integers.

Solution: First, we ignore the integer restriction and solve the problem by graphical method.

Let P0:

 

Maximise z = 7x1 + 9x2

subject to

x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
x1 ≥ 0, x2 ≤ 7
x1, x2 are integers
x1 + 3x2 = 6 → (0, 2) (−6, 0)
7x1 + x2 = 35 → (5, 0) (0, 35)

The feasible region for P0 is OABC

 

z = 7x1 + 9x2

Now,

Z at O (0, 0) = 7(0) + 9(0) = 0
Z at A(5, 0) = 7(5) + 9(0) = 35
Z at
Z at C(0, 2) = 7(0) + 9(2) = 18

Hence, the optimum solution of P0 is

 

x1 = 9/2, x2 = 7/2 with maximum of z = 63

FIGURE 3.4

The solution obtained is not an integer solution.

Now, x1 = 4 + 1/2, x2 = 3 + 1/2 and the maximum of {1/2, 1/2} = 1/2. Arbitrarily, choose x1 for branching. Now, divide the problem P0 into sub-problems:

P1: Maximise z = 7x1 + 9x2
subject to x1 + 3x2 ≤ 6
  7x1 + x2 ≤ 35
  x1 ≥ 0, x2 ≤ 7
 
  x1, x2 are integers
P2: Maximise z = 7x1 + 9x2
subject to x1 + 3x2 ≤ 6
  7x1 + x2 ≤ 35
  x1 ≥ 0, x2 ≤ 7
 
  x1, x2 are integers

Solution ofP1: Subdivide the feasible region OABC of P0 by adding the region corresponding to the new constraint x1 ≤ 4. The feasible region is ODEC and the point E is (4, 10/3). The optimum solution of P1 is x1 = 4, x2 = 10/3 with maximum of z = 58. The solution obtained is not an integer. Hence, divide the problem P1 into two sub-problems P11 and P12.

P11: Maximise z = 7x1 + 9x2
subject to x1 + 3x2 ≤ 6
  x2 ≤ 7
  x1 ≤ 4
  x2 ≤ 3
  x1, x2 ≥ 0
P12: Maximise z = 7x1 + 9x2
subject to x1 + 3x2 ≤ 6
  x2 ≤ 7
  x1 ≤ 7
  x2 ≥ 4
  x1, x2 ≥ 0

Solution of P2: Subdivide the feasible region OABC of P0 by adding the region corresponding to the constraint x1 ≥ 5. The feasible region for P2 is only the point A and so the optimum solution is

 

x1 = 5, x2 = 0 with maximum of z = 35

Since the solution is integer solution, we record the solution.

Solution of P11: Subdivide the feasible region ODEC by adding the region corresponding to the additional constraint x2 ≤ 3. Hence, the feasible region for P11 is ODFGC.

The solution of P11 is .

Since this is an integer solution we record it.

Solution of P12: Subdivide the feasible region ODEC by adding the region corresponding to the additional constraint x2 ≥ 4. Hence, no feasible region and so no feasible solution to the problem.

The tree diagram is

FIGURE 3.5

If we examine the recorded solutions we observe that the optimum solution is

 

x1 = 4, x2 = 3 with maximum ofz = 55

3.8 ZERO-ONE PROGRAMMING

3.8.1 Introduction

If all the variables in a linear programming problem are restricted to take the value zero or one only, then such a linear programming problem is known as a zero-one programming problem. Various methods are available for solving the zero-one programming problems.

The general integer programming methods such as the branch and bound method can be used to solve zero-one linear programming problems simply by introducing an additional constraint that all the variables must be less than or equal to one. The general integer programming methods were primarily developed for solving such type of problems; they do not take advantage of the special features of zero-one linear programming. Thus, a number of methods have been developed to solve zero-one linear programming problems more easily.

3.8.2 Examples of Zero-one Programming Problems

  1. Assignment problem
  2. Knapsack problem
  3. Fixed charge problem
  4. Travelling salesmen problem

3.8.3 Importance of Zero-one Integer Programming

The study of zero-one programming is important because of the following reasons:

  1. A certain class of non-linear integer programming problems can be converted into equivalent zero-one programming problems.
  2. A number of industrial and managerial problems can be formulated as zero-one programming problems.

3.8.4 Solution Methodologies

The zero-one problem can be solved by Geometry’s cutting plane method or the branch and bound method with the additional constraint that all the variables have values of zero or one.

Additive Algorithm

A number of efficient algorithms have been proposed to solve such problems, of which the additive algorithm by E. Bales is the one most commonly used.

Prerequisites: The continuous version of the zero-one problem must start dual feasible, that is, it should be optimal but infeasible. The integer problem must be of minimisation type, all objective function coefficients should be non-negative and constraints should be of ≤ type. That is,

 

Minimise Z =

subject to

Any linear programming problem can be converted into this form by the following operations:

  1. Change the sign of the objective function if it is of maximisation type.
  2. Replace all equality constraints by two weak inequalities, one of ≤ type and the other of type.
  3. Multiply all type constraints by −1 to convert them to ≤ type.
  4. Define a new variable yj such that

where yj is the binary variable in the objective function as well as the constraints. Slack variables si can be now added to the constraints to put then into the form

If the primal feasible, nothing more needs to be done. However, if it is optimally infeasible, additive algorithm can be used to find the optimal solution. As in the branch and bound method, the branching in this algorithm is also based on the use of branching variable xj. However, since xj is a binary variable two branches are associated, one for xj = 0 and the other for xj = 1. Bounding can be done as in the branch and bound method. An improved integer solution forms an upper bound on the minimum value of the objective function. The fathoming of the sub-problem can be done as follows:

  1. The sub-problem yields a feasible integer solution.
  2. The sub-problem does not lead to a feasible solution.
  3. The sub-problem does not yield a better upper bound.

Difference between branch and bound and additive algorithm:

In additive algorithm heuristics are used instead of solving the LPP.

Example 1

Solve the zero-one integer programming problem by using additive algorithm.

 

Maximise z = x1 + 2x2 − 3x3

subject to

20x1 + 15x2x3 ≤ 10
12x1 − 3x2 − 4x3 ≤ 20
3x1 + 5x2 + x3 ≤ 6
xj = 0 or 1 for all j

Solution:

  1. Multiply the objective function by −1 to convert the problem into minimisation type. The objective function becomes

     

    Minimise z′ = −x1 −2x2 + 3x3 where z′ = −z.

    To make the negative coefficients of the objective function as positive, make the following substitution.

    where yj is a binary variable.

     

    x1 = 1 − y1, x2 = 1 − y2  and  x3 = y3
    Minimise z′ = −(1 − y1) −z(1 − y2) + 3y3
    = y1 + 2y2 + 3y3 − 3

    The constant 3 can be omitted since it will not make any difference, being independent of the values of yj.

     

    Minimise z″ = (z′ + 3) = y1 + 2y2 + 3y3

    The constraints can be written as

     

    20 (1 − y1) + 15(1 − y2) − y3 ≤ 10  or  −20y1 − 15y2y3 ≤ −25
    12 (1 − y1) − 3(1 − y2) − 4y3 ≤ 10  or  −12y1 + 3y2 − 4y3 ≤ 5
    3 (1 − y1) + 15(1 − y2) + y3 ≤ 6  or  −3y1 − 5y2y3 ≤ −2

  2. Using the slack variable s1, s2, and s3 the constraints can be rewritten as

     

    −20y1 − 15y2y3 + s1 = −25

    or

    Now the problem is in the proper format to use implicit enumeration. By setting y1 = y2 = y3 = 0, the initial solution is obtained as s1 = −25, s2 = 5, s3 = −2 with z″ = 0. The solution is represented by node 1 in Fig. 3.6. The solution obtained is infeasible as s1 and s3 are negative. The variables y1, y2 and y3 are all free at this stage to take zero or one as values and hence are called free variables.

    Now check if the violated constraints (3.8.1) and (3.8.3) can be satisfied by assigning a value of one to each of the variables having positive coefficients in these constraints. There is no use in assigning the value of one to the variables with negative coefficients since it will worsen the feasibility.

    FIGURE 3.6

    Now substituting y1 = y2 = y3 = 1 in constraint (3.8.1) gives s1 = 11 > 0, and substituting y1 = y2 = 1 in constraint (3.8.3) gives s3 = 6 > 0. This indicates that there is a possibility of a feasible solution emanating from node 1.

Measure of infeasibility: To move the solution towards feasibility, some of the variables have to be raised to level 1. A number of heuristic procedures have been proposed to select the variable from the set of free variables. One method is to select the variable that will minimise the total feasibility over all the constraints. The infeasibility for a non-negative constraint is zero, and for a negative constraint it is the amount that must be added to make it zero. If uj measures the total infeasibility when variable yj is raised to level 1, then uj is defined as

Now

u1 =(−25 + 20) + 0 + 0 = −5,
u2 = (−25 + 15) + 0 + 0 = −10,
u3 = (−25 +1) + 0 + (−2 −1) = −27.

The variable y1 with the smallest infeasibility (= −5) is selected to take the value one while y2 and y3 remain free (note that the tie can be broken arbitrarily).

This solution y1 = 1, y2 = 0 with z" = 1 corresponds to node 2 of Fig. 3.6. This solution when substituted in constraints (3.8.1), (3.8.2) and (3.8.3) gives

 

s1=−25 + 20 = −5
s2 = 5 + 12 = 17
s3 =−2 + 3 = 1.

Thus, the above solution (node 2) is infeasible but constraint (3.8.1) can be satisfied by setting the free variables having positive coefficients equal to one. Hence, there is possibility of a feasible solution emanating from node 2.

Now y1 = 1 and one of the variables y2 and y3 is to be assigned the value one.

 

u2 = 0 + 0 + 0 = 0,
u3 = −4 + 0 + 0 = −4.

Since u2 is the smallest infeasibility, y2 is selected to take the value one (in addition to y1), while variable y3 remains free. This corresponds to node 4 in Fig. 3.7, which gives the solution y1 = y2 = 1, y3 = 0, z" = 3.

FIGURE 3.7

This solution when substituted in constraints (3.8.1), (3.8.2) and (3.8.3) gives

 

s1 = −25 + 20 + 15 = 10,
s2 = 5 + 12 − 3 = 14,
s3 =−2 + 3 + 5 = 6.

The solution is feasible and can be recorded as the best available solution so far. The value of the objective function corresponding to this solution will act as an upper bound for the future solutions.

Thus zu = 3

Since any solution with y1 = y2 = 1 and some other variable raised to one will destroy the optimality, there is no need to examine any solution emanating from node 4. In other words, all solutions emanating from node 4 have been implicitly enumerated. Node 4 is, then, said to be fathomed.

Now backtrack and go back to node 2. The other solution emanating from this node is y1 = 1, y2 = 0, y3 free to take value zero or one. This corresponds to node 5. When y3 = 0 we get an infeasible solution [constraints (3.8.1), (3.8.2) and (3.8.3) yield s1 = −5, s2 = 17, s3 = 1] and when y3 = 1, the optimality is destroyed (since y1 = 1, y2 = 0, y3 = 1 yields z" = 1 + 0 + 3 = 4, which is higher than the min zu = 3). There is no need for checking the feasibility condition of this solution (y1 = 1, y2 = 0, y3 = 1) Thus, since node 5 does not promise a better solution, it is fathomed.

Backtracking to node 1, we have node 3 emanating from node 1. The solution corresponding to node 3 is y1 = 0, y2 and y3 free to take value zero or one.

Now, we check the possibilities of getting a feasible solution emanating from node 3.

When y1 = 0, y2 = 1 and y3 is set at one, from constraints (3.8.1), (3.8.2) and (3.8.3) we get

 

s1 = −25 + 0 + 15 + −9,
s2 = 5 + 0 − 3 + 4 = 6,
s3=−2 + 0 + 5 − 1 = 2.

Since this does not give a feasible solution, node 3 is fathomed. Thus the optimal solution is

 

y1 = y2 = 2, y3 = 0; = 3.

This solution can now be translated in terms of the original variables as follows:

 

x1 = 1 − y1 = 1 − 1 = 0,
x2 = 1 − y2 = 1 − 1 = 0,
x3 = y3 = 0,
Zmin = 0 + 0 − 0 = 0.

3.9 LIMITATIONS OF LINEAR PROGRAMMING PROBLEM

In this section we will see some advantages and some limitations of linear programming problems.

3.9.1 Advantages of Linear Programming Problem

  1. It provides an insight and perspective into the problem environment. This generally results in clear picture of the true problem.
  2. It makes a scientific and mathematical analysis of the problem situations.
  3. It gives an opportunity to the decision-maker to formulate his strategies consistent with the constraints and the objectives.
  4. It deals with changing situations. Once a plan is arrived through the linear programming it can also be evaluated for changing conditions.
  5. By using linear programming the decision-maker makes sure that he is considering the best solution.

3.9.2 Limitations of Linear Programming

  1. The major limitation of linear programming is that it treats all relationship as linear. But it is not true in many real life situations.
  2. The decisions variables in some LPP would be meaningful only if they are integer values. But sometimes we get fractional values to the optimal solution, where only integer values are meaningful.
  3. All the parameters in the linear programming model are assumed to be known constants. But in real life they may not be known completely or they may be probabilistic and they may be liable for changes from time to time.
  4. The problems are complex if the number of variables and constraints are quite large.
  5. Linear programming deals with only a single objective problem whereas in real life situations, there may be more than one objective.
EXERCISES

Section 3.1

1. Write the dual of the following LPP

 

Maximise z = x1 + 2x2 + x3

subject to

2x1 + x2x3 ≤ 2
− 2x1 + x2 − 5x3 ≥ − 6
4x1 + x2 + x3 ≤ 6
x1, x2, x3 ≥ 0

[Answer: The dual is minimise w = 2y1 + 6y2 + 6y3, subject to 2y1 + y2 + 4y3 ≥ 1, y1y2 + y3 ≥ 1, − y1 + 5y2 + y3 ≥ 1 and y1, y2, y3 ≥ 0.]

2. Write the dual of the LPP

 

Maximise z = 3x + 10y + 2z

subject to

2x + 3y + 2z ≤ 7
3x − 2y + 4z = 3

and

x, y, z ≥ 0

[Answer: The dual problem is minimise w = 7r + 3s subject to 2r + 3s ≥ 3, 3r − 2s ≥ 10, 2r + 4s ≥ 2 and r ≥ 0, s is unrestricted.]

3. Obtain the dual of the following LPP

 

Maximise z = 3x1 + x2 + 2x3x4

subject to

2x1x2 + 3x3 + x4 = 1
x1 + x2x3 + x4 = 3
x1, x2, x3 ≥ 0 and x4 is unrestricted.

[Answer: The dual is minimise w = y1 + y2, subject to 2y1 + y2 ≥ 3, − y1 + y2 ≥ 1, 3y1y2 ≥ 2, y1 + y2 = − 1; y1 and y2 are unrestricted.]

4. Write the dual of the LPP

 

Minimise z = 7x1 + 3x2 + 8x3

subject to

8x1 + 2x2 + x3 ≥ 3
3x1 + 6x2 + 4x3 ≥ 4
4x1 + x2 + 5x3 ≥ 1
x1 + 5x2 + 2x3 ≥ 7
x1, x2, x3 ≥ 0

[Answer: The dual LPP is Maximise w = 3y1 + 4y2 + y3 + 7y4, subject to 8y1 + 3y2 + 4y3 + y4 ≤ 7, 2y1 + 6y2 + y3 + 5y4 ≤ 3, y1 + 4y2 + 5y3 + 2y4 ≤ 8, y1, y2, y3, y4 ≥ 0.]

5. Write the dual of the primal

 

Maximise z = 6x1 + 6x2 + x3 + 7x4 + 5x5

subject to

3x1 + 7x2 + 8x3 + 5x4 + x5 = 2
2x1 + x2 + 3x4 + 9x5 = 6
x1, x2, x3, x4 ≥ 0

and

x5 unrestricted.

[Answer: The dual is minimise w = 2y1 + 6y2 subject to 3y1 + 2y2 ≥ 6, 7y1 + y2 ≥ 7, 8y1 + 3y2 ≥ 1, 5y1 + 2y2 ≥ 7, y1 + 9y2 = 5; y1 and y2 are unrestricted.]

6. Apply simplex method to solve the following LPP

 

Maximise z = 30 x1 + 23x2 + 9x3,

subject to

6x1 + 5x2 + 3x3 ≤ 26, 4x1 + 2x2 + 5x3 ≤ 7, every xj 0

Also, read the solution to the dual from the final Table of primal.

[Answer: Solution of the primal is x1 = 0, x2 = 7/2, x3 = 0, maximum of z = 161/2. The solution of the dual problem is y1 = 0, y2 = 23/2 and minimum of w = 161/2.]

7. Applying the concept of duality, solve the LPP

 

Maximise z = 3x1 + 4x2

subject to

x1x2 ≤ 1
x1 + x2 ≤ 4
x1 − 3x2 ≤ 3
x1, x2 ≥ 0

[Answer: Since the dual problem does not possess any optimum basic feasible solution hence there exists an unbounded solution to the primal problem.]

8. Solve the following LPP by formulating its dual

 

Minimise z = 50x1 − 80x2 − 140x3

subject to

x1x2 − 3x3 ≥ 4
x1 − 2x2 − 2x3 ≥ 3

and

x1, x2, x3 ≥ 0

[Answer: Dual has no feasible solution and hence primal has no feasible solution.]

9. Use duality to solve the LPP

 

Minimise z = 8x1 − 2x2 − 4x3

subject to

x1 − 4x2 − 2x3 ≥ 2
x1 + x2 − 3x3 − 1
−3x1x2 + x3 ≥ 1
x1, x2, x3 ≥ 0

[Answer: Dual has an unbounded solution and hence primal has either an unbounded or no solution.]

10. Use duality to solve the LPP

 

Minimise z = 4x1 + 2x2 + 3x3

subject to

2x1 + 4x3 ≥ 5
2x1 + 3x2 + x3 ≥ 4
x1, x2, x3 ≥ 0

[Answer: The solution of the primal is x1 = 0, x2 = 11/12, x3 = 5/4 with minimum of z = 67/12. The solution of the dual is y1 = 7/2, y2 = 2/3 and maximum of w = 67/12.]

Section 3.2

11. Solve the following linear programming problems using dual simplex method.

  1. Minimise z = 2x1 + x2

    subject to

    3x1 + x2 ≥ 3
    4x1 + 3x2 ≥ 6
    x1 + 2x2 ≥ 3
    x1, x2 ≥ 0

    [Answer: x1 = 3/5, x2 = 6/5 with minimum of z = 12/5.]

  2. Minimise z = 3x1 + x2

    subject to

    x1 + x2 ≥ 1
    2x1 + 3x2 ≥ 2
    x1, x2 ≥ 0

    [Answer: x1 = 0, x2 = 1 with minimum of z = 1.]

  3. Minimise z = x1 + 2x2

    subject to

    2x1 + x2 ≥ 4
    x1 + 2x2 ≥ 7
    x1, x2 ≥ 0

    [Answer: x1 = 0, x2 = 2 with minimum of z = 4.]

  4. Minimise z = 3x1 + 2x2 + x3 + 4x4

    subject to

    2x1 + 4x2 + 5x3 + x4 ≥ 10
    3x1x2 + 7x3 − 2x4 ≥ 2 ×
    5x1 + 2x2 + x3 + 6x4 ≥ 15
    x1, x2, x3, x4 ≥ 0

    [Answer: x1 = 65/23, x2 = 0, x3 = 20/23, x4 = 0 with minimum of z = 215/213.]

  5. Minimise z = 2x1 + 9x2 + 24x3 + 8x4 + 5x5

    subject to

    x1 + x2 + 2x3x5x6 = 1,
    −2x1 + x3 + x4 + x5x7 = 2,
    xj 0, j = 1, …, 7

    [Answer: x1 = x2 = x5 = x6 = x7 = 0, x3 = 1/2, x4 = 3/2 with minimum of z = 24.]

  6. Minimise z = x1 + 2x2 + 3x3

    subject to

    x1x2 + x3 ≥ 4
    x1 + x2 + 2x3 ≤ 8
    x2x3 ≥ 2
    x1, x2, x3 ≥ 0

    [Answer: x1 = 6, x2 = 2, x3 = 0 with minimum ofz = 10.]

Section 3.3

12. Use revised simplex method to solve the following linear programming problems:

  1. Maximise z = 3x1 + 2x2 + 5x3

    subject to

    x1 + 2x2 + x3 ≥ 430
    3x1 + 2x3 ≥ 460
    x1 + 4x2 ≤ 420
    x1, x2, x3 ≥ 0

    [Answer: x1 = 0, x2 = 100, x3 = 230 with maximum ofz = 1350.]

  2. Minimise z = x1 + x2

    subject to

    x1 + 2x2 ≥ 7
    4x1 + x2 ≥ 6
    x1, x2 ≥ 0

    [Answer: x1 = 5/7, x2 = 22/7 with minimum of z = 27/7.]

  3. Maximise z = 2x1 + 3x2

    subject to

    x1 + x2 ≥ 0
    x1 ≤ 4

    and

    x1, x2 ≥ 0

    [Answer: Unbounded solution.]

  4. Maximise z = x1 + x2

    subject to

    2x1 + 5x2 ≥ 6,
    x1 + x2 ≥ 2,
    x1, x2 ≥ 0

    [Answer: Unbounded solution.]

  5. Maximise z = x1 + x2

    subject to

    3x1 + 2x2 ≤ 6
    x1 + 4x2 ≤ 4
    x1, x2 ≥ 0

    [Answer: x1 = 8/5, x2 = 3/5 with maximise of z = 11/5]

  6. Maximise z = x1 + 2x2

    subject to

    3x1 + 2x2 ≥ 6
    x1 + 6x2 ≤ 3
    x1, x2 ≥ 0

    [Answer: Unbounded solution.]

Section 3.4

13. Consider the LPP

 

Maximise z = 2x1 + x2 + 4x3x4

subject to

x1 + x2 + x3 − 3x4 ≤ 8
l−x1 + x3 + 2x4 ≤ 0
2x1 + 7x2 − 5x3 − 10x4 ≤ 21

and

x1, x2, x3, x4 ≥ 0

  1. Solve the LPP.
  2. Discuss the effect of change of b2 to 11.
  3. Discuss the effect of change of b to [3, − 2, 4].

[Answer: The optimal solution is

  1. x1 = 8, x2 = x3 = x4 = 0, maximum of z = 16
  2. x1 = 49/2, x2 = 0 = x3, x4 = 11/2, maximum of z = 87/2
  3. No feasible solution.]

14. Consider the LPP

 

Maximise z = 3x1 + 5x2 + 4x3

subject to

2x1 + 3x2 ≤ 8
2x2 + 5x3 ≤ 10
3x1 + 2x2 + 4x3 ≤ 15
x1, x2, x3 ≥ 0

  1. Solve the LPP.
  2. Find the range over which b2 can be changed maintaining feasibility of the solution.

[Answer: (a) x1 = 89/41, x2 = 50/41, x3 = 62/41 with maximum of z = 765/41.

(b) 25/4 ≤ Δ b2 ≤ 89/12.]

15. Consider the LPP

 

Maximise z = − x1 + 2x2x3

subject to

3x1 + x2x3 ≤ 10
x1 + 4x2 + x3 ≥ 6
x2 + x3 ≤ 4
x1, x2, x3 ≥ 0

  1. Determine an optimum solution to the problem.
  2. Determine the ranges for discrete changes in the components b2 and b3 of the required vector so as to maintain the optimality of the current optimum solution.

[Answer: (a) The optimal solution is x1 = 0, x2 = 4, x3 = 0 with maximum of z = 8.

(b) Δb2 ≤ 10, − 5/2 ≤ Δ b3 ≤ 6].

16. Given the LPP

 

Minimise z = 3x1 + 6x2 + x3

subject to the constraints

x1 + x2 + x3 ≥ 6
x1 + 5x2x3 ≥ 4
x1 + 5x2 + x3 ≥ 24
x1, x2, x3 ≥ 0

  1. Solve the LPP
  2. Discuss the effect of changing the required vector from [6, 4, 24] to [6, 2, 12] on the optimum solution.

[Answer: (a) x1 = 14, x2 = 0, x3 = 0, minimum of z = 52

(b) x1 = 7, x2 = 0, x3 = 5; minimum of z = 26.]

17. Solve the following linear programming problem

 

Maximise 3x1 + 5x2

subject to

x1 + x2 ≤ 1
2x1 + x2 ≤ 1
x1, x2 ≥ 0

Determine the range of variation of the cost coefficients cj (j = 1, 2) corresponding to the optimal solution.

[Answer: x1 = 0, x2 = 1, maximum z = 5, − ∞ < c1 < 5 and 3 ≤ c2 ≤ ∞]

18. Consider the LPP

 

Minimise z = 5x1 + 3x2

subject to

3x1 + 5x2 ≤ 15
5x1 + 6x2 ≤ 10

and,

x1, x2 ≥ 0

  1. Solve the LPP.
  2. Find how far the component c1 of C can be increased without affecting the optimality of the solution.

[Answer: (a) x1 = 20/19, x2 = 45/19 with minimum of z = 235/19, (b) 5 ≤ c1 ≤ 15/2]

19. Consider the LPP

 

Maximise z = 3x1 + 5x2

subject to

x1 ≤ 4
3x1 + 2x2 ≤ 18

and,

x1, x2 ≥ 0

  1. Solve this LPP.
  2. If a new variable x5 is added to this problem with a column and c5 = 7, find the change in the optimal solution.

[Answer: (a) x1 = 0, x2 = 9 with maximum of Z = 45.

(b) x1 = 0, x2 = 5, x5 = 5 with maximum of Z = 53.]

20. Consider the LPP.

 

Maximise z = 5x1 + 3x2 + 7x3

subject to

x1 + x2 + 2x3 ≤ 22
3x1 + 2x2 + x3 ≤ 26
x1 + x2 + x3 ≤ 18

and,

x1, x2, x3 ≥ 0.

  1. Solve the LPP.
  2. What will be the solution if the first constraint changes to x1 + x2 + 2x3 ≤ 26.

[Answer: (a) x1 = 6, x2 = 0, x3 = 52/2 and maximum of z = 26.

(b) x1 = 26/5, x2 = 0, x3 = 52/2 and maximum of z = 494/5.]

21.

  1. Solve the following LPP

     

    Maximise z = x1 + 5x2 + 3x3

    subject to

    x1 + 2x2 + x3 = 3
    2x1x2 = 4

    and,

    x1, x2, x3 ≥ 0

  2. If the objective function is changed to maximise z = 2x1 + 5x2 + 2x3, find the new optimal solution.

[Answer: (a) x1 = 2, x2 = 0, x3 = 1

(b) x1 = 11/5, x2 = 2/5, x3 = 0 with maximum of z = 32/5.]

22. Given the LPP

Maximise z = 10x1 + 3x2 + 6x3 + 5x4

subject to the constraints

x1 + 2x2 + x4 ≤ 6
3x1 + 2x3 ≤ 5
x2 + 4x3 + 5x4 ≤ 3
x1, x2, x3 ≥ 0

Compute the limits for a11 and a23 so that the new solution remains optimum feasible.

[Answer: − ∞ ≤ a11 ≤ 51/10, 39/40 ≤ a23 < ∞]

Section 3.5

23. Consider the parametric linear programming problem

Maximise z = (θ − 1) x1 + x2

subject to

x1 + 2x2 ≤ 10
2x1 + x2 ≤ 11
x1 − 2x2 ≤ 3
x1, x2 ≥ 0

Perform a complete parametric analysis. Identify all critical values of the parameter θ and the optimal basic solutions.

[Answer: x1 = 0, x2 = 5  for  0 ≤ θ ≤ 3/2

x1 = 4, x2 = 3  for  3/2 ≤ θ ≤ 3

x1 = 5, x2 = 1  for  3 ≤ θ ]

24. For the following linear programming problem:

 

Minimise z = λx1 − λx2 − x3 + x4

subject to

3x1 − 3x2x3 + x4 ≥ 5
2x1 − 2x2 + x3x4 ≤ 3
x1, x2, x3, x4 ≥ 0.

[Answer: For − 2 ≤ λ < 3, x1 = 8/5, x2 = 0, x3 = 0, x4 = 1/5 with minimum of z = 1/5 + 8/5λ.

For λ > 3, no solution exists.]

25. Solve the problem

 

Maximise z = 3x1 + 2x2 + 5x3

subject to

x1 + 2x2 + x3 ≤ 430 + 500λ
3x1 + 2x3 ≤ 460 + 100λ
x1 + 4x2 ≤ 420 − 200λ
x1, x2, x3 ≥ 0.

[Answer: For 0 ≤ λ ≤ 1/55, (x1, x2, x3) = (0, 100 + 225λ, 230 + 5λ) and minimum of z = 1, 350 +

700λ

For 1/55 ≤ λ ≤ 2.1, (x1, x2, x3) = (0, 105 − 50λ, 230 + 50λ) and minimum of z = 1,360 + 150λ; for λ > 2.1, no feasible solution exists.]

Section 3.6

26. Solve the following linear goal programming problem

 

Maximise z = {o3 + o4, o1, u2, u3 + 8/5 u4}

subject to

g1: x1 + x2 + u1o1 = 20
g2: x1 + x2 + u2o2 = 50
g3: x1 + u3o3 = 15
g4: x2 + u4o4 = 8,

xi, ui, oi ≥ 0 where the goals are written in order of priority.

[Answer: x1 = 12, x2 = 8 and maximum of z = (0, 0, 30, 3).]

27. The manager of the only record shop in a town has a decision problem that involves multiple goals. The record shop employs five full-time and four part-time salesmen. The normal working hours per month for a full-time salesman and a part-time salesman are 160 hours and 80 hours, respectively. According to the performance records of salesmen, the average sales has been five records per hour for full-time salesmen and two records per hour for part-time salesmen. The average hourly wage rates are 3 for full-time salesmen and 2 for part-time salesmen. Average profit from the sales of a record is 1.50.

In view of the past sales record and increased enrolment at the local college, the manager feels that the sales goal for the next month should be 5500 records. Since the shop is open six days a week, overtime is often required of salesman. The manager believes that a good employer employee relationship is an essential factor of business success.

Therefore, he feels that a stable employment level with occasional overtime requirement is a better practice than an unstable employment level with no overtime. However, he feels that over time of more than 100 hours among the full-time salesmen should be avoided because of the declining sales effectiveness caused by fatigue.

The manager, has set the following goals:

  1. The first goal is to achieve a sales goal of 5500 records for the next month.
  2. The second goal is to limit the overtime of full-time salesmen to 100 hours.
  3. The third goal is to provide job security to salesmen. The manager feels that full utilization of employees’ regular working hours (no layoffs) is an important factor for a good employer-employee relationship. However, he is twice as concerned with the full utilization of full-time salesmen as with the full utilization of part-time salesmen.
  4. The last goal is to minimise the sum of overtime for both full-time and part-time salesmen. The manager desires to assign differential weights to the minimisation of overtime according to the net marginal profit ratio between the full-time and part-time salesmen.

Formulate the situation as a goal programming problem.

[Answer: The LPP is

Maximise

subject to

Section 3.7

28. Find the optimum integer solution to the following liner programming problems using Gomory’s cutting plane method.

  1.  

    Maximise z = x1 + x2

    subject to

    3x1 + 2x2 ≤ 5
    x2 ≤ 2

    and

    x1 ≥ 0, x2 ≥ 0 and are integers.

    [Answer: x1 = 0, x2 = 2 with maximum of z = 2. (or)
    x1 = 1, x2 = 1 with maximum of z = 2.]

  2. Maximise z = 2x1 + 2x2

    subject to

    5x1 + 3x2 ≤ 8
    2x1 + 4x2 ≤ 8

    and

    x1, x2 ≥ 0 and are all integers.

    [Answer: x1 = 1, x2 = 1 with maximum of z = 4 (or)
    x1 = 0, x2 = 2 with maximum of z = 4.]

  3. Maximise z = 3x1 + 4x2

    subject to

    3x1 + 2x2 ≤ 8
    x1 + 4x2 ≤ 10

    and

    x1, x2 ≥ 0 and are integers.

    [Answer: x1 = 0, x2 = 3 with maximum of z = 12.]

  4. Maximise z = x1 − 2x2

    subject to

    4x1 + 2x2 ≤ 15
    x1, x2 ≥ 0 and are integers.

    [Answer: x1 = 3, x2 = 0 with maximum of z = 3.]

  5. Maximise z = 7x1 + 9x2

    subject to

    x1 + 3x2 ≤ 6
    7x1 + x2 ≤ 35
    x1, x2 ≥ 0 and are integers.

    [Answer: x1 = 4, x2 = 3 with maximum of z = 55.]

  6. (vi)

    Minimise z = 9x1 + 10x2

    subject to

    x1 ≤ 9
    x2 ≤ 8
    4x1 + 3x2 ≥ 40
    x1, x2 ≥ 0 and are integers.

    [Answer: x1 = 9, x2 = 2 with minimum of z = 101.]

  7. Maximise z = 2x1 + 20x2 − 10x3

    subject to

    5x1 + 20x2 + 4x3 ≤ 15
    6x1 + 20x2 + 4x3 = 20
    x1, x2 x3 ≥ 0 and are integers.

    [Answer: x1 = 2, x2 = 0, x3 = 2 with maximum of z = − 16.]

  8. Maximise z = 3x2

    subject to

    3x1 + 2x2 ≤ 7
    x1x2 − 2
    x1, x2 ≥ 0 and are integers.

    [Answer: Simplex method gives the integer solution: x1 = 0, x2 = 2 with maximum of z = 6.]

  9. Maximise z = x1 + 5x2

    subject to

    x1 + 10x2 ≤ 20
    x1 ≤ 2
    x1, x2 ≥ 0 and are integers.

    [Answer: x1 = 2, x2 = 1, with maximum of z = 7.]

  10. Maximise z = 2x1 + 2x2

    subject to

    5x1 + 3x2 ≤ 8
    x1 + 2x2 ≤ 4
    x1, x2 ≥ 0 and are integers.

    [Answer: x1 = 1, x2 = 1 with maximum of z = 4.]

29. Solve the following mixed integer programing problems:

  1. Maximise z = x1 + x2

    subject to

    3x1 + 2x2 ≤ 5
    x2 ≤ 2

    and

    x1, x2 ≥ 0 and x1 is an integer.

    [Answer: x1 = 0, x2 = 2 with maximum of z = 2.]

  2. Minimise z = 10x1 + 9x2

    subject to

    x1 ≤ 8
    x2 ≤ 10
    5x1 + 3x2 ≥ 45
    x1, x2 ≥ 0, x1 is an integer.

    [Answer: x1 = 8, x2 = 5/3 with minimum of z = − 95.]

  3. Maximise z = 4x1 + 6x2 + 2x3

    subject to

    4x1 − 4x2 ≤ 5
    x1 + 6x2 ≤ 5
    x1 + x2 + x3 ≤ 5
    x1, x2, x3 ≥ 0 and x1, x3 are integers.

    [Answer: x1 = 2, x2 = 1, x3 = 6 with maximum of z = 26.]

  4. Maximise z = 3x1 + x2 + 3x3

    subject to −x1 + 2x2 + x3 ≤ 4
    4x1 − 3x2 ≤ 2
    x1 − 3x2 + 2x3 ≤ 3
    x2 ≥ 0 and x1, x3 are non-negative integers.

    [Answer: x1 = 5, x3 = 3, x2 = 2.75 with maximum of z = 26.75.]

31. Use branch and bound technique to solve the following integer programming problem.

  1. Maximise z = x1 + x2

    subject to

    4x1x2 ≤ 10
    2x1 + 5x2 ≤ 10
    2x1 − 3x2 ≤ 6
    x1, x2 ≥ 0 and are integers.

    [Answer: x1 = 2, x2 = 1, with maximum of z = 3.]

  2. Maximise z = 3x1 + 4x2

    subject to

    3x1x2 + x3 = 12
    3x1 + 11x2 + x4 = 66
    xj ≥ 0 and are integers for j = 1, 2, 3, 4.

    [Answer: x1 = 5, x2 = 4 with maximum of z = 31.]

  3. Maximise z = x1 + 4x2

    subject to

    2x1 + 4x2 ≤ 7
    5x1 + 3x2 ≤ 15
    x1, x2 ≥ 0 and are integers.

    [Answer: x1 = 1, x2 = 1 with maximum of z = 5.]

  4. Maximise z = 3x1 + 4x2

    subject to

    7x1 + 16x2 ≤ 52
    3x1 − 2x2 ≤ 18
    x1, x2 ≥ 0 and are integers.

    [Answer: x1 = 5, x2 = 1, with maximum of z = 19.]