主要内容

このページの翻訳は最新ではありません。ここをクリックして、英語の最新版を参照してください。

カッティングストック問題:ソルバーベース

ライブ スクリプトを開く

この例は,整数線形計画法のサブルーチンと共に線形計画法を使用して,カッティング ストック問題を解く方法を説明します。この例では,ソルバーベースの最適化問題の設定のアプローチを使用します。問題ベースのアプローチについては,カッティング ストック問題: 問題ベースを参照してください。

問題概要

製材所は、木から固定長の木材を切り出すことから始めます。木材の固定長を指定します。

对数长度=40；

その後、以降の処理に適した固定長に木材を切ります。問題は、製材所が最小限の木材で一連の注文に対応できるように、どのように木材を切り出すかということです。

これらの固定長と長さごとの注文の数量を指定します。

长度列表=[8；12; 16; 20]; 数量=[90；111; 55; 30]; NLENGHTS=长度（长度列表）；

切り出す際に素材の無駄は生じず,カッティングのコストもかからないものとします。

線形計画法の定式化

河流浅水处と 富尔克森[1]および 吉尔摩と 戈莫里[2]を含む複数の著者が以下の手順を提案しています。これを次のセクションで実装します。カッティング パターンとは 1.本の木材から切り出すことができる長さのセットです。

すべての考えられるカッティング パターンを生成するより、部分問題の解としてカッティング パターンを生成する方が効率的です。カッティング パターンの基本セットから始め、既存のパターンを使用したカッティングで要求を満たすという制約の下で、使用する木材数を最小限にする線形計画問題を解きます。

その問題を解いた後に,整数線形計画法の部分問題を解いて新しいパターンを生成します。この部分問題では最適な新しいパターン,つまり,考えられる長さ合計の对数长度を総和が上回らないように、lengthlistの各長さで切り出せる木材の数を求めます。最適化するための数量は,新しいパターンの被約費用であり,現在の解のラグランジュ乗数と新しいカッティングパターンの積の和を,1から引いたものです。この数量が負の場合,そのパターンを線形計画問題に持ち込むと,その目的関数が改善されます。それ以外の場合は,より良いカッティングパターンは存在せず,今までに使用されたパターンが最適な線形計画問題の解を与えます。この結論の理由は,主シンプレックス法(被約費用が負になる変数がないときに停止する方法)を停止する場合の理由と正確に対応します。この例の問題は,負の被約費用のパターンがないときに終了します。詳細と例については,列生成アルゴリズムとその参考文献を参照してください。

この方法で線形計画問題を解くと、非整数解が得られることがあります。したがって、生成されたパターンを使用し、変数が整数値を持つという制約の下で、もう一度問題を解きます。

MATLABソルバーベースでの定式化

この定式化では、パターンはlengthlistの各長さのカット(切り出した木材)数を含む整数のベクトルです。パターンを保存するための行列模式を準備します。行列の各列が 1.つのパターンを表します。たとえば、

模式 = [ 2. 0 0 2. 0 1. 1. 0 ] .

最初のパターン (列) は長さ 8.の 2.本のカットと長さ 20の 1.本のカットを表します。2.番目のパターンは、長さ 12の 2.本のカットと長さ 16の 1.本のカットを表します。それぞれは、カットの長さの合計が对数长度= 40 を上回らないため、実行可能なパターンです。

この定式化では,xが、各パターンの使用回数を含む整数の列ベクトルである場合、图案*xは各タイプのカット数を示す列ベクトルとなります。要求を満たすための制約は、图案*x>=数量です。たとえば、前出の行列模式を使用して、 x = [ 45 56 ] であると仮定します (このxは 101本の木材を使用します)。この場合

模式 * x = [ 90 112 56 45 ] ,

これは要求を上回っているため、実行可能な解を表しています。

数量 = [ 90 111 55 30 ] .

初期の実行可能なカッティング パターンを得るため、カットの長さが 1.つだけの最も簡単なパターンを使用します。その長さで、木材に対して実行可能なだけ多くのカット数を使用します。

模式=diag（地板（对数长度/长度列表））；nPatterns=大小（模式，2）；

