Suppose I have an LP formulation as such:


$\min\ \ \sum\limits\_{i,j,t}\ w\_{ij}x\_{ijt} (\frac{t-r\_j}{p\_{ij}}+0.5)$


$\sum\limits\_{i,t}\frac{x\_{ijt}}{p\_{ij}}=1\,\forall\ j$


$\sum\limits\_{j}x\_{ijt}\leq 1\,\forall \ i,t$


$x\_{ijt}\geq 0\ \forall\ i,j,t\geq r\_j$


For understanding the context of its formulation, please refer [here](http://www.cse.iitd.ernet.in/~amitk/305_Kumar.pdf).


My question is how to proceed to compute its dual problem. Now for standard notation like


$\min\ p'x$


$Ax\geq b, x\geq 0$


The dual is simply


$\max\ b'u$


$A'u\leq p, u\geq 0$


But the primal problem of interest has inequalities of the less than ($\leq$) form as well as equality constraints. So how do we proceed with this kind of non-standard form?



Finding dual of a scheduling LP formulation
Two alternative approaches:


1. Rewrite the primal problem in standard form by replacing equality with two inequalities and multiplying both sides of $\le$ inequalities by $-1$ to reverse the sense to $\ge$.
2. For equality constraints in the primal, use free variables in the dual, and for $\le$ constraints in the primal, use $\le 0$ variables.
The second approach is simpler. See [this paper](https://pdfs.semanticscholar.org/f066/07117d318758b694df0f7de08c6c4dafe1da.pdf).


