John W. Chinneck
Systems and Computer Engineering
Carleton University
Ottawa, Ontario K1S 5B6
Kanada
Oroginal article:http://www.sce.carleton.ca/faculty/chinneck/po.html
http://www.sce.carleton.ca/faculty/chinneck/po.html
Kapitlen som visas nedan är utkast till kapitel i en introduktionsbok om optimering. Det slutgiltiga målet är att skapa en komplett, men kompakt, inledande enkättext om de viktigaste ämnena inom optimering. Materialet härrör från föreläsningsanteckningarna som används av författaren vid ingenjörskurser vid Carleton University och återspeglar designhänsynen till dessa kurser:
- Eleverna måste ha en solid intuitiv förståelse för hur och varför optimeringsmetoder fungerar. Detta gör det möjligt för dem att känna igen när saker har gått fel och att diagnostisera källan till svårigheten och vidta lämpliga åtgärder. Det tillåter också studenter att se hur metoder kan kombineras eller modifieras för att lösa icke-standardiserade problem.
- Förklaringar och diagram är mer effektiva för att överföra en verklig förståelse än en total beroende av matematik.
- Det bör finnas viss exponering för hur saker görs i praktiken, vilket kan skilja sig väsentligt från hur de vanligtvis görs i läroböcker.
- Målet är att studenter ska kunna känna igen när problem som de stöter på i sina jobb eller i examensarbetet framgångsrikt kan hanteras med optimeringsmetoder. Studenterna ska kunna abstrrahera en användbar formulering av ett problem ur en rörig verklig världsbeskrivning.
Materialet är skrivet på introduktionsnivå och förutsätter inte mer kunskap än gymnasialgebra. De flesta koncept utvecklas från grunden. Jag tänker att detta ska vara en mild introduktion.
Du behöver en Adobe Acrobat-läsare för att läsa filerna. En gratis läsare kan laddas ner från www.adobe.com
Kommentarer och förslag söks aktivt. Kontakta författaren på chinneck@sce.carleton.ca . Detta är ett utkast , så vissa diagram är handritade och det kan finnas stavfel etc. Ytterligare kapitel kommer att läggas till när tiden tillåter. Meddela mig om eventuella korrigeringar som behövs.
Bläddra bland algoritmanimationerna . Dessa ger animerade illustrationer av många av de viktigaste begreppen. Studentutvecklarna av dessa animationer finansierades genom ett IBM-fakultetspris till professor Chinneck. Senaste revision: 28 augusti 2007.
Skriva ut hela volymen? Lägg sedan till främre delen för ett bättre utseende. Senaste revision: 23 juni 2015.
Kapitel 1 Inledning. En introduktion till optimeringsprocessen och en översikt över de viktigaste ämnena som behandlas i kursen. Senaste revision: 12 december 2010.
Kapitel 2: Introduktion till linjär programmering. De grundläggande begreppen linjär programmering och simplexmetoden. Simplex-metoden är det enklaste sättet att ge en nybörjare en gedigen förståelse för linjär programmering. Senaste revision: 19 september 2007.
- Se animering LP1 .
- En bra artikel om formulering av LP-skivor av Gerry Brown och Rob Dell.
Kapitel 3: Mot Simplex-metoden för effektiv lösning av linjära program. Hörnpunkter och baser. Flytta till förbättrade lösningar. Senaste revision: 18 augusti 2006.
- Se animering LP2 .
Kapitel 4: Mekaniken för Simplex-metoden. Tableaurepresentationen som ett sätt att illustrera processen med simplexmetoden. Särskilda fall som degenerering och obegränsadhet. Senaste revision: 26 september 2017.
- Se animering LP3 .
Kapitel 5: Lösa allmänna linjära program. Lösa icke-standardiserade linjära program. Fas 1 LP-skivor. Genomförbarhet och genomförbarhet. Obegränsade variabler. Senaste revision: 18 augusti 2006.
Kapitel 6: Känslighetsanalys. Enkel datorbaserad känslighetsanalys. Senaste revision: 18 augusti 2006.
- Se animering LP6 .
Kapitel 7: Linjär programmering i praktiken. Omnämnande av andra lösningsmetoder som reviderad simplexmetod och inre punktmetoder. Omnämnande av avancerade tekniker som används i praktiken såsom avancerade metoder och kraschstartmetoder, analys av genomförbarhet och modelleringssystem. Senaste revision: 18 augusti 2006.
Kapitel 8: En introduktion till nätverk. Några grundläggande nätverksbegrepp. Det kortaste ruttproblemet. Det minsta spännande trädproblemet. Senaste revision: 10 september 2010.
Kapitel 9: Maximalt flöde och minimikapacitet. Maximalt flöde och minimala klippproblem i nätverk. Senaste revision: 18 augusti 2006 .
- Se animation Networks3 .
Kapitel 10: Programmering av nätverksflöde. Ett överraskande utbud av problem kan lösas med hjälp av minimikostnad för nätverksflödesprogrammering, inklusive kortaste rutt, maximalt flöde och minsta klippning etc. Variationer som generaliserade nätverk och bearbetningsnät introduceras också kort. Senaste revision: 12 oktober 2017 .
Kapitel 11: PERT för projektplanering och planering . PERT är ett nätverksbaserat hjälpmedel för projektplanering och schemaläggning. Många optimeringsproblem involverar någon aspekt av tidpunkten för aktiviteter som kan köras i följd eller parallellt, eller tidpunkten för resursanvändning. PERT-diagram hjälper dig att förstå och formulera sådana problem. Senaste revision: 3 november 2016 .
- Se animation Networks4 .
Kapitel 12: Heltal / diskret programmering via gren och bunden . Gren och bunden är den grundläggande arbetshästmetoden för att lösa många typer av problem som har variabler som endast kan ta på sig heltal, binära eller diskreta värden. Senaste revision: 23 oktober 2012 .
- Se animering IP1 .
Kapitel 13: Programmering av binära och blandade heltal. Dessa är specialversioner av gren och bundna. Ett binärt program har endast binära variabler (endast 0 eller 1). Ett blandat heltalsprogram ser ut som ett linjärt program, förutom att vissa eller alla variabler är heltal (eller binärt värderade), medan andra kan vara verkligt värderade. Senaste revision: 22 november 2016.
Kapitel 14: Heuristik för diskret sökning: genetiska algoritmer och simulerad glödgning. Vissa problem är bara för stora för grenar och bundna, i vilket fall du måste överge garantin för att hitta den optimala lösningen och istället välja heuristiska metoder som bara kan garantera att du gör det ganska bra för det mesta. Genetiska algoritmer och simulerad glödgning är två populära heuristiska metoder för användning på mycket stora problem. Senaste revision: 22 augusti 2006.
- Se animationerna Heuristics1 och Heuristics2 .
Kapitel 15: Dynamisk programmering . Denna optimeringsteknik bygger mot en lösning genom att först lösa en liten del av hela problemet och sedan gradvis öka storleken i en serie steg tills hela problemet är löst. Effektivitet uppnås genom att kombinera den lokala lösningen för en etapp med det bästa som hittades för en tidigare etapp. Vi tittar på de enklaste deterministiska diskreta fallen. Senaste revision: 16 december 2015.
- Se animering DP1 .
Kapitel 16: Introduktion till icke-linjär programmering (NLP). NLP är mycket svårare än linjär programmering. Vi börjar med att titta på orsakerna till detta. Därefter tittar vi på den enklaste metoden för att lösa den enklaste typen av NLP: obegränsade problem som endast består av en icke-linjär objektiv funktion. Metoden för brantaste stigning / nedstigning beskrivs. Senaste revision: 16 december 2015.
Kapitel 17: Mönster Sök efter obegränsad NLP . Vad gör du om du inte har tillgång till lutningsinformation? I så fall kan du använda mönster söktekniker (även kända som derivatfria, direkt sökning eller svarta rutor). Vi tittar på den klassiska metoden Hooke and Jeeves mönster. Senaste revision: 29 april 2014.
- Se animering NLP7 .
Kapitel 18: Begränsad icke-linjär programmering . Nu när vi har en uppfattning om hur man löser obegränsade NLP: er, hur hanterar vi begränsade NLP: er? Den första idén är naturligtvis att göra dem till obegränsade NLP: er! Detta görs genom att använda straff- och barriärmetoder som ersätter eller modifierar den ursprungliga objektivfunktionen på sätt som gör möjliga punkter attraktiva i det resulterande obegränsade problemet. Senaste revision: 29 april 2014.
Kapitel 19: Hantering av jämställdhetsbegränsningar i NLP . Jämställdhetsbegränsningar är de svåraste att hantera i icke-linjär programmering. Vi tittar på två sätt att hantera dem: (i) metoden för Lagrange och (ii) metoden Generalized Reduced Gradient (GRG). Och vi tittar på att göra linjära approximationer av icke-linjära funktioner eftersom vi behöver det för GRG-metoden. Senaste revision: 2 december 2015.
Kapitel 20: Funktions- och regionformer, Karush-Kuhn-Tucker (KKT) -förhållandena och kvadratisk programmering . Funktions- och regionformer (konvex, icke-konvex, etc.) är viktiga för att förstå hur icke-linjära lösare fungerar. KKT-förhållandena är mycket användbara för att avgöra om en lösningspunkt verkligen är ett lokalt optimalt i ett icke-linjärt program och utgör grunden för vissa metoder för att lösa kvadratiska program. Senaste revision: 21 december 2018.
Olika icke-linjära lokala lösare kan ge helt olika lösningsbanor , dvs sekvensen av mellanlösningar som nås före den slutliga lösningen. Du kan se detta i de närmaste animationerna.