XXXX学年第X学期《运筹学》期末试卷
Class ID Number Name Score
I.True/False
(1)A balanced transportation problem has the same number of supply points as demand points.
(2)In the search for an optimal solution of an LP problem, only vertexes of feasible region are
needed to be considered.
(3) The stepping stone method is used because the transportation problem cannot be solved via the
simplex method.
(4) Linear Programming can be employed to solve problems with single objective.
(5) If a resource is not finished out, then its shadow price must be positive.
(6) The first step in applying the simplex method is to transform all inequality constraints into
equality constraints by adding slack variables and subtracting surplus variables.
(7) The optimal value of the primal objective function is equal to the optimal value of the dual
objective function.
(8) If a constraint is in “≥” form in LP problem, then artificial variable is necessary.
(9) That the feasible region of LP is not empty means:
(A) it includes the origin X=(0,0,…,0);
(B) it is bounded;
(C) it is unbounded;
(D) it is convex.
(A, B, C, D)
(10) Both the primal and dual problems are of feasible solution, then may be
(A) an optimal solution is available for primal problem, but the optimal solution
is not available for dual problem;
(B) at least one problem is unbounded;
(C) an optimal solution is available for one problem, and the other problem is of
unbounded solution;
(D) both the primal and dual problems might be of optimal solution.
(A, B, C, D)
II.To solve the problems below:
(1) Min. w = 14X1 + 20X2
s.t. X1 + 4X2 ≥4
X1 + 5X2≥2
2X1 + 3X2≥7
X1, X2 ≥0
Please find out the optimal solutions for both this problem and its dual.
(2) The objective function of an LP is Max. Z = 5X1+6X2 +8X3. This LP is of two constraints (resources #1 and # 2 respectively) with “≤”form.Below is a processing step by using simplex method.
a)To complete this table;
b)Is this table optimal? If “yes”, then do c); if “no”, then find out the optimal table.
c)To write out the optimal solution and objective value.
d)To write out the shadow prices of resources #1 and #2, and describe the
significances.
III.To find the shortest path and its length from A to E:
7
B1 C1 1
6 4 4 D1
M+1
2 3 6
A 4 B2 2 C2 E
3 4 3
4
4 1 3 D2
B3 3 C3 3
M is the last place of your ID number.
