Q: A feasible solution to an LP problem

A feasible solution to an LP problem belongs to the feasible region. Feasible region is the set of all the points that satisfy the problem's constraints including inequalities, equalities and integer constraints.In the above figure, blue region is the feasible region. All the points in this region are feasible solutions or feasible points which satisfy the given constraints( 4x+3y\leq 480 and 2x+3y\leq 360 )

Question 1

Consider the following L.P.P.Maximize  Z=3x+2y Subject to the constraints x+2y\le 10 3x+y\le 15 x,y\ge 0 (a) Draw its feasible region.(b) Find the corner points of the feasible region.(c) Find the maximum value of  Z .

Accepted Answer

(a) Z=3x+2y  ..........  (i) subject to the constraints  x+2y\leq 10 3x+y\leq 15 Convert these inequalities into equations x+2y=10  .........  (ii) 3x+y=15  .........  (iii) From  (ii) , we get x=0\implies y=5  and  y=0  when  x=10 So, the points  (0,5)  and  (10,0)  lie on the line given in  (ii) From  (iii) , we get the points  (0,15)  and  (5,0) Let's plot these point and we get the graph in which, shaded part shows the feasible region.(b)Lines  (ii)  and  (iii)  intersect at  (4,3)  and other corner points of the region are  (0,5), (5,0)  and  (0,0) .(c)To find the maximum value of  z , we need to find the value of  z  at the corner pointsCorner points         z=3x+2y (0,0)                               0 (5,0)                              15 (0,5)                              10 (4,3)                              18 Thus,  z  is maximum at  (4,3)  and its maximum value is  18 .

Question 2

A company manufactures two types of toys  A  and  B . A toy of type  A  requires  5  minutes for cutting and  10  minutes for assembling. A toy of type  B  requires  8  minutes for cutting and  8  minutes for assembling. There are  3  hours available for cutting and  4  hours available for assembling the toy in a day. The profit is  Rs. 50  each on a toy of type  A  and  Rs. 60  each on a toy of type  B . How many toys of each type should the company manufacture in a day to maximize the profit? Use linear programming to find the solution

Accepted Answer

Toy  A \quad  Toy  B   \quad Time in a dayCutting time 5\ min 8\ min 180\ min Assembling time 10\ min 8\ min 240\ min Profit 50 60 Assumed quantity x y Profit function  z = 50x + 60y 5x + 8y = 180 A B x          0 36 y 22.5     0 x \geq 0, y \geq 0 5x + 8y \leq 180 10x + 8y \leq 240  or  5x + 4y \leq 120 5x + 4y = 120   C       D x   0 24 y       30 0 Corner point z = 50x + 60y At  O(0, 0)                  0 At  D (24, 0) 1200 At  E(12, 15) 1500 At  A(0, 22.5) 1350 Hence the maximum profit is  Rs. 1500  at  E(12, 15) .

Question 3

a) Minimize and maximize Z=x+2y , subject to the constraints x+2y \ge 100 2x-y \le 0 2x+y \le 200 x,y \ge 0 by graphical method.b) Prove that

∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ b + c b c a c + a c a b a + b ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣

=4abc

Accepted Answer

(a) Z=x+2y , subject to the constraints x+2y \ge 100 2x-y \le 0 2x+y \le 200 x-y \ge 0 by graphical method.On solving equations 2x-y=0 and x+2y=100 we get point B(20,40) On solving 2x-y=0 and 2x+y=200 we get C(50,100) herefore Feasible region is shown by ABCDA The corner points of the feasible region are A(0,50), B(20,40), C(50,100), D(0,200) Let us evaluate the objective function Z at each corner points as shown belowAt A(0,50), Z=0+100=100 At B(20,40),\ \ Z=20+80=100 At C(50,100), \ \ Z=50+200=250 At D(0.200),\ \ Z=0+400=400 Hence, Maximum value of Z is 400 at D(0,200) and minimum value of Z is 100 at A and B . (b) Consider,

∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ b + c b c a c + a c a b a + b ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣

=(b+c)

