OR Unit – II Important Questions

Q1. Explain the rules in constructing dual from primal. Hence, convert the
following primal to dual:
Max Z = 8x1 + 2x2 + 3x3
Subject to the constraints,
x1 + 2x2 + 5x3 ≥ 18,
4x1 + 2x2 + x3 ≥ 7
and x1, x2, x3 ≥ 0

Ans:
 The rules for constructing the dual from the primal and vice-versa using the
symmetrical form of LP problem are:
 A dual variable is defined corresponds to each constraint in the primal LP
problem and vice versa. Thus, for a primal LP problem with m constraints and
n variables, there exists a dual LP problem with m variables and n constraints
and vice-versa.
 The right-hand side constants b1, b2, . . ., bm of the primal LP problem
becomes the coefficients of the dual variables y1, y2, . . ., ym in the dual
objective function Zy. Also, the coefficients c1, c2, . . ., cn of the primal variables
x1, x2, . . ., xn in the objective function become the right-hand side constants in
the dual LP problem.
 For a maximization primal LP problem with all ≤ (less than or equal to) type
constraints, there exists a minimization dual LP problem with all ≥ (greater
than or equal to) type constraints and vice versa. Thus, the inequality sign is
reversed in all the constraints except the non-negativity conditions.
 The matrix of the coefficients of variables in the constraints of dual is the
transpose of the matrix of coefficients of variables in the constraints of primal
and vice versa.
 If the objective function of a primal LP problem is to be maximized, the
objective function of the dual is to be minimized and vice versa.
 If the ith primal constraint is = (equality) type, then the ith dual variables is
unrestricted in sign and vice versa.

Q2. What is integer programming problem and what are the different types of
integer programming problems?

Ans:
 In linear programming, each decision variable, slack and/or surplus variable is
allowed to take any discrete or fractional value. However, there are certain
real-life problems in which the fractional value of the decision variables has
no significance.
 For example, it does not make sense to say that 1.5 men will be working on a
project or 1.6 machines will be used in a workshop. The integer solution to a
 problem can, however, be obtained by rounding off the optimum value of the
variables to the nearest integer value.
 This approach can be easy in terms of economy of effort, time, and the cost
that might be required to derive an integer solution. This solution, however,
may not satisfy all the given constraints.
 Secondly, the value of the objective function so obtained may not be the
optimal value.
 All such difficulties can be avoided if the given problem, where an integer
solution is required, is solved by integer programming techniques.
 Integer LP problems are those in which some or all of the variables are
restricted to integer (or discrete) values.
 An integer LP problem has important applications like Capital budgeting,
construction scheduling, plant location and size, routing and shipping
schedule, batch size, capacity expansion, fixed charge, etc.
 Linear integer programming problems can be classified into three categories:
 Pure (all) integer programming problems in which all decision variables are
restricted to integer values.
 Mixed integer programming problems in which some, but not all, of the
decision variables are restricted to integer values.
 Zero-one integer programming problems in which all decision variables are
restricted to integer values of either 0 or 1.
Q3. What is the application of zero one integer programming problem?

Ans:
 Supply Chain optimization: One of the most common applications of zero-one
integer programming is in supply chain optimization.
 Companies often face the challenge of determining the most efficient way to
allocate resources, such as warehouses, vehicles, and production facilities, to
meet customer demands while minimizing costs.
 By formulating this problem as a zero-one integer programming model,
decision-makers can determine the optimal allocation strategy.
 For instance, a major retail company used zero-one integer programming to
optimize the locations of their distribution centres, considering factors such
as transportation costs, customer demand, and facility capacities. The
resulting solution allowed them to reduce transportation costs significantly
while maintaining high service levels.
 Project Portfolio Selection: Another area where zero-one integer
programming shines is project portfolio selection. Many organizations have
limited resources and must carefully choose which projects to undertake to
maximize their overall value.
 By formulating the problem as a zero-one integer programming model,
decision-makers can determine the optimal combination of projects to select
based on various criteria, such as profitability, resource requirements, and
strategic alignment.
 For example, a consulting firm used zero-one integer programming to select
