Matematika ∩ programozás

Az optimalizálás messze az egyik leggazdagabb módszer a számítástechnika és a matematika való való alkalmazására. Mindenki optimalizálni akar valamit: a vállalatok maximalizálni akarják a nyereséget, a gyárak maximalizálni a hatékonyságot, a befektetők minimalizálni a kockázatot, a lista csak folytatódik. Az optimalizálás matematikai eszközei szintén a leggazdagabb matematikai technikák. Ezek egy egész iparág alapkövét képezik, amelyet operációs kutatásnak neveznek, és az ezen a területen elért eredmények a szó szoros értelmében megváltoztatják a világot.

A matematikai mezőt kombinatorikus optimalizálásnak hívják, és az elnevezés abból a célból származik, hogy az optimális megoldásokat hatékonyabban kell megtalálni, mint a minden lehetőségre kiterjedő keresést. Ez a bejegyzés bemutatja a kombinatorikus optimalizálás egyik legfontosabb problémáját, amelyet lineáris programnak nevezünk. Még jobb, tudjuk, hogyan lehet hatékonyan megoldani a lineáris programokat, ezért a jövőben írunk egy olyan programot, amely a legkedvezőbb étrendet számolja ki, miközben megfelel az ajánlott egészségügyi előírásoknak.

Egy adott lineáris program általánosítása

Az optimalizálási problémák többségének két része van: egy célfüggvény, az a dolog, amelyet maximalizálni vagy minimalizálni akarunk, és korlátok, szabályok, amelyeket be kell tartanunk, hogy érvényes megoldást kapjunk. Egyszerű példaként érdemes minimalizálnia az adófizetésre fordított idő mennyiségét (célfüggvény), de biztosan nem tölthet rájuk negatív időt (korlát).

A következő bonyolultabb példa ennek a bejegyzésnek a középpontja. A legtöbb ember minimalizálni akarja az élelmiszerre fordított pénz mennyiségét. Ugyanakkor meg kell tartani a táplálkozás bizonyos szintjét. A 19-30 éves férfiak számára az Egyesült Államok Nemzeti Egészségügyi Intézete napi 3,7 liter vizet, napi 1000 milligramm kalciumot, napi 90 milligramm C-vitamint stb.

Matematikailag felállíthatjuk ezt a táplálkozási problémát, csak néhány játékváltozó felhasználásával. Tegyük fel, hogy volt lehetőségünk narancs, tej és brokkoli kombinációjának megvásárlására. Néhány durva becslés [1] az élelmiszerek következő tartalmát/költségeit tartalmazza. 0,272 USD-ért 100 gramm narancsot kaphat, amely összesen 53,2 mg kalciumot, 40 mg C-vitamint és 87 g vizet tartalmaz. 0,100 USD-ért 100 gramm teljes tej kapható, amely 276mg kalciumot, 0mg C-vitamint és 87g vizet tartalmaz. Végül 0,381 USD-ért 100 gramm brokkolit kaphat, amely 47 mg kalciumot, 89,2 mg C-vitamint és 91 g vizet tartalmaz. Az alábbi táblázat összefoglalja ezeket az információkat:

Néhány megfigyelés: a brokkoli drágább, de mindhárom tápanyagból a legtöbbet kapja, a teljes tejben nincs C-vitamin, de rengeteg kalciumot kap igazán olcsón, a narancs pedig valahol a kettő között van. Tehát valószínűleg csiszolhatja a mennyiségeket, és kitalálhatja, mi a legolcsóbb egészséges étrend. A probléma az, ami akkor történik, amikor több száz vagy ezer élelmiszer és több tíz tápanyag-ajánlás kerül beépítésre. Ez az egyszerű példa csak arra szolgál, hogy segítsen felépíteni egy szép formaságot.

Tehát folytassuk ezt. Ha a megvásárolni kívánt 100g-os brokkoli egységek számával, a tej mennyiségével és a narancs mennyiségével jelöljük, akkor az élelmiszer napi költségét felírhatjuk

