basic feasible solution

Angol

Főnév

basic feasible solution (tsz. basic feasible solutions)

(informatika) A basic feasible solution (BFS), magyarul alap megoldás, a lineáris programozás (LP) egyik kulcsfogalma. Ez a megoldás olyan pont a megengedett (feasible) tartományban, amely az egyenletrendszer egy bázismegoldásának felel meg – vagyis egy lehetséges sarokpontja a megoldási halmaznak.

📘 Lineáris programozási probléma (standard alak)

A BFS értelmezéséhez vegyük a következő LP-formát:

${\text{Maximalizálandó: }}\mathbf {c} ^{\top }\mathbf {x}$

${\text{megkötések: }}A\mathbf {x} =\mathbf {b} ,\quad \mathbf {x} \geq 0$

${\textstyle A}$ : ${\textstyle m\times n}$ mátrix (m egyenlet, n változó)
${\textstyle \mathbf {x} }$ : változók vektora
${\textstyle \mathbf {b} }$ : jobb oldal
${\textstyle \mathbf {c} }$ : célfüggvény együtthatói

🧠 Mi az a basic feasible solution?

📌 Definíció:

Egy basic feasible solution (BFS):

Feasible: teljesíti az egyenletrendszert: ${\textstyle A\mathbf {x} =\mathbf {b} }$ , és ${\textstyle \mathbf {x} \geq 0}$
Basic: a változók közül legfeljebb ${\textstyle m}$ darab nem nulla, és ezek megfelelnek egy független oszlophalmaznak az ${\textstyle A}$ mátrixban (ezeket nevezzük bázisváltozóknak)

🧮 Hogyan keletkezik BFS?

Válasszunk ki m darab független oszlopot az ${\textstyle A}$ mátrixból → ezek egy ${\textstyle m\times m}$ inverzibilis mátrixot alkotnak: ${\textstyle B}$
Oldjuk meg: ${\textstyle B\mathbf {x} _{B}=\mathbf {b} }$
Behelyettesítjük: a kiválasztott változók értéke ${\textstyle \mathbf {x} _{B}}$ , a többi 0
Ha ${\textstyle \mathbf {x} _{B}\geq 0}$ , akkor BFS-t kaptunk

📍 Geometriai értelmezés

A megoldáshalmaz egy konvex poliéder (vagy poliéderes halmaz)
A basic feasible solutions a poliéder csúcspontjai (sarokpontjai)
A Simplex-módszer pont ezek között mozog

📐 Példa

Oldjuk meg a következő LP-t:

${\text{Max }}z=3x_{1}+2x_{2}$

Értelmezés sikertelen (formai hiba): {\displaystyle \text{feltételek:} \\ x_1 + x_2 \leq 4 \\ 2x_1 + x_2 \leq 5 \\ x_1, x_2 \geq 0 }

Tegyük standard alakba slack változókkal:

Értelmezés sikertelen (formai hiba): {\displaystyle x_1 + x_2 + s_1 = 4 \\ 2x_1 + x_2 + s_2 = 5 \\ x_1, x_2, s_1, s_2 \geq 0 }

A mátrix:

$A={\begin{bmatrix}1&1&1&0\\2&1&0&1\\\end{bmatrix}},\quad \mathbf {b} ={\begin{bmatrix}4\\5\end{bmatrix}}$

Válasszuk: bázis = {s₁, s₂}

$B={\begin{bmatrix}1&0\\0&1\\\end{bmatrix}},\quad \mathbf {x} _{B}=\mathbf {b} ={\begin{bmatrix}4\\5\end{bmatrix}}$

A megoldás:

$(x_{1},x_{2},s_{1},s_{2})=(0,0,4,5)\Rightarrow {\text{BFS}}$

📊 A BFS-ek száma

Egy LP-problémának több BFS-e lehet – a Simplex ezek között sarokpontról sarokpontra lép a célfüggvény javítása mentén.

Ha a célfüggvény optimális értéke elérhető, az mindig egy BFS-ben (vagy BFS-ek konvex kombinációjában) lesz.

✅ Összefoglalás

Tulajdonság	BFS jelentése
Megfelelőség	Teljesíti az összes feltételt
Bázis kiválasztása	${\textstyle m}$ lineárisan független oszlop
Számosság	LP-ben több BFS is lehet
Geometriai jelentés	Poliéder csúcspontjai

🧩 TL;DR

A basic feasible solution (BFS) egy lineáris programozási probléma sarokpontja, amely megoldja az egyenletrendszert, nemnegatív, és legfeljebb m változója nem nulla (az ${\textstyle m}$ egyenlet számával egyezően). A Simplex-algoritmus ezek között keres optimális megoldást.

További információk

basic feasible solution - Szótár.net (en-hu)
basic feasible solution - Sztaki (en-hu)
basic feasible solution - Merriam–Webster
basic feasible solution - Cambridge
basic feasible solution - WordNet
basic feasible solution - Яндекс (en-ru)
basic feasible solution - Google (en-hu)
basic feasible solution - Wikidata
basic feasible solution - Wikipédia (angol)