a

- - '.=:tr Progratnming 3.23

j:i-slness Studies
lS. Maximize Z = 400x+ 300y
subjectto : .t+ ), < 200; x ) 20 Y 2 4x; x, Y > 0

"r. \{arimize Z = 10,000x+50,000Y

subjectto:10,000x+40,000y < 1,60,000; x>- 4; y < 2; x,y> 0

subject to : 90-t, + 65xr+ 45x.' > 60; 30x, +85't, + 70x, > 60; \ + xz + x3 = li xt,x2,4 2 0

: . THE GRAPH OF A LINEAR INEQUALITY

.. >0
lted in the preceding section, linear programming problems involve the use of linear
- -..1ities. In this section, we will see how to draw
graphs of linear inequalities in two
.1- and y. In Section 3.7 we will use these graphs to solve linear programming
involving two decision variables.
points (x, y) for
;::oh of a linear inequality in two variables x and / is the set of all
: :he inequality holds. The procedure for graphing a linear inequality is as follows :
l. Graph the corresponding linear equation, a line. This is done by finding any two
. ,,,t the line and drcnuing a straight line through them. For convenience, we choose the
+,-r00; - ':i-i s0 that eqch is on an axis.
>0
| :Jhoose a point P not on the line. Normally, this point is taken as the origin as long at
,. .:tt lie on the line. kst P to see whether P satisfies the inequality'
';..r.,xr)0
j. : rhe coordinates oi the chosen point P satisfy the inequality, then all points on the
: ;: of the line as the point P satisfy the inequality. If the coordinates of the point P do
x.y20 rhe inequality, tien all points on the opposite side of the line from P satisfy the

1et us consider following examples'

13, Graph the linear inequality : 2x +.v < 10

,rst r.ve graph the corresponding line : 2x + y = 19.

-:,:y.finding anytwo points on this line. For convenience, we choose two points so
: rn an axis. Thus whenx : O, y = 10, and wheny : 0, x : 5. We now know two
--.:1ine, namely, (0, 10) and (5,0). The line joining (0, 10) and (5,0) represents all
:eiisry the equation 2x + /: 10. For its graph, see Figure 3.2 (a).
-"ich side of the line satisfies the inequality, the coordinates of the origin are
.,'>0
into the inequality :

2 (0) + (0):0 < 10,

is true. Therefore all points on the same side of the line as the origin satisfy the
xt225 itv. The graph of the inequality is the shaded region of Figure 3.2 (b)'
 ::

I
11/

,A4o themailcs
for Bus ines,tStttdi
e ;L

Fig.3;2

Exumple 14. Graph the

linear inequality : 4x + 2y > ea.
;:,;:i.
"rs ,Ils +'rr t' : 60.
2y:60
+ ly
For its
For tra^h we
ils graph, r,.^ find
c.--r
tv .
1,s *,i ;;;;i,'{",ifl?:'#l3ji:::
15. Thus (0, 30) and
i;, ni",""-*
65, 0) -.,^"'-1Y'1"*t .,y3,
points on 'the
v:0, !:30 and wheny = 6, :
r1
Of *^.^_.-
represenrs
are tlre two
uf l porr, ,-,rra
t linear equation. The
line joinirC (0, 30)
.,n

1,,.t. ^\ qrv! oqrrDal urs equatlon