Annak érdekében, hogy kompaktak legyünk (és ismét az általános lineáris programozási megfogalmazás felé építve), az árinformációkat egyetlen költségvektorba vonhatjuk ki, és a változókat vektorként is megírhatjuk. A változókon implicit módon rögzítünk egy sorrendet, amely az egész probléma során fennmarad, de a sorrend megválasztása nem számít. Most a költségfüggvény csak a költségvektor és a változó vektor belső szorzata (ponttermék). Valamilyen oknál fogva sokan szeretik ezt úgy írni, ahol a mátrix átültetését jelöli, és mi ezt elképzeljük, és nagyságrendű mátrixok. Ragaszkodom a belső termék zárójelének használatához.

Most minden egyes élelmiszer-típushoz kapunk minden tápanyagból egy meghatározott mennyiséget, és ezen tápanyagok összegének nagyobbnak kell lennie, mint a minimális ajánlás. Például naponta legalább 1000 mg kalciumot szeretnénk, ezért erre van szükségünk. Hasonlóképpen kiírhatunk egy táblázatot a korlátozásokról, ha megnézzük táblázatunk fenti oszlopait.

Ugyanúgy, ahogyan a költségadatokat vektorba vontuk ki, hogy elválasszuk a változóktól, az összes tápanyagadatot mátrixba, az ajánlott minimumokat pedig vektorba vonhatjuk ki. Hagyományosan a betűt használják a minimumok vektorához, de most brokkolihoz használjuk.

És most a korlát az, ahol a „minden koordinátánál nagyobb vagy egyenlő” jelentése. Tehát most felírhatjuk a probléma általánosabb formáját sajátos mátrixainkra és vektorainkra. Vagyis a problémánk az, hogy ezt a korlátozást minimalizáljuk. Ezt gyakran offszet formában írják, hogy szembeállítsák azokat a variációkat, amelyeket egy kicsit látni fogunk:

Általában nincs ok arra, hogy ne legyen „negatív” mennyisége egy változónak. Ebben a problémában nem lehet negatív brokkolit vásárolni, ezért hozzáadjuk a korlátozásokat, hogy a változók nem negatívak legyenek. Végső formánk tehát

Általánosságban elmondható, hogy ha van mátrixa, „minimum” vektora és költségvektora, akkor annak a problémának a felkutatását, amely minimalizálja a költségfüggvényt, miközben megfelel a korlátoknak, lineáris programozási problémának vagy egyszerűen lineáris programnak nevezzük.

Az olvasó égető kíváncsiságának kielégítésére a kalcium/C-vitamin problémánkra nagyjából megoldást találunk. Vagyis kb. 100 g brokkolival és 4,2 kg tejjel kell rendelkeznie (például 4 liter), és a narancsot teljesen kihagyja. A napi költség körülbelül 4,53 USD. Ha ez kínosan nagynak tűnik, az azért van, mert olcsóbb módszerek vannak a víz megszerzésére, mint a tej.

100 g brokkoli (kép forrása: 100-grams.blogspot.com)

Kettősség

Most, hogy láttuk az általános lineáris programot és egy aranyos példát, feltehetjük az igazi húsos kérdést: van-e hatékony algoritmus, amely tetszőleges lineáris programokat old meg? Annak ellenére, hogy ezek a problémák mennyire alkalmazhatónak tűnnek, a válasz igen!

De mielőtt leírnánk az algoritmust, többet kell tudnunk a lineáris programokról. Tegyük fel például, hogy van valamilyen vektora, amely kielégíti a kötöttségeit. Hogyan lehet megmondani, hogy optimális-e? Ilyen teszt nélkül nem tudnánk megtudni, mikor kell befejezni az algoritmust. A másik probléma az, hogy a problémát a minimalizálás szempontjából fogalmaztuk meg, de mi a helyzet azokkal a problémákkal, ahol maximalizálni akarjuk a dolgokat? Használhatjuk ugyanazt az algoritmust, amely megtalálja a minimumokat, hogy megtaláljuk a maximumokat is?

