(57)【要約】【課題】非線形計画問題を求解する際に、問題規模が増大するのを避け、実用時間内に精度の高い最適解が得られるようにする。【解決手段】配合計画立案装置１００は、線形制約条件と非線形制約条件とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解するための非線形計画問題の演算装置として機能し、複数の異なる性質を持つ原材料を配合して製品を製造する製造プロセスにおいて、配合割合を決定変数とした配合計画を立案する。非線形制約条件を表わす非線形関数は、非線形計画問題の決定変数の線形結合で表わされる中間変数を独立変数とする関数であり、制約条件設定部１０３は、前記中間変数の上下限値を設定するとともに、当該上下限値の範囲で前記非線形関数を区分線形関数で近似して、制約条件を設定し、前記設定手段で設定した制約条件の下で前記非線形計画問題を求解する。【選択図】図１
2018180694.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.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非線形計画問題の求解手法として、いくつかの提案がなされている。
例えば特許文献１には、複数種の配合原材料を混合する配合計画を作成するためのシミュレータと、配合原材料の需給バランス制約を表す数式モデル、及び、混合後の性状制約を表す数式モデルを構築するモデル構築部と、モデル構築部により構築された数式モデルを用い、所定の目的関数に基づいて最適化計算を行い、シミュレータに対する指示を算出する計画部とを備え、混合後の性状制約を表す数式モデルが非線形の数式を含む場合、前記非線形の数式に代えて線形の数式を導入して数式モデルを定式化し、その線形の数式を含む数式モデルを用いた計画部による求解結果が前記非線形の数式を含む数式モデルを満たすか否かを確認する手法が開示されている。
また、非特許文献１には、非線形関数に補助変数を導入し、関数を分離可能な形に変換した後に、区分線形関数で近似して、混合整数計画問題として定式化する手法が示されている。
【０００６】
しかしながら、特許文献１の手法では、非線形計画問題を線形計画問題に簡略化して近似するため、近似誤差が発生して、解の精度が悪くなるおそれがある。
また、非特許文献１の手法では、非凸関数の定式化には、非線形関数の分割数に応じて０、１変数の定義が必要となる。この問題はＮＰ困難であり、変数の定義範囲が広すぎたり、分割数が増えすぎたりすると、問題規模が指数関数的に増大して、実用時間内に求解できなくなるおそれがある。
【０００７】
本発明は上記のような点に鑑みてなされたものであり、線形制約条件と非線形制約条件とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解する際に、問題規模が増大するのを避け、実用時間内に精度の高い最適解が得られるようにすることを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するための本発明の要旨は、以下のとおりである。
［１］  線形制約条件と非線形制約条件とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解するための非線形計画問題の演算装置であって、
前記非線形制約条件を表わす非線形関数は、前記非線形計画問題の決定変数の線形結合で表わされる中間変数を独立変数とする関数であり、
前記中間変数の上下限値を設定するとともに、当該上下限値の範囲で前記非線形関数を区分線形関数で近似して、制約条件を設定する設定手段と、
前記設定手段で設定した制約条件の下で前記非線形計画問題を求解する求解手段とを備え、
前記設定手段は、前記中間変数について、前記制約条件から前記非線形制約条件を取り除いたかたちで当該中間変数を目的関数とした数理計画問題を求解することにより、その上下限値を設定することを特徴とする非線形計画問題の演算装置。
［２］  前記設定手段は、
前記非線形関数に補助変数を導入して、一変数関数の和の形で表わされる分離可能関数に変換し、
前記変換した分離可能関数に用いられる前記中間変数の上下限値を設定するとともに、前記変換した分離可能関数を構成する非線形関数を区分線形関数で近似して、制約条件を設定することを特徴とする［１］に記載の非線形計画問題の演算装置。
［３］  前記設定手段は、非線形関数を区分線形関数で近似するときに、凸結合定式化及びタイプ２の特殊順序集合を用いた定式化のうち少なくともいずれか一方を行うことを特徴とする［１］又は［２］に記載の非線形計画問題の演算装置。
［４］  前記求解手段で得られた決定変数の値を、前記設定手段による区分線形近似後の関数に代入して得られた近似計算値と、
前記求解手段で得られた決定変数を、前記非線形制約条件を表わす非線形関数に代入して得られた理論計算値とを比較し、
前記近似計算値と前記理論計算値との差が所定の条件を満たすまで、区分線形関数の分割数を変更して、前記設定手段及び前記求解手段による処理を繰り返すことを特徴とする［１］乃至［３］のいずれか一つに記載の非線形計画問題の演算装置。
［５］  前記非線形計画問題は、複数の原材料を配合して製品を製造する製造プロセスにおいて、配合割合を決定変数とする配合計画問題であることを特徴とする［１］乃至［４］のいずれか一つに記載の非線形計画問題の演算装置。
［６］  線形制約条件と非線形制約条件とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解するための非線形計画問題の演算方法であって、
前記非線形制約条件を表わす非線形関数は、前記非線形計画問題の決定変数の線形結合で表わされる中間変数を独立変数とする関数であり、
設定手段が、前記中間変数の上下限値を設定するとともに、当該上下限値の範囲で前記非線形関数を区分線形関数で近似して、制約条件を設定する設定ステップと、
求解手段が、前記設定した制約条件の下で前記非線形計画問題を求解する求解ステップとを有し、
前記設定ステップでは、前記中間変数について、前記制約条件から前記非線形制約条件を取り除いたかたちで当該中間変数を目的関数とした数理計画問題を求解することにより、その上下限値を設定することを特徴とする非線形計画問題の演算方法。
［７］  線形制約条件と非線形制約条件とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解するためのプログラムであって、
前記非線形制約条件を表わす非線形関数は、前記非線形計画問題の決定変数の線形結合で表わされる中間変数を独立変数とする関数であり、
前記中間変数の上下限値を設定するとともに、当該上下限値の範囲で前記非線形関数を区分線形関数で近似して、制約条件を設定する設定処理と、
前記設定した制約条件の下で前記非線形計画問題を求解する求解処理とをコンピュータに実行させ、
前記設定処理では、前記中間変数について、前記制約条件から前記非線形制約条件を取り除いたかたちで当該中間変数を目的関数とした数理計画問題を求解することにより、その上下限値を設定することを特徴とするプログラム。
【発明の効果】
【０００９】
本発明によれば、線形制約条件と非線形制約条件とを含む制約条件の下で目的関数を最小化又は最大化する非線形計画問題を求解する際に、問題規模が増大するのを避け、実用時間内に精度の高い最適解が得られるようにすることができる。
【図面の簡単な説明】
【００１０】
【図１】実施形態に係る配合計画立案装置の機能構成を示す図である。
【図２】実施形態に係る配合計画立案装置による配合計画の立案方法の処理を示すフローチャートである。
【図３】図２のフローチャートにおける制約条件の定式化処理の詳細を示すフローチャートである。
【図４Ａ】変数同士の主従関係を表わす有向グラフの例を示す図である。
【図４Ｂ】図４Ａの有向グラフのノードに対してラベルを付与した結果を示す図である。
【図５】実施例における区分線形近似の分割数と相対誤差との関係を示す特性図である。
【図６】実施例における区分線形近似の分割数と計算時間との関係を示す特性図である。
【図７】実施例における配合量変更可能割合とコスト改善効果の関係の比較結果を示す特性図である。
【発明を実施するための形態】
【００１１】
以下、添付図面を参照して、本発明の好適な実施形態について説明する。
【００１２】
非線形関数を区分線形近似にて定式化する場合、区分線形関数の近似精度を上げるためには、区分線形関数の分割数を細かく切る必要がある。しかしながら、分割数を増やせば増やすほど計算負荷が上がるため、分割数は要求精度を満たす最低限度の値を与える必要がある。ここで、計算精度を保つために必要な区分線形近似関数の分割数は、区分線形近似関数を構築する変数の取りうる範囲によって決定される。もし変数の取りうる範囲が広ければ、多くの分割が必要となり、少なければ少ない分割数で定式化が済む。そこで、本発明者らは、非線形関数を構築する変数の最小値／最大値を、線形計画法を用いて事前に求めることによって、定式化後の最適化問題の解の探索範囲を減少させた。これによって、本プロセスの配合計画問題に対する高速・高精度の計画立案を実現する技術を確立した。
【００１３】
本実施形態では、製鉄業におけるコークスや焼結鉱の製造プロセスのように、複数の異なる性質を持つ原材料を配合して製品を製造する製造プロセスに対して本発明を適用した例を説明する。
【００１４】
図１に、実施形態に係る配合計画立案装置１００の機能構成を示す。配合計画立案装置１００は、本発明を適用した非線形計画問題の演算装置として機能し、複数の異なる性質を持つ原材料（銘柄）を配合して製品を製造する製造プロセスにおいて、配合割合を決定変数とし、目標となる製品の特性値や生産量、操業条件を満たし、かつ、製造に係るコストを最小化する配合計画を立案する。つまり最適な配合割合を求める。本実施形態で取り扱う配合計画問題では、制約条件の少なくとも一部が非線形関数で表わされる非線形制約となっている。
【００１５】
１０１は入力部であり、例えばデータベース１０８から配合計画を立案する上で必要になる各原材料の性状情報（性質や状態に関する情報）、操業条件情報、コスト情報等のデータを取り込む。
【００１６】
１０２は分割数設定部であり、非線形関数を区分線形近似する際の分割数を設定する。分割数設定部１０２は、例えばオペレータの指示に従って分割数を設定するようにしてもよいし、予め定められた分割数の範囲内で自動的に分割数を設定するようにしてもよい。
【００１７】
１０３は制約条件設定部であり、入力部１０１で取り込んだデータに基づいて、目標となる製品の特性値や生産量、操業条件を満たすための制約条件を数式モデルに定式化して設定する。
ここで、制約条件設定部１０３は、関数変換部１０３ａと、上下限値設定部１０３ｂとを備え、非線形制約に用いられる変数の上下限値を設定するとともに、非線形制約を構成する非線形関数を区分線形近似して、制約条件を設定する設定手段として機能する。
より詳細には、関数変換部１０３ａは、非線形制約を表わす非線形関数が、分離可能関数であるか否かを判断する。分離可能関数とは、ｎ次元のユークリッド空間の任意のｘ＝（ｘ1，ｘ2，・・・，ｘn）Tに対して、関数ｆが下記のかたちで表わされる関数である。
【００１８】
【数１】
2018180694.tif 000003
【００１９】
非線形関数が分離可能関数で表現されていない場合には、補助変数を導入し、非線形関数を分離可能関数に変換する。この変換により、全ての非線形関数は一変数関数の和の形で表現することが可能となる。
上下限値設定部１０３ｂは、関数変換部１０３ａで変換した分離可能関数に用いられる変数の上下限値を設定する。この上記設定された数式モデルのうちで、制約条件から非線形制約を取り除くことで緩和した数式モデルに対して、上下限値を求めるべき上記変数を目的関数とした数式モデルに定式化し、目的関数を最大化及び最小化する数理計画問題を求解することにより、その上下限値を設定する。
そして、制約条件設定部１０３は、関数変換部１０３ａで変換した分離可能関数を構成する一変数関数が非線形関数である場合には、該一変数関数を区分線形近似して、制約条件を設定する。
なお、ここでいう定式化とは、制約条件設定部１０３が数式モデルそのものを最初から構築するという意味ではなく、予め設定されている制約条件の数式モデルの枠組みに、ステップＳ１で取り込んだデータを反映させることをいう。
【００２０】
１０４は目的関数設定部であり、入力部１０１で取り込んだデータに基づいて、製造に係るコストを最小化する目的関数を数式モデルに定式化して設定する。
なお、ここでいう定式化とは、目的関数設定部１０４が数式モデルそのものを最初から構築するという意味ではなく、予め設定されている目的関数の数式モデルの枠組みに、ステップＳ１で取り込んだデータを反映させることをいう。
【００２１】
１０５は求解部であり、制約条件設定部１０３及び目的関数設定部１０４で設定した配合計画問題を求解する。
【００２２】
１０６は判定部であり、求解部１０５による求解結果が妥当なものか否かを判定する。その結果、求解結果が妥当なものである場合、該求解結果を確定する。求解結果が妥当なものでない場合は、分割数設定部１０２で分割数を変更して、制約条件設定部１０３、目的関数設定部１０４及び求解部１０５による配合計画問題の求解を繰り返す。
求解結果の妥当性を判定する仕組みとして、求解部１０５で得られた配合割合を、制約条件設定部１０３による区分線形近似後の関数に代入して得られた計算値と、元の非線形制約に代入して得られた理論計算値とを比較する。そして、計算値と理論計算値との差が所定の条件を満たすまで、分割数設定部１０２で分割数を変更して、制約条件設定部１０３、目的関数設定部１０４及び求解部１０５による配合計画問題の設定及び求解を繰り返す。
【００２３】
１０７は出力部であり、判定部１０６で妥当であると判定した求解結果を出力する。ここでいう出力とは、例えば求解結果を不図示の記憶領域に保存、登録したり、ディスプレイ１１０に表示したり、ネットワークを介して外部機器に送出したりすることをいう。
【００２４】
１０８はデータベースであり、配合計画を立案する上で必要になる各原材料の性状情報、操業条件情報、コスト情報等のデータを格納する。なお、ここでデータベース１０８からデータを取り込む例を示したが、それ以外にも、例えばネットワークを介して外部機器からデータを取り込んだり、ユーザが直接入力したデータを取り込んだりする形態であっても構わない。
【００２５】
１０９はポインティングデバイスやキーボード等の入力装置、１１０はディスプレイである。
【００２６】
次に、配合計画立案装置１００による配合計画の立案方法を説明する。
図２は、実施形態に係る配合計画立案装置１００による配合計画の立案方法の処理を示すフローチャートである。
ステップＳ１で、入力部１０１は、例えばデータベース１０８から配合計画を立案する上で必要になる各原材料の性状情報、操業条件情報、コスト情報等のデータを取り込む。例えば表１に示すように、各銘柄の配合割合に関して上下限値の情報が取り込まれる。また、具体的には示さないが、各銘柄の性質に関して上下限値の情報が取り込まれる。
【００２７】
【表１】
2018180694.tif 000004
【００２８】
ステップＳ２で、分割数設定部１０２は、非線形関数を区分線形近似する際の分割数Ｋを設定する。なお、区分線形近似すべき非線形関数が複数ある、或いは分離可能関数に用いられる変数が複数ある場合、分割数は非線形関数ごと、分離可能関数に用いられる変数ごとに設定してもよい。
【００２９】
ステップＳ３で、制約条件設定部１０３は、ステップＳ１で取り込んだデータに基づいて、目標となる製品の特性値や生産量、操業条件を満たすための制約条件を数式モデルに定式化して設定する。
本実施形態において制約条件は、式（１）のように線形関数で表わされる線形制約と、式（２）のように非線形関数で表わされる非線形制約とに分けられる。
【００３０】
【数２】
2018180694.tif 000005
【００３１】
式（１）は、制約条件の中でも線形となる制約条件を表わす式である。式（１）のｘは決定変数である配合割合を表わすＭ次元の列ベクトルであり、ベクトルの要素は各原材料の配合割合に相当する。式（１）のＡはＮ行Ｍ列の行列であり、Ａのすべての要素は実数値をとるものとする。ｂはＮ次元の列ベクトルであり、実数値をとるものとする。
式（２）のｇi(ｘ)は非線形関数であり、ｉは制約の種類を表わす。例えば非線形関数ｇi(ｘ)は、製鉄業であればコークス強度等、非線形性が強い特性値を表わす。式（２）の非線形関数ｇi(ｘ)は、多変数関数であったり、非凸関数であったり、微分不可能な関数であったりする。
【００３２】
本発明を適用するに際して、制約条件を線形制約と非線形制約を分けて定式化を行う。まず、線形制約を数式モデルに追加する。線形制約は、特に困難なく数式モデルへの追加が可能である。
【００３３】
次に、非線形制約の定式化を行う。ステップＳ３では、図３に示すフローチャートに従って、非線形制約を分離可能関数に変換し、分離可能関数に用いられる変数の上下限値を設定するとともに、分離可能関数を構成する一変数関数が非線形関数である場合には、該一変数関数を区分線形関数で近似して、近似した区分線形関数を制約条件として設定する。
ステップＳ３０１で、制約条件設定部１０３は、非線形関数ｇi(ｘ)を入力する。本実施形態では、非線形関数ｇi(ｘ)が、式（３）の形式で表わされる場合を考える。ｘは決定変数である配合割合を表わすＭ次元の列ベクトルであり、ベクトルの要素は各原材料の配合割合に相当する。ｗ1，ｗ2，ｗ3はＭ次元のベクトルであり、ベクトルの要素は実数値をとるものとする。
【００３４】
【数３】
2018180694.tif 000006
【００３５】
式（３）の非線形関数ｇi(ｘ)は、非凸関数で、かつ多変数関数である。一般的に非線形非凸関数に対して区分線形近似を適用する場合、凸結合定式化に加えて、タイプ２（Special Order Set type2：ＳＯＳ２）の特殊順序集合を用いた定式化を行う必要がある。このため、この非線形関数を区分線形近似で定式化した最適化問題はＮＰ困難な問題となる。
また、式（３）の非線形関数ｇi(ｘ)は、Ｍ次の多変数関数である。そのため、式変形を加えずに区分線形近似を適用しようとすると、Ｍ次の超平面で近似関数を構成しなければならない。例えば式（３）の非線形関数ｇi(ｘ)を、各変数ごとに、Ｋ個分割した区分線形関数を構成する場合を考える。このとき、非線形関数ｇi(ｘ)を区分線形近似するのに必要な変数の数はおおよそＫMと、累乗のオーダーである。例えばＫ＝５０、Ｍ＝１０とした場合、区分線形近似に必要な変数の数は５０10と非常に多い。そのため、このままの定式化では実用時間内に求解できない可能性が高い。したがって、問題規模を縮小する定式化の工夫が求められる。
【００３６】
そこで、ステップＳ３０２で、制約条件設定部１０３の関数変換部１０３ａは、非線形関数ｇi(ｘ)に補助変数を導入し、分離可能関数、すなわち一変数関数の和のかたちで表現できる多変数関数に変換する。分離可能関数への変換は、非特許文献２や非特許文献３に提示されるアルゴリズムを用いても構わないし、その他どのようなアルゴリズムを用いても構わない。非線形関数ｇi(ｘ)を分離可能関数に変換すると、式（４）のように表わされる。非線形関数ｇi(ｘ)は、決定変数ｘの線形結合で表わされる中間変数ｖ1〜ｖ4を独立変数とする関数となる。
【００３７】
【数４】
2018180694.tif 000007
【００３８】
式（４）の非線形関数に対して分割数Ｋが設定されているとする。式（４）には、非線形関数が３つ存在するが、それぞれの関数は一変数関数であるので、区分線形近似するのに必要な変数の数はそれぞれＫ個だけでよい。したがって、区分線形関数を構成する変数の数は３×Ｋで３Ｋ個となる。すなわち、式（４）のように、非線形関数を分離可能関数に変換したことにより、変換前はＫ3個必要であった区分線形関数を構成する変数の数が、変換後は３Ｋに抑えられたといえる。
【００３９】
ステップＳ３０３で、制約条件設定部１０３は、ステップＳ３０２で変換した関数に対して、変数同士の関係を明確化し、順序に沿って定式化を行う前準備として、関数中の変数をノードとした有向グラフを構築する。有向グラフは、それぞれの関数に対して、関数の入力となる変数を始点、関数を通して得られる変数を終点とする枝を張ることとする。例えばある関数がｚ＝ｆ(ｘ，ｙ)という関係がある場合は、２本の枝（ｘ，ｚ），（ｙ，ｚ）を張る。図４Ａは、式（４）に関して、ｘ及びｖkをノードとし、ｖkの従属関係を有向グラフで結んだ例である。式（４）の例では、ｖ4は変数ｖ2、ｖ3から構成される変数であり、変数ｖ5はｖ1、ｖ4から構成される変数である。図４Ａに示すように有向グラフを用いれば、変数同士の主従関係を設定することができる。
【００４０】
ステップＳ３０４で、制約条件設定部１０３は、ステップＳ３０３で構築した有効グラフのノード（変数）に対してラベル付けを行う。ステップＳ３０３で構築した有向グラフは、非巡回有効グラフ（木構造）となるので、トポロジカルソートが可能となる。トポロジカルソートとは、各ノードを順序付けして、どのノードもその出力辺の先のノードより前に来るように並べることである。ステップＳ３０３で構築した有向グラフに対してトポロジカルソートを行い、後ろにあるノードから順番に１からラベルを付与する。図４Ｂは、ステップＳ３０３で構築した有向グラフに対して、トポロジカルソートを行い、ノードに対してラベルを付与した結果である。
以上、ステップＳ３０３、Ｓ３０４によって、非線形関数を定式化するための変数同士の関係のグラフ化及び、ラベル付けが完了した。
本実施形態では、以降のステップＳ３０５〜Ｓ３１４で、ステップＳ３０３で付与したラベル順に処理を繰り返すことによって、変数の関係を数式モデルに追加する。
【００４１】
ステップＳ３０５で、制約条件設定部１０３は、木構造を持つノード集合に対して、ノードのラベルｋが小さい順にすべての変数に対して、繰り返し計算を開始する。以降、ノードｋに対応する変数をｕk（ｋ＝１、・・・、Ｍ＋６）とする。また、以降、木構造を持つノード集合において、あるノードに隣接し、かつ、下方に存在するノードを子ノードと呼ぶ。また、あるノードから見て、その子ノードやそこから先の子ノード全てのいずれかを子孫ノードと呼ぶ。
【００４２】
ステップＳ３０６で、制約条件設定部１０３は、ノードｋに子ノードが存在するか否かを判定する。ノードkに子ノードが存在する場合は、ステップＳ３０７に進み、子ノードが存在しない場合は、ステップＳ３１３にて、変数ｕkの上下限値を設定する。式（４）の例では、変数（ｘ1，ｘ2，・・・，ｘM）は、子ノードが存在しないノードに相当するため、ステップＳ３１３に進む。一方、変数（ｖ1，ｖ2，・・・，ｖn）は子ノードが存在するノードであり、ステップＳ３０７に進む。
【００４３】
まず、ステップＳ３０６でノードｋに子ノードが存在せず、ステップＳ３１３に進んだ場合を考える。この場合、ステップＳ３１３では、子ノードを持たないノードｋに対して上下限値を設定する。上下限値は予め与えられたノードｋの上下限値を設定する。本実施形態のような配合計画では、配合割合を表わす変数（ｘ1，ｘ2，・・・，ｘM）には上下限値が予め定まっていることが多く、それを設定値として与えればよい。本実施形態では、表１に設定された上下限値が変数（ｘ1，ｘ2，・・・，ｘM）に設定される。このように子ノードを持たないノード全ての上下限を決定することで、以降の計算で現れるノードの定式化において、その子ノードは全て有界変数となる。これにより、区分線形関数等、有界変数での表現が必要となる関数を数式モデルに追加することが可能となる。もし、ノードｋが有界変数ではない場合は、ノードｋが取りうる最大の範囲をノードｋの上下限値として設定すればよい。例えば、本実施形態における配合計画問題では、配合割合が０％以下、又は１００％以上になることは無いので、ノードｋの下限値は０、上限値は１００のように設定すればよい。
【００４４】
次に、ステップＳ３０６でノードｋに子ノードが存在し、ステップＳ３０７に進んだ場合を考える。ステップＳ３０７で、制約条件設定部１０３は、ノードｋとそのノードのすべての子孫ノード間の関係が、すべて線形関係式か、又は一つでも非線形関係式を含むか否かを判定する。線形関係式のみの場合は、ステップＳ３０８に進み、非線形関係式を含む場合は、ステップＳ３１０に進む。式（４）の例では、図４ＢのノードＭ＋１〜Ｍ＋４に対応する変数（ｖ1，ｖ2，ｖ3，ｖ4）の、それぞれの子孫ノードはすべて、線形関係式で結ばれているので、ステップＳ３０８へ進む。図４ＢのノードＭ＋５、Ｍ＋６に対応する変数（ｖ5）とｇi(ｘ)の子孫ノードは、非線形関係式を含むのでステップＳ３０９に進む。
【００４５】
ステップＳ３０８で、制約条件設定部１０３は、ノードｋと子ノードの線形関係式を数式モデルに追加する。具体的には、式（５）を制約条件として数式モデルに追加する。式（５）は、ノードｋとノードｋの子ノードの線形関係を表わし、Ｓkは、ノードｋのすべての子ノード集合、ｗjkはノードと子ノードの関係を表わす係数である。式（４）の変数ｖ1の例では、ｖ1の子ノードは、変数（ｘ1，ｘ2，・・・，ｘM）であり、ｖ1と子ノードの関係は、ｖ1＝ｗ1Tｘで結ばれているので、ｖ1＝ｗ1Tｘを制約条件として設定する。
【００４６】
【数５】
2018180694.tif 000008
【００４７】
ステップ３０９で、制約条件設定部１０３の上下限値設定部１０３ｂは、ノードｋに対応する変数の上下限値を設定する。具体的には、非線形計画問題の制約条件から非線形制約を取り除いた線形制約条件と、変数ｕkとｋのすべての子孫ノードの関係を表わした等式制約を制約条件とし、変数ｕkを目的関数とした数理計画問題を構築し、その問題を最大化及び最小化を行う。このように数理計画問題を求解することにより、変数ｕkの定義範囲、すなわち上下限値を求めることができる。
式（６）、式（７）、式（８）に、ｕkの最小（下限値）、最大（上限値）を求める線形計画問題を示す。
【００４８】
【数６】
2018180694.tif 000009
【００４９】
この線形計画問題は、式（１）、式（２）の制約条件から非線形制約を取り除いたかたちで構成される。このように線形制約を用いて変数ｕkを目的関数とした数理計画問題を求解することにより、変数ｕkの定義範囲を求めることができる。
この場合、ステップＳ３０９で得られる変数ｕkの定義範囲は、元問題から非線形制約を取り除いた一種の緩和問題を解いて得られた範囲であるので、元問題における変数ｕkのとりうる範囲とは必ずしも一致しない。しかしながら、変数ｕkの取りうる範囲を、本手法により予め求めることによって、後に説明する区分線形近似関数の定式化において、区分線形近似の精度を保つために必要な０、１変数の数を減らすことができるため、計算精度の向上と計算時間の短縮が期待できる。
【００５０】
続いてステップＳ３１３で、制約条件設定部１０３の上下限値設定部１０３ｂは、ステップＳ３０９で求めた最適解を変数ｕkの上下限値として設定する。
以上が、ステップＳ３０７にて、ノードｋとそのノードのすべての子孫ノードの関係が線形関係式で表わされる場合の定式化方法である。
【００５１】
次に、ステップＳ３０７にて、ノードｋとすべての子孫ノードの関係が、線形関係式だけでは表わされない場合を考える。例えば式（４）では、変数（ｖ5）とｇi(ｘ)の子孫ノードは線形関係式だけでは表わせないので、ステップＳ３１０に進む。ノードｋとそのノードの全ての子孫ノードが線形関係式だけでは表わされない場合は、変数の上下限を求める問題にも非線形制約条件が必要になってくるため、ステップＳ３０８〜Ｓ３０９のように、線形計画法を用いて変数の上下限値を設定することはできない。そこで、以降のステップＳ３１０〜Ｓ３１２ではノードｋの線形／非線形性にのみ着目し、変数の上下限設定及び、数式モデルへの定式化を行う。このように、親ノードと子ノードの関係を逐次的に定式化することで、非線形関数全体の数式モデルへの定式化を狙う。
【００５２】
ステップＳ３１０で、制約条件設定部１０３は、ノードｋとその子ノードが線形関係式で表わされるか否かを判定する。上記ノードｋの子ノードが線形関係式で表わされる場合、ステップＳ３１１に進み、ノードｋの子ノードが線形関係式のみでは表現できず、少なくとも一つの非線形関係式を含む場合は、区分線形近似による定式化を行うために、ステップＳ３１２に進む。式（４）の例では、変数（ｖ5）は変数ｖ1，ｖ4との非線形関数、ｇi(ｘ)は、変数ｖ5の非線形関数で表わされるので、ステップＳ３１２に進む。
【００５３】
ステップＳ３１１で、制約条件設定部１０３は、ノードｋとノードｋの子ノードの線形関係式を制約条件として数式モデルに追加する。
続いてステップＳ３１３で、制約条件設定部１０３の上下限値設定部１０３ｂは、線形関数である変数ｕkの上下限値を設定する。変数ｕkの上下限値は、線形関数の右辺にある変数の上下限値から最大値、最小値を解析的に求め設定する。
【００５４】
ステップＳ３１２で、制約条件設定部１０３は、ノードｋとノードｋの子ノードの非線形関係式を数式モデルへ定式化を行う。本実施形態では、非線形関数を区分線形関数で近似し、区分線形関数を、凸結合定式化手法で制約条件として数式モデルに追加する。凸結合定式化とは、非線形関数ｙ＝ｆ(ｘ)に対して区分線形近似し、区分線形関数の節を（ｘi，ｙi）ｉ＝１、・・・、Ｋと置いたときに、式（９）のように関係を定式化することである。
【００５５】
【数７】
2018180694.tif 000010
【００５６】
式（９）は、原点から区分線形関数の節を指すベクトルに対して、その重みｔkが１になるようなベクトルを求めることに相当する。もし、ｆ(ｘ)が凸関数でｆ(ｘ)を最小化する問題であれば、解はある線分上にあるので、必ず２つの連続するｔkだけが正の値をとる。そうでない場合は、隣り合わない２つのｔkが正になる場合があり、そのような解を取り除く必要がある。このような解を取り除くためには、ｔkの集合に、“高だか２つの隣り合うｔkだけが正の値をとる”制約を追加すればよい。高だか２つの隣り合うｔkだけが正の値をとるような変数群（ｔ1，ｔ2，・・・，ｔK）はＳＯＳ２変数群と呼ばれる。ＳＯＳ２変数群の定式化には、整数計画法を用いて定式化してもよいし、標準的なソルバーに用意されているＳＯＳ２集合を定義するための専用の関数を用いてもよい。整数変数を用いてＳＯＳ２変数群を定式化した例を式（１０）に示す。なお、その詳細は非特許文献４に記載されている。このように凸結合定式化に加え、ＳＯＳ２変数群を定義して、非凸な非線形関数を混合整数計画問題として定式化を行う。
続いてステップＳ３１３で、制約条件設定部１０３の上下限値設定部１０３ｂは、非線形関数である変数ｕkの上下限値を設定する。変数ｕkの上下限値は、変数ｕkを近似した区分線形関数の上下限値を設定する。
以上が、ノードｋの全ての子孫ノードに少なくとも一つの非線形関係式が含まれる場合の定式化方法である。
【００５７】
【数８】
2018180694.tif 000011
【００５８】
以上のステップＳ３０６〜Ｓ３１３を繰り返すことにより、すべての変数ｕkに対して、変数同士の関係を数式モデル化し、さらにすべての変数ｕkに対して上下限値を設定することができる。
そして、ステップＳ３１４で、ｇi(ｘ)≧０を数式モデルに追加すれば、非線形制約を含む制約条件を数式モデルに定式化することができる。
以上が、ステップＳ３の詳細である。従来は、配合計画の立案に使用される非線形関数は、区分線形近似を用いて定式化するために、配合割合を表わす変数の次元だけ区分線形関数を用意して定式化しなければならなかった。それに対して、本実施形態の手順に従えば、非線形制約式に使用される決定変数をノードとした計算グラフを構築し、ノード間の関係（線形・非線形）に対して定式化を実施することによって、非線形関数を区分線形近似するのに必要な変数の数を大きく減らすことが可能となった。さらに、区分線形関数を構築する変数の範囲を、線形計画法を用いて変数の最小化／最大化問題を事前に求解した。これによって、区分線形近似関数を構築する変数の定義範囲を狭めることが可能となり、区分線形近似関数の精度を保つために必要な０、１変数の数を減らした。したがって、実用時間内に求解できるモデルを構築できた。
【００５９】
図２に説明を戻して、ステップＳ４で、目的関数設定部１０４は、ステップＳ１で取り込んだデータに基づいて、製造に係るコストを最小化する目的関数を数式モデルに定式化して設定する。目的関数は、線形関数であっても、非線形関数であっても構わない。目的関数が非線形関数で表わされる場合は、制約条件の場合と同様に非線形関数を分離可能関数に変換し、変数の上下限値を設定するとともに、非線形関数を区分線形近似して、目的関数を設定すればよい。
【００６０】
ステップＳ５で、求解部１０５は、ステップＳ３及びステップＳ４で設定した非線形計画問題である配合計画問題を求解する。
【００６１】
ステップＳ６で、判定部１０６は、ステップＳ５での求解結果が妥当なものか否かを判定する。区分線形近似はあくまで近似手法であるため、近似誤差が必ず発生し、近似誤差が十分小さいかを確認しなければならない。
求解結果の妥当性を判定する仕組みとして、ステップＳ５で得られた配合割合を、ステップＳ３での区分線形近似後の関数に代入して得られた計算値と、元の非線形制約に代入して得られた理論計算値とを比較する。そして、計算値と理論計算値との差が所定の条件を満たすまで、ステップＳ２で分割数Ｋを変更して、ステップＳ３〜Ｓ５の非線形計画問題の設定及び求解を繰り返す。
【００６２】
ステップＳ７で、出力部１０７は、ステップＳ６で妥当であると判定された求解結果を出力する。
【実施例】
【００６３】
以上説明した手法を用いて、石炭の配合計画を対象として、非線形計画問題である配合計画問題を求解する実施例を説明する。
石炭の配合計画は、配合割合を決定変数とし、目標となる製品の特性値や生産量、操業条件を満たし、かつ、製造に係るコストを最小化する配合計画を立案する非線形計画問題として、以下の式（１１）〜式（１５）のように定式化した。
ｉ：銘柄名に関する添え字
ｊ：制約条件に関する添え字
ｘi：石炭の配合割合（決定変数）
ｐi：コークス製造コスト（石炭購買費用＋輸送費用＋操業費用）
ａij：原料炭の成分の比率（測定値）
ｇi(ｘ1，ｘ2，・・・，ｘN)：コークス品質推定式（非線形）
ＬＢj，ＵＢj：品質の上下限値
ＵiL，ＵiU：配合割合上下限値
【００６４】
【数９】
2018180694.tif 000012
【００６５】
なお、ここでは単一期間における配合計画を表わしているが、式（１１）〜式（１５）の定式化を多期間の配合計画に拡張してもよい。多期間の配合計画に拡張するためには、前後期間の在庫量や、多期間に渡る使用計画、原材料の受け入れ計画に関する制約条件が必要となるが、これらの制約条件は全て混合整数計画法にて定式化が可能であるので、単一期間での配合計画が立案できれば、多期間での配合計画も立案可能となる。
【００６６】
式（１１）の目的関数は、コークス製造に係るコストを表わす。本実施例では、目的関数を線形関数として与えたが、これが非線形関数であっても構わない。
【００６７】
式（１２）の制約条件は、品質に関する線形制約を表わし、例えば揮発分や硫黄分等に関する制約が含まれる。ａijは石炭の成分の比率を表わし、その値を配合割合で加重平均した値を制約条件として与える。
式（１３）の制約条件は、品質に関する非線形制約を表わし、例えばコークス冷間強度（コークスＤＩ)と膨張圧に関する制約が含まれる。コークスＤＩとは、石炭をコークス炉で焼き固めた後に得られたコークスの強度を表わす指標である。コークスは、高炉での通気性を確保するために一定以上の強度が求められ、その強度の指標としてコークスＤＩが使用されることが多い。また、膨張圧は、石炭をコークス炉内で焼き固めるときに発生するガスによってコークス炉内に掛かる圧力を表わす指標である。膨張圧が高いと、コークス炉の炉体にダメージを与えるため、なるべく低い値が望ましい。
式（１４）の制約条件は、配合割合の合計値に関する制約を表わす。
式（１５）の制約条件は、石炭の配合割合に関する上下限制約を表わす。
【００６８】
以上のようにした数式モデルにおいて、式（１３）は、式（２）の非線形制約に相当する。また、式（１２）、（１４）、（１５）は、式（１）の線形制約に相当する。本実施例では、式（１３）に含まれるコークスＤＩ及び膨張圧に対して、図３に示すフローチャートに従って定式化を行った。
【００６９】
表２に、配合割合（表１）及び性質の制約条件の下で、実施形態に従って最適化を行い、得られた配合割合の値を示す。表２に示すように、最適化結果は表１の配合割合制約を遵守している。また、最適化結果はすべての制約条件を遵守しており、正しい最適化が行われた。
【００７０】
【表２】
2018180694.tif 000013
【００７１】
図５は、区分線形近似の分割数を変更し、各分割数に対して最適化計算を行った結果を示す。横軸は分割数を表わし、分割数を１０から８０まで１０刻みで分割数を増やして最適化を行った。縦軸は、計算値と理論計算値との相対誤差［％］であり、計算値と理論計算値との差を理論計算値で割った値を百分率で表わしている。図５より、コークスＤＩ及び膨張圧の相対誤差は共に、分割数が増えるに従って減少している。さらに、相対誤差はすべての条件で０．１％以下であり、分割数が３０を超えれば誤差は殆ど無かった。この誤差の大きさは、コークスＤＩ及び膨張圧の操業ばらつきに比べて十分小さく、実務上問題にならない。
【００７２】
次に、図６は、区分線形近似の分割数を変更し、各分割数において最適化計算に要した計算時間を示す。横軸は分割数を表わし、縦軸は計算時間［ｓｅｃ］を表わす。図６に示すように、分割数が増えると計算時間は増えるが、汎用コンピュータを用いた計算環境下において、計算時間は分割数１０から８０までのすべての最適化において６０秒以内であり、実務上問題にならない計算時間で求解することができた。
【００７３】
次に、図７は、配合割合の制約条件を変更したときのコスト改善効果を調査した結果を示す。区分線形近似の分割数は５０で固定した。本実施例では、ある時点での配合量を基準配合と置き、基準配合から配合の変更を許す割合を少しずつ大きくしたときのコストの変化を図示した。ここで、基準配合量から配合の変更を許す割合を配合量変更可能割合と呼ぶ。横軸は配合量変更可能割合を表わし、０％〜８０％まで配合量変更可能割合を変化させた。縦軸はコスト改善効果［％］であり、配合割合変更可能割合が０％のときを基準として、基準に対するコスト改善効果を百分率で表わしている。図７に示すように、本発明を適用した発明手法は、比較手法（特許文献１のアルゴリズム）に比べて３倍以上コスト改善効果が見込まれ、本発明が十分有用であることが示された。
【００７４】
以上、本発明を実施形態と共に説明したが、上記実施形態は本発明を実施するにあたっての具体化の例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、又はその主要な特徴から逸脱することなく、様々な形で実施することができる。
本実施形態では、複数の異なる性質を持つ原材料を配合して製品を製造する製造プロセスとして、製鉄業におけるコークスや焼結鉱の製造を挙げたが、例えば石油の精製、セメントの製造等における配合計画の立案に本発明を適用してもよい。
さらにいえば、本発明は、配合計画問題に限定されるものではなく、非線形計画問題に広く適用可能である。例えば建設物を設計する際に、必要な強度を確保した上で柱の太さを最適化する問題がある。このとき、数多くの柱の太さを変数とすると、その強度の計算は変数の非線形関数となる。このような事例に対しても本発明を適用することにより、問題規模が増大するのを避け、実用時間内に精度の高い最適解が得られるようにすることができる。
【００７５】
本発明を適用した非線形計画問題の演算装置は、例えばＣＰＵ、ＲＯＭ、ＲＡＭ等を備えたコンピュータ装置により実現される。
また、本発明は、本発明の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータがプログラムを読み出して実行することによっても実現可能である。
【符号の説明】
【００７６】
１００：配合計画立案装置
１０１：入力部
１０２：分割数設定部
１０３：制約条件設定部
１０４：目的関数設定部
１０５：求解部
１０６：判定部
１０７：出力部
【図１】
2018180694.tif 000014
【図２】
2018180694.tif 000015
【図３】
2018180694.tif 000016
【図４Ａ】
2018180694.tif 000017
【図４Ｂ】
2018180694.tif 000018
【図５】
2018180694.tif 000019
【図６】
2018180694.tif 000020
【図７】
2018180694.tif 000021