opkut,tl&dr

• bólé

• bútor

• szerkesszük meg a megengedett megoldások halmazát

• ábrázoljuk a célfüggvény egy példányát (pl. a c(x)=0 egyenest)

• döntsük el, hogy a fenti egyenes le/felcsúsztatása milyen hatással van az értékére

• keressük meg azt a pontját a megengedett megoldások halmazának melyet "utoljára" metsz a célfüggvény, miközben a jó irányba csúsztatjuk

• lásd: phpsimplex

• a bevezető feladatokban a közös, hogy ilyenek vagy ilyen alakra hozhatók:

\[ \begin{gather*} \rm{a\ döntési-változó\ \ nemnegatívitása}\begin{cases} x \ge 0 \\ \end{cases}\\ \rm{korlátozó\ \ feltételek}\begin{cases} a_{11}x_{1}+\ldots+a_{1,n}x_{n} \le b_{1} \\ ... \\ a_{m1}x_{1}+\ldots+a_{m,n}x_{n} \le b_{m} \\ \end{cases} \\ \hline \rm{célfüggvény}\begin{cases} c_{1}x_{1}+\ldots+c_{n}x_{n} \to \max \\ \end{cases} \end{gather*} \]

• Tehát keressük azt a nemnegatív elemű vektort, amely egyrészt kielégíti az adott lineáris korlátozó feltételeket, másrészt, melynél egy adott lineáris célfüggvény a lehető legnagyobb értéket vesz fel.

• ugyanez mátrixos alakban:

\[ \begin{gather*} x \ge 0 \\ Ax \le b \\ \hline c^{T}x \to \max \end{gather*} \]

• a legtöbbször $m$ és $n$ jelöli a korlátozó feltételek és a változók számát (azaz $A$ egy $m\times n$ mátrix)

• általában valamilyen "homogén" alakra hozzuk a modellünket

  • a fenti az úgynevezett standard maximum feladat, lásd

  • ez meg egy standard minimum feladat:

\[ \begin{gather*} x \ge 0 \\ Ax \ge b \\ \hline c^{T}x \to \min \end{gather*} \]

• ha korlátozó feltételek mindegyike egyenlőség, akkor kanonikus formájunak nevezzük.

\[ \begin{gather*} x \ge 0 \\ Ax = b \\ \hline c^{T}x \to \min \end{gather*} \]

• lásd

• a korlátozó és nemnegtívitási feltételek által meghátorozott halmazt lehetséges megoldások halmazának nevezzük és LMH-val hivatkozunk rá.

• a következő esetek lehetségesek

  • LMH$=\emptyset$

  • a célfüggvény nem korlátos LMH-n

  • pontosan 1 optimum hely van

  • $\infty$ sok optimum hely van

• azért ismerkedünk meg az elemi bázistranszformációval (EBT), mert a szimplex módszer használja

• adott $a_1,\ldots,a_n \in \R^{n}$ bázis és $b,c$ vektorok esetén, a következő kérdések akarjuk megválaszolni:

  • $a_{i}$-t mikor cserélhetjük ki $b$-vel, hogy az új rendszer bázis maradjon?

  • az új rendszerben hogy néz ki $c$ és $a_{i}$ (mik a koordinátái)?

• legyen $b=\sum_k \beta_k a_k$ és $c=\sum_k \gamma_k a_k$

• $a_1,\ldots,a_{i-1},b,\ldots,a_{n}$ pont akkor bázis ha $\beta_i \neq 0$ ezt az számot generáló elemnek nevezzük.

  • ha $\beta_i=0$ akkor függő a rendszer. ha $\beta_i\neq 0$ akkor generátorrendszer, tehát bázis (mivel $n$-elemű)

• fejezzük ki $a_{i}$-t és $c$-t az új bázisban:

\[ a_{i} = \frac{1}{\beta_{i}}b + \sum_{k\neq i} -\frac{\beta_{k}}{\beta_{i}} a_{k} \\ c = \gamma_{i} a_{i} + \sum_{k\neq i} \gamma_{k} a_{k} = \frac{\gamma_{i}}{\beta_{i}}b + \sum_{k\neq i} -\frac{\gamma_{i}\beta_{k}}{\beta_{i}} a_{k}\\ \]

• a fenti szabályok táblázatosan:

az eredeti felállás:

transzformált adatok:

• a szabályok szóban olyan tábla esetén amikor valóban helyet cserélnek a vektorok (a tábla mérete állandó marad és a bázisbeli vektorok nem szerepelnek az oszlopok között)

  • a generáló elem helyén a reciproka

  • a sorábon osztunk a generáló elemmel

  • az oszlopában osztunk a a generáló elem minusz egyszeresével

  • a többi helyen a gyakorlaton említett téglalap szabály használjuk

• vagy konyebben megjegyezhető jelekkel:

  • a helyén: $\square \ \to \ \frac{1}{\square}$

  • a sorában: $\bigcirc \ \to \ \frac{\bigcirc}{\square}$

  • az oszlopában: $\bigcirc \ \to \ -\frac{\bigcirc}{\square}$

  • egyébként (téglalap-szabály): $\bigcirc \ \to \ \bigcirc -\frac{ / \cdot / }{\square}$