Mindkét problémára szépen válaszol a kettősség elmélete. A matematikában általában az a legjobb módja annak, hogy megértsük, mit értenek az emberek a „kettősség” alatt, hogy egy matematikai objektum egyedileg meghatároz két különböző perspektívát, amelyek mindegyike a maga módján hasznos. És általában a kettősségi tétel hatékony módot kínál arra, hogy az egyik perspektívát a másikba átalakítsa, és a kapott információkat mindkét szempontból összekapcsolja. A kettősség elméletét azért tekintik gyönyörűnek, mert valóban mély betekintést nyújt a számodra fontos matematikai tárgyba.

A lineáris programozásban a kettősség a maximalizálás és a minimalizálás között van. Különösen minden maximalizálási problémának egyedi „kettős” minimalizálási problémája van, és fordítva. Az igazán érdekes dolog az, hogy azok a változók, amelyeket egyik formában próbálsz optimalizálni, megfelelnek a másik formában érvényes korlátozásoknak! Így fedezhet fel egy ilyen gyönyörű levelezést. A dolgok megkönnyítése érdekében kis példányszámú kitalált példát fogunk használni.

Tehát megvan ez az optimalizálási probléma

Csak kuncogásért írjuk ki, mi és mi.

Tegyük fel, hogy egy alacsonyabb határt akarunk előállítani a probléma optimális megoldására. Vagyis tudni akarja, hogy egyes számoknál nem lehet kisebb. A korlátok segíthetnek nekünk ilyen alacsonyabb határok levezetésében. Különösen minden változónak nem negatívnak kell lennie, tehát ezt tudjuk, és így a 6 az optimális érték alsó határa. Hasonlóképpen,

és ez még jobb alsó határ, mint a 6. Megpróbálhatnánk ezt a megközelítést általában leírni: keressen meg néhány számot, amelyet az egyes kényszerek kialakításához használunk

Ahhoz, hogy érvényes alsó határ legyen, meg kell győződnünk arról, hogy mindegyikük együtthatója kisebb, mint a célfüggvény együtthatója (vagyis, hogy a végső együttható 4-nél kevesebb legyen). A lehető legalacsonyabb alsó határ elérése érdekében maximalizálni akarjuk, hogy mekkora lenne az egyenlőtlenség jobb oldali mérete:. Ha kiírja ezeket az egyenleteket és a korlátozásokat, akkor az „alsó határú” problémánkat így írjuk

És nem tudnád, a korlátokat biztosító mátrix, valamint a vektorok és a váltott helyek vannak.

Ez nem véletlen. Valamennyi lineáris program átalakítható ilyen módon, és hasznos gyakorlat lenne az olvasó számára, ha a fenti maximalizálási problémát ugyanazzal a technikával visszaváltaná minimalizálási problémává (a korlátok lineáris kombinációinak kiszámítása a felső határok létrehozása érdekében). Meg fog lepődni, amikor visszatér az eredeti minimalizálási problémához! Ez része annak, ami „kettősséggé” teszi, mert a kettős kettője ismét az eredeti dolog. Gyakran, amikor kijavítjuk az „eredeti” problémát, elsődleges formának hívjuk, hogy megkülönböztessük a kettős formától. Általában az elsődleges probléma az, amelyet könnyen lehet értelmezni.

(Megjegyzés: mivel egyelőre elkészültünk a brokkolival, a korábban használt kényszervektort fogjuk jelölni.)

