- 締切済み
【至急】線形計画問題について、ヒントをください！
maximize 7x1 + 4x2 + 2x3 subject to 3x1 + 3x2 + x3 ≦ 36 .................. 2x1 + x2 + x3 = 18 .................. x1,x2,x3≦0 . この問題の最適解と最適値を求めたいのですが、、まず標準形の線形計画問題に変形する段階で、 2x1 + x2 + x3 = 18 と、 = がでできてしまい、 subject to 3x1 + 3x2 + x3 + x4 = 36 ................... 2x1 + x2 + x3 + x5 = 18 ................... x1,x2,x3,x4,x5≦0 としていいのか、 subject to 3x1 + 3x2 + x3 + x4 = 36 ................... 2x1 + x2 + x3 = 18 ................... x1,x2,x3,x4≦0 としていいのかが分かりません。 ≦ や ≧ ではなく、= が制約関数に含まれていると、標準形ではどの様に変形すれば宜しいのでしょうか？ どなたか教えてください。また、理由もお聞かせ頂けると幸いです。
- みんなの回答 （3）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
ちなみに 2段階シンプレックス法を使うなら 1. まずスラック変数 x4 を導入して不等式制約 3x1 + 3x2 + x3 ≦ 36 を等式制約 3x1 + 3x2 + x3 + x4 = 36 にかえる (←これが「標準形」のはず) 2. さらに元の等式制約に対し人工変数 x5 を導入して 2x1 + x2 + x3 + x5 = 18 とし, 目的関数 -x5 を最大化する問題を解く (「目的関数 x5 を最小化」でも同じだけど普通はこう書く: 最大値が 0 でなければ元の問題は解けない) 3. 人工変数を取り除き, 目的関数を元に戻して再度シンプレックス法 って手順.
- info22_
- ベストアンサー率67% (2650/3922)
>x1,x2,x3≦0 これは x1,x2,x3≧0 の間違いではないですか？ そうであれば 2x1 + x2 + x3 = 18 は x3=18-2x1-x2≧0 なので 2x1+x2≦18 という制約条件に置き換えられます。 また x3=18-2x1-x2...(※) を目的関数ともう１つの制約条件に代入してやれば 目的関数：3x1 + 2x2 + 36 制約条件： 2x1 + x2 ≦ 18 ...........x1,x2≧0 という線形計画問題に変形できます。 ここでx3は(※)の式から決まります。 この線形計画問題の最適解は x1=0,x2=18,x3=0 で目的関数の最大値は72となります。
- Tacosan
- ベストアンサー率23% (3656/15482)
a = b if and only if a ≧ b and a ≦ b ではあるんだけど, この問題についていえば x2 なり x3 なりを消しちゃった方が早いと思う. ただ, この問題, 解けないんだよなぁ.
補足
書き忘れましたが、2段階法で解く予定です。 それでも解けませんか？