AU Previous Year Question Papers: UNIT – I INTRODUCTION TO LINEAR PROGRAMMING PROBLEM

PART - A

What is OR? Give some applications.

Operations Research has been variously described as the “ Science of Use”, “Quantitative Common sense” “Scientific approach to decision –making problem”etc. But only a few are commonly used and accepted namely

(i) Operations Research is the application of scientific methods techniques and tools to problems involving operations of a system so as to provide those in control of the system with optimum solutions to the problem.

(ii) Operations Research is the art of giving bad answers to problems which otherwise have worse answers.

(iii) O.R. is a scientific method of providing executive department with a quantitative basis for decisions regarding the operations under this control.

(iv) O.R. is applied decision theory. It use any scientific mathematical or logical means to attempt to cope with the problems that confront the executive when he tries to achieve a thorough going rationality in dealing with his decision problems.

(v) O.R. is a scientific approach to problems solving for executive management.

(vi) O.R. is a scientific knowledge through interdisciplinary team effort for the purpose of determining the best utilization of limited resources.

What do you mean by general LPP?

Linear Programming is a mathematical technique for choosing the best alternative from a set of feasible alternatives, in situations where the objective function as well as the restrictions or constraints can be expressed as linear mathematical function.

Give the standard form and canonical form of a LPP

Canonical Form: The general linear programming problem can always be expressed in the following form.

Max. Z = C1X1 + C2X2 + C3X3 + ………. + CnXn

Subject to Constraints

a₁₁x₁ +a₁₂x₂ + a₁₃x₃ + ………… + a_1nx_n £ b₁

a₂₁x₁ +a₂₂x₂ + a₂₃x₃ + ………… + a_2nx_n £ b₂

a₃₁x₁ +a₃₂x₂ + a₃₃x₃ + ………… + a_3nx_n £ b₃

………………………………………………..

a_m1x₁+ a_m2x₂ + a_m3x₃ + …………. + a_mn x_n£ b_m

and non-negativity restrictions x₁ , x₂, x₃ …………x_n ³ 0

This form of LPP is called Canonical form of LPP. In matrix notation the Canonical form of LPP can be expressed as

Max. Z = CX (Objective Fn.)

Subject to AX £ b(Constraints)

And X ³ 0 (Non – negativity restrictions)

Where C = (C₁, C₂, C₃, C₄ ………………. C_n)

A = a₁₁ a₁₂ a₁₃ ………………………. a_1n

a₂₁ a₂₂ a₂₃ ………………………. a_2n

a₃₁ a₃₂ a₃₃ ………………………. a_3n

_{.
.}

. .

_{.
.}

a_m1 a_m2 a_m3 ………………………. a_mn

Standard form: The general linear programming problem in the form

Max. Z = C1x1 + C2x2 + C3x3 + ………….. + Cnxn

Subject to the constraints

And x₁ , x₂, x₃, …….. >= 0is known as standard form.

Specify the components of a LPP (OR) Specify the basic assumptions of LPP

(i) Proportionality (ii) Additively (iii) Divisibility (iv) Certainty (or) Deterministic

(iv) Finiteness (vi) Optimality.

Write any two situations where LPP is applied.

Linear Programming technique is used in many industrial and economic problems. They are applied in product mix, blending, diet, transportation and assignment problems. Oil refineries, airlines, railways , textiles, industries , Chemical industries, steel industries, food processing industries and defense establishments.

Graphical solution is not possible for LPP problem with more than two constraints

True or False? Justify your answer

Which is false. We can solve the LPP by graphical solution with more than two constraints.

What is the use of artificial variable in LPP

The purpose of introducing artificial variables is just to obtain an initial basic

feasible solution.

Define Slack, Surplus variables

Slack Variable: If the constraints of a given LPP be S a_ij x_j£ bi then the non-

negative variable Si which are introduced to convert the inequalities to equalities

S a_ij x_j+ Si = b_i are called slack variables.

Surplus variable: If the constraints of a given LPP be S a_ij x_j³ b_i then the

nonnegative variable Si which are introduced to convert the inequality

constraints to the equations S a_ij x_j- Si = b_i are called surplus variables.

What do you mean by degenerate solution in LPP

A basic solution is said to be a degenerate basic solution if one or more of the

basic variables are zero