∣ ∣ ∣ ∣ ∣ ∣ c + a c b a + b ∣ ∣ ∣ ∣ ∣ ∣

-a

∣ ∣ ∣ ∣ ∣ ∣ b c b a + b ∣ ∣ ∣ ∣ ∣ ∣

+a

∣ ∣ ∣ ∣ ∣ ∣ b c c + a c ∣ ∣ ∣ ∣ ∣ ∣

=(b+c)[(c+a)(a+b)-bc] - a[ab+b^2-bc] + a[bc-c^2-ac] =(b+c)a(b+c+a)-a[b(b-c+a)]+a[-c(-b+c+a)] =4abc Hence,

∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ b + c b c a c + a c a b a + b ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣

=4abc

Question 4

Solve the following Linear Programming Problems graphically:Minimise  Z = x + 2y subject to  2x + y \geq 3, x + 2y \geq 6, x, y \geq 0 .

Accepted Answer

Given objective function is  Z=x+2y We have to minimize Z on constraints 2x+y\geq 3 x+2y\geq 6 x\geq 0,y\geq 0 After plotting the inequalities we got the feasible region as shown in the imageNow there are two corner points  (0,3)\ and\ (6,0)  lying on same line  x+2y=6 Value at corner points are : Corner Points Value of  Z=x+2y  (0,3) 6 (minimum) (6,0) 6 (minimum)Since, feasible region is unbounded. So, 6 may or may not be minimum value.Now to check if 6 is minimum or not, we have to draw  Z<6\Rightarrow x+2y< 6 Since this region doesn't have any common region with feasible region. So, 6 is the minimum value of Z.

Question 5

A feasible solution to an LP problem

Accepted Answer

A feasible solution to an LP problem belongs to the feasible region.  Feasible region is the set of all the points that satisfy the problem's constraints including inequalities, equalities and integer constraints.In the above figure, blue region is the feasible region. All the points in this region are feasible solutions or feasible points which satisfy the given constraints( 4x+3y\leq 480   and  2x+3y\leq 360 )

Question 6

The corner points of the feasible region determined by the system of linear constraints are  (0, 10), (5, 5), (15, 15), (0, 20) . Let  z=px+qy  where  p, q > 0 . Condition on p and q so that the maximum of z occurs at both the points  (15, 15)  and  (0, 20)  is __________.

Accepted Answer

Let  z_{0}  be the maximum value of  z  in the feasible region.Since maximum occurs at both  (15,15)  and  (0,20) , the value  z_{0}  is attained at  both  (15,15)  and  (0,20) . \implies z_{0}=p(15)+q(15)  and   z_{0}=p(0)+q(20) \implies p(15)+q(15)=p(0)+q(20) \implies 15p=5q \implies 3p=q Hence, the answer is option (D).

Question 7

Minimize and maximize  Z=600x+400y Subject to the constraints x+2y\le 12 2x+y\le 12 4x+5y\le 20 x\ge 0;y\ge 0  by graphical method

Accepted Answer

Draw the graph of  2x+y=12  .....  (i) We get intersection of  (i)  with the coordinate axes at points  (0,12)  and  (6,0) Draw the graph of  x+2y=12  .....  (ii) We get the intersection of  (ii)  with the coordinate axes at points  (0\quad 6)  and  (12\quad 0) Draw the graph of  4x+5y=20  .....  (iii) We get the intersection of  (iii)  with the coordinate axes at points  (0,4)  and  (5,0) Common shaded region is the feasible region with corner points  (5,0),(6,0),(4,4),(0,6),(0,4) Corner points  Z=600x+400y (0,4) 1600  minimum (0.6) 2400 (4,4) 4000  maximum (6,0) 3600 (5,0) 3000 Minimum value of  z=1600  at  (0,4) Maximum value of  z=4000  at  (4,4)

Question 8

A toy company manufactures two types of dolls,  A  and  B . Market tests and available resources have indicated that the combined production level should not exceed  1200  dolls per week and the demand for dolls of type  B  is at most half of that for dolls of type  A . Further, the production level of dolls of type  A  can exceed three times the production of dolls of other types by at most  600  units. If the company makes a profit of  Rs. 12  and  Rs. 16  per doll respectively on dolls  A  and  B , how many of each should be produced weekly in order to maximize the profit?