• legegyszerűbb az ún. normál feladattal kezdeni:

\[ \begin{gather*} x \ge 0 \\ Ax \le b \ \ b\ge 0 \\ \hline c^{T}x \to \max \end{gather*} \]

• a normál-feladat kiegészítő változók segítségével átalakítható kanonikus alakúvá:

\[ \begin{gather*} \binom{x}{x^{'}} \ge 0 \\ (A,E)\binom{x}{x^{'}} = b \ \ b\ge 0 \\ \hline (c,0,\ldots0)^{T}\binom{x}{x^{'}} \to \max \end{gather*} \]

• az $(A,E)$ mátrix legyen mondjuk $m\times n$-es méretű

• erről az "új" feladatról bebizonyítható, hogy ugyanaz a megoldás-szerkezete mint az eredetinek, azaz

  • az LMH-k egyszerre üres/nemüres halmazok

  • a célfüggvény egyszerre korlátos/nemkorlátos a megfelelő LMH-kon

  • egyszerre van a feladatoknak 1/$\infty$ optimumhelye, melyek megegyeznek.

  • az áttérést a $x \leftrightarrow \binom{x}{x'}$ valósítja meg

• a bevezetett új változóknak megfelelő oszlopvektorok bázist alkotnak ($\R^{m}$-ben), így van egy nem-negatív kezdőmegoldásunk. (a leírtak nemcsak normál-feladatra, hanem olyan esetekben is érvényesek maradnak, amikor a feladat oszlopvektorai közül választhatunk egy bázist, mellyel nemnegatív koordinátákkal a jobboldal előállítható)

• van tehát néhány vektorunk, melyek bázist alkotnak (az indexeik egy B halmazból valók) és néhány külső vektorunk (az indexeik egy N halmazból valók), plusz a $b$ vektor, melyeket táblázatba rendezünk.

• az $x_{i j}$ mennyiségek a bázisra vonatkozó koordináták

• most nézzük meg mi történik, a célfüggvényértékkel ha végrehajtunk egy EBT-t:

\[ z = \sum_{i\in B} x_i c_i = \sum_{i\in B-\{s\}} x_i c_i + x_s c_s \\ z{'} = \sum_{i\in B-\{s\}} x_i{'} c_i + \frac{x_s}{x_{st}} c_t = \sum_{i\in B-\{s\}} \left(x_i - \frac{x_{i t}x_{s}}{x_{s t}} \right) c_i + \frac{x_s}{x_{st}} c_t\\ \implies \\ z{'} = z - \frac{x_s}{x_{s t}}\left( \sum_{i \in B} x_{i t} c_i - c_t \right) = z - \frac{x_s}{x_{s t}}\left( z_t - c_t \right) \]

• az alsó sorba a kezdőmegoldásnál beírjuk a $\Delta_j = z_j - c_j$ mennyiségeket $j \in$N és a célfüggvény aktuális értékét ($z$)

• bebizonyítható, hogy EBT végrehajtásánál a $\Delta_j$-k és a $z$ ugyanazokkal a szabályokkal számolhatók mint amiket a vektorok koordinátáira tanultunk.

1. ALGORITMUS (LOOP)

2. ha minden $\Delta_j \ge 0$ akkor a táblázat optimális megoldást mutat (STOP)

3. ha van olyan $\Delta_j < 0$ amelyre $x_{i j} \le 0$ minden $i$-re (felette nincsen pozitív) akkor nemkorlátos a feladat (STOP)

4. Új táblázat kell a döntéshez:

• bejövő vektor: ahhoz hogy növekedjen a célfüggvény, a negatív $\Delta_j$-k közül választunk: $j = t$

• kimenő vektor: ahhoz hogy a megoldás nemnegatív maradjon a olyan $i$-t választunk, melyre a $\frac{x_{i}}{x_{i t}}$ mennyiség a lehető legkisebb (azaz válasszuk a minimálisat az $\frac{x_{i}}{x_{i t}}$-k közül ( $x_{i t}>0$ ), legyen a minimum-hely mondjuk $i = s$

• csináljuk meg az $a_s \leftrightarrow a_t$ EBT-t és (LOOP)

• bólé

• bútor

• desszert

• forrócsoki

• konzervgyár

• van $M$ raktárunk és $N$ felvevő helyünk és egységnyi árut $c_{ij}$ költséggel szállíthatunk az $i$-ik raktárból a $j$-ik felvevőhelyre

• raktárakban rendre $S_{1},\ldots,S_{M}$ egységnyi áru van

• a felvevőhelyek igénye $F_{1},\ldots,F_{N}$ egységnyi áru

• feltesszük, hogy $\sum S = \sum F$ (kiegyensúlyozott-feladat)

• a feladat minden raktárból minden árut elszállítani, minden felvevőhely minden igényét kielégíteni a legolcsóbban.

• azaz adott egy $C$ mátrix, egy $S$ oszlopvektor és egy $F$ sorvektor:

• to be cont.