# Assume an LP has 2 optimal solutions $u$ and $v$. Show for any t in [0,1] that $tu+(1-t)v$ is also optimal

Considering an LP with:

\begin{align} &\text{max}\ \ c\cdot x \\ &Ax\le b\\ & x\geq 0 \\ \end{align}

Assume this LP has two optimal solutions $$u$$ and $$v$$. Show for any $$t \in [0,1]$$ that $$tu+(1-t)v$$ is also an optimal solution. First show $$tu-(1-t)v$$ has the same value as $$u$$ in the objective function. Then show $$tu+(1-t)v$$ is feasible solution to the LP.

So I know since they're both optimal functions that means that $$u$$ and $$v$$ must have the same objective function value otherwise one isn't the optimal point. I don't know if it's a proof, but $$tu+(1-t)v$$ has to be feasible because it runs parallel to the points $$u$$ and $$v$$ which are both optimal so that means that $$tu+(1-t)v$$ is also optimal? But I don't think that's a sufficient proof if a proof at all.

We can show $$tu+(1-t)v$$ is feasible by $$A(tu+(1-t)v)=A(tu+(1-t)v)=Atu+(1-t)Av \le bt+(1-t)b=b$$ from the domain of x if it's in the epigraph of the function, but I don't know about showing $$tu+(1-t)v$$ as an optimal solution. I'd just say it is cause it runs parallel to $$u$$ and $$v$$, in the direction of the gradient?

To prove the objective value is optimal, notice $$c(tu+(1-t)v)=tcu+cv-tcv$$ We know $$cu=cv$$ since both $$u, v$$ are optimal. Therefore, $$tcu+cv-tcv=cv$$ so $$tu+(1-t)v$$ has an optimal objective value.