Matrislerde maksimum carpimi elde etme

0 beğenilme 0 beğenilmeme
55 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.

16, Haziran, 2015 Serbest kategorisinde Sercan (23,213 puan) tarafından  soruldu
16, Haziran, 2015 Sercan tarafından düzenlendi

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.

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.

16, Haziran, 2015 kerem.altun (121 puan) tarafından  cevaplandı

Soruyu duzelttim. Eksik ve hata varmis soruda.

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

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


...