UNIT - I

1. What is linear programming?

Linear programming is a technique used for determining optimum utilization of limited
resources to meet out the given objectives. The objective is to maximize the profit or minimize the
resources (men, machine, materials and money)

2. Write the general mathematical formulation of LPP.

1. Objective function
Max or Min Z = C1x1 + C2x2+ …..+ Cnxn
2. Subject to the constraints
a11x1+a12x2+…………+ a1nxn (≤=≥)b1 a21x1+a22x2+…………+ a2nxn (≤=≥)b2
…………………………………………………………..
…………………………………………………………..
am1x1+am2x2+…………+ amnxn (≤=≥)bm
3. Non-negative constraints
x1,x2,….xm≥ 0

3. What are the characteristic of LPP?

• There must be a well defined objective function.
• There must be alternative course of action to choose.
Both the objective functions and the constraints must be linear
equation or inequalities
4 What are the characteristic of standard form of LPP?
• The objective function is of maximization type.
• All the constraint equation must be of equal type by adding slack or surplus variables
• RHS of the constraint equation must be positive type
• All the decision variables are of positive type

5 What are the characteristics of canonical form of LPP? (NOV ’07)

In canonical form, if the objective function is of maximization type, then all
constraints are of ≤ type. Similarly if the objective function is of minimization type, then all
constraints are of ≥ type. But non-negative constraints are ≥type for both cases.
6
6. A firm manufactures two types of products A and B and sells them at profit of Rs 2
on type A and Rs 3 on type B. Each product is processed on two machines M1 and
M2.Type A requires 1 minute of processing time on M1 and 2 minutes on M2 Type B
requires 1 minute of processing time on M1 and 1 minute on M2. Machine M1 is
available for not more than 6 hours 40 minutes while machine M2 is available for 10
hours during any working day. Formulate the problem as a LPP so as to maximize
the profit. (MAY ’07) Maximize z =2x1 +3x2
Subject tot the constraints:
x1 + x2 ≤ 400 2x1 + x2 ≤ 600 x1
,x2≥ 0

7 A company sells two different products A and B , making a profit of Rs.40 and Rs. 30
per unit on them,respectively.They are produced in a common production process
and are sold in two different markets, the production process has a total capacity of
30,000 man-hours. It takes three hours to produce a unit of A and one hour to
produce a unit of B. The market has been surveyed and company official feel that the
maximum number of units of A that can be sold is 8,000 units and that of B is 12,000
units. Subject to these limitations, products can be sold in any combination.
Formulate the problem as a LPP so as to maximize the profit
Maximize z =40x1 +30x2
Subject tot the constraints:
3x1 + x2 ≤ 30,000 x1 ≤
8000 x2 ≤ 12000
x1 ,x2≥ 0

8 What is feasibility region? (MAY ’08)

Collections of all feasible solutions are called a feasible set or region of an
optimization model. Or A region in which all the constraints are satisfied is called feasible
region.

9
What is feasibility region in an LP problem? Is ti necessary that it should always be a
convex set?
A region in which all the constraints are satisfied is called feasible
region. The feasible region of an LPP is always convex set.
10 Define feasible solution? (MAY ’07,NOV/DEC 2016,NOV/DEC 2017)
Any solution to a LPP which satisfies the non negativity restrictions of LPP’s called the
feasible solution

11 Define optimal solution of LPP. (MAY ’09)

Any feasible solution which optimizes the objective function of the LPP’s called the
optimal solution

12 State the applications of linear programming

• Work scheduling
• Production planning & production process
• Capital budgeting
• Financial planning
• Blending
• Farm planning
• Distribution
• Multi-period decision problem
Inventory model
Financial model
13 State the Limitations of LP. (APR/MAY 2018)
• LP treats all functional relations as linear
• LP does not take into account the effect of time and uncertainty
• No guarantee for integer solution. Rounding off may not feasible or optimal solution.
• Deals with single objective, while in real life the situation may be difficult.

14 Define shadow pricing.

A shadow price is an estimated price for something that is not normally priced or sold in the
market.
In linear programming, a shadow price is the maximum price that should be paid to obtain an
extra unit of a resource. It's also the rate of change in the optimal objective value when the
availability of a resource changes by one unit..
14 What do you understand by redundant constraints?
In a given LPP any constraint does not affect the feasible region or
solution space then the constraint is said to be a redundant constraint.

15 Define Unbounded solution?

If the feasible solution region does not have a bounded area the maximum value of Z occurs
at infinity. Hence the LPP is said to have unbounded solution

16 Define Multiple Optimal solution?

A LPP having more than one optimal solution is said to have
alternative or multiple optimal solutions.

17 What is slack variable? (APR/MAY 2017)

If the constraint as general LPP be <= type then a non negative variable is introduced to
convert the inequalities into equalities are called slack variables. The values of these
variables are interpreted as the amount of unused resources.

18 What are surplus variables?

If the constraint as general LPP be >= type then a non negative
is introduced to convert the inequalities into equalities are called the surplus variables

19 Define Basic solution?

