UNIT I -LINEAR PROGRAMMING 9

Principal components of decision problem – Modeling phases – LP Formulation and

graphic solution –Resource allocation problems – Simplex method – Sensitivity analysis.

Bloom’s
Q. No. Questions CO
Level

What is linear programming?

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

Write the general mathematical formulation of LPP. C404.1 BTL1

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

C404.1 BTL1
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
3.

7
 What are the characteristic of standard form of LPP? C404.1 BTL1
 The objective function is of maximization type.
 All the constraint equation must be of equal type by adding slack or
4. surplus variables
 RHS of the constraint equation must be positive type
 All the decision variables are of positive type

What are the characteristics of canonical form of LPP? (NOV ’07) C404.1 BTL1
In canonical form, if the objective function is of maximization type,
then all constraints are of ≤ type. Similarly if the objective function is of
5 minimization type, then all constraints are of ≥ type. But non-negative
constraints are ≥type for both cases.

C404.1 BTL6
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 [Link] 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
6 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

A company sells two different products A and B , making a profit of C404.1 BTL6
Rs.40 and Rs. 30 per unit on them,[Link] 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
7 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) C404.1 BTL1
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
8 satisfied is called feasible region.

C404.1 BTL1
What is feasibility region in an LP problem? Is ti necessary that it
should always be a convex set?
9 A region in which all the constraints are satisfied is called feasible
region. The feasible region of an LPP is always convex set.

Define feasible solution? (MAY ’07,NOV/DEC 2016,NOV/DEC 2017) C404.1 BTL1

Any solution to a LPP which satisfies the non negativity restrictions of
LPP’s called the feasible solution
10

Define optimal solution of LPP. (MAY ’09) C404.1 BTL1

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

State the applications of linear programming C404.1 BTL1

 Work scheduling
 Production planning & production process
 Capital budgeting
 Financial planning
12  Blending
 Farm planning
 Distribution
 Multi-period decision problem
Inventory model
Financial model
State the Limitations of LP. (APR/MAY 2018) C404.1 BTL1
 LP treats all functional relations as linear
 LP does not take into account the effect of time and uncertainty
13  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.

9
 What do you understand by redundant constraints? C404.1 BTL1
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.
14

Define Unbounded solution? C404.1 BTL1

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
15 solution

Define Multiple Optimal solution? C404.1 BTL1

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

What is slack variable? (APR/MAY 2017) C404.1 BTL1

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

What are surplus variables? C404.1 BTL1

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

10
 Define Basic solution? C404.1 BTL1
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
19 remaining m variables is called a basic solution.

What do you mean by shadow pricing?(NOV/DEC 2016) C404.1 BTL1

Shadow price or dual price is a quantitative technique to analyze
theimprovement in the contribution or costs by having one
20 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

Define unrestricted variable and artificial variable. (NOV ’07) C404.1 BTL1
 Unrestricted Variable :A variable is unrestricted if it is allowed to
take on positive, negative or zero values
21  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

Define basic variable and non-basic variable in linear programming. C404.1 BTL1
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
22 not equal to zero. Such m variables are called basic variables and remaining
n zero variables are called non-basic variables.

What do you understand by degeneracy? C404.1 BTL1

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
23 basic variable is zero in the initial basic feasible solution.

How do you identify that LPP has no solution in a two phase method? C404.1 BTL1
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.
24

11
 From the optimum simplex table how do you identify that the LPP has C404.1 BTL1
no solution?
If atleast one artificial variable appears in the basis at zero level with
25 a +ve value in the Xb column and the optimality condition is satisfied
then the original problem has no feasible solution.

What is the function of minimum ratio? C404.1 BTL1

 To determine the basic variable to leave
 To determine the maximum increase in basic variable
26  To maintain the feasibility of following solution

Define degenerate basic solution? C404.1 BTL1

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

Define non Degenerate Basic feasible solution? C404.1 BTL1

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

Solve the following LP problem by graphical method. (MAY ’08) C404.1 BTL3
Maximize z =6x1 +4x2 Subject tot the constraints:
x1 + x2 ≤ 5
29 x2≥ 8
x1 ,x2≥ 0

Define the standard form of LPP in the matrix notation? C404.1 BTL1
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)
30 Where C = (C1,C2,…..Cn),

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

a21 a22….. a2n , x2 , b2
.
. .

12
 .
. .
am1 am2…. amn xn bn

C404.1 BTL1
What is sensitivity analysis? (APR/MAY 2017, NOV/DEC 2017)
Sensitivity Analysis deals with finding out the amount by which we can change
31 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.

C404.1 BTL1
List any four application areas of Operation Research.
APR/MAY 2018
32  Agriculture & Forestry.
 Airline Crew Scheduling.
 Bioinformatics.
 Cutting & Packing Problems in the Production Industry.
 Education.

PART – B
.(NOV/DEC 2016) C404.1 BTL6

Refer Notes
NOV/DEC 2016) C404.1 BTL6

13
 UNIT-I – LINEAR PROGRAMMING
Principal components of decision problem – Modeling phases – LP Formulation and
graphic solution – Resource allocation problems – Simplex method – Sensitivity
analysis.

PART-A
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).

[Link] are the characteristics of Standard form of LPP?

 The objective function is to maximization type.
 All the constraint equation must be 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

3. A firm manufactures two types of product A and B and sells them at profit of Rs2
on type A and Rs3 on type B. Each products is processed on two machines M1 and
[Link] A requires 1 minute of processing time onM1 and 2 minutes on M2 Type
B requires 1 minute of processing time on M1 and 1 minute on [Link] M1 is
available for not more than 6 hours 40 minutes while machine M2 is available for
10 hours during working day. Formulate the problem as a LPP so as to maximize
the profit.
Maximize z= 2 x1+3x2.
Subject to the constraints:
x1+x2 <=400
2x1+x2<=600
x1,x2 >=0

5
4. Define feasible solution.
Any Solution to a LPP which satisfies the non negativity restrictions of LPP‟s
called the feasible solution.

5. Define optimal solution of LPP.

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

6. State the applications of linear programming.

 Work scheduling
 Production planning and production process
 Capital budgeting
 Financial planning
 Blending
 Farm planning
 Distribution

7. State the limitations of LP.

 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.

8. What is slack variable?

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

6
[Link] 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
abasic solution.

[Link] 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.

[Link] surplus variable.

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.

12. Write the standard form of LPP in the matrix solution.

Maximize Z=CX(objective function)
Subject to AX <=b(constraints) and X>=0(non negative restrictions)
Where C=(C1,C2,…Cn)
A= a11…….a12…….a1n
a21…….a22…….a2n
.
.
am1……am2……amn
X=x1 b=b1
x2 b2
. .
. .
xn bn

7
13. What is sensitivity analysis? What does it signify? What is the purpose of
sensitivity analysis?
After formulating mathematic model to linear programming problems and then
attaining the optimal solution of the problem, it may be required to study the effect of
changes in the different parameters of the problem,on the optimum solution, that is it may
be desirable to see the sensitiveness of the feasible optimal solution corresponding to the
variations in the parameters. The investigations that deal with changes in the optimal
solutions due to discrete variations in the parameters aij,bj and cj are called sensitivity
[Link] purpose of sensitivity analysis is to find, how to preserve , to a minimum
,the additional computational efforts which arise in solving the problem as a new one.

[Link] 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

8
PART B

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50