線形計画法のシンプレックス法で、問題を解くために不等式であらわされた制約条件式を、わざわざ余裕変数を用いて等式条件にするのはどうしてですか?

このQ&Aに関連する最新のQ&A

A 回答 (1件)

線形計画法(linear programming)


(1)「A[i,1]x[1] + .... + A[i,N] x[N] ≦b[i]  (i=1,2,...,M)という条件下で 目的関数c' x (=Σ(c[j] xj]))を最大化する」
という問題を、slack またはstubと呼ばれる変数x[N+j](j=1,2,...,M)を追加して、未知数のベクトルxの次元を上げ、
(2)「A[i,1]x[1] + .... + A[i,N] x[N] + x[N+i] = b[i] (i=1,2,...,M)という条件下で c' x を最大化する」に変換するのは、なんでか?という質問ですね。
 (1)の条件式で不等号を等号に置き換えたひとつの方程式 A[i,1]x[1] + .... + A[i,N] x[N] =b[i] の解(一つには決まりません)の集合はN次元空間の一つの超平面を作ります。従って、この超平面上では、(2)の等式のslack変数x[N+i] は0になります。
 この問題の解は(存在するなら)、それは必ず各条件式によって決まるM個の超平面で囲まれた超多面体の頂点のどれかです。(どのjについても < だとすれば、c' xを必ずもっと大きくできる。)そして頂点に於いては、N個の変数がゼロになり、残りが正になる。
 つまり、slack変数を導入すれば、(1)の問題は、「(2)においてx[i] (i=1,2,....,N+M)のうちのどのN個を0にすれば良いか?」という問題に変換される。そして、まずどれか一つの頂点を選び(つまりx[i]のうちのN個を0にしてみて)、その頂点と辺で繋がっている頂点を調べて、目的関数がより大きくなるように、いわば移動していく。これがsimplex法です。
という訳で、答としては:「頂点だけをたどっていくのに便利だから。」
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qそれぞれ同じアルファベットは、同じ数字をあらわし、欄外の数字はその合計をあらわしています。 ?の数字

それぞれ同じアルファベットは、同じ数字をあらわし、欄外の数字はその合計をあらわしています。
?の数字はいくつになるでしょう。
この問題がわからず困ってます。
教えて下さい

Aベストアンサー

B+N+N+V = 52

●真面目に説くと、こつこつ連立方程式。

横に4つ並んだものを、行
縦に4つ並んだものを、列 として書きます。

・1行目 V+V+B+N=60 ・・・①
・4行目 V+V+H+N=66 ・・・②
②-①= H-B=6
したがって、 B=H-6

・2列目 H+H+B+V=40 ・・・③
・2行目 H+H+B+N=32 ・・・④
③-④ = V-N=8
したがって、N=V-8

・1行目に、B=H-6、N=V-8 を代入
V+V+(H-6)+(V-8)=60
3V+H=74

・2列目に、B=H-6 を代入
V+H+(H-6)+H=40
3H+V=46

3H+9V=222
3H+V=46
8V=176
V=22
H=8

N=V-8=14
B=H-6=2

∴ (B,H,N,V)=(2,8,14,22)

●とんちを効かせて解くなら。

Bはアルファベットの順番なら、A,B ということで2番目
Hは、A,B,C,D,E,F,G,H ということで、8番目。
同様に、Nは14番目、Vは22番目。

Q線形計画法とアローダイヤグラムのことを

すいませんが、線形計画法の問題で最大利益と最小コストの求め方
それにアローダイヤグラムの作り方をぜひ教えて頂きたいです。
2年前に試験を受けたのですが、友人たちはもうノートがないし、解き方も
忘れたと言うので、困っています。すぐテストがありますので、教えてください。
数学ダメなものでして。

Aベストアンサー

「アローダイヤグラム」に関しては、以下の参考URLサイトは参考になりますでしょうか?
「日程計画」

さらに参考になるかどうか・・・・???
●http://farm.agri.kagoshima-u.ac.jp/jyugyo/excel2.html
(少し高度な表計算ソフトの使いこなし)
●http://www.ne.jp/asahi/license/ikawa17/test2000sp/2k/20000317kai.html
●http://www.melma.com/mag/89/m00000189/a00000592.html

でも、教科書・参考書(?)に例題が記載されていないのでしょうか・・・?

参考URL:http://www.ogawa.nuee.nagoya-u.ac.jp/~yamazato/kks99/section7-main.html

Q制御:ゲイン余裕と位相余裕

制御理論に関しての質問です。

今、現代制御理論を一通り学び終えた後、古典制御理論を復習しているのですが、位相余裕(を考える動機)というものがよくわかりません。

ゲイン余裕は「あとどれだけゲインをあげられるか」なので、これは納得です。ゲインを上げて速応性を上げたいのだからどれだけあげられるかは確かに知りたいと思うのは自然なので。

一方、位相余裕は「あとどれだけ位相を遅らせられるか」と教科書にあるのですが、これがよくわかりません。位相を遅らせたい、という動機がそもそもよくわかりません。位相を遅らせることによってどんなメリットがあるのか、どういうときに遅らせたいと思うのか、教えて下さい。

Aベストアンサー

再登場です。いろいろと詳しく述べるとめちゃめちゃ長くなるので、必要な部分に関連したことだけ詳しく述べますね。ということで、色々省いちゃってるので、わからなかったらおっしゃってください☆

・最小位相系
安定なシステムで、かつ、不安定な零点をもたないシステムのことを言います。ゲイン線図が全く同じG1(不安定零点なし)とG2(不安定零点あり)という二つの伝達関数があるとします。このとき、ゲイン特性が全く同じでも、不安定零点をもつG2の方が、周波数による位相の推移(変化)が大きいんです。
ということで、不安定零点をもたないシステムを最小位相系と呼んでます。
そして重要なのは、この最小位相系では、「gainからphaseがユニークに決まる」のです(bodeさんが証明してくれてます)。
ゲインが-20[dB/dec]の一定傾き(つまり積分器)ならば、位相は-90[deg]になります。
ゲインの傾きが-40[dB/dec]ならば(1/s^2)、位相は-180[deg]で遅れてしまいます。
ゲインの傾きをa(aは定数。つまり傾き一定)だとしますと、20[dB/dec]=1で、a×(π/2)だけ位相が進むことが導けます。

つまり、
ゲインが負の傾き→位相が遅れる
ゲインが正の傾き→位相が進む
です。

・感度関数
おそらく教科書なんかに、フィードバック系における「制御対象の特性変動による影響」とか「外乱による出力への影響」とか「目標値入力に対する偏差」なんかは書かれているかと思います。
それに関係しているのが感度関数です。感度関数が低ければ、外乱が抑制でき、定常特性にも長け、パラメータ変動にも強くなります。

教科書なんかで上でいったような項目をみてみると、最終的に、一巡伝達関数をLとしますと、1/(1+L)といった関数が導かれているかと思います。これが感度関数(sensitivity function)です。
またこの式から、一巡伝達関数Lの大きさを上げれば、感度関数が小さくなっていくことがわかるかと思います。
前の回答の関係からいうと
低周波域でLの大きさを大きくする→このせいでLのゲインが負に傾いてしまう→位相が遅れる
です。

・相補感度関数
感度関数をS、相補感度関数をTとします。
すると、S+T=1を満足します(つまり、complementaryという意味で"相補"です)。
このTはL/(1+L)という形であらわせます。
よくみると目標値入力rから制御量yまでの伝達関数と一緒ですよね。
また、ノイズをn(フィードバックがかかっているところに入力する)だとすると、y=-Tnなので、この相補感度関数が小さいほど、ノイズの影響を低減することができます。
また、Lを下げれば、Tを下げることができることがわかるかと思います。

・制御系の型
一巡伝達関数Lに含まれている積分器の数がn個あったとします。
すると、これをn型の制御系と呼びます。
例えばL(s)=1/((s+1)s^2)は2型の制御系です。

型によって目標値に対する定常特性が決まります。
目標値rから偏差eまでの伝達関数は、感度関数(1/(1+L))になります。e=Sr=(1/1+L)rですね。
(これにラプラス変換での最終値定理を考えればあきらかですよね。)
理論上、
1型の制御系であれば、定常位置偏差(目標値r(s)=1/sに対する偏差)を0にできますし、
2型であれば、定常速度偏差(r(s)=1/s^2)まで0にできます。
実際は、摩擦などの影響で、偏差は残ってしまうことがあるようです。


・ゲイン交差周波数
これは言葉を知らないだけで、概念は恐らく知ってらっしゃるかと思います。
一巡伝達関数の大きさが1(0[dB])になるときの周波数です。
この周波数での一巡伝達関数の位相をもとに、位相余裕を算出しますよね。
この周波数で、もし一巡伝達関数の位相が進んでしまったら、ナイキストの安定判別法的にマズイです。(一巡伝達関数が-1より左にいっちゃいます)

・ロールオフ
高周波域におけるゲインの傾きのことをroll-off(ロールオフ)とよびます。ノイズは主に高周波域で入ってきます。なので、一巡伝達関数は、高周波域において、ゲインが急速に小さくなっていくのが望ましいんです。ですから、ゲインを負に大きく傾かせます。(先に述べたように、一巡伝達関数がさがれば、相補感度関数がさがり、ノイズの影響を低減できますよね)。
前回の回答の関係からいうと、
高周波域でLの傾きを大きく負にする(ロールオフ特性がよくなり、ノイズ低減)→しかし位相が遅れる
って感じです。


こんな感じでしょうか。。これで前の回答ある程度わかりますか…? 我ながらわかりにくい文章です^^; 何かわからない箇所があればおっしゃってください。

再登場です。いろいろと詳しく述べるとめちゃめちゃ長くなるので、必要な部分に関連したことだけ詳しく述べますね。ということで、色々省いちゃってるので、わからなかったらおっしゃってください☆

・最小位相系
安定なシステムで、かつ、不安定な零点をもたないシステムのことを言います。ゲイン線図が全く同じG1(不安定零点なし)とG2(不安定零点あり)という二つの伝達関数があるとします。このとき、ゲイン特性が全く同じでも、不安定零点をもつG2の方が、周波数による位相の推移(変化)が大きいんです...続きを読む

Qこんだけの文で仮定法あらわせるのですか?????

こんだけの文で仮定法あらわせるのですか?????

Aベストアンサー

再々回答

黒板の場合ですと、 Iwill fly to you . I want to fly to you . 等、英文として普通というか、時制や文法に
間違いがなければ、普通に訳しますが、

I would fly to you . の would は、何ですか。 will なら未来形ですが、would は未来の過去????。

つまり、このwouldの用法は、仮定法でしか現れてこないために、Iwould fly to you .  で、仮定の意味を込め、
あなたの元へ飛んでいければよいのに。(現実としては、できないという意味を含みます。)

必ずしも、if節を伴わないで、仮定法を表す文章があります。少しずつ、覚えましょう。

He read a book. は、read に、s が付いていないため、過去形と判断しますよね。

かなり乱暴ですが、助動詞の過去形が突然出てきたり、Iの後ろが were になっていたら、
仮定法の可能性が大きいとも言えます。

参考までに。

Q線形振動とと非線形振動の違いについて

線形振動とと非線形振動の違いについて教えてください.
具体例をあげてもらえると嬉しいです.

Aベストアンサー

ばねの場合を例に取ることにして,自然長からのずれを x とします.
ばねの伸び縮みによって力のポテンシャルが生じますが,それを U(x) としましょう.
あまり伸び縮みが大きくないときは U(x) がテーラー展開できて
(1)  U(x) = (k/2) x^2 + (A/3) x^3 + ・・・
と書けるでしょう.
x の零次の項がないのはポテンシャルの原点をそういう風に選んだから,
x の1次の項がないのは x=0 が自然長だからです.
線形のばねは(1)で k x^2 だけ考慮したものです.
力 f(x) は
(2)  f(x) = -dU(x)/dx = -kx
で,これが tocoche さんの
力と変位(伸び縮み)の関係が比例すれば線形,
に対応します.

質量mの質点をばねにつけているとしますと,運動方程式は
(3)  m (d^2 x / dt^2) + kx = 0
で,x に関して線形になっています.」
つまり,x1 と x2 が共に微分方程式(3)の解であれば
y = a x1 + b x2 も(3)の解になっています.

一方,(1)で x^3 の項まで取り入れてしまったら,(3)の代わりに
(4)  m (d^2 x / dt^2) + kx + Ax^2= 0
になってしまい,Ax^2 の存在のために線形になりません.
つまり,x1 と x2 が共に微分方程式(3)の解であっても
x1 + x2 はもちろん解になりません.
線形でないので非線形といいます.

> 振幅の大小で線形と非線形に別れるなんて...
振幅が大きい(x が大きい)と,非線形になる理由はもう明らかですね.
x が大きければ(1)で x^2 の項だけとってすましちゃうわけにはいきませんね.

ばねの場合を例に取ることにして,自然長からのずれを x とします.
ばねの伸び縮みによって力のポテンシャルが生じますが,それを U(x) としましょう.
あまり伸び縮みが大きくないときは U(x) がテーラー展開できて
(1)  U(x) = (k/2) x^2 + (A/3) x^3 + ・・・
と書けるでしょう.
x の零次の項がないのはポテンシャルの原点をそういう風に選んだから,
x の1次の項がないのは x=0 が自然長だからです.
線形のばねは(1)で k x^2 だけ考慮したものです.
力 f(x) は
(2)  f(x) = -dU(x)/dx = -kx...続きを読む


人気Q&Aランキング

おすすめ情報