Construct an LPP by choosing suitable c, A (a 5 x 7 matrix) and b such that it looks
like
Max Z = cx
Subject to
Ax = b
b ≥ 0 and x ≥ 0
with the conditions that A should have rank 3 and none of the existing variables
are slack variables. What do you observe when M –method and two phase
methods are used in such a case.
To construct a linear programming problem (LPP) that satisfies the given conditions, we need to choose a suitable objective function (Z), coefficient matrix (A), and constraint vector (b).
Let's start by choosing the objective function:
Max Z = cx
We need to ensure that none of the existing variables are slack variables, so let's choose c such that all coefficients are non-zero. For example, we can choose c = [1, 1, 1, 1, 1, 1, 1].
Next, we need to choose the coefficient matrix (A). Since A should have rank 3, we need to choose a 5 x 7 matrix such that any combination of 3 columns is linearly independent. As an example, we can choose the following matrix:
A = [1, 0, 0, 1, 0, 0, 1;
0, 1, 0, 0, 1, 0, 1;
0, 0, 1, 0, 0, 1, 1;
1, 1, 0, 1, 0, 0, 1;
0, 1, 1, 0, 1, 1, 0]
Finally, we need to choose a suitable constraint vector (b) such that Ax = b. Let's choose b = [1, 2, 3, 4, 5].
Now we have constructed the LPP with the given conditions:
Max Z = x₁ + x₂ + x₃ + x₄ + x₅ + x₆ + x₇
Subject to:
x₁ + x₄ + x₇ = 1
x₂ + x₅ + x₇ = 2
x₃ + x₆ + x₇ = 3
x₁ + x₂ + x₄ + x₇ = 4
x₂ + x₃ + x₅ + x₆ = 5
b ≥ 0 and x ≥ 0
When using the M-method, we introduce artificial variables to convert the problem into a standard form. For each equation in the constraint, we introduce an artificial variable and update the objective function accordingly.
In the case of the two-phase method, we initially solve a two-phase problem: Phase 1 finds a feasible solution by minimizing the sum of artificial variables. Once a feasible solution is obtained, we move to Phase 2, where we optimize the original objective function by removing the artificial variables.
When solving the LPP using the M-method or two-phase method in this case, you will observe the following:
1. M-method: It may take longer to find the optimal solution compared to cases where slack variables are used since additional artificial variables need to be introduced. The artificial variables will have non-zero values in the optimal solution, indicating their necessity in achieving feasibility.
2. Two-phase method: The Phase 1 problem will involve minimizing the sum of artificial variables, which may result in non-zero optimal values for these variables. Once Phase 1 is completed and a feasible solution is found, the Phase 2 problem will be solved to maximize the original objective function while disregarding the artificial variables.