téglalap-szabály

Angol

Főnév

téglalap-szabály (tsz. téglalap-szabálies)

(informatika) A lineáris egyenletrendszerek megoldásához használt elemi bázistranszformáció és a hozzá kapcsolódó téglalap-szabály magyarázata:

„Téglalap-szabály”

Ez a szabály segít meghatározni azokat az elemeket egy táblázatban (pl. szimplex tábla), amelyek nem esnek egy sorba vagy oszlopba a generáló elemmel (ez a pivot elem).

Téglalap példa:

	v1	v2	v3	v4
e1	b	.	d	.
e2	.	.	.	.
e3	a*	.	c	.

A a* a generáló elem (pivot).
A d a „szemben lévő csúcs”, azaz az új értéket kapó elem.
A b és c szintén a téglalap részei.

Új érték kiszámítása:

A d helyére az új érték:

$d-{\frac {bc}{a}}\quad {\text{vagy}}\quad {\frac {ad-bc}{a}}$

Ez a téglalap-szabály, amit a MODI módszernél és a simplex algoritmus során is alkalmazunk, amikor frissítjük a táblázat elemeit.

Elemi bázistranszformáció képletekkel

	…	${\textstyle x_{v}}$	…	${\textstyle x_{j}}$	…	${\textstyle b}$
${\textstyle e_{u}}$	…	${\textstyle a_{uv}}$	…	${\textstyle a_{uj}}$	…	${\textstyle b_{u}}$
…	…	…	…	…	…	…
${\textstyle e_{i}}$	…	${\textstyle a_{iv}}$ 🔴	…	${\textstyle a*_{ij}}$ ⭐	…	${\textstyle b_{i}}$
…	…	…	…	…	…	…

Jelölések:

🔴 ${\textstyle a_{iv}}$ – az ${\textstyle i}$ -edik sor és ${\textstyle v}$ -edik oszlop eleme, amit frissítünk.
⭐ ${\textstyle a*_{ij}}$ – pivot elem, amely mentén sor/oszlop transzformáció történik.
${\textstyle a_{uv}}$ , ${\textstyle a_{uj}}$ , ${\textstyle b_{u}}$ , ${\textstyle b_{i}}$ – az összes többi érintett elem, amit a képletek szerint frissítünk.

⭐ A pivot elem: ${\textstyle a_{ij}^{*}\neq 0}$

Ez alapján módosulnak az egyes elemek:

Képletek:

🔴 az új pivot sor egy eleme

$a'_{iv}={\frac {a_{iv}}{a_{ij}^{*}}}$
🔵: a többi nem-pivot elem

$a'_{uv}=a_{uv}-{\frac {a_{uj}a_{iv}}{a_{ij}^{*}}}={\frac {a_{uv}a_{ij}^{*}-a_{uj}a_{iv}}{a_{ij}^{*}}}$
🟢: jobb oldali oszlop (bővített együtthatók)

$b'_{u}=b_{u}-{\frac {a_{uj}b_{i}}{a_{ij}^{*}}}={\frac {b_{u}a_{ij}^{*}-a_{uj}b_{i}}{a_{ij}^{*}}},\quad b'_{i}={\frac {b_{i}}{a_{ij}^{*}}}$

Az új táblázatban minden sorban frissülnek az elemek a fenti szabályok alapján.
Az indexek (pl. ${\textstyle x_{j-1},x_{j+1}}$ ) a változók új elrendezését mutatják.

	…	${\textstyle x_{v}}$	…	${\textstyle x_{j-1}}$	${\textstyle x_{j}}$	${\textstyle x_{j+1}}$	…	${\textstyle b}$
${\textstyle e_{u}}$	…	${\textstyle a'_{uv}}$ 🔵	…	${\textstyle a'_{u(j-1)}}$	${\textstyle a'_{uj}}$	${\textstyle a'_{u(j+1)}}$	…	${\textstyle b'_{u}}$ 🟢
…	…	…	…	…	…	…	…	…
${\textstyle x_{j}}$	…	${\textstyle a'_{iv}}$ 🔴	…	${\textstyle a'_{i(j-1)}}$	${\textstyle a'_{ij}}$ ⭐	${\textstyle a'_{i(j+1)}}$	…	${\textstyle b'_{i}}$ 🟢
…	…	…	…	…	…	…	…	…

Jelölések:

🔴 ${\textstyle a'_{i}v}$ – új érték az ${\textstyle i}$ -edik sor és ${\textstyle v}$ -edik oszlopban (piros a dián).
🔵 ${\textstyle a'_{u}v}$ – új érték az ${\textstyle u}$ -edik sor és ${\textstyle v}$ -edik oszlopban (kék a dián).
⭐ ${\textstyle a'_{ij}}$ – pivot elem után egység lesz (azaz 1).
🟢 ${\textstyle b'_{u}}$ , ${\textstyle b'_{i}}$ – új jobb oldali értékek (zöld a dián).