WisFaq!

Schrijf in LP vorm

Hallo, ik heb een vraag over een huiswerkopgave.

De opdracht:
Gegeven m vectoren v1,...,vm Î$\mathbf{R}$ⁿ en m getallen t₁,...,tm Î$\mathbf{R}$. We zoeken een vector y Î$\mathbf{R}$ⁿ zodat

|vi^Ty-ti| $\le$ D voor i = 1,...,m met D Î$\mathbf{R}$ zo klein mogelijk.

Dit moet als LP probleem worden geschreven in de vorm
min c^Tx
odv Ax$\le$b met x Î $\mathbf{R}$ⁿ

Mijn idee was dat |vi^Ty-ti| zo klein mogelijk is voor D=0 en dat er altijd wel een y bestaat zodat dit geldt voor vi en ti. Zo kom ik tot

min vi^ty-ti
odv vi^ty$\le$ti 'i=1,...,m
y Î$\mathbf{R}$ⁿ

Mijn vraag is nu of ik er van uit mag gaan of zo'n vector y Î Rⁿ altijd bestaat.

Alvast bedankt.

Eline
27-9-2015

Antwoord

Als $m$ groter is dan $n$ dan is zo'n $y$ in het algemeen niet te vinden omdat een lineaire afbeelding van $\mathbb{R}^n$ naar $\mathbb{R}^m$ dan niet surjectief is. Als $m\le n$ dan hangt het een beetje van de $v_i$ af: als die lineair onafhankelijk zijn dan lukt het altijd, als niet dan lukt het weer niet altijd.`

kphart
27-9-2015