(57)【要約】【課題】材料から様々な形状の製品を切り出す場合に、その割付を最適化するための演算処理を高速化する。【解決手段】シンプレックス法演算を使用して実行可能解を求めるとき、緩和解の整数要素に対応する割付パターンベクトルを取り出して整数解とし、緩和解の整数でない要素に対応する割付パターンベクトルに割り付けられた製品データを取り出して次数の低い部分問題を生成し、この部分問題にシンプレックス法演算を実行する。材料の種類数と製品の寸法の種類数が多くなるとき、原問題から次数低減した部分問題を繰り返し作り、次数を低減させながら解くことで演算時間を短縮する。【選択図】図１
2020149207.tif 000002
【特許請求の範囲】
【請求項１】
それぞれ所定の長方形のｍ個の製品を、それぞれ所定の長方形のｋ種類の材料から切り出すときに、種類ごとに必要な材料の個数と各材料への製品の割付方を求め、材料費用を最小化するものであって、
用意されたｋ種類の長方形の材料データの入力を受付けて、材料の横長を要素とするｋ次の材料横長ベクトルｗmと、材料の縦長を要素とするｋ次の材料縦長ベクトルｈmと、材料の費用を要素とするｋ次の材料費用ベクトルsmとを生成し、記憶装置に記憶させる材料設定手段と、
求められているｍ個の製品の形状データの入力を受け付けて、同一形状の製品をまとめて形状の種類数をｍ’とし、ｍ’次の製品横長ベクトルｗpとｍ’次の製品縦長ベクトルｈpを生成し、記憶装置に記憶させる原問題のための製品設定手段と、
予め定めた割付方法で種類ごとに必要な材料の個数と材料費用の合計と各材料への製品の割付方を求めて、暫定解として記憶装置に記憶させる暫定解記憶手段と、
求められているｍ’種類の製品の要求数量を要素とするｍ’次の製品要求数量ベクトルｂを生成して、記憶装置に記憶させる製品要求数量ベクトル生成手段と、
求められている上記ｍ’ 種類の製品を、予め定めた割付方法で、１個または複数個の製品を経済的に割り付け、材料と製品の関係を示す、ｍ’次の割付パターンベクトルａjをｎ個生成し、記憶装置に記憶させる割付パターンベクトル生成手段と、
上記割付パターンベクトルが示す材料への製品の割付方を記憶装置に記憶させる割付方データ生成手段と、
上記割付パターンベクトル生成手段の生成したｎ個の割付パターンベクトルを並べた、ｍ’×ｎ次の割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
ｍ個の製品を切り出す際、ｋ種類の材料のうちいずれの材料を何個使用したかを表すために、上記割付パターンベクトルａjの使用個数を表す要素がｘi（i＝１〜ｎ）のｎ次の使用個数ベクトルｘを定義し、上記割付パターンベクトルａjが示す材料のそれぞれに対応するｎ次の費用係数ベクトルｆと上記使用個数ベクトルｘの積で表される目的関数ｆｘと、
上記割付パターン行列Ａから選択された割付パターンベクトルで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと、第２制約条件式xi＝｛0,1,2,3,…｝とを生成し、記憶装置に記憶させる第一の整数計画定式化手段と、
シンプレックス法で、LP緩和解を求めるシンプレックス法演算処理手段と、
材料費用を最小化するための種類ごとに必要な材料個数と各材料への製品の割付方とを出力する演算結果出力手段と、
整数要素に対応する割付パターンベクトルを実行可能解の一部として記憶装置に記憶させ、整数でない要素に対応する割付パターンベクトルが示す製品データを取り出し、記憶装置に記憶させる部分問題のための製品設定手段と、
各手段を制御する演算制御手段とを備え、
この演算制御手段は、順に（１）材料設定手段を実行させ、（２）原問題のための製品設定手段を実行させ、（３）暫定解記憶手段を実行させ、（４）製品要求数量ベクトル生成手段を実行させ、（５）割付パターンベクトル生成手段を実行させ、（６）割付方データ生成手段を実行させ、（７）割付パターン行列生成手段を実行させ、（８）第一の整数計画定式化手段を実行させ、（９）シンプレックス法演算処理手段を実行させて、
この（９）の処理で得られたLP緩和解が第一の整数計画の実行可能解であるか否かを判定し、この判定が実行可能解であるときは、記憶されている実行可能解の一部と上記実行可能解を編集して演算結果出力手段を実行させて終了し、実行可能解でないときは、上記LP緩和解の整数要素の個数が１以上か１未満かを判定し、１未満のときは、記憶されている実行可能解の一部と上記暫定解を編集して演算結果出力手段を実行させて終了し、１以上のときは、部分問題のための製品設定手段を実行させ、続いて上記（３）から（９）の処理を順に実行させて、上記の判定処理に進むものであることを特徴とする部材割付システム。
【請求項２】
それぞれ所定の長方形のｍ個の製品を、それぞれ所定の長方形のｋ種類の材料から切り出すときに種類ごとに必要な材料の個数と各材料への製品の割付方を求め、材料費用を最小化するものであって、
上記材料設定手段と、上記原問題のための製品設定手段と、
上記暫定解記憶手段と、上記製品要求数量ベクトル生成手段と、
上記割付パターンベクトル生成手段と、  上記割付方データ生成手段と、上記割付パターン行列生成手段と、上記第一の整数計画定式化手段と、シンプレックス法演算処理手段と、上記演算結果出力手段、上記部分問題のための製品設定手段と、
上記暫定解の目的関数値（上界）未満かつ上記第一の整数計画のLP緩和問題の目的関数値（下界）以上の範囲の値をとる種類ごとの材料の使用個数の組合せを列挙し、材料使用予定数量ベクトルｄを生成し、材料費用ベクトルとの内積（ｓm・ｄ）の値の昇順に並べ、記憶装置に記憶させる材料使用予定数量ベクトル生成手段と、
使用個数ベクトルｘの要素が、ｋ種類の材料のどの種類に対応するかを表す材料使用行列Ｃと使用個数ベクトルｘの積が材料使用予定数量ベクトルｄと等しいとする第３制約条件式Ｃｘ＝ｄの生成し、記憶装置に記憶させ、上記目的関数と上記第１制約条件式と上記第２制約条件式と上記第３制約条件式からなる第二の整数計画定式化手段と、 
各手段を制御する演算制御手段とを備え、
この演算制御手段は、順に（１）材料設定手段を実行させ、（２）原問題のための製品設定手段を実行させ、（３）暫定解記憶手段を実行させ、（４）製品要求数量ベクトル生成手段を実行させ、（５）割付パターンベクトル生成手段を実行させ、（６）割付方データ生成手段を実行させ、（７）割付パターン行列生成手段を実行させ、（８）第一の整数計画定式化手段を実行させ、（９）シンプレックス法演算処理手段を実行させて（AA）に処理を進め、
（AA）上記の（９）の処理で得られたLP緩和解が第一の整数計画の実行可能解であるか否かを判定し、この判定が実行可能解であるときは、記憶されている実行可能解の一部と上記実行可能解を編集して演算結果出力手段を実行させて終了し、実行可能解でないときは、（１０）材料使用予定数量ベクトル生成手段を実行させて（BB）に処理を進め、
（BB）この（１０）の処理で得られた材料使用予定数量ベクトルｄを選択し尽くしたか否かを判定し、選択し尽くしたときは、記憶されている実行可能解の一部と上記暫定解を編集して演算結果出力手段を実行させて終了し、選択し尽くしていないときは、材料使用予定数量ベクトルｄを選択し、（１１）第二の整数計画定式化手段を実行させて（CC）に処理を進め、
（CC）この（１１）の処理で得られた第二の整数計画がLP緩和して実行可能であるか否かを、上記（９）のシンプレックス法演算処理手段を実行させて判定し、実行可能でないときは上記の（BB）に処理を進め、
実行可能であるときは、上記（９）のシンプレックス法演算処理手段を実行させてLP緩和解を求め、上記LP緩和解が第二の整数計画の実行可能解であるか否かを判定し、実行可能解であるときは、記憶されている実行可能解の一部と上記実行可能解を編集して演算結果出力手段を実行させて終了し、
実行可能解でないときは、上記LP緩和解の整数要素の個数が１以上か１未満かを判定し、１未満のときは上記の（BB）に処理を進め、１以上のときは、部分問題のための製品設定手段を実行させ、続いて上記（３）から（９）の処理を順に実行させて、上記の（AA）に処理を進めるものであることを特徴とする部材割付システム。
【請求項３】
それぞれ所定の長方形のｍ個の製品を、それぞれ所定の長方形のｋ種類の材料から切り出すときに種類ごとに必要な材料の個数と各材料への製品の割付方を求め、材料費用を最小化するものであって、
上記材料設定手段と、上記原問題のための製品設定手段と、
上記暫定解記憶手段と、上記製品要求数量ベクトル生成手段と、
上記割付パターンベクトル生成手段と、 上記割付方データ生成手段と、上記割付パターン行列生成手段と、上記第一の整数計画定式化手段と、上記シンプレックス法演算処理手段と、上記演算結果出力手段と、上記部分問題のための製品設定手段と、上記材料使用予定数量ベクトル生成手段と、上記第二の整数計画定式化手段と、
部分問題のLP緩和解が劣化しているか否かを判定する劣化判定手段と、
各手段を制御する演算制御手段とを備え、
この演算制御手段は、順に（１）材料設定手段を実行させ、（２）原問題のための製品設定手段を実行させ、（３）暫定解記憶手段を実行させ、（４）製品要求数量ベクトル生成手段を実行させ、（５）割付パターンベクトル生成手段を実行させ、（６）割付方データ生成手段を実行させ、（７）割付パターン行列生成手段を実行させ、（８）第一の整数計画定式化手段を実行させ、（９）シンプレックス法演算処理手段を実行させて、
この（９）の処理で得られたLP緩和解が第一の整数計画の実行可能解であるか否かを判定し、この判定が実行可能解であるときは、記憶されている実行可能解の一部と上記実行可能解を編集して演算結果出力手段を実行させて終了し、
実行可能解でないときは、（１０）材料使用予定数量ベクトル生成手段を実行させて
（AA）に処理を進め、以下の（AA）、（BB）、（CC）、（DD）、（EE）、（FF）にしたがい処理を進めるものであることを特徴とする部材割付システム。
（AA）材料使用予定数量ベクトルｄを選択し尽くしたか否かを判定し、選択し尽くしたときは、記憶されている実行可能解の一部と上記暫定解を編集して演算結果出力手段を実行させて終了し、選択し尽くしていないときは、材料使用予定数量ベクトルｄを選択して（BB）に処理を進める。
（BB）（１１）第二の整数計画定式化手段を実行させ、得られた第二の整数計画のLP緩和問題が実行可能であるか否かを判定し、実行可能でないときは、（AA）に進め、
実行可能であるときは、LP緩和解を求めて（CC）に処理を進める。
（CC）（BB）で求めたLP緩和解がこの（１１）の処理で得られた第二の整数計画の実行可能解であるか否かを判定し、実行可能解であるときは、記憶されている実行可能解の一部と上記実行可能解を編集して演算結果出力手段を実行させて終了し、
実行可能解でないときは、（DD）に処理を進める。
（DD）LP緩和解の整数要素の個数が１以上か１未満かを判定し、１未満のときは、（EE）に処理を進め、
１以上のときは、部分問題のための製品設定手段を実行させ、上記（３）から（９）の処理を順に実行させ、
この（９）の処理で得られたLP緩和解が第一の整数計画の実行可能解であるか否かを判定し、この判定が実行可能解であるときは、上記実行可能解を編集して演算結果出力手段を実行させて終了し、
実行可能解でないときは、（１０）材料使用予定数量ベクトル生成手段を実行させて
（FF）に処理を進める。
（EE）この（１１）の処理で得られた第二の整数計画が上記LP緩和問題と異なるLP緩和解を持つか否かを判定し、持つときは、異なるLP緩和解を求め、（DD）に進める、持たないときは、（AA）に処理を進める。
（FF）劣化判定手段を実行させ、劣化していると判定したときは、実行可能解の一部を記憶を消し、（AA）に進め、劣化していないと判定したときは、上記LP緩和解が実行可能解か否かを判定し、実行可能解のときは、記憶した実行可能解の一部と上記実行可能解を編集して、終了させる。実行可能解でないときは、材料使用予定数量ベクトルｄを更新して（AA）に処理を進める。
【請求項４】
上記の予め定めた割付方法は、ボトムレフト法であるか、またはギロチンカット対応であることを特徴とする請求項１乃至請求項３のいずれかに記載の部材割付システム。
【請求項５】
上記の所定の製品には多角形を含むことを特徴とする請求項１乃至請求項３のいずれかに記載の部材割付システム。
【請求項６】
コンピュータを請求項１乃至請求項５のいずれかに記載の部材割付システムとして機能させるコンピュータプログラム。
【請求項７】
請求項６に記載のコンピュータプログラムを記録したコンピュータ読取可能な記録媒体。
【請求項８】
請求項１乃至請求項５のいずれかに記載の部材割付システムが出力する演算結果を入力として動作する材料切断装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、材料から様々な形状の製品を切り出す場合に、その割付を最適化するための演算処理を高速化する、部材割付システムと部材割付プログラムと記録媒体と材料切断装置に関する。
【背景技術】
【０００２】
住宅用建材のプレカット加工においては、構造材のように棒状の材料から製品を切り出す際や、断熱材のように板状の材料から製品を切り出す際に、製品の割付を材料費用を削減するようにすることが重要である。また歩留を向上し、廃材を削減することは環境にとっても重要である。
【０００３】
構造材には、断面形状や樹種，等級、レイヤといった仕様ごとに何種類かの材料がある。そこから求められる寸法の製品を切り出す。製品の仕様と、製品の寸法と、切り出される製品の割付により、材料から切り落とされて無駄になる部分の量が異なる。構造材や一定の幅の板といった棒状材料については、シンプレックス演算処理を利用し、山登り法、ランダムリスタート法、焼き鈍し法等により、費用を最小にするための最適値を探索する技術が開発された（特許文献１、特許文献２参照）。続いて、断熱材のような板状材料を縦横に切断するための、製品と材料との最適な割付を特許文献１、２よりも高速に求める技術が開発された（特許文献３参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第４９０９８６９号公報
【特許文献２】特許第５０００７３５号公報
【特許文献３】特許第５９８３９７６号公報
【非特許文献１】「最適化手法第５回  整数計画法（４）：分枝限定法  電通大  岡本吉央http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/opt/handout05.pdf#search=%27%E5%88%86%E6%9E%9D%E9%99%90%E5%AE%9A%E6%B3%95+%E9%9B%BB%E9%80%9A%E5%A4%A7%27
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来の技術では、材料の種類数と製品の寸法の種類数が、増加すると、割付パターンは指数関数的に増加する。そのため、材料の種類数と製品の寸法の種類数が多くなる場合、演算時間が長くなるのは不可避であるが、演算時間をできる限り短縮しなければならないという課題があった。本発明は、以上の課題を解決するためになされたもので、材料から様々な形状の製品を切り出すための割付計算のための、演算処理時間をさらに短縮する、部材割付システムと部材割付プログラムと記録媒体と材料切断装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
以下の構成はそれぞれ上記の課題を解決するための手段である。
【０００７】
＜構成１＞
それぞれ所定の長方形のｍ個の製品を、それぞれ所定の長方形のｋ種類の材料から切り出すときに、種類ごとに必要な材料の個数と各材料への製品の割付方を求め、材料費用を最小化するものであって、
用意されたｋ種類の長方形の材料データの入力を受付けて、材料の横長を要素とするｋ次の材料横長ベクトルｗmと、材料の縦長を要素とするｋ次の材料縦長ベクトルｈmと、材料の費用を要素とするｋ次の材料費用ベクトルsmとを生成し、記憶装置に記憶させる材料設定手段と、
求められているｍ個の製品の形状データの入力を受け付けて、同一形状の製品をまとめて形状の種類数をｍ’とし、ｍ’次の製品横長ベクトルｗpとｍ’次の製品縦長ベクトルｈpを生成し、記憶装置に記憶させる原問題のための製品設定手段と、
予め定めた割付方法で種類ごとに必要な材料の個数と材料費用の合計と各材料への製品の割付方を求めて、暫定解として記憶装置に記憶させる暫定解記憶手段と、
求められているｍ’種類の製品の要求数量を要素とするｍ’次の製品要求数量ベクトルｂを生成して、記憶装置に記憶させる製品要求数量ベクトル生成手段と、
求められている上記ｍ’ 種類の製品を、予め定めた割付方法で、１個または複数個の製品を経済的に割り付け、材料と製品の関係を示す、ｍ’次の割付パターンベクトルａjをｎ個生成し、記憶装置に記憶させる割付パターンベクトル生成手段と、
上記割付パターンベクトルが示す材料への製品の割付方を記憶装置に記憶させる割付方データ生成手段と、
上記割付パターンベクトル生成手段の生成したｎ個の割付パターンベクトルを並べた、ｍ’×ｎ次の割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
ｍ個の製品を切り出す際、ｋ種類の材料のうちいずれの材料を何個使用したかを表すために、上記割付パターンベクトルａjの使用個数を表す要素がｘi（i＝１〜ｎ）のｎ次の使用個数ベクトルｘを定義し、上記割付パターンベクトルａjが示す材料のそれぞれに対応するｎ次の費用係数ベクトルｆと上記使用個数ベクトルｘの積で表される目的関数ｆｘと、
上記割付パターン行列Ａから選択された割付パターンベクトルで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと、第２制約条件式xi＝｛0,1,2,3,…｝とを生成し、記憶装置に記憶させる第一の整数計画定式化手段と、
シンプレックス法で、LP緩和解を求めるシンプレックス法演算処理手段と、
材料費用を最小化するための種類ごとに必要な材料個数と各材料への製品の割付方とを出力する演算結果出力手段と、
整数要素に対応する割付パターンベクトルを実行可能解の一部として記憶装置に記憶させ、整数でない要素に対応する割付パターンベクトルが示す製品データを取り出し、記憶装置に記憶させる部分問題のための製品設定手段と、
各手段を制御する演算制御手段とを備え、
この演算制御手段は、順に（１）材料設定手段を実行させ、（２）原問題のための製品設定手段を実行させ、（３）暫定解記憶手段を実行させ、（４）製品要求数量ベクトル生成手段を実行させ、（５）割付パターンベクトル生成手段を実行させ、（６）割付方データ生成手段を実行させ、（７）割付パターン行列生成手段を実行させ、（８）第一の整数計画定式化手段を実行させ、（９）シンプレックス法演算処理手段を実行させて、
この（９）の処理で得られたLP緩和解が第一の整数計画の実行可能解であるか否かを判定し、この判定が実行可能解であるときは、記憶されている実行可能解の一部と上記実行可能解を編集して演算結果出力手段を実行させて終了し、実行可能解でないときは、上記LP緩和解の整数要素の個数が１以上か１未満かを判定し、１未満のときは、記憶されている実行可能解の一部と上記暫定解を編集して演算結果出力手段を実行させて終了し、１以上のときは、部分問題のための製品設定手段を実行させ、続いて上記（３）から（９）の処理を順に実行させて、上記の判定処理に進むものであることを特徴とする部材割付システム。
【０００８】
＜構成２＞
それぞれ所定の長方形のｍ個の製品を、それぞれ所定の長方形のｋ種類の材料から切り出すときに種類ごとに必要な材料の個数と各材料への製品の割付方を求め、材料費用を最小化するものであって、
上記材料設定手段と、上記原問題のための製品設定手段と、
上記暫定解記憶手段と、上記製品要求数量ベクトル生成手段と、
上記割付パターンベクトル生成手段と、  上記割付方データ生成手段と、上記割付パターン行列生成手段と、上記第一の整数計画定式化手段と、シンプレックス法演算処理手段と、上記演算結果出力手段、上記部分問題のための製品設定手段と、
上記暫定解の目的関数値（上界）未満かつ上記第一の整数計画のLP緩和問題の目的関数値（下界）以上の範囲の値をとる種類ごとの材料の使用個数の組合せを列挙し、材料使用予定数量ベクトルｄを生成し、材料費用ベクトルとの内積（ｓm・ｄ）の値の昇順に並べ、記憶装置に記憶させる材料使用予定数量ベクトル生成手段と、
使用個数ベクトルｘの要素が、ｋ種類の材料のどの種類に対応するかを表す材料使用行列Ｃと使用個数ベクトルｘの積が材料使用予定数量ベクトルｄと等しいとする第３制約条件式Ｃｘ＝ｄの生成し、記憶装置に記憶させ、上記目的関数と上記第１制約条件式と上記第２制約条件式と上記第３制約条件式からなる第二の整数計画定式化手段と、 
各手段を制御する演算制御手段とを備え、
この演算制御手段は、順に（１）材料設定手段を実行させ、（２）原問題のための製品設定手段を実行させ、（３）暫定解記憶手段を実行させ、（４）製品要求数量ベクトル生成手段を実行させ、（５）割付パターンベクトル生成手段を実行させ、（６）割付方データ生成手段を実行させ、（７）割付パターン行列生成手段を実行させ、（８）第一の整数計画定式化手段を実行させ、（９）シンプレックス法演算処理手段を実行させて（AA）に処理を進め、
（AA）上記の（９）の処理で得られたLP緩和解が第一の整数計画の実行可能解であるか否かを判定し、この判定が実行可能解であるときは、記憶されている実行可能解の一部と上記実行可能解を編集して演算結果出力手段を実行させて終了し、実行可能解でないときは、（１０）材料使用予定数量ベクトル生成手段を実行させて（BB）に処理を進め、
（BB）この（１０）の処理で得られた材料使用予定数量ベクトルｄを選択し尽くしたか否かを判定し、選択し尽くしたときは、記憶されている実行可能解の一部と上記暫定解を編集して演算結果出力手段を実行させて終了し、選択し尽くしていないときは、材料使用予定数量ベクトルｄを選択し、（１１）第二の整数計画定式化手段を実行させて（CC）に処理を進め、
（CC）この（１１）の処理で得られた第二の整数計画がLP緩和して実行可能であるか否かを、上記（９）のシンプレックス法演算処理手段を実行させて判定し、実行可能でないときは上記の（BB）に処理を進め、
実行可能であるときは、上記（９）のシンプレックス法演算処理手段を実行させてLP緩和解を求め、上記LP緩和解が第二の整数計画の実行可能解であるか否かを判定し、実行可能解であるときは、記憶されている実行可能解の一部と上記実行可能解を編集して演算結果出力手段を実行させて終了し、
実行可能解でないときは、上記LP緩和解の整数要素の個数が１以上か１未満かを判定し、１未満のときは上記の（BB）に処理を進め、１以上のときは、部分問題のための製品設定手段を実行させ、続いて上記（３）から（９）の処理を順に実行させて、上記の（AA）に処理を進めるものであることを特徴とする部材割付システム。
【０００９】
＜構成３＞
それぞれ所定の長方形のｍ個の製品を、それぞれ所定の長方形のｋ種類の材料から切り出すときに種類ごとに必要な材料の個数と各材料への製品の割付方を求め、材料費用を最小化するものであって、
上記材料設定手段と、上記原問題のための製品設定手段と、
上記暫定解記憶手段と、上記製品要求数量ベクトル生成手段と、
上記割付パターンベクトル生成手段と、 上記割付方データ生成手段と、上記割付パターン行列生成手段と、上記第一の整数計画定式化手段と、上記シンプレックス法演算処理手段と、上記演算結果出力手段と、上記部分問題のための製品設定手段と、上記材料使用予定数量ベクトル生成手段と、上記第二の整数計画定式化手段と、
部分問題のLP緩和解が劣化しているか否かを判定する劣化判定手段と、
各手段を制御する演算制御手段とを備え、
この演算制御手段は、順に（１）材料設定手段を実行させ、（２）原問題のための製品設定手段を実行させ、（３）暫定解記憶手段を実行させ、（４）製品要求数量ベクトル生成手段を実行させ、（５）割付パターンベクトル生成手段を実行させ、（６）割付方データ生成手段を実行させ、（７）割付パターン行列生成手段を実行させ、（８）第一の整数計画定式化手段を実行させ、（９）シンプレックス法演算処理手段を実行させて、
この（９）の処理で得られたLP緩和解が第一の整数計画の実行可能解であるか否かを判定し、この判定が実行可能解であるときは、記憶されている実行可能解の一部と上記実行可能解を編集して演算結果出力手段を実行させて終了し、
実行可能解でないときは、（１０）材料使用予定数量ベクトル生成手段を実行させて
（AA）に処理を進め、以下の（AA）、（BB）、（CC）、（DD）、（EE）、（FF）にしたがい処理を進めるものであることを特徴とする部材割付システム。
（AA）材料使用予定数量ベクトルｄを選択し尽くしたか否かを判定し、選択し尽くしたときは、記憶されている実行可能解の一部と上記暫定解を編集して演算結果出力手段を実行させて終了し、選択し尽くしていないときは、材料使用予定数量ベクトルｄを選択して（BB）に処理を進める。
（BB）（１１）第二の整数計画定式化手段を実行させ、得られた第二の整数計画のLP緩和問題が実行可能であるか否かを判定し、実行可能でないときは、（AA）に進め、
実行可能であるときは、LP緩和解を求めて（CC）に処理を進める。
（CC）（BB）で求めたLP緩和解がこの（１１）の処理で得られた第二の整数計画の実行可能解であるか否かを判定し、実行可能解であるときは、記憶されている実行可能解の一部と上記実行可能解を編集して演算結果出力手段を実行させて終了し、
実行可能解でないときは、（DD）に処理を進める。
（DD）LP緩和解の整数要素の個数が１以上か１未満かを判定し、１未満のときは、（EE）に処理を進め、
１以上のときは、部分問題のための製品設定手段を実行させ、上記（３）から（９）の処理を順に実行させ、
この（９）の処理で得られたLP緩和解が第一の整数計画の実行可能解であるか否かを判定し、この判定が実行可能解であるときは、上記実行可能解を編集して演算結果出力手段を実行させて終了し、
実行可能解でないときは、（１０）材料使用予定数量ベクトル生成手段を実行させて
（FF）に処理を進める。
（EE）この（１１）の処理で得られた第二の整数計画が上記LP緩和問題と異なるLP緩和解を持つか否かを判定し、持つときは、異なるLP緩和解を求め、（DD）に進める、持たないときは、（AA）に処理を進める。
（FF）劣化判定手段を実行させ、劣化していると判定したときは、実行可能解の一部を記憶を消し、（AA）に進め、劣化していないと判定したときは、上記LP緩和解が実行可能解か否かを判定し、実行可能解のときは、記憶した実行可能解の一部と上記実行可能解を編集して、終了させる。実行可能解でないときは、材料使用予定数量ベクトルｄを更新して（AA）に処理を進める。
【００１０】
＜構成４＞
上記の予め定めた割付方法は、ボトムレフト法であるか、またはギロチンカット対応であることを特徴とする構成１乃至構成３のいずれかに記載の部材割付システム。
【００１１】
＜構成５＞
上記の所定の製品には多角形を含むことを特徴とする構成１乃至構成３のいずれかに記載の部材割付システム。
【００１２】
＜構成６＞
コンピュータを構成１乃至構成５のいずれかに記載の部材割付システムとして機能させるコンピュータプログラム。
【００１３】
＜構成７＞
構成６に記載のコンピュータプログラムを記録したコンピュータ読取可能な記録媒体。
【００１４】
＜構成８＞
構成１乃至構成５のいずれかに記載の部材割付システムが出力する演算結果を入力として動作する材料切断装置。
【発明の効果】
【００１５】
材料の種類数と製品の寸法の種類数が多くなる場合、演算時間が長くなるのは不可避であるが、演算時間をできる限り短縮できる。即ち、原問題から次数低減した部分問題を繰り返し作り、次数を低減させながら解くことで大幅に演算時間を短縮することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明のシステムの機能を示す説明図である。
【図２】実施例１で使用するフローチャート(構成１用)である。
【図３】実施例１で使用する材料データである。
【図４】実施例１で使用する製品データである。
【図５】実施例１の材料横長ベクトルｗmである。
【図６】実施例１の材料縦長ベクトルｈmである。
【図７】実施例１の材料費用縦長ベクトルｓmである。
【図８】実施例１の８５次製品横長ベクトルｗpである。
【図９】実施例１の８５次製品縦長ベクトルｈpである。
【図１０】実施例１の原問題の８５次の割付パターンベクトルａj（各列ベクトル）、８５×６８４９８次の割付パターン行列Ａ（割付パターンベクトルを並べたもの）である。
【図１１】実施例１の原問題の８５次の製品要求数量ベクトルｂである。
【図１２】実施例１の原問題の６８４９８次費用係数ベクトルfである。
【図１３】実施例１の１つ目の部分問題の４６次の割付パターンベクトルａj（各列ベクトル）、１つ目の４６×２５７６８次の割付パターン行列Ａ（割付パターンベクトルを並べたもの）である。
【図１４】実施例１の１つ目の部分問題の４６次の製品要求数量ベクトルｂである。
【図１５】実施例１の１つ目の部分問題の２５７６８次費用係数ベクトルｆである。
【図１６】実施例１の原問題の整数要素の割付結果（実施例１の解の１）である。
【図１７】実施例１の原問題の整数要素の割付結果（実施例１の解の２）である。
【図１８】実施例１の原問題の整数要素の割付結果（実施例１の解の３）である。
【図１９】実施例１の原問題の整数要素の割付結果（実施例１の解の４）である。
【図２０】特許文献３の部材割付システムの割付結果（その１）である。
【図２１】特許文献３の部材割付システムの割付結果（その２）である。
【図２２】特許文献３の部材割付システムの割付結果（その３）である。
【図２３】本発明と特許文献３との比較である。
【図２４】実施例２で使用するフローチャートである（構成２用）
【図２５】実施例２で使用する材料データである。
【図２６】実施例２で使用する製品データである。
【図２７】実施例２の暫定解の材料使用数と目的関数値（上界）
【図２８】実施例２の材料使用予定数量と内積（ｓｍ・ｄ）の昇順並替結果
【図２９】実施例２のＣｘ＝ｄの説明図である。
【図３０】実施例２の整数要素の割付結果（その１）である。
【図３１】実施例２の整数要素の割付結果（その２）である。
【図３２】実施例２のフローチャート（構成３用の１）である。
【図３３】実施例２のフローチャート（構成３用の２）である。
【図３４】実施例２の原問題から始めて１つ目の部分問題で求解完了することの説明図である。
【図３５】解が劣化する場合の割付パターンの例である。
【図３６】実施例１の割付図中の材料番号が１番の割付け例平面図である。
【図３７】実施例１の割付図中の材料番号が３６番の割付け例平面図である。
【図３８】実施例１の割付図中の材料番号が４８番の割付け例平面図である。
【図３９】実施例１の割付図中の材料番号が４９番の割付け例平面図である。
【図４０】実施例１の割付図中の材料番号が５４番の割付け例平面図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施の形態を実施例毎に詳細に説明する。
【実施例１】
【００１８】
図１に示した本発明のシステムの機能を説明する。コンピュータ２は、材料切断装置４を制御するための割付演算処理を実行する。コンピュータ２の記憶装置６には図のようなデータが記憶され、演算処理装置８にはそれぞれ次のような機能が付与される。
【００１９】
このコンピュータの記憶装置６には、材料の寸法等の情報を示す材料データ１２と製品の寸法等の情報を示す製品データ１４と演算処理の結果得られる種類ごとに必要な材料個数１６、材料費用の合計１８、各材料への製品の割付方２０、および演算途中に生成するベクトル、行列等のデータが記憶される。演算制御手段４４が図２のフローチャートのように動作するように各手段を制御する。
【００２０】
図２に基づいて実施例１の部材割付の動作について説明する。
図２のステップS-1で、材料設定手段２２が、図３に示す２種類の材料データ１２を受付けて、図５に示す２次の材料横長ベクトルｗmと、図６に示す２次の材料縦長ベクトルｈmと、図７に示す２次の材料費用ベクトルｓmとを生成し、記憶装置６に記憶させ、原問題のための製品設定手段２４が、図４に示す２４２個の製品データ１４を受付けて、図８に示す８５次の製品横長ベクトルｗpと図９に示す８５次の製品縦長ベクトルｈpとを生成し、記憶装置６に記憶させた。
【００２１】
次にステップS-2で、暫定解記憶手段２６がファーストフィット法を用いて暫定解を求め、記憶装置６に記憶させた。ステップS-3で、製品要求数量ベクトル生成手段２８が、図１１に示す８５次の製品要求数量ベクトルｂを生成し、記憶装置６に記憶させ、割付パターンベクトル生成手段３０が、実施例１ではギロチンカット対応、ファーストフィット法を用いて、図１０に示す８５次の割付パターンベクトルａjを68498個生成し（j＝1〜68498）、記憶装置６に記憶させた。
【００２２】
割付方データ生成手段３２が、割付パターンベクトルａjが示す材料への製品の割付方を記憶装置６に記憶させ、割付パターン行列生成手段３４が、図１０に示す８５×68498次の割付パターン行列Ａを生成し、記憶装置６に記憶させ、第一の整数計画定式化手段３６が、68498次の使用個数ベクトルｘを定義し、図１２に示す68498次の費用係数ベクトルｆと上記使用個数ベクトルｘの積で表される目的関数ｆｘと、第１制約条件式Ａｘ≧ｂと第２制約条件式ｘi＝｛0,1,2,3,…｝とを生成し、記憶装置６に記憶させた。
【００２３】
ステップS-4で、シンプレックス法演算手段３８が、第一の整数計画をLP緩和して、すなわち第２制約条件式を除いて、LP緩和解を求めた。ステップS-5で、演算制御手段４４が、ステップS-4で求めたLP緩和解が実行可能解でない、すなわち、除いた第２制約条件式を満足しないと判定し、ステップS-6に進めた。ステップS-6で、演算制御手段４４が、ステップS-4で求めたLP緩和解の整数要素数≧１であると判定した。
【００２４】
この判定は、次のように行われる。図１６は、LP緩和解の整数要素に対応する割付パターンベクトルを取り出した結果である。LP緩和解の値が１である要素が２０個、値が２である要素が６個、値が３である要素が１個あったことを示している。したがって、整数要素の数は２０個＋６個＋１個＝２７個であるから、LP緩和解の整数要素数≧１である。また、材料の個数は１×２０個＋２×６個＋３×１個＝３５個である。ステップS-7に進んだ。
【００２５】
ステップS-7で、部分問題のための製品設定手段４２が、LP緩和解の整数でない要素に対応する割付パターンベクトルに割り付けられた製品データ１４を取り出し、４６次の製品横長ベクトルｗpと４６次の製品縦長ベクトルｈpとを生成し、記憶装置６に記憶させた。ステップS-2に戻り、１つ目の部分問題のための処理を続けた。暫定解記憶手段２６がファーストフィット法を用いて暫定解を求め、記憶装置６に記憶させた。ステップS-3で、製品要求数量ベクトル生成手段２８が、図１４に示す４６次の製品要求数量ベクトルｂを生成し、記憶装置６に記憶させた。
【００２６】
割付パターン生成手段が図１３に示す４６次の割付パターンベクトルａjを25768個生成し（j＝1〜25768）、記憶装置に記憶させた。割付方データ生成手段３２が、割付パターンベクトルａjが示す材料への製品の割付方を記憶装置６に記憶させ、割付パターン行列生成手段３４が、図１３に示す４６×25768次の割付パターン行列Ａを生成し、記憶装置６に記憶させ、第一の整数計画定式化手段３６が、25768次の使用個数ベクトルｘを定義し、図１５に示す25768次の費用係数ベクトルｆと上記使用個数ベクトルｘの積で表される目的関数ｆｘと、第１制約条件式Ａｘ≧ｂと第２制約条件式ｘi＝｛0,1,2,3,…｝とを生成し、記憶装置６に記憶させた。
【００２７】
原問題の割付パターン行列Aは８５×68498次であり、１つ目の部分問題の割付パターン行列では、４６×25768次である。製品要求数量ベクトルｂでは、原問題（８５次）、１つ目の部分問題（４６次）、使用個数ベクトルｘでは、原問題（68498次）、１つ目の部分問題（４６次）、費用係数ベクトルｆでは、原問題（68498次）、１つ目の部分問題（25768次）である。このように大幅に問題の次数が低減されることから、部分問題では演算時間が大幅に短縮される。
【００２８】
その後、ステップS-4以下、図２のフローチャートに基づいて、図１７、図１８、図１９に示すように進み実行可能解を求めた。すなわち、２つ目の部分問題、３つ目の部分問題を生成した。図１７は、１つ目の部分問題のLP緩和解の整数要素から得られた１３個の材料と製品の関係であり、図１８は、２つ目の部分問題のLP緩和解の整数要素から得られた３個の材料と製品の関係である。
【００２９】
図１９は、ステップS-5で、LP緩和解が実行可能解となり得られた３個の材料と製品の関係である。そして、ステップS-9に進み、演算結果出力手段４０が、材料費用を最小化するための種類毎に必要な材料個数と各材料への製品の割付方２０を出力して、終了した。ここで、特許第5983976号公報（特許文献３）に記載の方法と比較するために、実施例１の材料データ１２、製品データ１４を用いて割付を実施した結果を図２０から図２２に示す。比較結果を図２３に示す。図２３（ａ）から、実施例１では、特許文献３と比べて費用は同じであるが、計算時間が４分の１程度に短縮している。なお、刃物厚＝0ミリとした。
【実施例２】
【００３０】
実施例１は、２次元製品（板状製品）の割付例を示したが、実施例２では１次元製品（棒状製品）割付例を示す。本発明の部材割付システムは、長方形の製品の縦長要素を削除して、横長要素のみで適用すれば棒状製品にも使用可能である。
【００３１】
実施例２では図２４に示すフローチャートを用いる。すなわち、図１に示した演算制御手段４４が図２４のフローチャートのように動作するように各手段を制御する。図２４に基づいて実施例２の部材割付の動作について説明する。
【００３２】
図２４のステップS-101で、材料設定手段２２が、図２５に示す３種類の材料データ１２を受付けて、３次の材料横長ベクトルｗmと、３次の材料費用ベクトルｓmとを生成し、記憶装置６に記憶させ（材料縦長ベクトルｈmは１次元製品割付なので不要である）、原問題のための製品設定手段２４が、図２６に示す３６１個の製品データ１４を受付けて、９８次の製品横長ベクトルｗp（製品縦長ベクトルｈpは１次元製品割付なので不要）を生成し、記憶装置６に記憶させた。
【００３３】
次にステップS-102で、暫定解記憶手段２６がファーストフィット法を用いて暫定解を求め、記憶装置６に記憶させた。ステップS-103で、製品要求数量ベクトル生成手段２８が、９８次の製品要求数量ベクトルｂを生成し、記憶装置６に記憶させ、割付パターンベクトル生成手段３０が、ファーストフィット法を用いて、９８次の割付パターンベクトルａjを149000個生成し（j＝1〜149000）、記憶装置６に記憶させる。
【００３４】
割付方データ生成手段３２が、割付パターンベクトルａjが示す材料への製品の割付方を記憶装置６に記憶させ、割付パターン行列生成手段３４が、９８×149000次の割付パターン行列Ａを生成し、記憶装置６に記憶させ、第一の整数計画定式化手段３６が、149000次の使用個数ベクトルｘを定義し、149000次の費用係数ベクトルｆと上記使用個数ベクトルｘの積で表される目的関数ｆｘと、第１制約条件式Ａｘ≧ｂと第２制約条件式ｘi＝｛0,1,2,3,…｝とを生成し、記憶装置６に記憶させた。
【００３５】
ステップS-104で、シンプレックス法演算手段３８が、第一の整数計画をLP緩和して、すなわち第２制約条件式を除いて、LP緩和解を求めた。ステップS-105で、演算制御手段４４が、ステップS-104で求めたLP緩和解が実行可能解でない、すなわち、除いた第２制約条件式を満足しないと判定し、ステップS-106に進めた。
【００３６】
ステップS-106で、材料使用予定数量ベクトル生成手段４６が、ステップS-102で求めた図２７に示す上記暫定解の目的関数値（上界）＝３４５，０４０未満かつ、上記第一の整数計画のLP緩和して得られる目的関数値（下界）＝３４２，４８５．７…以上の範囲の値をとる種類ごとの材料の使用個数の組合せを列挙し、内積（ｓm・ｄ）の値の昇順に並べ、記憶装置６に記憶した。図２８にその結果を示す。図２７、図２８の費用計は目的関数値と同意である。
【００３７】
ステップS-108で、ｄは選択し尽くしていないと判定し、ステップS-109に進んだ。し尽くしていると判定した場合はステップS-115の処理を実行して、終了する。第二の整数計画定式化手段４８が、ステップS-109で、目的関数値＝３４２，５２０、費用4000の材料が７２個、費用3680の材料が１４個、費用3000の材料が１個となる材料使用予定数量ベクトルｄを選択し、ステップS-110で、第３制約条件式Ｃｘ＝ｄを生成し、記憶装置６に記憶させ、第二の整数計画を定式化した。
【００３８】
図２９でＣｘ＝ｄの説明をする。材料使用行列Ｃは３×149000次であり、１行目の要素は、対応する使用個数ベクトルｘが材料費用4000を表す場合は１、そうでない場合は０であり、２行目の要素は、対応する使用個数ベクトルｘが材料費用3680を表す場合は１、そうでないない場合は０であり、３行目の要素は、対応する使用個数ベクトルｘが材料費用3000を表す場合は１、そうでない場合は０である行列である。材料使用予定数量ベクトルｄは、上記の費用4000の材料が７２個、費用3680の材料が１４個、費用3000の材料が１個を要素とする３次のベクトルである。
【００３９】
この第二の整数計画のLP緩和問題が実行可能であるかを判定するために、シンプレックス法演算手段３８を実行する。材料使用予定数量ベクトルｄによっては実行可能でない場合があるからである。実行不可能の判定されたらステップS-108、S-109に戻ってｄの選択をやりなおす。実施例２では、実行可能と判定されたので、LP緩和解を求めてステップS-111へ進んだ。
【００４０】
ステップS-111で、ステップS-110のLP緩和解が第二の整数計画の実行可能解ではないと判定し、ステップS-112へ進んだ。もし、実行可能解であると判定した場合は、ステップS-114へ進み、記憶した整数要素と実行可能解を編集して解として出力して終了する。ステップS-112で、演算制御手段４４が、ステップS-4で求めたLP緩和解の整数要素数≧１であると判定した。
【００４１】
この判定は、次のように行われる。図３０は、LP緩和解の整数要素に対応する割付パターンベクトルを取り出した結果である。LP緩和解の値が１である要素が３４個、値が２である要素が４個、値が３である要素が１個、値が９である要素が１個あったことを示している。したがって、整数要素の数は３４個＋４個＋１個＋１個＝４０個であるから、LP緩和解の整数要素数≧１である。また、材料の個数は１×３４個＋２×４個＋３×１個＋９×１個＝５４個である。ステップS-113に進んだ。
【００４２】
ステップS-113で、部分問題のための製品設定手段４２が、LP緩和解の整数でない要素に対応する割付パターンベクトルに割り付けられた製品データ１４を取り出し、４５次の製品横長ベクトルｗpを生成し、記憶装置に記憶させた。ステップS-102に戻り、この１つ目の部分問題のための処理を続けた。暫定解記憶手段２６がファーストフィット法を用いて暫定解を求め、記憶装置６に記憶させた。
【００４３】
ステップS-103で、製品要求数量ベクトル生成手段２８が、４５次の製品要求数量ベクトルｂを生成し、記憶装置６に記憶させ、割付パターン生成手段が、ファーストフィット法を用いて、４５次の割付パターンベクトルａjを74335個生成し（j＝1〜74335）、記憶装置６に記憶させる。
【００４４】
割付方データ生成手段３２が、割付パターンベクトルａjが示す材料への製品の割付方を記憶装置６に記憶させ、割付パターン行列生成手段３４が、４５×74335次の割付パターン行列Ａを生成し、記憶装置６に記憶させ、第一の整数計画定式化手段３６が、74335次の使用個数ベクトルｘを定義し、74335次の費用係数ベクトルｆと上記使用個数ベクトルｘの積で表される目的関数ｆｘと、第１制約条件式Ａｘ≧ｂと第２制約条件式ｘi＝｛0,1,2,3,…｝とを生成し、記憶装置６に記憶させた。
【００４５】
原問題の割付パターン行列Aは９８×149000次であり、１つ目の部分問題の割付パターン行列では、４５×74335次である。製品要求数量ベクトルｂでは、原問題（９８次）、１つ目の部分問題（４５次）、使用個数ベクトルｘでは、原問題（149000次）、１つ目の部分問題（74335次）、費用係数ベクトルｆでは、原問題（149000次）、１つ目の部分問題（74335次）である。このように大幅に問題の次数が低減されることから、部分問題では演算時間が大幅に短縮される。
【００４６】
その後、ステップS-104で、シンプレックス法演算手段３８が、第一の整数計画をLP緩和して、すなわち第２制約条件式を除いて、LP緩和解を求めた。
ステップS-105で、演算制御手段４４が、ステップS-104で求めたLP緩和解が実行可能解であると判定し、ステップS-107に進み、ステップS-107で、演算結果出力手段４０が、材料費用を最小化するための種類毎に必要な材料個数と各材料への製品の割付方２０を出力して、終了した。
【００４７】
図３１は、ステップS-105で、LP緩和解が実行可能解となり得られた３３個の材料と製品の関係である。ここで、特許第5983976号公報（特許文献３）に記載の方法と比較するために、実施例２の材料データ１２、製品データ１４を用いて割付を実施した。比較を図２３（ｂ）に示す。図２３（ｂ）から、特許文献３と比べて、実施例２は、費用は同じであるが、計算時間が７分の１程度に短縮している。刃物厚＝５ミリ、ハナ切り長＝１５ミリ、後切り長＝１５ミリとした。
【００４８】
図３２のステップS-215の解の劣化について、実施例２の結果を用いて説明する。図２８からステップS-206の第二の整数計画で定式化された問題が整数解を持てば、費用4000の材料を７２個、費用3680の材料を１４個、費用3000の材料を１個使用して、製品を割り付けることができ、原問題の目的関数値が最小（３４２，５２０）になることがわかる。
図３４に実施例２の原問題から始めて１つ目の部分問題で求解完了する様子を示す。
【００４９】
費用4000の材料を７２個、費用3680の材料を１４個、費用3000の材料を１個使用して、製品を割り付けることができたのであるから、原問題の目的関数値を最小にしている。原問題を解の整数要素と非整数要素に分けているので、原問題の整数要素の費用＝4000×５３＋3000×１＝２１５，０００となり、原問題のLP緩和解の目的関数値（下界）（＝３４２，４８５．７…  費用と同意）であるから、原問題の非整数要素の費用＝３４２，４８５．７…−２１５，００＝１２７，４８５．７…となる。この１２７，４８５．７…は、１つ目の部分問題の下界になり、この下界以上で最も近い費用となる材料使用予定数量は、費用4000が１９個、費用3680が１４個、費用3000が０個となり、このとき費用計＝4000×１９＋3680×１４＋3000×０＝１２７，５２０である。これは、図２８の費用計の最小値（＝３４２，５２０）＝原問題の整数要素の費用（＝２１５，０００）
＋１つ目の部分問題の整数要素の費用（＝１２７，５２０）となっている。実施例２では、このように１つ目の部分問題が、費用4000が１９個、費用3680が１４個、費用3000が０個という整数解を得ている。当然１つ目の部分問題が材料使用予定数量どおりの整数解を得られるかどうかは求解した結果からわかることである。
しかしながら、例えば、次のような場合には１つ目の部分問題を生成した時点で、求解操作をしなくても、１つ目の部分問題の下界以上で最も近い費用となる材料使用予定数整数量となる解が得られない場合があることがわかる。
【００５０】
（解が劣化する理由）
パターンベクトルを元の問題と同じに構成できないことがある。
製品が、それぞれ２個以上要求された場合に、図３５（ａ）、（ｂ）のような割付パターンが生成する。原問題のLP緩和解の非整数要素が図３５の（ａ）、（ｂ）で表される割付パターンを０．５個ずつ要求し、他のLP緩和解は整数要素であると、部分問題は１個の材料に製品番号１＝２個、製品番号２＝１個、製品番号３＝１個、製品番号４＝１個を割り付ける問題になる。製品番号３の要求数量は１個であり、製品番号４の要求数量は１個であるから、この部分問題では図３４（ａ）、（ｂ）の割付パターンは生成されない。そして、図３５（ｃ）のように１個の材料に割り付けられないことになると、解が劣化して原問題の材料使用予定数量ベクトルでは割り付けられないことになる。このような場合、材料使用予定数量ベクトルｄを選択しなおしたり、または、別のLP緩和解を求めなおしたりして、別の部分問題を生成して、解の劣化を防ぐとよい。図１に示した劣化判定手段５０は、このようにして、部分問題のLP緩和解が劣化しているか否かを判定する。
【００５１】
図３６から図４０までは、図１６から図１９に示した実施例１の割付け結果の一部の例を示している。材料番号が１番の材料には、例えば図３６に示すように製品が割付けされる。図３７の材料番号が３６番の例や、図３８の材料番号が４８番の例や、図３９の材料番号が４９番の例や、図４０の材料番号が５２番の例は、部分問題から得られる割付け例である。ここで、図３８の材料番号４８番の例では、２分の１の材料に割付けをしている。これで、残りの２分の１の材料は別の工程で生かすことができる。
【符号の説明】
【００５２】
１２  材料データ
１４  製品データ
１６  種類ごとに必要な材料個数
１８  材料費用の合計
２０  各材料への製品の割付方
２２  材料設定手段
２４  原問題のための製品設定手段
２６  暫定解記憶手段
２８  製品要求数量ベクトル生成手段
３０  割付パターンベクトル生成手段
３２  割付方データ生成手段
３４  割付パターン行列生成手段
３６  第一の整数計画定式化手段
３８  シンプレックス法演算手段
４０  演算結果出力手段
４２  部分問題のための製品設定手段
４４  演算制御手段
４６  材料使用予定数量ベクトル生成手段
４８  第二の整数計画定式化手段
５０  劣化判定手段
【図１】
2020149207.tif 000003
【図２】
2020149207.tif 000004
【図３】
2020149207.tif 000005
【図４】
2020149207.tif 000006
【図５】
2020149207.tif 000007
【図６】
2020149207.tif 000008
【図７】
2020149207.tif 000009
【図８】
2020149207.tif 000010
【図９】
2020149207.tif 000011
【図１０】
2020149207.tif 000012
【図１１】
2020149207.tif 000013
【図１２】
2020149207.tif 000014
【図１３】
2020149207.tif 000015
【図１４】
2020149207.tif 000016
【図１５】
2020149207.tif 000017
【図１６】
2020149207.tif 000018
【図１７】
2020149207.tif 000019
【図１８】
2020149207.tif 000020
【図１９】
2020149207.tif 000021
【図２０】
2020149207.tif 000022
【図２１】
2020149207.tif 000023
【図２２】
2020149207.tif 000024
【図２３】
2020149207.tif 000025
【図２４】
2020149207.tif 000026
【図２５】
2020149207.tif 000027
【図２６】
2020149207.tif 000028
【図２７】
2020149207.tif 000029
【図２８】
2020149207.tif 000030
【図２９】
2020149207.tif 000031
【図３０】
2020149207.tif 000032
【図３１】
2020149207.tif 000033
【図３２】
2020149207.tif 000034
【図３３】
2020149207.tif 000035
【図３４】
2020149207.tif 000036
【図３５】
2020149207.tif 000037
【図３６】
2020149207.tif 000038
【図３７】
2020149207.tif 000039
【図３８】
2020149207.tif 000040
【図３９】
2020149207.tif 000041
【図４０】
2020149207.tif 000042