4x + 2y: 60. For i ;;;
W'e now substifute
the- < ;l'::,1ffi:fT ::,: :i-:';;';"#::"-
:oordinates of the origin " '*
in the inequah;, #;3 il:
4(01+ 2(0) = 0 > 60.
which is not true' Since
(0' 0) does not qatissz
rine rrom (0, 0) satisry,h" th1 urequarifi all points
*;;;;. il.J1; i, trr.
on the opposite side
.rrui"J;;;, of the
shown in Figure 3.3 (ut.

Fig.3.3
So far we have considered
only one linear inequality
linear inequalities. The at a
u time. Nc
Now we consider a systep
grapn or a -;;:::::1" ']1* " c:
coordinates,;;,,;J",sJ;'#,T
:f :1il'Jl:l' *. set o r au o";;;";; -
il.r r ffiillil[.', ",

=
L :"
 3ttsiness Studies -. - Programming 3.25

; ::mple 15. Graph the following system of linear

inequalities :

3x+3v < 36
5x+2y < 50
:i;rr;;,.irl \\''e first graph the two lines :

3-r-+ 3r,
= 36
5x+2-y = 50
1rs are shown in Figure 3.4 (a). The graphs of the two linear inequalities are shown in
": ih), and the desired solution is the cross-hatched region.

'rrrning (0, 30) and

see Fig. 3.3 (a).

,x
..pposite side of the
in Figure 3.3 (b).
Fig.3.4

- o. Graph the following system of linear inequalities :

2x+4y < 40
5x+2y<50
x>0
v)0
:,; :uSt shade in all points that satisfy
-;;-ualities (i) - (iv). This can be
------>.r frsr drawing the graphs of the four
:;ualities. Once these lines have
r can mentally identify the four
::" j:;..:inq inequalities (l) - (iv) and
consider a system of -': :.ction of these regions. The
':
set of all points whose - :s shaded in Figure 3.5. The
lliltLrl n (rrr) and (iv) are satisfied by the
11lllrxl " . - - riined the graph to the first
Fig.3.5
llllflr[
I 3.26

3,7 THE GRAPHIC METHOD OF SOLUTION OF I.INEAR PROGRAMMING

PROBLEMS

We rvi11 now present the graphic merhod for solr,,ing linear

involve only two variables' This method is based on a theorem,
Matltemqtics ./br Business Snrdit

prograrnrning prr-blerns it-.,

calleci extrente poirtt tlteot.;,
which states as follows :

Extreme Point Theorem. An olttitttuttt solutiort b a linear progrctnrnting

problent, if it e.ri:
occltrs at one of the corner (or extrente) points ,f'llte ctreo- o./
/'eusibte regic,,.
The graphic method involves three basic steps.

Step l.TheJirst step irt the graphic inethotl is to derenuine tlrc urea o.f'.ft:ctsihle region.
T:
crrea vvill contain tlre .set ttf'all ytoints thctr .sinnritrtneott'!1, sotis.f\, all t-,onstraittts ('inclttti
. -
no n-n egativ e re,s tric' ti o n s ).

Step 2' l{ote the coorclinutes of' eaclt corrler

Ttoint of the .lbosible region artd substitute :
coorclinates oJ'tlte c"orner points into the objec:tit,e
function.
Step 3' The optimum 'golution occLrs in a maximizatictn cuse at the corner point yielcting : ,
largest value oJ'the objective .ftmction and in a ntinimization case at the c:ornet- point tiejci -
the smallest value of the objective .function.

Example 17. Solve the following Zp problem by the graphic method.

Maximize Z =3x+4v
subject to the constraints:
2r+2y<80
2r+4y<120
'f, ,1' > 0

Solution. First we find the feasible region which

consists of the set of all points whose coordinates
simultaneously satisfy all constraints including
non-negative restrictions. Applying the techniques
of Section 3.6 to the above system of inequalities
leads to the feasible region shown in Figure 3.6. 40

The corner points of the feasible region are c (0. 30)

O (0, 0), A (40,0), B (20, 20) and C (0, 30). Note
that the coordinates of the point B have been
obtained by solving 2x + )y: 80 and 2x + 4y:
120 simultaneously for x and y. The values of the

il
objective function at these corner points are o (0. 0) .1(.+0, 0) 60

summarized in the followins table :

Fig.3.6
 : .rrrc-r.! SUdies Programming 3.27

R AMMING ,-,-tnter point Value of the objective function

(.r,
-t,) Z:3x+4y
-
- '-'l'cblems th;rt
E-.
o (0, 0) 3(0)+4(0):0
f,- . lt-)iltt theoretn,
-1 (40, 0) 3 (40) + 4 (0): 120

' tr' ii-fi erists' B (20.20) 3(20)+4(20): 140

c (0, 30) 3 (0) + 4 (30): 120

rir',-jrlulr value of Z is thus given by the coordinates of B. Hence optimum solution occurs
:-ie
gion. This
- :nd ), : 20, resulting a maximum value of Z as 140.
re
=
',.rtrtLs (int'iuding

i-;u,nr:,18. lVlaximize Z=l0x+6v

.;,tcl strbstitttte the
sr"rbject to the constraints:
3x+y<12
2r+5v<34
,-,ctint
.yielding ilte -t,y ) 0
t ller point Yielding
,,, .-. " :'_erhod. lDelhi Univ. B.Com. (H) 19841
,,ririlirlLrr&li, ' : ; :-tfst plOt the lineS :

- -
,i = 12 ...(i)
- -:r = 34 ....(ii) t2

line (i) meets the axes at the

c (0, 34ls)
and (4, 0), and the line (ii) at
r17. 0). The shaded arca in
n s the feasible region.

