(57)【要約】【課題】  複数の線形制約条件の実行可能解の求解プログラム及び求解装置において、制約式数と変数数および制約式数と変数数の加算をそれぞれ乗じた数の定数倍の四則演算以内で解または固定される制約式の最小の組を見い出す。【解決手段】  実行可能解求解装置１は、複数の線形制約式を受け付けるユーザからの入力部１０と、制約式の特異値分解を利用して変形する処理を行う特異値変換部１２と、直行する問題に変換する処理を行う直行化部１３と、直行性を保持しながら実行可能解が含まれる実行可能解を含む条件を逐次固定する処理を行う逐次固定部１４と、逐次固定部１４で固定しきれなかった制約式を固定する最終固定部１５と、前記固定した制約式から解を逆演算をする処理を行う実行可能解再現部１６、および、前記解を出力する表示部１７と、を有する。【選択図】図１
2014089683.tif 000002
【特許請求の範囲】
【請求項１】
線形制約条件の実行可能解を算出する演算装置であって、複数の線形制約式を受け付けるユーザからの入力部１０と、制約式の特異値分解を利用して変形する処理を行う特異値変換部１２と、直行する問題に変換する処理を行う直行化部１３と、直行性を保持しながら実行可能解が含まれる実行可能解を含む条件を逐次固定する処理を行う逐次固定部１４と、逐次固定部１４で固定しきれなかった制約式を固定する最終固定部１５と、前記固定した制約式から解を逆演算をする処理を行う実行可能解再現部１６、および、前記解を出力する表示部１７とを有すること  を特徴とする実行可能解求解装置。
【請求項２】
請求項１に記載の実行可能解求解装置であって、前記線形制約式を、前記入力部を介して受け付けるユーザからの入力部を有し、前記入力を同じくユーザからの入力部に記憶し、前記特異値変換部は入力を正規化した後の特異値変換を前記特異値変換部に記憶し、直行する問題に変換した結果を前記直行化部に記憶し、直行性と正規性を保持するそれぞれの繰り返しに必要となる情報を前記逐次固定部に記憶し、実行可能な内点を取得した後に固定しきれていない部分を固定するために必要となる逐次固定部と同じ形式での情報を最終固定部に記憶し、それぞれを用いて、前記実行可能解を算出すること、を目的とした実行可能解求解装置。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、与えられた複数の線形制約条件の下で、実行可能つまり、すべての線形制約条件を満たすような解の一つを探索する装置に関する。本技術は特に、線形計画問題で必要とする目的関数値の推定がついている際に、そのような複数の線形制約条件を満たす解またはそのために固定する制約式の中で最小の組を探索する必要のある業務を対象とする。
【背景技術】
【０００２】  近年、コンピュータ技術の発展により、例えば効率のよい栄養の摂取などを目的とした献立の立て方などを行うために、与えられた複数の線形制約条件を満たし、ある線形関数に対して栄養摂取の効率などが最大となるような組み合わせを計算する装置が開発されている。これらについて、線形計画問題について、特許文献１や非特許文献１、非特許文献２等にあるように、最悪計算量を考慮して内点法を用いて計算することが現在主流である。また、特許文献２にあるように、制約条件を変化させた場合に関しても、高速に探索する装置が開発されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】  特昭６２−５０２５８０
【０００４】
【特許文献２】  特開２０１０−６１１７９
【非特許文献】
【０００５】
【非特許文献１】  組み合わせ最適化  第２版  Ｂ．コルテ、Ｊ．フィーゲン著、浅野孝夫、浅野泰仁、小野孝男、平田富夫訳  ＳｐｒｉｎｇｅｒＪａｐａｎ  ＩＳＢＮ  ９７８−４−４３１−１００２１−８  ｐ。７１
【０００６】
【非特許文献２】  ＭａｔｈｅｍａｔｉｃａｌＰｒｏｇｒａｍｍｉｎｇＭａｙ１９９０，Ｖｏｌｕｍｅ４７，Ｉｓｓｕｅ１−３，ｐｐ．１７５−２０１  Ｐｒａｖｉｎ  Ｍ．Ｖａｉｄｙａ著
【発明の概要】
【発明が解決しようとする課題】
【０００７】  ところで例えば、献立に関しては、必ずしも摂取効率が最大でなくてもよい場合があり、このような場合には、ある特定の摂取効率以上の解があるか、または一番効率を上げるための障害となっているのはどの献立か、などが必要な場合がある。この場合、ユーザは実行可能解の一つ、あるいは固定する制約式の中で最小の組を要望している。【０００８】  前記参考文献の中で最も効率のよい計算方法である、非特許文献２に関する技術では、実行可能解の一つを得るためにある問題に対して、求解のための繰り返し回数が計算精度や問題に応じた計算量で計算をしなくてはならない。【０００９】  本発明は、実行可能解が計算精度に対して十分広い領域を持っている場合には、求解のための繰り返し回数を計算精度に依存しない計算量で計算することを目的とする。
【課題を解決するための手段】
【００１０】  上記の課題を解決するための装置にかかる発明は、前記複数の線形制約式を、ユーザからの入力を入力部を介して受け付けるステップと、受け付けた制約式を固有値がある範囲内に収まるように変形するステップと、特異値変換をするステップと、特異値変換に直行するように切片を変形し、正規化するステップと、特異値変換と直行した切片を使用して逐次制約式を直行性と正規性を保持しながら制約式を固定していくステップと、内点が求まり、かつ固定する制約式が足りない場合に、逐次制約式を固定していくステップ、および、固定した制約式からの解の逆変換のステップと、前記実行可能解を出力する解出力部と、を有する。【００１１】  また、上記の課題を解決するための方法にかかる発明は、コンピュータを上記の実行可能解求解として機能させるプログラムである。
【発明の効果】
【００１２】  本発明によれば、問題の実行可能解が計算精度に対して十分広い範囲を持っているときに、計算精度によらない回数の四則演算で、実行可能解を再現することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の例示した実施形態に係る実行可能解求解装置１の機能構成を示すブロック図。
【図２】例示した実行可能解求解装置１のハードウェア構成例を示すブロック図
【図３】実行可能解求解の流れを示すフロー図
【図４】実行可能解求解の例示した対象のモデルを説明するための図
【発明を実施するための形態】
【００１４】  以下、本発明の一実施形態について、図面を参照して説明する。
【００１５】  図１は、本発明の一実施形態に係る実行可能解求解装置１の機能構成を示すブロック図である。
【００１６】  本図に示すように、実行可能解求解装置１は、ユーザからの入力部１０、条件記憶部１１、特異値変換部１２、直行化部１３、逐次固定部１４、最終固定部１５、実行可能解再現部１６、および表示部１７を有する。
【００１７】  ユーザからの入力部１０は、例えばユーザがあらかじめ入力した線形制約条件を数値として条件記憶部に格納する。
【００１８】  特異値変換部１２では、条件記憶部１１の各条件を変数の係数に関して正規化した後特異値変換により生成された判定のための行列（以下、便宜のため「判定行列」と呼ぶ）と、逆変換のための行列及び特異値が格納される。
【００１９】  直行化部１３には、判定行列により直行化した切片が正規化されて格納され、両方をあわせて新たな判定行列として格納する。ここで、切片がすべて０である場合には、切片をすべて−１として前記直行化及び正規化処理を施した切片を計算し、おなじく切片がすべて０である場合には、逆変換により得られた解を実行可能解として表示部１７に表示する。
【００２０】  逐次固定部１４では、判定行列と全要素が１であるベクトルを用いて、もっとも固定に適した条件を記憶部に固定し、その条件を使って判定行列の他の条件を直行化することで、新たな判定行列を逐次作成していく。
【００２１】  逐次固定部１４で固定しきれなかった条件を、最終固定部１６で、内部の点より進んで条件を固定していく。
【００２２】  実行可能解再現部１６で、固定した逆算可能な複数の制約式をもとにして、実行可能解を計算する。
【００２３】  計算が終了すると、表示部１７に計算結果をテキスト、あるいは専用のユーザインターフェースなどを用いて表示する。
【００２４】  上記の各種機能を有する実行可能解求解装置１は、例えば図２に示すようなコンピュータにより実現される。
【００２５】  本図に示すように、実行可能解求解装置１は、演算装置１００、揮発性主記憶装置１１０、不揮発性記憶装置１２０、補助記憶装置１３０、通信装置１４０を有する。実行可能求解装置１は例えば一般的なワークステーションである。
【００２６】  演算装置１００は、各種演算を実行するユニットである。演算装置１００は、補助記憶装置１３０から揮発性主記憶装置１１０に読み込んだ所定の実行可能解求解プログラムを実行することにより、各種処理を実行する。
【００２７】  実行可能求解装置１は、例えば、ＯＳ（ＯｐｅｒａｔｉｎｇＳｙｓｔｅｍ）プログラム上で実行可能なアプリケーションプログラムである。
【００２８】  揮発性主記憶装置１１０は、演算装置１００により実行されるプログラムや、プログラムに必要なデータなどを格納する。
【００２９】  不揮発性記憶装置１２０は、実行可能解求解装置１の起動に必要なプログラムなどを格納する。
【００３０】  補助記憶装置１３０は、例えばＨＤＤ（ＨａｒｄＤｉｓｋＤｒｉｖｅ）  などの装置である。
【００３１】  通信装置１４０は、例えばＥｔｈｅｒｎｅｔ（登録商標）などの装置である。
【００３２】  上述した、ユーザからの入力部１０、条件記憶部１１、特異値変換部１２、直行化部１３、逐次固定部１４、最終固定部１５、実行可能解再現部１６は、演算装置１００が揮発性主記憶装置１１０に読み込んだ実行可能解求解プログラムを実行することにより実現される。条件記憶部１１、特異値変換部１２、直行化部１３、逐次固定部１４、最終固定部１５、実行可能解再現部１６のデータは、例えば、揮発性主記憶装置１１０および補助記憶装置１３０に格納される。
【００３３】  また、入力部１０及び表示部１７は、例えば演算装置１００が所定のプログラムを実行して、通信装置１４０を制御することにより実現される。
【００３４】  次に、上記の実行可能解求解装置１により実現される実行可能解求解処理について説明する。
【００３５】  以下では、例として実行可能解求解のモデルをレシピの決定と関連付けて説明を行う。
【００３６】  材料Ａ、材料Ｂがあり、材料Ａの比率はレシピａが１０単位、レシピｂが２単位、レシピｃが３単位、レシピｄが１単位、レシピｅが３単位、レシピｆが０．２単位必要である。また、材料Ａは１０グラム以上、５００グラム以下で作りたい。材料Ｂも同様に、ａが２単位、ｂが１０単位、ｃが２単位、ｄが５単位、ｅが７単位、ｆが８単位、５０グラム以上、７００グラム以下で作りたい。一方、それぞれのレシピ１単位あたりに含まれるたんぱく質は、ａが０．２グラム、ｂが０．３グラム、ｃが０．３グラム、ｄが０．５グラム、ｅが０．１グラム、ｆが０．２５グラムである。このとき、たんぱく質を７５グラム以上とりたい。というレシピの決定モデルを考える。
【００３７】  この場合、線形制約条件は以下のように定式化される。
（制約条件１）  １０ａ＋２ｂ＋３ｃ＋ｄ＋３ｅ＋０．２ｆ＜＝５００
（制約条件２）  −１０ａ−２ｂ−３ｃ−ｄ−３ｅ−０．２ｆ＜＝−５０
（制約条件３）  ２ａ＋１０ｂ＋２ｃ＋５ｄ＋７ｅ＋８ｆ＜＝７００
（制約条件４）  −２ａ−１０ｂ−２ｃ−５ｄ−７ｅ−８ｆ＜＝−５０
（制約条件５）  −０．２ａ−０．３ｂ−０．３ｃ−０．５ｄ−０．１ｅ−０．２５ｆ＜＝−７５
（制約条件６）  −ａ＜＝０
（制約条件７）  −ｂ＜＝０
（制約条件８）  −ｃ＜＝０
（制約条件９）  −ｄ＜＝０
（制約条件１０）  −ｅ＜＝０
（制約条件１１）  −ｆ＜＝０
【００３８】  図３は、実行可能解求解処理の流れを示すフロー図である。本フローは、例えば、通信装置１４０を介したユーザの操作により所定の実行可能解求解処理プログラムが実行されることで開始される。
【００３９】  本フローが開始されると、まず、ユーザからの入力部が、複数の制約条件を受け付ける。（Ｓ１１）
【００４０】  具体的には、ユーザ設定受付部１０は、線形制約条件を入力するためのインターフェースを通信装置１４０を通じて外部の端末に表示させ、外部の端末が入力したテキストデータを、同じく通信装置１４０を通じて受け付ける。
【００４１】  テキストデータは、例えば前記００３７の制約条件のリストに示すように記載される。
【００４２】  その後、入力部１０は受け付けたテキストデータから複数の線形制約式として制約条件を順次抽出し、条件記憶部１１に格納する。なお、受け付けた変数の定義（００３７）も、所定の記憶部（１１）に格納する。
【００４３】  図１のモデルの場合、制約条件１〜１１が、条件記憶部１１に順次格納される。
【００４４】  図３は特異値変換部１２から実行可能回再現部１６の流れを示すフロー図である。以降、簡単のため図３のフロー図を使用して説明する。
【００４５】  特異値変換部１２は、格納された制約式を行列として扱った場合の、行方向の正規化と特異値変換を計算し、結果を格納する。（Ｓ１２）
【００４６】  それから、直行化部１３は、切片をベクトルとして扱った場合の、判定行列による切片の直行化を行う。この際、切片がすべて０になってしまったら、切片をすべて−１に代入して同様に直行化を行い、同じく切片がすべて０になってしまった場合には、切片がすべて−１であるような解を逆変換したものが実行可能解である。（Ｓ１３）
【００４７】  実行可能か判定がつかない場合は逐次固定部１４に移り、実行可能となる制約式のうちで最小の組を見つける。（Ｓ１４）
【００４８】  逐次固定部１４は、要素がすべて−１である制約式の個数と等しい次元のベクトルを用意し、判定行列により、実行可能解のうち一つが必ず上に乗る線形制約条件を逆算する。（Ｓ１４）
【００４９】  必ず上に乗る線形制約条件が算出されない場合、実行可能解が算出されている。この場合、最終固定部１５（Ｓ１５）に進む。
【００５０】  そうでない場合、必ず上に乗る線形制約条件が算出されているので、その条件を固定して、（Ｓ１６）に進む。
【００５１】  このループは必ず行列の階数回未満の繰り返しで終了する。
【００５２】  図４のモデルの場合、ここまでの操作で制約条件（１）、（３）、（５）、（７）、および（１０）が固定される。
【００５３】  最終固定部１５（Ｓ１５）では、実行可能解が算出されている状態である。
【００５４】  この場合、内部から誤差の一番少ないと概算される方向へ向かって進めるか判定し、進める場合にはその制約条件を固定し、判定行列のすべての要素が０でなければ、同様のことを繰り返す。
【００５５】  このループは必ず判定行列の階数回未満の繰り返しで終了する。
【００５６】  図４のモデルの場合、ここまでの操作で更に制約条件（１１）が固定される。
【００５７】  続いて、固定された制約条件から、特異値分解を再度利用して、変換された空間内での実行可能解の一つを取得する。（Ｓ１６）
【００５８】  その後、特異値分解部１２に記録されている変換されたデータを利用して、実行可能解を元の空間に戻す。（Ｓ１７）
【００５９】  図４のモデルの場合、この操作で、それぞれのレシピの量がおおよそ２３．９単位、０単位（作らない）、５０単位、１１０．４単位、０単位（作らない）、０単位（作らない）と定まる。
【００６０】  以上のようにして実行可能解求解処理が実行される。
【００６１】  以上、本発明の一実施形態について説明した。本実施形態によれば、計算精度が実行可能解の持つ空間の広さよりも十分広ければ、計算精度に依存しない四則演算の回数で実行可能解を実現することができる。
【００６２】  すなわち、実行可能解を十分広く持つような線形制約条件の実行可能解のみを必要とするような状況では、本実施形態により、計算精度に依存しない回数の四則演算により解を再現できる。
【００６３】  以上、本発明について、例示的な実施形態と関連させて記載した。多くの代替物、修正および変形例が当業者にとって明らかであることは明白である。したがって、上に記載した本発明の実施形態は、本発明の要旨と範囲を例示することを意図し、限定するものではない。
【産業上の利用可能性】
【００６４】  例えば、本発明は、献立の決定業務に限られず、液体など区切りのないものの重量のみから計画する運搬計画の決定業務にも適用可能である。
【符号の説明】
【００６５】  １：実行可能解求解装置、１０：ユーザからの入力部、１１：条件記憶部、１２：特異値変換部、１３：直行化部、１４：逐次固定部、１５：最終固定部、１６：実行可能解再現部、１７：および表示部、１００：演算装置、１１０：揮発性主記憶装置、１２０：不揮発性記憶装置、１３０：補助記憶装置、１４０：通信装置
【図１】
2014089683.tif 000003
【図２】
2014089683.tif 000004
【図３】
2014089683.tif 000005
【図４】
2014089683.tif 000006