Weak duality for maximization problems asserts that the if $\mathbf{p}$ is a feasible solution to the dual problem, and $\mathbf{x}$ is a feasible solution to the primal problem, then
$$\mathbf{p}^{T}\mathbf{b} \geq \mathbf{c}^{T}\mathbf{x}.$$
Unfortunately, the classic corollary in this case states that:
- If the optimal cost of the primal problem is unbounded, then the dual is infeasible.
- If the optimal cost of the dual problem is unbounded, then the primal is infeasible.
You want something like the converse of the first statement in the corollary. If you show that the dual is infeasible, then the primal must be unbounded or infeasible by weak duality, and then you just have to show that the primal is feasible.
I assume that $A \in \mathbb{M}_{m_1,m_2}(\mathbb{R})$
The variables of the problem are : $X= (x_1,...x_{m_1},v)$ ($v$ is a variable not a constant which is what you needed in your answer)
$$
\begin{aligned}
&\max v = C^TX\\
&\text{s.t. } v-(A^Tx)_j = (DX)_j&\leq0&\text{, for }j=1,..,m_2\\
&(DX)_{m_2+1}=x_1+...+x_{m_1}&=1&\text{, for }j=m_2+1\\
&x_i&\geq 0&\text{, for }j=1,...,m_1\\
\end{aligned}
$$
In the standard form, the problem is as follow :
$$
\begin{aligned}
&\max C^TX\\
&\text{subject to }\\
&(DX)_j&\leq0&\text{, for }j=1,..,m_2\\
&(DX)_{m_2+1}&=1&\text{, for }j=m_2+1\\
&x_i&\geq 0&\text{, for }j=1,...,m_1\\
\end{aligned}
$$
Where :
$X = (x_1,...,x_{m_1},v)$ is the variable of the problem
$$D = \begin{pmatrix}
-a_{1,1} & .. & -a_{1,m_1}&1\\
: & & &:\\
-a_{m_2,1} & .. &-a_{m_2,m_1} &1\\
1&..&1&0
\end{pmatrix} = \begin{pmatrix}
-A^T&1\\
1&0
\end{pmatrix}
$$
$B = (b_1,...,b_{m_2},b_{m_2+1})=(0,..,0,1)$ same as $ b_1 = 0$, $b_2 = 0$,...,$b_{m_2}=0$, $b_{m_2+1}=1$ as required in the standard form
$C = (c_1,...,c_{m_1},c_{m_1+1})=(0,..,0,1)$ which means that ($c_1 = 0$, $c_2 = 0$,..., $c_{m_1} = 0$, $c_{m_1+1}=1$)
You can then use the general recipe for LP duals (page 7 in your lecture) :
The dual variable has the same length as $B$. I will call it : $Y = (y_1,...,y_{m_2},u)$
$$
\begin{aligned}
&\max B^TY = u\\
&\text{s.t. }(D^TY)_i = u-(Ay)_i&\geq0&\text{, for }i=1,..,m_1\\
&(D^TY)_{m_1+1}=y_1+...+y_{m_2}&=1\\
&y_i&\geq 0&\text{, for }i=1,...,m_2\\
\end{aligned}
$$
because :
$$
D^T = \begin{pmatrix}
-A&1\\
1&0
\end{pmatrix}
$$
Best Answer
A dual pair includes a maximization problem and a minimization problem. Weak duality says that a feasible solution to the maximization problem has value at most the value of a feasible solution of the minimization problem. That is, it does not give you $b^T y \leq c^T x$.
If you like, you can turn the problem of maximizing $c^Tx$ to negative the minimum of $-c^Tx$, and derive a different looking dual which would then be a maximization problem (with its end result still multiplied by $-1$). If you apply weak duality to this pair and work through the algebra you will get something essentially equivalent to what weak duality gave you for the original problem because of the negative signs. You will not get $b^Ty \leq c^T x$.