Treffer: Simultaneous solution of linear equations and inequalities in max-algebra

Let a⊕b=max(a,b) and a⊗b=a+b for a,b∈R. Max-algebra is an analogue of linear algebra developed on the pair of operations (⊕,⊗) extended to matrices and vectors. The system of equations A⊗x=b and inequalities C⊗x≤d have each been studied in the literature. We consider a problem consisting of these two systems and present necessary and sufficient conditions for its solvability. We also develop a polynomial algorithm for solving max-linear program whose constraints are max-linear equations and inequalities.