(a) Solve the following linear programme using Simplex algorithm. Show the intermediate steps in the form of either the tableau or the dictionary. For each intermediate tableau/dictionary, identify the corresponding basic feasible solution. Maximise ₁ + 37₂ subject to ₁ + 1₂ ≤ 6 - 11 +21₂ ≤8 I1, I2 20

Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
icon
Related questions
Question

Please written by computer source

Past paper help: Optimisation

Q2:
(a) Solve the following linear programme using Simplex algorithm. Show the intermediate
steps in the form of either the tableau or the dictionary. For each intermediate tableau/dictionary,
identify the corresponding basic feasible solution.
Maximise x₁ + 3x2
subject to x₁ + x₂ ≤ 6
-1 +21₂ ≤8
I1, I2 ≥ 0
(b) What is meant by polynomial time complexity in the context of linear programmes? Comment
on the computational complexity of Simplex algorithm, Ellipsoid algorithm and the interior
point methods for solving a linear programme. Which of these is known to run in polynomial
time and which of them are fast in practice?
(c) (i) Write the dual of the following linear program:
Maximise 5x + 2y
subject to - x + y ≤3
x+y=4
2x+y 22
x, y ≥0
(ii) Explain what is the meaning of the sensitivity interval associated with the right-hand
side term of a constraint. If the right-hand side term of a constraint changes, but
without leaving its sensitivity interval, which of the following will remain unchanged
(i) the composition of the basis, or (ii) the value of the basic variables, or (iii) the value
of the objective function?
Transcribed Image Text:Q2: (a) Solve the following linear programme using Simplex algorithm. Show the intermediate steps in the form of either the tableau or the dictionary. For each intermediate tableau/dictionary, identify the corresponding basic feasible solution. Maximise x₁ + 3x2 subject to x₁ + x₂ ≤ 6 -1 +21₂ ≤8 I1, I2 ≥ 0 (b) What is meant by polynomial time complexity in the context of linear programmes? Comment on the computational complexity of Simplex algorithm, Ellipsoid algorithm and the interior point methods for solving a linear programme. Which of these is known to run in polynomial time and which of them are fast in practice? (c) (i) Write the dual of the following linear program: Maximise 5x + 2y subject to - x + y ≤3 x+y=4 2x+y 22 x, y ≥0 (ii) Explain what is the meaning of the sensitivity interval associated with the right-hand side term of a constraint. If the right-hand side term of a constraint changes, but without leaving its sensitivity interval, which of the following will remain unchanged (i) the composition of the basis, or (ii) the value of the basic variables, or (iii) the value of the objective function?
Expert Solution
steps

Step by step

Solved in 2 steps

Blurred answer
Similar questions
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
Basic Technical Mathematics
Basic Technical Mathematics
Advanced Math
ISBN:
9780134437705
Author:
Washington
Publisher:
PEARSON
Topology
Topology
Advanced Math
ISBN:
9780134689517
Author:
Munkres, James R.
Publisher:
Pearson,