PROBLEM 1

Maximize,

\[ z=x_1+x_2\] subject to, \[x_1+x_2\leq 2000\] \[x_1+x_2\leq 1500\] \[x_2\leq 600\] and \(x_1,x_2\geq 0\)

To solve the given LPP graphically, we first plot the following lines formed by changing the constraints to equations. \[x_1+2x_2=2000\] \[x_1+x_2=1500\] \[x_2=600\] Then in order to locate the feasible region of the problem we put \(x_1=x_2=0\) and check if the statements are either true or false as follows: \[0\leq 0(TRUE)\] \[0\leq 0(TRUE)\] If the statements are true then we draw arrows from the respective lines (pointing) towards the origin, otherwise we draw arrows pointing in the opposite direction. The feasible region (in our case, the blue shaded polygon OABCD) is the region where all the arrows, merge. It is to be noted that our LPP problem restricts the values of x1 and x2 to be in the first quadrant.

As the Fundamental Theorem[Geometrical Approach] of LPP states that if an LPP admits an optimal solution, then the objective function assumes optimum value of an extreme point of the convex set generated by the set of all feasible solutions, we first proceed with finding the values of the objective function at the extreme points O,A,B,C,D as:

\(z(0,0)=0,z(0,600)=600,z(800,600)=1400,z(1000,500)=1500,z(1500,1500)=1500\)

Now we draw the lines(given below) when the objective function takes on the above values. \[z_0=x_1+x_2=0\] \[z_1=x_1+x_2=600\] \[z_2=x_1+x_2=1400\]

\[z_3=x_1+x_2=1500\]

By viewing the lines(dotted green lines) it is quite easy to see that as how the solution set moves around as we increase the value of the objective function. Also it is quite evident that our objective function can take a maximum value of 1500 in the feasible region (as a value more than 1500 would simply imply that the solution will be outside the feasible region). Hence, the optimum value of the objective function is 1500. Also, as there were two extreme points C and D where the objective function can take a value of 1500, all the points in the line segment CD may be viewed as the solution leading us to conclude that there are infinite solutions to the given LPP.

 x = seq(-100,2000,1)
y1 = (2000-x)/2  
y2 = (1500-x)
y3 = rep(600,length(x))
o1=c(0,0,800,1000,1500,0)
o2=c(0,600,600,500,0,0)
z = function(x,y) x+y
opt.values=z(o1,o2)[-6]
plot(x=x,y=y1,type="l",xlab="x1",ylab="x2",xlim=c(-100,2000),
       ylim=c(-100,800),col="blue",main="Figure 1")
abline(v=0)
abline(h=0)
lines(x=x,y=y2,col="red")
lines(x=x,y=y3)
text(1100,620,"x2=600")
text(1600,300,"x1+2x2=2000",col="blue")
text(1000,700,"x1+x2=1500",col="red")
text(o1+50,o2+50,c("O","A","B","C","D"))
points(o1,o2)
polygon(cbind(o1,o2),col="lightblue")
for(i in 1:length(opt.values)){
  lines(x,opt.values[i]-x,lty="longdash",col="dark green",lwd=2)
}