線形計画法を計画問題に使用できると聞きました。線形計画法が最適であり、大規模な計画 (たとえば、m 台のマシンで n 個のジョブを計画する) は指数関数的に困難であるため、その方法がよくわかりません。
たとえば、線形計画法を使用して 100 個のジョブと 10 個のマシンの問題を解決するにはどうすればよいでしょうか? 説明またはさらに読み物を教えてもらえますか？
質問する
349 次
1 に答える
1
たとえば、線形計画法を使用して 100 個のジョブと 10 個のマシンの問題を解決するにはどうすればよいでしょうか?
通常、できません。これは、線形計画法 (LP) が適用できる種類の計画問題ではありません。
LP 問題では、解決したい一連の変数があります。これらの変数に対する制約を表す一連の線形不等式があります。そして、特定のソリューションのコスト (または利益) を表す、これらの変数の線形関数 (つまり、指数、除算、「if-then-else」など) があります。
そのような問題を抱えている場合、LP を使用して効率的に最適解を生成できます。あなたが求めているような製造現場のスケジューリングは、そのような問題ではありません。
LP は、「より高いレベル」の計画に役立つ傾向があります。たとえば、各工場で各製品をどれくらい作ればいいですか？このような問題では、多くの場合、制約を線形不等式として指定し、コスト (または利益) を線形関数として指定できます。これは、LP を利用するために行う必要があります。注意してください、私は「各製品の量...」と言いましたが、「何...」ではありません. これは LP のもう 1 つの制限であるため、変数は実際の値を取ることができなければなりません。整数解を与える解が必要な場合は、整数計画法 (または混合整数計画法) の問題を見ています。
于 2016-11-09T14:53:09.590 に答える