Define a feasible region in graphical method.

A region or a set of points is said to be convex (or) feasible region if the line

joining any two of its points lies completely within the region

What is meant by an optimal solution?

Any feasible solution, which optimizes (maximizes or minimizes) the objective

function of the LPP is called its optimum solution or optimal solution.

What is the difference between feasible solution and basic feasible solution?

Feasible solution: Any solution to a LPP, which satisfies the non-negativity

restrictions of the LPP is called its feasible solution.

Basic solution: A basic solution is said to be a degenerate basic solutionif one

or more of the basic variables are zero.

Basic feasible solution: A feasible solution, which is also basic, is called a basic

Feasible solutions.

Define non-degenerate solution

A basic solution is said to be a non-degenerate basic solution if none of the basic variables is zero.

Define unbalanced solution and infeasible solution

Let there exists a basic feasible solution to a given LPP if for at least one j, for which aij £ 0 Zj – Cj is negative, and then there does not exists any optimum solution to this LPP

Infeasible solution: If some values of the set of values x₁,x₂,x₃,x₄ ……..x_n

are negative which satisfies the constraints of the LPP is called its infeasible solution

Which are decision variables in the construction of OR problems?

Linear programming problem deals with the optimization ie maximization or minimization of a function of decision variable. The variables whose values determine the solution of a problem are called decision variables of the problem.

How many basic feasible solutions are there to a given system of m equations in

n Unknowns

Here n > m . There are nCm basic solutions are possible.

What is key column and how is it selected ?

By performing the optimality test we can find whether the current feasible

solution can be improved or not. This can be done by performing Cj – Ej. If

Cj – Ej is positive under any column, at least one better solution is possible. To

find the incoming variable take the highest positive integer in the row Cj – Ej,

the variables belongs to highest positive integer column is the incoming

variable and that column is a key column K

What is key row and how is it selected?

To find the outgoing variable divide the elements of the column “b” by the

element of the key column. The row containing the minimum positive ratio is

marked. The variable belongs to that row is the outgoing variable. That row is

called key row.

How will you find whether a LPP has got an alternative optimal solution or

not, from the optimal simplex table ?

If Cj – Ej is positive under any column, the profit can be increased ie the

current basic feasible solution is not optimal and a better solution exists. When

no more positive values remain in the Cj – Ej row, the solution becomes

Optimal.

What are the advantages of duality?

(i) If the primal problem contains a large number of rows (Constraints) and a smaller number of columns (Variables), the computational procedure can be considerably reduced by converting it into dual and then solving it. Hence it offers advantages in many applications.

(ii) It gives additional information as to how the optimal solution changes as a result of the changes in the coefficients and the formulation of the problem.

(iii) Duality in LP has certain far-reaching consequences of economic nature.

(iv) Calculations of the dual checks the accuracy of the primal solution.

State the existence theorem of duality

If either problem has an unbounded solution then the other problem has no

Feasible solution

State fundamental theorem of duality

If either the primal or dual problem has a finite optimal solution, then the

other problem also has a finite optimal solution and also the optimal values of

the objective function in both the problem are the same. I.e., Max Z = Min Z’

What are the advantages of dual simplex method?

The dual simplex method is used to solve the problems, which start dual

Feasible ie the primal is optimal but infeasible. The advantages of this

Method is avoiding the artificial variables introduced in the constraints along

With the surplus variables as all “ >= “ constraints are converted into “<= “

Type.

24 What do you meant by shadow prices?

The values of the decision variable of dual of a LPP represents shadow

price of a resource.

25.What is the advantage of dual simplex method?

The advantage of dual simplex method is to avoid introducing the artificial

variables along with the surplus variable as the ³ type constraint is converted into

£ type.

PART-B

(1) A firm produces 3 products. These products are processed on 3 different machines. The time required to manufacture one unit of each of the 3 products and the daily capacity of the 3 machines are given below:

Machine	Time per unit (minutes)			Machine
Machine	Product1	Product2	Product3	Capacity (Minutes/day)
M₁	2	3	2	440
M₂	4	-	3	470
M₃	2	5	-	430

It is required to determine the number of units to be manufactured for each product daily. The profit per unit for product 1,2 and 3 is Rs4, Rs3, Rs6 respectively. It is assumed that all the amounts produced are consumed in the market. Formulate the mathematical model for the problem.

