Scribd
Upload
6 views2 pages

Linear Programming Exam Questions

The document outlines the final exam for Class K71 K in Optimization at Hanoi National University of Education, focusing on linear programming problems. It includes multiple-choice questions, a linear programming formulation for an oil refinery's crude oil purchase, and tasks related to solving a linear programming problem using the simplex method. Additionally, it presents an assignment problem with specific cost data for workers and jobs.

Uploaded by

Nga Bùi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views2 pages

Linear Programming Exam Questions

The document outlines the final exam for Class K71 K in Optimization at Hanoi National University of Education, focusing on linear programming problems. It includes multiple-choice questions, a linear programming formulation for an oil refinery's crude oil purchase, and tasks related to solving a linear programming problem using the simplex method. Additionally, it presents an assignment problem with specific cost data for workers and jobs.

Uploaded by

Nga Bùi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Hanoi National University of Education Final Exam for Class K71 K: Optimization

Department of Mathematics and Informatics (Test 1 - Two pages)


Time: 90 minutes – No document –
Calculator allowed

Question 1 (2 points). (Multiple Choice, points {0, 0.5} each) No justifications needed.
Choose ‘yes’ or ‘no’.
a) If the feasible set of the LP problem max{cTx | Ax = b} (with A ∈ Rmxn, 1 ≤ m < n,
rank(A) = m, b ∈ Rm, c ∈ Rn) is not empty, it has at least one basic solution.
b) During the dual simplex algorithm for solving a LP problem, if the current base is
dual feasible, then the base in the next iteration (after pivoting) can be dual infeasible.
c) If we solve the assignment problem (in minimization form with n jobs, n workers and
positive costs) using the simplex method big-M, the objective function of the problem
can be unbounded from below.
d) Suppose that the simplex tableau of a linear programming problem (without artifical
variables) is given as follows :
x x
5 3
z 10 2 1
x 3 -1/2 1/2
2
x 7 5/2 -1/2
4
x 5 3/2 1/2
1

The base corresponding to the variables {x1, x2, x4} is both primal feasible and dual
feasible.

Question 2 (2 points). An oil refinery has two sources of crude oil: a light crude that costs
$35/barrel and a heavy crude that costs $30/barrel. The refinery produces gasoline, heating
oil, and jet fuel from crude in the amounts per barrel indicated in the following table:

Gasoline Heating oil Jet fuel


Light crude 0.3 0.2 0.3
Heavy crude 0.3 0.4 0.2

The refinery has contracted to supply 900,000 barrels of gasoline, 800,000 barrels of heating
oil, and 500,000 barrels of jet fuel. The refinery wishes to find the amounts of light and heavy
crude to purchase so as to be able to meet its obligations at minimum cost. Formulate this
problem as a linear program. Does this LP problem have optimal solution? Why?

Question 3 (4.0 points). Consider the linear programming problem (P):


max −x1 − 6x2 + 7x3 − x4 − 5x5
s.t. 5x1 − 4x2 + 13x3 − 2x4 + x5 = 20
x1 − x2 + 5x3 − x4 + x5 = 8
x1, x2, x3, x4, x5 ≥ 0.

1
a) (1.5 points) Solve this problem using the simplex method Big-M.
b) (1.0 points) What is the dual problem (D) of (P)? Draw the feasible set of dual
problem (D) on the plane.
c) (0.5 points) From the result in part a), fing all optimal solution of the dual problem
(D) using the complementary slackness theorem.
d) (1.0 points) From the information of the last simplex table in part a) (not from the
begining), find a new optimal solution after adding a new constraint below to (P):
!
x1 + x2 + x3 + x4 ≤
"
.

Question 4 (2.0 points). Solve the assignment problem in the minimization form with the
following data of costs:

Workers Jobs
1 2 3 4 5
1 9 22 58 11 19
2 43 78 72 50 63
3 41 28 91 37 45
4 74 42 27 49 39
5 36 11 57 22 25

----- End -----

You might also like