Given a system of m linear equations with n variables(m<n).The
solution obtained by setting (n-m) variables equal to zero and solving for the remaining
m variables is called a basic solution.
20 What do you mean by shadow pricing?(NOV/DEC 2016)
Shadow price or dual price is a quantitative technique to analyze
theimprovement in the contribution or costs by having one additional unit
of a resource which is causing a bottleneck. The maximum price that a
business should be willing to pay for one additional unit of some type of
resource

21 Define unrestricted variable and artificial variable. (NOV ’07)

• Unrestricted Variable :A variable is unrestricted if it is allowed to take on
positive, negative or zero values
• Artificial variable :One type of variable introduced in a linear program model in
order to find an initial basic feasible solution; an artificial variable is used for
equality constraints and for greater-than or equal inequality constraints

22 Define basic variable and non-basic variable in linear programming.

A basic solution to the set of constraints is a solution obtained by setting any n
variables equal to zero and solving for remaining m variables not equal to zero. Such
m variables are called basic variables and remaining n zero variables are called non-
basic variables.

23 What do you understand by degeneracy?

The concept of obtaining a degenerate basic feasible solution in LPP
is known as degeneracy. This may occur in the initial stage when atleast one basic
variable is zero in the initial basic feasible solution.

24 How do you identify that LPP has no solution in a two phase method?
If all Zj – Cj ≤ 0 & then atleast one artificial variable appears in the
optimum basis at non zero level the LPP does not possess any solution.

25 From the optimum simplex table how do you identify that the LPP has
no solution?
If atleast one artificial variable appears in the basis at zero level with
a +ve value in the Xb column and the optimality condition is satisfied then
the original problem has no feasible solution.
26 What is the function of minimum ratio?
• To determine the basic variable to leave
• To determine the maximum increase in basic variable To
maintain the feasibility of following solution

27 Define degenerate basic solution?

A basic solution is said to be a degenerate basic solution if one or
more of the basic variables are zero.

28 Define non Degenerate Basic feasible solution?

The basic solution is said to be a non degenerate basic solution if
None of the basic variables is zero.

29 Solve the following LP problem by graphical method. (MAY ’08)

Maximize z =6x1 +4x2 Subject tot the constraints: x1 + x2 ≤ 5
x2≥ 8
x1 ,x2≥ 0

30 Define the standard form of LPP in the matrix notation?

In matrix notation the canonical form of LPP can be expressed as
Maximize Z = CX(obj fn.)
Sub to AX <= b(constraints) and X >= 0 (non negative
restrictions)
Where C = (C1,C2,…..Cn),

A= a11 a12 ….. a1n X = x1 b = b1

a21 a22….. a2n , x2 , b2
.
. .
.
. .
am1 am2…. amn xn bn
31
What is sensitivity analysis? (APR/MAY 2017, NOV/DEC 2017)
Sensitivity Analysis deals with finding out the amount by which we can
change the input data for the output of our linear programming model to
remain comparatively unchanged. This helps us in determining the
sensitivity of the data we supply for the problem.

32 List any four application areas of Operation Research. APR/MAY 2018

• Agriculture & Forestry.
• Airline Crew Scheduling.
• Bioinformatics.
• Cutting & Packing Problems in the Production Industry.
Education.
 UNIT-II

UNIT II DUALITY AND NETWORKS 9

Definition of dual problem – Primal – Dual relation ships – Dual simplex methods – Post optimality
analysis – Transportation and assignment model - Shortest route problem

1 Define transportation problem.

It is a special type of linear programming model in which the goods
are shipped from various origins to different destinations. The objective is
to find the best possible allocation of goods from various origins to different
destinations such that the total transportation cost is minimum.

2 Define the following: Feasible solution

A set of non-negative decision values xij (i=1,2,….m; j=1,2…n)
satisfies the constraint equations is called a feasible solution.

3 Define the following: basic feasible solution

A basic feasible solution is said to be basic if the number of positive
allocations are m+n-1.( m-origin and n-destination).If the number of
allocations are less than (m+n-1) it is called degenerate basic feasible
solution.

4 Define optimal solution in transportation problem

A feasible solution is said to be optimal, if it minimizes the total
transportation cost.

5 . What are the methods used in transportation problem to obtain the

initial basic feasible solution.
• North-west corner rule
• Lowest cost entry method or matrix minima method
• Vogel’s approximation method
6 What are the basic steps involved in solving a transportation problem.
To find the initial basic feasible solution
To find an optimal solution by making successive improvements from the
initial basic feasible solution

7 What do you understand by degeneracy in a transportation problem?

(NOV ’07,APR/MAY 2018)
If the number of occupied cells in a m x n transportation problem is
less than ( m+n-1) then the problem is said to be degenerate.

8 What is balanced transportation problem& unbalanced transportation

problem?
When the sum of supply is equal to demands, then the problem
is said to be balanced transportation problem.
A transportation problem is said to be unbalanced if the total supply
is not equal to the total demand.

9 How do you convert an unbalanced transportation problem into a

balanced one? (APR/MAY 2018)

The unbalanced transportation problem is converted into a

balanced one by adding a dummy row (source) or dummy column
(destination) whichever is necessary. The unit transportation cost of the
dummy row/ column elements are assigned to zero. Then the problem is
solved by the usual procedure.