.nts of the feasible region are o (0, 0) A (1.0)

. tl B (2,6) and C (.0,3415). Fig.3.7
:he ob_jective function at these
Ji summarized as follows :

Value oJ'the objective function

Z: 10x + 6v

10(0)+6(0) :0
10 (4) + 6 (0) :40
10(2)+6(6) :s6
.4(40, o)
l0 (0) + 6 (341s): 2041s
Fig.3.6
:

I
{
I
;
i
3.28
Since objective function is one we wish
1,: 6, yielding the maximum value of Z
Example 19. Solve gxaphically:

Maximize
as 56.

Z = 50r+30):
Matltemotic,s.fbr.Busines,s Stuclte,

to marimize, the optimum solution occ,rs

at,r .= 2 ar.

I subject to the constraints:

2-r+.r' > 18
_r+y > 12
3r+ y < 34
.t, ,1, > 0

lDelhi Lrniv. B.Com. (II) 20091

Solution. The feasible region satisfying all
the v
constraints including non negative restrictions
is shaded in Figure 3.8. The corner points c (0, 34)
of
the feasible region arc A (6, 61, A i l,t1,
C (0,34) andD (0, 1g). Evaluating Z atthese
points, we obtain

Z(A)= 50x6+30x6 =4g0

Z(B)= 50xll+30x1 =580
Z(C)=50x0+30x34=1020
Z(D)= 50x0+30x18 = 540

Thus the maximum value of Z is 1020 and it

occurs when x: 0 and v:34. e
+12
34/3
Fig.3.8
Example 20' Solve the folrowing linear programming probrem
graphically

Maximize Z = 4x+6y
subject to the constraints:
x+y - 5
x>2
v14
r,J ) 0
fDethi Univ. B.Com. (H) 1992, 2003 (ModiJied)l
Solution. Notice that the first constraint x + y:
5 is an equality. This meets the axes at (i.
0) and (0, 5). The equation x : 2 correspondirg
to the construin, , > 2 is the rine para[e1 i:
y-axis at a distance 2 and the equation y :
4 conesponding to the constr ainty <4 is the
parallel to r-axis at a distance 4. A feasible l*.;
point (i, y) miist hur", > 0,1 > 0, must
the line x + y:5, must be on or right of rie t:
x: 2 and onor below the line y : .Hence th;
 - ". )r Programming 3.29
i,i.rl/?e.ss Studies
:rr :ie region is the dark line segment AB as
-:i.l1.s at x:2 and - ,,:.) in Figure 3.9. Thus Z is maximum at
-: :,1the two extreme points of AB. The
--:rates of A are (5, 0). To fincl
B, we solve
': :quations x + y 5 and :
: - ::neously, which gives r -- 2, y =x3. 2
. - -,ting Z atthese points, we obtain

Z(A)=a(s)+6(0)=26
Z (B) = aQ) + 6(3) = 26 I (5, oi
Fig.3.9
B.Coru. (H) 20091
- :-,: ihe maximum value of Z, subject to the
- -*,;rts, is 26 and it occurs rvhen x : 2 and v = 3.
; ;",::le 21. Solve graphically :

Minimize Z =200xt+400x,
subject to the constraints:
xt+x2>200
l3
-x,+lx,)100
4' 4'
l1
I0 s '
-xr*-x"<35
X1,X2 >0
B(11,1)

" At2 lDelhi Univ. B.Com. (H) 20il1

