2
$\begingroup$

Consider the following linear problem

$$\max tx_1+x_2\\ s.t. 4x_1+3x_2\le12 \\ 3x_1+4x_2\le12\\ x_1,x_2\ge0$$

where the parameter $t$ grows exponentially $t\in[1,\infty).$

Find the sequence of basic optimal solutions.

Attempt:

First we should convert to standar form

$$\max tx_1+x_2\\ s.t.\ 4x_1+3x_2+x_3=12 \\ 3x_1+4x_2+x_4=12\\ x_1,x_2\ge0$$

Then, I am not sure how should I proceed.

I've solved exercise where you have say $3$ instead of $t$ and then you change $3$ by $4$ and then analyze how the final simplex tableau changes, as it is a coefficient of a basic variable the optimality and factibility might both be affected.

But this could be fixed by using again simplex method or dual-simplex in the final tableau.

My question is how should I proceed in this case where there is a $t$ instead of a number?

Could someone help me please?

I would really appreciate any help you're willing to provide. Thank you.

$\endgroup$
  • $\begingroup$ Just iterate through a couple of times, and see how the process depends on $t$, and where you end up $\endgroup$ – gt6989b Dec 5 '18 at 19:45
2
$\begingroup$

You can work geometrically. The domain is given in the picture below :

enter image description here

Now, the gradient of $f(x_1,x_2) = tx_1+x_2$ equals $\pmatrix{t\\1}$.

If $t=1$, the optimum lies at the intersection of $3x_1+4x_2=12$ and $4x_1+3x_2=12$, i.e. $(\frac{12}{7},\frac{12}{7})$.

If $t=\frac{4}{3}$, the gradient is orthogonal to $4x_1+3x_2=12$, which means that all points on this line are optimal, in particular $(\frac{12}{7},\frac{12}{7})$ and $(3,0)$.

So for any $t\in [1,\frac{4}{3}[$, $(\frac{12}{7},\frac{12}{7})$ is the optimal point.

Then, as $t$ increases, the gradient points towards $(3,0)$.


Note that this matches gt6989b's answer : solving $3t = \frac{12(t+1)}{7}$ for $t$ yields $t=\frac{4}{3}$.

$\endgroup$
  • $\begingroup$ Thank you. What would be the sequence of basic optimal solutions? $\endgroup$ – user441848 Dec 5 '18 at 21:06
  • 1
    $\begingroup$ $(12/7,12/7)$, $(3,0)$, $(3,0)$, $(3,0)$,....... $\endgroup$ – Kuifje Dec 5 '18 at 21:09
  • $\begingroup$ ok. Could you explain this part if $t=1$ the optimum lies at the intersection of $3x_1+4x_2=12$ and $3x_1+4x_2=12$ ? $\endgroup$ – user441848 Dec 5 '18 at 21:29
  • 1
    $\begingroup$ If $t=1$, the gradient is $(1,1)$, so it points in the direction of the line $x_2=x_1$. Since $(12/7,12/7)$ lies on this line, the gradient points towards $(12/7,12/7)$. $\endgroup$ – Kuifje Dec 5 '18 at 22:25
  • $\begingroup$ ok I understand that part, I don't see how the gradient points towards $(3,0)$ when $t$ increases; there is a constant $1$, how can you know that it will point towards $(3,0)$ ? $\endgroup$ – user441848 Dec 5 '18 at 22:33
1
$\begingroup$

Here is one high-level approach. Your region looks like this:

LP Plot

Easy to see $(0,0)$ produces the optimization value 0, so only 3 points are in play: $(3,0),(0,3)$ and $(12/7,12/7)$.

Which one will get chosen and how will the optimization converge?

UPDATE

You are maximizing $f(x_1,x_2) = tx_1 + x_2$. It produces the following values at the vertices:

$$ f(0,3) = 3, f(3,0) = 3t, f(12/7,12/7) = (t+1)12/7 $$

As $t$ evolves, which of the values is larger?

$\endgroup$
  • $\begingroup$ $(3,0)$ will get chosen, I don't know how the optimization will converge. How? $\endgroup$ – user441848 Dec 5 '18 at 20:07
  • 1
    $\begingroup$ Nice picture ! ^^ $\endgroup$ – Kuifje Dec 5 '18 at 20:15
  • $\begingroup$ @Alt. see update, not so simple $\endgroup$ – gt6989b Dec 5 '18 at 20:18
  • $\begingroup$ $f(3,0)=3t$ is the larger value $\endgroup$ – user441848 Dec 5 '18 at 20:26
  • $\begingroup$ Am I correct? ${}$ $\endgroup$ – user441848 Dec 5 '18 at 20: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.