Operációkutatás, lineáris programozási feladat?

Ha jól képzelem hogy mi történik:

Addigra az első feladatrész teljesen kész van. Megvan a feladatban kért A', b' és c' is (A*, b, c*).

A második feladatrészt oldja, példát keres.

A (4,0) egy hasraütésszerű x. (Teljesül rá az egyenletrendszer, de ez nem szükséges.)

Ebből úgy csinál x'-t, hogy

: x' := (x^+, x^-)

ahol x^+ az x pozitív része, a pozitív koordináták maradnak, a negatívak meg 0 mind, x^- az x negatív része, a pozitív koordináták vannak kinullázva, a negatívok meg pozitív előjellel szerepelnek. (A megoldásban ezek x' és x", de ez konfliktusban áll a feladat jelölésével, ami helyes, de nem szerencsés.)

A példában

: x = (4,0) szerepel, aminek a pozitív része (4,0), a negatív része (0,0), így a hozzá tartozó x'

: x' = (4,0,0,0).

Vissza irány is csak hasraütésszerű, a (7,3,3,3) egy hasraütésszerű x'.

x'-ből úgy lesz x, hogy az utolsó 2 koordinátát levonod az első kettőből,

: x' = (7,3,3,3) -> (7-3,3-3) = (4,0) = x.

Ez egy klasszikus LP feladat, amelyet a szimplex módszerrel számolunk ki konkrétan. A módszer rendkívül számolásigényes, ezért igazán számítógéppel oldják meg.

Gyanítom, hogy már a feladat megértéssel is probléma van, onnan pedig nehéz folytatni.

Az LP feladat lényege, hogy adott egy sor változó, amelyekre feltételek vannak előírva úgy, hogy végtelen megoldás van. Azonban a változókra van egy további bonyolult feltétel, amely egy optimalizálási feladat. A változókra vonatkozó feltételek Ax≤b alakúak, de az x-re adott egy célfüggvény, amelyet optimalizálni (maximalizálni például) kell, ez a max {c*x} skalár formánan adott.

A szimplex módszer egy tételen alapul, amely szerint egy lineáris egyenletrendszernek akkor és csak akkor van megoldása, ha az A mátrixra bizonyos kikötések érvényesek, amit egyenlőtlenségek formájában adhatunk meg. Ezért az eredeti LP a Gauss módszer kiterjesztésével oldható meg, és vagy nincs megoldása vagy van (és végtelen sok). Gyanítom, a gyakorlati példa ennek egy konkrét számokkal való, 2×3-as mátrixon számolás, itt a választott megoldás (0, 4) valóban az (ezt mutatta be), tehát jó. Az más kérdés, honnan jövünk rá a (0, 4) értékre. Ezt számolja ki a szimplex módszer. Ennek leírása itt nem lehetséges, számos oktató cikk áll rendelkezésre (a tankönyveken kívül). A feladat átlátása azon múlik, megérted-e a feladatot magát.

Egy számolási segédlet magyarázatokkal

[link]