A féreg kanonikus formája online

Az LPP kanonikus alakja lineáris programozási probléma az ax = b formában, ahol a a koefficiens mátrix, és b a constraint vektor.

Utasításokat. Válassza ki a változók számát és a sorok számát (a korlátozások számát). A kapott megoldást Word fájlba menti.

A ZLP matematikai modelljét alapvetőnek nevezik. ha a korlátok egyenlet formájában vannak jelen, azzal a feltétellel, hogy a változók nem negatívak.

A matematikai modell kanonikus. ha a kényszer rendszert m lineárisan független egyenletek (rendszer r = m) sorrendjében ábrázolják, akkor egyetlen rendszer alapul szolgál. szabad változók vannak definiálva, és az objektív függvény szabad változók formájában fejeződik ki. Az egyenletek jobb oldala nem negatív (bi ≥ 0).

Azok a változók, amelyek egy együtthatójú rendszer egyik egyenletébe lépnek, és amelyek más egyenletekben hiányoznak, alapszintű ismeretlenek. és minden más szabad.

A rendszer megoldását alapvető megoldásnak hívják. ha a benne lévő szabad változók 0, és ennek a formája:
Xbas = (0, 0; b1 ..., bm), f (Xba3) = c0

Az alapoldat a rendszer oldatainak sarokpontja; meghatározza a modell döntés poligon csúcsát. Az ilyen megoldások közül az az a tény, hogy az objektív funkció optimális értéket vesz fel.

Egy bázikus megoldást támogató megoldásnak neveznek, ha elfogadható, azaz. a rendszer egyenleteinek (vagy egyenlőtlenségeinek) mindegyik jobb oldala pozitív bi ≥ 0.

A kanonikus modell kompakt formája a következőképpen alakul:
AX = b
X ≥ 0
Z = CX (max)

Elfogadható megoldás, az elfogadható megoldások területe, a lineáris programozási probléma optimális megoldása.
Definíció 1. Az LPA korlátozó rendszert kielégítő X vektort, beleértve a nem-negativitási feltételeket, ha van ilyen, az LPA elfogadható megoldásának nevezzük.
Fogalommeghatározás 2. Az elfogadható megoldások gyűjteménye az elfogadható megoldások (ODT) 3L területét képezi.
Meghatározás 3. Az optimális megoldás egy megvalósítható megoldás, amelyre a célfüggvény eléri a maximális (vagy minimális) értéket.

Példa: 1. A következő LP probléma csökkenthető a kanonikus alakra: F (X) = 5x1 + 3x2 → max korlátok között:
2x1 + 3x2 ≤20
3x1 + x2 ≤15
4x1 ≤16
3x2 ≤12
A modell szabványos formában készült. Lássuk be a nem negatív változók x3 értékét. x4. x5. x6. amelyet az egyenlőtlenségi korlátok bal oldalán adunk hozzá. Az objektív függvényben minden további változót bevezetünk a nullával egyenlő koefficiensekkel:
A jelentés első egyenlőtlensége (≤) bemutatjuk az x3 alapváltozót. A jelentés második egyenlőtlensége (≤) bemutatjuk az x4 alapváltozót. A harmadik egyenlőtlenségben bemutatjuk az x5 alapváltozót. A 4. egyenlőtlenségben az x6 alapváltozót. Megkapjuk a modell kanonikus formáját:
2x1 + 3x2 + 1x3 + 0x4 + 0x5 + 0x6 = 20
3x1 + 1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 15
4x1 + 0x2 + 0x3 + 0x4 + 1x5 + 0x6 = 16
0x1 + 3x2 + 0x3 + 0x4 + 0x5 + 1x6 = 12
F (X) = 5x1 + 3x2 + 0x3 + 0x4 + 0x5 + 0x6 → max