I just started learning LP and I saw this Q in my textbook:

$$ min : -x -y \\ S.T. : x + 2y \le 3, 2x +y \le 3, x \ge 0, y \ge 0 $$

It is easy to see that the polygon created from these constraints can't have a negative coordinate. In my textbook it says the answer is $(0,0)$ since $-0 -0 = 0$ and this is the minimum value of the target function (i.e. $f(x,y) = -x -y$).

Why is that the minimum? If I choose any other values (S.T. the constraints are satisfied) I can get, for example, $(1,1)$ which will result in $-1 -1 = -2 < 0$!

Another thing that I don't understand - would there be a difference if my function was different? If the min is $(0,0)$ - wouldn't it be the case for any other $f(x,y) = a*x + b*y$ for any other $a,b$?

  • $\begingroup$ Just using an online LP solver (I used comnuan.com/cmnn03/cmnn03004 for no good reason), the minimum is $x=1$, $y=1$ as you suggest. Have you checked the errata for the textbook? (And made sure you read the question right of course :D) $\endgroup$ – Luke Mathieson Nov 27 '17 at 8:26
  • $\begingroup$ Checked. Twice :-( I just can't understand this. About my 2nd Q - the min will be the same for f(x,y) = a(x+y) as well, wouldn't it [a < 0]? $\endgroup$ – CIsForCookies Nov 27 '17 at 9:18

Is easy to prove that $(0,0)$ is the maximum of your suggested target function, so it may be an errata of your text.

Your second question is way more interesting, the answer is no, if you change your target function to another linear function the maximum or minimum may change, suppose you change your target function to $x+y$, the minimum now is $(0,0)$, previously it was $(1,1)$.

However, as you suggested in the comments, if you only change your function by a positive scaling factor $a$, the maximum/minimum remain the same. This is easy to prove as $$\alpha\leq \beta\iff a\alpha\leq a\beta$$ holds (I leave the details to you).

In general, there are branches of linear programming called "postoptimization" and "sensitivity analysis" in which your second question is studied in detail, for example, describing algorithms to obtain an optimal solution of the same problem for various target functions in almost the same running time of solving just one problem.

| cite | improve this answer | |
  • $\begingroup$ I talked to a friend. She said that the function describes a line (-a -b = k), and that I actually need to minimize k under the constrains, which means k Is 0, and k is actually the target function. Does that make sense? $\endgroup$ – CIsForCookies Nov 27 '17 at 16:08
  • $\begingroup$ For me that makes no sense. A visual trick to see whats happening in an LP problem is to imagine you are mesuring something in the space, for example, temperature (target function), and you are told to find the coldest point of a certain region (feasible region). This can be very difficult if the region or the "temperature" function are weird. But, when the region is "good" (in this context good means that the nonnegative points of an affine manifold) and the target function is linear there are algorithms (for example the Simplex method) to solve the problem, and thats the LP branch of study $\endgroup$ – Álvaro G. Tenorio Nov 27 '17 at 16:28

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.