Solution: Maximize Z = 4x₁+3x₂+6x₃

Sub to the constraints

2x₁+3x₂+2x₃ £ 440

4x₁+3x₂ £ 470

2x₁+5x₂ £ 430 & x₁,x₂,x₃ ³ 0

(2)A firm produces an alloy having the following specifications:

(i) Specific gravity £ 0.98

(ii) Chromium ³ 8%

(iii) Melting point ³ 450°C

Raw materials A, B, C having the properties shown in the table can be used to make the alloy.

Property	Raw material
Property	A	B	C
Specific gravity	0.92	0.97	1.04
Chromium	7%	13%	16%
Melting point	440°C	490°C	480°C

Cost of the various raw materials per unit ton are: Rs.90 for A, Rs.280 for B and Rs.40 for C. Find the proportions in which A,B and C be used to obtain an alloy of desired properties while the cost of raw materials is minimum.

Solution: Minimize Z = 90x₁+ 280x₂ + 40x₃

Sub to

0.92x₁ + 0.97x₂ +1.04x₃ £ 0.98

7x₁ + 13x₂+16x₃ ³ 8

440x₁ +490x₂ +480x₃ ³ 450 & x₁, x₂, x₃ ³ 0

(3)ABC manufacturing company can make 2 products P₁ and P₂.Each of the product require time on a cutting machine and a finishing machine relevant data are

Require time	Product
Require time	P₁	P₂
Cutting hrs (per unit)	2	1
Finishing hrs (per unit)	3	3
Profit 9per unit)	Rs.6	Rs.4
Max. sales (per week)	-	210

The number of cutting hours available per week is 390 and the number of finishing hours available per week is 810.How much of each product should be produce in order to maximize the profit ? Nov/Dec 2003
Solution: Max Z = 6x₁ +4x₂

Sub to

2x₁ +x₂ £ 390

3x₁ + 3x₂ £ 810 & x₁, x₂ ³ 0

(4)Old hens can be bought at Rs.2 each and young ones at Rs.5 each. The old hens lay 3 eggs per week and the young ones lay 5eggs per week, each egg being worth 30 paise. A hen costs Rs.1 per week to feed. A person has only Rs.80 to spend for hens. How many of each kind should he buy to give a profit of more than Rs.6 per week, assuming that he cannot house more than 20 hens. Formulate this as a L.P.P.

Solution: Max Z = 0.5 x₂ – 0.1x₁

Sub to

2x₁ + 5x₂ £ 80

x₁ + x₂ £ 20

0.5x₂ – 0.1x₁ ³ 6 & x₁, x₂ ³ 0

(5) A television company operates 2 assembly sections, section A and section B. Each section is used to assemble the components of 3 types of televisions : Colour, standard and Economy. The expected daily production on each section is as follows :

T.V Model	Section A	Section B
Colour	3	1
Standard	1	1
Economy	2	6

The daily running costs for 2 sections average Rs.6000 for section A and Rs.4000 for section B .It is given that the company must produce at least 24 colours, 16 standard and 40 Economy TV sets for which an order is pending. Formulate this as a L.P.P so as to minimize the total cost.

Solution : Minimize Z = 6000x₁+ 4000x₂

Sub to

3x₁ + x₂ ³ 24

x₁ + x₂³ 16

2x₁ + 6x₂³ 40 & x₁ , x₂ ³ 0

(6) An electronics company produces three types of parts for automatic washing machine.

It purchases costing of the parts from a local foundry and then finishes the part of

drilling, shaping and polishing machines.

The selling prices of parts A,B and C respectively are Rs. 8,Rs.10 and Rs.14.All parts

made can be sold.Casing for parts A,B and C respectively cost Rs.5,RS.6 and

Rs.10.The shop possesses only one of each type of machine. Costs per hour to run

each type of three machines are Rs.20 for drilling, Rs.30 for shaping and for

polishing.The capacities for each part on each machine are shown in the following

table.

Machine/Capacity per hour	Part A	Part B	Part C
Drilling	25	40	25
Shaping	25	20	20
Polishing	40	30	40

(MAY/JUNE 2007)

(6) Solve Graphically: Maximize Z = 3x₁ + 9x₂

sub to x₁ + 4x₂ £ 8

