No.

of Printed Pages : 15 I MTE-12

BACHELOR'S DEGREE PROGRAMME

T-i
Term-End Examination
June, 2010

ELECTIVE COURSE : MATHEMATICS

MTE-12 : LINEAR PROGRAMMING

Time : 2 hours Maximum Marks : 50

Note : Attempt five questions in all. Question no. I is

compulsory. Do any four questions out of 2 to 7.
Calculators are not allowed.

1. Which of the following statements are true and

which are false ? Give reasons for your answer.
5x2=10
The optimality criteria for the maximization
and minimization problems are different in
the simplex method.

If the primal LPP has an unrestricted

variable the dual LPP will have an equality
constraint.

MTE-12 1 P.T.O.
 In an optimal solution of any balance
transportation problem with 3 sources and
3 destinations, there are at least 6 routes over
which a positive quantity is being
transported.
In a two-person zero-sum game, if the
optimal solution requires one player to use
a pure strategy, the other player must also
use a pure strategy.
(e) For any two square matrices A and B,
AB = BA.

2. (a) A toy company manufactures two types of 6

dolls, a basic version, doll A, and a deluxe
version, doll B. Each doll of type B takes
twice as long as to produce as one of type
A, and the company would have time to
make a maximum of 20 dolls per day, if it
produces only the basic version. The supply
of plastic is sufficient to produce 15 dolls
per day (both A and B combined). The
deluxe version requires a fancy dress of
which there are only 6 per day available. If
the company makes a profit of Rs. 30 and
50 per doll, respectively on doll A and B;
how many of each should be produced per
day in order to maximize profit ? Formulate
this problem as an LPP and solve it by
graphical method.

MTE-12 2


(b) Write the mathematical model of the 4

following transportation problem.

Destination
Di D2 D3 Availability
01 5 7 2 25
Origin 02 3 6 5 35
03 1 12 4 40
Requirement 30 28 42

Also find an initial basic feasible solution to

the problem using North-West corner
method.

3. (a) Using simplex method solve the LPP 7

max Z = 2x 1 + 5x2 + 7x3

subject to

3x1 + 2x 2 + 4x3 100

xl + 4x2 + 2x3 5 100

xl + x 2 + 3x 3 5 100

x 1 , x 2, x 3 . 0

(b) Show that the set S {(x, y) : xy x 0, y  0} 3
is not convex.

MTE-12 3 P.T.O.


4. (a) Write the dual (D) of the following LPP 6

(P) Min 2x2 + 5x3
subject to x1 + x2 2
2x1 + x2 + 6x3 6
x1, x2, x3 3 0.

Check whether ( 1 , 1 , 2) is a feasible

