# A proof about feasible solution

$$15.$$ Consider the linear programming problem

Maximize $$z=e^Tx$$

subject to $$Ax\le b$$ $$x\ge0$$

If $$x_1$$ and $$x_2$$ are feasible solutions, show that $$x=\frac{1}{3}x_1+\frac{2}{3}x_2$$is a feasible solution.

$$16.$$ Generalize the previous exercise to show that $$x=rx_1+sx_2$$ is a feasible solution if $$r+s=1$$

(Chap $$1.2$$ exercises $$15\&16$$ of "Elementary Linear Programming With Application" by Bernard Kolman ⋅ Robert E. Beck)

$$15.$$ By Definition.(p.g.$$64$$) that A vector $$x\in\mathbb{R}^n$$ satisfying the constraints of a linear programming problem is called a feasible solution to the problem

Proof.

Assume $$x_1,x_2$$ are feasible solutions, Have

$$Ax_1\le b\wedge x_1\ge0$$$$\wedge Ax_2\le b\wedge x_2\ge0$$

Show $$x$$ is also a fesible solution, that:$$Ax\le b\wedge x\ge0$$ $$\text{WTS }A(\frac{1}{3}x_1+\frac{2}{3}x_2)\le b\wedge \frac{1}{3}x_1+\frac{2}{3}x_2\ge0$$

$$Ax_1\le b\wedge Ax_2\le b$$

Since A is a linear transformation, have the following:

$$\Leftrightarrow A(\frac{1}{3}x_1)\le \frac{1}{3}b\wedge A(\frac{2}{3}x_2)\le \frac{2}{3}b$$

$$\Rightarrow \boxed{A(\frac{1}{3}x_1+\frac{2}{3}x_2)}\le b$$

Second part that $$\boxed{\frac{1}{3}x_1+\frac{2}{3}x_2\ge0} \text{ is trivial} \tag*{\square}$$

$$16.$$ the proof is similar to $$(15.)$$

Proof

Assume $$x_1,x_2$$ are feasible solutions, Have

$$Ax_1\le b\wedge x_1\ge0$$$$\wedge Ax_2\le b\wedge x_2\ge0$$

Show $$x$$ is also a fesible solution, that:$$Ax\le b\wedge x\ge0$$ $$\text{WTS }A(rx_1+sx_2)\le b\wedge rx_1+sx_2\ge0$$

Since A is a linear transformation, have the following:

$$\Leftrightarrow A(rx_1)\le rb\wedge A(sx_2)\le sb$$

$$\Rightarrow \boxed{A(rx_1+sx_2)}\le b$$

Second part that $$\boxed{rx_1+sx_2\ge0} \text{ is trivial} \tag*{\square}$$

Is my proof correct$$?$$

In my proof, I didn't talk about the objective function $$z=e^Tx$$, would this be a problem$$?$$

I think that the problem description has two additional hypotesis: $$r\geq 0$$ and $$s\geq 0$$. But, your proof is correct in these terms. The solution is feasible and this fact do not use the objective function. $$Ax\leq b$$ and $$x\geq 0$$ define the constrained domain of the objective function. You can improve your proof:

$$Ax_1\leq b\implies r.Ax_1\leq r.b ~ (r\geq 0)$$

And

$$Ax_2\leq b\implies s.Ax_2\leq s.b ~(s\geq 0)$$

Summing these two parts and using distributive property

$$A(r.x_1+s.x_2)\leq (r+s).b = b$$

$$r.x_1+s.x_2\geq 0 ~ (r,s\geq 0)$$