Accepted Answer

Let's assume that the number of dolls of type A is  X and number of dolls of type B be  Y Since combined production level should not exceed 1200 dolls 	herefore X+Y\leq 1200\ \ \ ...(1) Since production levels of dolls of type A exceeds 3 times the production of type B by at most 600 units 	herefore X-3Y\leq 600\ \ \ ...(2) Also, the demands of dolls of type B is at most half of that for dolls of type A 	herefore  Y\leq \dfrac{X}{2} \Rightarrow 2Y-X\leq 0\ \ \ ...(3) Since the count of an object can't be negative.So,  X\geq 0,Y\geq 0\ \ \ ...(4) Now, profit on type A dolls  =12\ Rs and profit on type B dolls  =16\ Rs So, total profit  Z=12X+16Y We have to maximize the total profit (Z) of the manufacturers.After plotting all the constraints given by equation (1), (2), (3) and (4) we get the feasible region as shown in the image. Corner points Value of  Z=12X+16Y  A (800,400) 16000 (maximum) B (1050,150) 15000 C (600,0) 7200 O (0,0) 0So, in order to maximize the profit, the company should produce  800  type A dolls and  400  type B dolls

Question 9

Solve the following problem graphically:Minimise and Maximise z = 3x + 9y Subject to the constraints: x + 3y \leq 60 x + y \geq 10 x \leq y x\geq 0, y\geq 0 .

Accepted Answer

Let  Z = 3x + 9y .... (1) Converting inequalities to equalities x + 3y = 60 x              0        60 y 20          0 Points are  (0, 20), (60, 0) x + y = 10 x       0 10 y       10         0 Points are  (0, 10), (10, 0) x - y = 0 x          0           10            20 y 0           10 20 Points are  (0, 0), (10, 10), (20, 20) Plot the graph for the set of pointsThe graph shows the bounded feasible region.  ABCD , with corner points  A = (10, 0), B = (5, 5), C = (15, 15)  and  D = (0, 20) To find maximum and minimumCorner point Z = 3x + 9y A = (0, 10) 90 B = (5, 5) 60 C = (15, 15) 180 D = (0, 20) 180 From the graph maximum value of  X  occurs at two corner points  C(15, 5)  and  D(0, 20)  with value  180  and minimum occurs at point  B(5, 5)  with value  60 .

Question 10

Find graphically, the maximum value of  z=2x+5y , subject to constraints given below: 2x+4y\le 8 3x+y\le 6 x+y\le 4 x\ge 0, y \le 0.6

Accepted Answer

Maximise  z = 2x + 5y , subject to the constraints 2x+4y\leq 8\Rightarrow x+2y\leq 4 3x+y\leq 6, x + y\leq 4, x\geq 0, y\geq 0 .Draw the lines  x + 2y = 4  (passes through  (4, 0), (0, 2) ); 3x + y = 6  (passes through  (2, 0), (0, 6) ) and  x + y = 4  (passes through  (4, 0), (0, 4) ).Shade the region satisfied by the given inequations.The shaded region in the figure gives the feasible region determined by the given inequations.Solving  3x + y = 6  and  x + 2y = 4  simultaneously, we get x=\dfrac{8}{5}  and  y=\dfrac{6}{5} We observe that the feasible region OABC is a convex polygon and bounded and has corner points. O(0, 0), A(2, 0), B(\dfrac{8}{5}, \dfrac{6}{5}), C(0, 2) The optimal solution occurs at one of the corner points.At  O(0, 0), z = 2.0+5.0=0; At  A(2, 0), z = 2.2+5.0=4; At  B(\dfrac{8}{5}, \dfrac{6}{5}),z = 2.\dfrac{8}{5}+5.\dfrac{6}{5}=\dfrac{46}{5}; At  C(0, 2), z = 2.0+5.2=10; Therefore,  z  maximum value at  C  and maximum value  = 10.