(57)【要約】      （修正有）【課題】制約条件を満たした上で評価関数が最適となる原料の配合割合を計画するにあたり、非線形変数を含む混合整数計画問題として定式化された原料配合計画問題を高速に解くことができる原料配合計画作成方法、コークス製造方法、混合整数計画問題の求解方法および原料配合計画作成装置を提供すること。【解決手段】原料配合計画作成方法は、非線形制約の非線形項に含まれる一つ以上の要素を異なる変数に置き換えてベクトル化するベクトル化ステップと、ベクトル変数に関する制約条件を追加する緩和制約条件作成ステップと、設定するベクトル変数の値を予め定めた所定の数だけ設定し、ベクトル変数の値を探索する第一の最適化ステップと、複数の線形計画問題群を構成し、操業指標の評価基準が改善されていくベクトル変数の値を探索する第二の最適化ステップと、混合整数計画問題によって最終解を得る最終解決定ステップと、を含む。【選択図】図４
2020149607.tif 000002
【特許請求の範囲】
【請求項１】
生産量制約および複数の原料の銘柄ごとの在庫制約を含む線形制約と、前記原料の配合後の性状制約を含む非線形式で与えられる非線形制約と、配合に使用する前記原料の銘柄数の上限を含む整数制約と、を含む制約条件を設定し、前記原料の配合に係る操業指標を評価基準として与え、前記制約条件および前記評価基準に基づいて、前記原料の各銘柄の配合量を決定する原料配合計画作成方法であって、
前記非線形制約に対して、非線形項に含まれる一つ以上の要素を異なる変数に置き換えてベクトル化し、ベクトル変数とするベクトル化ステップと、
前記整数制約を連続変数制約に変換し、前記ベクトル変数を用いて前記非線形制約を線形化し、前記ベクトル変数に関する制約条件を追加することにより、緩和制約条件を作成する緩和制約条件作成ステップと、
前記線形制約および前記緩和制約条件を含み、かつ前記操業指標を評価基準とした最適化問題が解を持つように、設定するベクトル変数の値を予め定めた所定の数だけ設定し、前記ベクトル変数の値を探索する第一の最適化ステップと、
前記第一の最適化ステップで探索した全てのベクトル変数または一部のベクトル変数に対して、前記線形制約および前記緩和制約条件を含み、かつ前記操業指標を評価基準とした複数の線形計画問題群を構成し、前記操業指標の評価基準が改善されていく前記ベクトル変数の値を探索する第二の最適化ステップと、
前記第二の最適化ステップで決定された一つのベクトル変数値に基づいて構成された、混合整数計画問題によって最終解を得る最終解決定ステップと、
を含む原料配合計画作成方法。
【請求項２】
前記第一の最適化ステップは、
前記線形制約および前記緩和制約条件を含み、かつ非線形項に含まれた要素であって、ベクトル変数の要素に置き換えられた要素が、前記非線形項に含まれた要素に対応するベクトル変数の要素との値の差をペナルティ項とし、前記ペナルティ項の和を評価関数とする線形計画問題を構成するステップと、
前記ベクトル変数の値を複数設定し、複数の線形計画問題群を構築し、前記複数の線形計画問題群の解を求めつつ、前記ペナルティ項の和の評価関数が０に漸近するように前記ベクトル変数をヒューリスティック解法によって探索するステップと、
を有する請求項１に記載の原料配合計画作成方法。
【請求項３】
前記第二の最適化ステップは、前記第二の最適化ステップで構成された複数の線形計画問題群に対して、前記複数の線形計画問題群の解を求めつつ、前記操業指標を評価基準として、前記ベクトル変数をヒューリスティック解法によって探索し、一つのベクトル変数値を決定するステップを有する請求項１または請求項２に記載の原料配合計画作成方法。
【請求項４】
前記最終解決定ステップは、前記第二の最適化ステップで得られたベクトル変数値に基づいて、前記非線形制約を線形化した混合整数計画問題の解を導出し、最終解を決定する請求項１から請求項３のいずれか一項に記載の原料配合計画作成方法。
【請求項５】
前記ヒューリスティック解法には、粒子群最適化法または遺伝的アルゴリズムが含まれる請求項２または請求項３に記載の原料配合計画作成方法。
【請求項６】
前記原料は、石炭であり、
前記非線形制約は、コークス強度推定式を含む、
請求項１から請求項５のいずれか一項に記載の原料配合計画作成方法。
【請求項７】
請求項１から請求項６のいずれか一項に記載の原料配合計画作成方法によって作成された原料配合計画に基づいてコークスを製造するコークス製造方法。
【請求項８】
線形式で与えられる線形制約と、非線形式で与えられる非線形制約と、整数制約と、を含む制約条件を設定し、所定の指標を評価基準として与え、前記制約条件および前記評価基準に基づいて、混合整数計画問題を解く混合整数計画問題の求解方法であって、
前記非線形制約に対して、非線形項に含まれる一つ以上の要素を異なる変数に置き換えてベクトル化し、ベクトル変数とするベクトル化ステップと、
前記整数制約を連続変数制約に変換し、前記ベクトル変数を用いて前記非線形制約を線形化し、前記ベクトル変数に関する制約条件を追加することにより、緩和制約条件を作成する緩和制約条件作成ステップと、
前記線形制約および前記緩和制約条件を含み、かつ前記所定の指標を評価基準とした最適化問題が解を持つように、設定するベクトル変数の値を予め定めた所定の数だけ設定し、前記ベクトル変数の値を探索する第一の最適化ステップと、
前記第一の最適化ステップで探索した全てのベクトル変数または一部のベクトル変数に対して、前記線形制約および前記緩和制約条件を含み、かつ前記所定の指標を評価基準とした複数の線形計画問題群を構成し、前記所定の指標の評価基準が改善されていく前記ベクトル変数の値を探索する第二の最適化ステップと、
前記第二の最適化ステップで決定された一つのベクトル変数値に基づいて構成された、混合整数計画問題によって最終解を得る最終解決定ステップと、
を含む混合整数計画問題の求解方法。
【請求項９】
生産量制約および複数の原料の銘柄ごとの在庫制約を含む線形制約と、前記原料の配合後の性状制約を含む非線形式で与えられる非線形制約と、配合に使用する前記原料の銘柄数の上限を含む整数制約と、を含む制約条件を設定し、前記原料の配合に係る操業指標を評価基準として与え、前記制約条件および前記評価基準に基づいて、前記原料の各銘柄の配合量を決定する原料配合計画作成装置であって、
前記非線形制約に対して、非線形項に含まれる一つ以上の要素を異なる変数に置き換えてベクトル化し、ベクトル変数とするベクトル化手段と、
前記整数制約を連続変数制約に変換し、前記ベクトル変数を用いて前記非線形制約を線形化し、前記ベクトル変数に関する制約条件を追加することにより、緩和制約条件を作成する緩和制約条件作成手段と、
前記線形制約および前記緩和制約条件を含み、かつ前記操業指標を評価基準とした最適化問題が解を持つように、設定するベクトル変数の値を予め定めた所定の数だけ設定し、前記ベクトル変数の値を探索する第一の最適化手段と、
前記第一の最適化手段で探索した全てのベクトル変数または一部のベクトル変数に対して、前記線形制約および前記緩和制約条件を含み、かつ前記操業指標を評価基準とした複数の線形計画問題群を構成し、前記操業指標の評価基準が改善されていく前記ベクトル変数の値を探索する第二の最適化手段と、
前記第二の最適化手段で決定された一つのベクトル変数値に基づいて構成された、混合整数計画問題によって最終解を得る最終解決定手段と、
を備える原料配合計画作成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、原料配合計画作成方法、コークス製造方法、混合整数計画問題の求解方法および原料配合計画作成装置に関する。
【背景技術】
【０００２】
近年、製鉄プロセスでは、各工程における生産計画、物流計画の最適化および立案自動化が進められている。原料工程では、原料を積載した船舶から荷役した原料をどのヤードに積み付けるかを決めるヤード配置問題、ヤードやパイル上の原料をどのベルトコンベア系列を用いていつ払い出すかを決める原料搬送問題、高炉に装入する原料配合問題等の計画問題等がある。
【０００３】
また、原料配合問題の一つに鉱石配合問題がある。この鉱石配合問題は、高炉の要求する性状制約等の制約条件を満たした上で、コストが最小となるような各銘柄の配合割合を考える問題である。この鉱石配合問題に関して、特許文献１では、生産物の性状と製造設備の能力とに関する制約を守り、原料の購買ならびに製造に掛かるコストを最小化する原料の購買計画および使用計画を作成する際に、制約式および評価関数が非線形式で与えられる場合であっても、それをベクトル変数として探索を実施する方法が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１８−７７８４０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、実際の操業では、設備上の制約等により配合に使用できる銘柄数に上限がある場合が多い。特許文献１では、非線形計画問題を線形計画問題に置き換える手法が開示されているが、銘柄数に制約がある場合、配合問題は非線形変数を含む混合整数計画問題となってしまうため、同様の処理を施しても線形計画問題よりも求解が格段に難しくなってしまう。
【０００６】
また、特許文献１で開示された手法は、一般的に高速に解くことができる線形計画問題では成立するが、線形計画問題と比べて計算時間が非常にかかる混合整数計画問題では、最適解を得ることが困難であるという問題があった。
【０００７】
本発明は、上記に鑑みてなされたものであって、制約条件を満たした上で評価関数が最適となる原料の配合割合を計画するにあたり、非線形変数を含む混合整数計画問題として定式化された原料配合計画問題を高速に解くことができる原料配合計画作成方法、コークス製造方法、混合整数計画問題の求解方法および原料配合計画作成装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するために、本発明に係る原料配合計画作成方法は、生産量制約および複数の原料の銘柄ごとの在庫制約を含む線形制約と、前記原料の配合後の性状制約を含む非線形式で与えられる非線形制約と、配合に使用する前記原料の銘柄数の上限を含む整数制約と、を含む制約条件を設定し、前記原料の配合に係る操業指標を評価基準として与え、前記制約条件および前記評価基準に基づいて、前記原料の各銘柄の配合量を決定する原料配合計画作成方法であって、前記非線形制約に対して、非線形項に含まれる一つ以上の要素を異なる変数に置き換えてベクトル化し、ベクトル変数とするベクトル化ステップと、前記整数制約を連続変数制約に変換し、前記ベクトル変数を用いて前記非線形制約を線形化し、前記ベクトル変数に関する制約条件を追加することにより、緩和制約条件を作成する緩和制約条件作成ステップと、前記線形制約および前記緩和制約条件を含み、かつ前記操業指標を評価基準とした最適化問題が解を持つように、設定するベクトル変数の値を予め定めた所定の数だけ設定し、前記ベクトル変数の値を探索する第一の最適化ステップと、前記第一の最適化ステップで探索した全てのベクトル変数または一部のベクトル変数に対して、前記線形制約および前記緩和制約条件を含み、かつ前記操業指標を評価基準とした複数の線形計画問題群を構成し、前記操業指標の評価基準が改善されていく前記ベクトル変数の値を探索する第二の最適化ステップと、前記第二の最適化ステップで決定された一つのベクトル変数値に基づいて構成された、混合整数計画問題によって最終解を得る最終解決定ステップと、を含む。
【０００９】
また、本発明に係る原料配合計画作成方法は、上記発明において、前記第一の最適化ステップが、前記線形制約および前記緩和制約条件を含み、かつ非線形項に含まれた要素であって、ベクトル変数の要素に置き換えられた要素が、前記非線形項に含まれた要素に対応するベクトル変数の要素との値の差をペナルティ項とし、前記ペナルティ項の和を評価関数とする線形計画問題を構成するステップと、前記ベクトル変数の値を複数設定し、複数の線形計画問題群を構築し、前記複数の線形計画問題群の解を求めつつ、前記ペナルティ項の和の評価関数が０に漸近するように前記ベクトル変数をヒューリスティック解法によって探索するステップと、を有する。
【００１０】
また、本発明に係る原料配合計画作成方法は、上記発明において、前記第二の最適化ステップが、前記第二の最適化ステップで構成された複数の線形計画問題群に対して、前記複数の線形計画問題群の解を求めつつ、前記操業指標を評価基準として、前記ベクトル変数をヒューリスティック解法によって探索し、一つのベクトル変数値を決定するステップを有する。
【００１１】
また、本発明に係る原料配合計画作成方法は、上記発明において、前記最終解決定ステップが、前記第二の最適化ステップで得られたベクトル変数値に基づいて、前記非線形制約を線形化した混合整数計画問題の解を導出し、最終解を決定する。
【００１２】
また、本発明に係る原料配合計画作成方法は、上記発明において、前記ヒューリスティック解法には、粒子群最適化法または遺伝的アルゴリズムが含まれる。
【００１３】
また、本発明に係る原料配合計画作成方法は、上記発明において、前記原料が、石炭であり、前記非線形制約が、コークス強度推定式を含む。
【００１４】
上述した課題を解決し、目的を達成するために、本発明に係るコークス製造方法は、上記発明に係る原料配合計画作成方法によって作成された原料配合計画に基づいてコークスを製造する。
【００１５】
上述した課題を解決し、目的を達成するために、本発明に係る混合整数計画問題の求解方法は、線形式で与えられる線形制約と、非線形式で与えられる非線形制約と、整数制約と、を含む制約条件を設定し、所定の指標を評価基準として与え、前記制約条件および前記評価基準に基づいて、混合整数計画問題を解く混合整数計画問題の求解方法であって、前記非線形制約に対して、非線形項に含まれる一つ以上の要素を異なる変数に置き換えてベクトル化し、ベクトル変数とするベクトル化ステップと、前記整数制約を連続変数制約に変換し、前記ベクトル変数を用いて前記非線形制約を線形化し、前記ベクトル変数に関する制約条件を追加することにより、緩和制約条件を作成する緩和制約条件作成ステップと、前記線形制約および前記緩和制約条件を含み、かつ前記所定の指標を評価基準とした最適化問題が解を持つように、設定するベクトル変数の値を予め定めた所定の数だけ設定し、前記ベクトル変数の値を探索する第一の最適化ステップと、前記第一の最適化ステップで探索した全てのベクトル変数または一部のベクトル変数に対して、前記線形制約および前記緩和制約条件を含み、かつ前記所定の指標を評価基準とした複数の線形計画問題群を構成し、前記所定の指標の評価基準が改善されていく前記ベクトル変数の値を探索する第二の最適化ステップと、前記第二の最適化ステップで決定された一つのベクトル変数値に基づいて構成された、混合整数計画問題によって最終解を得る最終解決定ステップと、を含む。
【００１６】
上述した課題を解決し、目的を達成するために、本発明に係る原料配合計画作成装置は、生産量制約および複数の原料の銘柄ごとの在庫制約を含む線形制約と、前記原料の配合後の性状制約を含む非線形式で与えられる非線形制約と、配合に使用する前記原料の銘柄数の上限を含む整数制約と、を含む制約条件を設定し、前記原料の配合に係る操業指標を評価基準として与え、前記制約条件および前記評価基準に基づいて、前記原料の各銘柄の配合量を決定する原料配合計画作成装置であって、前記非線形制約に対して、非線形項に含まれる一つ以上の要素を異なる変数に置き換えてベクトル化し、ベクトル変数とするベクトル化手段と、前記整数制約を連続変数制約に変換し、前記ベクトル変数を用いて前記非線形制約を線形化し、前記ベクトル変数に関する制約条件を追加することにより、緩和制約条件を作成する緩和制約条件作成手段と、前記線形制約および前記緩和制約条件を含み、かつ前記操業指標を評価基準とした最適化問題が解を持つように、設定するベクトル変数の値を予め定めた所定の数だけ設定し、前記ベクトル変数の値を探索する第一の最適化手段と、前記第一の最適化手段で探索した全てのベクトル変数または一部のベクトル変数に対して、前記線形制約および前記緩和制約条件を含み、かつ前記操業指標を評価基準とした複数の線形計画問題群を構成し、前記操業指標の評価基準が改善されていく前記ベクトル変数の値を探索する第二の最適化手段と、前記第二の最適化手段で決定された一つのベクトル変数値に基づいて構成された、混合整数計画問題によって最終解を得る最終解決定手段と、を備える。
【発明の効果】
【００１７】
本発明によれば、非線形変数を含む混合整数計画問題として定式化された原料配合計画問題を高速に解くことができる。すなわち、配合に使用する原料の銘柄数の上限と、原料の配合後の性状とに関する制約を含む原料配合計画問題を高速に解くことができる。
【図面の簡単な説明】
【００１８】
【図１】図１は、線形計画問題の解領域および実行可能領域を示す模式図であるである。
【図２】図２は、混合整数計画問題の解領域および実行可能領域を示す模式図である。
【図３】図３は、本発明の実施形態に係る原料配合計画作成装置の概略的な構成を示す模式図である。
【図４】図４は、本発明の実施形態に係る原料配合計画作成方法の流れを示すフローチャートである。
【図５】図５は、本発明の実施形態に係る原料配合計画作成方法において、緩和条件求解ステップの詳細を示すフローチャートである。
【図６】図６は、緩和制約条件作成ステップの概要を説明するための図である。
【図７】図７は、粒子群最適化法の概要を説明するための図である。
【図８】図８は、本発明の実施形態に係る原料配合計画作成方法において、真の計画問題求解ステップの詳細を示すフローチャートである。
【図９】図９は、本発明の実施形態に係る原料配合計画作成方法の実施例であり、原料配合計画を立案した際の評価値の推移を示すグラフである。
【発明を実施するための形態】
【００１９】
本発明の実施形態に係る原料配合計画作成方法、コークス製造方法、混合整数計画問題の求解方法および原料配合計画作成装置について、図面を参照しながら説明する。なお、本発明は以下で説明する実施形態に限定されるものではない。
【００２０】
まず、本発明が適用される原料配合計画の最適化問題の概要について説明する。鉄鋼業界では、購入した種々の性状を有する多種類の鉄鉱石や石炭等の原料を混合して、混合後の品質および性状を一定範囲内に収めることが求められている。また、この際にはコストが重要な指標として判断されるため、購入コスト、製造コスト等の最小化が求められる。更に、原料の在庫が切れないように、配合割合を変化させながら複数日に亘って、配合を計画することが求められる。本発明では、原料配合計画を最適化問題として定式化している。本発明が対象とする原料配合計画の最適化問題は、例えば下記式（１）、（２）のように表すことができる。
【００２１】
【数１】
2020149607.tif 000003
【００２２】
ここで、上記式（１）、（２）において、Ｆはｎ次元ベクトル空間Ｒｎの部分集合、ｆはＲｎで定義された評価関数である。
【００２３】
図１は、線形計画問題（ＬＰ：Linear  Programming  Problem）の解領域および実行可能領域を示す模式図である。線形計画問題では、上記評価関数および制約条件は線形である。また、同図の多角形は、線形計画問題の実行可能領域を示している。線形計画問題を解く場合、多角形の頂点（同図の破線丸参照）のみを探索すればよいため、高速計算が可能である。
【００２４】
図２は、混合整数計画問題（ＭＩＰ：Mixed  Integer  Programming  Problem）の解領域および実行可能領域を示す模式図である。混合整数計画問題は、実行可能領域が凸多角形（図１参照）である線形計画問題とは異なり、実行可能領域が同図に示すような非連続の図形となっている。そのため、混合整数計画問題を解く場合、非連続な図形上の点を探索する必要があり、計算に時間を要する。また、混合整数計画問題に非線形の変数が加わると、更に複雑となる。
【００２５】
上記式（１）における評価関数の値は、最適化問題に応じて所定の数値とすることができる。たとえば、最小値や最大値、あるいは予め定められた所定の値とすることができる。以下では、本発明の対象である原料配合問題を例として、下記式（３）〜（９）に示すような数理モデルを定式化し、最適化問題を考える。
【００２６】
【数２】
2020149607.tif 000004
【００２７】
上記式（３）〜（９）において、ｘｉ，ｊを各計画期間ｊにおける銘柄ｉの配合量、ｓを各計画期間ｊにおける銘柄ｉの在庫量、Ｃを銘柄ｉのコスト、Ｎを各計画期間ｊにおける配合量の総和、ｄｉ，ｅｉ，ｋｉを銘柄ｉのある成分、ｙｉ，ｊを銘柄ｉが配合されるか否かの０−１変数、とした場合、上記式（３）〜（９）は、以下を示す式となる。
【００２８】
式（３）：配合後の計画のコストを示す式
式（４）：各計画期間ｊで充足すべき配合量に関する制約を示す式
式（５）：銘柄ごとの在庫制約を示す式
式（６）、（７）：配合後の性状制約を示す式
式（８）：配合に使用する銘柄数の上限制約を示す式
式（９）：式は銘柄ｉを使用するか否かを示す式
【００２９】
なお、上記式（６）のような性状制約は複数あってもよい。また、上記式（３）〜（９）中におけるＣ，Ｃ１，Ｃ２は定数である。また、全ての変数および定数は非負の実数である。
【００３０】
また、上記式（３）で示される評価関数は、ここでは配合後の計画のコストを用いているが、他の態様であっても構わない。例えば、期間的に隣接する計画期間での各原料銘柄の使用量ｘｉ，ｊに関する配合率の変化幅を用い、この変化幅を最小化する式としてもよい。これは、例えば原料配合の仕方が日替わりで大きく変わるよりも、配合の仕方が類似しているほうが操業条件の変化が小さいため、操業上の負担を小さくできるためである。いずれにしろ、上記式（３）で示される評価関数は、原料の配合に係る操業指標であればよく、場合によって、その操業指標の最小化または最大化を目的とすればよい。
【００３１】
ここで、上記式（７）は、二次の非線形変数を含むため、そのまま扱うと非線形計画問題となる。しかも、上記式（８）は、左辺に０−１変数を含むため、求解が非常に困難である。そこで、本発明では、上記式（７）の非線形変数をベクトル変数に置き換え（後記する図５のステップＳ３１，Ｓ３２）、上記式（８）のｙは「０以上１以下」の連続変数に近似し（同図のステップＳ３３）、下記式（１０）〜（１９）に示すような数理モデルを定式化する（同図のステップＳ３４）。
【００３２】
【数３】
2020149607.tif 000005
【００３３】
ここで、上記式（１４）、（１５）におけるベクトル変数ｇｊｋは、計画期間ｊにおけるΣｅｉｘｉ，ｊの近似値の定数を示している。また、上記式（１５）におけるｐｊは、近似値との差を示すペナルティ変数である。
【００３４】
上記式（１４）、（１５）により、上記式（７）を線形式で表すことができる。また、上記式（１８）、（１９）は、上記式（９）を緩和した式であり、０−１のバイナリ変数ｙを０〜１の連続変数とし、十分に大きい定数Ｍによって緩和する「ｂｉｇ−Ｍ法」と呼ばれる手法を用いている。なお、今回は、Ｍ＝ΣｊＮｊとした。
【００３５】
ここで、上記式（１５）のペナルティ変数ｐｊを用いたのは、上記式（７）の非線形項を特定の固定値にそのまま置き換えた場合、解が得られる保証がないためである。そのため、式（１５）のようなペナルティ変数ｐｊ（ｐｊ≧０）を加えた上で、そのペナルティ変数ｐｊが０となるように最小化問題を解いて、上記式（３）〜（９）の解が得られるようなパラメータ（ベクトル変数ｇｊｋ）の候補を探索する。
【００３６】
また、上記式（１０）〜（１９）に示す数理モデルは、上記式（１４）のベクトル変数ｇｊｋの値によって大きく左右されるため、設定する定数の組み合わせとなるベクトルをＫ個用意する。すなわち、Ｋ個の緩和問題が定式化され、その評価関数値を比較することによってＪ次元のベクトル変数ｇｊｋの値を更新し（後記する図５のステップＳ３６）、上記式（１０）の評価関数が最小、すなわち０となるまで探索していく。
【００３７】
ベクトル変数ｇｊｋの値の更新には、例えば粒子群最適化法（ＰＳＯ：Particle  Swarm  Optimization）や遺伝的アルゴリズム（ＧＡ：Genetic  Algorithm）等のヒューリスティック解法を用いることができる。以下では、粒子群最適化法を用いた例を説明する。
【００３８】
粒子群最適化法のアルゴリズムは、生物の集団行動にヒントを得たメタヒューリスティックスであり、探索の対象となる評価関数が与えられたとき、複数の粒子が互いに情報を共有しながら最適解を求めて探索空間内を動き回るというものである。粒子群最適化法は、このような概念とアルゴリズムの簡素さ、動作の柔軟さ、改良の可能性等を特徴としている。粒子群最適化法のアルゴリズムでは、下記式（２０）、（２１）に従って各非線形ベクトルの成分を更新する。
【００３９】
【数４】
2020149607.tif 000006
【００４０】
上記式（２０）、（２１）において、ａｍｋは時刻ｍ∈Ｍにおけるベクトル変数ｋ∈Ｋの更新ベクトル、ｂｍｋは時刻ｍにおけるベクトル変数ｋの位置ベクトル（座標）、ｒ，Ｃはそれぞれ乱数によって与えられるパラメータを示している。また、Ｐｋは、各粒子（各ベクトル変数）ｋが時刻ｍまでに取った最良の位置ベクトルを示すパーソナルベスト、Ｇｍは、全粒子（全ベクトル変数）が時刻ｍまでに取った最良の位置ベクトルを示すグローバルベスト、を示している。問題設定が最小化問題である場合には、目的関数値が小さくなれば、パーソナルベストＰｋおよびグローバルベストＧｍを更新する。
【００４１】
本発明において、位置ベクトルｂｍｋは、上記式（１０）〜（１９）の数理モデルにおける、時刻ｍのベクトル変数ｇｊｋに相当する。上記式（１０）〜（１９）の数理モデルでは、評価値（評価関数の値）が０、または予め定めた極小の所定値（ほとんど０とみなせる値）以下となったときに終了条件を満たすものとし、終了条件を満たすと（図５のステップＳ３７でＹｅｓ）、探索を終了する。そして、探索が終了した時点でＬ個の粒子を選択し、改めてベクトル変数ｇｊｋを設定し、以下の緩和問題を解いていく。ここでＬ個の粒子は、前記した粒子群最適化法のアルゴリズムで探索したベクトル変数について、評価関数最小化後の任意のＬ個を選択してよい。また、評価関数が小さいものからＬ個選択してもよい。あるいは、探索に用いたＫ個の粒子のパラメータを全て用いてもよい。
【００４２】
上記式（１０）の評価関数値が０になると、上記式（１４）、（１５）が上記式（７）と同じ意味を成すことになる。そのため、上記で選択されたベクトル変数ｇｊｋを用いて、上記式（１０）〜（１９）の数理モデルを、下記式（２２）〜（３０）に示す数理モデルに切り替える（後記する図５のステップＳ３８，Ｓ３９）。これにより、元の数理モデル（上記式（３）〜（９））の下界を解くことになる（同図のステップＳ４０）。
【００４３】
【数５】
2020149607.tif 000007
【００４４】
上記式（２２）〜（３０）に示す数理モデルについても、上記式（２６）のベクトル変数ｇｊｋの値によって大きく左右される。そのため、設定する定数の組み合わせとなるベクトルは、上記式（１０）〜（１９）の数理モデルと粒子群最適化法によって得られたＬ個のベクトルとする。すなわち、Ｌ個の緩和問題が定式化され、その評価関数値を比較することによってＪ次元のベクトル変数ｇｊｋの値を更新する（後記する図５のステップＳ４１）。
【００４５】
ベクトル変数ｇｊｋの値の更新には、例えば粒子群最適化法や遺伝的アルゴリズム等のヒューリスティック解法を用いることができる。以下では、粒子群最適化法を用いた例を説明する。粒子群最適化法のアルゴリズムは上記の通りであり、上記式（２０）、（２１）に従って各非線形ベクトルの成分を更新する。ベクトル変数の更新の手順は、対象とする数理モデルが上記式（２２）〜（３０）であることを除いて、前記した通りである。
【００４６】
すなわち、Ｌ個の位置ベクトルｂｍｋに対して、上記式（２２）〜（３０）の数理モデルを解き、評価関数値（式（１９）のｆ（ｘ））を用いてパーソナルベストＰｋおよびグローバルベストＧｍとともに位置ベクトルｂｍｋを更新し、予め定められた終了条件を満たすと（後記する図５のステップＳ４２でＹｅｓ）、グローバルベストＧｍを出力する（同図のステップＳ４３）。終了条件は、例えば繰り返し回数を定める方法や、評価関数の変化量等により定めることができる。
【００４７】
そして、出力されたグローバルベストＧｍに対して、下記式（３１）〜（３８）の数理モデルで示される混合整数計画問題を解く（図４のステップＳ４）。
【００４８】
【数６】
2020149607.tif 000008
【００４９】
但し、ｋ∈Ｌ∈Ｋである。以上の手順により、非線形変数を含む混合整数計画問題を高速に解くことができる。
【００５０】
［原料配合計画作成装置］
本発明の実施形態に係る原料配合計画作成装置の構成について、図３を参照しながら説明する。原料配合計画作成装置１は、入力部１０と、出力部２０と、演算部３０と、を備えている。
【００５１】
入力部１０は、演算部３０に対する入力手段であり、例えばキーボード、マウスポインタ、テンキー等の入力装置によって実現される。
【００５２】
出力部２０は、例えばＬＣＤディスプレイ、ＣＲＴディスプレイ等の表示装置によって実現され、演算部３０から入力される表示信号をもとに、計算結果等を表示する。
【００５３】
演算部３０は、例えばＣＰＵ（Central  Processing  Unit）等からなるプロセッサと、ＲＡＭ（Random  Access  Memory）やＲＯＭ（Read  Only  Memory）等からなるメモリ（主記憶部）と、によって実現される。
【００５４】
演算部３０は、プログラムを主記憶部の作業領域にロードして実行し、プログラムの実行を通じて各構成部等を制御することにより、所定の目的に合致した機能を実現する。演算部３０は、プログラムの実行を通じて、求解部３１として機能する。
【００５５】
［原料配合計画作成方法］
本発明の実施形態に係る原料配合計画作成方法について、図４〜図８を参照しながら説明する。本実施形態に係る原料配合計画作成方法は、非線形変数を含む混合整数計画問題として定式化された原料配合計画において、制約条件を満たした上で評価関数が最適となる原料の配合割合を決定するための方法である。本実施形態に係る原料配合計画作成方法では、具体的には、線形制約、非線形制約および整数制約を含む制約条件を設定し、原料の配合に係る操業指標を評価基準として与え、制約条件および評価基準に基づいて、原料の各銘柄の配合量を決定する。
【００５６】
ここで、前記した原料としては、例えば石炭が挙げられる。例えば本実施形態に係る原料配合計画作成方法によって原料配合計画を作成し、当該原料配合計画に従って複数銘柄の石炭を配合した後、コークス炉で乾留することにより、コークスを製造することができる。
【００５７】
また、前記した線形制約としては、例えばコークスの計画生産量に関する生産量制約や、複数の原料の銘柄ごとの在庫制約等が挙げられる。また、前記した非線形制約は、非線形式で与えられ、複数銘柄の原料を配合した後の性状制約等を示している。また、前記した整数制約は、配合に使用する原料の銘柄数の上限を示している。
【００５８】
本実施形態に係る原料配合計画作成方法は、後記するように、ベクトル化ステップＳ３１と、緩和制約条件作成ステップＳ３３と、線形制約および緩和制約条件を含み、かつ操業指標を評価基準とした最適化問題が解を持つように、設定するベクトル変数の値を予め定めた所定の数だけ設定し、ベクトル変数の値を探索する第一の最適化ステップ（第一の緩和問題作成ステップＳ３４〜ベクトル変数更新ステップＳ３６）と、を行い、予め定められた終了条件を満たすまで第一の最適化ステップを繰り返し（第一の緩和問題繰り返しステップＳ３７）、終了条件を満たした際のベクトル変数群を決定するベクトル変数設定ステップＳ３８を行う。
【００５９】
続いて、第一の最適化ステップで探索した全てのベクトル変数または一部のベクトル変数に対して、線形制約および緩和制約条件を含み、かつ操業指標を評価基準とした複数の線形計画問題群を構成し、操業指標の評価基準が改善されていくベクトル変数の値を探索する第二の最適化ステップ（ベクトル変数設定ステップＳ３８〜ベクトル変数更新ステップＳ４１）を行い、予め定められた終了条件を満たすまで第二の最適化ステップを繰り返し（第二の緩和問題繰り返しステップＳ４２）、終了条件を満たした際の第二の最適化ステップで決定された一つのベクトル変数値に基づいて構成された、混合整数計画問題によって最終解を得る最終解決定ステップ（真の計画問題求解ステップＳ４）を行う。
【００６０】
以下、本実施形態に係る原料配合計画作成方法の詳細について説明する。本実施形態に係る原料配合計画作成方法は、図４に示すように、入力データ取り込みステップＳ１と、制約条件取り込みステップＳ２と、緩和問題求解ステップＳ３と、真の計画問題求解ステップＳ４と、結果出力ステップＳ５と、をこの順番で行う。なお、同図に示した各ステップは、演算部３０の求解部３１が主体となって実施される。
【００６１】
（入力データ取り込みステップＳ１）
入力データ取り込みステップＳ１では、入力部１０を介して、原料配合計画の立案に必要な入力データを取り込む。この入力データとしては、例えば在庫、入荷、操業計画、配合計画に使用する銘柄の性状に関する情報が挙げられる。
【００６２】
（制約条件取り込みステップＳ２）
制約条件取り込みステップＳ２では、入力部１０を介して、原料の配合後に求められる性状、在庫の上下限、操業条件等の、原料配合計画を立案する上で必要となる複数の制約条件を取り込む。
【００６３】
（緩和問題求解ステップＳ３）
緩和問題求解ステップＳ３では、入力データ取り込みステップＳ１で取り込んだ入力データと、制約条件取り込みステップＳ２で取り込んだ制約条件とをもとに、非線形変数を含む混合整数計画問題を緩和した問題を定式化し、求解する。なお、緩和問題求解ステップＳ３の詳細については後記する。
【００６４】
（真の計画問題求解ステップＳ４）
真の計画問題求解ステップＳ４では、緩和問題求解ステップＳ３で緩和問題を解いて得られた結果をもとに、元の非線形変数を含む混合整数計画問題を定式化し、求解する。すなわち、真の計画問題求解ステップＳ４では、緩和問題求解ステップＳ３で得られたベクトル変数値に基づいて、非線形制約を線形化した混合整数計画問題の解を導出し、最終解を決定する。なお、真の計画問題求解ステップＳ４の詳細については後記する。
【００６５】
（結果出力ステップＳ５）
結果出力ステップＳ５では、出力部２０を介して、真の計画問題求解ステップＳ４で得られた結果を出力する。
【００６６】
＜緩和問題求解ステップＳ３の詳細＞
緩和問題求解ステップＳ３は、具体的には図５に示すように、ベクトル化ステップＳ３１と、ベクトル変数の組み合わせ作成ステップＳ３２と、緩和制約条件作成ステップＳ３３と、第一の緩和問題作成ステップＳ３４と、第一の緩和問題最適化ステップＳ３５と、ベクトル変数更新ステップＳ３６と、第一の緩和問題繰り返しステップＳ３７とを実施し、真の最適化問題に対応するベクトル変数を定め、その後、第二の緩和問題のベクトル変数設定ステップＳ３８を実施する。そして引き続き、第二の緩和問題作成ステップＳ３９と、第二の緩和問題最適化ステップＳ４０と、ベクトル変数更新ステップＳ４１と、第二の緩和問題繰り返しステップＳ４２と、緩和解出力ステップＳ４３と、をこの順番で行う。
【００６７】
（ベクトル化ステップＳ３１）
ベクトル化ステップＳ３１では、一つ以上の非線形制約に含まれる非線形項、または非線形項に含まれる一部の変数（要素）を異なる変数に置き換え、置き換えた変数をベクトル化する。ベクトル化ステップＳ３１では、具体的には、入力データ取り込みステップで取り込んだ非線形変数（上記式（７）参照）を、一次元以上のベクトル変数（上記式（１４）の「ベクトル変数ｇｊｋ」参照）として定義し、ベクトル化する。
【００６８】
（ベクトル変数の組み合わせ作成ステップＳ３２）
ベクトル変数の組み合わせ作成ステップＳ３２では、ベクトル化ステップＳ３１でベクトル化された非線形項に対応する変数（上記式（１４）の「ベクトル変数ｇｊｋ」参照）を、予め定められた組み合わせ数だけ作成する。
【００６９】
（緩和制約条件作成ステップＳ３３）
緩和制約条件作成ステップＳ３３では、整数制約を連続変数制約に変換する。緩和制約条件作成ステップＳ３３では、制約条件取り込みステップＳ２で取り込んだ制約条件と、ベクトル変数の組み合わせ作成ステップＳ３２で作成された複数のベクトル変数とが満たすべき制約条件について、オリジナルの制約条件（上記式（３）〜（９）参照）を緩和した形で定義した制約条件一式を、前記ベクトル変数の組み合わせ数だけ作成する。緩和制約条件作成ステップＳ３３では、整数制約を連続変数制約に変換し、ベクトル変数を用いて非線形制約を線形化し、ベクトル変数に関する制約条件を追加することにより、緩和制約条件を作成する。
【００７０】
緩和制約条件作成ステップＳ３３では、具体的には、オリジナルの制約条件（上記式（３）〜（９）参照）に含まれる０−１変数（上記式（８）参照）を、０〜１の連続変数に近似することにより、線形計画問題（線形制約問題）に変更する。そして、図６に示すように、元問題の下界となる近似線形計画問題の群を解き、下界の最適解の近傍を探索する。これにより、元問題を効率良く解くことができる。なお、線形計画問題に変更することにより、前記した図１と同様に解領域が多角形となる。そのため、多角形の頂点のみを探索すればよく、高速計算が可能となる。
【００７１】
（第一の緩和問題作成ステップＳ３４）
第一の緩和問題作成ステップＳ３４では、緩和制約条件作成ステップＳ３３で作成された緩和制約条件と、オリジナルの制約条件（上記式（３）〜（９）参照）を満たすほど評価関数値が改善するような線形変数で定義された評価関数により構成された緩和問題一式（上記式（１０）〜（１９）参照）を、ベクトル変数の組み合わせ数だけ作成する。
【００７２】
第一の緩和問題作成ステップＳ３４では、具体的には、線形制約および緩和制約条件を含み、かつ非線形項に含まれた要素であって、ベクトル変数の要素に置き換えられた要素が、非線形項に含まれた要素に対応するベクトル変数の要素との値の差をペナルティ項とし、ペナルティ項の和を評価関数とする線形計画問題を構成する。
【００７３】
（第一の緩和問題最適化ステップＳ３５）
第一の緩和問題最適化ステップＳ３５では、第一の緩和問題作成ステップＳ３４で作成された緩和問題一式を求解する。
【００７４】
（ベクトル変数更新ステップＳ３６）
ベクトル変数更新ステップＳ３６では、第一の緩和問題最適化ステップＳ３５で得られた緩和解一式に対して、ベクトル変数の成分を更新する。ベクトル変数更新ステップＳ３６では、具体的には、第一の緩和問題最適化ステップＳ３５で得られた緩和解と評価値（ここでは式（１０））とをもとに、予め定められたアルゴリズムに従って、ベクトル変数の座標（位置ベクトル）を更新する。このベクトル変数の座標を更新する際のアルゴリズムには、例えば粒子群最適化法を用いる。
【００７５】
粒子群最適化法では、図７に示すように、各探索ユニットについて、座標および評価値の情報を共有しながら、現状ベスト（パーソナルベスト、グローバルベスト）の座標方向へと座標を確率的に更新する。これにより、探索ユニットのより良い座標を探索する。なお、同図における探索ユニットは、本実施形態における「ベクトル変数」に相当する。
【００７６】
このように、第一の緩和問題最適化ステップＳ３５およびベクトル変数更新ステップＳ３６では、ベクトル変数の値を複数設定し、複数の線形計画問題群を構築し、複数の線形計画問題群の解を求めつつ、ペナルティ項の和の評価関数が０に漸近するようにベクトル変数をヒューリスティック解法によって探索する。
【００７７】
（第一の緩和問題繰り返しステップＳ３７）
第一の緩和問題繰り返しステップＳ３７では、ベクトル変数更新ステップＳ３６で更新されたベクトル変数の組み合わせについて、第一の緩和問題最適化ステップＳ３５およびベクトル変数更新ステップＳ３６を繰り返す。第一の緩和問題繰り返しステップＳ３７では、具体的には、予め定められた終了条件（ペナルティ変数ｐｊの総和が０または極小の所定値以下）を満たさない場合は第一の緩和問題最適化ステップＳ３５に戻り、終了条件を満たす場合は繰り返し処理を終了し、第二の緩和問題のベクトル変数設定ステップＳ３８に進む。
【００７８】
（ベクトル変数設定ステップＳ３８）
ベクトル変数設定ステップＳ３８では、第一の緩和問題の最適解として得られたベクトル変数（上記式（２６）の「ベクトル変数ｇｊｋ」参照）を予め定めた個数だけ取得し、設定する。
【００７９】
（第二の緩和問題作成ステップＳ３９）
第二の緩和問題作成ステップＳ３９では、前記したように、第一の緩和問題作成ステップＳ３４で作成された緩和問題の解（以下、「緩和解」という）が最適解となった時点におけるベクトル変数ｇｊｋを利用する。このベクトル変数を用いて、第一の緩和問題作成ステップＳ３４で緩和する前のオリジナルの制約条件（上記式（３）〜（９）参照）と、予め定められた真の評価関数に置き換えた緩和問題一式（上記式（２２）〜（３０）参照）とを、前記ベクトル変数の組み合わせ数だけ作成する。
【００８０】
（第二の緩和問題最適化ステップＳ４０）
第二の緩和問題最適化ステップＳ４０では、第二の緩和問題作成ステップＳ３９で作成された緩和問題一式を求解する。
【００８１】
（ベクトル変数更新ステップＳ４１）
ベクトル変数更新ステップＳ４１では、第二の緩和問題最適化ステップＳ４０で得られた緩和解一式に対して、ベクトル変数の成分を更新する。ベクトル変数更新ステップＳ４１では、具体的には、第二の緩和問題最適化ステップＳ４０で得られた緩和解と評価値とをもとに、予め定められたアルゴリズムに従って、ベクトル変数の座標（位置ベクトル）を更新する。このベクトル変数の座標を更新する際のアルゴリズムには、例えば粒子群最適化法を用いる。この粒子群最適化法は、前記した通りである。
【００８２】
このように、第二の緩和問題最適化ステップＳ４０およびベクトル変数更新ステップＳ４１では、複数の線形計画問題群に対して、複数の線形計画問題群の解を求めつつ、操業指標を評価基準として、ベクトル変数をヒューリスティック解法によって探索し、一つのベクトル変数値を決定する。
【００８３】
（第二の緩和問題繰り返しステップＳ４２）
第二の緩和問題繰り返しステップＳ４２では、ベクトル変数更新ステップＳ４１で更新されたベクトル変数の組み合わせについて、第二の緩和問題最適化ステップＳ４０およびベクトル変数更新ステップＳ４１を繰り返す。第二の緩和問題繰り返しステップＳ４２では、具体的には、予め定められた終了条件（繰り返し回数）を満たさない場合は第二の緩和問題最適化ステップＳ４０に戻り、終了条件を満たす場合は繰り返し処理を終了し、緩和解出力ステップＳ４３に進む。
【００８４】
（緩和解出力ステップＳ４３）
緩和解出力ステップＳ４３では、ベクトル変数の位置ベクトルと、緩和解および評価値とを結びつけた形で緩和解一式を出力し、真の計画問題求解ステップＳ４へと進む。
【００８５】
＜真の計画問題求解ステップＳ４の詳細＞
真の計画問題求解ステップＳ４は、具体的には図８に示すように、ベクトル変数設定ステップＳ５１と、真の計画問題作成ステップＳ５２と、真の計画問題最適化ステップＳ５３と、をこの順番で行う。
【００８６】
（ベクトル変数設定ステップＳ５１）
ベクトル変数設定ステップＳ５１では、緩和解出力ステップＳ４３で出力された緩和解のグローバルベストＧｍのベクトル変数を取得し、真の計画問題作成ステップＳ５２に進む。
【００８７】
（真の計画問題作成ステップＳ５２）
真の計画問題作成ステップＳ５２では、ベクトル変数設定ステップＳ５１で取得されたベクトル変数に対して、オリジナルの制約条件（上記式（３）〜（９））と、予め定められた評価関数とで構成される真の計画問題（上記式（３１）〜（３８）参照）を作成する。真の計画問題作成ステップＳ５２では、具体的には、入力データ取り込みステップＳ１および制約条件取り込みステップＳ２で取り込まれた入力データおよび制約条件と、ベクトル変数設定ステップＳ５１で作成した非線形変数とを含む制約条件を線形式に置き換えた制約条件を定める。そして、予め定められた評価関数によって定義された真の計画問題を定式化する。
【００８８】
（真の計画問題最適化ステップＳ５３）
真の計画問題最適化ステップＳ５３では、真の計画問題作成ステップＳ５２で作成された真の計画問題（数理モデル）を解き、結果出力ステップＳ５に進む。
【００８９】
以上説明したような本実施形態に係る原料配合計画作成方法によれば、非線形変数を含む混合整数計画問題として定式化された原料配合計画問題を高速に解くことができる。すなわち、配合に使用する原料の銘柄数の上限と、原料の配合後の性状とに関する制約を含む原料配合計画問題を高速に解くことができる。
【実施例】
【００９０】
本実施形態に係る原料配合計画作成方法の実施例について、図９を参照しながら説明する。同図は、本実施形態に係る原料配合計画作成方法によって原料配合計画を立案した際の評価値の推移を示すグラフである。本実施例では、５０種類以上の原料炭をブレンドする石炭配合計画を３ヶ月分立案した。
【００９１】
本実施例では、非線形制約として、二次以上の関数として定義されたコークス強度推定式を用いた。また、本実施例では、第二の緩和問題繰り返しステップＳ４２における終了条件は１０ループとし、ベクトル変数設定ステップＳ５１では、グローバルベストＧｍのベクトル変数を取得し、真の計画問題最適化ステップＳ５３では、市販のパーソナルコンピュータにて、計算時間を６０秒で終了とした。また、本発明に係る手法は、ベクトル変数の初期値に影響を受けるため、数値実験を１０回実施した。
【００９２】
図９に示すように、本発明に係る手法を用いることにより、高速に計算が収束することがわかる。すなわち、約１５分（９００秒）の計算で十分に収束している。なお、本発明に係る手法では、性質上評価関数が切り替わるため、同図では、第一の緩和問題求解中のプロットは消去している。
【００９３】
表１，２は、本実施例で解として出力された原料配合計画の一部を示している。同表に示すように、設定した制約条件を全て満たした実行可能解が得られていることがわかる。
【００９４】
【表１】
2020149607.tif 000009
【表２】
2020149607.tif 000010
【００９５】
以上、本発明に係る原料配合計画作成方法、コークス製造方法、混合整数計画問題の求解方法および原料配合計画作成装置について、発明を実施するための形態および実施例により具体的に説明したが、本発明の趣旨はこれらの記載に限定されるものではなく、特許請求の範囲の記載に基づいて広く解釈されなければならない。また、これらの記載に基づいて種々変更、改変等したものも本発明の趣旨に含まれることはいうまでもない。
【００９６】
例えば、本発明では、非線形項として変数の二乗項を対象として線形化を行うように変数の置き換えを実施した例を示したが、これに限られない。非線形な項を別の変数に置き換えることにより、非線形制約を見かけ上線形にできればよい。
【００９７】
また、前記した原料配合計画作成装置は、一つのコンピュータによって構成してもよく、あるいは複数のコンピュータによって構成し、各コンピュータ間で情報の授受をさせるように構成してもよい。また、前記した原料配合計画作成方法は、コンピュータに実装したコンピュータプログラムにより実行することができる。このコンピュータプログラムは、ＣＤ、磁気テープ等の記録媒体に記録し、読み取り可能としてもよい。
【符号の説明】
【００９８】
１  原料配合計画作成装置
１０  入力部
２０  出力部
３０  演算部
３１  求解部
【図１】
2020149607.tif 000011
【図２】
2020149607.tif 000012
【図３】
2020149607.tif 000013
【図４】
2020149607.tif 000014
【図５】
2020149607.tif 000015
【図６】
2020149607.tif 000016
【図７】
2020149607.tif 000017
【図８】
2020149607.tif 000018
【図９】
2020149607.tif 000019