Student
number
Semester 1 Assignment 2, 2021
School of Mathematics and Statistics
MAST20018 Discrete Mathematics and Operations Research
Submission deadline:
This assignment consists of 3 pages (including this page)
Instructions to Students
• If you have a printer, print the assignment.
Writing
• This assignment is individual.
• Write your answers on A4 paper. Page 1 should only have your student number, the
subject code and the subject name. Write on one side of each sheet only. Each question
should be on a new page. The question number must be written at the top of each page.
Scanning
• Put the pages in question order and all the same way up. Use a scanning app to scan all
pages to PDF. Scan directly from above. Crop pages to A4. Make sure that you upload
the correct PDF file and that your PDF file is readable.
Submitting
• Go to the Gradescope window. Choose the Canvas assignment for this assignment. Submit
your file. Get Gradescope confirmation on email.
c©University of Melbourne 2021 Page 1 of 3 pages Do not place in Baillieu Library
MAST20018 Discrete Mathematics and Operations Research Semester 1, 2021
Question 1
Consider the following feasible region of a Linear Program.
x1 + x2 ≤ 6
x1 − x2 ≤ 4
3x1 + x2 ≥ 3
x1, x2 ≥ 0.
(a) Write the problem with equalities, using slack or surplus variables x3, x4 and x5
for the three functional constraints.
(b) Draw the feasible region and identify all basic feasible solutions (BFS). For each
BFS, give the values of all components of the solution (original and slack/surplus
variables).
(c) Identify one basic solution that is not feasible. Which component(s) of the solution
vector tell you that this solution is not feasible?
(d) Identify one feasible solution that is not basic. Looking at the solution values only
(ignoring the graph), how can you tell that this solution is feasible but not basic?
Question 2
Consider the Linear Program below.
max z = x1 + 2x2 + 3x3
x1 + 2x2 + 3x3 ≤ 10
x1 + 4x2 ≤ 5
x1 ≤ 1
x1, x2, x3 ≥ 0
(a) Write the problem in canonical form.
(b) Use the simplex algorithm to find all optimal solutions.
(c) Write an expression for the space defined by the optimal solutions.
Question 3
Consider the LP below:
min z = x1 + 3x2 − 5x3
s.t.
x1 + x2 + x3 = 8
2x1 − 5x2 + x3 ≥ 10
x1, x2, x3 ≥ 0
(a) Convert the LP to canonical form:
(b) Solve the above LP using the Two-Phase Simplex method. At the end, indicate
what is the optimal solution and its value.
Page 2 of 3 pages
MAST20018 Discrete Mathematics and Operations Research Semester 1, 2021
Question 4
The Big-M method is an adaptation of the Simplex Algorithm which is used as an alternative
to the Two-Phase Simplex method. The pseudo-code for the Big-M method is as follows:
ALGORITHM Big-M
Input: An LP in canonical form with objective max z = f(x) and artificial variables y1, ..., yp
Output: An optimal solution to the LP or a statement that the LP is infeasible or unbounded
1: Let M be a very large constant
2: Modify the objective of the LP to max z′ = f(x)−M!pi=1 yi
3: Employ the standard Simplex Algorithm to solve the LP with the modified objective. The
Optimality Criterion is satisfied when there are no more negative reduced costs in the
columns of the non-artificial variables
(a) Express the following LP in canonical form and solve using the Big-M method
(b) Sketch the feasible region and identify the point associated to each tableau you
obtained in (a).
Hints:
• Use the symbol M in the Simplex tableau and NOT simply a large number of your
choice.
• Note that you may choose not to add artificial variables to all constraints as in the
algorithm. All you need to start the method is an initial Identity matrix in your
coefficient matrix A.
min z = −x1 − x2
s.t.
x1 + x2 ≥ 1
2x1 + 3x2 ≤ 12
3x1 + 2x2 ≤ 12
x1, x2 ≥ 0
End of Assignment
Page 3 of 3 pages

欢迎咨询51作业君