Most mondjuk, hogy egy lineáris program adatait kapja meg a minimalizáláshoz, vagyis a probléma vektorait és mátrixát, „minimalizálja a témát”. Készíthetünk egy általános meghatározást: a kettős lineáris program a maximalizálási probléma „maximalizálja az alárendeltséget”. Itt van az új változókészlet, a T felső index pedig a mátrix transzpozícióját jelöli. Gyakran írják a kettős korlátozását, amely ismét egyoszlopos mátrixokkal azonosítja a vektorokat, de az átültetés mocsarát értelmetlennek és idegesítőnek találom (miért kell oszlopoknak lennie a dolgoknak?).

Most valóban bebizonyíthatjuk, hogy a kettős objektív függvénye megköti az eredeti probléma objektív függvényét. Az elvégzett munkánkból nyilvánvaló, ezért hívják gyenge kettősség tételnek.

Gyenge kettősség tétel: Legyen egy lineáris program adatai elsődleges formában (a minimalizálási probléma), amelynek célfüggvénye. Emlékezzünk vissza arra, hogy a kettős (maximalizálás) probléma objektív funkciója az. Ha megvalósítható megoldások vannak (kielégítik a problémáik korlátjait), akkor

Más szavakkal, a duál maximuma az elsődleges probléma minimumának alsó határa és fordítva. Ezenkívül az egyik megvalósítható megoldás kötöttséget nyújt a másik számára.

Bizonyíték. A bizonyítás kellemesen egyszerű. Csak ellenőrizze a mennyiséget. Az elsődleges és kettős definícióinak korlátai ezt adják meg nekünk

Az egyenlőtlenségek abból a lineáris algebrai tényből következnek, hogy ha az in nem negatív, akkor a termék méretét csak a komponenseinek növelésével növelheti. Ezért van szükségünk a nemnegativitási korlátokra.

Valójában a világ sokkal kellemesebb. Van egy tétel, amely szerint a két optimum egyenlő!

Erős kettősségi tétel: Ha vannak megoldások az elsődleges (minimalizálás) és a kettős (maximalizálás) problémára, akkor a két problémának is vannak optimális megoldásai, és két jelölt megoldás akkor és csak akkor optimális, ha azonos objektív értékeket produkál .

Ennek a tételnek a bizonyítéka kissé összevissza, mint a gyenge kettősségi tétel, és a legfontosabb technika a Farkas és annak variációinak lemma. A teljes igazolást lásd a megjegyzések második felében. A jó dolog az, hogy ez a tétel módot ad arra, hogy megmondjuk, elkészül-e egy algoritmus a lineáris programok megoldására: tartson fenn egy pár megvalósítható megoldást az elsődleges és kettős problémákra, javítsa őket valamilyen szabály szerint, és álljon meg, amikor a két megoldás egyenlő objektív értékek. A nehéz rész tehát egy elvi és garantált módszer megtalálása az adott megoldáspár fejlesztésére.

Másrészt az erős kettősség-tételt bebizonyíthatja egy bizonyíthatóan véget érő algoritmus feltalálásával is. A következő bejegyzésben látni fogunk egy ilyen algoritmust, amelyet szimplex algoritmusnak nevezünk. Sneak peek: nagyon hasonlít a Gauss-eliminációhoz. Ezután az algoritmust (vagy ennek megfelelő iparági változatot) egy sokkal nagyobb táplálkozási probléma megoldására használjuk.

Valójában egy kicsit jobban teljesíthet, mint az erős kettősség-tétel, abból a szempontból, hogy egy lineáris programozási algoritmus leállási feltételével áll elő. Megfigyelheti, hogy az optimális megoldás további korlátozásokat von maga után az elsődleges és a kettős probléma kapcsolatában. Különösen ezt hívják komplementer lazaságfeltételeknek, és lényegében azt mondják, hogy ha az elsődleges optimális megoldás pozitív változóval rendelkezik, akkor a kettős probléma megfelelő korlátjának szorosnak kell lennie (egyenlőség), hogy optimális megoldást nyújtson a dupla. A fogamzásgátló azt mondja, hogy ha valamilyen kényszer laza vagy szigorú egyenlőtlenség, akkor vagy a megfelelő változó nulla, vagy pedig a megoldás nem optimális. Formálisabban,

