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.

    L'invention est motivée par le fait que les systèmes conventionnels de résolution de problèmes de programmation linéaire utilisent une méthode de points intérieurs ou une méthode du simplexe accompagnée d'une répétition, et il était donc difficile d'estimer le temps nécessaire jusqu'à ce qu'une solution optimale soit acquise et de garantir l'acquisition de la solution optimale au cours d'un cycle de commande. La présente invention comporte: une unité (22) de recherche de solution duale candidate qui acquiert, avec comme entrée des informations concernant une matrice de coefficients de contraintes et un vecteur de coût, un problème dual dans lequel un problème de programmation linéaire est un problème principal et tous les ensembles valides indiquant des combinaisons valides entre des conditions de contraintes sont des expressions du problème dual, acquiert une solution duale candidate exécutable dans laquelle une condition de contrainte devient valide pour chacun des ensembles valides, associe les solutions duales candidates aux ensembles valides, et stocke les solutions duales candidates dans une unité (4) de stockage; et un dispositif (3) de calcul de solution optimale qui sélectionne, avec comme entrée un vecteur de contrainte, un ensemble valide optimal d'après un produit interne des solutions duales candidates stockées dans l'unité (4) de stockage et le vecteur de contrainte, et acquiert et délivre une solution fondamentale exécutable correspondant à l'ensemble valide sélectionné en tant que solution optimale.

    従来の線形計画問題求解システムは、反復を伴う内点法やシンプレックス法を用いるため、最適解が得るまでに必要な時間の見積り、制御サイクル内で最適解を得る保証が困難。制約係数行列および費用ベクトルの情報を入力として、線形計画問題を主問題とする双対問題および双対問題の制約条件の式のうち有効な組合せを表す有効セットを全て求め、有効セットごとに制約条件が有効となる実行可能な双対解候補を求めて有効セットと関連付けて双対解候補を記憶部(4)に記憶する双対解候補探索部(22)と、制約ベクトルを入力とし、記憶部(4)に記憶された双対解候補と制約ベクトルとの内積から最適となる有効セットを選択し、選択した有効セットに対応する実行可能基底解を最適解として求めて出力する最適解算出装置(3)とを備える。


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    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


    Weitere Titelangaben:

    SYSTÈME DE RÉSOLUTION DE PROBLÈMES DE PROGRAMMATION LINÉAIRE, DISPOSITIF DE CALCUL DE SOLUTIONS CANDIDATES, DISPOSITIF DE CALCUL DE SOLUTION OPTIMALE, DISPOSITIF DE COMMANDE DE PROPULSEURS POUR ENGIN SPATIAL, DISPOSITIF DE COMMANDE D'OBJET VOLANT, ET PROCÉDÉ DE RÉSOLUTION DE PROBLÈMES DE PROGRAMMATION LINÉAIRE
    線形計画問題求解システム、解候補算出装置、最適解算出装置、宇宙機のスラスタ制御装置および飛翔体制御装置並びに線形計画問題の求解方法


    Beteiligte:
    ASANO YUTA (Autor:in) / NISHIYAMA TAKEHIRO (Autor:in)

    Erscheinungsdatum :

    28.11.2019


    Medientyp :

    Patent


    Format :

    Elektronische Ressource


    Sprache :

    Japanisch


    Klassifikation :

    IPC:    G06F ELECTRIC DIGITAL DATA PROCESSING , Elektrische digitale Datenverarbeitung / B64G Raumfahrt , COSMONAUTICS