0

How can I find the range of an added parameter in the linear programming problem which preserve the original optimal solution remaining to be the optimal solution? such as: $$ Max \space\space\space 6x_1+x_2+\theta x_3 $$ $\theta$ is the added parameter, it used to be zero, and we get the original optimal solution $(x^{*}_{1},x^{*}_{2})$ of the problem , the constrain conditions hasn't been changed.

In fact, I am dealing with the following problem in the picture, and I think I can use $y_1=-3x_2+4x_3, \space y_2=x_2+x_3$ to transform the problem into the former type. but I still don`t know how to deal with it. I have a toilsome method to just calculate all the vertex and construct the equality between the value of different vertex to get the max and min of $\theta$ of the problem. If I take $\theta$ into the simplex method to calculate directly, there would be too many classified discussion based on the value of $\theta$, Is there any simple method for such a problem? enter image description here

maopao
  • 21

1 Answers1

1

First, make some coordinate substitutions to get $\max\ x_1+x_2+\theta x_3$. Wlog, assume $\theta>0$. Maximize $x_3$ such that $(x_1^*,x_2^*,x_3)$ satisfies the inequalities. Assume that only one inequality is active in the sense of preventing a higher value of $x_3$. This inequality determines a plane. Solve the equation of the plane for $x_3$. Calculate the maximal directional derivative of $x_3$ w.r.t. $x_1$ and $x_2$. The inverse of this derivative is $\theta_{max}$.

NeitherNor
  • 1,210