Question

This sections seeks to assess understanding for course objectives #3, #5, an u5, and t6. 3.1 Consider the following visualization for a linear program. Let slack variables xs, ra xs be added a correspond to constraints 1, 2, and 1, respectively. You have been told that the optimal solution has O, and 1a 0. respectively. You have been told that the optimal solution has 40 35 30 .Constraint 1 - Constraint 2 Constraint3 20 15 10 0 5 10 15 20 25 30 3540 From this given information, what lettered point is the optimal solution? Why? From this given information, can there be multiple optimal solutions? Why or why not? arer and

Answer 1

1) We are given that x1 >= 0 and x3, x4 = 0

X3 = 0 means that constraint 1 is a binding constraint.

X4 = 0 means that constraint 2 is a binding constraint.

Therefore, point at the intersection of constraint 1 and 2 is the point of optimal solution.

That point is D.

2) From the given information, there cannot be multiple optimal solution. Because to have constraints1 and 2 as binding, while the feasible region is a two-dimensional space, so there can be only one point at their intersection as optimal solution.

3) The starting point for simplex algorithm is origin (A)

The next point is one which improves the objective function.

As constraint 1 and 2 are binding, the slope of the objective function must be between the slopes of these two constraints. So, the next parallel objective function will pass through point E.

The point on the next iteration is D.

So the most efficient path for simplex algorithm is A->E->D