10 Explain how the profit maximization transportation problem can be

converted to an equivalent cost minimization transportation problem.
(MAY ’08)
If the objective is to maximize the profit or maximize the expected
sales we have to convert these problems by multiplying all cell entries by
1.Now the maximization problem becomes a minimization and it can be
solved by the usual algorithm
11 Determine basic feasible solution to the following transportation
problem using least cost method. (MAY ’09)
A B C D SUPPLY
P 1 2 1 4 30
Q 3 3 2 1 50
R 4 2 5 9 20 Demand 20 40
30 10

12 Define transshipment problems?

A problem in which available commodity frequently moves from one source
to another source or destination before reaching its actual destination is
called transshipment problems

m n
ai bj
i 1 j 1
13 What are the necessary and sufficient conditions for a transportation
problem to have a solution? (NOV/DEC 2016)
A necessary and sufficient condition for the existence of a feasible
solution to the transportation problem is that

14 What is the difference between Transportation problem &

Transshipment Problem?
In a transportation problem there are no intermediate shipping points
while in transshipment problem there are intermediate shipping points

15 What is assignment problem? (NOV/DEC 2017)

An assignment problem is a particular case of a transportation
problem in which a number of operations are assigned to an equal number
of operators where each operator performs only one operation, the overall
objective is to maximize the total profit or minimize the overall cost of the
given assignment.
16 . Define unbounded assignment problem and describe the steps
involved in solving it?
If the no. of rows is not equal to the no. of column in the given cost
matrix the problem is said to be unbalanced. It is converted to a balanced
one by adding dummy row or dummy column with zero cost.

17 Explain how a maximization problem is solved using assignment

model?
The maximization problems are converted to a minimization one of
the following method.
(i) Since max z = min(-z)
(ii) Subtract all the cost elements all of
the cost matrix from the
Highest cost element in that cost matrix.

18 What do you understand by restricted assignment? Explain how you

should overcome it?
The assignment technique, it may not be possible to assign a
particular task to a particular facility due to technical difficulties or other
restrictions. This can be overcome by assigning a very high processing
time or cost (it can be ∞) to the corresponding cell.

19 How do you identify alternative solution in assignment problem?

Sometimes a final cost matrix contains more than required number
of zeroes at the independent position. This implies that there is more than
one optimal solution with some optimum assignment cost.

20 What is a traveling salesman problem?

A salesman normally must visit a number of cities starting from his
head quarters. The distance between every pair of cities are assumed to
be known. The problem of finding the shortest distance if the salesman
starts from his head quarters and passes through each city exactly once
and returns to the headquarters is called Traveling Salesman problem.
21 Define route condition?
The salesman starts from his headquarters and passes through each
city exactly once.

22 What are the areas of operations of assignment problems?

Assigning jobs to machines.
Allocating men to jobs/machines.
Route scheduling for a traveling salesman

23 DefineTransportation problem(TP): (NOV/DEC 2017)

Distributing any commodity from any group of supply centers, called
sources, to any group of receiving centers, called destinations, in such a
way as to minimize the total distribution cost (shipping cost).

24 24. What are the Methods to find optimal solution

1. The stepping-stone method
2. The Modified distribution method(MODI or u-v method)

25 What are the Solution of TP:

Step 1 :Make a transportation model
Step 2 : Find the initial basic feasible solution
Step 3 : Find an optimal solution
26.What are the characteristics of primal and dual problem? NOV/DEC
2016)
26 Define unbounded assignment problem and what are the rules to
recognize it?
In some LP models, the values of the variables may be increased
indefinitely without violating any of the constraints, meaning that the
solution space is unbounded in at least one direction. As a result, the
objective value may increase (maximization case) or decrease
(minimization case) indefinitely.
The rule for recognizing unboundedness is that if at any iteration all the
constraint coefficients of any non basic variable are zero or negative, then
the solution space is unbounded in that direction. The objective coefficient
of that variable is negative in the case of maximization or positive in the
case of minimization, then the objective value is unbounded as well.

27 Define the mathematical formulation of an assignment problem.

The assignment problem can be expressed as
Maximize Z =
Where cij is the cost of assigning ith machine to the jth job subject to the
constraints

xij =

i.e) xij = 1 or 0 xij (xij – 1) = 0 xij2 = xij

= 1, i = 1, 2, …, n and

=1, j = 1, 2, … , n
28 How will you overcome degeneracy in a transportation problem?

If the number of occupied cells in a m x n transportation problem is

less than (m+n-1) then the problem is said to be degenerate where m is the
number of rows and n is the number of columns in the transportation table.
To resolve degeneracy, allocate an extremely small amount (close to zero)
to one or more empty cells of the transportation table, so that the total
number of occupied cells becomes (m+n-1) at independent positions. The
small amount is denoted by .

29 Explain the difference between transporta tion and assignment

problems? Assignment problems
Supply at any source
Transportation problems be 1.
Demand at any
1) supply at any source may will be 1.
be a will any positive One source one
quantity.

2) Demand at any destination

may destination be a
positive quantity.

3) One or more source to any

