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

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.

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

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

• Thank you. What would be the sequence of basic optimal solutions? – user441848 Dec 5 '18 at 21:06
• $(12/7,12/7)$, $(3,0)$, $(3,0)$, $(3,0)$,....... – Kuifje Dec 5 '18 at 21:09
• 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$ ? – user441848 Dec 5 '18 at 21:29
• 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)$. – Kuifje Dec 5 '18 at 22:25
• 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)$ ? – user441848 Dec 5 '18 at 22:33

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?

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