x₁ + 2x₂ £ 4 & x₁, x₂ ³ 0

Solution : Z = 18 , x₁ = 0, x₂ = 2 , x₃ = 0, x₄= 0.

(7)Solve graphically : Maximize Z = 2x₁ + 4x₂

sub to x₁+ 2x₂£ 5

x₁ + x₂ £ 4 & x₁, x₂ ³ 0

Solution : Alternate solution

x₁ = 0 , x₂ = 5/2 and Z = 10 & x₁ = 3, x₂ = 1 , Z = 10.

(8)Solve Graphically: Maximize Z = 2x₁+ x₂

sub to x₁ – x₂ £ 10

2x₁ £ 40 & x₁,x₂ ³ 0.

Solution : Unbounded solution

(9) Solve graphically : Maximize Z = 3x₁+ 2x₂

sub to 2x₁ + x₂ £ 2

3x₁+ 4x₂ ³ 12 & x₁,x₂ ³ 0.

Solution : Infeasible solution.

(10)Solve graphically : Maximize Z = 100x₁+ 40x₂

5x₁ +2 x₂ £ 1000

3 x₁ +2 x₂£ 900

x₁ + 2x₂£ 500 & x₁ , x₂ ³ 0 (MCA,MAY/JUNE 2007)

(11)Solve by Simplex Method: Maximize Z = 3x₁ + 9x₂

sub to x₁+ 4x₂ £ 8

x₁ + 2x₂ £ 4 & x₁,x₂³ 0

Solution : Z = 18 ,x₁= 0, x₂ = 2 , x₃= 0, x₄ = 0.

(12)Solve by Simplex Method : Maximize Z = 2x₁+ 4x₂

sub to x₁ + 2x₂ £ 5

x₁ + x₂£ 4 & x₁,x₂ ³ 0

Solution : Alternate solution

x₁ = 0 , x₂ = 5/2 and Z = 10 & x₁ = 3, x₂ = 1 , Z = 10.

(13) Solve by Simplex Method : Maximize Z = 2x₁+ x₂

sub to x₁ – x₂£ 10

2x₁ £ 40 & x₁,x₂ ³ 0.

Solution : Unbounded solution

(14) Solve by Simplex Method: Maximize Z = 3x1 + 2x2

sub to 2x1 + x2 £ 2

3x1 + 4x2 ³ 12 & x1,x2 ³ 0.

Solution : Infeasible solution.

(15) Solve by Simplex Method : Maximize Z = 20 x₁ + 30x₂

Sub to 2x₁+ 3x₂£ 120

x₁ + x₂ ³ 35

2x₁ + 1.5x₂£ 90 & x₁, x₂ ³ 0. Apr/May 2004

Solution : Z = 1050 ,x₁ = 0 , x₂ = 35.

(16)Maximize Z = 15x₁ +6 x₂ +9 x₃+2x4

Sub to 2x₁ +x₂+ 5x₃ +6x₄£ 20

3x₁+x₂+ 3x₃ +25x₄£ 24

7x₁ + x₄ £ 70 & x₁, x₂,x_3, x₄ ³ 0. (MCA,MAY/JUNE 2007)

(16) Solve by Simplex Method : Minimize Z = 8x₁ – 2x₂

Sub to -4x₁+ 2x₂ £ 1

5x₁ – 4x₂£ 3 & x₁, x₂ ³ 0.

Solution : Min Z = -1, x₁ = 0, x₂= ½.

(17)Use Big-M OR Penalty Method to solve

Maximize Z = 2x₁ + x₂ + x₃

Sub to 4x₁ + 6x₂+ 3x₃ £ 8

3x₁– 6x₂– 4x₃ £ 1

2x₁ + 3x₂ – 5x₃ ³ 4. & x₁, x₂,x₃ ³ 0.

Solution: Max Z = 64/21, x₁ = 9/7, x₂ = 10/21 , x₃ = 0

(18)Use Big-M OR Penalty Method to solve

Minimize Z = 4x₁+ 3x₂

Sub to 2x₁ + x₂³ 10

-3x₁ + 2x₂£ 6

x₁ + x₂ ³ 6 & x₁,x₂ ³ 0.

Solution : Min Z = 22, x₁= 4, x₂ = 2.

(19)Use Two-phase method to solve

