Qs2
Using Bland’s Rule, the three iterations are as follows:
Construct the initial simplex tableau:
Basic Variables x1 x2 x3 x4 x5 Right-hand side
x4 1 3 −1 1 0 2
x5 1 0 0 0 1 2
Zj −5 −5 3 0 0 0
Cj − Zj 5 5 −3 0 0
First Iteration:
Select the entering variable: Using Bland’s Rule, select x1 to enter
the basis.
Select the exiting variable: Calculate the leaving ratios:
b1 2
= =2 for x4
a14 1
b2 2
= = 2 for x5
a24 1
Choose the variable with the smallest ratio to leave the basis. Here, x4 and
x5 have the same ratio, so according to Bland’s Rule, select the variable with
the smallest index, x4 , to leave the basis. Update the simplex tableau:
Basic Variables x1 x2 x3 x4 x5 Right-hand side
x1 1 3 −1 1 0 2
x5 0 −3 1 −1 1 0
Zj 5 0 0 5 0 10
Cj − Zj 0 5 3 −5 0
Second Iteration:
Select the entering variable: According to Bland’s Rule, select x2
to enter the basis.
Select the exiting variable: Calculate the leaving ratios:
2 2
= for x1
3 3
1
x1 leaves the basis.
Update the simplex tableau:
Basic Variables x1 x2 x3 x4 x5 Right-hand side
x2 1
3
1 − 31 1
3
0 2
3
x5 −1 0 0 1 1 2
5 1 2
Zj 3
0 3 3
0 0
Cj − Zj 5
3
5 − 31 − 23 0
Third Iteration:
Select the entering variable: Choose x1 to re-enter the basis.
Select the exiting variable: Calculate the leaving ratios:
2/3
=2 for x2
1/3
2
= Invalid for x5
−1
x2 leaves the basis. Update the simplex tableau:
The final tableau is:
Basic Variables x1 x2 x3 x4 x5 Right-hand side
x1 1 0 − 13 2
3
0 2
1 1
x5 0 0 3 3
1 2
Zj 0 0 − 23 0 0 10
Cj − Zj 0 5 2
3
− 32 0
After the third iteration, we obtain the current basic solution:
• Basic variables are x1 = 2, x5 = 2.
• Objective function value Z = 10.
• Non-basic variables x2 = 0, x3 = 0, x4 = 0.
Qs3
(a)
Correct.
2
Proof: When solving linear programming problems using the simplex
method, if the optimal solution is obtained, there will be no situation where
all the coefficients in a row of the coefficient matrix are non-positive during
the iteration process.
In the given standard form, there are negative numbers in the first row
of coefficients, but there are also positive numbers, which does not meet the
condition where all coefficients are non-positive.
(b)
Correct.
Proof: Let x1 −y1 and x2 −y2 be any two points in C, where x1 , x2 ∈ C1
and y1 , y2 ∈ C2 . For any λ ∈ [0, 1], consider the point
z = λ(x1 − y1 ) + (1 − λ)(x2 − y2 )
z = λx1 + (1 − λ)x2 − λy1 − (1 − λ)y2
Since C1 and C2 are both convex sets, λx1 + (1 − λ)x2 ∈ C1 , and
λy1 + (1 − λ)y2 ∈ C2 . Therefore, z ∈ C, indicating that C is a convex set.
(c)
Incorrect.
Counterexample: Consider the set in two dimensions {(x1 , x2 ) ∈ R2 :
|x1 | + |x2 | = 1}. This set is a square with vertices at (1, 0), (0, 1), (−1, 0),
and (0, −1). These vertices are the extreme points of the set.
(d)
Incorrect.
Counterexample: Consider the following infeasible linear program-
ming problem:
max z = x1 + x2
3
subject to
1 ( )1 1
−1 −1 x1 ≤ −2
x
2
1 −1 0
x1 , x 2 ≥ 0
This problem has no feasible solution because it is not possible to satisfy
all the inequality constraints simultaneously.
(e)
Correct.
Proof: For example, in two-dimensional space, consider a linear con-
straint without fixed boundaries, such as the half-plane formed by x1 ≥ 0
and x2 ≥ 0. In this case, the feasible region has infinitely many extreme
points.
Qs5
(a)
The dual problem D is:
Maximize αy1 + βy2 + 7y3
subject to the constraints:
2 4y 2 γ
1
1 2 −1 · y2 ≤ −1
−1 3 2 y3 3
and y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.
(b)
y1 (2x1 + x2 − x3 − α) = 0
4
y2 (4x1 + 2x2 + 3x3 − β) = 0
y3 (2x1 − x2 + 2x3 − 7) = 0
Furthermore,
x1 · (2y1 + 4y2 + 2y3 − γ) = 0
x2 · (y1 + 2y2 − y3 + 1) = 0
x3 · (−y1 + 3y2 + 2y3 − 3) = 0
(c)
a = (0, 1, 4)T Substituting into the constraints of the primal problem
gives:
1−4≥α ⇒ α ≤ −3
2 + 12 ≥ β ⇒ β ≤ 14
Thus, α ≤ −3, β ≤ 14.
b = (1, 0, 2)T Substituting into the constraints of the dual problem
gives:
2+4≤γ ⇒ γ≥6
Thus, γ ≥ 6.
The ranges for α, β, and γ are:
α ≤ −3, β ≤ 14, γ ≥ 6.
