MTH355 Solving Linear Equations and Optimization Using LU Decomposition and Linear Programming, TMA, Singapore

Question 1

(a) Consider the following system of linear equations:

5x₁ + 4x₂ + 17x₃ = 3
−4x₁ + 4x₂ − 7x₃ = 6
x₁ + x₃ = −5

(i) Write down matrix A and vector b, where Ax = b. Apply the LU decomposition technique on A. Find the elementary matrices E_ij.
(10 marks)

(ii) Based on the LU decomposition of A, solve the system of linear equations.
(5 marks)

(iii) Use the LU decomposition of A to find the first column of A⁻¹.
(5 marks)

(b) Consider the following system of linear equations:

−2x₁ + 8x₂ + 4x₃ = 5
4x₁ − 3x₂ + 8x₃ = 6
6x₁ − 2x₂ + 3x₃ = −1

Apply the conditions for a set of linear equations. Starting from (x₁, x₂, x₃) = (−1, 0, 1), perform three iterations of the Gauss-Seidel iterative scheme. Keep all values up to five decimal places. Provide enough details for the iterative process.
(5 marks)

Question 2

A company manufactures two types of products, A and B, which require four types of resources, Q, R, S, and T, for production. The key facts about the two types of product and the resources required to produce them are summarised in Table Q2. The company must decide how many units of Product A and Product B it must produce to maximise its profit.

Table Q2

(a) Formulate a linear programming model for the company to make the decision.
(10 marks)

(b) Solve the formulated linear programming problem
(10 marks)

(c) If the amount of resource T available increases to 80, what is the optimal solution to the problem formulated in Question 2(a)?
(5 marks)

Question 3

Consider the following linear programming problem:

Maximise 3x₁ + 9x₂ + 5x₃

x₁ + x₂ + x₃ ≤ 10
3x₁ + 5x₂ + 2x₃ ≤ 23
6x₁ + 7x₂ + 10x₃ ≤ 60
x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0

(a) Solve the given linear programming problem using the simplex method.
(15 marks)

(b) Formulate the dual of the given linear programming model and determine the optimal objective value of the dual problem.
(10 marks)

Question 4

Consider the following linear programming problem:

Minimise 2x₁ + 4x₂ + 5x₃

x₁ + 3x₂ + 4x₃ ≥ 10
x₁ + 6x₂ + 7x₃ = 18
x₁ ≥ 0, x₂ ≥ 0, x₃ free

(a) Formulate the dual problem of the given linear programming model.
(8 marks)

(b) Compute the optimal objective value of the dual problem.
(7 marks)

(c) Using the optimal solution obtained in Question 4(b) and the complementary slackness optimality conditions, solve for the optimal solution of the primal model.
(10 marks)