6
$\begingroup$

There is a method of solving a minimization problem using the simplex method where you just need to multiply the objective function by -ve sign and then solve it using the simplex method. All you need to do is to multiply the max value found again by -ve sign to get the required max value of the original minimization problem. My question is there is any condition that must be satisfied on the constraints of the optimization problem to use this method?

$\endgroup$
  • $\begingroup$ Would you be able to edit your question to include an example of your objective function in algebraic terms? $\endgroup$ – danielcharters Apr 10 at 7:45
  • $\begingroup$ @danielcharters many thanks for ur reply. please see my edit I mean is there are any conditions that must be satisfied on the constrains inequality equations to use this method? Sorry about that. $\endgroup$ – John adams Apr 10 at 7:49
  • $\begingroup$ @Johnadams, To solve the optimization problem using the simplex method, it needs to be interpreted as a standard form, in which all of the model constraints are equal. (To do that, adding slack/surplus/artificial variables.). $\endgroup$ – A.Omidi Apr 10 at 9:33
  • $\begingroup$ @A.Omidi but there is no constrain on the inequality itself to use the above-mentioned method? I mean the constrain should be <= or >= to use the above-mentioned method or whatever the inequality is I can use this method? $\endgroup$ – John adams Apr 10 at 9:43
  • $\begingroup$ @Johnadams, for both inequality you mentioned, $<=$ or $>=$, you could use the simplex method. In the $<=$ you need slack variables and in the $>=$ you need surplus and even artificial variables. If your problem has many variables I recommended using optimization software to do that automatically. $\endgroup$ – A.Omidi Apr 10 at 9:48
15
$\begingroup$

It has nothing to do even with linear programming. It's a simple mathematical fact:

$$\min \left( f \left( x \right) \right) = - \max \left( -f \left( x \right) \right)$$

which still holds when you restrict the domain of the function by the constraints (actually to a convex polyhedron in case of LP).

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ "Convex cone" should probably be "convex polytope" (or polyhedron), but the mathematical statement is correct. $\endgroup$ – prubin Apr 10 at 19:38
4
$\begingroup$

The only requirements for the constraints, that I am aware of, when using the simplex algorithm to solve a minimization (and maximization) problem is to include the slack and surplus variables where needed, and the decision variables have to be non-negative. Below is an example to illustrate how to formulate a problem to be solved using the simplex algorithm and how to include slack and surplus variables into your formulation. \begin{align}\min&\quad z = 2x_1 - 3x_2\\\text{s.t.}&\quad x_1+x_2 \leq 4\\&\quad x_1-x_2 \geq 6\\&\quad x_1,x_2 \geq 0\end{align}

The optimal solution to this would be where $ z = 2x_1-3x_2$ is the smallest, but equivalently it can be said that the optimal solution would be where $ -z = -2x_1+3x_2$ is the largest. This is done as the simplex algorithm is used to solve maximization problems, and the formulation now becomes \begin{align}\max&\quad-z = -2x_1 + 3x_2\\\text{s.t.}&\quad x_1+x_2 \leq 4\\&\quad x_1-x_2 \geq 6\\&\quad x_1,x_2 \geq 0\end{align}

We add a slack variable $s_1$ to the first constraint, which now becomes $x_1 +x_2 +s_1 = 4$. Similarly for the second constraint, we add the surplus variable $s_2$, and the constraint now becomes $x_1-x_2 + s_2= 6$.

The formulation, which is now in standard form to be solved using the simplex algorithm, is as follows: \begin{align}\max&\quad-z = -2x_1 + 3x_2\\\text{s.t.}&\quad x_1 +x_2 +s_1 = 4\\&\quad x_1-x_2 + s_2= 6\\&\quad x_1,x_2 \geq 0\\&\quad s_1,s_2 \geq 0.\end{align}

| improve this answer | |
$\endgroup$

Your Answer

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

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