0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.