I am working on the following exercise:
Consider the following LP $(P)$:
$$\min_{x \in \mathbb{R}^n} x_1 + 2x_2 + \ldots + nx_n$$
with
\begin{align} x_1 &\ge 1 \\ x_1 + x_2 &\ge 2 \\ x_1 + x_2 + x_3 &\ge 3 \\ &\vdots \\ x_1 + x_2 + \ldots + x_n &\ge n\\ x_i \ge 0 \quad (\forall i) \end{align}
Find the dual of $(P)$ and explain why strong duality applies here, i.e. there are solutions to both problems and their optimal values are equal.
For a) I would suggest to add slack variables to obtain:
$$A := \begin{bmatrix} &1 &0 &0 &0 &\ldots &0 &-1 &0 &0 &0\\ &1 &1 &0 &0 &\ldots &0 &0 &-1 &0 &0\\ &1 &1 &1 &0 &\ldots &0 &0 &0 &-1 &0\\ &\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots &\vdots &\vdots &\vdots\\ &1 &1 &1 &1 &\ldots &1 &0 &0 &0 &-1\\ \end{bmatrix}.$$
Then for $$b := c:= \begin{bmatrix} 1 \\ 2 \\ 3 \\ \vdots \\ n \end{bmatrix} $$
we have found the standardform of $(P)$:
$$\min_{x \in \mathbb{R}^{2n}} \ c \cdot x \quad \text{ such that } \quad Ax = b \text{ and } x \ge 0$$
The dual of $(P)$ is thus
$$\max_{\lambda \in \mathbb{R}^m} \ b\lambda \quad \text{ such that } \quad A^T \lambda \le c.$$
Concernign the strong duality: I know that the existence of an optimal solution for one problem implies the existence of an optimal solution for the other and that both function values are then equal. However, I do not see how I could argue that $(P)$ or $(D)$ has an optimal solution. Could you help me?
By inspection, $(n,0,\dots,0)$ is optimal for $(P)$, with objective value $n$. Now can you find a dual feasible solution that has the same objective value? By complementary slackness, the dual constraint associated with $x_1$ will be satisfied with equality.