Problem 58 - Applied Mathematics: For the Managerial, Life, and Social Sciences

Question

Consider the linear programming problem $$ \begin{array}{lr} \text { Maximize } & P=2 x+7 y \\ \text { subject to } & 2 x+y \geq 8 \\ x+y & \geq 6 \\ x & \geq 0, y \geq 0 \end{array} $$ a. Sketch the feasible set \(S\). b. Find the corner points of \(S\). c. Find the values of \(P\) at the corner points of \(S\) found in part (b). d. Show that the linear programming problem has no (optimal) solution. Does this contradict Theorem \(1 ?\)

Step-by-Step Solution

Answer

In short, the feasible set S was graphically represented by plotting the constraint inequalities and finding the intersection of the shaded areas. The corner points of the feasible set were found to be (2,4), (4,0), and (0,6). The value of the objective function P at these points is 32, 8, and 42, respectively. However, there is no optimal solution as the value of P keeps increasing along the line x + y = 6 and moving towards higher values of y. This does not contradict Theorem 1 since it does not guarantee the existence of an optimal solution in all cases, just its occurrence at a corner point if it exists.

Step 1: Sketch the feasible set S

To represent the feasible set graphically, we need to draw the constraint inequalities. First, we rewrite the inequalities as equalities to get the constraint lines: 1. \(2x + y = 8\) 2. \(x + y = 6\) Now, plot these lines on a graph with x and y as the coordinate axes, and then shade the areas satisfying the inequalities. The intersecting area of the shaded areas is the feasible set S.

Step 2: Find the corner points of S

The corner points of the feasible set are the vertices or intersections of the constraint lines and non-negativity constraints. To get the corner points, find the intersection points of the constraint lines and the intersection points of the constraint lines with the non-negativity constraints x ≥ 0 and y ≥ 0. The corner points are: 1. Intersection of the line \(2x + y = 8\) and the line \(x + y = 6\): Solve this system of equations to get \(x = 2\) and \(y = 4\). So, the point is (2,4). 2. Intersection of the line \(2x + y = 8\) and the x-axis (y = 0): Put y = 0 in the equation to get \(x = 4\). So the point is (4,0). 3. Intersection of the line \(x + y = 6\) and the y-axis (x = 0): Put x = 0 in the equation to get \(y = 6\). So, the point is (0,6). So, we have 3 corner points: (2,4), (4,0), and (0,6).

Step 3: Find the values of P at the corner points

Calculate the value of the objective function P = 2x + 7y at the corner points: 1. P(2,4) = 2(2) + 7(4) = 4 + 28 = 32 2. P(4,0) = 2(4) + 7(0) = 8 3. P(0,6) = 2(0) + 7(6) = 42

Step 4: Analyze the (optimal) solution

The given problem asked to maximize the objective function P. From the calculated values of P at the corner points, the maximum value of P is 42 at the point (0,6). However, let's analyze whether this is an optimal solution or if the problem has no optimal solution. To verify if there is no optimal solution, we can find a point in the feasible set where the value of P would be greater than the maximum value found at the corners. Consider a point along the bounded line (line x + y = 6) and moving towards the increasing values of y. The value of P will keep increasing as we move along the line and go towards infinity, as there is no upper bound for the value of y. As we move upwards along the line, we will continue to find points with greater values of P. Hence, there is no optimal solution to this problem. This does not contradict Theorem 1, since Theorem 1 states that if there is an optimal solution for a linear programming problem, it will occur at a corner point of the feasible set. However, in our case, there is no optimal solution, which means that Theorem 1 does not guarantee the existence of an optimal solution in all cases.

Key Concepts

Feasible Set

In linear programming, a feasible set is the collection of all possible solutions that satisfy given constraints. When you graph these constraints, the feasible set represents the shared region that adheres to all conditions. For the given problem, you plot the inequalities as straight lines on a graph:

• The line for the inequality \(2x + y \geq 8\).
• The line for the inequality \(x + y \geq 6\).
• Additionally, the inequalities \(x \geq 0\) and \(y \geq 0\) symbolize that solutions must be in the first quadrant, where both x and y are non-negative.

In this situation, the feasible set is a geometric region where all these conditions overlap. It's crucial to identify this area because any point within it is a potential solution to the problem.

Constraint Inequalities

Constraint inequalities are mathematical expressions that limit the range of possible solutions in a linear programming problem. They shape the feasible set by defining the boundaries within which a solution can exist. Let's look at the constraint inequalities for this exercise:

• First, \(2x + y \geq 8\) means every solution must have a total value combining twice the x and y values that is at least 8.
• Similarly, \(x + y \geq 6\) requires the sum of x and y to be no less than 6.
• The constraints \(x \geq 0\) and \(y \geq 0\) ensure values are non-negative, indicating a focus on practical, real-world scenarios where negatives are typically invalid.

These inequalities are pivotal as they define the feasible region's limits, giving form and direction to the search for an optimal solution within the problem.

Objective Function

The objective function in linear programming is a mathematical expression that you want to maximize or minimize. In this problem, you're looking to maximize \(P = 2x + 7y\).

• Here, \(x\) and \(y\) are variables that need to be adjusted within the feasible set.
• The coefficients of these variables, 2 and 7, determine how much each variable contributes to the total objective value.

This function helps you find a particular solution within the feasible set that offers the greatest or least value. It tells us how changes in the variables affect the overall goal, guiding the decision of where to look for the optimal solution. Understanding the objective function's role will enable you to align strategies with your expected outcome efficiently.

Corner Points

Corner points, or vertices, are crucial in linear programming as they represent potential solutions at the edges of the feasible set. These are points where constraint lines intersect, making them important to evaluate:

• The intersection of \(2x + y = 8\) and \(x + y = 6\) gives the point (2,4).
• The intersection of \(2x + y = 8\) with the x-axis (y=0) yields the point (4,0).
• The intersection of \(x + y = 6\) with the y-axis (x=0) gets us the point (0,6).

Evaluating the objective function at these corner points helps establish an optimal solution. However, if no single point optimizes the function within given constraints, further steps need to be taken, typically pointing to a lack of bounded maximum or minimum within the feasible set. For this specific exercise, analyzing corner points reveals no definitive optimum, aligning with scenarios of unbounded solutions.