- 締切済み
線形計画法の問題です
Ｐ：最大化ｃ＾Ｔｘ（ｃ＾Ｔはｃの転置） 条件Ａｘ＜＝ｂ ｘ＞＝０ ただし、Ａはｍ＊ｎ行列、ｂはｍ次元ベクトル、ｃはｎ次元ベクトル、ｘはｎ次元 変数ベクトルである。ベクトルはすべて列ベクトルとし、ｃ＾Ｔはｃの転置を表す。 問題Ｐは最適解を持つと仮定し、目的関数の最大値をｆと表す。また、問題Ｐ に関連して、ｍ次元ベクトルｕをパラメータとする次の線形計画問題を考える。 Ｐ（ｕ）：最大化ｃ＾Ｔｘ－ｕ＾Ｔ（Ａｘ－ｂ） 条件ｘ＞＝０ 問題Ｐ（ｕ）の目的関数の最大値ｇ（ｕ）と表す。ただし、問題Ｐ（ｕ）が有界でない 場合はｇ（ｕ）＝無限大と定義する。以下の問いに答えなさい。 １）問題Ｐの双対問題を書きなさい ２）任意のｕ＞＝０に対して、ｇ（ｕ）＞＝ｆが成り立つことを示しなさい ３）ｍｉｎ｛ｇ（ｕ）｜ｕ＞＝０｝＝ｆが成り立つことを示しなさい。ただし、線形計画問題 に対する強双対定理を用いて良い。 以上の問題をお願いします。
- f3yin
- お礼率33% (1/3)
- 数学・算数
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
関連するQ&A
- 線形計画問題の標準形
現在大学で線形計画法を学んでいるのですが，実際に数字を用いて問題を解く事にはなれてきたのですが，証明問題などになるとどの様に回答を行えば良いか回答に繋がるプロセス分かりません． どの様なプロセスで回答をすれば良いかなにかアドバイスがございましたらよろしくお願いします．以下が現在回答に困っている問題ですのでよろしくお願いします． 線形計画法の標準形 目的関数：c^T x →最小 制約条件：Ax =b x≧0 m<nとなる自然数．x ∈ R^n, c ∈ R^n, b ∈ R^mであり，Aはm*n実行列で，rankA = m とし b ≠ 0 とする． 問題１．線形計画問題の制約条件を満たすxのなす集合を実行可能領域Fで表し，Fが空集合でないときFが凸集合であることを示しなさい． Fが凸集合とは x,x' ∈ F ⇒tx + (1 - t)x' ∈ F (∀t ∈ [0,1]) が成立するときをいう． 問題２．Au = b を満たすベクトル u ≠ 0 が存在する事を示せ． 問題３．Ax = 0 を満たすxのなす R^n の線形部分空間はAの核と呼ばれkerAと表す．Ax = bを満たすxのなす R^n の部分集合を J で表すとき J = { x ∈ R^n | x = u + v, v ∈ kerA} となる事を示せ．ただしuは問題２で存在を示したベクトルである．
- 締切済み
- 数学・算数
- 線形写像の問題です。
線形写像の問題です。 V:n次元実ベクトル空間 線形写像f:V→V f^k:k回写像 とするとき (1)任意の自然数kに対して Imf^(k+1)⊂Imf^k を示せ (2)dimImf^k=1⇒f^(k+1)=cf^k (cは実数)を示せ (1)はImf^kの元からkerf^(k+1)の元を引いて、fで写像させるとImf^(k+1)だからなのはわかるんですが、どのように証明を書いたらいいですか？ (2)1次元の写像は1次元または0という意味ですよね？ 任意にn次元ベクトルxをとる。 dimImf^k=1より、 f^kは行ベクトルで (a,0,…,0) (転置ベクトルで書いている)と表せる。 f^(k)x=(ax,0,…,0)となる これをfで写像すると、Imf^(k+1)は1次元または0次元になっていないようにしか思えないんですが… よろしくお願いします。
- ベストアンサー
- 数学・算数
- 線形代数の問題が解りません。
線形代数の問題が解りません。 線形代数の問題が解りません。 宜しかったら教えてください。 1.次のシステムを考える x(t)= A x(t) + b u(t) ・・・I xに上点あり A=[1 0 0 0;0 -1 0 1;0 0 -1 0;2 0 -1 -1] b=[-1 1 0 -1]の転置 y(t)=c x(t) ・・・II c=[1 0 1 0] 1-1. このシステムの可観測行列をMとするとき、rank=2を示せ これは可観測行列M=[c cA cA^2 cA^3]の転置 となるので、行基本変形で M=[c cA cA^2 cA^3] =[1 0 1 0;1 0 -1 0;1 0 1 0;1 0 -1 0] ・ ・ ・ =［1 0 0 0;0 0 1 0;0 0 0 0;0 0 0 0］ と変形でき、rankM=2となり、ここまでは何とかわかりました。 1-2．KerMの基底ベクトルω3、ω4を求めよ 1-3．ベクトルω1、ω2をω1、ω2、ω3、ω4がR^4の基底ベクトルとなるように定めよ 1-4．T=[ω1 ω2 ω3 ω4]とおく。状態変換x(t)=Tx(t) (右辺のxの上には~あり) によって、状態方程式Iと出力方程式IIはそれぞれどのような式へと変換されるか 1-5．このシステムの伝達関数を求めよ 1-6．システム(A,b,c)の極、および、伝達関数G(ｓ)の極を求めよ 2．Mをk*l行列とする。 2-1 Mの像Im M がベクトル空間R^kの部分空間となることを示せ 2-2 Mの核Ker M がベクトル空間R^lの部分空間となることを示せ 1－5、6については 前の定義に システム(A,B,C)の伝達関数G(ｓ)は G(ｓ)＝C(sI-A)^(-1)B= C adj(sI-A)B/det(sI-A) と表せるから s=pが伝達関数G(s)の極なら、s=pがシステム(A,B,C)の極である、 とあるのですが、よく意味が解りませんでした。関係がなかったらすみません。 どなたかわかる方がいましたら、一問でも構いませんので 具体的な解き方も含めて教えてください。 宜しくお願いします。
- 締切済み
- 数学・算数
- 非線形計画法 主-双対問題
次のような制約付き最小化問題を考えています。 目的関数は非線形です。 min x1^2+x2^2 s.t. -x1-x2+4<=0 x1>=0 x2>=0 この問題の場合最適解は(x1,x2)=(2,2)であり、その時の目的関数値は8となります。 次に次式のような双対問題を考えます。 g(x)=-x1-x2+4とおき 双対関数 φ(u)=inf{x1^2+x2^2+u*(-x1-x2+4) : x1>=0 , x2>=0} =inf{x1^2-u*x1 : x1>=0}+inf{x2-2-u*x2 : x2>=0}+4*u 上記においてもしu>=0であれば、x1=x2=(u/2). （なぜなら、x1^2-u*x1をx1で微分するとx1=u/2となる。） u<0であるならばx1=x2-0であることに注目しますと。 φ(u)=-(1/2)*u^2+4*u for u>=0 =4u for u<0 となります． 双対関数がu>0の場合は最大がu=4であることに注目すると、その時の目的関数は8であり、主問題と双対問題の最適な目的関数値は一緒となります。 次に主問題を次のように制約を増やした最小化問題を考えます。 min x1^2+x2^2 s.t. -x1-x2+4<=0 -2*x1-3*x2<=0 x1>=0 x2>=0 これの最適解は上記の問題と同じにならないといけないのですが、 例えば、ラグランジュ関数F(x1,x2,λ1,λ2)を次のようにおき各変数で偏微分して最適解を求めると（λ：ラグランジュ乗数）、 F(x1,x2,λ1,λ2)=x1^2+x2^2+λ1*(-x1-x2+4)+λ2*(-2*x1-3*x2) 最適解はx1=12, x2=-8であり、その時の目的関数は208となり、前問と異なった解が得られました。 この原因は明確であり、ラグランジュ関数の中の各制約式が、偏微分して解を得ることで不等式制約ではなく等式制約とみなされたためです。 偏微分して解を求めなければいいのですが、どうしても偏微分でかいを求めたいために、、前門で示した双対問題を導入しましたが、結果は双対問題のほうでも偏微分するので一緒でした。 しかし、双対問題で得られた解。つまりuは主問題のλに相当し、KKT条件より必ず正である必要があるので、双対問題を解き、uが負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり２番目の問題を前問に置き換える。 っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。 これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。
- 締切済み
- 数学・算数
- 線形計画法の問題です
線形計画法の問題です 問題 ・原料PとQから3種類の製品A、B、Cを生産している。 ・製品Aを生産するのに、原料Pを1トン、原料Qを2トン必要 ・製品Bを生産するのに、原料Pを1トン、原料Qを3トン必要 ・製品Cを生産するのに、原料Pを2トン、原料Qを4トン必要 ・原料Pの使用可能量は10トン、原料Qの使用可能量は28トン ・製品A、B、Cの1トン当たりの利益は、30万円、20万円、４０万円 ・市場調査の結果、製品Aの需要量は、製品Bの需要量を2トンより多く上回ることはない 問1．利益を最大化する問題を線形計画問題として定式化せよ 問2．最大利益とその時の各製品の生産量 問3．原料Pの最大使用可能量が1トン減った場合、最大利益がどのように変化するか 問4．原料Qの最大使用可能量が1トン減った場合、最大利益がどのように変化するか 答１．目的関数 30x1+20x2+40x3 → MAX 制約条件 x1+x2+2x3<=10 2x1+3x2+4x3<=28 答2．最大利益 300万円 製品A 10トン 製品B 0トン 製品C 0トン 答3．最大利益は-30万円 答４．最大利益は変化しない となってしまいます。 たぶん、『・市場調査の結果・・・』を制約式に入れていないため、変な答えになっていると思います。 どなたか、模範解答を教えてください。
- ベストアンサー
- 数学・算数
- 線形写像と線形変換
線形写像と線形変換 V , W をK上のベクトル空間とする。このときベクトル空間Vからベクトル空間Wへの写像fが、 Vの任意の要素x,yに対してf(x+y)=f(x)+f(y),f(kx)=kf(x)を満たすとき、fをVからWへの線形写像と言う。 これが線形写像の定義です。 別の記載では、R^n,R^mをk上のベクトル空間とする。このときベクトル空間R^n からベクトル空間R^m への写像f がR^nの任意の要素x,yに対して f(x+y)=f(x)+f(y),f(kx)=kf(x)を満たすとき、fを R^n からR^m への線形写像という。 ここで、テキストにはfがVからV自身への線形写像である時fを線形変換と呼ぶと記載されているのですが、 「VからV自身への線形写像」のイメージがあまりつきません・・・ 次元が同じ場合であれば線形変換？と思ったのですが間違いでしょうか？ よろしくお願い致します。
- ベストアンサー
- 数学・算数
- 線形代数の問題です。
線形代数の問題です。 1.U,U'がそれぞれK上のn次元ベクトル空間とする。このとき線形写像f:U→U'が単射であることと全射であることが同値であることを証明せよ。 2. 行列Aの固有値をλ1,λ2,…λnとしたとき、 行列A^2の固有値は、Aの固有値をそれぞれ２乗したもの以外には存在しない。これは正しいか 3.Aのすべての成分が正でかつ行列式が正なら、Aの逆行列の成分もすべて正であることを示せ。 以上です。よろしくお願いします。
- 締切済み
- 数学・算数
- ベクトル空間の問題のアドバイスをお願いします _ _
以下の問題についてアドバイスいただけないでしょうか。 特に(aa^T + bb^T)というのが何を表すのかよく分からないです。。 3次元実空間における線形独立な2つの非零ベクトルをa, b∈R^3とし、a, bと直交する非零ベクトルをc∈R^3とする。 このとき、線形写像、 f : x∈R^3 → (aa^T + bb^T)x∈R^3 の像及び核を求めよ。（^Tは転置です。)
- ベストアンサー
- 数学・算数
- x1=(1,1,1),x2=(1,1,-1),x3=(1,-1,-1)をC^3の基底,{y1,y2,y3}がその双対基底でx=(0,1,0)の時,y1(x),y
[問] ベクトルx1=(1,1,1),x2=(1,1,-1),x3=(1,-1,-1)をC^3の基底とする。 {y1,y2,y3}がその双対基底でx=(0,1,0)の時、 y1(x),y2(x),y3(x)を求めよ。 という問題の解き方をお教え下さい。 双対基底とは {f;fはF線形空間VからFへの線形写像} という集合(これをV*と置く)において、 V(dimV=nとする)の一組基底を{v1,v2,…,vn}とすると fi(vj)=δij(:クロネッカーのデルタ)で定めるV*の部分集合 {f1,f2,…,fn}はV*の基底となる。これを{v1,v2,…,vn}の双対基底と呼ぶ。 まず、 C^3の次元は6(C^3の基底は(1,0,0),(0,1,0),(0,0,1),(i,0,0),(0,i,0),(0,0,i)) だと思うので上記のx1,x2,x3は基底として不足してると思うのです(もう3ベクトル必要?)。 うーん、どのようにしたらいいのでしょうか?
- ベストアンサー
- 数学・算数
補足
1) 2)はできるけど、三番目を聞きたい、書くのは忘れた