0

I just started reading up on linear programming by myself, and am a bit confused by the decision variable coefficients $c_j$, in the objective function $ \sum_j c_jx_j$.

Do they matter? I mean, if I replace $4x + 2y$ with $2x + y$, or with $8x + 4y$, i.e. keep them at the same ratio, will it effect the optimum solution, or just the value of the function itself?

I'm not sure, but surely many Simplex method problems would be easier to calculate if we could take advantage of above, if it were true?

Also, if we didn't know the coefficients, how would we graphically solve it? Right now I'm just practicising the intuition with 2 variables, and if I did just call $c_1 = c_1$ and $c_2 = kc_1$, how would I go about solving it graphically, i.e. with the slopes and everything?

NashEw.
  • 49
Janus Feenf
  • 1
  • Of course the $c_j$ will change the optimum solution. $\max{2x}$ s.t. $-1 \le x \le 1$ does not have the same solution as $\max{-2x}$ s.j. $-1 \le x \le 1$. – MarkG Feb 14 '15 at 22:37
  • How, exactly, are you keeping the same ratio by changing the sign of the $c_j$? If there is only one variable, then obviously you cannot change $c_1$ at all. What I am saying is that if you have two variables, and if you change $c_1$ and $c_2$ into $c_1'$ and $c_2'$ such that $c_1/c_2 = c_1'/c_2'$, will that (in some cases/most cases/never/always) result in the same optimum solution (not value of course)? Also, I am not looking for a general answer, but a "yes, it would happen if ----- but not if -----". – Janus Feenf Feb 14 '15 at 22:55
  • For example, I've been typing some problems into Maple with all types of constraints and several variables, and often changing the $c_j$s but keeping the ratio does not alter the solutions to the problem. – Janus Feenf Feb 14 '15 at 22:59
  • Ah, yes. I read too quickly. You're right, because $\max(mc_1x_1 + mc_2x_2) = m\max(c_1x_1 + c_2x_2)$. – MarkG Feb 14 '15 at 23:08

1 Answers1

0

Provided you don't multiply by a negative value or by zero, two objective functions that are simply multiples of each other will yield the same optimal point (but different values of objective function).

tomi
  • 9,594