Linear program with parameter $t$ as coefficient of basic variable

Question

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.

Answer 1

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

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}$.

Answer 2

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

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?