Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
753 kez görüntülendi

Elimizde pozitif tanimli, girdileri tam sayi olan ve hic bir satir ve sutunu tamamen sifir olmayan $n\times n$'lik bir $A$ matrisi olsun. Bunu hangi $x=(x_1,\cdots,x_n) \in \mathbb R^n$ ile carparsak ($xA=y=(y_1,\cdots,y_n)$) tum $i$'ler icin $y_i \leq 1$ sarti ile $\sum \limits_{i=0}^nx_i$ maksimum olur? (ya da daha yuksek bir deger elde ederiz, maksimuma yaklasiriz?)

Soru genel oldugu icin cevaplanmayabilir, fakat bu cevaba ulasmak icin hangi tarz yontemler kullanabiliriz? Eger matris ornegi verilecekse en az $3\times3$'luk bir matris olmasini rica ederim.

Ek olarak: Bence bu deger  $\frac 12$'den kucuk olmali.

Serbest kategorisinde (25.4k puan) tarafından 
tarafından düzenlendi | 753 kez görüntülendi

Mesela A matrisi 3x3 lük bir birim matris olsun. $x=(x_1,x_2,x_3)$ olsun. O zaman $xA=(x_1,x_2,x_3)$ olur. $x_1\leq1$ , $x_2\leq1$ , $x_3\leq1$ . Dolayısıyla $x_1+x_2+x_3\leq3$ oluyor. Başka kısıtlamalar var mı? Neden $\frac{1}{2}$ den küçük olmalı?. Sorunun cevabını ben de merak etmeye başladım.

Baska kisitlama yok yanilmiyorsam. (asal) $p$-yogunluk egimi (epey islemden sonra gosterilebilir) bunun icin bir ust sinir, o da maksimum $\frac{1}{2}$ olur.

isinize yarar mi bilemedim ama soyle bir seyler karaladim
$\langle x , Ay \rangle = \|y\|_2$
$ |\langle x , Ay \rangle | \leq \|x\|_2\|Ay\|_2$

$ \|y\|_2 \leq \|x\|_2\|Ay\|_2$

$ \frac{\|Ay\|_2}{\|y\|_2} \geq \|x\|_2$

$\|A\| \geq \|x\|_2$ (Bu hamleden cok emin degilim)

$\|x\|_1 \leq \sqrt{n} \|x\|_2 \leq \sqrt{n} \|A\| $

$\sum{x_i} $ leri sinirlayamadim ama $\sum{|x_i|}$ ler icin bir ust sinir buldugumu dusunuyorum
Soruyu sorduğum zamanlardaki kafama dönemiyorum şu an ama bence o girdiler de pozitif olmalı.

Ece'nin yorum ile bakınca soruyu iyi sormamış olduğumu düşünüyorum. Türkçem çok kötüymüş. Muhtemelen iyi sorduğumu düşünmüş olmalıyım o zamanlar.

Kerem'in dediği tarzda bir soru sorduğumu düşünüyorum. 
https://en.wikipedia.org/wiki/Linear_programming

1 cevap

0 beğenilme 0 beğenilmeme

Sonuçta aradığınız şey $x_i$'lerin bir lineer kombinasyonu. Bu lineer kombinasyonun bir maksimum değeri yoktur. Ama eğer kısıtlar varsa (ve bu kısıtlar lineer denklemler ya da eşitsizlikler ise), doğrusal programlama yöntemleri ile maksimum değer bulunabilir.

(236 puan) tarafından 

Soruyu duzelttim. Eksik ve hata varmis soruda.

Sanırım aradığınızı burada bulabilirsiniz:

https://en.wikipedia.org/wiki/Linear_programming


20,217 soru
21,750 cevap
73,347 yorum
1,971,769 kullanıcı