問題タブ [linear-programming]

C ベースの LPPSolver ライブラリを使用してシンプレックス問題を解決する古いコードを移行する必要があります。Java での私の問題は、多数の変数を処理できる anon 商用 Java ベースのソルバーを見つけることです。Apache SimplexSolver を試しました。しかし、ほとんどの場合、実現不可能な解決策が得られます。助けてください。ありがとう

私はいくつかの解決策を見つけましたが、それらはあまりにも厄介です。

線形計画問題を自動的に実行可能にするアルゴリズムが必要です。具体的には、アルゴリズムは、その入力が実行可能な解を持たない可能性のある線形計画問題であり、その出力が実行可能な解を持つようにバインドされている同様のプログラミング（パラメーターが最小で変更されている）であるようなものです。私はアルゴリズムの初心者であり、そのような問題に関する既存の研究/作業があるかどうかを尋ねますか？任意の提案やコメントをいただければ幸いです。ありがとう、リチャード

私は中間試験の準備をしようとしていて、アルゴリズムの本からいくつかの問題を調べていましたが、次の問題を理解できないようです:

線形計画法が成り立つ実数 a と b の必要十分条件を求めます。

(a) 実行不可能です。(b) は無制限です。(c) 有限で唯一の最適解を持つ。

これが私が思いついたものです: (a) に対して、別の制約を追加できます: ax+by=>5

b と c についてどうすればよいかわかりません。すでに与えられている制約を変更できるかどうか、または新しい制約を追加できるかどうかわかりません。

どんな助けでも大歓迎です。どうもありがとうございました。

これは数学に焦点を当てた質問かもしれませんが、CSのコンテキストにあるため、ここで質問したいと思います。別の（任意の）クワッドの内側に、可能な限り最大の高さと幅を持つ内接クワッドで長方形を内接することを検討しています。アルゴリズムも似ていると思うので、サークルでもできるかと思っています。

より明確に聞くことは、例として境界四辺形が意味することです。

これが私が達成しようとしている内接最大化の2つの例です：

私はいくつかの予備調査を行いましたが、決定的なものは何も見つかりませんでした。何らかの形の動的計画法が解決策になる可能性があるようです。これは線形最適化問題であり、私が見つけたよりも一般的であるはずであり、おそらく私は間違った用語を探しています。

注： 内接正方形については、探しているターゲットのw / h比がわかっていると仮定します（例：4：3）。クワッドの場合、辺が交差せず、凹面になると想定します（計算が簡単になる場合）。

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

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

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

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

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

ベクトルと行列についてちょっとした質問があります。

ベクトル V = {v1, v2, ..., vn} とします。次のように定義された n 行 n 列の距離行列 M を生成します。

M_ij = | v_i - v_j | i、jが[1、n]に属するように。

つまり、正方行列の各要素 M_ij は、V の 2 つの要素の絶対距離です。

たとえば、ベクトル V = {1, 3, 3, 5} がある場合、距離行列は M=[ 0 2 2 4; になります。2 0 0 2; 2 0 0 2; 4 2 2 0; ]

とてもシンプルに思えます。ここで問題になります。このような行列 M が与えられた場合、初期 V を取得するにはどうすればよいでしょうか?

ありがとうございました。

この質問に対するいくつかの回答に基づいて、答えは一意ではないようです。したがって、すべての初期ベクトルが平均 0、分散 1 に正規化されているとします。問題は、このような対称距離行列 M が与えられた場合、正規化された初期ベクトルをどのように決定するかです。

問題を解決する必要があります。私は5つのデバイスを持っています。いずれも 4 種類の I/O タイプがあります。そして、対象となる入出力の組み合わせがあります。最初のステップでは、選択したデバイスの合計 I/O 数がすべて目標値以上になるように、デバイス間のすべての組み合わせを見つけたいと考えています。説明させてください：

制約もあります。組み合わせで、最大。デバイスの数は最大 5 です。

2 番目のステップでは、見つかった組み合わせの中から最も安いものを選びます。

実際、この問題は Python の for ループで解決できました。私は魔法のように働きます。しかし、cython を使っているのに時間がかかりすぎます。

この種の問題に対して、他にどのようなオプションを利用できますか?

MapReduceを使用して分散システムで単純な線形計画問題を解決できますか？

これは、線形計画法を知っている人にとっては非常に基本的な質問かもしれません。
私が LP で見た問題のほとんどは、次の形式に多少似ています。

つまり、目的関数と制約関数に同じ数の未知数があります。

私の問題は、目的関数に未知の変数が 1 つ、制約関数に未知の変数が 3 つあることです。
問題はこんな感じ

ご覧のとおり、目的関数には 1 つの未知数、つまりw1しかなく、制約関数には 3 つ (または 2 つとしましょう) の未知数、つまりw1、x、yがあります。
特にRまたはMATLAB線形プログラミングツールボックスを使用して、この問題を解決する方法を教えてください。