6

確かに、これはそれ自体プログラミングに関する質問ではありません...しかし、同じように質問するより良い場所は思いつきませんでした。

私は、買い物客が特定のサイトで最大の節約を達成する方法を決定するのを最終的に支援するアプリケーションを作成しています。このサイトでは、ほぼすべての製品について、通常価格と割引価格の 2 つの価格を提供しています。割引価格はどなたでもご利用いただけますが、1 つの注文に追加できる割引商品は 1 つだけです。その情報だけで、インセンティブは注文サイズを最小限に抑え、代わりに複数の注文を行うことです. 一方、総送料は注文サイズ (重量) によって決まるため、注文サイズを最大にして 1 回だけ注文するインセンティブがあります。

1 つの商品に対して利用可能な割引と、注文の送料に影響を与える重量を考慮して、注文のバランスをとる最も効率的な方法を決定するためのモデルを探しています。

学校に戻ったときのことを十分に覚えているので、これは線形計画法の問題だと思います...しかし、そのクラスについて覚えているのは、それがどれほど混乱したかということだけでした。

このプログラムの計算方法に関するヒントはありますか?

4

2 に答える 2

2

上記の私のコメントを拡張すると、この問題は送料の正確な構造に大きく依存します。送料が (潜在的に) 非ゼロの定数項で線形であるとします。つまり、送料 = C + Rw、ここで C と R は定数、w は注文の重量です。次に、最適な解決策は単純であることがわかります。割引が C 未満のすべてのアイテムを 1 つの注文にグループ化し、割引が C を超える各アイテムを個別に注文します (読者の演習として残します)。C = 0 の縮退ケースでは、単純に各アイテムを個別に注文します。

一方、配送コストがしきい値構造のほうが多い場合、たとえば、荷物の重量が B 未満の場合、コストは C1 ですが、B より大きい場合、コストは C2 になります。状況は次のようになります。 NP 完全ビンパッキング問題の一種。ここで、状況が NP 完全問題のような形をしているからといって、すぐに希望をあきらめてはならないことに注意してください。多くの現実世界の状況では、優れたヒューリスティックが存在し、現実世界の入力の範囲によって問題が管理可能なインスタンスに制限される可能性は十分にあります。

実生活では、輸送費はおそらくさまざまなものの組み合わせである可能性が高く（たとえば、不連続性を伴う区分線形である可能性があります）、問題のモデル化が非常に困難になります。しかし、問題を理解するためには、これらのコストがどのように構成されているかを明確に理解することが重要であることを実証できたと思います.

于 2011-02-18T17:49:43.687 に答える
2

これは通常の線形計画法ではなく、整数線形計画法です。前者は O( n ²) で可解、2 番目は NP 困難です。

分枝限定アルゴリズムのいくつかの変形をプログラムに適用できるはずです。自分で実装したくない場合は、GLPK、COIN-OR、CPLEX などのライブラリを利用できます。

于 2011-02-16T22:34:02.787 に答える