-r-t 3 'r'-,'i':" ':' The feasible region satisfying all the constraints including non-negative restrictions
* '--;- ,n Figure 3.10. The comer points of the feasible region u..,n
Fig.3.8
1too, too;,
j and C (50, 150). The values ofthe objective fun-ction at these.o.n., B
r,tr; * -::J in the following table:
: points are

The Value of the

Objective Function

Z=200\+400x,
200 (100) + 400 (100) = 60,000

200 (250) + 400 (50) = 70,000

W.:. )003 (Modiieill
200 (50) + 400 (150) = 70,000
i r' -:.: ihe axes at (5.
200 350
1 - .. ti.re line parallel to
Fig.3.10
E,i :i1.1t.r'< 4 is the line e minimum value of Z is 60,000 and it occurs when
t-.r>0,mustlieon x, = 100 and xz = 100.
E :-,e r' : 4. Hence the
3.30 Mathematics for Business Studies

Example 22. Using graphic method, find the maximum value of

Z = 7x+lOy
subiect to the constraints:
.r+I < 30,000
y < 12,000
x > 6000
x>-y
ir, -)' > 0

lDelhi Univ. B.Com. (H) 1990, l99q

Solution. The shaded portion in Figure 3.11 represents the feasible region. The comer poinr
of the feasible region are A (6000, 0), B (30,000, 0), c (18,000, 12,000
D (12,000, 12,000) and E (5000, 6000).
I
Evaluating Z at these points, we obtain

Z(A) = 7(6000) + 0 = 42,000 x

\,/.1/
Z(B) = 7(30,000) + 0 = 2,10,000 ; \tr,/
.l),,\C , = rli'nr,
Z(C) = 7(18,000) + 10(12,000) = 2,46,000
Z(D) = 7(12,000) + 10(12,000) = 2,04,000 l)

Z (.8) = 7(6000) + 10(6000) = 1,02,000

OA
Fig. 3.11
Thus the maximum vahre of Z is 2,46,000 and it occurs when x : 18,000 and y : 12,00[t

Example 23. An oil company requires 12,000,20,000 and 15,000 barrels of high-gra;:
medium-grade and low-grade oil, respectively. Refinery I produces 100, 300 and 200 bari::
per day of high-grade, medium-grade and low-grade oil, respectively, while refineq.
produces 200,400 and 100 barels per day of high-grade, medium-grade and low-grade : .

respectively. If refinery,4 costs T 400 per day and refinery B costs t 300 per day to ope
how many days should each be run to minimize cost while satisfliing requirements ?

Solution. A table can help form our equations and inequalities :

ReJinerl High-grade Meclium-grctde Loty-grade

A 100 300 200 { 40r.

B 200 400 i00 T 3(lr,

Minimum requiremenis 12,000 20,000 15,000

 -l:r-iure.ss Studies ,:ear Progrommirug 3.3 I

,: x and;; denote, respectively, the number of days refinery I and refinery B should be run. Then
: appropriate mathematical formulation of the problem is :

Minimize Z= 40Ax +300y Objective function

subject to the constraints:
100x+200y>12,000 High - grade ccnstraint
300r+400y > 20,000 Medium - grade constraint
200x+100y > 15"000 Low - grade constraint
.r,.v ) 0 Non - negativity constraints
[ ,,t. tH) 1990, 19961
: - :,\\ ,ise gfaphic method to find the solution of the
Fr ..,r00.
.,re comer PotntS
*: . rroblem. Again, we first graph the constraints. The
I i2,000).
"-
150

-.: portion of Figure 3.12 sliorvs tire feasible region.

: : - i'ner points of the feasible region are .4 ( 120, 0),
r i0) and C (0, 150). Note that tlie coordinates of
..1 r
: r.t B have been obtained by solving the equations
- 100,v: 12,000 and 200x + 100 y = i5,000
-- - -.'reously for x and y. It remains only to evaluate
';: .^: of the objective function at each corner point.
60
i0
i ' r: Z at these comer points, we obtain

-- -{) = 400(120)+0 = 48,000

