0
$\begingroup$
f(x) = -2x1 + 3x2 -2x4 -4x5 + x6 -> max

constraint:

-x1 + 2x2 -x3 -2x4 -2x6 = 2
2x1 + x2 +2x4 -x5 <=4
-x1 -x2 -2x3 + x4 -2x5 + x6 <=6
x1, x2, x3, x4. x4, x5, x6 >= 0

If I replace $f(x)\rightarrow max$ with $f(x)\rightarrow min,$ what is the solvability of the new problem.

My solution is that I will build a new simplex method and show that there is a direction where the $f(x)$ will decrease to infinity and conclude that the problem is unsolvable. But is there any faster way so that I don't have to make a new simplex table?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

The model you are playing with isn't unbounded. In order to turn a maximization problem into a minimization problem is to multiply only the objective function row by negative one. Below we'll look at the given model and what it looks like to convert a maximization problem into a minimization problem, and then we'll look into how we can detect unboundedness before we start using Simplex method (if it was assumed that when you meant was literally replacing the problem with $\min$ and not converting it).


Given Model $\mathbf{\max\to\min}$

For the given model: $$\max z = -2x_1 + 3x_2 -2x_4 -4x_5 + x_6$$ Subject to: $$-x_1 + 2x_2 -x_3 -2x_4 -2x_6 = 2$$ $$2x_1 + x_2 +2x_4 -x_5 \le 4$$ $$-x_1 -x_2 -2x_3 + x_4 -2x_5 + x_6 \le 6$$ $$x_1, x_2, x_3, x_4, x_5, x_6 \ge 0$$

The final solution will be: $$z^*=15,\quad x_1^* = 0 \quad x_2^* = 4, \quad x_3^* = 0$$ $$x_4^* = 0,\quad x_5^* = 0, \quad x_6^* = 3$$

Suppose we turn the model from a $\max$ problem into a $\min$ problem. We can do this by multiplying the objective function row by a negative one like so: $$\max z = -2x_1 + 3x_2 -2x_4 -4x_5 + x_6$$ $$\to\min z = 2x_1 - 3x_2 + 2x_4 + 4x_5 - x_6$$

with the exact same constraints as before. Then, the optimal solution is: $$z^*=-15,\quad x_1^* = 0 \quad x_2^* = 4, \quad x_3^* = 0$$ $$x_4^* = 0,\quad x_5^* = 0, \quad x_6^* = 3$$


Detecting unboundedness

Suppose we have a new minimization objective function where all we did was replace the original $\max$ with $\min$ without conversion like so:

$$\min z = -2x_1 + 3x_2 -2x_4 -4x_5 + x_6$$ $$-x_1 + 2x_2 -x_3 -2x_4 +0x_5 -2x_6 = 2$$ $$2x_1 + x_2 + 0x_3 +2x_4 -x_5 + 0x_6 \quad\le 4$$ $$-x_1 -x_2 -2x_3 + x_4 -2x_5 + x_6 \le 6$$ $$x_1, x_2, x_3, x_4, x_5, x_6 \ge 0$$

Then, if we isolate $x_5$ like so (with the constraints in standard form to make this easier to visualize): $$\min z = -4x_5$$ $$0x_5 -e_1 + a_1 = 2$$ $$-x_5 \quad\le 4$$ $$-2x_5 \le 6$$ $$x_5, a_1, e_1 \ge 0$$

Then we can immediately see, before even starting the Simplex method, that the algorithm will immediately want to pick $x_5$ because it has the highest cost and there is nothing preventing $x_5$ from being endlessly increased. This is how one would detect unboundedness without even having to start the Simplex method.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.