1 An LP with a Max objective function and 2 decision variabl

1) An LP (with a Max objective function and 2 decision variables (x,y)) has two extreme

(corner) points that are optimal: (x1,y1)= (1,2), (x2,y2)=(0,3)

Which of the following points is definitely not an optimal solution? Explain/show why.

a) (0.1, 2.9)

b) (0.5, 2.5)

c) (0.2, 2.8)

d) (1.2, 2.3)

Solution

There is an error in attaching the image. If you point out all the 4 points on a graph and also the extreme points and find the boundaries you then can see the outliers of the maximum function.

The image attached demonstrates how (1.2,2.3) stays outside the boundary. When the given points x1,y1,x2,y2 are extreme corners there cant be another extreme corner outside the boundary. Tus, option D cannot fall under the category of optimal solution.

z=ax+by

z=a+2b

z=3b

Solving on the maximum function- u get a=b.

Substituting the values in the maximum function get option D as the outlier.

If a linear programming problem has a solution, it must occur at a vertex of the set of feasible solutions. If the problem has more than one solution, then at least one of them must occur at a vertex of the set of feasible solutions. In either case, the value of the objective function is unique.