number

destination.
of destination.

30 Explain how the profit maximization transportation problem can be

converted to an equivalent cost minimization transportation problem.
(MAY ’08)
If the objective is to maximize the profit or maximize the expected
sales we have to convert these problems by multiplying all cell entries by
1.Now the maximization problem becomes a minimization and it can be
solved by the usual algorithm
31

Define primal and dual problem? (APR/MAY 2017,

NOV/DEC 2017)
The Duality in Linear Programming states that every linear programming
problem has another linear programming problem related to it and thus can
be derived from it. The original linear programming problem is called
“Primal,” while the derived linear problem is called “Dual.”

32 Write the difference between the transportation problem and the

assignment problem. (APR/MAY 2017)

Assignment Problem Transportation Problem

(i) Assignment means (i) A transportation problem
allocating various jobs to is concerned with
various people in the transportation method or
organization. Assignment selecting routes in a product
should be done in such a way distribution network among the
that the overall processing time manufacture plant and
is less, overall efficiency is distribution warehouse situated
high, overall productivity is in different regions or local
high, etc. outlets.
(ii) We solve an assignment (ii) We use three methods
problem by using two methods. for solving a transportation
(a) Completer enumeration problem i.e., to find IBFS : (a)
method. VAM (b) NWCR (c) LCM
Thereafter we find the optimum
solution by using the MODI
method.
(b) Hungarian method

(iii)In assignment problem (iii)In transportation method,

management aims at management is searching for a
assignment jobs to various distribution route, which can
people. lead to minimization of cost
and maximization of profit.
33

What is Dual Simplex Method ? (NOV/DEC 2017)

In dual simplex method, the LP starts with an optimum (or
better) objective function value which is infeasible. Iterations are
designed to move toward feasibility without violating optimality.
At the iteration when feasibility is restored, the algorithm ends.

UNIT-III INTEGER PROGRAMMING 9

Cutting plan algorithm – Branch and bound methods, Multistage (Dynamic) programming.
Q. No. Questions

1. Define Integer Programming Problem (IPP)? (DEC ’07)

A linear programming problem in which some or all of the variables in
the optimal solution are restricted to assume non-negative integer values is
called an Integer Programming Problem (IPP) or Integer Linear
Programming

2. Explain the importance of Integer programming problem?

In LPP the values for the variables are real in the optimal solution.
However in certain problems this assumption is unrealistic. For example if
a problem has a solution of 81/2 cars to be produced in a manufacturing
company is meaningless. These types of problems require integer values
for the decision variables. Therefore IPP is necessary to round off the
fractional values.

3. List out some of the applications of IPP? (MAY ’09) (DEC ’07) (MAY
’07) NOV/DEC 2016)
• IPP occur quite frequently in business and industry.
• All transportation, assignment and traveling salesman problems are
IPP, since the decision variables are either Zero or one.

• All sequencing and routing decisions are IPP as it requires the

integer values of the decision variables.
• Capital budgeting and production scheduling problem are PP. In
fact, any situation involving decisions of the type either to do a job or
not to do can be treated as an IPP.
All allocation problems involving the allocation of goods, men,
machines, give rise to IPP since such commodities can be assigned only
integer and not fractional values
3 Bellman’s Principle of Optimality
It is a foundational concept in dynamic programming and optimization,
introduced by Richard Bellman in the 1950s. It provides a framework for
solving complex decision-making problems by breaking them down into
simpler, overlapping subproblems.
The principle states:
"An optimal policy has the property that, regardless of the initial state and
initial decision, the remaining decisions must constitute an optimal policy
with regard to the state resulting from the first decision.
4 List the various types of integer programming? (MAY ’07, APR/MAY
2018)

Mixed IPP
Pure IPP

5 What is pure IPP?

In a linear programming problem, if all the variables in the optimal
solution are restricted to assume non-negative integer values, then it is
called the pure (all) IPP.

6 What is Mixed IPP?

In a linear programming problem, if only some of the variables in
the optimal solution are restricted to assume non-negative integer values,
while the remaining variables are free to take any non-negative values,
then it is called A Mixed IPP.

7 What is Zero-one problem?

If all the variables in the optimum solution are allowed to take values either
0 or 1 as in ‘do’ or ‘not to do’ type decisions, then the problem is called
Zero-one problem or standard discrete programming problem
8 What is the difference between Pure integer programming & mixed
integer integer programming.
When an optimization problem, if all the decision variables are restricted to
take integer values, then it is referred as pure integer programming. If
some of the variables are allowed to take integer values, then it is referred
as mixed integer integer programming
9 Explain the importance of Integer Programming? (APR/MAY 2018)

In linear programming problem, all the decision variables allowed to

take any non-negative real values, as it is quite possible and appropriate to
have fractional values in many situations. However in many situations,
especially in business and industry, these decision variables make sense
only if they have integer values in the optimal solution. Hence a new
procedure has been developed in this direction for the case of LPP
subjected to additional restriction that the decision variables must have
integer values.