Tétel (kiegészítő lazaságfeltételek): Legyen a lineáris program elsődleges formájának adatai, „minimalizálja a témát”. Akkor az optimális megoldások az elsődleges és kettős problémákra, ha vannak ilyenek, csak akkor, ha a következő feltételek mindegyike fennáll.

mindkettő kivitelezhető az adott problémájukra.
Amikor 0 "title =" x ^ * _ i> 0 "/> a megfelelő korlát egyenlőség.
Amikor a 0 "title =" y ^ * _ j> 0 "/> a megfelelő korlát egyenlőség.

Itt jelöljük a mátrix-harmadik sorával és egy vektor -edik bejegyzésével. A feltétel egy másik módja az angol helyett vektorok használatával

A bizonyítás a kettősségi tételekből következik, és csupán valamilyen vektoralgebra körüli tolást jelent. Lásd ezen megjegyzések 6.2. Szakaszát.

A lineáris programok kiegészítő lazaságát nagyon sokféleképpen lehet értelmezni. Számunkra ez egyszerűen egy algoritmus felmondási feltétele lesz: hatékonyan ellenőrizhetjük ezeket a feltételeket a nem nulla változók tekintetében, és leállíthatjuk, ha mindannyian meg vagyunk elégedve, vagy ha találunk egy változót, amely sérti a lazaság feltételét. Érettebb optimalizálási elemzések során a súlyosabb módon megsértett lazaságfeltételek bizonyítékot szolgáltathatnak arra, hogy a jelölt megoldás hol javítható a legjobban. A kiegészítő lazaságfeltételek értelmezésének bonyolultabb és részletesebb történetét lásd Joel Sobel jegyzeteinek 4. szakaszában.

Végül, mielőtt lezárnánk, meg kell jegyeznünk, hogy geometriai módszerek vannak a lineáris programozás gondolkodására. A fejemben van a preferált vizualizáció, de még nem találtam megfelelő animációt az interneten, amely megismételné. Itt van egy példa két dimenzióban. A korlátok halmaza domború geometriai tartományt határoz meg a síkban

A megszorítások meghatározzák a „megvalósítható megoldások” konvex területét. Kép forrása: Wikipedia.

Most az optimalizálási függvény egyben lineáris függvény is, és ha kimeneti értéket javítunk, ez meghatároz egy vonalat a síkban. Változásként a vonal a normál vektora mentén mozog (vagyis mindezek a rögzített vonalak párhuzamosak). A célfüggvény geometriai optimalizálása érdekében elképzelhetjük, hogy kezdjük a vonallal, és csúsztatjuk a normál vektor mentén abba az irányba, amely a megvalósítható tartományban tartja. Folyamatosan csúsztathatjuk ebbe az irányba, és a függvény maximuma csak az utolsó pillanat, amikor ez a vonal metszi a megvalósítható régiót. Ha egyik megkötés sem párhuzamos az által definiált vonalcsaláddal, akkor ez garantáltan a megvalósítható régió csúcsánál fog bekövetkezni. Ellenkező esetben az utolsó kereszteződés vonalszakaszán bárhol hever egy optima-család.

Magasabb dimenziókban az egyetlen változás az, hogy a vonalak a dimenzió affin alterévé válnak. Ez azt jelenti, hogy három dimenzióban csúsztat síkokat, négy dimenzióban 3 dimenziós hipersíkokat csúsztat, stb. Az utolsó kereszteződés csúcsként vagy „vonalszakaszként” való tényei továbbra is érvényesek. Tehát, amint legközelebb látni fogjuk, a lineáris programozás sikeres algoritmusai a gyakorlatban kihasználják ezt a megfigyelést azáltal, hogy hatékonyan bejárják ennek a konvex régiónak a csúcspontjait. Ezt a következő bejegyzésben sokkal részletesebben láthatjuk.