Let $a \oplus b=\max(a,b)$ and $a \otimes b = a+b$ for $a,b\in{\mathbb{R}}$. Max-algebra is an analogue of linear algebra developed on the pair of operations $(\oplus, \otimes)$ extended to matrices and vectors. The system of equations $A \otimes x=b$ and inequalities $C \otimes x \leq 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.
max-algebra, linear equations and inequalities, max-linear programming
15A06, 15A39, 90C26, 90C27