10 Why not round off the optimum values in stead of resorting to IP?
(MAY ’08)
There is no guarantee that the integer valued solution (obtained by
simplex method) will satisfy the constraints. i.e. ., it may not satisfy one or
more constraints and as such the new solution may not feasible. So there
is a need for developing a systematic and efficient algorithm for obtaining
the exact optimum integer solution to an IPP.

11 What are methods for solvingIPP? (MAY ’08,NOV/DEC 2016)

Integer programming can be categorized as
(i) Cutting methods (ii)
Search Methods
12 What is cutting plane method?
A systematic procedure for solving pure IPP was first developed by
R.E.Gomory in 1958. Later on, he extended the procedure to solve mixed
IPP, named as cutting plane algorithm, the method consists in first solving
the IPP as ordinary LPP.By ignoring the integrity restriction and then
introducing additional constraints one after the other to cut certain part of
the solution space until an integral solution is obtained.

13 What is search method?

It is an enumeration method in which all feasible integer points are
enumerated. The widely used search method is the Branch and Bound
Technique. It also starts with the continuous optimum, but systematically
partitions the solution space into sub problems that eliminate parts that
contain no feasible integer solution. It was originally developed by
A.H.Land and A.G.Doig.
14 Explain the concept of Branch and Bound Technique?
The widely used search method is the Branch and Bound
Technique. It starts with the continuous optimum, but systematically
partitions the solution space into sub problems that eliminate parts that
contain no feasible integer solution. It was originally developed by
A.H.Land and A.G.Doig.

15 Define the general format of IPP?

The general IPP is given by
Maximize Z = CX
Subject to the constraints
AX ≤ b,
X ≥ 0 and some or all variables are integer.

16 Explain an algorithm for Gomory’s Fractional Cut algorithm?

(NOV/DEC 2017)

1. Convert the minimization IPP into an equivalent

maximization IPP and all the coefficients and constraints should
be integers.
2. Find the optimum solution of the resulting
maximization LPP by using simplex method.
3. Test the integrity of the optimum solution.
4. Rewrite each XBi
5. Express each of the negative fractions if any, in the kth
row of the optimum simplex table as the sum of a negative
integer and a non-negative fraction.
6. Find the fractional cut constraint
7. Add the fractional cut constraint at the bottom of
optimum
simplex table obtained in
step 2.
8. Go to step 3 and repeat the procedure until an
optimum integer
solution is obtained.
17 What is the purpose of Fractional cut constraints?
In the cutting plane method, the fractional cut constraints cut the
unuseful area of the feasible region in the graphical solution of the problem.
i.e. cut that area which has no integer-valued feasible solution. Thus these
constraints eliminate all the non-integral solutions without loosing any
integer-valued solution.
18.A manufacturer of baby dolls makes two types of dolls, doll X and
doll Y. Processing of these dolls is done on two machines A and B.
Doll X requires 2 hours on machine A and 6 hours on Machine B. Doll
Y requires 5 hours on machine A and 5 hours on Machine B. There
are 16 hours of time per day available on machine A and 30 hours on
machine B.
18 The profit is gained on both the dolls is same. Format this as IPP?
Let the manufacturer decide to manufacture x1 the number of doll X
and x2 number of doll Y so as to maximize the profit. The complete
formulation of the IPP is given by
Maximize Z = x1+x2
Subject to 2 x1 + 5 x2 ≤16

19 Explain Gomory’s Mixed Integer Method?

The problem is first solved by continuous LPP by ignoring the
integrity condition. If the values of the integer constrained variables are
integers, then the current solution is an optimal solution to the given mixed
IPP. Else select the source row which corresponds to the largest fractional
part among these basic variables which are constrained to be integers.
Then construct the Gomarian constraint from the source row. 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 this procedure
until the values of the integer restricted variables are integers in the
optimum solution obtained.

20 What is the geometrical meaning of portioned or branched the original

problem?
Geometrically it means that the branching process eliminates portion
of the feasible region that contains no feasible-integer solution. Each of the
sub-problems solved separately as a LPP.
21 What is standard discrete programming problem?
If all the variables in the optimum solution are allowed to take
values either 0 or 1 as in ‘do’ or ‘not to do’ type decisions, then the problem
is called standard discrete programming problem.

22 What is the disadvantage of branched or portioned method?

It requires the optimum solution of each sub problem. In large
problems this could be very tedious job.

23 How can you improve the efficiency of portioned method?

The computational efficiency of portioned method is increased by
using the concept of bounding. By this concept whenever the continuous
optimum solution of a sub problem yields a value of the objective function
lower than that of the best available integer solution it is useless to explore
the problem any further consideration. Thus once a feasible integer solution
is obtained, its associative objective function can be taken as a lower
bound to delete inferior sub-problems. Hence efficiency of a branch and
bound method depends upon how soon the successive sub-problems are
fathomed.

24 What are the condition of branch and bound method

1.The values of the decision variables of the problem are integer
2.The upper bound of the problem which has non-integer values for
its decision variables is not greater than the current best lower
bound
3. The problem has an infeasible solution

25 What are Traditional approach to solving integer programming

problems.
 Feasible solutions can be partitioned into smaller subsets
Smaller subsets evaluated until best solution is found.
 Method is a tedious and complex mathematical process

