On the Properties of the Greatest Subsolution for Linear Equations in the Max-Plus Algebra

Hiroyuki GOTO

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A    No.2    pp.424-432
Publication Date: 2004/02/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Systems and Control
max-plus algebra,  greatest subsolution,  linear programming,  linear equation,  

Full Text: PDF(162KB)>>
Buy this Article

This paper examines the properties of the greatest subsolution for linear equations in the max-plus algebra. The greatest subsolution is a relaxed solution of the linear equations, and gives a unified and reasonable solution whether there exists a strict solution or not. Accordingly, it forms part of a key algorithm for deriving a control law in the field of controller design, and some effective controllers based on the greatest subsolution have been proposed. However, there remain several issues to be discussed regarding the properties of the greatest subsolution. Hence, the main focus of this paper is on the following fundamental properties: 1) Formulation as an optimization problem, 2) Uniqueness of the greatest subsolution, 3) Necessary and sufficient condition for the correspondence of the greatest subsolution with the strict solution. These results could provide flexibility of the controller design based on the greatest subsolution, and facilitate the performance evaluation of the controller. Finally, the uniqueness of the strict solution of the linear equations is examined, and it is confirmed through illustrative examples.