W dniu 2012-09-25 22:11, bartekltg pisze:

Trochę poprawiłem czytelność.

Zajmujemy się najpierw zmodyfikowanym problemem,
potem pokażemy, że to dokładnie to samo.


Rozwiązujemy następujące zadnienie zmodyfikowane:
[programowanie liniowe]


x*z1 > = 1
x*z2 > = 1
x*z3 > = 1
...
x*zn > = 1

z minimalizowaną funkcją celu sum(x)
(czy jak kto woli x*[1,1,....1] )

Za standardowym warunkiem x_i > 0
****

Rozwiązaniem jest jakiś x1.

Oznaczmy b = 1/sum(x1)



Twierdzimy, że rozwiązaniem oryginalnego problemu jest
wtedy x2 = x1*b = x1 / (sum(x1)) - ten sam wektor
znormalizowany do interesującej nas (hiper)płaszczyzny.


Dlaczego to jest to samo?

sum (x2_i) = 1 // zgadza się z tym, co ma być

x*z1 > = b
x*z2 > = b
x*z3 > = b
...
x*zn > = b

Czyli min (x*z1, ..., x*zn) >=b.
[skądinąd wiemy, ze co najmniej jedną nierówność wysyca]

Pozostaje pytanie, czy nie da się lepiej niż b.

Niech x_3 będzie takim lepszym rozwiązaniem oryginalnego
zagadnienia.

sum (x3_i) = 1

x*z1 > = c
x*z2 > = c
x*z3 > = c
...
x*zn > = c

Gdzie c > b.

Wtedy x4 = x3/c spełnia

x*z1 > = 1
x*z2 > = 1
x*z3 > = 1
...
x*zn > = 1

oraz sum (x_4) = 1/c

Ale to to samo, co funkcja celu w zagadnieniu zmodyfikowanym.
a 1/c < 1/b.

Jest to sprzeczne z tym, że x2 jest optymalne dla tego
zmodyfikowanego problemu (prog lin).

Więc x2 = x1 / sum(x1) jest rozwiązaniem oryginalnego problemu.



pzdr
bartekltg