# Optimization Techniques for Design Problems in Selected Areas in WSNs: A Tutorial
## 3 Linear Programming Problems
### Linear Duality  
Associated with any LP is another LP called its _dual_. Knowing how both are related is very important for understanding advanced linear programming and non-linear programming. It gives insights in another important topic which is _sensitivity analysis_, which studies the effect of changing some of the costs in the objective function, or the bound of a constraint function on the feasibility and optimality of an obtained optimal solution. Sensitivity analysis is extremely important when the parameters of an LP have non-zero uncertainty. In the field of WSNs, this can happen in the measurements of the channel coefficients, which have could have some degree of error.  
There is a dual variable (or _dual price_) associated with each constraint in the primal problem. It represents the objective function improvement obtained by relaxing a binding constraint by one unit. A dual variable is nonzero only when the constraint is binding and zero otherwise. This is known as the _complementary slackness_ property connecting the primal and dual problems. The units of the dual prices are the units of the objective function divided by the units of the constraint. Knowing the units of the dual prices can be useful when you are trying to interpret what the dual prices mean.  
The dual of the _primal LP_ given in Equation (1) (with a the minor modification of having \(\mathbf{x}\geq\mathbf{0}\)) is:  
\[w=\underset{\mathbf{y}}{max}\;\mathbf{b}^{T}\mathbf{y} \tag{4a}\] \[\mathbf{A}^{T}\mathbf{y}\geq\mathbf{c}\] (4b) \[\mathbf{y}\geq\mathbf{0} \tag{4c}\]  
where \(\mathbf{y}\in\mathbb{R}^{m}\), and the set of variables \(y_{i}\) are the dual variables.  
In linear duality, the _dual theorem_ states that the optimum objective function value of both the primal and its dual problem are equal, if the primal has a feasible bounded solution. This is an interesting property in its own, as well as a number of important insights the dual theorem has in linear programming.  
Important elements that constitute the dual theorem are:  
1. _Weak Duality:_ For any feasible solution \(\mathbf{x}\) to the primal problem given in Equation (1) and any feasible solution \(\mathbf{y}\) for Equation (4), the (z-value for \(\mathbf{x}\)) \(\geq\) (w-value for \(\mathbf{y}\)). If a feasible solution to either the primal or the dual problems is obtained, weak duality enables its use to obtain a bound on the objective function value of the other problem.
2. _Strong Duality:_ Is a situation when the bounds are equal to each other i.e., \(\mathbf{c}^{T}\mathbf{x}^{*}=\mathbf{b}^{T}\mathbf{y}^{*}\), where \(\mathbf{x}^{*}\) and \(\mathbf{y}^{*}\) are optimum solutions of the primal and dual respectively.
3. If the primal is unbounded the dual is infeasible, and vice versa.
4. A basis \(BV\) in a primal problem that is feasible is also optimal **if and only if** the vector \(\mathbf{\tilde{y}}=\mathbf{c}_{BV}\mathbf{B}^{-1}\) is dual feasible, where:* \(\mathbf{c}_{BY}\) is a \(1\times m\) vector of costs in the objective function of the standard form of the primal problem (1) that corresponds to the basic variables in the optimal tableau (last tableau obtained) and,
* \(\mathbf{B}\) is an \(m\times m\) matrix whose \(j\)th column is the column for the \(j\)th basic variable in the standard form of the primal problem (1).  
Hence, when the optimal solution \(\mathbf{x}^{*}\) for the primal problem is found by the simplex, we also have found the optimal solution \(\mathbf{y}^{*}\) to its dual problem.