Finding parameters of a linear programming problem

I have the following programming problem:

$\min c_1x_1+c_2x_2$ such that $$x_2 \leq x_1$$$$x_1 \leq 2x_2+2$$$$x_1, x_2 \geq 0$$

How do I show that this problem is feasible and how do i find the condition of $c_1$ and $c_2$ so that the given problem has a finite optimal value using the dual problem?

Can I just set $x_1, x_2=0$ to show feasibility?

And also I the dual is as follows:

$\max 2y_2$ such that $$-y_1+y_2 \geq c_1$$ $$y_1-2y_2 \geq c_2$$$$c_1, c_2 \geq 0$$

Solution 1:

Strong duality holds whenever the primal has an optimal solution, i.e. the problem is not infeasible and its minimum is not $-\infty$.

Consider the plot of the boundaries of your primal problem's feasible region.

I've omitted the shading of the inequalities, but if you can convince yourself that the feasible region is one of the bounded triangles, then all choices of $c_{1}$ and $c_{2}$ will give the same primal and dual solution because the feasible region is bounded and nonempty. In other words, no additional conditions are required on $c_{1}$ and $c_{2}$.

If, on the other hand, the feasible region is another section of the plot, then you have an unbounded solution for some choices of $c_{1}$ and $c_{2}$. Namely, those values of $c_{1}$ and $c_{2}$ which take the objective value to $-\infty$ cause an issue. See if you can reason which $c$ values give you problems from the geometry of the picture.

And yes, to check feasibility it suffices to note that $x_1 = 0$, $x_{2} = 0$ is feasible.