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

A spacecraft, comprising:

• thrusters equal in number to a variable dimensionality;
• and
• a thruster control circuit for a spacecraft including processing circuitry configured by software as
• a thruster drive computator to generate a constraint vector varying at any time based on a translation force and a torque to be provided by the spacecraft, to output information about the constraint vector varying at any time, and to generate, based on a resultant variable vector, a signal to be output to the thrusters and to control an operation of the thrusters, and
• an optimal solution calculation circuit configured as a linear programming problem solving system to find a solution to a linear programming problem of optimizing an objective function of a variable vector and a cost vector under constraints represented by simultaneous formulas having a given constraint coefficient matrix, the constraint vector varying at any time, and the variable vector including a variable having the variable dimensionality different from a constraint dimensionality of the constraint vector varying at any time, the optimal solution calculation circuit including
• an active set dual solution storage including a memory to store information about a dual problem of the linear programming problem being a primal problem and active sets representing combinations of active formulas in dual constraints being constraints in the dual problem, in a manner associated with a feasible dual solution candidate meeting the constraints for each of the active sets,
• a constraint vector receiver to receive the information about the constraint vector varying at any time,
• an optimal active set computator to select an optimal one of the active sets as an optimal active set based on an inner product of the constraint vector and the feasible dual solution candidate stored in the storage, and
• an optimal solution computator to find and output, as an optimal solution, a basic feasible solution corresponding to the active set selected by the optimal active set computator,
• wherein
• the constraint dimensionality is smaller than the variable dimensionality,
• the variable vector is nonnegative,
• the simultaneous formulas are simultaneous equations,
• the dual constraints are inequality constraints equal in number to the variable dimensionality and represented by a transposed matrix of the constraint coefficient matrix,
• the optimal active set computator finds an active set maximizing the determined inner product as the optimal active set, and
• the optimal solution represents injection quantity for the thrusters.

A flying object, comprising:

• rotors equal in number to a variable dimensionality;
• and
• a rotor control circuit including processing circuitry configured by software as
• a rotor drive computator to generate a constraint vector varying at any time based on a translation force and a torque to be provided by the rotors, to output information about the constraint vector varying at any time, and to generate, based on a resultant variable vector, a signal to be output to the rotors and to control an operation of the rotors, and
• an optimal solution calculation circuit configured as a linear programming problem solving system to find a solution to a linear programming problem of optimizing an objective function of a variable vector and a cost vector under constraints represented by simultaneous formulas having a given constraint coefficient matrix, the constraint vector varying at any time, and the variable vector including a variable having the variable dimensionality different from a constraint dimensionality of the constraint vector varying at any time, the optimal solution calculation circuit including
• an active set dual solution storage including a memory to store information about a dual problem of the linear programming problem being a primal problem and active sets representing combinations of active formulas in dual constraints being constraints in the dual problem, in a manner associated with a feasible dual solution candidate meeting the constraints for each of the active sets,
• a constraint vector receiver to receive the information about the constraint vector varying at any time,
• an optimal active set computator to select an optimal one of the active sets as an optimal active set based on an inner product of the constraint vector and the feasible dual solution candidate stored in the storage, and
• an optimal solution computator to find and output, as an optimal solution, a basic feasible solution corresponding to the active set selected by the optimal active set computator,
• wherein
• the constraint dimensionality is greater than the variable dimensionality,
• the simultaneous formulas are simultaneous inequalities,
• the dual constraints are equality constraints equal in number to the variable dimensionality and represented by a transposed matrix of the constraint coefficient matrix and are nonnegative constraints on a solution vector to the dual problem,
• the optimal active set computator finds an active set minimizing the determined inner product as the optimal active set, and
• the optimal solution is provided as a rotor thrust command to each of the rotors.