19 9 5
solution to (P) and -i , 4 ' 6 ) is a feasible
solution to D. Without solving (P) or (D),
„ 1
check whether 1, 2) is an optimal
solution to the primal problem (P) and
(9 9 5)
2 4 ( is an optimal solution to the
dual problem (D).
(b) Formulate a linear programming model for 4
the maximising player A of the following
game :
Player B
I II III
I 8 2 —3
Player A II 6 5 4
III 0 —8 12

MTE-12 4
5. (a) A manufacturer wants to send 8 loads of 6
his product as shown below. The matrix
gives the distance (in miles) from origin '0'
to destination 'D'

Destination
Origin A B C Availability
X 5 1 7 1
Y 6 4 6 3
3 2 5 4
Requirement 3 3 2 8

Find an optimal transportation schedule for

minimising the mileage, starting from an
initial basic feasible solution by matrix
minima method.

(b) Suppose player A and player B each have 4

two coins, one of Rs. 2 and one of Rs. 5.
Player A and player B choose one coin each.
If the sum of the coin values is even, then
player A wins player B's coin and if the sum
of the value is odd, then player B wins
player A's coin. Formulate this as a two
person game. Also find the optimal
strategies for the two players and the value
of the game.

MTE-12 5 P.T.O.
6. (a) Solve the cost maximising assignment 6
problem whose cost matrix is given by :

A BCD
I 42 30 30 24
II 35 25 25 20
Ill 28 20 20 16
Iv 21 15 15 12

(b) Find all the basic solutions of the following 4

system :

x + 2x2 -I- X 3=4

2x1 + x2 + 5x3 5
Xi, X2, X3

Which of the solutions are feasible ? Justify

your answer.

7. (a) For what values of k are the following vectors 5

linearly independent ?

1 1 k
[21 1 [1(1 , 11.

MTE-12 6


(b) A soft drink company A has two products 5

and its rival B has three products. Both the
companies have calculated the impact of
additional advertisement for any of their
products on the sales of that product and
on the sales of the products of their rival.
The data is given below :

I II III
A I 6 7 15
II 20 12 10

Treating the problem of finding the optimal

advertising strategies as a problem in game
theory, solve the problem by graphical
method.

MTE-12 7 P.T.O.


1... -12
*-11 14) zETrru chi, chTT

HARI 1:rftaTT

"‘ff, 2010

g ickg swi :
71:44.-12 : Arioth AA ±.11-141

04.1 q 2 ti c/ T fewdzT 37-W : 50

: rifw 50Of-47l Trig Ff. I 37ft7TJ 7I 3T. Fi 2 4 7
# 4 Ph w so,t1 3-ff OThi q 470g)(4ej *7. vafrif
ch( 3751*. ItY g/

1. •
1.11-sirtifisid -4 4 -14t-7? at Ai-74 wpm?
5x2=10
dTI( got . ' tf-AR

WT f4fel alf NWOVril -eiii-achtui

:z
TP R iTat isc-R Et-144cci Pi ciA NW-NW t14 t

7/fq aTFEI LPP aTed""U trdT 'c tic

LPP KW TirriWr Wdtti *11

(c) ?WA. 3 tt1c 3 3 am Ttgfm'tif{4-0

1:114FIT t-ardi:rgF 14, 'WTI Wri 6 7TA trU.
fq9.4 t1971W -1711 -WT tfird'e fct
i wIaI t

MTE-12 9 P.T.O.
 •RW'rg--tr-ffi• v-q -4-1Trm ao 'W1:1"•F
*31-gig lifq w Rstrusl tiracbc-4 Ti
anti t alit4 fig oiil ift tirciebeN
ir in

Wald A at B,*rmAB = BA.

2. (a) fg14-4 co-0 '4IFI TI:Ert mall( lifF1 6

'7W TITell-foT m cnit 1171T A, 3 Vrft
m cilit B, B m cbR a m ch
'fizir 61114 4, A M cblt 1;kW rcrr
TFRI tl zifq W4x191 *-4M. TITVRTIT
m chtt (si-K afkiWffri 20
lii-44r 410 I tmrrew a aTrtft .srr-Ai 15
7 4"ziT (A B t-4 ri-Kim() tg li4 4,1itt
In? t Nol-ki mew (B wzbk
q mcbi(*aqivir4. gRcNtl
*TO 6 ATIFT 37-0a1 tf ti zit
A 4 B A ct)K Tr( cb likl: 30
T. 31 50 T. Wf t,car 31fIlWait'9111
"tiff ct.A omit 'ft-dt
err .111-11 ? .414 1:P: mfr LPP Ttt
‘-rwff w11-4R atIT7r0 z1 farq Ta. wlf-A7i

MTE-12 10
 (b) tgo IT:Rzrr Trruitzi 1;4 1-4-{gR : 4

+itic4
D2 D3 ztra-ardr

01 5 7 2 25
13tru 022 3 6 5 35

03 1 12 4 40

3.11-4rWaT 30 28 42

3-1{- 1-1P-14 44 et) fartT 14 TR 'WIRT 305V

arett TiTrff re ql wIr-4R

3. (a) 7WNT isIct LPP c Vf77 : 7

Z = 2x 1 + 5x2 + 7x3

3TRT-*--ditvur wif-o7

3x 1 2X 2 4x 3 100

X1 4X2 -1- 2X3 100

x1 + x 2 + 3x3 100

X 1, x2, X3 0

(b) tgri47 f"W filmclef S {(X, y) : xy 1, x 0, y _ 3

34-41:T3 t

MTE-12 11 P.T.O.
 6
4. (a) -P--i 0 tga LPP W* tt (D) fifes :
(P) 2x2 + 5x3 W' voi-il ebtui *WWWR
741-w xi + x 22
2x1 + x2 + 6x3  6
x l , x2, x3  0.

\Ail TlfA7 fw qzfr ( 1 , 1 , -fl, (P) TT Vriff

3-fr{ 1-9i, 1, -5j), (D) WI IFtird Te t I (I')

7iT (D), WI fa r fiii, 7N -11---A7 -N-

( 1 , 1 , -1-) aTTUTP:Rzif (P) w 7-di TO at

22 , 1 , fl 'at l'FfizzIT (D) W 'MR Sri t zrr

1
9t I
(b) P1 4-ircifigo ao t afti-*--driwt rg m§ A t 4
rc-RtFTW't grgri f0 7f-A-d W---A7 :
fi g
I II III
I 8 2 -3
(5° 11 A II 6 5 4
III 0 -8 12

MTE-12 12

5. (a) LTA' fffqtaT 14-1irut aTcrk dctif q 8 *I 47-41 6
t i 8iTag #rd '0' 14 1 10 044 'D'
(410.14)

"71-M-0-TaT
A B

X 5 1 7 1

Y 6 4 6 3

3 2 5 4

3741471-*77 3 3 2 8

3 rfafT r ITW 3TRTRI.

ATtg ttA 1:11F-#Tgtrr arcil

WT1 trrrd-e 3T-11:It Vff Tlf-A7 I

(b) fisiotil A 3fR ft9C1141 B, TrAT t 4

"C ITRfk1
tl Rittcbi 2T.
7' 5 T. 'Wf rii cm t I fg(Ft A atIT ft9MIs1 B
fit t I zrfq 1.4 Tg fiqc4
Hfr) if trrch---o. figrii41 A fortis? B

Ri ctzhi "Atd t 19 1 I 1
trk TR Rg oi41 B Rictchi Clai t I
-p4fg--.arfw @(-1 ftgdirsql
wa-rr If-Tztt * -14c *rrivi '111.
7

MTE-12 13 P.T.O.

6. (a) Pii-liortg o CINIc1 aTfaT cticii (via aftwim-(1. 6
alg al Trz:R:zrr w1:1-4R I

A BCD
I 42 30 30 24

II 35 25 25 20

III 28 20 20 16

IV 21 15 15 12

(b) ZiTtitc ff WAR : 4

x + 2x2 + x3 = 4
2x1 + x2 ± 5x3 = 5
xi, x2, x3  0

c-TiTrff
*1-4-Trr aTrtit la aTtr4 31/..&gra
I

7. (a) k f*-9.-grrt t 101, 1-icifiga tit i ifuwff: 5

1 k 1
[21 0
11

MTE-12 14


(b) Trrqz ft t1I g ii1 441 A* t 30-1K t at{ 5

31171 40441 B * *ff 3041q t
4041:iii 4 3474 fwA. 1.11- dCkilq T1. fe0:4 at{

arT.4 .strugt ac t few-441- utatafTw

fay 3riTra. 7rd rch q i 1 w4,

I II III
A I 6 7 15
II 20 12 10

1-4Wiff c4 TFRIF
1rt -14 TtrrFrr
7104 "WIT *WWR I