Maximize Z = 5x₁+ 8x₂

Sub to

3x₁+ 2x₂ ³ 3

x₁ + 4x₂ ³ 4

x₁+ x₂ £ 5 & x₁,x₂ ³ 0.

Solution : Max Z = 40, x₁ = 0, x₂ = 5.

(20) Use Two-phase method to solve

Minimize Z = -2x₁– x₂

Sub to

X₁ + x₂ ³ 2

X₁+ x₂ £ 4 & x₁,x₂ ³ 0.

Solution: Min Z = -8, x₁ = 4, x₂ = 0.

Variants of the Simplex Method:

(21`) Solve the L.P.P by Simplex Method :

Maximize Z = x₁ + 2x₂ + x₃

Sub to

2x₁ + x₂ – x₃ £ 2

-2x₁ + x₂ – 5x₃ ³ -6

4x₁ + x₂+ x₃ £ 6 & x₁,x₂,x₃ ³ 0.

Solution : Max Z = 10, x₁= 0, x₂ = 4, x₃ = 2.

(22) Solve the L.P.P by Simplex Method :

Maximize Z = 3x₁ – x₂

Sub to

X₁ – x₂ £ 10

X₁ £ 20 & x₁,x₂ ³ 0.

Solution : Unbounded solution.

(23) Solve the L.P.P by Simplex Method :

Maximize Z = 6x₁ + 4x₂

Sub to

2x₁ + 3x₂ £ 30

3x₁ + 2x₂ £ 24

x₁ + x₂ ³ 3 & x₁,x₂ ³ 0.

Solution : Max Z = 48, x₁ = 8, x₂ = 0 & Max Z = 48, x₁ = 12/5, x₂ = 42/5

(24) Solve the L.P.P by Simplex Method :

Maximize Z = 3x₁+ 2x₂

Sub to

2x₁+ x₂ £ 2

3x₁+ 4x₂ ³ 12 & x₁,x₂ ³ 0.

Solution : Infeasible solution.

(25) Solve the L.P.P by Simplex Method :

Maximize Z = 2x₁ + 3x₂

Sub to

-x₁+ 2x₂ £ 4

x₁ + x₂ £ 6

x₁ + 3x₂ £ 9 & x₁, x₂ are unrestricted.

Solution : Max Z = 27/2, x₁ = 9/2, x₂ = 3/2.

(26)Solve by Dual Simplex Method:

Minimize Z = 3x₁ + x₂

Sub to

3x₁+ x₂³ 3

4x₁+ 3x₂ ³ 6

x₁ + x₂ £ 3 & x₁,x₂ ³ 0.

Solution : Min Z = 21/5, x₁ = 3/5, x₂ = 6/5.

(27) Solve by Dual Simplex Method:

Minimize Z = 2x₁+ 3x₂

Sub to

2x₁ + 2x₂£ 30

x₁ + 2x₂ ³ 10 & x₁, x₂³ 0.

(28)Write down the dual of the following LPP and solve it.

Max Z = 4x₁ + 2x₂

Sub to

-x₁– x₂ £ -3

-x₁ + x₂ ³ -2 & x₁, x₂ ³ 0.

Solution : Infeasible solution

(29)Use duality to solve the following LPP

Minimize Z = 2x₁+ 2x₂

Sub to

2x₁+ 4x₂ ³ 1

-x₁ – 2x₂ £ -1

2x₁ + x₂ ³ 1 & x₁, x₂ ³ 0.

Solution : Min Z = 4/3, x₁ = 1/3, x₂ = 1/3.

(30)Use duality to solve the following LPP

Maximize Z = 3x₁ + 2x₂

Sub to

X₁ + x₂ ³ 1

X₁ + x₂ £ 7

X₁+2x₂ £ 10

X₂ £ 3 & x₁, x₂ ³ 0.

Solution: Max Z =21, x₁= 7, x₂ = 0.

(31)Use duality to solve the following LPP

Minimize Z =x₁–x₂+x₃

Sub to

x₁ – x₃ ³ 4

x₁– x₂ + 2x₃ ³ 3 & x₁, x₂,x₃ ³ 0.

Solution: Infeasible solution.

(32) Consider the LPP

Max Z = 2x₁+ x₂+ 4x₃–x₄

Sub to

X₁ +2x₂ + x₃-3x₄£ 8

-x₂ + x₃+2x₄ £ 0

2x₁+ 7x₂ – 5x₃ – 10x₄ £ 21 & x₁, x₂, x₃, x₄ ³ 0.

(a) Solve the LPP

(b) Discuss the effect of change of b2 to 11.

Solution: (a) Max Z =16, x₁ = 8, x₂= x₃ = x₄= 0.

(b) Max = 87/2, x₁= 49/2, x₂= x₃ = 0, x₄ = 11/2.

( c) Infeasible solution.

(33)Consider the LPP

Max Z = 3x₁+ 4x₂ + x₃ + 7x₄

Sub to

8x₁ + 3x₂ + 4x₃+ x₄£ 7

2x₁ + 6x₂ + x₃ + 5x₃ £ 3

x₁ + 4x₂ + 5x₃ + 2x₄ £ 8 & x₁, x₂, x₃, x₄ ³ 0.

(a) Solve the LPP.

(b) If a new constraint 2x₁ + 3x₂ + x₃ + 5x₄£ 4 is added to the above LPP, discuss the effect of change in the solution of the original problem.

(c) If a new constraint 2x₁ + 3x₂+ x₃ + 5x₄ £ 2 is added (or) if the upper limit of the above constraint is reducd to 2, discuss the effect of change in the otimum solution of the original problem.

Solution : (a) Min Z = 83/19, x₁= 16/19, x₂ = 0, x₃ = 0, x₄ = 5/19.

(b) Redundant.

( c) Max Z = 113/38, x₁ = 33/38, x₂ = x₃ = 0, x₄ = 1/19.

(34)Consider the LPP

Max Z = 2x₁+ x₂ + 4x₃ – x₄

Sub to

X₁+ 2x₂+ x₃ – 3x₄£ 8

-x₂ +x₃ + 2x₄£ 0

2x₁+ 7x₂ – 5x₃ – 10x₄£ 21 & x₁, x₂, x₃, x₄ ³ 0.

(a) Solve the LPP.

(b) Discuss the effect of change of c₁ to 1.

(d) Discuss the effect6vcof change of (c₁, c₂, c₃, c₄) to (1, 2 , 3 , 4)

Solution :

(a) Max Z = 16, x₁ = 8, x₂= x₃ = x₄= 0.

(b) Max Z 40/3, x₁= x₄ = 0, x₂ = 8/3, x₃ = 8/3.

(d) Max Z = 431/10, x₁= 0, x₂= 21/2, x₃= 11/10, x₄ = 47/10.

(35)Consider the LPP

Max Z = 5x₁ + 12x₂ + 4x₃

Sub to

X₁+ 2x₂ + x₃£ 5

2x₁– x₂+ 3x₃ = 2 & x₁, x₂, x₃ ³ 0.

(a) Discuss the effect of changing a₃ to (2,5) from (1,3)

(b) Discuss the effect of changing a₃ to (-5,2) from (1,3).

Solution :

(b) Unbounded solution.

(d) Max Z = 60, x₁ = 0, x₂= 4, x₃ = 3.

(36)Consider the LPP

Max Z = 3x₁+ 5x₂

Sub to

X₁ £ 4

3x₁ + 2x₂ £ 18 & x₁, x₂ ³ 0.

(a) Solve this LPP.

(b) If a new variable x₅is added to this problem with a column (1,2) and c₅= 7 find the change in the optimal solution.

Solution :

(a) Max Z = 45, x₁ = 0, x₂ = 9.

(b) Max Z = 53, x₁ = 0 , x₂= 5, x₅ = 4.

(37)Consider the optimal table of a maximization problem

		C_j=	3	5	0	0	7
C_B	Y_B	X_B	x₁	x₂	x₃	x₄	x₅
7	x₅	4	1	0	1	0	1
5	x₂	5	1/2	1	-1	1/2	0
Z_j - C_j		53	13/2	0	2	5/2	0

Find the change in the optimal solution, when the basic variable x₂ is deleted.

Solution : Max Z = 28, x₁ = 0, x₂ = 0 & x₅ = 4.

AU Previous Year Question Papers

UNIT – I INTRODUCTION TO LINEAR PROGRAMMING PROBLEM

No comments:

Post a Comment