Praktisk Optimering: En Mjuk Introduktion

link: http://www.sce.carleton.ca/faculty/chinneck/po.html

John W. Chinneck
System-och datorteknik
Carleton University
Ottawa, Ontario K1S 5B6
Kanada

http://www.sce.carleton.ca/faculty/chinneck/po.html

De kapitel som visas nedan är förslag till kapitel i en grundläggande lärobok på optimering. Den ultimata målet är att skapa en komplett, men ändå kompakt, inledande undersökning text om de viktigaste frågorna i optimering. Materialet kommer från de föreläsningsanteckningar som används av författaren i civilingenjörsutbildningarna vid Carleton University, och speglar design överväganden för de kurser:

Studenter måste ha en solid intuitivt förståelse för hur och varför optimering metoder fungerar. Detta gör det möjligt för dem att känna igen när saker och ting har gått fel, och att ta reda på orsaken till de svårigheter och vidta lämpliga åtgärder. Den gör det också möjligt för studenter att se hur metoderna kan kombineras eller modifierade för att lösa icke-standard problem.

Förklaring till diagram är mer effektiva i att förmedla en verklig förståelse än ett totalt beroende av matematik.

Det bör finnas en viss exponering för hur saker och ting ska göras i praktiken, vilket kan vara väsentligt annorlunda än hur de görs oftast i läroböcker.

Målet är att den studerande skall kunna känna igen när problem som de stöter på i sitt arbete eller i examensarbetet kan med fördel hanteras av optimeringsmetoder. Eleverna ska kunna sammanfattning en användbar formulering av ett problem från en rörig verkliga världen beskrivning.

Materialet är skrivet på inledande nivå, förutsatt att inga mer kunskap än high school algebra. De flesta koncept utvecklas från scratch. Jag tänker att detta är en skonsam introduktion.

Du behöver Adobe Acrobat reader för att läsa filerna. En gratis läsare är nedladdningsbara från www.adobe.com

Kommentarer och förslag är aktivt. Kontakta författaren på chinneck@sce.carleton.ca. Detta är en utkast till, så vissa diagram är handritade, och det kan finnas stavfel, etc. Fler kapitel kommer att läggas till i mån av tid. Vänligen låt mig veta om eventuella korrigeringar som behövs.

Bläddra i algoritm animationer. Dessa ger animerade illustrationer av många av de viktigaste begreppen. Den studerande utvecklare av dessa animationer finansierades genom en IBM-Faculty Award till Prof. Chinneck. Senast ändrad: 28 augusti 2007.

Att skriva ut hela volymen? Lägg sedan till främre roll för att kunna se bättre. Senast ändrad: den 23 juni 2015.

Kapitel 1: Inledning. En introduktion till processoptimering och en översikt över de viktigaste ämnen som behandlas i kursen. Senast ändrad: 12 December, 2010.

Kapitel 2: Introduktion till Linjär Programmering. i De grundläggande begreppen inom linjär programmering och simplex-metoden. Simplex-metoden är det enklaste sättet att ge en nybörjare med en solid förståelse av linjär programmering. Senast ändrad: September 19, 2007.

Se animation LP1.
En bra artikel om att formulera Lp-skivor av Gerry Brown och Rob Dell.

Kapitel 3: Mot Simplex-Metoden för Effektiv Lösning av Linjära Program. Cornerpoints och baser. Flytta till bättre lösningar. Senast ändrad: 18 augusti 2006.

Se animation LP2.

Kapitel 4: Mekanik Simplex-Metoden. tablån representation som ett sätt att illustrera processen av simplex-metoden. Särskilda fall som förfall och unboundedness. Senast ändrad: 18 augusti 2006.

Se animation LP3.

Kapitel 5: Lösa Allmänna Linjära Program. för att Lösa icke-standard linjär program. Fas 1 Lp. Genomförbarhet och infeasibility. Fria variabler. Senast ändrad: 18 augusti 2006.

Se animationer LP4 och LP5.

Kapitel 6: känslighetsanalys. Enkel dator-baserade känslighetsanalys. Senast ändrad: 18 augusti 2006.

Se animation LP6.

Kapitel 7: Linjär Programmering i Praktiken. Omnämnande av andra metoder lösning som reviderade simplex-metoden och inre punkt metoder. Omnämnandet av avancerade tekniker som används i praktiken, såsom avancerade och krascha börja metoder, infeasibility analys och modellering av system. Senast ändrad: 18 augusti 2006.

Kapitel 8: En Introduktion till Nätverk. Några grundläggande begrepp nätverk. Den kortaste vägen problem. Den minsta uppspännande träd-problem. Senast ändrad: 10 September, 2010.

Se animationer Networks1 och Networks2.

Kapitel 9: Maximalt Flöde och Minimalt Snitt. Den maximala flödet och minimala cut problem i nätverk. Senast ändrad: 18 augusti 2006.

Se animation Networks3.

