Project for Operations Research 1
March 27, 2019
• Marks for project: 30%.
• Project due date: 23:55 Friday 12 April 2019 (Week 12).
1 Project Description
A file has been placed at http://jkcray.maths.ul.ie/ms4303/Projectdata. pdf containing a list of LP’s, a different one for every student in the class.
The LP’s are in Standard Form, so z is to be minimised. 2 Solution to Optimality
You should:
• Find and copy down “your” problem.
• CreateaMatlab/Octavescriptm-fileRun.mcontainingalltheMatlab/Octave commands needed to solve the problem.
• Generate a Simplex tableau T0 for your LP.
• UsetheprovidedPivot.mm-filewitheitherOctaveorMatlabtotransform
T0 to a canonical form tableau TB.
• Use the provided colsortjk m-file with either Octave or Matlab to trans- form TB to a canonical form tableau TC which has the basic columns in standard order on the right of the tableau.
⋆ This corresponds to re-labelling the decision variables but does not change the optimal value of the LH–column and in particular z.
• Use the Pivot.m m-file with either Octave or Matlab to solve TC to opti- mality.
• Name the optimal tableau T∗.
• What is the optimal solution vector x and the optimal z–value?
• You don’t need to — and shouldn’t — “undo” the column sort.
1
3 Sensitivity Analysis
For the remaining questions, you need to interpret your Standard Form LP (which is a min problem) as derived from a max problem with (of course) the objective coefficients reversed in sign.
The techniques needed for this part of the project will be explained in class from Week 8 on — they are covered in Ch. 5 of the Notes in the same sequence as the tasks in the following paragraphs.
(A) First deal with some changes in the Production Requirements. (a) There has been a change in the Production Requirements.
• Pick the last non-basic variable in T∗ (I’ll refer to it as xnbl) and increase it up to a value X — where X is either 1 unit or to half the maximum value of xnbl (whichever is the greater).
• What is the new optimal solution x and optimal z–value?
• Check your result(s) by adding the constraint xnbl = X to T∗ and
pivot to optimality.
(b) There has been another change in the Production Requirements.
Find the last basic variable in T∗ (I’ll refer to it as xbl) and increase it from its optimal value by 1 unit or by half its maximum increase (whichever is the greater).
∗ Choose the “cheapest” non-basic variable to be increased
from zero — i.e. the one has the least effect on the objective
function value.
⋆ Ifthelastbasicvariablecannotbeincreased,choosethesecond-
last, . . . until you find a basic variable that can increased. What is the new optimal solution x and optimal z–value?
Check your result(s) by adding the constraint xbL = X to T∗ where X is the chosen larger value of xbL and pivot to optimality.
• ⋆
• •
(c) There has been yet another change in the Production Requirements.
• Find the first non-basic variable in T∗ (I’ll refer to it as xnbf) and increase it by one unit above its maximum value, the mini- mum row ratio (mrr) for the variable. If xnbf cannot be increased by one unit above its mrr, increase it by the maximum amount possible. (Use the two-phase method explained in Ch. 5 “When a Nonbasic Variable becomes Basic and Exceeds its Minimum Row Ratio” in the Notes.)
• What is the new optimal solution x and optimal z–value?
• Check your result(s) by adding the constraint xnbf = X to T∗
where X is the chosen value of xnbF and pivot to optimality.
2
(B) There has been a change in the availability of resources.
• Use the tableau TC as your STARTING tableau for this part of the project.
• The availability of the resource corresponding to the last non-basic slack variable of your optimal form tableau T∗ has changed.
• Work out (using the technique explained in Ch.5 of the Notes) the maximum amount by which the availability of this resource may be reduced and the maximum amount by which it can be increased while maintaining the optimality of your optimal tableau T∗.
• Use the technique explained in Ch. 4 of the Notes to increase the availability of this resource by half this maximum amount and find the new optimal solution x and optimal z–value.
• Check your result(s) by altering the availability of the resource in TC and pivoting to optimality.
(C) A change in the price/cost (price if positive, cost if negative) of the first variable that is basic in your optimal tableau is required. (I’ll call it xbf.)
• Use the tableau TC as your STARTING tableau for this part of the project.
• Use the technique explained in Ch. 5 of the Notes to find the range of price-changes q for that product in the canonical form tableau TC that keeps the current set of basis variables basic in your optimal tableau.
• If possible, Decrease {if not then Increase} the price/cost in the “real” LP (equivalent to Increasing {otherwise Decreasing} the price/cost in the canonical form tableau TC) for the selected basic variable by half the maximum amount possible that keeps the cur- rent set of basic variables basic in your optimal tableau.
• Find the new optimal z–value (the optimal x–vector will not change).
• Check your result(s) by altering the price in TC and pivoting to opti-
mality.
4 Report
• Write a report in PDF format using LATEX explaining your steps and your interpretation of the results.
• Your report should include the succession of tableaux that you created when solving the problem, copy/pasted from the diary file.
• Use the LATEX verbatim environment to enclose the successive tableaux.
• Use \tiny if necessary to allow your tableaux to fit on a page.
3
• You should submit a zip file containing your working folder, including your LATEXfiles and your Matlab/Octave m-files.
• Email attachments (other than a single zip file) will not be accepted.
• Marks will be awarded for correct results and also for clear explanations of your steps.
4