9
$\begingroup$

While I do understand the general workings of the Big-M-method I am struggling with the following sample exercise, in which the Big-M-method has to be used to find a first feasible solution:

\begin{alignat}2\max&\quad 10x_1+4x_2\\\text{s.t.}&\quad x_1+x_2+x_3=4\tag1 \\&\quad 2x_1-x_2-x_4=2\tag2\\&\quad -x_1+x_5=-1\tag3\\&\quad x_1+x_3-x_4+x_5=4\tag4\\&\quad x_1,\cdots,x_5 \geq 0\tag5\end{alignat}

I am not sure how to introduce the artificial variable for the Big-M. The only problem here seems to be the negative value on the right side of equation #3. So I would multiply with $-1$. Now it looks as though we have a negative slack variable $x_5$ which would allow us to add another variable $y_1$ as part of the Big-M-Method. But I doubt if $x_5$ can be considered a slack variable here since it is given as part of the task and is also specified as $\geq 0$. So I just need to know if I am on the wrong track and if so, how to introduce the Big-M the right way

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
4
$\begingroup$

All your constraints are equality. So, add an artificial variable to each constraint (let's call them $a_i \quad i\in\{1,..,4\}$). Now all these artificial variables need to be in the objective function with a coefficient of Big-M. Since you are maximizing, you want to make sure using any of them will penalize your objective function (so, you add them with negative sign). So, your objective function becomes: $$ \max \quad 10x_1 +4x_2 - Ma_1 - Ma_2 - Ma_3 - Ma_4$$

The artificial variables play the role of your initial basis. So, you need to standardize your simplex table and make sure they are zero in the objective row. After doing that, just solve the simplex problem as you normally do.

If you like to check a simple example, take a look at this example

Improve this answer
$\endgroup$
7
  • 4
    $\begingroup$ Since the constraints are equalities, you cannot assume the artificials are nonnegative. So you really should have two artificials per equation (as when modeling absolute values). $\endgroup$
    – prubin ♦
    Commented Nov 25, 2019 at 22:10
  • 1
    $\begingroup$ @prubin I tried to find an example to confirm that but any example I searched and found (from MIT, columbia, Brown, and some others) they all introduce one positive artificial variable for equality constraints too. Am I forgetting something here? $\endgroup$
    – EhsanK ♦
    Commented Nov 25, 2019 at 22:46
  • 1
    $\begingroup$ One positive variable for equalities requires an assumption about the sign of the RHS IMO. $\endgroup$
    – ErlingMOSEK
    Commented Nov 26, 2019 at 11:10
  • 1
    $\begingroup$ @JohnEren You add artificial variables ($a$) to make a new space where the origin point is part of your solution so you start from there. So, you add it to a constraint that you don't have the available $+1s$ for your initial basis (where $s$ is a slack). You have that $+1$ in $\le$, you have $-1$ for $\ge$ (from a surplus) and you add an $a$ there. You also need it for equality constraint to satisfy the requirement. In your example, if constraint 4 was $x_1+x_3-x_4+x_6=4$ and you don't see $x_6$ anywhere else, then that $x_6$ could play the role in the basis for you (no need for $a$). $\endgroup$
    – EhsanK ♦
    Commented Nov 26, 2019 at 18:45
  • 1
    $\begingroup$ @prubin that was assumed as the OP mentioned in the question "...The only problem here seems to be the negative value on the right side of equation #3. So I would multiply with −1. ..." $\endgroup$
    – EhsanK ♦
    Commented Nov 29, 2019 at 15:37

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.