全体100人のうちリンゴ派90人みかん派80いちご派50人のときすべての派閥に入ってる人として考えら

全体100人のうちリンゴ派90人みかん派80いちご派50人のときすべての派閥に入ってる人として考えられる最小の値を求めよ
どうやってときますか？

No.13 回答者： ありものがたり 回答日時： 2025/04/01 08:54

＞ 参考サイトをみたのですがかなり高度な内容でした。

確かにゴチャゴチャはしているのですが、可能解が多面体になることを利用して
その頂点から頂点へ、辺を通って移動しているだけです。

No.3 流の解法は、言ってることはシンプルですが、じゃあ、その式変形を
どうやって思いついたの？ という点に説明のつけようがありません。
No.4 (というか、そのリンク先)の解法は、線型計画問題の一般解法であって、
ヒラメキを要さず、ＰＣのプログラムでも実行できる点に特徴があります。

No.12 回答者： tknakamuri 回答日時： 2025/04/01 08:33

う～ん、よく質問を見ると

無所属0人とは書いてないな。
NO.6でD(無所属)≧0を導入しても結論は動かないけど。
A+B+CがA+B+C+Dに変わるだけ。

No.11 回答者： mtrajcp 回答日時： 2025/04/01 06:19

全=(全体集合)

り=(林檎派の集合)
み=(蜜柑派の集合)
苺=(苺派の集合)
無=(無派の集合)
とすると

|り|+|み|+|苺|-|り∩み|-|り∩苺|-|み∩苺|+|り∩み∩苺|+|無|=|全|

↓両辺に |り∩み|+|り∩苺|+|み∩苺|-(|り|+|み|+|苺|)-|無| を加えると

|り∩み∩苺|=|り∩み|+|り∩苺|+|み∩苺|+|全|-(|り|+|み|+|苺|)-|無|…①
----------------
|り∪み|=|り|+|み|-|り∩み|

↓|り∪み∪苺|≧|り∪み|だから

|り∪み∪苺|≧|り|+|み|-|り∩み|

↓|り∪み∪苺|=|全|-|無|だから

|全|-|無|≧|り|+|み|-|り∩み|

↓両辺に|り∩み|+|無|を加えると

|り∩み|+|全|≧|り|+|み|+|無|…②
----------------
|り∪苺|=|り|+|苺|-|り∩苺|

↓|り∪み∪苺|≧|り∪苺|だから

|り∪み∪苺|≧|り|+|苺|-|り∩苺|

↓|り∪み∪苺|=|全|-|無|だから

|全|-|無|≧|り|+|苺|-|り∩苺|

↓両辺に|り∩苺|+|無|を加えると

|り∩苺|+|全|≧|り|+|苺|+|無|…③
----------------
|み∪苺|=|み|+|苺|-|み∩苺|

↓|り∪み∪苺|≧|み∪苺|だから

|り∪み∪苺|≧|み|+|苺|-|み∩苺|

↓|り∪み∪苺|=|全|-|無|だから

|全|-|無|≧|み|+|苺|-|み∩苺|

↓両辺に|み∩苺|+|無|を加えると

|み∩苺|+|全|≧|み|+|苺|+|無|…④
------------------
↓②③④を加えると

|り∩み|+|り∩苺|+|み∩苺|+3|全|≧2|り|+2|み|+2|苺|+3|無|

↓両辺に-2|全|-|り|-|み|-|苺|-|無|を加えると

|り∩み|+|り∩苺|+|み∩苺|+|全|-(|り|+|み|+|苺|)-|無|≧|り|+|み|+|苺|+2|無|-2|全|

↓①とこれから

|り∩み∩苺|≧|り|+|み|+|苺|+2|無|-2|全|

↓|全|=100,|り|=90,|み|=80,|苺|=50だから

|り∩み∩苺|≧90+80+50+2|無|-200=2|無|+20

↓2|無|+20≧20だから

|り∩み∩苺|≧20

これと図から
すべての派閥に入ってる人として考えられる最小の値は

20

No.10 回答者： ありものがたり 回答日時： 2025/03/31 14:35

