2
$\begingroup$

I was wondering if there is any write up that shows how to perform dual simplex with boxed variables where l <= x <= u and preferably with a small example (like 4-5 variable problem with a few iterations).

I tried searching but I keep getting into some dissertations.

$\endgroup$

4 Answers 4

2
$\begingroup$

Pan's book chapter 8: https://link.springer.com/book/10.1007/978-981-19-0147-8 . It has examples.

$\endgroup$
2
$\begingroup$

Two good options:

The second one is a dissertation but I don't understand why this should be an issue.

$\endgroup$
1
  • $\begingroup$ Thanks! I was just hoping for something with simple ratio tests and a bit self contained. Like maybe a 4-5 pages of write up with a few small examples. $\endgroup$
    – Morpheus
    Dec 26, 2022 at 7:05
2
$\begingroup$

A textbook that deals with this at the undergraduate level is Chvatal's Linear Programming. Sadly, it's out of print, but you might be able to find it in an academic library.

$\endgroup$
2
$\begingroup$

For simplicity, you can write the bounded variable as two additional constraints. In the following example, there are four positive variables with a bounded variable $3 \leq x_1 \leq 5$.

\begin{array}{l} \text{Maximize} & Z = -15x_1 - 10x_2 - 8x_3 - 4x_4\\ \text{subject to:}& \\ &-3x_1 - 5x_2 - 3x_3 \leq -5\\ &-5x_1 - 2x_2 - 6x_4 \leq -3\\ &x_1 \geq 3\\ &x_1 \leq 5\\ &x_1, x_2, x_3, x_4 \geq 0, \end{array}

Now, by performing the dual simplex algorithm the problem is solved in four iterations.

enter image description here

To try that yourself please, took a look at this link.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.