[SOLVED] CSE218-LU & Simplex Method

Description

In this assignment, you are required to find solutions of a set of simultaneous linear equations using LU decomposition. A set of n linear equations consisting of n unknowns 𝑥₁, 𝑥₂, 𝑥₃, …, 𝑥_𝑛 can be written in the following form:

 

𝑎₁₁𝑥₁ + 𝑎₁₂𝑥₂ + …… + 𝑎_1𝑛𝑥_𝑛  = 𝑏₁ 𝑎₂₁𝑥₁ + 𝑎₂₂𝑥₂ + ……..+ 𝑎_2𝑛𝑥_𝑛 = 𝑏₂

………………………………………

………………………………………

𝑎_𝑛1𝑥₁ + 𝑎_𝑛2𝑥₂ + ……..+𝑎_𝑛𝑛𝑥_𝑛  = 𝑏_𝑛

In matrix form, this set of equations can be expressed as:

 

AX = B  ……………………………………………………… (1)

Where,

𝑎11 𝑎 A = [ …21 𝑎𝑛1

𝑎12 𝑎22 … 𝑎𝑛2

… … … …

𝑎1𝑛 𝑎2𝑛 … ] 𝑎𝑛𝑛

 

𝑥₁

𝑥²

X = […]

𝑥_𝑛

 

𝑏₁

B = [^𝑏2]

…

𝑏_𝑛

In LU decomposition, you are required to decompose the matrix A such that,

A = LU  ……………………………………………………… (2)

where L is a lower triangular matrix and U is an upper triangular matrix.

Then, from (1) we get,

LUX = B  ……………………………………………………… (3)

Let, UX = Y ………………………………………………….. (4)

Then from (3),

LY = B, where Y is an n × 1 matrix of artificial variables and

 

𝑦₁

𝑦²

Y = […]

𝑦_𝑛

We can solve for Y easily since L is a lower triangular matrix. Substituting the value of Y in (4), we can find the solutions for X.

 

You are required to write a python script named 1.py which will take the matrices A and B as inputs and perform the following tasks:

Task 1: Calculate and print the L matrix.

Task 2: Calculate and print the U matrix.

Task 3: Determine whether the set of linear equations has a unique solution or not. A unique solution is unachievable if an entire row in the U matrix becomes zero. Print “No unique solution” (without the quotes) if no unique solution can be found and terminate the program.

Otherwise, continue to the following tasks.

Task 4: Calculate and print the Y matrix.

Task 5: Calculate and print the X matrix

 

The input will be from a file named in1.txt which must reside in the same directory as that of the python source file 1.py

 

The format of the input file in1.txt will be as followed:

Line 1 will contain an integer n, denoting the number of variables and equations in the set of equations where 2 ≤ n ≤ 100. After that, there will be n lines each containing n double values separated by a space. These n lines constitute the A matrix. Then, there will be n lines each containing a double value. These n lines constitute the B matrix.

 

All outputs (print statements for this assignment) must be in a file named out1.txt. Outputs printed in the console will not be considered for evaluation. The format of the output file will be as followed:

 

First n lines should contain n double values each separated by a space. These n lines should constitute the L matrix.

A blank line should be printed after that.

Next n lines should contain n double values each separated by a space. These n lines should constitute the U matrix.

A blank line should be printed after that.

If there is no unique solution for the set of equation, print “No unique solution” (without the quotes) and terminate the program. Otherwise, there should be n more lines containing a double value in each line. These n lines constitute the Y matrix.

A blank line should be printed after that.

Next n lines should contain a double value in each. These n lines should constitute the X matrix.

A sample input file and output file are attached for your convenience.

 

In this assignment, you have to develop a program implementing the popular simplex method for LP maximization problem only. Please follow the specifications carefully:

 

INPUT

• You need to implement simplex method for maximization problem only. So, you have to consider only the “less than or equal to” inequality relations.
• You must take input from a file named “in2.txt”. The input file must reside in the same directory as that of your python script. The structure of the input file is described below- <Coefficients of Objective function>

<Constraints>

<Constraints>

…

<Constraints>

• The first line will contain the coefficients of the variables in the objective function. If we have n variables, then this line should have n values (can be float) in a space separated manner.
• Then there will be m lines for the m “less than or equal to” constraints. Please note that, no input is necessary for constraints like X₁ ≥ 0. For this assignment, you can assume that, these constraints are present by default.
• Each of these m lines will have n + 1 values (n values for the coefficients of each variable and 1 value for the right hand side) in a space separated manner. For example, for a constraint X₁ + 3X₂ ≤ 15, the input line should be “1 3 15” (For two variables). For a constraint X₂ ≤ 10, the input line should be “0 1 10” (For two variables).

 

Consider the following maximization problem:

Maximize Z = 12X₁ + 10X₂ subject to

5X₁ + 4X₂ ≤ 1700

X₁ + X₂ ≤ 7

4.5X₁ + 3.5X₂ ≤ 1600

X₁ + 2X₂ ≤ 500

X₁, X₂ ≥ 0

For this problem, the input file should look like the following:

12 10

5 4 1700

1 1 7

4.5 3.5 1600

1 2 500

OUTPUT

• You must output the tableu of each step. The precision of the double values should be upto 2 decimal places after the decimal point. You can output in the console or in a file, which ever one you prefer.
• You must output the maximum value of the objective function along with the corresponding value of the variables.