【手続補正書】
【提出日】平成22年2月17日(2010.2.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、
求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、
用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、
求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘi≦１を生成して、記憶装置に記憶させる制約条件生成手段と、
任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備えたことを特徴とする部材割付システム。
【請求項２】
請求項１に記載の部材割付システムにおいて、
探索制御手段は、２回目以降のシンプレックス演算処理の繰り返し回数に上限値を設けることを特徴とする部材割付システム。
【請求項３】
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する手段と、最適化された部材割り付けデータを受け入れて、前記ｍ本の製品を、順次供給される前記ｋ種類の原材料から切り出すプレカット装置とを備え、
求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、
用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、
求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘi≦１を生成して、記憶装置に記憶させる制約条件生成手段と、
任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備えたことを特徴とする部材加工装置。
【請求項４】
請求項２に記載の部材加工装置において、
探索制御手段は、２回目以降のシンプレックス演算処理の繰り返し回数に上限値を設けることを特徴とする部材加工装置。
【請求項５】
コンピュータを、請求項１に記載の各手段として機能させる部材割付プログラム。
【請求項６】
コンピュータを、請求項１に記載の各手段として機能させる部材割付プログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項７】
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する方法であって、
製品長設定手段が、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させるステップと、
原材料長設定手段が、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させるステップと、
割付パターンベクトル生成手段が、求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙するステップと、
割付パターン行列生成手段が、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させるステップと、
目的関数生成手段が、前記割付パターン行列に含まれたｎ個の割付パターンをから選択して該当する原材料を選択する要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させるステップと、
制約条件生成手段が、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘi≦１を生成して、記憶装置に記憶させるステップと、
初期設定手段が、任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させるステップと、
シンプレックス演算手段が、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するステップと、
探索制御手段が、前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択するステップと、
前記探索制御手段が、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼するステップと、
前記探索制御手段が、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼するステップと、
前記探索制御手段が、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御するステップを含むことを特徴とする部材割付方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
以下の構成はそれぞれ上記の課題を解決するための手段である。
〈構成１〉
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、
求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、
用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、
求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘi≦１を生成して、記憶装置に記憶させる制約条件生成手段と、
任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備えたことを特徴とする部材割付システム。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
予め任意の方法で求めた初期実行可能解を割付パターンベクトルに含めてシンプレックス演算処理をするので、多数の組合せのある演算処理の最適解探索範囲を当初から狭めることができる。また、始めに、緩和した第３制約条件式０≦ｘi≦１を使用して、シンプレックス演算処理をさせるので、目的関数値の最小値を容易に探索できる。即ち、初期実行可能解の目的関数の値を最大値とし、シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し第２制約条件式Ｃｘ＝ｄと緩和した第３制約条件式０≦ｘi≦１を生成して、改めてシンプレックス演算処理を実行できる。これにより、さらに短時間で、最適値を求める演算処理が実行できる。また、単に原材料長の合計値の減少だけでなく、原材料の種類に応じた加工費用等の成分を、原材料長に含める。これにより、計算は原材料長についてのみ行われても、原材料の価格を考慮した割付の最適化ができる。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
〈構成２〉
構成１に記載の部材割付システムにおいて、探索制御手段は、２回目以降のシンプレックス演算処理の繰り返し回数に上限値を設けることを特徴とする部材割付システム。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
組合せリストのリストアップ量が多量の場合の長時間の演算処理継続を防止する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
〈構成３〉
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する手段と、最適化された部材割り付けデータを受け入れて、前記ｍ本の製品を、順次供給される前記ｋ種類の原材料から切り出すプレカット装置とを備え、
求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、
用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、
求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘi≦１を生成して、記憶装置に記憶させる制約条件生成手段と、
任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備えたことを特徴とする部材加工装置。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
構成１の演算処理機能を組み込んだ部材加工装置は、該当する製品長や材料長を指定すると、自動的に、最適割り付けで製品の切り出しを行う。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
〈構成４〉
構成２に記載の部材加工装置において、探索制御手段は、２回目以降のシンプレックス演算処理の繰り返し回数に上限値を設けることを特徴とする部材加工装置。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
〈構成５〉
コンピュータを、構成１に記載の各手段として機能させる部材割付プログラム。
〈構成６〉
コンピュータを、構成１に記載の各手段として機能させる部材割付プログラムを記録したコンピュータで読み取り可能な記録媒体。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
〈構成７〉
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する方法であって、
製品長設定手段が、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させるステップと、
原材料長設定手段が、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させるステップと、
割付パターンベクトル生成手段が、求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙するステップと、
割付パターン行列生成手段が、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させるステップと、
目的関数生成手段が、前記割付パターン行列に含まれたｎ個の割付パターンをから選択して該当する原材料を選択する要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させるステップと、
制約条件生成手段が、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘi≦１を生成して、記憶装置に記憶させるステップと、
初期設定手段が、任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させるステップと、
シンプレックス演算手段が、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するステップと、
探索制御手段が、前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択するステップと、
前記探索制御手段が、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼するステップと、
前記探索制御手段が、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼するステップと、
前記探索制御手段が、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御するステップを含むことを特徴とする部材割付方法。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
図２は、部材割付システム１０を構成するコンピュータのハードウエアブロック図である。
部材割付システム１０の具体的な機能を説明する前に、部材割付システム１０のハードウエアを説明する。図のように、コンピュータ１２の本体ケース３中に収められた内部バス１１０には、ＣＰＵ（中央処理装置）１１１と、ＲＯＭ（リードオンリメモリ）１１２と、ＲＡＭ（ランダムアクセスメモリ）１１３と、ＨＤＤ（ハードディスク）１１４と、入出力インタフェース１１５と、ネットワークインタフェース１１６とが接続されている。入出力インタフェース１１５には、ディスプレイ３とキーボード４とマウス５とが接続されている。ネットワークインタフェース１１６には、ネットワーク１４を介して、端末装置１６が接続されている。以上のハードウェアは一般的によく知られたパーソナルコンピュータに備えられているものと変わらない。端末装置１６は、プレカット装置１７の部材選択供給装置１２０に、部材割付データを５３を供給する。これにより、指定された原材料が部材切断装置１２１に供給され、指定された割付パターンで切断される。切断された製品は製品搬送装置１２２により搬送され排出される。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
図３は、演算処理のパラメータを説明するための説明図である。
この図を参照しながら、演算処理に使用するパラメータの定義と、上記の各コンピュータプログラムの機能を説明する。
［製品長ベクトルLp］
生産されるべき製品の数量をｍとする。図の例では、ｍ＝７である。
製品長をLp1,Lp2,…,Lpmと表現する。単位は例えば、ｍ（メートル）である。
ｍ次の製品長ベクトルLpを下記のように定義する。
Lp＝（Lp1,Lp2,…,Lpm）
但し、（Lp1≧Lp2≧…≧Lpm）
図の例では、Lp＝（Lp1,Lp2,Lp3,Lp4,Lp5,Lp6,Lp7）である。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
［原材料データ］
原材料にはｋ種類の長さのものが含まれている。図の例では、ｋ＝３である。
原材料長をLm1,Lm2,…,Lmkと表現する。単位は例えば、ｍ（メートル）である。
ｋ次の原材料長ベクトルLmを下記のように定義する。
Lm＝（Lm1,Lm2,…,Lmk）
但し、（Lm1＞Lm2＞…＞Lmk）
図の例では、Lm＝（Lm1,Lm2,Lm3）である。
原材料長設定手段２２は、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLm４３を生成し、記憶装置４０に記憶させる。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００３２
【補正方法】変更
【補正の内容】
【００３２】
［第３制約条件］
上記の使用本数ベクトルｘの各要素ｘiは０または１である。列挙された多数の割付パターンベクトルの中のいずれを選択するかどうかを決める意味をもつからである。従って、下式のような制約条件式が成立する。
ｘi∈｛０，１｝
なお、この実施例では、この制約条件を緩和する。即ち、０≦ｘi≦１という制約条件式を設定する。
制約条件生成手段は、使用本数ベクトルｘの各要素ｘiが０≦ｘi≦１である旨を示す第３制約条件式を生成して、記憶装置に記憶させる。  
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００３４
【補正方法】変更
【補正の内容】
【００３４】
原材料の価格が長さに比例する場合は、歩留が最高になる場合と総費用が最小になる場合とは同意である。しかし、単位長さ当たりの価格が原材料長により異なる場合には、費用係数を調整する。
費用係数ベクトル生成手段２７は、原材料長ベクトルLmの各要素に価格成分を含めてｎ次の費用係数ベクトルｆを生成する。費用係数ベクトルｆの要素ｆiは、単位が円のデータである。費用計数係数ベクトル生成手段２７は原材料長ベクトルLmを費用係数ベクトルｆで置き換えるようにすれば、以下は、費用係数ベクトルｆを意識することなく演算処理ができる。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００３７
【補正方法】変更
【補正の内容】
【００３７】
初期設定手段２３は、任意の方法で取得した任意の初期実行可能解４４を受け付ける。そして、シンプレックス演算処理のためのパラメータを生成する。任意の方法とは、例えばFirst Fit法、特許文献１に記載された方法等である。初期実行可能解は、上記の割付パターン行列Ａ４６から選択される割付パターンベクトルを指定する原材料の使用本数ベクトルｘで表すことができる。これも、実施例３でより具体的に説明をする。最初のシンプレックス演算処理のために入力するパラメータは、目的関数Σｆi・ｘiと第１制約条件式Ａｘ≧ｂと第３制約条件式０≦ｘi≦１を構成するデータである。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】００４７
【補正方法】変更
【補正の内容】
【００４７】
また、ステップＳ３６では、目的関数生成手段２８に依頼をして、目的関数の設定をする。ステップＳ３７でシンプレックス演算を実行する。ステップＳ３８では、探索制御手段３０が、整数解が得られたかどうかという判断をする。この判断の結果がイエスのときはこの処理を終了して、図４のステップＳ２３に進む。一方、ノーのときはステップＳ３９の処理に移行する。ステップＳ３９では、予め設定されたＷ回だけ、ステップＳ３８のピボット演算処理を繰り返したかどうかを判断する。Ｗ回は上限値である。これにより、長時間探索をしても、解が得られない場合に、処理を中止する。即ち、ステップＳ４０で、初期実行可能解を演算処理結果として出力する。繰り返し回数がＷ回に満たないときは、ステップＳ３４に戻り、次に大きい目的関数値となる組合せリストを選択して、再度シンプレックス演算処理を実行する。以上の処理により、コンピュータプログラムは自動的に最適解を探索する。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】００４８
【補正方法】変更
【補正の内容】
【００４８】
図６から図１１までは、具体的な計算例の説明図である。
これらの図を用いて、実際の計算例により、上記の装置の動作をより具体的に説明する。
（原材料データ）
例えば、用意された原材料は５種類である。その長さは下記のとおりとする。長さの単位は０．１ｍｍ（ミリメートル）である。
Lm1＝６００００
Lm2＝４９０００
Lm3＝４５０００
Lm4＝４００００
Lm5＝３００００
（製品長データ）
求められている製品は７本で、その長さは下記のとおりとする。長さの単位は０．１ｍｍ（ミリメートル）である。
Lp1＝５３０５０
Lp2＝４４３５０
Lp3＝３０７００
Lp4＝２６２５０
Lp5＝２１０５０
Lp6＝１７８４０
Lp7＝１７１５０