Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


529 users

0 votes
How to get an integer solution from rational solution in simplex algorithm?
in * TF "Emb. Sys. and Rob." by (640 points)
recategorized by

1 Answer

0 votes
Best answer
This is explained on slides 77-79 (Simplex Algorithm on Integer Numbers). The idea is as follows: We first compute a rational solution. For every variable that has a non-integer solution, we enforce that the simplex algorithm will push it to either the next greater or next lower integer by changing the bound of that variable. We may have to repeat that for the other variables until an integer solution is found.
by (166k points)
selected by
Thanks for the explanation.

Is it possible to have multiple solutions for a given set of equations, like if we pivot a violating variable with other variable as taken in solution, the answer comes different.
Yes, that is possible. The simplex algorithm traverses the corners of the polyhedron specified by the inequalities and you may choose different paths for that traversal by choosing the variables for pivoting. As there may be several solutions, you may find also different ones this way.
Imprint | Privacy Policy