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

未知の変数はすべて整数または整数でなければならないことを指定しながら線形システムを解こうとすると、整数線形計画問題が発生します。 線形システムは、プログラマーが解を見つけようとしている状況を記述する方程式のセットです。 それらは通常、最大化または最小化する必要がある1つの方程式と、未知の変数に制限を設定する1つ以上の制限方程式で構成されます。 システムが線形になるためには、各制限が線形方程式でなければなりません。 つまり、指数が1より大きい未知の変数のインスタンスが含まれてはなりません。

通常の線形システムは、コンピューターを使用して簡単に解決できます。 プログラムは、導関数を見つけてゼロに設定することにより、解を特定できます。 次に、関数のすぐ近くをチェックすることにより、ポイントが最大または最小であることを確認できます。 導関数が関数に沿った各点で定義されている限り、コンピューターには限られた数のチェック可能な解決策しかありません。

線形計画法は、整数制限が追加された整数線形計画法になります。 これは、問題が同じままであることを意味しますが、答えは未知の値の整数値で構成されている必要があります。それらは整数でなければなりません。 時々、これは、分数が許可される場合と比較して、解が最適ではないことを意味します。 しかし、それは現実の世界を反映しており、アイテムはしばしば個別の不可分な単位で入っています。 企業は利益を最大化することを望みますが、製品の一部を販売することは選択できないため、整数線形計画法はビジネスアプリケーションにとって重要になります。

整数の制限が設定されると、線形システムを解く問題はNP完全です。 これは、コンピューターがシステムを解決するのに必要な時間が不定であることを意味します。 整数の制限がある場合、デリバティブのゼロ点が整数になるという保証がないため、コンピューターはデリバティブのツールを使用できません。 解決策は、すべての整数の中で最高値または最低値を持つ整数になるため、コンピューターはそれらすべてをチェックする必要があります。これは、無限の時間を要するプロセスです。

プログラマーは、これらの問題の複雑さに対処するために、ヒューリスティックまたは問題解決の方法を開発しました。 整数線形計画問題を解く方法の1つは、コンピューターが元の問題に関連する一連の問題を解決して、利用可能な値の範囲を1つの解に絞り込む分岐限定アルゴリズムです。 ただし、複雑な問題の場合、これには時間がかかる場合があります。