the most profitable combination of projects from a pool of potential
opportunities. By considering factors like project duration, resource
availability, and client preferences, they were able to maximize their overall
revenue and effectively allocate their consulting teams.
 Crew Scheduling in Airlines: Zero-one integer programming has also proven
invaluable in crew scheduling for airlines. Airlines face the complex task of
assigning flight crews to various flights while considering legal regulations,
crew qualifications, and operational constraints.
 By formulating crew scheduling as a zero-one integer programming problem,
airlines can optimize crew assignments to minimize costs, ensure compliance
 with regulations, and enhance overall operational efficiency. For instance, a
major airline used zero-one integer programming to optimize their crew
scheduling process, taking into account factors like crew preferences, rest
requirements, and flight demand.
 The resulting solution allowed them to reduce crew costs, improve crew
satisfaction, and maintain high service levels.
 Capital Budgeting: It is used for selecting investment projects to maximize the
return on investment. A company may have several investment opportunities
and must decide which ones to undertake. Each project can either be
accepted (1) or rejected (0), depending on the budget and other constraints.
 Routing Problems: It is used for optimizing routes in logistics or
transportation. In a vehicle routing problem, decide which routes to assign to
delivery vehicles, ensuring they visit all necessary stops while minimizing the
total travel cost.

Q4. Explain different types of integer programming problem.

Ans:
 Integer programming can be categorized into different types based on the
nature and constraints of its variables, each having its unique application
scenarios and challenges. The three main types of integer programming are:
 Pure Integer Programming: In Pure Integer Programming, all decision
variables are constrained to integer values. This type is often applied to
scenarios where each decision element is indivisible, such as the quantity of
items or allocation of personnel. Even though the structure of a pure integer
programming problem might resemble linear programming, the integer
constraints introduce a higher level of complexity. A classic example is
production planning in manufacturing, where the number of units to produce
for each product type must be determined.
 Mixed Integer Programming: Mixed Integer Programming is a more general
form, where some variables are integers while others can be continuous. This
type is prevalent in practical applications because it accommodates the
simultaneous handling of integer and non-integer decision variables. For
example, in supply chain optimization, one might need to decide the integer
 quantity of items to purchase (integer variables) while also considering
transportation costs or times (continuous variables). Its flexibility makes
mixed integer programming widely applicable in various complex real-world
problems.
 0–1 Integer Programming: 0–1 Integer Programming is a special case of pure
integer programming, where all integer variables are restricted to take only
the values 0 or 1. This type is often used in modelling selection problems,
where each variable represents a yes-or-no decision. For instance, in a project
selection problem, each project is either chosen (1) or not chosen (0). 0–1
integer programming is particularly important in combinatorial optimization
problems, such as portfolio selection in finance or path selection in
operations research.
 Understanding these different types of integer programming is crucial for
selecting the appropriate solving method and comprehending the potential
application scenarios.
 Despite the challenges in solving integer programming problems due to
integer constraints, they offer higher accuracy and practicality in modelling
and solving real-world issues.

Q5. Write the properties of duality.

Ans:
 The dual of the dual LP problem is again the primal problem.
 If either the primal or the dual problem has an unbounded objective function
value, the other problem has no feasible solution.
 If either the primal or dual problem has a finite optimal solution, the other
one also possesses the same, and the optimal value of the objective functions
of the two problems are equal, i.e. Max Zx = Min Zy. This analytical result is
known as the fundamental primal-dual relationship
 Complementary slackness property of primal-dual relationship states that for
a positive basic variable in the primal, the corresponding dual variable will be
equal to zero. Alternatively, for a non-basic variable in the primal (which is
zero), the corresponding dual variable will be basic and positive.
Q6. Solve the following by branch and bound method.
Max Z = 2x1 + 3x2
Subject to the constraints,
x1 + 3x2 ≤ 9,
3x1 + x2 ≤ 7,
x1 – x2 ≤ 1,
and x1, x2 ≥ 0

Ans:

Q7. Discuss about sensitive analysis.

Ans:
 While study of duality helps to identify only an increase (or decrease) in the
value of objective function due to per unit variation in the number of
resources available, the sensitivity analysis reveals the magnitude of change
in the optimal solution of an LP model due to discrete variations (changes) in
its parameters.
 The possible change in the parameter values, can range from zero to a
