CSE218 LU Simplex Method-Solved

𝑎11𝑥1 + 𝑎12𝑥2 + …… + 𝑎1𝑛𝑥𝑛  = 𝑏1 𝑎21𝑥1 + 𝑎22𝑥2 + ……..+ 𝑎2𝑛𝑥𝑛 = 𝑏2

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

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

𝑎𝑛1𝑥1 + 𝑎𝑛2𝑥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𝑛

… ]

𝑎𝑛𝑛
 

𝑥1

𝑥2

X = […]

𝑏1

B = [𝑏2]

…

𝑏𝑛  

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

A = LU  ............................................................... 

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

Then, from (1) we get,

LUX = B  ............................................................... 

Let, UX = Y ........................................................... 

Then from 

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

 
𝑦1

𝑦2

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  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.

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

INPUT
(i)  You need to implement simplex method for maximization problem only. So, you have to consider only the “less than or equal to” inequality relations.

(ii) 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 X1 ≥ 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 X1 + 3X2 ≤ 15, the input line should be “1 3 15” (For two variables). For a constraint X2 ≤ 10, the input line should be “0 1 10” (For two variables).

Consider the following maximization problem:

Maximize Z = 12X1 + 10X2 subject to

5X1 + 4X2 ≤ 1700

X1 + X2 ≤ 7

4.5X1 + 3.5X2 ≤ 1600

X1 + 2X2 ≤ 500

X1, X2 ≥ 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
(i)   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. 

(ii) You must output the maximum value of the objective function along with the corresponding value of the variables.