26 What are the condiitions that are helpful in computation in ILP.

The most important factor affecting computation in ILP is the number of
integer variables and the feasible range in which they apply. It may be
 advantageous to reduce the number of integer variables in the ILP model
as much as possible. The following suggestions may provide helpful:
 Approximate the integer variables by continuous ones whenever
possible.
 For the integer variables, restrict their feasible ranges as much as
possible.
Avoid the use of nonlinearity in the model

27 What is a fractional cut?

In the cutting plane method, the fractional cut constraints cut the
unused area of the feasible region in the graphical solution of the problem.
i.e. cut that area which has no integer-valued feasible solution. Thus these
constraints eliminate all the non-integral solutions without loosing any
integer-valued solution. A desired cut which represents a necessary
condition for obtaining an integer solution is referred to as the fractional cut
because all its coefficients are fractions.

28 . What is mixed integer problem?

In the mixed integer programming problem only some of the
variables are integer constrained, while other variables may take integer or
other real values. The problem is first solved as a continuous LPP by
ignoring the integer condition. If the values of the integer constrained
variables are integers then the current solution is an optimal 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 Gomorian constraint from the
source row.

29
What is dynamic programming? (NOV/DEC 2017)

Dynamic programming is the mathematical technique of

optimization using multistage decision process. It is a process in which a
sequence of interrelated decisions has to be made. It provides a systematic
procedure for determining the combination of decisions which maximize
overall effectiveness.

30 What is the need for dynamic programming.

Decision making process consists of selecting a combination of
 plans from a large number of alternative combinations. This involves lot of
computational work and time. Dynamic programming deals with such
situations by dividing the given problem into sub problems or stages. Only
one stage is considered at a time and the various infeasible combinations
are eliminated with the objective of reducing the volume of computations.
The solution is obtained by moving from one stage to the next and is
completed when the final stage is reached.

31 List some characteristics of dynamic programming problems.

The characteristics of dynamic programming problems may be outlined as:
 Each problem can be divided into stages, with a policy decision
required at each stage.
 Each stage has number of states associated with it.
 The effect of the policy decision at each stage is to transform the
current state into a state associated with the next stage.
The current state of the system is described by state variables.

32
List different types of Integer programming problems.
(APR/MAY 2017)
0-1 integer linear programming
Mixed-integer programming
33
Write the Gomory's constraint for the all integer programming problem
whose simplex table (with non integer solution) given below :
(APR/MAY 2017)

Refer Notes

UNIT-IV CLASSICAL OPTIMISATION THEORY

Unconstrained external problems, Newton – Ralphson method – Equality constraints – Jacobean
methods – Lagrangian method – Kuhn – Tucker conditions – Simple problems.

Q. No. Questions

1. Discuss the different types of nonlinear programming problems.

Price elasticity

• Product-mix problem
• Graphical nillustration
• Global and local optimum
2. Explain the application areas of nonlinear programming problems.
• Transportation problem
• Product mix problem
• NP Problems

3.
Define the Lagrangean model.

4 What is Newton Ralphson method? (APR/MAY 2018)

Newton and Joseph Raphson, is a method for finding successively
better approximations to the roots (or zeroes) of a real-valued
function

5 Define KKT (APR/MAY 2018)

The Karush–Kuhn–Tucker (KKT) conditions (also known as the Kuhn–

Tucker conditions) are first order necessary conditions for a solution in
nonlinear programming to be optimal, provided that some regularity
conditions are satisfied. Allowing inequality constraints, the KKT
approach to nonlinear programming generalizes the method of
Lagrange multipliers, which allows only equality constraints. The
system of equations corresponding to the KKT conditions is usually not
solved directly, except in the few special cases where a closed-form
solution can be derived analytically.

6 Define Jacobean method.

7 What are the Kuhn-Tucker conditions. (APR/MAY 2018)

1.L10inearity constraint qualification.

2.Line11ar independence constraint qualification (LICQ):
3.Manga12sarian–Fromovitz constraint qualification (MFCQ):
3.Constant 13rank constraint qualification (CRCQ):
4.Constant po14sitive linear dependence constraint qualification
(CPLD): 15

8 Define nonlinear programming.

Nonlinear programming is the process of solving an optimization
problem defined by a system of equalities and inequalities, collectively
termed constraints, over a set of unknown real variables, along with an
objective function to be maximized or minimized, where some of the
constraints or the objective function are nonlinear

9 Explain format of non linear programming

Let n, m, and p be positive integers. Let X be a subset of Rn, let f, gi,
and hj be real-valued functions on X for each i in {1, …, m} and each j in {1,
…, p}.
A nonlinear minimization problem is an optimization problem of the form
10 What is the condition to be checked for minimization type objective
function?
The stationary point will be given the minimum objective function
value if the sign of each of the last (n – m) principal minor determinants of
the bordered Hessian matrix is the same as that of (-1)m, ending with the
(2m+1)th principal minor determinant.

11 What re the optimisation problems

• Constrained optimisation problems
• Un Constrained optimisation problems

12

what
are steps for gomary algorithms
13 What are the steps for branch and bound algorithm.

14 Define lower bound in optimisation.

