Uvod v matematično programiranje

z
Russell C. Walker

 

 

 

 

To besedilo je mehko kritje, spiralno vezana, prilagojena objavljena različica besedila s trdim pokrovom istega imena. To ali njegov predhodnik s trdimi platnicami je bilo že več kot 10 let v programu Business Administration v Carnegie Mellon. To je edino besedilo za modele in metode optimizacije in eno od besedil za multivariatno analizo.

V različici po meri je prišlo do več izboljšav, ki je zdaj v tretji izdaji:

  • Dva odseka o matrični razlagi simbolnega algoritma sta dodana. Ti vodijo do večjega razumevanja algoritma simpleksa in zmožnosti dodajanja spremenljivke linearnemu programu, če je znana optimalna tabela, ne da bi morali ponovno rešiti težavo.
  • Dodan je razdelek o numeričnem iskanju maksimuma.
  • Vaje so bile dodane.
  • Dodana je bila prilagoditev transportnega modela za rešitev problema pretovarjanja.
  • Dodana je bila razprava o alternativnih omejitvah z aplikacijo za zaporedje delovnih mest.
  • Dodatek o uporabi Solverja v Excelu je nadomestil tisti, ki je na grafičnih kalkulatorjih.
  • Napake so bile odpravljene in izboljšanje oblikovanja.
  • Dodatek z rešitvami čudnih težav je končan.
  • Dodatek, ki vsebuje rešitve za celo število oštevilčenih problemov, in študije primerov iz poglavja 10, je zaključen in je na voljo od avtorja kot datoteko s 125 strani pdf.

Besedilo lahko naročite tako, da se obrnete na avtorja: rw1k AT andrew DOT cmu DOT edu ali Amazon.

 

Kazalo vsebine in povzetki poglavja:

Poglavje 1: Uvod v težave
Oddelek 1.1 Uvod str. 1
Oddelek 1.2 Vrste težav, ki jih je treba upoštevati str. 3
Oddelek 1.3 Problemi z vzorcem str. 6
Oddelek 1.4 Grafična rešitev linearnih programov str. 17
Oddelek 1.5 Povzetek in cilji str. 26
V prvem poglavju je podana raziskava vrst problemov, ki jih je treba obravnavati, da bi označili možne aplikacije.
V nekaterih primerih je naveden prispevek rešitve k organizaciji, da se poudari pomen teh spretnosti. Problemi vzorca v tretjem delu kažejo linearno strukturo, ki je vključena v večino modelov, ki jih obravnavamo, in vprašanja, povezana z modelno formulacijo. Zaključni razdelek predstavlja grafični pristop k reševanju dveh spremenljivih linearnih programov.
Poglavje 2: Vektorji in matrike
Oddelek 2.1 Uvod str. 28
Oddelek 2.2 Vektorji str. 29
Oddelek 2.3 Razpon množice vektorjev str. 34
Oddelek 2.4 Matrike str. 38
Oddelek 2.5 Linearna neodvisnost str. 48
Oddelek 2.6 Sistemi enačb str. 54
Oddelek 2.7 Inverzna matrika str. 68
Oddelek 2.8 Povzetek in cilji str. 77
To poglavje razvija matrično algebro, potrebno za obravnavo linearnih problemov.
Razdelek 2.5 je pomemben, saj obstaja linearno neodvisen niz vektorjev, ki ustrezajo vsaki osnovni raztopini v simpleksnem algoritmu. Razprava o linearni neodvisnosti vključuje nekatere principe osnovnega matematičnega sklepanja, ki jih mora razumeti vsak študent, ki je študiral matematiko. Te ideje se nato uporabijo pri dokazovanju predlogov glede linearne neodvisnosti.
Razdelek o sistemih enačb je pomemben, ker so uporabljene vrste vrstic enake tistim, ki so kasneje potrebne v algoritmu simpleksa.
Matrični inverzi so razpravljeni, vendar so potrebni le v vajah oddelka 3.3 in v oddelkih 4.4 in 4.5.
Poglavje 3 Linearno programiranje
Oddelek 3.1 Uvod str. 81
Oddelek 3.2 Spremenljive spremenljivke str. 83
Oddelek 3.3 Simbolni algoritem str. 89
Oddelek 3.4 Osnovne izvedljive rešitve in ekstremne točke str. 101
Oddelek 3.5 Primeri priprave str. 112
Oddelek 3.6 Splošne omejitve in spremenljivke str. 128
Oddelek 3.9 Povzetek in cilji str. 142
Osrednja tema v besedilu je linearno programiranje.
Razdelki 3.2 in 3.3 razvita simpleksni algoritem.
V razdelku 3.4 ugotovimo, da je algoritem simpleksa pravilen.
Razdelek 3.5 obravnava oblikovanje problemov in je posebej pomemben za tiste, ki jih najbolj spodbujajo aplikacije.
Oddelek 3.6 razširja simpleksni algoritem na težave z nestandardnimi omejitvami ali nepodpisanimi spremenljivkami.
Poglavje 4 Duality and Post Optimal Analysis
Oddelek 4.1 Uvod str. 144
Oddelek 4.2 Dvotirni in zmanjśajni problemi str. 1445
Oddelek 4.3 Analiza občutljivosti str. 166
Oddelek 4.4 Nastavitev matrike za simpleksni algoritem str. 186
Oddelek 4.5 Dodajanje spremenljivke str. 192
Oddelek 4.6 Povzetek in cilji str. 198
Razdelek 4.2 obravnava rešitev problemov zmanjševanja z uporabo povezanega problema dvojnega povečanja. Moč linearnega programiranja kot vodstvenega orodja je prikazan v primeru, ki pomaga motivirati razpravo o analizi občutljivosti v oddelku 4.3. Razdelek 4.4 podrobneje obravnava linearno algebro, vključeno v simpleksni algoritem, v oddelku 4.5 pa se uporablja linearna algebra, da se pokaže, da se spremenljivki lahko dodajo v rešeni linearni program, ne da bi ga bilo treba ponovno rešiti.
Poglavje 5 Omrežni modeli
Oddelek 5.1 Uvod str. 200
Oddelek 5.2 Problem transporta str. 206
Oddelek 5.3 Metoda kritične poti str. 231
Oddelek 5.4 Najkrajši modeli poti str. 254
Oddelek 5.5 Minimalna drevesa str. 261
Oddelek 5.6 Največji tok p. 276
Oddelek 5.7 Povzetek in cilji str. 284
Poglavje 5 obravnava šest težav v omrežju: problem prevoza, težave s pretovarjanjem, metoda kritične poti, najkrajša pot problemov, minimalna drevesa in največji pretok. Vzorci modelov v podjetju LINGO in LINDO so na voljo. Razprave o najkrajših poteh in minimalnih vpetih drevesih zahtevajo nekaj uvoda v teorijo grafov. Učinkovitost in pravilnost algoritma sta tudi uvedena in upoštevana pri minimalnih algoritmih za razširjanje dreves.
Poglavje 6 Neomejena ekstrema
Oddelek 6.1 Uvod str. 287
Oddelek 6.2 Iskanje ekstremov str. 288
Oddelek 6.3 Model velikosti serije in konveksnost str. 294
Oddelek 6.4 Lokacija ekstremov v dveh spremenljivkah str. 307
Oddelek 6.5 Približevanje najmanjših kvadratov str. 317
Oddelek 6.6 Primer n-spremenljivke str. 323
Oddelek 6.7 Numerično iskanje str. 329
Oddelek 6.8 Povzetek in cilji str. 337
V tem poglavju razpravljamo o klasičnih tehnikah optimizacije. Potrebno je nekaj znanja o diferencialnem računu. Konveksnost se razpravlja v povezavi s problemom količine gospodarskega reda in upravljanjem zalog. Oddelek je namenjen za namestitev krivulje najmanjših kvadratov. Obstaja razprava o teoriji, na kateri temelji optimizacija, in tudi uvod v uporabo Maple za reševanje problemov optimizacije. Uvedene so tudi numerične tehnike iskanja.
Poglavje 7 Omejeno Extrema
Oddelek 7.1 Uvod str. 339
Oddelek 7.2 Dve spremenljivi problemi str. 346
Oddelek 7.3 Več spremenljivk; več omejitev str. 352
Oddelek 7.4 Težave z omejitvami neenakosti str. 362
Oddelek 7.5 Problem s konveksnim programiranjem str. 372
Oddelek 7.6 Ponovno pregledano linearno programiranje str. 389
Oddelek 7.7 Povzetek in cilji str. 392
To poglavje razširja razpravo, ki se je začela v prejšnjem, na težave, pri katerih je rešitev podvržena omejitvam. Ključna izreka je izrek Karuš-Kuhn-Tuckerja za reševanje konveksnih problemov. Glavne predstavljene aplikacije so zmanjšanje stroškov kartonske škatle, maksimiranje uporabnosti, zmanjšanje stroškov zamenjave opreme in izbiro naložbenega portfelja, da se doseže sprejemljiv donos z minimalnim tveganjem. Poglavje se zaključi s pogledom na linearno programiranje kot poseben primer konveksnega programiranja.
Poglavje 8 Celotno programiranje
Oddelek 8.1 Uvod str. 394
Oddelek 8.2 Problem s hitrostjo str. 397
Oddelek 8.3 Dvostopenjski algoritem str. 406
Oddelek 8.4 Dodajanje omejitve str. 415
Oddelek 8.5 Podružnica in povezana za celo število programov: str. 422
Oddelek 8.6 Modeli programiranja osnovnih celih številk str. 429
Oddelek 8.7 Problem prodajalca potnika str. 452
Oddelek 8.8 Povzetek in cilji str. 466
Algoritmi, povezani s podružnicami, so osrednjega pomena za to temo. Najprej se šteje, da je problem hackback-a predstavljen z vejico in vezano metodo.
Dvojni simpleksni algoritem je nato razpravljal in nato uporabljen za ponovno optimizacijo rešenega problema, potem ko je bila dodana omejitev. Nato je osnova pristopa, ki je povezana z vejstvom in reševanjem integriranih programov.
Nato se razpravlja o različnih modelih celostnega programiranja, poglavje pa se zaključi s pristopom k veščini potujočega prodajalca.
Poglavje 9 Uvod v dinamično programiranje
Oddelek 9.1 Uvod v rekurzijo str. 468
Oddelek 9.2 Najdaljša pot str. 476
Oddelek 9.3 Problem transporta fiksnih stroškov str. 479
Oddelek 9.4 Več primerov str. 484
Oddelek 9.5 Povzetek in cilji str. 491
Težave, za katere je rešitev mogoče doseči z zaporedjem neodvisnih odločitev, se pogosto lahko reši z dinamičnim programiranjem. Dinamično programiranje zahteva uvod v rekurzijo. To vodi do kratkega izleta skozi stolpe Hanoja, številke Fibonacci in binomsko širitev. Razpravljali o aplikacijah so najdaljša težava, ki je podobna določanju najzgodnejših časov v modelu CPM, problemu s fiksnimi stroški in problemu nalaganja tovora. Prav tako se vrnemo k problemu potujočega prodajalca in preiskujemo računalniški izziv tega problema.
Poglavje 10 Študije primerov
Oddelek 10.1 Pripomoček Pripomoček Pripomoček str. 494
Oddelek 10.2 Možnost prodaje pohištva str. 501
Oddelek 10.3 Garderobne omare za zgradbo str. 502
Oddelek 10.4 Kmetija McIntire str. 503
Oddelek 10.5 Valji za pijače str. 504
Oddelek 10.6 Knjige na počitnicah str. 506
Oddelek 10.7 V slepo zaupanje str. 508
Oddelek 10.8 Davki Maxovi str. 509
Oddelek 10.9 Oskrba z omrežjem str. 510
Poglavje 10 predstavlja nekaj več odprtih problemov, primernih za daljše naloge in skupinske projekte. Rešitve primerov in predlogov za njihovo uporabo v razredih so na voljo avtorjem v priročniku za rešitve.

