整数計画法

整数計画法は、最適化または数学的計画法の一分野です。これは、可能な解決策の集合から最良の解を見つけることを意味します。線形計画法が線形方程式といくつかの制約を扱うのに対し、整数計画法は解の変数が整数でなければならない特別なタイプです。この制約により、整数計画法はより複雑で難しくなりますが、いくつかのリソースが丸ユニットでのみあるシナリオにおいて、より適用可能になります。

整数計画法とは何ですか？

整数計画法は、与えられた目的関数を最適化することを目的とする数学的問題を含みます。回線上で最初は線形計画法のように見えるかもしれませんが、重要な違いがあります。整数計画法では、関数が最適化される確率は、一部またはすべての変数が整数でなければ定数です。制限がある場合のみです。

整数計画法は、さまざまな最適化問題を解くために使用できます。例として、計画とスケジューリング、リソース配分、物流、製造、電気通信、金融などの産業での意思決定が含まれます。

数学的定式化

線形計画問題の一般的な形式は次のように表現できます。

Max または Min: c1*x1 + c2*x2 + ... + cn*xn

制約条件:

a11*x1 + a12*x2 + ... + a1n*xn (=) b1
a21*x1 + a22*x2 + ... + a2n*xn (=) b2
,
am1*x1 + am2*x2 + ... + amn*xn (=) bm

x1, x2, ..., xn >= 0

ここで、cは目的関数の係数、aは制約の係数、bは右辺の定数を示します。目的関数を最大化または最小化するためにx1, x2, ..., xnの値を見つけることが目標です。最小化してください。

整数計画法では、1つまたは複数の変数x1, x2, ..., xnは整数のみの値を取るよう制約されます。すべての変数が整数で制約されている場合、その問題は純粋な整数計画問題と呼ばれます。一部の変数のみが整数の場合、これは混合整数計画問題です。

例

単純な整数計画問題

これらの概念を理解するために、単純な整数計画の例を見てみましょう。例えば、ある会社が製品AとBを最適に生産する数を決定したいと考えています。製品Aの1単位当たりの利益は3ドルで、製品Bの1単位当たりは5ドルです。その会社は、製品Aを7単位以上、製品Bを4単位以上生産することはできません。

整数計画モデルは次のように設定できます。

Max: 3A + 5B

制約条件:

A + B 
        
        
        
        
        
        

コメント