整数線形プログラミングとは何ですか？

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

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

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

整数制限が整ったら、線形システムを解く問題はNP完全になります。これは、コンピューターがシステムを解決するために必要な時間が不確定であることを意味します。整数制限、コンピューターSは、導関数のゼロポイントが整数に落ちるという保証がないため、導関数のツールを使用できません。ソリューションは、すべての整数から最高または最低値の整数であるため、コンピューターはそれらをすべてチェックする必要があります。これは、無限の時間がかかる可能性があります。

プログラマーは、これらの問題の複雑さに対処するために、ヒューリスティックまたは問題解決の方法を開発しました。整数線形プログラミングの問題を解決する1つの方法は、ブランチとバウンドアルゴリズムです。このアルゴリズムでは、コンピューターは元の問題に関連する一連の問題を解決して、利用可能な値の範囲を1つのソリューションに絞り込みます。ただし、複雑な問題の場合、これには長い時間がかかる場合があります。