# Questions about Simplex method - How should I devide?

I have made a simplex method algorithm in C language and I have some questions about it.

Assume that we have this objective function. $$max: z = c^T x$$ At the subject to: $$Ax <= b \\ x >= 0$$

Then we create our tableau matrix $$T$$.

$$T = \begin{bmatrix} A & I & 0 & b\\ -c^T & 0 & 1 & z \end{bmatrix}$$

$$z = 0$$ to begin with and the $$I$$ is the identity matrix. The last row is one single vector row.

My procedure is easy!

• Step 1: I check the SMALLEST negative value in ONLY $$-c^T$$. If all the elements in vector ONLY $$-c^T$$ are $$> 0$$ then I quit my algorithm, else, I remember what index the smallest negative value have its position. Assume it calls $$indexColumn$$

• Step 2: I take the first row of ONLY $$A$$ at the column $$indexColumn$$ and divide it with the first row of vector ONLY $$b$$. I loop the whole rows in ONLY $$A$$ and ONLY $$b$$ and I check which value will be come smallest. Don't care about the $$I$$ matrix and the $$z$$ value.

$$value = b(i) /A(i, indexColumn)$$

• Step 3: When I find the smallest value on $$indexRow$$ (I call it like that), then I make sure that the the value in $$A(indexRow, indexColum)$$ will be 1 and the rest of $$A(:, indexColumn)$$ will be 0.

By doing that, I do some row operations.

$$\frac{1}{\text{smallest value}}*R_{indexRow} -> R_{indexRow}$$

And the rest $$-\frac{1}{A(\text{i, indexColum})}*R_{indexRow} + R_i-> R_{i}$$

Where $$i \neq indexRow$$

I wrote some C code for that, but I have some issues with it and I wonder if my steps are correct?

https://github.com/DanielMartensson/EmbeddedLapack/blob/master/EmbeddedLapack/src/LinearAlgebra/linprog.c

• What is your question? – copper.hat Nov 24 at 18:57
• @copper.hat If I'm thinking correct in the algorithm. Should I divide $z$ too? – Daniel Mårtensson Nov 24 at 19:10
• The dimension of $c^T$ and the column dimension of $A$ may be inconsistent. How can you construct the $T$ matrix properly? – UnbelieveTable Nov 30 at 9:16
• @UnbelieveTable I have solved this problem :) try the code – Daniel Mårtensson Nov 30 at 13:55
• Okay, you just assume the dimensions to be consistent :P – UnbelieveTable Nov 30 at 17:51