Answer to Question #174181 in Operations Research for Nishi sharma

Question

Which of the following statements are true and which are false? Give a short proof or a 

counter example in support of your answer. (10) 

 

(a) The optimal solution for the following LPP is 30 :

*

Z =

Max 1 2 3 3 Z = x − x + x

 Subject to x1 + x2 + x3 ≤10

 x1

, x2

, x3 ≥ .0

 

 (b) The optimal solution of an ILLP can be obtained by rounding off the optimal solution 

of its LP relaxation. 

 (c) If the availabilities and requirements of a balanced transportation problem are 

integers, the optimal solution to the problem will have integer values. 

 (d) The following max /3/4 F / F problem can be reduced to a machine problem. 

 

Job 

Processing time on

M1 M2 M3

1 8 6 10

2 5 2 13

3 4 11 11

4 6 7 10

 (e) For the mixed generator rn+1 = 5( rn + )7 (mod ),8 if r0 = ,4 then 3

r is zero.

Answer 1

a) true

$Z_{max}=x_1-x_2+3x_3$

Solve by simplex method using online calculator:

$Z_{max}=30,x_1=x_2=0,x_3=10$

b) false

The rounded LP relaxation solution is almost certainly non-optimal and may be very non-optimal (in the sense that the objective function value of the rounded LP relaxation solution is very far away from the objective function value of the optimal integer solution).

c) true

For balanced problem: total supply=total demand.

In process we perform only addition and substraction with integers.

e) false

$r_{n+1}=(5r_n+7)mod8$

$r_1=27mod8=3$

$r_2=22mod8=6$

$r_3=37mod8=5$

d) false

An optimal solution to this problem can be obtained, if either or both of the following

conditions hold(s):

$mint_{1j}\geq maxt_{2j}$

$mint_{mj}\geq maxt_{2j},m=1,2,3$

We have:

$mint_{1j}=4<maxt{2j}=11$

So, condition for optimal solution is not getting.