Now we're going to look at some special case of optimization problems where there are multiple optimal solutions. In particular, we're going to look at an example to see when can there be multiple optimal solutions. This will give us an intuition as to when, or what are the situations in which linear optimization problem can have multiple optimal solutions. Let's take a look at the example. Now let's look at an example of a linear problem where there are more than one optimal solution. This type of a situation is one where there are alternate optimal solutions instead of a single solution. There can be more than one feasible point that maximizes or minimizes the value of the objective function. To see that, let's look at an example. We had been looking at this example of production of two products and two machines that were working on these products. Let's modify that problem a little bit. Consider this objective function where instead of originally we have 300x_1 plus 200x_2 instead of that, now we have 400x_1 plus 200x_2 as the objective function. That is, each unit or product one, produces a profit of $400, and each unit of product two produces a profit of $200 as before. We have changed this number over here so product one, now has a profit of $400 per unit instead of $300, as in the original problem. The constraints remain unchanged from the original problem, 2x_1 plus x_2 is less than or equal to eight. That's the constraint on the number of hours that machine one has, and x_1 plus 2x_2 two is less than or equal to eight, which is the constraint from the number of hours that machine two has. We have the non-negativity constraints. Because none of these constraints have changed, the feasible region that we have, is the same as the original problem that we have. The corner points of this feasible region are 0,0, 0,4, 4,0 and eight over three, which is the intersection of the two boundary lines from the two constraints. The only difference in this problem is in the objective function. Since this number is different, the level curve for this objective function will be also different, so let's try to plot the level curves for this objective function. We have 400x_1 plus 200x_2, is equal to some value V. This is the value that the objective function can take. Lets say we are interested in finding all the values of x_1 and x_2 such that the total value is $800. We're looking for this line, 400x_1 plus 200x_2 is equal to 800. We can see that when x_1 equal to zero, then x_2 has to be equal to four in order for the objective function to have a value of 800. We have a point 0,4 that lies on this objective function. Similarly, x_1 is two when x_2 is zero to produce 800. This point 2,0 is also a point on the level curve of the objective function when the value is 800. Let's plot this. We have 0,4, which is this point, and 2,0 which is this point. This is the level curve for the objective function. This is the level curve for the value of 800, so 4x_1 plus 200x_2 is equal to 800. For all values of x_1, x_2 that lies on this line and the part of the feasible region, if you select any of these points, then the value of the objective function will be $800. Now of course, this is not the optimal because you can keep on getting higher and higher profit, but pushing out this level curve further out, and you can have a level curve, let say somewhere like this. Now you can do even better. You can push it further out. Here you can see that for some value V, the level curve for this objective function will coincide with this constraint, with the constraint for machine one. This is not a coincidence because if you look at the structure of the objective function 400x_1 plus 200x_2, equal to some value V. Here you have the coefficient of x_1 is twice that of x_2, which is same as the structure of the constraint for machine one. It was 2x_1, plus x_2, so the coefficient of x_1 was twice that of x_2. Here also for the objective function, you have the coefficient which is twice as large as that of x_2. The slopes of this line, of the level curve denoting this objective function is the same as the slope of this constraint, and that's why they are coinciding when you are pushing this level curve further and further out. We're getting a situation where the level curve for the objective function and one of the constraints, which is the first constraint here, are completely coinciding. Therefore, all these points here, in this part are optimal solutions. Previously, because the slope of the objective function was different from that of the slopes of the constraints, we had one point, that was the optimal solution. But now here the slope of the objective function is such that it is exactly the same as one of the boundaries of the feasible region as determined by one of the constraints. Therefore all these points here are going to be optimal. This final curve that you are getting as you push out this level curve for the objective function further and further away from the origin, we see that the final curve intersects with the feasible region along the edge of the feasible region, rather than at a single point. Therefore, all the points in this line segment, joining the point eight over three over, eight over three, and 4,0 are producing the same value of the objective function. Which is here it is going to be, since it's passing through 4,0, the value of the objective function here would be, four times 400. That is 1,600 plus 200 times zero, so that is going to be 1,600. This level curve that we have here, for the objective function, is this value, 400x_1 plus 200x_2 is equal to 1,600. All the points here would produce this solution of $1,600. This is the same objective function value for all these points, and so all of them are optimal. All the points in this segment are optimal solution. There, instead of a single value, there is a whole continuous set of values over here on this part of the segment, data optimal solutions. You can choose any one of them, and all of them would produce a profit of $1,600, and that's the optimal solution for this problem. This is an example where you have multiple optimal solutions, which produce the same value of the objective function as the $1,600 in this case, as opposed to having just a single point as the optimal solution.