-- .J) = 400(60) + 300(30) = 33,000 200t3 75
f is. ,1.11
: -- l) = 0+300(150) = 45,000 Fig.3.12
I and.]' 12,000'
-: ..: .3 minimum value of Z is 33,000 and it occurs
] :'::els of high-grade' , ::- =50andy:36.
t -:rl0 and 200 banels t 2-1. The standard weight of a speciai purpose brick is 5 kg and it contains two basic
t . . u'hile refinerY B :-s .8, and B, B, cosis T 5 per kg and B" costs T 8 per kg. Strength considerations
p::3 3nd low-grade oii' ,:t the brick contains not more than 4 kg of B, and minimum of 2 kg of Br. Since the
[ : 'Per daY to operate' :,rr the product is likely to be related to the price of the brick, find the minimum cost
tg ::quirements ? .:tisfying the above conditions.
fDelhi Univ. B.Com. (H) 1997, 20081

n,--.;,ie Cost per da

x, : the amount of ingredient ,8, (in kC) used in the brick
t 400
,r, : the amouilt of ingredient B, (in kg) used in the brick
t 300
=:lropriate mathematical formulation of the problem is :

.: i.l
 3.32
Mathematics for Business fr{
Minimize (Total cost) Z = 5xr+8x2
subject to the constraints:
x1*x2=J
xr34
xr22
\,x220
we now use graphic method to find the solution
of-the above problem. The graphing procedr;
the same as used previously in Example u
20. The feasible ,.gio, i, ,t . dark line segment,,l;
drow n in Fi3ure 3 'i' 3 . To f,rd tre coordinabs :!
o fl, we solve-the equations x, * xr: 5 and .r- =
l
:3,
gives x, xz= 2. The coordinates of B are
;'#*l"TJ:"1*r'/hich io, s;. rruuuting Z at ttt-*
Z(A)=s(3)+8(Z;=31
z(B):s(0)+8(s1=46
Thus the minimum value of Z occurs
at A (3,2). Hence the
optimum product mix is : 3 kg of ingredient
jngredjent.B, so as
.8, and 2 kg of 2
to achieve the minimum cost of { 31.

Example 25. A box manufacturer makes Fig3.r3

small and large
boxes from a large piece of cardboard.
The large boxes require 4 sq. ft. per box,
small boxes require 3 sq' ft' per box. while th:
The manufacturer is required to make
at least three larg=
boxes and at least twice as many
small boxes as large boxes. If 60 sq.
ft. of cardboard is r
stock' and if the profits on the small
and large boxes are T 2 and { 3 per
how many of each should be made box, respectiverr.
in order to maximize the totar profit (use
method). ? graphi:

solution' Let box manufacturer make

x large boxes and y small boxes.
Then the appropriate mathematical
formulation of the problem is :

Maximize (Total profit) Z =3x+2y

subject to the constraints:
4x+3y < 60
x>3
Y>2x
x'!20
' , Business Studies " '!t'ctmming J.J J

portion in Figure 3.14 represents the feasible

--: .orner points of the feasible region are A
: il)and C(3, 16). Evaluating Z.atthese points,
c(3,16)

_l .ri = 3(3) + 2(6)

= 21 B (6, t2)

-- Bt = 3(6) + 2(r2) = 42
_::phing procedure is ,- ,l) = 3(3) + 2(16) = 41
.rne segment lB as

-.rr:5 andxr-2 -:: see that the maximum profit is { 42 and it

:r aluating Z at these rh r : 6 and y : 12. Hence the manufacturer
rke 6 large boxes and 72 small boxes.
Fig.3.14
+ 16. Alpha Heavy Engineering Company
=':thmovers and harvesters. Each product passes through two assembly departments
rl!
ll
{ , i-.ich, respectively, have 300 hours and 320 hours of available time for the next
:. ,duction. Each earthmover requires 20 hours in department A and 40 in deparlment
h=2 narvester requires 30 hours in department A and 20 in department -8. The two
::: tested in a third department. Each earthmover is given 60 hours of testing and
20, and, as per the agreement with the labour union, the total labour hours
4
: testing cannot fall below 270. The management has the operating policy of
:g at least one harvester for every two earthmovers produced. A major customer
Hg.113
.n order for a minimum of 5 earlhmovers and harvesters (in any combination,
.,:,r next month, and, so, at least that many must be produced. Each earthmover
:. per box, while the
:- ,.: of { 10,000 and each hawester { 8000. lDelhi LIniv. B.Com. (H) 20021
at least three large -
:t r denote the number of earthmovers and y denote the number of harvesters
:, of cardboard is in ien the appropriate mathematical formulation of the problem is :
::: box, respectivel)'.
? (Use graphic ',iarimize Z:10,A00x+8000y
:ibiect to the constraints:
20x+30y < 300
40x+20y <320
60x+201;>270
y>xl2 or x-2y<0
r+v >5
.Y. l > 0

::ea in the Figure 3.15 represents the feasible region. The comer points of the
t27 21 \ /32 32\ /e -\ I: ^\
: rrel [; u l;'l0,J'c \r'')andD l;'J' EvaluatingZatthese
",J
il 3.34
Mathematics for Business Studi..

Z(A) = 10,000(27l7)+8000(2jt14) s4,000 t6

=
Z (E) = 1 0, 000 (32 / 5) + 8000 (3 2
fi}i) = 89, 600 :7rl
Z(C) = i0,000(9/2) + 8000(7) = 1,01,000
rir
Z(.D) = 10,000(3/2) + 8000(9) = 87,000

Thus the maximum value of Z is T 1,01,000 5

and it
g
occurs when x -; ancl r.= 7.

Example 27. A firm assembles and sells rrB'r.tr'

two
motors A and.B using four resources. rhe produ*ion process car
flt:Lfa";r"i.?,:,3:"ld
Resources
Capaciq,per Month
1 Motor unit shop
400 Type A or 250 Type B units or a:,
Iinear cornbination of the rwo
ll Type A gear and drive shop resource
175 Type I units
III Type B gear and drive shop resource
225 Type B units
IV Final assembly resource
I
200 Type units or 350 Type B unirs
.-
any linear combination of the two
Type A units bring in a profit of r 90 each and Tlpe B units t 60 each.
as a linear programming problem Fonnulate the aborr
to maximize profit and solve the same by graphic
methoc
fDethi Univ. B.Com. (H) 2003,2009i"
solution. Let x and y denote the number
of outboard motors of rype A andType
respectively. Then the appropriate mathematical formulation J
of the problem is :

Maximize Z = 90x + 60y

subject to the constraints:
xv
+OO
n
iSO =
| or 5.r + gy *< 2000

x<li5
y<225
irv
,OO
o
:SO =
I or 7.r + 4.v < 1400
r,.)/ > 0
 3.3 5
u Business Studies
- -'. -;, Pt'ogramming

350

250
225

Fig.3.16
-1.15
area in Figure 3.16 represents the feasible region. The corner points of the feasible
car- -.-: O (0, 0),1 (175, 0), B (175, 17514), C (800/9, 175019), D (40,225) and E
(0,225).
: :..Juction Plocess
Z at these points, we obtain

per Month z(.o) = e0(0)+60(0) = 0

Tlpe B units or Z(A) = 90(17s)+60(0) = 15,750
of the two Z(B)= 90(l7s)+60(175 l4) =1s.375
Z(C) = 90(800/9) +60(1750t9) =19,666.67
Z(D) = 90(40) + 60(225) = 17,100
Z(E) = 90(0) + 60(22s) = 13,500
or 350 TYPe B units
of the two
-',.:rum value of Z is t 19,666.67 and it occurs w-hen x: 800i9 andr: ll5Al9.
Formulate the
It. \ carpenter has started a workshop in which he manufactures handcarts. Each
satne bY graPhic
-: a frame and two wheels. A frame uses 3 hours and a wheel 2 hours of labour
B.Cottt. (H) 2003, ' .trs per week are available. The carpenter wants that he should manufacture at

of TyPe ,4 and TYP'

t
during a week. The cost of frame is 500 and that of a wheel is 200. t
':,.: as a linear programming model and using graphic method, determine an
problem is :
p1an. lDelhi Univ. B.Com. (H) 20041
,: be the number of frames (or handcarts) and y the number of wheels produced
-::1 lhe appropriate mathematical formulation of the problem is :

- 8y < 2000 ,l-:rmize Z = 500x +2001'

,,:-3Lt to the constraints:
3x+2y <90
r>10
x+4Y<1400 l=2x
x,.Y >0
I
3.36
Mathematics for Business Studie:
The dark line segment ,1_B represents
the t-easible region.
The coordinares of the.poinis,4
and A u.. tiO, 20) and
(:417., i 80i 7) respectii.ety,. u.
Evaluatinf ihe ob;ectio,e
function at tirese points, we obtain
ZIA) -- 500(10) + 200(20) = 9000
z(B) = 500(90i 7) + 200(180t7) = 81,000/7
: 11.571.43

Thus the minirnurn value of Z is t 9000 and it occurs

rviren x - l0 and t: : 2{).
Fig.3.I7

3.8 SOME EXCEPTIONAL CASES

In the preceding section, we solved some linear programming
problems using graphic methorl
such that in each problem a unique optimum solution
was obiained. These problems may be
called "w-ell behaverf'problems. However,
there may be situations where an zp problem
no solulion or nlore tiran one oprimum solution has
or evcn an unbounded solution.
rnfeasible solution' Sometimes, the system
of constraints in a linear programming probler:
has no point u'hich satisfies all the
uirtr. ln such cases, the linear programming probien_
"onut
is said to have no feasible solutirn or
in/bas;ibte solution. rne rouowing
example illustrates ,1;
solurion.
casc of inteasible
a dlsl\A^
5
Example 29. Maximize MC
Z = 4r + Z,
subject to the constraints:
2.r + 3r., < lS
x r--y) i0
x,l'> 0

Solution.It is clear liom Figure 3.lg that

there is
no poinr in the i'irst quadrant which
satisfies both
the constraints. Jn other words. the
set o1. points
satisfying one constr-aint includes ,on.
points satisfying the other. Thus the
if ,h.
given Lpp
has no feasible solution.

Fig.3.I8
 -'.,,i ress Snrdies Progromming ).J I

r..: unded Salutions. Whenever a linear programming problem has an unbounded feasible
1:: - ihat is, it cannot be contained in any circle) and the objective function is one w-e wish
- -..:nize, then the problem has an unbounded solution. That is. given any value of the
:m 5-
"e f unction Z, a feasible solution with a greater value of Z can always be found. To
- -::;'. consider the following example.
;-:-rq j,/e 30. Maximize Z = I5.t + z5:'fu1ccUq poq &rttnct li6+-irn;.,lyZ--
subject to the constraints: ?o.llw. fu an,,bgrr^rt6:g*1,sll.a-,
2r +.r' -> -lW
7

"r +.rr ) 5
2x+5y>16
r,-Y > 0
Ftg J lr
lDethi Univ. B.Com. @ryl
.'r.,.r.,r. The feasible rcgion satislying all
: . :>rrsints including non-negativity
't:r

-. :: graphic method li, .* - ,toS is shaded in Figure 3.19. The

: ,:: f roblelns may be ::r... - ; region is unbounded. The corner
'- .':" LP problem has r - - the feasible region arc A (.8,0), B
...1r)11, - -. l. 3) and D (0, 7). Evaluating Z at
' linmiilg probleni :r:r ,r : ::tis. We Obtain
-
:- Jr1'nming probiem zt.1) : 16(8) + 2s(0) = 128
: r:rD1e illustrates the ztB):16(3)+2s(2)=e8
-.9^ ZtC):16{2)+25(3)=191
ZtD):16(0)+25(7)=175

