We have the following linear program:
$ \max \;\{ d^Tx \; | \; Ax \le b, x \ge 0 \; \} $
This is our abstract definition of a linear program (maximize). Assume this linear program has an optimal solution. The lexicographical program is now defined as follows:
$ \max \;\{c^Tx\; | \; x \in \arg \max \;\{ d^Tx \; | \; Ax \le b, x \ge 0 \; \} \}$
Now i want to reformulate this second program, the lexicographical one in a equivalent linear program, but i dont have a clue. Can somebody give me a hint or an idea?
You can add the constraint that there exists is a dual variable $y$ for the first problem such that $d^T x \geq b^T y$. The full problem becomes: $$\max\{c^T x \mid Ax\leq b, \; d^T x \geq b^T y, \; A^Ty \geq d, \; x \geq 0, \; y \geq 0\}.$$