substantial change. Thus, aim of sensitivity analysis is to determine the range
(or limit) within which the LP model parameters can change without affecting
the current optimal solution.
 For this, instead of solving an LP problem again with new values of
parameters, the current optimal solution is considered as an initial solution to
determine the ranges, both lower and upper, within which a parameter may
assume a value.
 The sensitivity analysis is also referred to as post-optimality analysis because
it does not begin until the optimal solution to the given LP model has been
obtained.
 Different parametric changes in an LP problem are as follows:
 Profit (or cost) per unit (cj) associated with both basic and non-basic decision
variables (i.e., coefficients in the objective function).
 Availability of resources (i.e., right-hand side constants, bi in constraints).
 Consumption of resources per unit of decision variables xj (i.e., coefficients of
decision variables in the constraints, aij).
 Addition of a new variable to the existing list of variables in LP problem.
 Addition of a new constraint to the existing list of constraints in the LP
problem.

Q8. Write the economic interpretation of dual constraints and dual variables.

Ans:
 Economic Interpretation of Dual Variables:
 In the maximization primal LP model, we may define each parameter as
follows: Z = return, cj = profit (or return) per unit of variable (activity) xj, xj =
number units of variable j, aij = units of resource i consumed (required), bi =
maximum units of resource i available per unit of variable j
 The new variables introduced in the dual problem are Zy and yi (dual
variables). When both the primal and the dual solutions are optimal, the
value of objective function satisfies the strict equality, i.e. Zx = Zy. The
interpretation associated with the dual variables yi (i = 1, 2, . . ., m) is
discussed below. Rewrite the primal LP problem as follows:
 From these expressions of parameters of both primal and dual problems, it is
clear that for the unit of measurement to be consistent, the dual variable (yi)
must be expressed in terms of return (or worth) per unit of resource i. This is
called dual price (simplex multiplier or shadow price) of resource i.
 In other words, optimal value of a dual variable associated with a particular
primal constraint indicates the marginal change (increase, if positive or
decrease, if negative) in the optimal value of the primal objective function.
Similarly, for feasible solutions of both primal and dual LP problems, objective
function value satisfy the inequality Zx ≤ Zy. This inequality is interpreted as:
Profit ≤ Worth of resources.
 Thus, so long as the total profit (return) from all activities is less than the
worth of the resources, the feasible solution of both primal and dual is not
optimal. The optimality (maximum profit or return) is reached only when the
resources have been completely utilized. This is only possible if the worth of
the resources (i.e. input) is equal to profit (i.e. output).
 Economic Interpretation of Dual Constraints:
 As stated earlier, the dual constraints are expressed as:

 Since coefficients aji represents the amount of

resource bi consumed by per unit of activity xj, and the dual variable yi
represents shadow price per unit of resource bi, the quantity Σ ajiyi (= zj)
should be total shadow price of all resources required to produce one unit of
activity xj.
 For maximization LP problem, if cj – zj > 0 value corresponds to any non-basic
variable, then the value of objective function can be increased. This implies
that the value of variable, xj can be increased from zero to a positive level
provided its unit profit (cj) is more than its shadow price, i.e.
 Profit per unit of activity xj ≥ Shadow price of resources used per unit of
activity, xj.

Q9. What are the rules for constructing the dual from primal.

Ans: Same as Q1

Q10. What are the advantages of duality?

Ans:
 It is advantageous to solve the dual of a primal that has a smaller number of
constraints because the number of constraints usually equals the number of
iterations required to solve the problem.
 This avoids the necessity for adding surplus or artificial variables and solves
the problem quickly (the technique is known as the primal-dual method ). In
economics, duality is useful in the formulation of the input and output
systems. It is also useful in physics, engineering, mathematics, etc.
 The dual variables provide an important economic interpretation of the final
solution of an LP problem.
 It is quite useful when investigating changes in the parameters of an LP
problem (the technique is known as the sensitivity analysis).
 Duality is used to solve an LP problem by the simplex method in which the
initial solution is infeasible (the technique is known as the dual simplex
method).

