linear programmingoptimization
I wondered if someone could explain to me the intuition of what it would mean if the objective function in a Linear Programme is a multiple of one of the constraints?
I am thinking it means that the lines are parallel with the objective function being at a different contour. Does this imply anything about the uniqueness of an optimal solution? Would appreciate some intuition
Suppose your feasible region looks as shown below :
Lets assume we're maximizing the objective function $C=ax+by$
Notice that, for different values of C, you get different straight lines of varying y intercepts but they will have same slope :
Only the lines that cut through the feasible region satisfy all the given constraints because you can cookup x,y values such that they fall in both feasible region and the objective function.
From the second picture it is obvious that the the maximum value of $ax+by=C$ occurs when the y intercept of these feasible lines is maximum. Consequently the vertex A gives the maximum value for the objective function.
Including a constant term in the objective does not change the set of optimal solutions, and this is true even for nonlinear programming. Some solvers might not allow it, so you can just omit it, solve, and add it back to your final objective value.
Best Answer
It means indeed that the optimal solution is not unique, if it exists. The corresponding constraint must be active. In a linear program with two variables it can be shown graphically. An example. Le´t suppose you have the following program:
$\textrm{max} \ Z=500x_{1}+300x_{2}$
s.t.
$15x_{1}+5x_{2}\leq 300$
$10x_{1}+6x_{2}\leq 240$
$8x_{1}+12x_{2}\leq 450$
$x_{1},x_{2}\geq 0$
We can solve the objective funktion for $x_2$: $ \, \, \, x_2=\frac{Z}{300}-\frac53x_1$. This function has a slope of $\color{red}{-\frac53}$. And we can solve the second constraint (equality) for $x_2$ as well:
$10x_{1}+6x_{2}=240\Rightarrow x_2=40\color{red}{-\frac53}x_2$
For more detailed information with a graph to this example see here.