11

線形計画法を解くためのシンプレックス法を学んだばかりで、双対問題が何を表しているのかを理解しようとしています。

二重の問題を解決する仕組みを理解しています - それについては助けは必要ありません。(ウィキペディアでそれについて読んだ後でも)得られないのは、 dualのy変数の実際の意味です。

主な問題の変数の意味と、双対から私が理解したことをすべて一緒に例を挙げて、双対の意味を説明するのに十分親切な人に尋ねたいと思います。

プライマル:

max z = 3*x1 +  5*x2

subject to:
          x1          <=  4
                2*x2  <= 12
        3*x1 +  2*x2  <= 18

        x1, x2 >= 0

主問題では、x1とx2は生産される製品AとBの数量です。3と5はそれぞれの販売単価です。製品はM1 ～ M3 の3 台の機械で生産されます。最初の製品を生産するには、M1で 1 時間、 M3で 3 時間の作業が必要です。2 番目のものを作成するには、 M2とM3の両方で 2 時間の作業が必要です。マシンM1、M2、M3は最大4、12、および18で動作可能時間、それぞれ。最後に、どの製品も負の数量を生産できません。

ここで、二重の問題を設定します。

min z = 4*y1 + 12*y2 + 18*y3

subject to:
          y1         +  3*y3 >= 3
                  y2 +  2*y3 >= 5

          y1, y2, y3 >= 0

今、私が理解できると思う唯一のことは、制約が意味することです: - M1で 1 時間、 M3で3 時間の作業に対して、少なくとも 3 マネーユニットを支払わなければなりません - M2と 2で 2 時間の作業に対してM3で数時間、少なくとも 5 マネー ユニットが支払われるはずです

しかし、 y1変数とy2変数の意味を理解することはできません。最終的に最小化を行うと、zの結果は主変数で同じになります (ただし、主変数は結果の下限を増やし、双対変数は上限を減らします)、双対問題の目的関数は何で構成されますか?の？

4

1 に答える 1

12

デュアルの目的関数は、3 台のマシン (リソース) の時間あたりのコストを最小限に抑えることです。

したがって、Dual の目的関数 ( 4*y1 + 12*y2+ 18*y3) は次のように読み取ることができます。

Minimize 4*(cost/hour of Machine1) + 12*(cost/hour of M2) + 18*(cost/hr of M3)

プライマルが生産の利益を最大化することを扱ったので、デュアルは企業の生産コストを最小化するものと考えることができます。

(企業が機械M1、M2、M3 を「レンタル」していると考えると役立つ場合があります。) 彼らがそれをレンタルする場合、各機械に [$/hour] を支払う必要があり、それでも製造して利益を上げているのはいくらですか? ?x1x2

二重変数の意味y1, y2, and y3は、1 時間あたりの所有/レンタル コストです。

双対問題のy変数は、資源の「影の価格」と呼ばれることがよくあります。

デュアルを理解するための洞察を探しているので：

  1. 1 つの秘訣は、双対の次元を減らすことです。(Machine M1が 1 つしかないと想像してください。) ここで、双対を定式化し、目的関数と制約を理解しようとします。
  2. 「機会費用」の観点から考えると役立ちます。製造会社が機械 (リソース) をレンタルする必要がある場合、1 時間あたりいくらの料金を支払う必要がありますか? あるいは、他に多くの (収益性の高い) 製品があった場合、これらの他の製品を製造する代わりにX1、機械を 1 時間あたりどのくらいのコストで割り当てるか。X2
  3. すべての双対を簡単に「理解」できるわけではないことに注意してください。ただし、プライマルの対応する変数を見ると、多くの二重制約の感覚をつかむことができます。同様に、対応する主制約を調べることで、双対変数に関する洞察を得ることができます。
于 2012-02-02T09:46:03.783 に答える