Q11. Write the dual of the following LP problem.

Minimize Zx = 3x1 - 2x2 + 4x3
Subject to the constraints,
3x1 + 5x2 + 4x3 ≥ 7,
6x1 + x2 + 3x3 ≥ 4,
7x1 - 2x2 - x3 ≤ 10,
x1 - 2x2 + 5x3 ≥ 3,
4x1 + 7x2 - 2x3 ≥ 2,
and x1, x2 ,x3 ≥ 0

Ans:
Q12. What is Principle of Complementary Slackness?

Ans:
 The principle of complementary slackness establishes the relationship
between the optimal value of the main variables in one problem with their
counterpart slack or surplus variables in other problem. Thus, this principle
can also be helpful in obtaining the primal LP problem solution when only the
dual solution is known. To illustrate this concept, let us consider the following
example.
 If at the optimal solution of a primal problem, a primal constraint has a
positive value of a slack variable, the corresponding resource is not
completely used and must have zero opportunity cost (shadow price). This
means that having more of this resource will not improve the value of the
objective function. But if the value of slack variable is zero in that constraint,
the entire resource is being used and must have a positive opportunity cost,
i.e. additional resource will improve the value of objective function by
allowing more production.
 Since resources are represented by slack variables in the primal and by main
variables in the dual, therefore, the principle of complementary slackness
states that for every resource, the following condition must hold: Primal slack
variable × Dual main variable = 0
 In cases where the resources are not completely used, the opportunity cost
of such resources exceeds the unit profit from that variable. But, if few units
of the variable are obtained, then the opportunity cost of resources used
must equal the profit from each unit of the variable, so that the surplus cost
is zero.
 A primal variable in primal LP problem represents the quantity to be
obtained, and the surplus variables in dual represent surplus costs. In this
case the principle of complementary slackness states that for every unit of
the variable, the following condition must hold. Primal main variable × Dual
surplus variable = 0

Q13. Write the advantages of duality.

Ans: Same as Q10

Q14. What do you understand by the term ‘sensitivity analysis?

Ans: Same as Q7

Q15. Discuss the effect of:

1. Variation of cj
2. Variation of bi and
3. Addition of new constraint

Ans:
 Variation of cj
 In an optimization problem, specifically linear programming, typically cj
represents the coefficient of the jth variable in the objective function.
 Increasing : If cj increases, the objective function gives more weight to the jth
variable. This may shift the optimal solution towards higher values of xj if it is
still feasible within the constraints.
 Decreasing : If cj decreases, the importance of xj in the objective function
decreases, and it may become less likely for xj to be at the optimal value.
 Zero : If cj becomes zero, the jth variable will no longer influence the objective
function directly. The value of xj will only be determined by the constraints.
 Variation of bi
 In linear programming, bi often represents the right-hand side value of the ith
constraint.
 Increasing bi: If bi increases, the feasible region of the constraint becomes
larger (i.e., the constraint is relaxed). This may allow a better or higher
objective function value, as it gives the solution more flexibility.
 Decreasing bi: If bi decreases, the constraint becomes tighter, reducing the
feasible region. This may lead to a worse or lower optimal objective function
 value, and in extreme cases, it could make the problem infeasible if no
solution satisfies the new tighter constraints.
 Addition of a New Constraint
 Adding a new constraint to an optimization problem typically reduces the size
of the feasible region.
 Impact on Feasibility: A new constraint might render the current optimal
solution infeasible. If the feasible region becomes empty (i.e., no solutions
satisfy all constraints), the problem becomes infeasible.
 Impact on Optimal Solution: If the new constraint doesn't eliminate the
current optimal solution, it might still force the solution to shift, often
resulting in a worse (lower or higher, depending on whether you are
maximizing or minimizing) objective value. In rare cases, the new constraint
might not change the optimal solution at all if it is already satisfied by the
current optimal solution.
 Thus, the following points can be concluded:
 Variation of cj affects the relative weight of the corresponding decision
variable in the objective function.
 Variation of bi changes the feasible region by relaxing or tightening the
constraints.
 Addition of a new constraint reduces the feasible region and can impact both
feasibility and the optimal solution.