Question

According to the Fundamental Theorem of linear programming, if either a linear program or its dual has no feasible point, then the other one has no solution. Illustrate this assertion with an example.

Short answer

We constructed a linear program (LP) and its dual linear program (DLP). After analyzing the LP, we found it has no feasible region, as no point satisfies all three constraints simultaneously. According to the Fundamental Theorem of linear programming, if the LP has no feasible point, then its DLP must have no solution. True to the theorem, we found that there is no combination for y_1, y_2, and y_3 that satisfy all DLP constraints simultaneously, proving the assertion.

Step-by-step solution

Create a linear program

: Let's create a linear program (LP). Maximize: \(z = 2x_1 + 3x_2\) Subject to: \(x_1 + x_2 ≤ 1\) \(x_1 - x_2 ≥ 3\) \(-2x_1 + 3x_2 ≤ 1\) \(x_1, x_2 \geq 0\)

Create the dual of the linear program

: Now, let's construct the dual linear program (DLP) for the given LP. Minimize: \(w = y_1 + 3y_2 + y_3\) Subject to: \(y_1 + y_2 - 2y_3 ≥ 2\) \(y_1 - y_3 + 3y_3 ≥ 3\) \(y_1, y_2, y_3\geq 0\)

Check for feasible region in the linear program

: Now, let's check whether the given LP has a feasible region (in which an optimal solution could exist) by finding the intersection of the constraints. Plot the constraints: \(x_1 + x_2 = 1\), \(x_1 - x_2 = 3\), and \(-2x_1 + 3x_2 = 1\). Upon analyzing the plots, we can see that no point satisfies all three constraints simultaneously, indicating that the LP does not have a feasible region.

Check the dual linear program for a solution

: According to the Fundamental Theorem of linear programming, since the given LP has no feasible point, its DLP should have no solution: Check the DLP constraints: \(y_1 + y_2 - 2y_3 = 2\), \(y_1 - y_3 + 3y_3 =3\), and \(y_1, y_2, y_3\geq 0\). Upon attempting to solve the DLP constraints, we find that there is no combination of values for y_1, y_2, and y_3 that satisfy all constraints simultaneously. Therefore, the DLP does not have a solution. Thus, the given example illustrates the Fundamental Theorem of linear programming asserting that if either a linear program or its dual has no feasible point, the other one also has no solution.