＞ (x²+y²)⁴=x²-y² かつ x,y>0 のとき x+y の最大最小といわれたらどうときますか？

その問題なら、 x+y=u, x-y=v とでも置いて (x²+y²)⁴=x²-y² を u,v の式に書き換え、
u, v の軌跡を求めて u の最大最小を考えるでしょうね。

No.4 で話した線型計画法は、
条件式も目的関数も一次式である場合の一般解法です。
No.8 に、そう書いたでしょう？

No.9 回答者： ありものがたり 回答日時： 2025/03/31 13:57

＞ 他の問題への応用ききますか？

いくつかの変数があって、変数間にいくつかの一次方程式と一次不等式がある
という条件下に、その変数たちの一次関数の最大値最小値を求める問題に
一般的に使える解法です。線型計画法と呼ばれています。
言われたとおりの手順で作業するだけなので、コンピュータに計算させることが
多いですね。変数の個数が多くなると、手作業ではたいへんなので。

この回答へのお礼

まだよく理解できないです。たとえば以下の問題ならどうときますか？
(x²+y²)⁴=x²-y²かつx,y＞0のときx+yの最小最小といわれたらどうときますか？

お礼日時：2025/03/31 14:15

No.8 回答者： ありものがたり 回答日時： 2025/03/31 13:39

みただけで答えのわかる解答というは、無理なのでは？

No.3 のようにベン図を描いても、
3派共通に属する人が 20人であるような状況(のひとつ)
を図示しているだけで、それが最小値であるという情報は
図に含まれません。

この問題は、No.4 No.6 が書いているように、
8個の変数(各分派の人数)が 4本の等式と 8本の不等式を
満たしているという条件下で、そのうちの 1個の変数の
最小値を求めるものです。
等式のほうを使って何個かの変数(4個)を消去しても、
条件を満たす変数の値の組は 4次元の領域になります。
その中の、ひとつの座標の最小値を求めようというわけです。
4次元のグラフ用紙が無いと、図は描けません。

数式を使って共通部分の人数が ≧20 を満たすことを示し、
次に、実際に =20 となる例があることを挙げる方法が
普通かなと思います。

No.4 で紹介したシンプレックス法は、それとは逆に
実際に取り得る値の中でより小さい値へと改訂してゆき、
最後に最小値であることを確認して終わるというスタイルです。
やり方を知っていれば、ほぼ一本道で答えが得られます。

この回答へのお礼

参考サイトをみたのですがかなり高度な内容でした。他の問題への応用ききますか？それなら何とかして理解しようとおもうのですが、、

お礼日時：2025/03/31 13:47

No.7 回答者： kairou 回答日時： 2025/03/30 21:10

＞みただけで答えのわかる解答が気になります

No2、 No5 です。
「みただけで答えが 分かる」では無いですよ。
「見ただけで 答えの見当が付く」です。
腕組みをして 問題文を眺めているだけでは 答えは出て来ません。
この問題に限らず 手を動かして やって見ないと 答えは出て来ません。

この様な問題では 問題文の条件を 紙に書いてみることです。
絵では無いですよ。一本の棒でも良いです。
「全体100人」「リンゴ派90人」「みかん派80人」「いちご派50人」
それぞれを 長さの違う棒で 書いてみれば、答えの見当が付く筈です。
勿論 長さは 定規無しで 目分量で充分です。

No.6 回答者： tknakamuri 回答日時： 2025/03/30 19:29

りんごみかん派をa、

りんごいちご派をb、
みかんいちご派をc、
りんごみかんいちご派(全部派)をd
りんご単独派をA、みかん単独派をB、
いちご単独派をC
とすると
a+b-d=90 -A①
a+c-d=80 -B②
b+c-d=50 -C③
a+b+c-2d=100 -A-B-C④

①+②+③
2(a+b+c)-3d=220-A-B-C ⑤
⑤-④×2
d=20+A+B+C
A≧0、B≧0、C≧0だから、d≧20
よって dの最小値は20。

No.5 回答者： kairou 回答日時： 2025/03/30 12:53