現在のラグランジュ乗数に基づいて既存のパターンから新しいパターンを生成するには、部分問題を解きます。それ以上の改善が見つからなくなるまで、ループ内で部分問題を呼び出してパターンを生成します。部分問題の目的関数は、現在のラグランジュ乗数のみに依存します。変数は、各長さのカット数を表す非負の整数です。唯一の制約は、1.つのパターン内のカットの長さの合計が木材の長さを超えないことです。下限ベクトルlb2と行列A2,およびこれらの範囲と線形制約を表すb2を作成します。

lb2=零（n长度，1）；A2=长度列表'；b2=对数长度；

ソルバーからの不要なフィードバックを避けるために、外側のループと内側の部分問題の解の両方に対して展示オプションを“关闭”に設定します。

lpopts=options(“linprog”,“显示”,“关闭”); ipopts=options(“intlinprog”，lpopts）；

ループの変数を初期化します。

降低成本=-Inf；降低成本公差=-0.0001；exitflag=1；

ループを呼び出します。

而降低的成本<降低的成本公差和退出间隔>0磅=零（n模式，1）；f=lb+1；A=-模式；b=数量[值，nlog，exitflag，~，lambda]=linprog（f，A，b，[]，[]，lb，[]，lpopts）；如果exitflag>0 fprintf('正在使用%g日志\n'（非直瞄发射系统）；%现在生成一个新的模式，如果可能的话f2=-lambda.ineqlin[值，降低的成本，pexitflag]=intlinprog（f2,1:nLength，A2，b2，[]，[]，[]，[]，lb2，[]和ipopts）；降低成本=1+降低成本；%如果此降低的成本为负，则继续newpattern=圆形（值）；如果pexitflag>0&&reducedCost结束结束结束
使用97.5日志使用92日志使用89.9167日志使用88.3日志

これで,線形計画問題の解が得られます。解を完全なものにするために,すべての変数が整数であるintlinprogを使用して,最終パターンでもう一度問題を解きます。また,各パターンと問題全体について,使用されない木材の数量(フィート単位)として無駄を計算します。

如果exitflag<=0显示(“列生成阶段出错”)其他的[values，logsUsed，exitflag]=intlinprog（f，1:length（lb），A，b，[]，[]，[]，[]，lb，[]，[]，[]，ipopts）；如果exitflag>0值=四舍五入（值）；logsUsed=圆形（logsUsed）；fprintf('最佳解决方案使用%g日志\n', logsUsed);Totalwaste = sum((patterns*values - quantity).*lengthlist);生产过剩造成浪费对于j=1：尺寸（值）如果值(j) > 0 fprintf('使用模式剪切%g个日志\n'，值（j））；对于w=1：尺寸（图案，1）如果图案（w，j）>0 fprintf(' %d切(s)的长度%d\n'、模式(w, j), lengthlist (w));结束结束wastej=对数长度-点（图案（：，j），长度列表）；%由于模式效率低下而造成的浪费总废物=总废物+废物j；fprintf('此模式的浪费为%g\n', wastej);结束结束fprintf('此问题中的总浪费量为%g。\n', totalwaste);其他的disp (“最终优化中的错误”)结束结束
最佳解决方案使用89个日志
切15根有图案的原木
2个长度为20的切口
此模式的浪费为0
切18根有图案的原木
1段8段2段16段
此模式的浪费为0
切割37根有花纹的原木
2个长度为8的切口2个长度为12的切口
此模式的浪费为0
切19根有图案的原木
2个长度为12的切口1个长度为16的切口
此模式的浪费为0
这个问题的总浪费是28。

無駄の一部は過剰生産が原因です。製材所は 1.本の木材から 3.本の 12フィートの木材を切り出しますが、1.本しか使用しないためです。無駄の一部はパターンの非効率性が原因です。3.本の 12フィートの木材は、全長の 40フィートより 4.フィート短いためです。

参考文献

福特，Jr. R.， Jr. Fulkerson。最大多商品网络流的建议计算。《管理科学》1958年第5期，第97-101页。

[2] 吉尔摩，P。C.和R。E戈莫里。下料问题的线性规划方法——第二部分。运筹学研究11，第6期，1963年，第863-888页。

関連するトピック

优化工具箱ドキュメンテーション

サポート

データサイエンス向けMATLABチートシート

データサイエンス向けMATLABチートシート

チートシートをダウンロードして