15 Define
upper
bound
in
optimization

16 What are condition of branch and bound method

17 What is the condition to be checked for maximization type objective

function? The stationary point will be given the maximum objective
function value if the sign of each of the last (n – m) principal minor
determinants of the bordered Hessian matrix is the same as that of (-1)m+1,
ending with the (2m+1)th principal minor determinant
18 What are the steps to implement Jacobean method?

19 What are the condition for Kuhn-Tucker conditions.

1.Linearity constraint qualification.
2.Linear independence constraint qualification (LICQ):

20 What are the KKTcondition?

21 Solve the problem by kkt condition

22 What are the requirements of newton’s method

23 what are the methods of one dimentional unconstrained optimization?

24 what are the methods of one dimentional unconstrained optimization?

25 .(NOV/DEC 2016)

The form for nonlinear programming: Maximize or minimize Z = f(X 1, X2,

….., Xj,……, Xn) subject to Gi(X1, X2, ….., Xj,……, Xn) = bi, i = 1, 2, ….., m,
Xj 0, j = 1, 2, ….., n.

26 How do classical optimization problems determine points of maxima

and minima?

Classical optimization theory uses differential calculus to determine

points of maxima and minima extrema) for unconstrained and constrained
functions. The methods may not be suitable for efficient numerical
computations, but the underlying theory provides the basis for most
nonlinear programming algorithms.
27 What is the necessary condition for an n variable function to have
extrema?
A necessary condition for X0 to be an extreme point of f(x) is that
f(X0) = 0.

28 What is the sufficient condition for a function to have extrema?

A sufficient condition for a stationary point X0 to be an extremum is that
Hessian matrix H evaluated at X0 satisfy the following conditions:

H is positive definite if X0 is minimum point.

H is negative definite if X0 is maximum point.

29 List the types of constrained problems.

There are 2 types of constrained problem
Equality constraints
Inequality constraints
30 Mention the steps involved in Lagrangean method.
Step 1: Form the Lagrangean function.
Step 2: The first partial derivative of L with respect to Xj is obtained,
where j varies from 1 to n, and also with respect to i, where i
varies from 1 to m. then equate them to 0.
Step 3: Solution to equations in step 2 are found.
Step 4: The bordered Hessian square matrix [HB] of size n + m is
formed.
Step 5: The stationary points (X1*, X2*, ….., Xj*,……, Xn*) are tested
for maximization/minimization objective function.

31

The form for nonlinear programming: Maximize or minimize Z = f(X1, X2, …..,
Xj,……, Xn) subject to Gi(X1, X2, ….., Xj,……, Xn) = bi, i = 1, 2, ….., m, Xj 0,
j = 1, 2, ….., n.
(APR/MAY 2017)

32
 (APR/MAY 2017)

UNIT-V OBJECT SCHEDULING: 9

Network diagram representation – Critical path method – Time charts and resource leveling –
PERT
Q. No. Questions

1. What do you mean by project?

A project is defined as a combination on inter related activities with
limited resources namely men, machines materials, money and time all of
which must be executed in a defined order for its completion.

2. . What are the three main phases of project?

Planning – This phase involves a listing of tasks or jobs that must be
performed to complete a project under considerations. Scheduling – This
phase involves the laying out of the actual activities of the projects in a
logical sequence of time in which they

have to be performed.
Control – This phase consists of reviewing the progress of the project
whether the actual performance is according to the planned schedule and
finding the reasons for difference, if any, between the schedule and
performance.
3. What are the two basic planning and controlling techniques in a
network analysis?
• Critical Path Method (CPM)
• Programme Evaluation and Review Technique (PERT)

4 What are the advantages of CPM and PERT techniques?

• It encourages a logical discipline in planning, scheduling and control
of projects
• It helps to effect considerable reduction of project times and the cost
• It helps better utilization of resources like men,machines,materials
and money with reference to time
• It measures the effect of delays on the project and procedural
changes on the overall schedule.

5 What is the difference CPM and PERT (APR/MAY 2018)

CPM
• Network is built on the basis of activity
• Deterministic nature
• One time estimation
PERT
• An event oriented network
• Probabilistic nature
Three time estimation
6 What is network?
A network is a graphical representation of a project’s operation and is
composed of all the events and activities in sequence along with their inter
relationship and inter dependencies
7 What is Event in a network diagram?
An event is specific instant of time which marks the starts and end
of an activity. It neither consumes time nor resources. It is represented by a
circle.

8 Define activity?
A project consists of a number of job operations which are called
activities. It is the element of the project and it may be a process, material
handling, procurement cycle etc.

9 Define Critical Activities?

In a Network diagram critical activities are those whose if consumer

more than estimated time the project will be delayed.

10 Define non critical activities?
Activities which have a provision such that the event if they
consume a specified time over and above the estimated time the project
will not be delayed are termed as non critical activities.

11 Define Dummy Activities?

When two activities start at a same time, the head event are joined
by a dotted arrow known as dummy activity which may be critical or non
critical.

12 Define duration?
It is the estimated or the actual time required to complete a trade or
an activity.

13 Define total project time?