" , - :-,nclusionisthatthemaximumvalueof Zisl11.Thisis./alse! Infact,thereare

rltr::':-: -rmber of points in the feasible region where the value of the objective function is
rlnr,'.; '-.:. ihis value i.e., there is no lirnit to how large the objective function can become.
'''r:r"
. :: the problem has an ttnbounded solution.
u.#huur":.. Optimum Solutions. ln iinear programming problems, situation may arise when
ll|liLrl:' :
.-: possibility of more than one optimal solution. In such a situation, we say that there
,iml"'
* , - 'r- solutions to the problem. Two conditions need to be met in order for multiple
lll ., . - r :,-r erist :
- i rtective function must be parallel to a constraint which forms a boundary of the
: ._;.11€ region.
. . : : :,nstraint must form a boundary of the feasible region in the direction of the optimal
9
- rment of the objective function.
Fig,3.18 ""r' - ::: illustrated r.vith the help of following example.
I 3.3 8

Exumple 31. Maximize

Z = 4r+3y
Mathentatics for Business 5...

subject to the constraints:

3x+4y < 24
8x+6u < 48
1( 5
y< 6
x,! 2 0

[Delhi Univ. B.Conl (H) I

solution' The shaded portion represents the feasible
region as shown in Figure 3.2t)
c orner p o int s o r th e r.;
E';;I;ffi ." J'i.,"fi i] i',;:il:;
i ;: Zfr;,'L'&;, :
, (0, 6). Evaluating the objective function at these points, *. ottuin ;\,.:

Z(O) = 4(0)+3(0) = 6

Z(A):4(s)+ 3(0) = 26
Z(B)=a(s)+3(4t3):24
Z(C) = 4(24 t7) + 3(24 /7) : 24
Z(D) = a(0)+3(6) = 1g

Thus the maximum value of Z is 24 and

it
occurs at two corner points, B and C.
In fact,
this maximum value also occurs at all points
on
the line segment joining B and, C. Thus
we have
an infinite number of optimal solutions.

The reason that this problem has multiple

solutions is that the objective function Z: + jt
has the same slope as the constraint line gx
+ 6y:4g, which fo,.,,].; u boundary of the 4x
feasiblr
region in the direction of optimal movement
of the objectiu" t n"tron.
Redundancy' A constraint in,a, given linear
programming probrem is said to be redundant
the feasible region of the problJn ,"*uin, d
,r.lianged ui a"iJrg trrat constraint.
The following example illustrates the case
of redundancy.
Exunrple 32. Minimize
Z :6x+l\y
subject to the constraints:
2x + 1' (0.[t, ekye,l (vu.fun )-
-= ]o
x>6
1:22
x,!>0
 . "..-- Ptogramming 3.39
Business Studies

-, ' * r,r/r. The feasitrle region of this problem is

, -: - rr.i Figure 3.21. Obviously the constraint
, 10 is redundant as it does not affect the

qir. B.Com. (H) 198n

n in Figure 3.20. The
ll C (2417,2417) and fig.3"?l

EXEffiCISE 3.2

-., :lain the graphic method of solving a linear progratmning problem.

:ase of linear progranrming prc,blems, what is a feasible solution and an inf-easible solution?
r'=6 ..cribe each giving an imaginary graph. lDelhi Univ. B.{owr" (I{) 2#{}3}
: ,.:1ain how you u,ould identifii the cases of redundant constraint, no solution, multiple soiutions
- : unbounded solution from the graph of linear programming problems involving two variables.
',: a rough sketch ofeach case. lDelhi Uniu B.Com. (X{) 19911
" - ,,.r graphically a situation when an ZP problem has :
t
.J.. :ro solution, (ii) an unbounded solution, (ili) multiple solutions.
\t.
\'+ lDelhi Univ. B.Com. GI) 20051
-
do you understand by (l) infeasibility and (ii) unbounded solution? How would you identify
168 't
,. one of these in graphic
: solutiorr to linear programming problems'/ Draw a rough sketch for
Fi:. -r,l0 :,-i. one. lDelhi(Jrtiv'. B.Cont. (fd) 20121

E,< runction 7:$+3t : ih that the following problems have no feasible solution ;

r r,:,rindary of the feasible

,., \{arimize Z =l5x+20y
t: subject to : -{+ y > 12; 6x +9y < 54; l5x+10y < 90; -r,y > 0
L -:id to be redundant ri -r Maximize Z = 4x+3);
h": constraint.
subjectto : -r+ y 3 3; 2r- y < 3; r >,1;,t,y > 0
-:,n.that the tbllowing problems have multiple solutions.

\{aximize Z =6x+4y"
I.-r (rrrrW) subject to : -r +,y l 5; 3x + 2y ! 12; x, y > 0
-1 Minirnize Z =l2x+9),
subjectto : 3r + 6y >- 36; 4x+3y > 24; x +y < 15; "y,y > 0