2
$\begingroup$

I have some question related to the Linear Programming problem:

  1. If we have an objective function that needs to be maximized and let the feasible region be unbounded such that there is no finite optimum solution. My question is what is the meaning of "finite" here?

  2. If we need to solve LP using the simplex method, we need to transform any constrain that is written as an inequality equation to equality equation using the addition of the slack variables, so my question is by doing this modification did we change the problem? I mean that we have added an extra variable so I think that we have created a new constraint?

  3. Also to solve the LP using simplex method, we need to have a maximization problem, so if we have to minimize an objective function, in this case to transform it to a maximization problem all we need to do is to negate the coefficients? For example, we need to minimize $3x+y=2$; is this equivalent to maximizing $-3x-y=2$?

$\endgroup$
9
$\begingroup$

Let me answer your questions one by one:

  1. The solution of the linear program $\max x$ is $\infty$. This is an example with not finite optimum solution. This is the same as just having no optimum solution.

  2. When adding slack variables, the optimum value remains unchanged. As an example, you change $x \geq y$ to the equivalent $x = y+z$, where $z \geq 0$.

  3. You never minimize $3x+y=2$. What you minimize is a linear function, not an equation. Minimizing $3x+y$ and maximizing $-(3x+y)$ are the same.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So you mean by max x =infinity is that x is not a finite number hence the statement no finite solution exists for x? $\endgroup$ – John adams Apr 8 at 7:17
  • $\begingroup$ You can think of it in many ways. The bottom line is that the objective function is unbounded. The text you quote seems to be confusing you. You should ignore it. $\endgroup$ – Yuval Filmus Apr 8 at 7:52

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.