It is time taken to complete to complete a project and just found
from the sequence of critical activities. In other words it is the duration of the
critical path.

14 Define Critical Path?(NOV/DEC 2016)

It is the sequence of activities which decides the total project
duration. It is formed by critical activities and consumes maximum
resources and time.

15 Define float or slack? (MAY ’08)

Slack is with respect to an event and float is with respect to an
activity. In other words, slack is used with PERT and float with CPM. Float
or slack means extra time over and above its duration which a non-critical
activity can consume without delaying the project.

16 . Define total float? (MAY ’08)

The total float for an activity is given by the total time which is
available for performance of the activity, minus the duration of the activity.
The total time is available for execution of the activity is given by the latest
finish time of an activity minus the earliest start time for the activity. Thus
Total float = Latest start time – earliest start time.

17 Define free float? (MAY ’08)

This is that part of the total float which does not affect the subsequent
activities. This is the float which is obtained when all the activities are
started at the earliest
18 Define Independent float? (MAY ’07) (MAY ’08)
If all the preceding activities are completed at their latest, in some cases,
no float available for the subsequent activities which may therefore

become critical.
Independent float = free – tail slack.

19 Define Interfering float?

Sometimes float of an activity if utilized wholly or in part, may
influence the starting time of the succeeding activities is known as
interfering float.
Interfering float = latest event time of the head - earliest event time of
the event
20 Define Optimistic?
Optimistic time estimate is the duration of any activity when everything goes
on very well during the project
21 Define Pessimistic? (APR/MAY 2018)

Pessimistic time estimate is the duration of any activity when almost

everything goes against our will and a lot of difficulties is faced while doing
a project
22 Define most likely time estimation?
Most likely time estimate is the duration of any activity when
sometimes thing go on very well, sometimes things go on very bad while
doing the project.

23 What is a parallel critical path?

When critical activities are crashed and the duration is reduced other
paths may also become critical such critical paths are called parallel critical
path.

24 What is standard deviation and variance in PERT network? (NOV ’07)

The expected time of an activity in actual execution is not
completely reliable and is likely to vary. If the variability is known we can
measure the reliability of the expected time as determined from three
estimates. The measure of the variability of possible activity time is given
by standard deviation, their probability distribution
Variance of the activity is the square of the standard deviation
25 Compare direct cost and indirect cost? (NOV ’07)
Direct cost is directly depending upon the amount of resources
involved in the execution of all activities of the project. Increase in direct
cost will decrease in project duration. Indirect cost is associated with
general and administrative expenses, insurance cost, taxes etc. Increase in
indirect cost will increase in project duration.

26 What is meant by resource analysis?

Resources are required to carry out the project tasks. They can be
equipment,
facilities, funding which are required for the completion of a project activity.
The lack of resource will therefore be a constraint on the completion of a
project activity.

Resource scheduling, availability and optimization are considered key to

successful project management.

27 . What are the three time estimates used in the context of PERT? How
are the expected duration of an activity and its standard deviation
calculated?
Optimistic time estimate or least time estimate (to or a)
Pessimistic time estimate or greatest time estimate (tp or b)
Most likely time estimate (tm or b)
Expected Duration = (te+4tm+tp)/6
Standard deviation = (tp-to)/6

28 Define a dummy arrow used in a network and state two purposes for
which it is used.
Dummy activity is a hypothetical activity which requires zero time and
zero resources for completion. Dummy arrow represents an activity with
zero duration. It is represented by dotted line and is inserted in the network
to clarify activity pattern under the following situations:
i. It is created to make activities with common starting and finishing
events distinguishable, and ii. To identify and maintain the proper
precedence relationship between activities those are not connected
by events.
29 What are the advantages of PERT.
 It compels managers to plan their projects critically and analyse all
factors affecting the progress of the plan. The process of the network
analysis requires that the project planning be conducted on
considerable detail from the start to the finish.
 It provides the management a tool for forecasting the impact of
schedule changes and be prepared to correct such situations. The
likely trouble spots are located early enough so as to apply some
preventive measures or corrective actions.
 A lot of data can be presented in a highly ordered fashion. The task
relationships are graphically represented for easier evaluation and
individuals in different locations can easily determine their role in the
total task requirements. The PERT time (Te) is based upon 3-way
estimate and hence is the most objective time in the light of
uncertainties and results in greater degree of accuracy in time
forecasting.

30 .(NOV/DEC 2016)

31

(APR/MAY 2017)
32

A network is a graphical representation of a project’s operation and is composed of all

the events and activities in sequence along with their inter relationship and inter
dependencies
33

What is CPM ? (NOV/DEC 2017)

The critical path method (CPM) is a step-by-step methodology, technique or algorithm
for planning projects with numerous activities that involve complex, interdependent
interactions. CPM is an important tool for project management because it identifies
critical and non-critical tasks to prevent conflicts and bottlenecks.

34 Write about PERT. (NOV/DEC 2017)

Program evaluation and review technique (PERT) is a technique adopted by

organizations to analyze and represent the activity in a project, and to illustrate the flow
of events in a project. PERT is a method to evaluate and estimate the time required to
complete a task within deadlines.

67