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

摘要

Conventional linear programming problem solving systems use an internal point method or a simplex method accompanied by repetition, and thus it has been difficult to estimate the time necessary until an optimal solution is acquired and to guarantee acquisition of the optimal solution within a control cycle. The present invention is provided with: a dual solution candidate search unit (22) that acquires, with information about a constraint coefficient matrix and a cost vector as an input, a dual problem in which a linear programming problem is a main problem and all valid sets indicating valid combinations among constraint condition expressions of the dual problem, acquires an executable dual solution candidate in which a constraint condition becomes valid for each of the valid sets, associates the dual solution candidates with the valid sets, and stores the dual solution candidates in a storage unit (4); and an optimal solution calculation device (3) that selects, with a constraint vector as an input, an optimal valid set on the basis of an inner product of the dual solution candidates stored in the storage unit (4) and the constraint vector, and acquires and outputs an executable basic solution corresponding to the selected valid set as an optimal solution.