LINEAR PROGRAMMING PROBLEM SOLVING SYSTEM, SOLUTION CANDIDATE CALCULATION DEVICE, OPTIMAL SOLUTION CALCULATION DEVICE, THRUSTER CONTROL DEVICE FOR SPACECRAFT, FLYING OBJECT CONTROL DEVICE, AND LINEAR PROGRAMMING PROBLEM SOLVING METHOD

摘要

Known linear programming problem solving systems use interior point methods and simplex methods with iterations and have difficulty in estimating the time taken to find the optimal solution and reliably finding the optimal solution within a control cycle. A dual solution candidate searcher (22) receives an input of information about a constraint coefficient matrix and a cost vector, determines a dual problem of a linear programming problem being a primal problem and all active sets representing combinations of active formulas in constraints of the dual problem, finds, for each of the active sets, a feasible dual solution candidate meeting constraints, and stores the dual solution candidate into a storage (4) in a manner associated with a corresponding one of the active sets. An optimal solution calculation device (3) receives an input of a constraint vector as, selects an optimal one of the active sets as an optimal active set based on an inner product of the constraint vector and the dual solution candidate stored in the storage (4), and finds and outputs a basic feasible solution corresponding to the selected active set as an optimal solution.