私の質問は、古い輸送の問題についてです。一度に1つのアイテムしか転送できないボートで、川を渡って3つのアイテムを運ぶことです。制約は、ヤギとキャベツ、ヤギとオオカミなど、特定のアイテムを一緒に残すことができないことです。この問題は、整数計画法または別の最適化アプローチを使用して解決できるはずです。コスト関数は、川の反対側にあるすべてのアイテムであり、そこに到達するために必要な旅行は、さまざまな実行可能なソリューションを試すシンプレックス（？）からの出力である可能性があります。誰かがこの問題の整数計画法（または線形計画法）の定式化、および/またはすべてのパスを試しているシンプレックスのトレースを含む、プログラムでソリューションを提供できるMatlab、Octave、Pythonベースのコードを持っているかどうか疑問に思いました-私たちのボート乗り。
ここには面白いものがいくつかありました
http://www.zib.de/Publications/Reports/SC-95-27.pdf
ありがとう、
この定式化には整数変数が必要であることは間違いありません。このような問題を解決する従来の方法は、バイナリ変数モデルを定式化し、その定式化をソルバーに渡すことです。この場合の MATLAB は、Optimization Toolbox にアクセスできない限り機能しません。
http://www.mathworks.com/products/optimization/index.html
あなたの定式化では、次のことに対処する必要があります。
あなたの場合、これは次のようになります。
x_it ([yes=1 no=0] を選択して、アイテム i をボートトリップ番号 t の間に輸送します)
これがあなたの説明からはよくわかりませんが、各ボート旅行に関連するコスト c_t があるはずです。合計時間を最小限に抑えたい場合、各移動のコストは定数 1 になります。したがって、目的は次のようになります。
SUM((i,t),c_t*x_it) を最小化します (したがって、すべての旅行の総費用を最小化しています)
これは、問題のトリッキーな部分です。複雑な制約は、特定した排他性です。x_it はバイナリであることを思い出してください。
互いに競合する項目 (i1、i2) の各ペアに対して、次のような制約があります。
x_(i1 t) + x_(i2 t) <= 1
例えば：
x_("キャベツ" "1") + x_("ヤギ" "1") <= 1
x_("オオカミ" "1") + x_("ヤギ" "1") <= 1
x_("キャベツ" "2") + x_("ヤギ" "2") <= 1
x_("オオカミ" "2") + x_("ヤギ" "2") <= 1
など。
これにより、競合が防止されることがわかります。「キャベツ」と「ヤギ」を同じトリップに割り当てるボート スケジュールは、「1+1 > 1」であるため、このバイナリ排他制約に違反します。
GAMS、AMPL、GLPK などのツールを使用すると、この一連の制約を非常に簡潔に表現できます。
それが役立つことを願っています。