(57)【要約】【課題】非線形計画問題を求解する際に、区分線形近似の近似範囲を適切に設定し、実用時間内に精度の高い最適解が得られるようにする。【解決手段】配合計画立案装置１００は、非線形計画問題を求解する手法により、複数の異なる性質を持つ原材料を配合して製品を製造する製造プロセスにおいて、配合割合を決定変数とした配合計画を立案する。制約条件設定部１０３は、非線形制約条件を表わす非線形関数に中間変数を導入して分離可能関数に変換し、一変数関数の和の形で表現する。また、制約条件設定部１０３は、ランダムサンプリングにより、非線形制約に準じた条件を満たすように、配合割合のサンプルを複数生成し、これらサンプルを用いることにより、中間変数の上下限値を設定する。そして、制約条件設定部１０３は、中間変数の上下限値の範囲で、分離可能関数を構成する関数を区分線形近似して、制約条件を設定する。【選択図】図１
2020086706.tif 000002
【特許請求の範囲】
【請求項１】
線形制約条件と非線形制約条件とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解するための非線形計画問題の演算装置であって、
前記非線形制約条件を表わす非線形関数に中間変数を導入して分離可能関数に変換した上で区分線形近似して、制約条件を設定する設定手段と、
前記設定手段で設定した制約条件の下で前記非線形計画問題を求解する求解手段とを備え、
前記設定手段は、ランダムサンプリングにより、前記非線形関数を構成する変数のうち中間変数を除いた独立変数のサンプルを複数生成し、前記サンプルを用いることにより、前記中間変数の上下限値を設定して、当該上下限値の範囲で、前記分離可能関数を構成する関数を区分線形近似することを特徴とする非線形計画問題の演算装置。
【請求項２】
前記設定手段は、前記非線形制約条件に準じた条件を満たすように、前記非線形関数を構成する変数のうち中間変数を除いた独立変数のサンプルを複数生成することを特徴とする請求項１に記載の非線形計画問題の演算装置。
【請求項３】
前記設定手段は、前記非線形関数を、前記中間変数を導入して一変数関数の和の形で表現することを特徴とする請求項１又は２に記載の非線形計画問題の演算装置。
【請求項４】
前記非線形計画問題は、複数の原材料を配合して製品を製造する製造プロセスにおいて、配合割合を決定変数とする配合計画問題であり、
前記設定手段は、ランダムサンプリングにより、配合割合をランダムに生成して、配合割合のサンプルを複数生成することを特徴とする請求項１乃至３のいずれか１項に記載の非線形計画問題の演算装置。
【請求項５】
前記設定手段は、前記分離可能関数を構成する各関数に対して、前記中間変数の上下限値の設定、及び区分線形近似を繰り返すことを特徴とする請求項１乃至４のいずれか１項に記載の非線形計画問題の演算装置。
【請求項６】
線形制約条件と非線形制約条件とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解するための非線形計画問題の演算方法であって、
設定手段が、前記非線形制約条件を表わす非線形関数に中間変数を導入して分離可能関数に変換した上で区分線形近似して、制約条件を設定する設定ステップと、
求解手段が、前記設定ステップで設定した制約条件の下で前記非線形計画問題を求解する求解ステップとを有し、
前記設定ステップでは、ランダムサンプリングにより、前記非線形関数を構成する変数のうち中間変数を除いた独立変数のサンプルを複数生成し、前記サンプルを用いることにより、前記中間変数の上下限値を設定して、当該上下限値の範囲で、前記分離可能関数を構成する関数を区分線形近似することを特徴とする非線形計画問題の演算方法。
【請求項７】
線形制約条件と非線形制約条件とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解するためのプログラムであって、
前記非線形制約条件を表わす非線形関数に中間変数を導入して分離可能関数に変換した上で区分線形近似して、制約条件を設定する設定手段と、
前記設定手段で設定した制約条件の下で前記非線形計画問題を求解する求解手段としてコンピュータを機能させ、
前記設定手段は、ランダムサンプリングにより、前記非線形関数を構成する変数のうち中間変数を除いた独立変数のサンプルを複数生成し、前記サンプルを用いることにより、前記中間変数の上下限値を設定して、当該上下限値の範囲で、前記分離可能関数を構成する関数を区分線形近似することを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、線形制約条件と非線形制約条件とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解するための非線形計画問題の演算装置、方法及びプログラムに関する。
【背景技術】
【０００２】
数理計画問題は、制約条件の下で目的関数を最小化又は最大化する問題である。その中でも、制約条件及び目的関数のうち少なくともいずれか一方に非線形関数を含むものを非線形計画問題と呼ぶ。
例えば製鉄業におけるコークスや焼結鉱の製造プロセスでは、各工場が保有する複数の原材料を配合して、製品を製造する。この場合に、目標となる製品の特性値や生産量を満たすように配合計画を立案しなければならない。また、製造プロセスにおける操業条件を満たすように配合計画を立案しなければならない。
このように目標となる製品の特性値や生産量、操業条件を満たすようにするための制約条件は、数学的に最適解を求めることが難しい関数を含む場合が多い。例えばコークスの品質を予測する推定式には、コークス強度等の構造的特性を表わす式が含まれるが、この推定式には、実験や理論に基づいた非線形関数が使用される。このように製造プロセスにおける数理計画問題の多くは、複雑な非線形計画問題となるため、実用時間内に精度の高い最適解を得ることが難しかった。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−１７５８０４号公報
【非特許文献】
【０００４】
【非特許文献１】Applied Mathematical Programming, Stephen P. Bradley, Addison-Wesley, 1977
【非特許文献２】多変数関数を一変数の和で表現するアルゴリズムI，山村清隆、村山泰子，電子情報通信学会技術研究報告，CAS，回路とシステム 93(102)，67-74，1993-06-19
【非特許文献３】多変数関数を一変数の和で表現するアルゴリズムII，山村清隆、村山泰子，電子情報通信学会技術研究報告，CAS，回路とシステム 93(102)，75-82，1993-06-19
【非特許文献４】藤江哲也, "整数計画法による定式化入門," オペレーションズ・リサーチ : 経営の科学，vol. 57，no. 4，pp. 190-197，Apr. 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非線形計画問題の求解手法として、いくつかの提案がなされている。
例えば特許文献１には、複数種の配合原材料を混合する配合計画を作成するためのシミュレータと、配合原材料の需給バランス制約を表す数式モデル、及び、混合後の性状制約を表す数式モデルを構築するモデル構築部と、モデル構築部により構築された数式モデルを用い、所定の目的関数に基づいて最適化計算を行い、シミュレータに対する指示を算出する計画部とを備え、混合後の性状制約を表す数式モデルが非線形の数式を含む場合、前記非線形の数式に代えて線形の数式を導入して数式モデルを定式化し、その線形の数式を含む数式モデルを用いた計画部による求解結果が前記非線形の数式を含む数式モデルを満たすか否かを確認する手法が開示されている。
【０００６】
また、非特許文献１には、非線形関数に補助変数（中間変数とも呼ばれる）を導入し、分離可能関数に変換した後に、区分線形関数で近似して、混合整数計画問題として定式化する手法が示されている。ここで、分離可能関数とは、一変数関数の和の形で表現できる多変数関数である。非線形関数を分離可能関数に変換することにより、区分線形近似の関数評価回数が、大幅に減少することが知られている（非特許文献２、非特許文献３）。区分線形関数は、区分的に定義される関数で、各区間が一次関数となっているものをいう。非線形関数を区分線形関数で近似することは区分線形近似と呼ばれる。以下では、非線形関数を区分線形関数で近似する全範囲を近似範囲と称し、区分線形関数で近似する各区間（一つの一次関数で近似する各区間）を近似区間と称する。
【０００７】
しかしながら、特許文献１の手法では、非線形計画問題を線形計画問題に簡略化して近似するため、近似誤差が発生し、十分な精度の解が得られないおそれがある。
【０００８】
また、非特許文献１の手法では、分離後の非線形関数それぞれに近似範囲を設定する必要があるが、適切な近似範囲が設定されない場合、区分線形関数の発散や、近似精度の悪化を招くおそれがある。
【０００９】
本発明は上記のような点に鑑みてなされたものであり、非線形計画問題を求解する際に、区分線形近似の近似範囲を適切に設定し、実用時間内に精度の高い最適解が得られるようにすることを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するための本発明の要旨は、以下のとおりである。
［１］  線形制約条件と非線形制約条件とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解するための非線形計画問題の演算装置であって、
前記非線形制約条件を表わす非線形関数に中間変数を導入して分離可能関数に変換した上で区分線形近似して、制約条件を設定する設定手段と、
前記設定手段で設定した制約条件の下で前記非線形計画問題を求解する求解手段とを備え、
前記設定手段は、ランダムサンプリングにより、前記非線形関数を構成する変数のうち中間変数を除いた独立変数のサンプルを複数生成し、前記サンプルを用いることにより、前記中間変数の上下限値を設定して、当該上下限値の範囲で、前記分離可能関数を構成する関数を区分線形近似することを特徴とする非線形計画問題の演算装置。
［２］  前記設定手段は、前記非線形制約条件に準じた条件を満たすように、前記非線形関数を構成する変数のうち中間変数を除いた独立変数のサンプルを複数生成することを特徴とする［１］に記載の非線形計画問題の演算装置。
［３］  前記設定手段は、前記非線形関数を、前記中間変数を導入して一変数関数の和の形で表現することを特徴とする［１］又は［２］に記載の非線形計画問題の演算装置。
［４］  前記非線形計画問題は、複数の原材料を配合して製品を製造する製造プロセスにおいて、配合割合を決定変数とする配合計画問題であり、
前記設定手段は、ランダムサンプリングにより、配合割合をランダムに生成し、配合割合のサンプルを複数生成することを特徴とする［１］乃至［３］のいずれか一つに記載の非線形計画問題の演算装置。
［５］  前記設定手段は、前記分離可能関数を構成する各関数に対して、前記中間変数の上下限値の設定、及び区分線形近似を繰り返すことを特徴とする［１］乃至［４］のいずれか一つに記載の非線形計画問題の演算装置。
［６］  線形制約条件と非線形制約条件とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解するための非線形計画問題の演算方法であって、
設定手段が、前記非線形制約条件を表わす非線形関数に中間変数を導入して分離可能関数に変換した上で区分線形近似して、制約条件を設定する設定ステップと、
求解手段が、前記設定ステップで設定した制約条件の下で前記非線形計画問題を求解する求解ステップとを有し、
前記設定ステップでは、ランダムサンプリングにより、前記非線形関数を構成する変数のうち中間変数を除いた独立変数のサンプルを複数生成し、前記サンプルを用いることにより、前記中間変数の上下限値を設定して、当該上下限値の範囲で、前記分離可能関数を構成する関数を区分線形近似することを特徴とする非線形計画問題の演算方法。
［７］  線形制約条件と非線形制約条件とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解するためのプログラムであって、
前記非線形制約条件を表わす非線形関数に中間変数を導入して分離可能関数に変換した上で区分線形近似して、制約条件を設定する設定手段と、
前記設定手段で設定した制約条件の下で前記非線形計画問題を求解する求解手段としてコンピュータを機能させ、
前記設定手段は、ランダムサンプリングにより、前記非線形関数を構成する変数のうち中間変数を除いた独立変数のサンプルを複数生成し、前記サンプルを用いることにより、前記中間変数の上下限値を設定して、当該上下限値の範囲で、前記分離可能関数を構成する関数を区分線形近似することを特徴とするプログラム。
【発明の効果】
【００１１】
本発明によれば、非線形計画問題を求解する際に、区分線形近似の近似範囲を適切に設定し、実用時間内に精度の高い最適解を得ることができる。
【図面の簡単な説明】
【００１２】
【図１】実施形態に係る配合計画立案装置の機能構成を示す図である。
【図２】実施形態に係る配合計画立案装置による配合計画の立案方法の処理を示すフローチャートである。
【図３】図２のフローチャートにおける制約条件の設定処理の詳細を示すフローチャートである。
【図４】図３のフローチャートにおけるランダムサンプリングの詳細を示すフローチャートである。
【図５】変数の範囲を決定するイメージを示す図である。
【図６】中間変数ｖ4の範囲を求めた結果を示し、中間変数ｖ4と２ｌｏｇ(ｖ4)との関係を示す図である。
【図７】中間変数ｖ4と２ｌｏｇ(ｖ4)との関係を示す図である。
【発明を実施するための形態】
【００１３】
以下、添付図面を参照して、本発明の好適な実施形態について説明する。
線形制約条件（以下、単に線形制約と呼ぶ）と非線形制約条件（以下、単に非線形制約と呼ぶ）とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解する際に、非線形制約を表わす非線形関数が多変数関数である場合、この非線形関数を、中間変数を導入して一変数関数の和の形で表現することで、分離可能関数に変換することが考えられる。これにより、非線形関数の次元を減らし、区分線形近似に必要な変数を減らすことができる。
【００１４】
このようにして分離した後の一変数関数を区分線形近似するためには、その近似範囲を決定しなければならない。一変数関数の近似範囲を大きくすると、近似精度を保つためにより多くの近似区間が必要となる他、近似対象となる非線形関数が発散する可能性がある。したがって、できるだけ狭い近似範囲を事前に決定することが望ましい。しかしながら、近似範囲の決定は、非線形制約を考慮しなければならず、元の非線形計画問題と同等に難しい。
【００１５】
そこで、本発明者は、一変数関数の近似範囲を決定する手法を確立した。以下に詳述するが、ランダムサンプリングにより、非線形関数を構成する変数のうち中間変数を除いた独立変数のサンプルを複数生成する。その際、当該独立変数のサンプルは、非線形制約に準じた条件を満たすようにする生成する。そして、これらサンプルを用いることにより、中間変数の上下限値を設定して一変数関数の近似範囲を決定する。これにより、非線形計画問題を求解する際に、区分線形近似の近似範囲を適切に設定し、実用時間内に精度の高い最適解を得ることができる。
【００１６】
以下に述べる実施形態では、製鉄業におけるコークスや焼結鉱の製造プロセスのように、複数の異なる性質を持つ原材料（以下、銘柄と呼ぶ）を配合して製品を製造する製造プロセスに対して本発明を適用した例を説明する。
図１に、実施形態に係る配合計画立案装置１００の機能構成を示す。配合計画立案装置１００は、本発明を適用した非線形計画問題の演算装置として機能し、複数の異なる性質を持つ銘柄を配合して製品を製造する製造プロセスにおいて、配合割合を決定変数とし、目標となる製品の特性値や生産量、操業条件を満たし、かつ、製造に係るコストを最小化する配合計画を立案する。つまり、最適な配合割合を求める。本実施形態で取り扱う配合計画問題では、制約条件の少なくとも一部が、非線形関数で表わされる非線形制約となっている。
【００１７】
入力部１０１は、例えばデータベース１０８から配合計画を立案する上で必要になる各銘柄の性状情報（性質や状態に関する情報）、操業条件情報、コスト情報等のデータを取り込む。
【００１８】
分割数設定部１０２は、非線形関数を区分線形近似する際の分割数を設定する。分割数設定部１０２は、例えばオペレータの指示に従って分割数を設定するようにしてもよいし、予め定められた分割数の範囲内で自動的に分割数を設定するようにしてもよい。
【００１９】
制約条件設定部１０３は、入力部１０１で取り込んだデータに基づいて、目標となる製品の特性値や生産量、操業条件を満たすための制約条件を設定する。
ここで、制約条件設定部１０３は、関数変換部１０３ａと、上下限値設定部１０３ｂとを備える。
関数変換部１０３ａは、非線形制約を表わす非線形関数が、分離可能関数であるか否かを判断する。分離可能関数とは、ｎ次元のユークリッド空間の任意のｘ＝（ｘ1，ｘ2，・・・，ｘn）Tに対して、関数ｆが下記のかたちで表わされる関数である。非線形関数が分離可能関数でない場合には、非線形関数に中間変数を導入して分離可能関数に変換し、一変数関数の和の形で表現する。
【００２０】
【数１】
2020086706.tif 000003
【００２１】
非線形関数を分離可能関数に変換すると、一つの非線形関数が、複数の一変数関数で表現される。ここで、各一変数関数には非線形関数が含まれる場合がある。このため、定式化のためには、各一変数関数に対して区分線形近似をしなければならない。ただし、非線形関数を分離するときに用いた中間変数は、変数の取りうる範囲が定まっていない。したがって、もし、区分線形近似の独立変数に中間変数が存在する場合は、事前に中間変数の取りうる範囲を定めるために、区分線形関数の近似範囲を決めなければならない。ここで、一変数関数の近似範囲を大きくすると、近似精度を保つためにより多くの近似区間が必要となる他、非線形関数の形状によっては非線形関数が発散する（±∞の値になる）領域も近似対象になり得る。これらの問題を避けるために、近似精度は保ちつつ、近似範囲をできるだけ狭い範囲に事前に決定することが望ましい。
そこで、上下限値設定部１０３ｂは、ランダムサンプリングにより、非線形制約に準じた条件を満たすように、非線形関数を構成する変数のうち中間変数を除いた独立変数（例えば決定変数である配合割合）のサンプルを複数生成し、これらサンプルを用いることにより、中間変数の上下限値を設定する。
そして、制約条件設定部１０３は、関数変換部１０３ａで変換した分離可能関数を構成する関数（本実施形態では一変数関数）が非線形関数である場合には、上下限値設定部１０３ｂで設定した上下限値の範囲で、当該一変数関数を区分線形近似して、制約条件を設定する。
【００２２】
目的関数設定部１０４は、入力部１０１で取り込んだデータに基づいて、製造に係るコストを最小化する目的関数を設定する。
【００２３】
求解部１０５は、制約条件設定部１０３及び目的関数設定部１０４で設定した配合計画問題を求解する。
【００２４】
判定部１０６は、求解部１０５による求解結果が妥当なものか否かを判定する。その結果、求解結果が妥当なものである場合、当該求解結果を確定する。求解結果が妥当なものでない場合は、分割数設定部１０２で分割数を変更して、制約条件設定部１０３、目的関数設定部１０４及び求解部１０５による配合計画問題の求解を繰り返す。
求解結果の妥当性を判定する仕組みとして、求解部１０５で得られた配合割合を、制約条件設定部１０３による区分線形近似後の関数に代入して得られた計算値と、元の非線形制約に代入して得られた理論計算値とを比較する。そして、計算値と理論計算値との差が所定の条件を満たすまで、分割数設定部１０２で分割数を変更して、制約条件設定部１０３、目的関数設定部１０４及び求解部１０５による配合計画問題の設定及び求解を繰り返す。
【００２５】
出力部１０７は、判定部１０６での求解結果を出力装置１１０に送信する。
【００２６】
データベース１０８は、配合計画を立案する上で必要になる各銘柄の性状情報、操業条件情報、コスト情報等のデータを格納する。なお、ここでデータベース１０８からデータを取り込む例を示したが、それ以外にも、例えばネットワークを介して外部機器からデータを取り込んだり、ユーザが直接入力したデータを取り込んだりする形態であっても構わない。
【００２７】
入力装置１０９は、ポインティングデバイスやキーボード等である。
出力装置１１０は、出力部１０７から送信された求解結果を出力するディスプレイ等の表示装置、音声情報を出力するスピーカ等の音声出力装置等であってもよい。また、出力装置１１０は、出力部１０７から送信された求解結果を不図示の記憶領域に保存、登録する記憶装置等であってもよい。
【００２８】
次に、配合計画立案装置１００による配合計画の立案方法を説明する。
図２は、実施形態に係る配合計画立案装置１００による配合計画の立案方法の処理を示すフローチャートである。
ステップＳ１で、入力部１０１は、例えばデータベース１０８から配合計画を立案する上で必要になる各銘柄の性状情報、操業条件情報、コスト情報等のデータを取り込む。例えば表１に示すように、各銘柄の配合割合に関して上下限値の情報が取り込まれる。
【００２９】
【表１】
2020086706.tif 000004
【００３０】
ステップＳ２で、分割数設定部１０２は、非線形関数を区分線形近似する際の分割数Ｋを設定する。なお、区分線形近似すべき非線形関数が複数ある、或いは分離可能関数に用いられる変数が複数ある場合、分割数は非線形関数ごと、分離可能関数に用いられる変数ごとに設定してもよい。
【００３１】
ステップＳ３で、制約条件設定部１０３は、ステップＳ１で取り込んだデータに基づいて、目標となる製品の特性値や生産量、操業条件を満たすための制約条件を設定する。
本実施形態において制約条件は、式（１）のように線形関数で表わされる線形制約と、式（２）のように非線形関数で表わされる非線形制約とに分けられる。
【００３２】
【数２】
2020086706.tif 000005
【００３３】
式（１）は、制約条件の中でも線形となる制約条件を表わす式である。式（１）のｘは決定変数である配合割合を表わすＭ次元の列ベクトルであり、ベクトルの要素は各銘柄の配合割合に相当する。式（１）のＡはＮ行Ｍ列の行列であり、Ａのすべての要素は実数値をとるものとする。ｂはＮ次元の列ベクトルであり、実数値をとるものとする。
式（２）のｇi(ｘ)は非線形関数であり、ｉは制約の種類を表わす。例えば非線形関数ｇi(ｘ)は、製鉄業であればコークス強度等、非線形性が強い特性値を表わす。式（２）の非線形関数ｇi(ｘ)は、多変数関数であったり、非凸関数であったり、微分不可能な関数であったりする。ｄiは定数であり、ｇi(ｘ)の下限値を表わす。
【００３４】
本発明を適用するに際して、制約条件を線形制約と非線形制約に分けて定式化を行う。まず、線形制約を数式モデルに追加する。線形制約は、特に困難なく数式モデルへの追加が可能である。
【００３５】
次に、非線形制約の定式化を行う。ステップＳ３では、図３に示すフローチャートに従って、非線形制約を表わす非線形関数に中間変数を導入して分離可能関数に変換する。そして、中間変数の上下限値を設定するとともに、分離可能関数を構成する関数（本実施形態では一変数関数）が非線形関数である場合は、当該一変数関数を区分線形近似して、近似した区分線形関数を制約条件として設定する。
【００３６】
ステップＳ３０１で、制約条件設定部１０３は、非線形関数ｇi(ｘ)を入力する。本実施形態では、非線形関数ｇi(ｘ)が、式（３）の形式で表わされる場合を例として考える。ｘは決定変数である配合割合を表わすＭ次元の列ベクトルであり、ベクトルの要素は各銘柄の配合割合に相当する。ｗ1，ｗ2，ｗ3はＭ次元のベクトルであり、ベクトルの要素は実数値をとるものとする。本実施形態では、各ｗiの次元は５として、値は表２のように与えられる場合を考える。ｗiは例えば各銘柄別の性状や成分を表すパラメータを表す。
【００３７】
【数３】
2020086706.tif 000006
【００３８】
【表２】
2020086706.tif 000007
【００３９】
ステップＳ３０２で、制約条件設定部１０３は、非線形関数ｇi(ｘ)を、中間変数を導入して分離可能関数に変換し、一変数関数の和の形で表現する。分離可能関数への変換は、非特許文献２や非特許文献３に提示されるアルゴリズムを用いても構わないし、その他どのようなアルゴリズムを用いても構わない。非線形関数ｇi(ｘ)を分離可能関数に変換すると、式（４）のように表わされる。非線形関数ｇi(ｘ)は、決定変数ｘの線形結合で表わされる中間変数ｖ1〜ｖ5を独立変数とする関数となる。
【００４０】
【数４】
2020086706.tif 000008
【００４１】
ここで、分離可能関数を構成する関数（本実施形態では一変数関数）を区分線形近似するために、非線形関数の独立変数である中間変数ｖ1，ｖ4，ｖ5の範囲（上下限値）を設定しなければならない。式（４）の例では、中間変数ｖ2，ｖ3は中間変数ｖ4の独立変数であり、中間変数ｖ4と線形関係である。このため、区分線形近似による近似誤差や、関数の発散は発生しない。つまり、近似範囲を決定する必要はないので、本実施形態の考察から除外する。
【００４２】
ステップＳ３０３で、制約条件設定部１０３は、ランダムサンプリングにより、配合割合をランダムに生成し、配合割合のサンプルを複数生成する。その際、配合割合のサンプルは、非線形制約に準じた条件を満たすようにする生成する。そして、これらサンプルを用いることにより、各中間変数の範囲を設定する。
図４を参照して、ステップＳ３０３のランダムサンプリングの詳細を説明する。
ここで、ｄrsiは、ランダムサンプリングを行うときの非線形関数ｇi(ｘ)のしきい値である。しきい値ｄrsiの条件が厳しい場合、本来最適化で解くべき実行可能領域をサンプリングによって損失する可能性が存在する。このため、通常、しきい値ｄrsiの値は、元の非線形制約のしきい値ｄiよりも緩和した値を与える。例えばしきい値ｄiは５００であるので、しきい値ｄrsiは非線形制約を緩和する５００以下の値を与えればよい。本実施形態では、しきい値ｄi，ｄrsiともに５００とした。
中間変数ｖkの範囲を正確に定めるには、中間変数ｖkの範囲を主問題の制約条件式（１）、（２）から逸脱しないようにしなければならない。しかしながら、式（２）の非線形関数を考慮する必要があるため、計算が難しい。もし、変数の範囲が実操業範囲から大きく逸脱した場合は、配合銘柄の品質に係る非線形制約の関数自体が未定義となり、区分線形近似自体が行えない、といった事態を招く可能性がある。
そこで、本発明者は、中間変数ｖkの範囲を設定するにあたり、非線形関数を近似した制約条件を用いて範囲を限定すればよいと考えた。図５に、変数の範囲を決定するイメージを示す。非線形制約に対して、配合割合の乱数を発生させ、非線形制約に準じた条件を満たすサンプルを抽出し、サンプル結果を凸関数で近似することで、変数の範囲を決定できると考えた。
【００４３】
ステップＳ４０１で、一定数のサンプルが得られるまでランダムサンプリングを繰り返す。
ステップＳ４０２で、表１の例のように与えられた各銘柄の配合割合の上下限値の範囲内で配合割合をランダムに生成する。
ステップＳ４０３で、ステップＳ４０２において生成した全銘柄の配合割合の合計値が計画値の１００％であるか否かを判定し、１００％である場合、ステップＳ４０６に移行し、そうでない場合、ステップＳ４０４に移行する。
ステップＳ４０４で、銘柄をランダムに選択する。
ステップＳ４０５で、ステップＳ４０４において選択した銘柄の配合量を、全銘柄の配合割合の合計値が計画値の１００％に近づくように調整する。具体的には、選択した銘柄の配合量をｘ、調整後の配合量をｘ'、銘柄の配合割合の上下限値をそれぞれｘmin、ｘmaxと置く。次に、全銘柄の配合割合の合計値が１００％を超えていた場合、ｘminからｘの間でランダムな値を生成し、生成した値をｘ'として採用する。また、全銘柄の配合割合の合計値が１００％を下回っていた場合、ｘからｘmaxの間でランダムな値を生成し、生成した値をｘ'として採用する。その後、ステップＳ４０３に移行し、再度、配合割合の合計値が１００％であるか否かを判定する。以上の手順を繰り返すことで、全銘柄の配合割合の合計値が計画値の１００％となるサンプルを得ることができる。
【００４４】
ステップＳ４０６で、今回のループで得られたサンプルが、非線形制約に準じた条件であるｇi(ｘ)≧ｄrsiを満たすか否かを判定する。ｇi(ｘ)≧ｄrsiを満たさない場合、ステップＳ４０２に戻り、処理を繰り返す。ｇi(ｘ)≧ｄrsiを満たす場合、ステップＳ４０７に移行し、今回のループで得られたサンプルを有効なサンプルとして採用し、その後、ステップＳ４０２に戻り、次のサンプルの生成に移行する。有効なサンプルが十分な数揃った段階で、ステップＳ３０３のランダムサンプリングを終了する。
【００４５】
表３は、ステップＳ３０３のランダムサンプリングにより、ｇi(ｘ)≧ｄrsi＝５００を満たす配合割合のサンプルを２０００個生成した例を示す。
【００４６】
【表３】
2020086706.tif 000009
【００４７】
図３に説明を戻して、ステップＳ３０４で、制約条件設定部１０３は、分離可能関数を構成する各関数（本実施形態では一変数関数）に対して、区分線形近似による定式化の繰り返しを開始する。分離可能関数を構成する関数同士の関係は非巡回有向グラフで表わすことができ、各関数をラベル付けして、どの関数もその出力辺の先の関数より前に来るように並べることができる。ステップＳ３０４では、この並び順に従って、繰り返し計算を実施する。例えば式（４）の例では、中間変数ｖ1〜ｖ5の順番に定式化を実施する。
【００４８】
ステップＳ３０５で、制約条件設定部１０３は、分離可能関数を構成する関数（本実施形態では一変数関数）の近似範囲を決定する。近似範囲は、ステップＳ３０３で生成したサンプルを関数に代入して、サンプル数分の中間変数の値を計算する。そして、その最大値を中間変数の上限値として、最小値を下限値として設定する。図６は、式（４）の中間変数ｖ4にサンプルの値を代入し、中間変数ｖ4の範囲を求めた結果を示す図であり、中間変数ｖ4と、中間変数ｖ5の式の一部である２ｌｏｇ(ｖ4)との関係を示す図である。中間変数ｖ4の範囲は、７．７４≦ｖ4≦１４．２９と求めることができる。
【００４９】
ステップＳ３０６で、制約条件設定部１０３は、分離可能関数を構成する関数（本実施形態では一変数関数）を区分線形関数で近似し、数式モデルに追加する。区分線形関数の数式モデルへの追加方法は、非特許文献４に記載の手法を用いても構わないし、その他どのような手法を用いても構わない。本実施形態では、非凸な非線形関数を区分線形近似しているので、凸結合定式化手法を用いて数式モデルに追加した。凸結合定式化とは、非線形関数ｙ＝ｆ(ｘ)に対して区分線形近似し、区分線形関数の節を（ｘi，ｙi）ｉ＝１、・・・、Ｋと置いたときに、式（５）のように関係を定式化することである。
【００５０】
【数５】
2020086706.tif 000010
【００５１】
なお、分離可能関数を構成する関数が線形関数である場合は、区分線形近似するまでもなく、線形関数のまま数式モデルとして追加すればよい。
以上のステップＳ３０４〜Ｓ３０６を繰り返すことにより、すべての中間変数に対して、変数同士の関係を数式モデル化し、さらにすべての中間変数に対して上下限値を設定することができる。
そして、ステップＳ３０７で、ｇi(ｘ)≧ｄiを数式モデルに追加すれば、非線形制約を含む制約条件を設定することができる。
以上が、ステップＳ３の制約条件の設定処理の詳細である。
【００５２】
図２に説明を戻して、ステップＳ４で、目的関数設定部１０４は、ステップＳ１で取り込んだデータに基づいて、製造に係るコストを最小化する目的関数を設定する。目的関数は、線形関数であっても、非線形関数であっても構わない。目的関数が非線形関数で表わされる場合は、制約条件の場合と同様に非線形関数を分離可能関数に変換した上で区分線形近似して、目的関数を設定すればよい。
【００５３】
ステップＳ５で、求解部１０５は、ステップＳ３及びステップＳ４で設定した非線形計画問題である配合計画問題を求解する。
【００５４】
ステップＳ６で、判定部１０６は、ステップＳ５での求解結果が妥当なものか否かを判定する。区分線形近似はあくまで近似手法であるため、近似誤差が必ず発生し、近似誤差が十分小さいかを確認しなければならない。
求解結果の妥当性を判定する仕組みとして、ステップＳ５で得られた配合割合を、ステップＳ３での区分線形近似後の関数に代入して得られた計算値と、元の非線形制約に代入して得られた理論計算値とを比較する。そして、計算値と理論計算値との差が所定の条件を満たすまで、ステップＳ２で分割数Ｋを変更して、ステップＳ３〜Ｓ５の非線形計画問題の設定及び求解を繰り返す。
【００５５】
ステップＳ７で、出力部１０７は、ステップＳ６で妥当であると判定された求解結果を出力する。
【００５６】
以上述べた手法（以下、本手法と呼ぶ）を用いることで、線形制約と非線形制約とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解する際に、区分線形近似の近似範囲を適切に設定し、実用時間内に精度の高い最適解を得ることができる。
【００５７】
比較例として、本手法を用いずに、分離可能関数を構成する関数の有向グラフのラベルが若い順番から中間変数の上下限値を計算する方法が考えられる。例えば式（４）の場合に、中間変数ｖ1〜ｖ5と順番に上下限値を決定する状況を考える。各銘柄の配合割合の制約条件に表１に示した値が与えられ、各ベクトルｗiに表２に示した値が与えられた場合、ｖ1，ｖ2，ｖ3の範囲は表４のようになる。
【００５８】
【表４】
2020086706.tif 000011
【００５９】
ここで、ｖ2，ｖ3を独立変数として持つｖ4の範囲は、表４に示すｖ2，ｖ3の範囲に基づいて、−１６．４５≦ｖ4≦１９．１６と計算される（図７に単純計算として示す範囲）。ところが、ｖ5は、ｖ4のｌｏｇ関数であるため、図７に示すように、ｖ4≦０の範囲では関数が未定義となる。また、ｖ4の定義領域を正の範囲に限定した場合であっても、ｖ4＝０を近似範囲に含む場合は、その後段であるｖ5の定義領域がマイナス無限大から定義する必要があるため、近似精度が著しく劣化する。
これに対して、本手法を用いた場合は、上述したようにｖ4の範囲が７．７４≦ｖ4≦１４．２９と正の範囲に限定されており、関数は発散していない。したがって、本手法を用いることで、近似範囲を適切に決定し、高い近似精度の区分線形関数を構築できることが確認することができた。
【００６０】
本発明を適用した非線形計画問題の演算装置は、例えばＣＰＵ、ＲＯＭ、ＲＡＭ等を備えたコンピュータ装置により実現される。
また、本発明は、本発明の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータがプログラムを読み出して実行することによっても実現可能である。
【符号の説明】
【００６１】
１００：配合計画立案装置
１０１：入力部
１０２：分割数設定部
１０３：制約条件設定部
１０４：目的関数設定部
１０５：求解部
１０６：判定部
１０７：出力部
【図１】
2020086706.tif 000012
【図２】
2020086706.tif 000013
【図３】
2020086706.tif 000014
【図４】
2020086706.tif 000015
【図５】
2020086706.tif 000016
【図６】
2020086706.tif 000017
【図７】
2020086706.tif 000018