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?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Would you be able to edit your question to include an example of your objective function in algebraic terms? $\endgroup$– danielchartersApr 10, 2020 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 adamsApr 10, 2020 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.OmidiApr 10, 2020 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 adamsApr 10, 2020 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.OmidiApr 10, 2020 at 9:48
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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).
-
1$\begingroup$ "Convex cone" should probably be "convex polytope" (or polyhedron), but the mathematical statement is correct. $\endgroup$– prubin ♦Apr 10, 2020 at 19:38
$\begingroup$
$\endgroup$
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}
