Suppose we have a polyhedron with vertices (extreme points) $e_1 = (4,5)$, $e_2 = (0,3)$ , $e_3=(1,2)$, $e_4=(6,0)$ and extreme direction $d_1 = (1,0)$. I want to write the vector $(10,1)$ as convex combination of the vertices and a non-negative combination of the extreme direction.
Attempt
To see If Im understanding this material, what they are asking is that I need to find $\lambda_i$ and $\mu$ so that
$$ (10,1) = \lambda_1 (4,5) + \lambda_2 (0,3) + \lambda_3 (1,2) + \lambda_4 (6,0) + \mu (1,0) $$
satisfying the conditions $\lambda_1+\lambda_2+\lambda_3+\lambda_4=1$ and $\lambda_i, \mu \geq 0$
But, this would involve solve a system of 3equations and three 5 unknowns. For example, can I choose some points before doing gauss jordan elimination? for example, I can make $\mu = 9$ so that LHS becomes $(1,1)$. Is this the right approach to this problem?
Let us first look at a picture of the vertices and the point which we want to describe as a conic combination of the vertices and the extreme direction:
We observe that the $y$-coordinate of $X=(10,1)$ lies on the line between $D=(6,0)$ and $C=(1,2)$. Our extreme direction $d_1=(1,0)$ will not change the $y$-coordinate but only move a point in $x$-direction. Thus, we need to find a point with the same $y$-coordinate as $X$ and then simply add the required amount of $d_1$.
We find hence want to find the point on the line between (6,0) and (1,2) with $y$-coordinate 1. Hence, we seek $E=(\alpha,1)$ with $\lambda (6,0) +(1-\lambda)(1,2)=(\alpha,1)$ for some $\lambda \in (0,1)$. We thus need to solve for $\lambda$:
$$\lambda \cdot 0 + (1-\lambda)\cdot 2 =1$$
We obtain $\lambda = \frac{1}{2}$ and thus the point $E=(3.5,1)$. Now, all we have to do is add 6.5 times $d_1$ to $E$ to reach $X=(10,1)$. In other words, we can write $X=(10,1)$ as
$$0 \cdot (4,5) +0 \cdot (0,3) +\frac{1}{2} \cdot (1,2) +\frac{1}{2} \cdot (6,0) + 6.5 \cdot (1,0) = (10,1).$$
Since $0+0+\frac{1}{2}+\frac{1}{2}=1$ and $6.5 \ge 0$ we have indeed written $X$ as a conic combination of the $e_i$ and $d_1$.
Note that I picked points $C$ and $D$ in the picture to obtain a point with $y$-coordinate equal to 1. Instead of $C$ you could also pick any of the other points. You do, however, always need the point $D$.