Metode, potrebne za njihovo rešitev, so linearno programiranje, celovito programiranje, kritično upravljanje poti in nelinearna optimizacija.

Dodatek Kratek uvod v LINDO in LINGO
Oddelek A.1 LINDO p. 512
Oddelek A.2 LINGO p. 516
Program LINDO je izjemno uporaben pri reševanju linearnih programov, vključno s tistimi z integriranimi omejitvami. Primeri uporabe so predstavljeni skupaj z uporabo osnovnih ukazov.
LINGO je povezan paket, ki omogoča reševanje nelinearnih problemov. Kot jezik modeliranja je LINGO še posebej uporaben za njegovo sposobnost učinkovito izražanja težav s ponavljajočimi se omejitvami.
Dodatek B A Kratek uvod v Maple
Oddelek B.1 Osnove str. 521
Oddelek B, 2 Uporaba paketov str. 525
Simbolična računalniška programska oprema Maple je lahko zelo uporabna, zlasti pri reševanju klasičnih problemov optimizacije, kot so predstavljene v poglavjih 5 in 6, kot tudi pri izračunih matrik, prilagajanju krivulj, reševanju linearnih programov in reševanju mrežnih modelov.
Dodatek C Uporaba programa Excel Solver
Oddelek C.1 Osnovni primer str. 533
Oddelek C.2 Dva primera omrežja str. 539
Oddelek C.3 Dva nelinearna primera str. 543
Preglednica Excel vključuje dodatek Solver, ki je izjemno uporaben pri linearnih težavah z optimizacijo. Zagotavlja se kratek uvod v Solver z nekaj primeri njegove uporabe.
Dodatek D Izbrani odgovori in nasveti str. 546 Tukaj so navedeni odgovori na vse lahke probleme. Rešitve za celo oštevilčene težave so na voljo pri avtorju v datoteki pdf.

Literatura str. 585

Indeks str. 588

 

Izvirni članek: http://www.math.cmu.edu/~rw1k/rw1k_extra/thrdbook.html

Leave a Reply

Your email address will not be published. Required fields are marked *