Since all z_{j} − c_{j} ≥ 0, the current solution is optimum and the optimum integer solution is
x_{1} = 4, x_{2} = 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 f_{k} 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,
s_{k} = Gomorian slack
J^{+} = {J/f_{kf} ≥ 0}
J^{−} = {J/f_{kj} < 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 = x_{1} + x_{2}
subject to the constraints
2x_{1} + 5x_{2} ≤ 16
6x_{1} + 5x_{2} ≤ 30
x_{2} ≥ 0, x_{1} nonnegative integer.
Solution: Ignoring the integer restriction, solve the problem by simplex method then the optimum simplex table is
TABLE 3.49
But x_{1} = 7/2 which is not an integer. Take the x_{1} equation and construct the Gomory’s constraint
i.e.
3 + 1/2 = x_{1} + 0x_{2} − 1/4 x_{3} + 1/4 x_{4}
The Gomorian constraint is
i.e.
1/4s_{1} + 1/4s_{2} ≥ 1/2
i.e.
−1/4s_{1} − 1/4s_{2} + s_{3} = −1/2
where, s_{3} 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 s_{1}. Hence, s_{1} enters into the basis. The next iteration is
TABLE 3.51
Since all z_{j} − c_{j} ≥ 0 and all X_{Bi} ≥ 0, the current solution is optimal and feasible. Since x_{1} = 4 which is an integer the condition is satisfied. The required optimum solution is
x_{1} = 4, x_{2} = 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:
 If the solution is in integers, the current solution is optimum to the given integer programming problem.
 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 x_{j} is not an integer. Then, subdivide the given LPP into two problems:
Subproblem 1: Given LPP with an additional constraint ≤ [].
Subproblem 2: Given LPP with an additional constraint ≤ [] + 1.
where [] is the integer part of .
Step 5: Solve the two subproblems obtained in step 4.
There may arise three cases:
 If the optimum solution of the two subproblems are integral, then the required solution is one that gives larger value of z.
 If the optimum solution of one subprogram is integral and other subprogram has no feasible optimum solution, the required solution is same as that of the subprogram having integer valued solution.
 If the optimum solution of one subprogram 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 noninteger valued subproblem.
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 subprogram 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 = 7x_{1} + 9x_{2}
subject to
− x_{1} + 3x_{2} ≤ 6
7x_{1} + x_{2} ≤ 35
x_{1} ≥ 0, x_{2} ≤ 7
x_{1}, x_{2} are integers.
Solution: First, we ignore the integer restriction and solve the problem by graphical method.
Let P_{0}:
Maximise z = 7x_{1} + 9x_{2}
subject to
− x_{1} + 3x_{2} ≤ 6
7x_{1} + x_{2} ≤ 35
x_{1} ≥ 0, x_{2} ≤ 7
x_{1}, x_{2} are integers
− x_{1} + 3x_{2} = 6 → (0, 2) (−6, 0)
7x_{1} + x_{2} = 35 → (5, 0) (0, 35)
The feasible region for P_{0} is OABC
z = 7x_{1} + 9x_{2}
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 P_{0} is
x_{1} = 9/2, x_{2} = 7/2 with maximum of z = 63
FIGURE 3.4
The solution obtained is not an integer solution.
Now, x_{1} = 4 + 1/2, x_{2} = 3 + 1/2 and the maximum of {1/2, 1/2} = 1/2. Arbitrarily, choose x_{1} for branching. Now, divide the problem P_{0} into subproblems:
P_{1}: Maximise  z = 7x_{1} + 9x_{2} 
subject to  −x_{1} + 3x_{2} ≤ 6 
7x_{1} + x_{2} ≤ 35  
x_{1} ≥ 0, x_{2} ≤ 7  
x_{1}, x_{2} are integers  
P_{2}: Maximise  z = 7x_{1} + 9x_{2} 
subject to  − x_{1} + 3x_{2} ≤ 6 
7x_{1} + x_{2} ≤ 35  
x_{1} ≥ 0, x_{2} ≤ 7  
x1, x_{2} are integers 
Solution ofP1: Subdivide the feasible region OABC of P_{0} by adding the region corresponding to the new constraint x_{1} ≤ 4. The feasible region is ODEC and the point E is (4, 10/3). The optimum solution of P_{1} is x_{1} = 4, x_{2} = 10/3 with maximum of z = 58. The solution obtained is not an integer. Hence, divide the problem P_{1} into two subproblems P_{11} and P_{12}.
Solution of P_{2}: Subdivide the feasible region OABC of P_{0} by adding the region corresponding to the constraint x_{1} ≥ 5. The feasible region for P_{2} is only the point A and so the optimum solution is
x_{1} = 5, x_{2} = 0 with maximum of z = 35
Since the solution is integer solution, we record the solution.
Solution of P_{11}: Subdivide the feasible region ODEC by adding the region corresponding to the additional constraint x_{2} ≤ 3. Hence, the feasible region for P_{11} is ODFGC.
The solution of P_{11} is .
Since this is an integer solution we record it.
Solution of P_{12}: Subdivide the feasible region ODEC by adding the region corresponding to the additional constraint x_{2} ≥ 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
x_{1} = 4, x_{2} = 3 with maximum ofz = 55
3.8 ZEROONE 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 zeroone programming problem. Various methods are available for solving the zeroone programming problems.
The general integer programming methods such as the branch and bound method can be used to solve zeroone 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 zeroone linear programming. Thus, a number of methods have been developed to solve zeroone linear programming problems more easily.
3.8.2 Examples of Zeroone Programming Problems
 Assignment problem
 Knapsack problem
 Fixed charge problem
 Travelling salesmen problem
3.8.3 Importance of Zeroone Integer Programming
The study of zeroone programming is important because of the following reasons:
 A certain class of nonlinear integer programming problems can be converted into equivalent zeroone programming problems.
 A number of industrial and managerial problems can be formulated as zeroone programming problems.
3.8.4 Solution Methodologies
The zeroone 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 zeroone 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 nonnegative 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:
 Change the sign of the objective function if it is of maximisation type.
 Replace all equality constraints by two weak inequalities, one of ≤ type and the other of type.
 Multiply all type constraints by −1 to convert them to ≤ type.
 Define a new variable y_{j} such that
where y_{j} is the binary variable in the objective function as well as the constraints. Slack variables s_{i} 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 x_{j}. However, since x_{j} is a binary variable two branches are associated, one for x_{j} = 0 and the other for x_{j} = 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 subproblem can be done as follows:
 The subproblem yields a feasible integer solution.
 The subproblem does not lead to a feasible solution.
 The subproblem 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 zeroone integer programming problem by using additive algorithm.
Maximise z = x_{1} + 2x_{2} − 3x_{3}
subject to
20x_{1} + 15x_{2} − x_{3} ≤ 10
12x_{1} − 3x_{2} − 4x_{3} ≤ 20
3x_{1} + 5x_{2} + x_{3} ≤ 6
x_{j} = 0 or 1 for all j
Solution:
 Multiply the objective function by −1 to convert the problem into minimisation type. The objective function becomes
Minimise z′ = −x_{1} −2x_{2} + 3x_{3} where z′ = −z.
To make the negative coefficients of the objective function as positive, make the following substitution.
where y_{j} is a binary variable.
x_{1} = 1 − y_{1}, x_{2} = 1 − y_{2} and x_{3} = y_{3}
Minimise z′ = −(1 − y_{1}) −z(1 − y_{2}) + 3y_{3}
= y_{1} + 2y_{2} + 3y_{3} − 3The constant 3 can be omitted since it will not make any difference, being independent of the values of y_{j}.
Minimise z″ = (z′ + 3) = y_{1} + 2y_{2} + 3y_{3}
The constraints can be written as
20 (1 − y_{1}) + 15(1 − y_{2}) − y_{3} ≤ 10 or −20y_{1} − 15y_{2} − y_{3} ≤ −25
12 (1 − y_{1}) − 3(1 − y_{2}) − 4y_{3} ≤ 10 or −12y_{1} + 3y_{2} − 4y_{3} ≤ 5
3 (1 − y_{1}) + 15(1 − y_{2}) + y_{3} ≤ 6 or −3y_{1} − 5y_{2} − y_{3} ≤ −2  Using the slack variable s_{1}, s_{2}, and s_{3} the constraints can be rewritten as
−20y_{1} − 15y_{2} − y_{3} + s_{1} = −25
or
Now the problem is in the proper format to use implicit enumeration. By setting y_{1} = y_{2} = y_{3} = 0, the initial solution is obtained as s_{1} = −25, s_{2} = 5, s_{3} = −2 with z″ = 0. The solution is represented by node 1 in Fig. 3.6. The solution obtained is infeasible as s_{1} and s_{3} are negative. The variables y_{1}, y_{2} and y_{3} 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 y_{1} = y_{2} = y_{3} = 1 in constraint (3.8.1) gives s_{1} = 11 > 0, and substituting y_{1} = y_{2} = 1 in constraint (3.8.3) gives s_{3} = 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 nonnegative constraint is zero, and for a negative constraint it is the amount that must be added to make it zero. If u_{j} measures the total infeasibility when variable y_{j} is raised to level 1, then u_{j} is defined as
Now
u_{1} =(−25 + 20) + 0 + 0 = −5,
u_{2} = (−25 + 15) + 0 + 0 = −10,
u_{3} = (−25 +1) + 0 + (−2 −1) = −27.
The variable y_{1} with the smallest infeasibility (= −5) is selected to take the value one while y_{2} and y_{3} remain free (note that the tie can be broken arbitrarily).
This solution y_{1} = 1, y_{2} = 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
s_{1}=−25 + 20 = −5
s_{2} = 5 + 12 = 17
s_{3} =−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 y_{1} = 1 and one of the variables y_{2} and y_{3} is to be assigned the value one.
u_{2} = 0 + 0 + 0 = 0,
u_{3} = −4 + 0 + 0 = −4.
Since u_{2} is the smallest infeasibility, y_{2} is selected to take the value one (in addition to y_{1}), while variable y_{3} remains free. This corresponds to node 4 in Fig. 3.7, which gives the solution y_{1} = y_{2} = 1, y_{3} = 0, z" = 3.
FIGURE 3.7
This solution when substituted in constraints (3.8.1), (3.8.2) and (3.8.3) gives
s_{1} = −25 + 20 + 15 = 10,
s_{2} = 5 + 12 − 3 = 14,
s_{3} =−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 z_{u} = 3
Since any solution with y_{1} = y_{2} = 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 y_{1} = 1, y_{2} = 0, y_{3} free to take value zero or one. This corresponds to node 5. When y_{3} = 0 we get an infeasible solution [constraints (3.8.1), (3.8.2) and (3.8.3) yield s_{1} = −5, s_{2} = 17, s_{3} = 1] and when y_{3} = 1, the optimality is destroyed (since y_{1} = 1, y_{2} = 0, y_{3} = 1 yields z" = 1 + 0 + 3 = 4, which is higher than the min z_{u} = 3). There is no need for checking the feasibility condition of this solution (y_{1} = 1, y_{2} = 0, y_{3} = 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 y_{1} = 0, y_{2} and y_{3} free to take value zero or one.
Now, we check the possibilities of getting a feasible solution emanating from node 3.
When y_{1} = 0, y_{2} = 1 and y_{3} is set at one, from constraints (3.8.1), (3.8.2) and (3.8.3) we get
s_{1} = −25 + 0 + 15 + −9,
s_{2} = 5 + 0 − 3 + 4 = 6,
s_{3}=−2 + 0 + 5 − 1 = 2.
Since this does not give a feasible solution, node 3 is fathomed. Thus the optimal solution is
y_{1} = y_{2} = 2, y_{3} = 0; = 3.
This solution can now be translated in terms of the original variables as follows:
x_{1} = 1 − y_{1} = 1 − 1 = 0,
x_{2} = 1 − y_{2} = 1 − 1 = 0,
x_{3} = y_{3} = 0,
Z_{min} = 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
 It provides an insight and perspective into the problem environment. This generally results in clear picture of the true problem.
 It makes a scientific and mathematical analysis of the problem situations.
 It gives an opportunity to the decisionmaker to formulate his strategies consistent with the constraints and the objectives.
 It deals with changing situations. Once a plan is arrived through the linear programming it can also be evaluated for changing conditions.
 By using linear programming the decisionmaker makes sure that he is considering the best solution.
3.9.2 Limitations of Linear Programming
 The major limitation of linear programming is that it treats all relationship as linear. But it is not true in many real life situations.
 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.
 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.
 The problems are complex if the number of variables and constraints are quite large.
 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 = x_{1} + 2x_{2} + x_{3}
subject to
2x_{1} + x_{2} − x_{3} ≤ 2
− 2x_{1} + x_{2} − 5x_{3} ≥ − 6
4x_{1} + x_{2} + x_{3} ≤ 6
x_{1}, x_{2}, x_{3} ≥ 0
[Answer: The dual is minimise w = 2y_{1} + 6y_{2} + 6y_{3}, subject to 2y_{1} + y_{2} + 4y_{3} ≥ 1, y_{1} − y_{2} + y_{3} ≥ 1, − y_{1} + 5y_{2} + y_{3} ≥ 1 and y_{1}, y_{2}, y_{3} ≥ 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 = 3x_{1} + x_{2} + 2x_{3} − x_{4}
2x_{1} − x_{2} + 3x_{3} + x_{4} = 1
x_{1} + x_{2} − x_{3} + x_{4} = 3
x_{1}, x_{2}, x_{3} ≥ 0 and x_{4} is unrestricted.
[Answer: The dual is minimise w = y_{1} + y_{2}, subject to 2y_{1} + y_{2} ≥ 3, − y_{1} + y_{2} ≥ 1, 3y_{1} − y_{2} ≥ 2, y_{1} + y_{2} = − 1; y_{1} and y_{2} are unrestricted.]
4. Write the dual of the LPP
Minimise z = 7x_{1} + 3x_{2} + 8x_{3}
subject to
8x_{1} + 2x_{2} + x_{3} ≥ 3
3x_{1} + 6x_{2} + 4x_{3} ≥ 4
4x_{1} + x_{2} + 5x_{3} ≥ 1
x_{1} + 5x_{2} + 2x_{3} ≥ 7
x_{1}, x_{2}, x_{3} ≥ 0
[Answer: The dual LPP is Maximise w = 3y_{1} + 4y_{2} + y_{3} + 7y_{4}, subject to 8y_{1} + 3y_{2} + 4y_{3} + y_{4} ≤ 7, 2y_{1} + 6y_{2} + y_{3} + 5y_{4} ≤ 3, y_{1} + 4y_{2} + 5y_{3} + 2y_{4} ≤ 8, y_{1}, y_{2}, y_{3}, y_{4} ≥ 0.]
5. Write the dual of the primal
Maximise z = 6x_{1} + 6x_{2} + x_{3} + 7x_{4} + 5x_{5}
subject to
3x_{1} + 7x_{2} + 8x_{3} + 5x_{4} + x_{5} = 2
2x_{1} + x_{2} + 3x_{4} + 9x_{5} = 6
x_{1}, x_{2}, x_{3}, x_{4} ≥ 0
and
x_{5} unrestricted.
[Answer: The dual is minimise w = 2y_{1} + 6y_{2} subject to 3y_{1} + 2y_{2} ≥ 6, 7y_{1} + y_{2} ≥ 7, 8y_{1} + 3y_{2} ≥ 1, 5y_{1} + 2y_{2} ≥ 7, y_{1} + 9y_{2} = 5; y_{1} and y_{2} are unrestricted.]
6. Apply simplex method to solve the following LPP
Maximise z = 30 x_{1} + 23x_{2} + 9x_{3},
subject to
6x_{1} + 5x_{2} + 3x_{3} ≤ 26, 4x_{1} + 2x_{2} + 5x_{3} ≤ 7, every x_{j} 0
Also, read the solution to the dual from the final Table of primal.
[Answer: Solution of the primal is x_{1} = 0, x_{2} = 7/2, x_{3} = 0, maximum of z = 161/2. The solution of the dual problem is y_{1} = 0, y_{2} = 23/2 and minimum of w = 161/2.]
7. Applying the concept of duality, solve the LPP
Maximise z = 3x_{1} + 4x_{2}
subject to
x_{1} − x_{2} ≤ 1
x_{1} + x_{2} ≤ 4
x1 − 3x_{2} ≤ 3
x_{1}, x_{2} ≥ 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 = 50x_{1} − 80x_{2} − 140x_{3}
subject to
x_{1} − x_{2} − 3x_{3} ≥ 4
x_{1} − 2x_{2} − 2x_{3} ≥ 3
and
x_{1}, x_{2}, x_{3} ≥ 0
[Answer: Dual has no feasible solution and hence primal has no feasible solution.]
9. Use duality to solve the LPP
Minimise z = 8x_{1} − 2x_{2} − 4x_{3}
subject to
x_{1} − 4x_{2} − 2x_{3} ≥ 2
x_{1} + x_{2} − 3x_{3} − 1
−3x_{1} − x_{2} + x_{3} ≥ 1
x_{1}, x_{2}, x_{3} ≥ 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 = 4x_{1} + 2x_{2} + 3x_{3}
subject to
2x_{1} + 4x_{3} ≥ 5
2x_{1} + 3x_{2} + x_{3} ≥ 4
x_{1}, x_{2}, x_{3} ≥ 0
[Answer: The solution of the primal is x_{1} = 0, x_{2} = 11/12, x_{3} = 5/4 with minimum of z = 67/12. The solution of the dual is y_{1} = 7/2, y_{2} = 2/3 and maximum of w = 67/12.]
Section 3.2
11. Solve the following linear programming problems using dual simplex method.

Minimise z = 2x_{1} + x_{2}
subject to
3x_{1} + x_{2} ≥ 3
4x_{1} + 3x_{2} ≥ 6
x_{1} + 2x_{2} ≥ 3
x_{1}, x_{2} ≥ 0[Answer: x_{1} = 3/5, x_{2} = 6/5 with minimum of z = 12/5.]

Minimise z = 3x_{1} + x_{2}
subject to
x_{1} + x_{2} ≥ 1
2x_{1} + 3x_{2} ≥ 2
x_{1}, x_{2} ≥ 0[Answer: x_{1} = 0, x_{2} = 1 with minimum of z = 1.]

Minimise z = x_{1} + 2x_{2}
subject to
2x_{1} + x_{2} ≥ 4
x_{1} + 2x_{2} ≥ 7
x_{1}, x_{2} ≥ 0[Answer: x_{1} = 0, x_{2} = 2 with minimum of z = 4.]

Minimise z = 3x_{1} + 2x_{2} + x_{3} + 4x_{4}
subject to
2x_{1} + 4x_{2} + 5x_{3} + x_{4} ≥ 10
3x_{1} − x_{2} + 7x_{3} − 2x_{4} ≥ 2 ×
5x_{1} + 2x_{2} + x_{3} + 6x_{4} ≥ 15
x_{1}, x_{2}, x_{3}, x_{4} ≥ 0[Answer: x_{1} = 65/23, x_{2} = 0, x_{3} = 20/23, x_{4} = 0 with minimum of z = 215/213.]

Minimise z = 2x_{1} + 9x_{2} + 24x_{3} + 8x_{4} + 5x_{5}
subject to
x_{1} + x_{2} + 2x_{3} − x_{5} − x_{6} = 1,
−2x_{1} + x_{3} + x_{4} + x_{5} − x_{7} = 2,
x_{j} 0, j = 1, …, 7[Answer: x_{1} = x_{2} = x_{5} = x_{6} = x_{7} = 0, x_{3} = 1/2, x_{4} = 3/2 with minimum of z = 24.]

Minimise z = x_{1} + 2x_{2} + 3x_{3}
subject to
x_{1} − x_{2} + x_{3} ≥ 4
x_{1} + x_{2} + 2x_{3} ≤ 8
x_{2} − x_{3} ≥ 2
x_{1}, x_{2}, x_{3} ≥ 0[Answer: x_{1} = 6, x_{2} = 2, x_{3} = 0 with minimum ofz = 10.]
Section 3.3
12. Use revised simplex method to solve the following linear programming problems:

Maximise z = 3x_{1} + 2x_{2} + 5x_{3}
subject to
x_{1} + 2x_{2} + x_{3} ≥ 430
3x_{1} + 2x_{3} ≥ 460
x_{1} + 4x_{2} ≤ 420
x_{1}, x_{2}, x_{3} ≥ 0[Answer: x_{1} = 0, x_{2} = 100, x_{3} = 230 with maximum ofz = 1350.]

Minimise z = x_{1} + x_{2}
subject to
x_{1} + 2x_{2} ≥ 7
4x_{1} + x_{2} ≥ 6
x_{1}, x_{2} ≥ 0[Answer: x_{1} = 5/7, x_{2} = 22/7 with minimum of z = 27/7.]

Maximise z = 2x_{1} + 3x_{2}
subject to
− x_{1} + x_{2} ≥ 0
x_{1} ≤ 4and
x_{1}, x_{2} ≥ 0
[Answer: Unbounded solution.]

Maximise z = x_{1} + x_{2}
subject to
2x_{1} + 5x_{2} ≥ 6,
x_{1} + x_{2} ≥ 2,
x_{1}, x_{2} ≥ 0[Answer: Unbounded solution.]

Maximise z = x_{1} + x_{2}
subject to
3x_{1} + 2x_{2} ≤ 6
x_{1} + 4x_{2} ≤ 4
x_{1}, x_{2} ≥ 0[Answer: x_{1} = 8/5, x_{2} = 3/5 with maximise of z = 11/5]

Maximise z = x_{1} + 2x_{2}
subject to
3x_{1} + 2x_{2} ≥ 6
x_{1} + 6x_{2} ≤ 3
x_{1}, x_{2} ≥ 0[Answer: Unbounded solution.]
Section 3.4
13. Consider the LPP
Maximise z = 2x_{1} + x_{2} + 4x_{3} − x_{4}
subject to
x_{1} + x_{2} + x_{3} − 3x_{4} ≤ 8
l−x_{1} + x_{3} + 2x_{4} ≤ 0
2x_{1} + 7x_{2} − 5x_{3} − 10x_{4} ≤ 21
and
x_{1}, x_{2}, x_{3}, x_{4} ≥ 0
 Solve the LPP.
 Discuss the effect of change of b_{2} to 11.
 Discuss the effect of change of b to [3, − 2, 4].
[Answer: The optimal solution is
 x_{1} = 8, x_{2} = x_{3} = x_{4} = 0, maximum of z = 16
 x_{1} = 49/2, x_{2} = 0 = x_{3}, x_{4} = 11/2, maximum of z = 87/2
 No feasible solution.]
14. Consider the LPP
Maximise z = 3x_{1} + 5x_{2} + 4x_{3}
2x_{1} + 3x_{2} ≤ 8
2x_{2} + 5x_{3} ≤ 10
3x_{1} + 2x_{2} + 4x_{3} ≤ 15
x_{1}, x_{2}, x_{3} ≥ 0
 Solve the LPP.
 Find the range over which b_{2} can be changed maintaining feasibility of the solution.
[Answer: (a) x_{1} = 89/41, x_{2} = 50/41, x_{3} = 62/41 with maximum of z = 765/41.
(b) 25/4 ≤ Δ b_{2} ≤ 89/12.]
15. Consider the LPP
Maximise z = − x_{1} + 2x_{2} − x_{3}
subject to
3x_{1} + x_{2} − x_{3} ≤ 10
−x_{1} + 4x_{2} + x_{3} ≥ 6
x_{2} + x_{3} ≤ 4
x_{1}, x_{2}, x_{3} ≥ 0
 Determine an optimum solution to the problem.
 Determine the ranges for discrete changes in the components b_{2} and b_{3} of the required vector so as to maintain the optimality of the current optimum solution.
[Answer: (a) The optimal solution is x_{1} = 0, x_{2} = 4, x_{3} = 0 with maximum of z = 8.
(b) Δb_{2} ≤ 10, − 5/2 ≤ Δ b_{3} ≤ 6].
16. Given the LPP
Minimise z = 3x_{1} + 6x_{2} + x_{3}
subject to the constraints
x_{1} + x_{2} + x_{3} ≥ 6
x_{1} + 5x_{2} − x_{3} ≥ 4
x_{1} + 5x_{2} + x_{3} ≥ 24
x_{1}, x_{2}, x_{3} ≥ 0
 Solve the LPP
 Discuss the effect of changing the required vector from [6, 4, 24] to [6, 2, 12] on the optimum solution.
[Answer: (a) x_{1} = 14, x_{2} = 0, x_{3} = 0, minimum of z = 52
(b) x_{1} = 7, x_{2} = 0, x_{3} = 5; minimum of z = 26.]
17. Solve the following linear programming problem
Maximise 3x_{1} + 5x_{2}
subject to
x_{1} + x_{2} ≤ 1
2x_{1} + x_{2} ≤ 1
x_{1}, x_{2} ≥ 0
Determine the range of variation of the cost coefficients c_{j} (j = 1, 2) corresponding to the optimal solution.
[Answer: x_{1} = 0, x_{2} = 1, maximum z = 5, − ∞ < c_{1} < 5 and 3 ≤ c_{2} ≤ ∞]
Minimise z = 5x_{1} + 3x_{2}
subject to
3x_{1} + 5x_{2} ≤ 15
5x_{1} + 6x_{2} ≤ 10
and,
x_{1}, x_{2} ≥ 0
 Solve the LPP.
 Find how far the component c_{1} of C can be increased without affecting the optimality of the solution.
[Answer: (a) x_{1} = 20/19, x_{2} = 45/19 with minimum of z = 235/19, (b) 5 ≤ c_{1} ≤ 15/2]
19. Consider the LPP
Maximise z = 3x_{1} + 5x_{2}
subject to
x_{1} ≤ 4
3x_{1} + 2x_{2} ≤ 18
and,
x_{1}, x_{2} ≥ 0
 Solve this LPP.
 If a new variable x_{5} is added to this problem with a column and c_{5} = 7, find the change in the optimal solution.
[Answer: (a) x_{1} = 0, x_{2} = 9 with maximum of Z = 45.
(b) x_{1} = 0, x_{2} = 5, x_{5} = 5 with maximum of Z = 53.]
20. Consider the LPP.
Maximise z = 5x_{1} + 3x_{2} + 7x_{3}
subject to
x_{1} + x_{2} + 2x_{3} ≤ 22
3x_{1} + 2x_{2} + x_{3} ≤ 26
x_{1} + x_{2} + x_{3} ≤ 18
and,
x_{1}, x_{2}, x_{3} ≥ 0.
 Solve the LPP.
 What will be the solution if the first constraint changes to x_{1} + x_{2} + 2x_{3} ≤ 26.
[Answer: (a) x_{1} = 6, x_{2} = 0, x_{3} = 52/2 and maximum of z = 26.
(b) x_{1} = 26/5, x_{2} = 0, x_{3} = 52/2 and maximum of z = 494/5.]
21.
 Solve the following LPP
Maximise z = x_{1} + 5x_{2} + 3x_{3}
subject to
x_{1} + 2x_{2} + x_{3} = 3
2x_{1} − x_{2} = 4and,
x_{1}, x_{2}, x_{3} ≥ 0
 If the objective function is changed to maximise z = 2x_{1} + 5x_{2} + 2x_{3}, find the new optimal solution.
[Answer: (a) x_{1} = 2, x_{2} = 0, x_{3} = 1
(b) x_{1} = 11/5, x_{2} = 2/5, x_{3} = 0 with maximum of z = 32/5.]
Maximise z = 10x_{1} + 3x_{2} + 6x_{3} + 5x_{4}
subject to the constraints
x_{1} + 2x_{2} + x_{4} ≤ 6
3x_{1} + 2x_{3} ≤ 5
x_{2} + 4x_{3} + 5x_{4} ≤ 3
x_{1}, x_{2}, x_{3} ≥ 0
Compute the limits for a_{11} and a_{23} so that the new solution remains optimum feasible.
[Answer: − ∞ ≤ a_{11} ≤ 51/10, 39/40 ≤ a_{23} < ∞]
Section 3.5
23. Consider the parametric linear programming problem
Maximise z = (θ − 1) x_{1} + x_{2}
subject to
x_{1} + 2x_{2} ≤ 10
2x_{1} + x_{2} ≤ 11
x_{1} − 2x_{2} ≤ 3
x_{1}, x_{2} ≥ 0
Perform a complete parametric analysis. Identify all critical values of the parameter θ and the optimal basic solutions.
[Answer: x_{1} = 0, x_{2} = 5 for 0 ≤ θ ≤ 3/2
x_{1} = 4, x_{2} = 3 for 3/2 ≤ θ ≤ 3
x_{1} = 5, x_{2} = 1 for 3 ≤ θ ]
24. For the following linear programming problem:
Minimise z = λx1 − λx2 − x_{3} + x_{4}
subject to
3x_{1} − 3x_{2} − x_{3} + x_{4} ≥ 5
2x_{1} − 2x_{2} + x_{3} − x_{4} ≤ 3
x_{1}, x_{2}, x_{3}, x_{4} ≥ 0.
[Answer: For − 2 ≤ λ < 3, x_{1} = 8/5, x_{2} = 0, x_{3} = 0, x_{4} = 1/5 with minimum of z = 1/5 + 8/5λ.
For λ > 3, no solution exists.]
25. Solve the problem
Maximise z = 3x_{1} + 2x_{2} + 5x_{3}
subject to
x_{1} + 2x_{2} + x_{3} ≤ 430 + 500λ
3x_{1} + 2x_{3} ≤ 460 + 100λ
x_{1} + 4x_{2} ≤ 420 − 200λ
x_{1}, x_{2}, x_{3} ≥ 0.
[Answer: For 0 ≤ λ ≤ 1/55, (x_{1}, x_{2}, x_{3}) = (0, 100 + 225λ, 230 + 5λ) and minimum of z = 1, 350 +
700λ
For 1/55 ≤ λ ≤ 2.1, (x_{1}, x_{2}, x_{3}) = (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 = {o_{3} + o_{4}, o_{1}, u_{2}, u_{3} + 8/5 u_{4}}
subject to
g_{1}: x_{1} + x_{2} + u_{1} − o_{1} = 20
g_{2}: x_{1} + x_{2} + u_{2} − o_{2} = 50
g_{3}: x_{1} + u_{3} − o_{3} = 15
g_{4}: x_{2} + u_{4} − o_{4} = 8,
x_{i}, u_{i}, o_{i} ≥ 0 where the goals are written in order of priority.
[Answer: x_{1} = 12, x_{2} = 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 fulltime and four parttime salesmen. The normal working hours per month for a fulltime salesman and a parttime 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 fulltime salesmen and two records per hour for parttime salesmen. The average hourly wage rates are 3 for fulltime salesmen and 2 for parttime 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 fulltime salesmen should be avoided because of the declining sales effectiveness caused by fatigue.
The manager, has set the following goals:
 The first goal is to achieve a sales goal of 5500 records for the next month.
 The second goal is to limit the overtime of fulltime salesmen to 100 hours.
 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 employeremployee relationship. However, he is twice as concerned with the full utilization of fulltime salesmen as with the full utilization of parttime salesmen.
 The last goal is to minimise the sum of overtime for both fulltime and parttime salesmen. The manager desires to assign differential weights to the minimisation of overtime according to the net marginal profit ratio between the fulltime and parttime 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.

Maximise z = x_{1} + x_{2}
subject to
3x_{1} + 2x_{2} ≤ 5
x_{2} ≤ 2and
x_{1} ≥ 0, x_{2} ≥ 0 and are integers.
[Answer: x_{1} = 0, x_{2} = 2 with maximum of z = 2. (or)
x_{1} = 1, x_{2} = 1 with maximum of z = 2.] 
Maximise z = 2x_{1} + 2x_{2}
subject to
5x_{1} + 3x_{2} ≤ 8
2x_{1} + 4x_{2} ≤ 8and
x_{1}, x_{2} ≥ 0 and are all integers.
[Answer: x_{1} = 1, x_{2} = 1 with maximum of z = 4 (or)
x_{1} = 0, x_{2} = 2 with maximum of z = 4.] 
Maximise z = 3x_{1} + 4x_{2}
subject to
3x_{1} + 2x_{2} ≤ 8
x_{1} + 4x_{2} ≤ 10and
x_{1}, x_{2} ≥ 0 and are integers.
[Answer: x_{1} = 0, x_{2} = 3 with maximum of z = 12.]

Maximise z = x_{1} − 2x_{2}
subject to
4x_{1} + 2x_{2} ≤ 15
x_{1}, x_{2} ≥ 0 and are integers.[Answer: x_{1} = 3, x_{2} = 0 with maximum of z = 3.]

Maximise z = 7x_{1} + 9x_{2}
subject to
− x_{1} + 3x_{2} ≤ 6
7x_{1} + x_{2} ≤ 35
x_{1}, x_{2} ≥ 0 and are integers.[Answer: x_{1} = 4, x_{2} = 3 with maximum of z = 55.]
 (vi)
Minimise z = 9x_{1} + 10x_{2}
subject to
x_{1} ≤ 9
x_{2} ≤ 8
4x_{1} + 3x_{2} ≥ 40
x_{1}, x_{2} ≥ 0 and are integers.[Answer: x_{1} = 9, x_{2} = 2 with minimum of z = 101.]

Maximise z = 2x_{1} + 20x_{2} − 10x_{3}
subject to
5x_{1} + 20x_{2} + 4x_{3} ≤ 15
6x_{1} + 20x_{2} + 4x_{3} = 20
x_{1}, x_{2} x_{3} ≥ 0 and are integers.[Answer: x_{1} = 2, x_{2} = 0, x_{3} = 2 with maximum of z = − 16.]

Maximise z = 3x_{2}
subject to
3x_{1} + 2x_{2} ≤ 7
x_{1} − x_{2} − 2
x_{1}, x_{2} ≥ 0 and are integers.[Answer: Simplex method gives the integer solution: x_{1} = 0, x_{2} = 2 with maximum of z = 6.]

Maximise z = x_{1} + 5x_{2}
subject to
x_{1} + 10x_{2} ≤ 20
x_{1} ≤ 2
x_{1}, x_{2} ≥ 0 and are integers.[Answer: x_{1} = 2, x_{2} = 1, with maximum of z = 7.]

Maximise z = 2x_{1} + 2x_{2}
subject to
5x_{1} + 3x_{2} ≤ 8
x_{1} + 2x_{2} ≤ 4
x_{1}, x_{2} ≥ 0 and are integers.[Answer: x_{1} = 1, x_{2} = 1 with maximum of z = 4.]
29. Solve the following mixed integer programing problems:

Maximise z = x_{1} + x_{2}
subject to
3x_{1} + 2x_{2} ≤ 5
x_{2} ≤ 2and
x_{1}, x_{2} ≥ 0 and x_{1} is an integer.
[Answer: x_{1} = 0, x_{2} = 2 with maximum of z = 2.]

Minimise z = 10x_{1} + 9x_{2}
subject to
x_{1} ≤ 8
x_{2} ≤ 10
5x_{1} + 3x_{2} ≥ 45
x_{1}, x_{2} ≥ 0, x_{1} is an integer.[Answer: x_{1} = 8, x_{2} = 5/3 with minimum of z = − 95.]

Maximise z = 4x_{1} + 6x_{2} + 2x_{3}
subject to
4x_{1} − 4x_{2} ≤ 5
−x_{1} + 6x_{2} ≤ 5
−x_{1} + x_{2} + x_{3} ≤ 5
x_{1}, x_{2}, x_{3} ≥ 0 and x_{1}, x_{3} are integers.[Answer: x_{1} = 2, x_{2} = 1, x_{3} = 6 with maximum of z = 26.]

Maximise z = 3x_{1} + x_{2} + 3x_{3}
subject to −x1 + 2x_{2} + x_{3} ≤ 4
4x_{1} − 3x_{2} ≤ 2
x_{1} − 3x_{2} + 2x_{3} ≤ 3
x_{2} ≥ 0 and x_{1}, x_{3} are nonnegative integers.[Answer: x_{1} = 5, x_{3} = 3, x_{2} = 2.75 with maximum of z = 26.75.]
31. Use branch and bound technique to solve the following integer programming problem.
 Maximise z = x_{1} + x_{2}
subject to
4x_{1} − x_{2} ≤ 10
2x_{1} + 5x_{2} ≤ 10
2x_{1} − 3x_{2} ≤ 6
x_{1}, x_{2} ≥ 0 and are integers.[Answer: x_{1} = 2, x_{2} = 1, with maximum of z = 3.]

Maximise z = 3x_{1} + 4x_{2}
subject to
3x_{1} − x_{2} + x_{3} = 12
3x_{1} + 11x_{2} + x_{4} = 66
x_{j} ≥ 0 and are integers for j = 1, 2, 3, 4.[Answer: x_{1} = 5, x_{2} = 4 with maximum of z = 31.]

Maximise z = x_{1} + 4x_{2}
subject to
2x_{1} + 4x_{2} ≤ 7
5x_{1} + 3x_{2} ≤ 15
x_{1}, x_{2} ≥ 0 and are integers.[Answer: x_{1} = 1, x_{2} = 1 with maximum of z = 5.]

Maximise z = 3x_{1} + 4x_{2}
subject to
7x_{1} + 16x_{2} ≤ 52
3x_{1} − 2x_{2} ≤ 18
x_{1}, x_{2} ≥ 0 and are integers.[Answer: x_{1} = 5, x_{2} = 1, with maximum of z = 19.]