Kapitel 10: Nätverk Flöde Programmering. Ett överraskande utbud av problem kan lösas med minsta kostnad nätverk flöde programmering, inklusive kortaste vägen, maximalt flöde och minimalt snitt, etc. Variationer såsom generaliserad och bearbetning nätverk är också kortfattat. Senast ändrad: 23 oktober, 2012.

Kapitel 11: PERT för Projektets Planering och Schemaläggning. PERT är en nät-baserade stöd för projektets planering och schemaläggning. Många optimeringsproblem innebära en viss aspekt av timing av verksamheter som kan köras sekventiellt eller parallellt, eller tidpunkten för resursanvändning. PERT-diagram för att hjälpa dig att förstå och formulera sådana problem. Senast ändrad: November 3, 2016.

Se animation Networks4.

Kapitel 12: Integer/Diskret Programmering via en Gren och Bundna. Gren och bunden är den grundläggande arbetshäst som metod för att lösa många typer av problem som har variabler som kan ta på bara heltal, binära, eller diskreta värden. Senast ändrad: 23 oktober, 2012.

Se animation IP1.

Kapitel 13: Binära och Blandad heltalsprogrammering. Dessa är specialiserade versioner av filial och bundna. En binär programmet har endast binära variabler (0 eller 1). En blandad heltal program ser ut som en linjär program, förutom att vissa eller alla av de variabler som är integer-värde (eller binär-värde), medan andra kan vara riktigt uppskattade. Senast ändrad: 22 November 2016.
Se animationer IP2 och IP3.

Kapitel 14: Heuristik för Diskreta Sök: Genetiska Algoritmer och Simulated Annealing.   Vissa problem är bara för stor för gren och bunden, i vilket fall du måste överge garanti för att hitta den optimala lösningen och istället väljer heuristiska metoder som kan garantera att göra ganska bra för det mesta. Genetiska Algoritmer och Simulated Annealing är två populära heuristiska metoder för att användas på mycket stora problem. Senast ändrad: augusti 22, 2006.

Se animationer Heuristics1 och Heuristics2.

Kapitel 15: Dynamisk Programmering. Denna optimering teknik bygger mot en lösning genom att först lösa en liten del av hela problemet, och sedan gradvis öka i storlek i en serie av steg tills problemet är löst. Effektivitet resultat genom att kombinera lokal lösning för en scen med optimal hittade för ett tidigare skede. Vi tittar på den enklaste deterministiska diskret fall. Senast ändrad: 16 December 2015.

Se animation DP1.

Kapitel 16: Introduktion till Ickelinjär Programmering (NLP). NLP är en mycket, svårare än linjär programmering. Vi börjar med att titta på orsakerna till detta. Nästa vi titta på den enklaste metoden för att lösa den enklaste typen av NLP: otvungen problem som består endast av en icke-linjära objektiva funktion. Metoden för brantaste ascent/descent beskrivs. Senast ändrad: 16 December 2015.

Se animationer NLP1 och NLP2.

Kapitel 17: Mönster Sök för Unconstrained NLP. Vad gör du om du inte har tillgång till gradient information? I så fall kan du använda mönster sök tekniker (även känd som derivat-gratis, direkt söka, eller svart låda metoder). Vi tittar på den klassiska Hooke och Jeeves mönster search metoden. Senast ändrad: 29 April, 2014.

Se animation NLP7.

Kapitel 18: Begränsad Ickelinjär Programmering. Nu när vi har en idé om hur man kan lösa obegränsad före detta polymerer, hur vi handskas med begränsad före detta polymerer? Den första tanken är att förvandla dem till obegränsad före detta polymerer av kursen! Detta görs genom att använda straff och hinder metoder som kan ersätta eller ändra de ursprungliga målet funktion på ett sätt som gör det möjligt punkter attraktiva i den resulterande obegränsad problem. Senast ändrad: 29 April, 2014.

Kapitel 19: Hantera Jämlikhet Begränsningar i NLP. Jämställdhet begränsningar är de svåraste att hantera i en icke-linjär programmering. Vi tittar på två sätt att handskas med dem: (i) metoden av Lagrange, och (ii) den Generaliserade rgbm (GRG) metod. Och vi tar en titt på att göra linjära approximationer till olinjära funktioner eftersom det är det vi behöver för GRG-metoden. Senast ändrad: December 2, 2015.

Kapitel 20: Funktion och Region Former, Karush-Kuhn-Tucker (KKT) Villkor, och Kvadratisk Programmering. Funktion och region former (konvex, nonconvex, etc.) är viktig för att förstå hur icke-linjär lösare arbete. KKT villkoren är mycket användbara för att besluta om en lösning punkt är verkligen en lokal optimalt i en icke-linjär program, och utgör grunden för några metoder för att lösa kvadratiska program. Senast ändrad: 16 December 2015.

Olika ickelinjära lokala lösare kan ge helt olika lösning banor, dvs sekvens av mellanliggande lösningar nås före den slutliga lösningen. Du kan se detta i nästa några animationer.

Se animationer NLP3, NLP4, NLP5, NLP6,