＞なぜ50-30なのでしょうか

いちご派は 50人で、100人中 30人は リンゴ派又は みかん派 ですから、
残りの 20人は リンゴ派とみかん派 の両方に入っている筈です。
従って 20人が 全ての派に 入っていることになります。

NO2 で書いたように 図を書いて 考えてみましたか。
NO3 の様に 〇の図でも良いですし、
小学校で習った リボン状の 帯の図でも良いです。
図が書けたら 見ただけで 答えの見当が付く筈です。

この回答へのお礼

みただけで答えのわかる解答が気になります

お礼日時：2025/03/30 20:14

No.4 回答者： ありものがたり 回答日時： 2025/03/30 09:56

派閥が 3つあるので、各人は

どの派閥に入っていてどの派閥には入ってないか
によって 8つの分派に分けられます。
各分派の人数を
リンゴ派に入っていて他の 2つの派閥には入ってない人数 n(リ),
リンゴ派とみかん派に入っていていちご派には入ってない人数 n(リみ)
のように書くことにしましょう。
どこの派閥にも入ってない人数は n(無) とします。

この問題は、
n(無) + n(リ) + n(み) + n(い） + n(リみ) + n(リい) + n(みい) + n(リみい) = 100,
n(リ) + n(リみ) + n(リい) + n(リみい) = 90,
n(み) + n(リみ) + n(みい) + n(リみい) = 80,
n(い） + n(リい) + n(みい) + n(リみい) = 50,
n(無) ≧ 0,
n(リ) ≧ 0,
n(み) ≧ 0,
n(い） ≧ 0,
n(リみ) ≧ 0,
n(リい) ≧ 0,
n(みい) ≧ 0,
n(リみい) ≧ 0.
という条件下に n(リみい) の最小値を求めよ
という話です。

シンプレックス法で解いてみましょう。参考↓
https://www.bunkyo.ac.jp/~nemoto/lecture/or/97/s …
シンプレックス法の慣習にならって、目的変数を z = - n(リみい) として
z を最大化する問題と考えます。

基底変数　z, n(無), n(リ), n(み), n(い）, n(リみ), n(リい), n(みい), n(リみい)　定数項　増加限界
n(リみい)　0,　1,　　1,　　1,　　1,　　1,　　　1,　　　1,　　　1　　100
n(りみ)　　0,　0,　　1,　　0,　　0,　　1,　　　1,　　　0,　　　1　　90
n(りい)　　0,　0,　　0,　　1,　　0,　　1,　　　0,　　　0,　　　1　　80
n(みい)　　0,　0,　　0,　　0,　　1,　　0,　　　1,　　　1,　　　1　　50
z　 　　　1,　0,　　0,　　0,　　0,　　0,　　　0,　　　0,　　　1　　0

初期の基底変数として n(リみい), n(リみ), n(リい), n(みい) をとってみました。
このとき、連立方程式
n(リみ) + n(リい) + n(みい) + n(リみい) = 100,
n(リみ) + n(リい) + n(リみい) = 90,
n(リみ) + n(みい) + n(リみい) = 80,
n(リい) + n(みい) + n(リみい) = 50
の解が n(みい) = 10, n(リい) = 20, n(リみ) = 50, n(リみい) = 20 となって
全て ≧0 なので、この基底は実行可能領域にあります。

連立方程式の容易さから、つい
n(無), n(リ), n(み), n(い） を基底にとりたくなりますが、
そちらの解は n(無)≦0 になってしまうので、駄目です。

さてこの n(みい) = 10, n(リい) = 20, n(リみ) = 50, n(リみい) = 20,
n(無) = n(リ) = n(み) = n(い） = 0 のとき、表より z = -20 です。

次に暫定解の吟味ですが、このとき、非基底変数 n(無), n(リ), n(み), n(い） の
z の行での係数がどれも ≧0 になっている(実際 0)ので、この解は最適解です。
あれ？ 表の更新を 1度も行わずに最適解が見つかってしまいました。幸運ですね。

以上より、 z の最大値は -20。つまり, n(リみい) の最小値は 20 です。