Modelleren en Optimaliseren met Wiskunde Beoefening van Wiskunde in het Spoor van Newton. Rede uitgesproken door

Modelleren en Optimaliseren met Wiskunde Beoefening van Wiskunde in het Spoor van Newton

Rede uitgesproken door C. Roos

op vrijdag 10 december 1999 bij de openlijke aanvaarding van het ambt van bijzonder hoogleraar in de Faculteit Wiskunde en Natuurwetenschappen aan de Universiteit Leiden om werkzaam te zijn op het vakgebied Toepassingen van de Wiskunde.

Modelleren en Optimaliseren met Wiskunde

1

2


I do not know what I may appear to the world; but to myself I seem to have been only like a boy playing on the sea-shore, and diverting myself in now and then finding a smoother pebble or a prettier shell than ordinary, whilst the great ocean of truth lay all undiscovered before me ([18], p. 863). Isaac Newton (1642–1724)


3

4


Mijnheer de rector magnificus, Leden van het Bestuur van het Leids Universiteits Fonds, Leden van het Curatorium van deze bijzondere leerstoel, Zeer gewaardeerde toehoorders,

Inleiding Eerder dit jaar, bij de viering van de dies natalis, herinnerde mevrouw prof.dr. E.G.E. van der Wal ons er aan dat het door Prins Willem van Oranje opgegeven ‘mission statement’ voor de Leidse Universiteit een belangrijke plaats toekende aan de studie van het christelijk geloof [?]. Op dat moment dreigde de opleiding van predikanten in Leiden te sneuvelen onder het geweld van de Samen-Op-Weg beweging. Het is een uitermate verheugende zaak dat op de vorige week gehouden trio-synode deze ontwikkeling alsnog werd teruggedraaid. Graag feliciteer ik de universiteit in de persoon van de rector magnificus met deze wending in de loop der gebeurtenissen waardoor wordt recht gedaan aan de historische wortels van de oudste universiteit in Nederland. Men dient in het leven altijd open te staan voor verrassingen. Mijn ervaring is dat dit ook geldt in de wiskunde. Ik zal daarvan straks enkele voorbeelden geven. Centraal in de rede van professor van der Wal stond een vraag die rond de vorige eeuwwisseling een rol speelde in de discussies, namelijk: Zijn wij nog christenen? Zij verwachtte opnieuw aandacht voor deze vraag bij het opmaken van de balans van het tweede millennium in onze christelijke jaartelling. Ik wil deze gelegenheid niet voorbij laten gaan zonder er op te wijzen dat we een jaar langer de tijd hebben voor het opmaken van deze balans dan veelal wordt gedacht. Het tweede millennium eindigt namelijk niet over drie weken maar pas een jaar later. Ik wil deze bewering staven met een bewijs. Het is een eenvoudige oefening in tellen. Onze jaartelling dateert uit de zesde eeuw. Toen stelde Dionysius Exiguus een nieuwe chronologie op, in opdracht van paus Johannes I. Het getal 0 is pas later in het Westen ingevoerd door paus Sylvester, rond het jaar 1000. Het eerste jaar van onze jaartelling kan daarom niet het jaar 0 geweest zijn maar was noodzakelijk het jaar 1. Wij leven nu in 1999, het negentienhonderd-negen-en-negentigste jaar van onze jaartelling; deze eeuw eindigt aan het eind van het tweeduizendste jaar, dit is dus aan het eind van het jaar 2000. Einde bewijs. Viering van het einde van het tweede millennium over drie weken is als het vieren van je vijftigste verjaardag op de dag dat je 49 wordt. De grote aandacht voor de komende jaarwisseling heeft meer te maken met de moeite die onze compu-


5

ters hebben met het niet-natuurlijke getal 0 dan met de structuur die onze jaartelling aan de tijd geeft. Maar nu terzake. Mijn leeropdracht is Toepassingen van de Wiskunde. Ik beschouw het als een uitdaging om vanmiddag te laten zien dat wiskunde een boeiend vak is, met ongelofelijk veel toepassingen op allerlei gebieden. Ik wil mij daarbij concentreren op het gebruik van wiskundige optimalisatiemodellen. Het onderwerp heeft een lange geschiedenis, waaraan veel grote geesten in het verleden en heden hebben bijgedragen. Hun ideeën, gecombineerd met de geweldige rekenkracht die de moderne computertechnologie ons verschaft, maken van de wiskunde een krachtig stuk gereedschap. Bedrijven die hiervan gebruik weten te maken kunnen er een beslissende voorsprong op de concurrentie mee verkrijgen. Wiskundigen hebben hun eigen taal, waarin formules en plaatjes een belangrijke rol spelen. In deze prachtige, historische zaal, ooit de kapel van een nonnenklooster, is het moeilijk om deze taal te gebruiken. De kapel is er kennelijk niet voor gemaakt. Vanmiddag wordt het daarom wiskunde ´ ´ zonder formules en zonder plaatjes. Voor de meesten van u is dit waarschijnlijk zeer welkom; het dwingt mij om mezelf te bedienen van een voor u begrijpelijke taal. Een jaar geleden vroeg iemand met wie mijn vrouw en ik al vele jaren bevriend zijn, waarover het vanmiddag zou gaan. Ik heb toen geantwoord dat het zou gaan over de relevantie en de schoonheid van de wiskunde. Voor de meesten van u ligt de combinatie van wiskunde en schoonheid wellicht minder voor de hand. Daarom wil ik daarbij apart stil staan. Het mag misschien nauwelijks hardop worden gezegd aan een universiteit die markten maatschappijgericht wil zijn, maar voor de meeste wiskundigen, evenals trouwens andere wetenschappers, is de diepste drijfveer waarschijnlijk dat zij geboeid zijn door iets geweldig moois. Wetenschappers, en in het bijzonder wiskundigen zijn op zoek naar structuur; men zou kunnen zeggen dat het toepassen van wiskunde neerkomt op het benutten van de kennis van structuur. De ontdekking van een nieuwe structuureigenschap leidt tot een beleving van schoonheid en verwondering. Ik wil daarvan straks enkele illustraties geven. In het bijzonder zal ik wat langer stilstaan bij Isaac Newton. Op conferenties en in artikelen op mijn vakgebied wordt geen naam vaker genoemd dan de zijne. Bij de voorbereiding van deze rede vond ik in recente biografieën van Newton dingen die ik niet ongenoemd wil laten omdat ze mij erg verrasten.

6


Wiskundige modellen Veel praktische problemen in de techniek, economie, telecommunicatie, logistiek en andere gebieden laten zich wiskundig modelleren. Een wiskundig model ontstaat door eerst de relevante grootheden in het probleem te identificeren en vervolgens de relevante relaties tussen deze grootheden. Een wiskundig model bestaat zodoende uit een stelsel relaties tussen variabelen. Deze relaties kunnen van allerlei aard zijn. In de natuurkunde bijvoorbeeld, worden zij vaak bepaald door fysische wetten, zoals de bekende wet van Newton, of behoudswetten. Zij hebben dan de vorm van een algebra¨ısche vergelijking of een differentiaalvergelijking. Ook voor de variabelen zijn er vele mogelijkheden. Zij kunnen continu zijn, bijvoorbeeld als de variabele een temperatuur voorstelt. Het andere uiterste treedt op voor variabelen die aantallen voorstellen; zulke variabelen mogen alleen geheeltallige waarden aannemen. Een bijzonder geval van een geheeltallige variable is een logische variabele die alleen de waarde 0 of 1 mag aannemen; dergelijke variabelen modelleren ja-nee situaties, waarbij een keuze moet worden gemaakt uit 2 mogelijkheden. Uiteraard is een wiskundig model altijd een abstractie van de werkelijkheid en worden aspecten genegeerd die moeilijk kwantificeerbaar zijn of die de maker van het model minder relevant acht. Het streven moet gericht zijn op een wiskundig model dat enerzijds wiskundig hanteerbaar (dat wil zeggen oplosbaar) is en anderzijds voldoende nauwkeurig aansluit bij de geabstraheerde werkelijkheid. Het maken van een wiskundig model is een kunst op zich; zelfs voor ervaren wiskundige modelmakers is het maken van een goed model een iteratief proces. Mijn ervaring is dat colleges waarin studenten kennis maken met geavanceerde modelleer-technieken hoog scoren; een breed terrein van toepassingen in onder andere de economie, de techniek en de logistiek kan worden bestreken. Tegelijkertijd blijkt het maken van een goed model de student vaak voor een intellectuele uitdaging te plaatsen.

Het solvatie-probleem Het wordt voor de meeste wiskundigen pas echt interessant als we eenmaal een model hebben. Het model moet namelijk worden opgelost. Dit betekent dat de verzameling van alle oplossingen moet worden gevonden. Dit kan bijvoorbeeld betekenen dat een stelsel lineaire vergelijkingen moet worden opgelost, of een stelsel differentiaalvergelijkingen. Verschillende onderdelen van de wiskunde kunnen worden gekarakteriseerd door het soort mo-


7

dellen dat er in wordt bestudeerd: (lineaire) algebra, analyse, differentiaalvergelijkingen, integraalvergelijkingen, etc. De kunst om efficiënte algoritmen te vinden voor het oplossen van dergelijke stelsels heeft wiskundigen al eeuwen beziggehouden; veel van de door hen ontwikkelde algoritmen behoren tot de standaard-bagage van de wiskundige en worden nog steeds gebruikt. Door de opkomst van de computer worden deze algoritmen in feite meer gebruikt dan ooit. Er kunnen nu problemen mee worden opgelost die de menselijke maat ver te boven gaan. Vooral bij het oplossen van grootschalige problemen blijkt een recht-toerecht-aan implementatie van een standaard-algoritme bijna altijd tot veel te lange rekentijden te leiden. In dergelijke gevallen moet het algoritme worden aangepast en verfijnd zodat optimaal gebruik gemaakt wordt van de aanwezige structuur in het probleem, waardoor de rekentijd tot aanvaardbare proporties wordt teruggebracht. Hierbij is het vaak ook van belang het gebruikte model opnieuw kritisch te bekijken; veel problemen kunnen op verschillende manieren worden gemodelleerd. Daarnaast kan de keuze van geschikte datastructuren voor de opslag van gegevens van het probleem in de computer doorslaggevend zijn voor de efficiëntie van een implementatie. Concluderend kunnen we zeggen dat het bij het oplossen van een gegeven probleem aankomt op het vinden van een goede combinatie van model, datastructuren en algoritme. Er zijn nog enkele niet-vanzelfsprekende eisen die aan een algoritme moeten worden gesteld. Als een probleem precies e´ e´ n oplossing heeft dan zal een goed algoritme deze oplossing genereren. Een voorbeeld van zo een probleem is de ontbinding van een gegeven getal in priemfactoren; het is een bekend feit dat deze ontbinding, tot op de volgorde der factoren na, eenduidig is. Er zijn ook problemen die helemaal geen oplossing hebben. In dat geval heet het model met een Engels woord infeasible. Een algoritme dient eventuele infeasibiliteit van een model vast te stellen. Anderzijds gebeurt het heel vaak dat een probleem meerdere oplossingen heeft. In zulke gevallen zal het algoritme een aanwijzing moeten geven dat de geproduceerde oplossing niet de enige is en bij voorkeur ook een indicatie over het aantal oplossingen dat het model heeft. Veel bekende algoritmen voldoen trouwens niet aan deze voor de hand liggende eis!

Het optimalisatie-probleem Als er meerdere oplossingen zijn dan geeft dit meestal aanleiding tot een optimalisatie-probleem. Dit doet zich voor als er een of ander criterium be-

8


staat waardoor de ene oplossing ‘beter’ geacht wordt dan de andere. In het algemeen wordt het betreffende criterium gemodelleerd als een functie op de verzameling van alle oplossingen. Het probleem waarvoor we ons dan gesteld zien, is om een oplossing te vinden die deze zogenaamde doelfunctie optimaliseert. Optimaliseren is een heel natuurlijke activiteit. De natuur doet het: een lichtstraal tussen twee punten kiest de kortste weg en een zeepbel omsluit een maximaal volume bij gegeven oppervlakte; bijen maken honingraten met maximale inhoud bij gegeven hoeveelheid materiaal. Wijzelf optimaliseren ook: velen van ons zoeken ’s morgens de snelste weg naar ons werk. Dit laatste voorbeeld doet al zien dat optimaliseren lang niet altijd eenvoudig is: vanuit Waddinxveen komend zijn er vele wegen naar het Mathematisch Instituut; als ik na vele file-vermijdende keuzes op het instituut ben aangekomen blijft het altijd een vraag of de gekozen route wel de snelste was. Ik wil nu iets zeggen over het oplossen van een optimalisatie-modellen. Daarbij beginnen we met het eenvoudigste geval, namelijk dat alle beperkingen lineair zijn en dat ook de doelfunctie lineair is. We hebben dan te maken met een zogenaamd lineair optimalisatie-model.

Lineaire optimalisatie Het vakgebied Lineaire Optimalisatie (afk. LO) ontstond in en na WO II, dankzij het werk van Dantzig, Kantorovich, Koopmans en von Neumann. Zij waren de eersten die het belang inzagen van lineaire optimalisatie-modellen voor het oplossen van met name economische planningsproblemen. De eerste methode voor het oplossen van dergelijke modellen was de door Dantzig voorgestelde Simplex methode. Zonder te overdrijven kan worden gesteld dat dit waarschijnlijk de meest toegepaste wiskundige methode is. De Simplex methode is rekentechnisch zeer eenvoudig uit te voeren. Alleen de elementaire rekenkundige operaties optellen, aftrekken, delen en vermenigvuldigen worden uitgevoerd op een tableau waarin aanvankelijk de gegevens van het model staan. Het aantal operaties is echter dermate groot dat met pen en papier alleen betrekkelijk kleine modellen kunnen worden opgelost, zeg met hoogstens een tiental variabelen en een tiental beperkingen. Gelukkigerwijze viel de ontdekking van de Simplex methode samen met de opkomst van de computer. Het rekenwerk kon daarom worden geautomatiseerd. Dit opende op den duur de weg naar meer grootschalige toepassingen. Vooral oliemaatschappijen behoorden tot de grote gebruikers van het computerprogramma MPS/360 voor lineaire


9

optimalisatie dat IBM in 1966 op de markt bracht en dat draaide op de toen juist ge¨ıntroduceerde IBM 360 computers. Aan het eind van de jaren 60 en het begin van de 70-er jaren kwamen ook andere softwarepakketten op de markt. Vanuit theoretisch gezichtspunt heeft de Simplex methode een aantal problematische eigenschappen. Een eerste probleem is dat de methode kan rondzingen: na uren rekenwerk kan het gebeuren dat een tableau wordt gevonden dat al eerder werd gegenereerd. Dit verschijnsel wordt cycling genoemd. Het is een verschijnsel dat in het dagelijks leven ook optreedt. Bijvoorbeeld, als je in een onbekende stad op zoek bent naar een bepaald adres en na korte of langere tijd constateert dat de zoektocht je op een plaats brengt waar je al eerder bent geweest. Het verschijnsel cycling valt trouwens ook nogal eens op te merken in bestuurlijke processen. Moderne bedrijven en instellingen zijn voortdurend op zoek naar een optimale organisatiestructuur. Daartoe worden bijna continu veranderingen in de organisatie doorgevoerd. Elke verandering wordt gepresenteerd als een verbetering. Soms blijkt na enige jaren dat er na alle veranderingen niets veranderd is: de nieuwe situatie is dezelfde als die van enkele jaren eerder. Voor een wiskundig algoritme is het verschijnsel van cycling desastreus: het betekent dat de gewenste oplossing nooit zal worden gevonden. Voor de Simplex methode is dit gevaar al door Dantzig herkend, e` n bezworen. Het gevolg hiervan is dat de Simplex methode altijd convergeert naar een oplossing van het probleem. Een tweede eigenschap van de Simplex methode betreft de vereiste rekentijd. Men mag verwachten dat deze groter is naarmate het aantal variabelen en het aantal relaties groter is. Maar als de rekentijd te snel toeneemt leidt dit er toe dat grotere problemen excessief veel rekentijd vergen. Men heeft getracht om de door de Simplex methode vereiste rekentijd te schatten. Maar elke poging eindigde met een formule voor de rekentijd die exponentieel is in het aantal variabelen of het aantal relaties. In 1972 werd duidelijk dat de Simplex methode het niet beter kan. In dat jaar publiceerden Klee en Minty een elegant voorbeeld waarvoor de rekentijd exponentieel aangroeit met de grootte van het probleem [?]. Het resultaat van Klee en Minty luidde een nieuwe periode in in de wereld van de Lineaire Optimalisatie. Men ging op zoek ging naar andere, meer efficiënte methoden. In 1979 melde de voorpagina van de New York Times een belangrijke doorbraak: de Russische wiskundige Leonid Khachiyan had een nieuwe methode gevonden met de begeerde eigenschap, de Ellipso¨ıde methode. Hiermee konden LO-problemen in polynomiale tijd worden opgelost. De rekentijd van de Ellipso¨ıde methode neemt toe volgens een polynomiale functie van de grootte van het probleem. Dit was een

10


enorme doorbraak, met geweldige theoretische gevolgen die onder andere door onze landgenoot Schrijver nadien te gelde zijn gemaakt. Voor practici was het resultaat van Khachiyan echter een grote teleurstelling. Computerprogramma’s gebaseerd op de Ellipso¨ıde methode bleken veel langzamer en minder robuust te zijn dan die welke gebaseerd waren op de Simplex methode. Het gevolg was een onplezierige spanning tussen de theorie en de praktijk: de theoretisch efficiënte Ellipso¨ıde methode voldeed in de praktijk veel minder goed dan de theoretisch inefficiënte Simplex methode. Er vond opnieuw een doorbraak plaats in 1984. In dat jaar werd de wereld verrast met een publicatie van de Indiër Narendra Karmarkar die de theorie en de praktijk weer met elkaar verzoende [7]. Het was opnieuw voorpaginanieuws. Karmarkar was werkzaam bij het bekende Amerikaanse bedrijf AT&T, en had een heel nieuwe benadering gevonden van het LO-probleem. Zijn zogenaamde Projectieve methode was polynomiaal en, zoals Karmarkar claimde, in de praktijk minstens 100 maal sneller dan de Simplex methode, met name voor grootschalige problemen. Vooral de laatste claim veroorzaakte grote commotie. Ik ken geen ander voorbeeld in de hedendaagse wiskunde dat zoveel opwinding e´ n tegenspraak heeft opgeroepen. Het was buitengewoon boeiend om tijdens conferenties de discussies tussen Karmarkar en collega’s met een gevestigde reputatie mee te maken, en er aan deel te nemen. Voor een belangrijk deel werd de reactie op Karmarkar’s werk veroorzaakt doordat de gepubliceerde versie (in het vaktijdschrift Combinatorica, 1984) afweek van de bij AT&T ge¨ımplementeerde versie. Daarover gaf Karmarkar geen openheid. Later werd duidelijk waarom: AT&T zag een kans om een computerprogramma voor LO te maken dat ongeveer 200 maal sneller was dan de toenmalige commerciële standaardpakketten. Omdat het hier een markt betreft waarin grote bedragen omgaan, was AT&T bereid fors te investeren. Er werd een projectgroep gevormd met als opdracht een nieuw LOpakket te ontwerpen op basis van Karmarkar’s methode. De grootte van de groep groeide gedurende zijn bestaan aan van 20 tot 200 onderzoekers. In 1989, dus ongeveer 5 jaar later, werd het pakket gelanceerd onder de naam KORBX. De prijs: 7 miljoen dollar. Daar werd dan wel een parallelle vector-computer van Alliant bijgeleverd. Het pakket was niet portable, het draaide alleen op de bijgeleverde computer. Dit is achteraf beschouwd een grote beleidsfout geweest. Het is daardoor allemaal anders gegaan dan bij AT&T werd gehoopt. Voorzover bekend is het pakket (tegen een gereduceerde prijs) alleen verkocht aan de Amerikaanse luchtmacht, die het ge´ en tijdens bruikt heeft voor de optimalisatie van de logistieke operaties vo´ or de Golfoorlog, en aan Delta Airlines.


11

Buiten AT&T had men ondertussen niet stilgezeten. Aanvankelijke implementaties, die waren gebaseerd op Karmarkar’s artikel, bleken zo’n 100 maal langzamer te zijn dan de Simplex methode in plaats van 100 maal sneller. Sommigen dachten daarom dat de geschiedenis zich herhaalde: men vreesde dat hier opnieuw sprake was van een polynomiale methode die in de praktijk minder efficiënt was dan de Simplex methode; zij haakten daarom al snel af. Anderen probeerden langs theoretische weg duidelijk te maken dat Karmarkar niets nieuws bedacht had en namen, veelal uit onbegrip, een zeer conservatieve houding aan. Karmarkar hield evenwel vast aan zijn claims. Dat inspireerde, wereldwijd, velen tot verder onderzoek. In een periode van 10 jaar verschenen meer dan 2000 wetenschappelijke publicaties. Dit leidde tot allerlei nieuwe theoretische inzichten. Enkele collega’s verwerkten deze inzichten onmiddellijk in nieuwe computerprogramma’s. Het werk van Irv Lustig, Roy Marsten en David Shanno leidde na enige tijd tot een code, OB1 geheten, die kon wedijveren met de snelste implementaties van de Simplex methode. Tegen de tijd dat KORBX op de markt kwam, was OB1 sneller, geschikt voor alle gangbare computersystemen en bovendien voor onderzoeksdoeleinden vrij beschikbaar. Overigens was OB1 gebaseerd op een methode die eigenlijk al in de jaren 70 bekend was, de zogenaamde logaritmische barriëre methode. Door deze methode te verfijnen ontstonden de zogenaamde primaal-duale padvolgende methoden of inwendige-punt methoden. De eerste naam verwijst naar het zogenaamde centrale pad van een LO-probleem; dit is een curve in het inwendige van het toelaatbare gebied van het probleem die naar een optimale oplossing convergeert. Toen het centrale pad eenmaal ontdekt was door diverse collega’s, onafhankelijk van elkaar, werd het de basis van alle moderne inwendige-punt methoden. Deze methoden zijn in feite niets anders dan numerieke recepten die een rij van punten genereren, op of dichtbij het centrale pad, zodanig dat de rij convergeert naar een optimale oplossing. Op deze manier ontstonden efficiënte (dit is: polynomiale) methoden, waarvan de praktische efficiëntie de claim van Karmarkar meer dan rechtvaardigde [13]. Inmiddels was gebleken dat bij het implementeren van de Simplex methode nauwelijks gebruik was gemaakt van in de literatuur aangedragen technieken om de methode te versnellen. Het is vooral de verdienste van collega Bob Bixby (Rice University, Houston, USA) geweest om hier baanbrekend werk te doen. In feite ontstond een spannende competitie tussen hem en een groep van collega’s die de inwendige-punt-benadering implementeerden. Uiteindelijk leidde dit in sommige toepassingen tot een prachtige synthese van beide benaderingen. Daarbij wordt eerst een bijna-optimale op-

12


lossing geconstrueerd met de inwendige-punt-benadering, waarna vervolgens met de Simplex methode een exacte oplossing wordt bepaald. Het gevolg van de geschetste ontwikkelingen is dat tegenwoordig LO-problemen ongeveer 1.000.000 maal sneller kunnen worden opgelost dan in 1984. Een factor 1000 is te danken aan de vooruitgang in de algoritmiek en de andere factor 1000 aan het feit dat de computers van nu ongeveer 1000 maal sneller zijn dan in die tijd. De gevolgen voor de toepassingen zijn verstrekkend. Een model waarvoor 15 jaar geleden 1 jaar rekentijd nodig was, kan nu in ongeveer 30 seconden worden opgelost. Het is duidelijk dat problemen die 1 jaar rekentijd vergen vanuit praktisch oogpunt bezien onoplosbaar zijn. De genoemde verbetering in performance is daarom niet slechts een kwantitatieve verbetering. Het betekent dat problemen die 10 jaar geleden praktisch gesproken onoplosbaar waren nu in enkele seconden kunnen worden opgelost. Moderne pakketten voor lineaire optimalisatie bevatten de mogelijkheid om zowel de Simplex methode als de inwendige-punt methode te gebruiken. Voorbeelden zijn de pakketten OSL van IBM en CPLEX (gebaseerd op de Simplex code van Bixby en de eerder genoemde inwendige-punt code OB1), sinds 1997 eigendom van het Franse bedrijf ILOG en sinds 1998 van het bekende Duitse bedrijf SAP. Het aantal omgevingen waarin deze pakketten dagelijks worden gebruikt is zeer gevarieerd: luchtvaartmaatschappijen, oliemaatschappijen, waterschappen, financiële instellingen, enzovoort. Door de veel betere performance van met name CPLEX maakt het gebruik van lineaire optimalisatie-modellen een explosieve groei door en kan worden gesproken van een bloeitijd voor de optimalisatie. Ter illustratie wil ik hier het werk noemen van een van mijn oud-studenten, ir. Henk Post. Hij houdt zich bezig met de automatisering van vraagafhankelijk vervoer in Nederland, bij het in Baarn gevestigde bedrijf Future Technology. Het mede door hem ontwikkelde Route Beheers Systeem (afk. RBS) wordt op grote schaal gebruikt door taxibedrijven en leidt tot aanzienlijke besparingen. In plaats van 100 - 250 ritten per centralist per dag kunnen er nu 500 - 1000 ritten geregeld worden. Dagelijks worden zo’n 10.000 ritten in Nederland automatisch toegewezen aan zo’n 500 beschikbare voertuigen. Dit jaar zijn de routines van RBS uitgebreid, zodat er ook gecombineerd kan worden met alle vormen van openbaar vervoer. Dit product heet TraXX. TraXX wordt gebruikt door het openbaar vervoer bedrijf Connexxion in heel Nederland voor het vervoer van gehandicapten van deur tot deur en was bij de invoering enkele maanden geleden uitgebreid in het nieuws.


13

Het moet nog wel worden opgemerkt dat veel verschijnselen in deze wereld niet door een lineair model zijn te beschrijven. In zulke gevallen ontstaan niet-lineaire modellen. Het oplossen daarvan vergt andere methoden, waarop ik nu niet kan ingaan. Ik volsta met enkele opmerkingen. Ook op het gebied van de niet-lineaire optimalisatie zijn de laatste 10 jaar aanzienlijke vorderingen gemaakt. Cruciaal was het werk van Nesterov en Nemirovski [?]. Zij hebben aangetoond dat de inwendige-punt-benadering ook toepasbaar is op zogenaamde convexe problemen. Het meest verrassende gevolg van hun baanbrekend werk is misschien wel dat de niet-lineariteit van sommige niet-lineaire problemen zodanig kan worden gemodelleerd dat het model als een lineair probleem kan worden opgelost. Momenteel staat de zogenaamde Semidefiniete Optimalisatie daardoor zeer in de aandacht. De achterliggende wijze van wiskundig modelleren vergt echter wel nieuwe vaardigheden die pas in de hogere jaren van de wiskunde-opleiding kunnen worden aangeleerd. Onder mijn collega’s in de optimalisatie heerst vrij algemeen de overtuiging dat Karmarkar’s werk het topje van de ijsberg is; daaronder ligt een groot massief waarvan nog maar een klein deel is verkend. Bij een eerste verkenning van dit massief hebben Goemans en Williamson [5] prachtige resultaten gevonden voor een bekende moeilijke klasse van combinatorische optimalisatie-problemen. De door hun ontwikkelde techniek is al gebleken van toepassing te zijn op vele andere ingewikkelde problemen, onder andere bij het ontwerpen van de lay-out van chips.

Schoonheid in de wiskunde Ik gebruikte zojuist het woord prachtig. Maar ik kan in het kader van deze rede helaas niet laten zien waarom. Dat is een beetje het probleem met de schoonheid van de wiskunde. De schoonheid van het werk van Goemans en Williamson is onder wiskundigen onbetwist; het werk is dan ook vele malen bekroond. Maar om die schoonheid te kunnen zien moet men zich enige wiskundige inspanning getroosten. Het is als bij het uitzicht vanaf een hoge berg: men moet de berg eerst beklimmen om van het uitzicht te kunnen genieten. Het eigenaardige van wiskundigen is dat zij vaak zelf hun problemen definiëren. Dit geldt met name voor de meer theoretisch ingestelde wiskundigen. Een beroemd voorbeeld hiervan is de laatste stelling van Fermat. Deze stelling uit de zeventiende eeuw zegt dat er voor geen positieve gehele getallen en bestaan die voldoen aan de vergelijking . 14


Helaas heeft Fermat ons zijn bewijs voor deze stelling niet nagelaten. In feite bestaat er gerede twijfel of zijn ons onbekende bewijs wel correct was. Veel beroemde wiskundigen hebben nadien gezocht naar een bewijs. Uiteindelijk is het bewijs door de Engelse wiskundige Andrew Wiles in 1995 gevonden. Wiles was (en is) hoogleraar aan Princeton University en heeft zeven jaar aan het bewijs gewerkt, in bijna volledige afzondering. Toen Wiles een eerste versie van zijn bewijs tijdens een conferentie in Cambridge (Engeland) presenteerde, sloeg dat in als een bom en viel hem een langdurige ovatie ten deel. Enkele maanden later ontdekte een collega een lacune in het bewijs. Wiles bracht het op om zich opnieuw op te sluiten in zijn studeerkamer. Na twee jaar lang zoeken vond hij de sluitsteen van het bewijs. Toen hij in een BBC-documentaire de herinnering ophaalde aan het moment waarop hem de sluitsteen als het ware in een openbaring werd aangereikt, werd het hem emotioneel te machtig. Nadat hij zich had hersteld zei hij geëmotioneerd dat de uiteindelijke oplossing een sublieme schoonheid, eenvoud en elegantie vertoonde: It was so incredibly beautiful, so simple and so elegant. Een ander voorbeeld. Als iemand zo is gebiologeerd door de wiskunde dat hij er zijn hele leven aan wijdt dan moet er wel iets aan de hand zijn. Zo iemand was de Hongaarse wiskundige Paul Erd˝os (1913–1996). Hij zou kunnen worden gekarakteriseerd als een pelgrimerende wiskundige. Paul Erd˝os had geen andere bezittingen dan een koffertje met wat kleren en boeken en daarmee reisde hij de wereld rond. Er wordt verteld dat hij er van hield om te filosoferen over Het Boek, waarin de mooiste bewijzen staan van wiskundige stellingen. Volgens Erd˝os hoefde je niet in God te geloven, maar iedere wiskundige zou moeten geloven in Het Boek. Bewijzen die niet voldeden aan de criteria van Het Boek, ‘lelijke’ bewijzen, verdienden in zijn ogen geen blijvend bestaan. Twee collega’s stelden hem voor om een eerste benadering van Het Boek te maken; hij werkte er samen met deze twee collega’s aan die het werk, na Erd˝os’ dood in de zomer van 1996, voltooiden. Het resultaat verscheen in 1998 bij Springer [1]. Het bevat vijf hoofdstukken met prachtige bewijzen van stellingen uit de Getaltheorie, Meetkunde, Analyse, Combinatoriek en Grafentheorie. De stellingen en de gegeven bewijzen zijn afkomstig van vele wiskundigen, van Euler tot Erd˝os zelf. Voorzover ik kon nagaan treffen we onder hen de naam van slechts e´ e´ n Nederlander aan: L.E.J. Brouwer, met zijn beroemde vaste-punt stelling. Ik wil in dit verband ook stilstaan bij Isaac Newton (25 december 1642 – 20 maart 1724). De hiervoor genoemde inwendige-punt methoden voor lineaire en niet-lineaire optimalisatie maken zonder uitzondering gebruik van een door Newton voorgestelde methode om het nulpunt van een functie te


15

bepalen. Een belangrijk deel van het recente onderzoek betrof de analyse van deze methode; met name door het eerdergenoemde werk van Nesterov en Nemirovski wordt het gedrag van Newtons methode voor convexe functies nu veel beter begrepen. Bij wijze van eerbetoon aan Newton daarom het volgende. Niemand heeft meer bijgedragen aan de ontdekking van structuren in de natuur dan Isaac Newton. Op lijsten van de 100 meest belangrijke personen in de geschiedenis van de Westerse wetenschap staat Newton meestal bovenaan [16]. Zijn zogenaamde traagheidswet en gravitatiewet zijn grondleggend geweest voor de moderne Westerse wetenschap. De bekende wiskundige formuleringen van deze wetten kunnen worden beschouwd als de eerste wiskundige modellen van fysische verschijnselen. Newton kan daarom worden beschouwd als de uitvinder van het gebruik van wiskundige modellen. Hij heeft daarnaast belangrijke technieken ontwikkeld om dergelijke modellen op te lossen. Zijn werk over machtreeksen en de differentiaalrekening is onderwerp geweest van een eeuwenlange prioriteitsvraag, met Leibniz als tegenspeler. De strijd is nog altijd onbeslist, hoewel er sterke argumenten in het voordeel van Newton zijn. Ook op vele andere gebieden is Newton actief geweest. Zoals bekend heeft hij een belangrijke bijdrage geleverd aan de vernieuwing van het muntstelsel in Engeland , en was hij vanaf 1703 tot aan zijn dood president van de Royal Academy of London. Newton kan worden gekarakteriseerd als een zoeker naar de Waarheid, over God, de geschiedenis en de natuur. Met deze drie thema’s is hij zijn hele leven bezig geweest. Zijn natuurwetenschappelijk werk heeft hem beroemd gemaakt. Het is tijdens zijn leven gepubliceerd, zij het veelal pas na lang aandringen van anderen. De omvang en inhoud van de chronologische en theologische manuscripten die door Newton zijn achtergelaten zijn pas bekend geworden nadat een groot deel van deze manuscripten in 1936 werd geveild bij Sotheby’s, in de zogenaamde Portsmouth collectie. Het beeld dat oprijst, is dat de natuur zich aan Newton voordeed als een puzzel waarvan de stukjes op een passende wijze bij elkaar moeten worden gelegd. Zo beschouwde hij ook de Bijbel, met name de profetische geschriften daarin. Newton heeft tijdens zijn leven deze chronologische en theologische manuscripten niet gepubliceerd. Zeker voor wat betreft de theologische geschriften is de reden daarvan duidelijk. Hij had namelijk grote problemen met de klassieke leer van de Drie-eenheid. Daarin staat zijns inziens een gelijkteken dat er niet hoort te staan. Publicatie van zijn opvattingen zou hem de toegang tot de universiteit en de openbare ambten die hij op latere leeftijd bekleedde hebben ontnomen. De belangstelling van Newton voor de chronologie was in zijn tijd niet uniek. Meer grote geesten hebben zich

16


ingespannen om vat te krijgen op de vele verschillende tijdrekeningen van oude culturen, en deze met elkaar in harmonie te brengen. Dat had te maken met het besef dat ook de tijd een structuur heeft. Dit besef werd voornamelijk ontleend aan de profetische geschriften in de Bijbel, het boek Daniël in het Oude en het boek Openbaringen in het Nieuwe Testament. Uit Newtons manuscripten blijkt dat hij zijn hele leven bezig is geweest met de puzzel die de profetie voor hem was. Sommige van zijn resultaten zijn zeer opmerkelijk. Langs een tijdas staat bij het jaar 1899: Call to return to Jerusalem, en bij het jaar 1944: End of the great tribulation of the Jews [19]. In aanmerking nemend dat Newton zelf waarschuwde voor de mogelijkheid dat er een onnauwkeurigheid van 1 tot 5 jaar in zijn berekeningen zat is dit verbazingwekkend. Door veel biografen zijn de theologische en chronologische geschriften genegeerd als zijnde ketters, ongerijmd, of mystiek, de donkere zijde van de held [8]. De Franse biograaf Biot (1774 – 1862) stelde dat Newtons belangstelling voor theologie en chronologie pas aan het eind van zijn leven, in de periode van 1712 tot 1719 ontstond, en veronderstelde dat het verband hield met de geestesziekte waaraan Newton van 1693 tot 1695 geleden zou hebben. Moderne biografen laten echter niets heel van deze veronderstelling ([8], page 363, [18], page 319).

Dankwoord Geachte aanwezigen, tot slot enkele woorden van persoonlijke aard. Laat mij beginnen met te zeggen dat ik nooit heb vermoed dat mijn levensweg langs deze katheder zou leiden. Velen ben ik daarvoor dank verschuldigd. Om te beginnen mijn ouders, aan wie ik met grote dankbaarheid terugdenk. Na de MULO, HTS, militaire dienst en een toelatingsexamen aan de Technische Hogeschool Delft begon ik op 15 oktober 1964 de studie Elektrotechniek met een studiebeurs van 3200,-. Na de 2-jarige propedeuse zwaaide ik in 1966 om naar de toen 10 jaar bestaande opleiding voor wiskundig ingenieur. Met dankbaarheid denk ik terug aan mijn leermeester prof. dr. F. Loonstra, bij wie ik in 1969 afstudeerde op een onderwerp uit de coderingstheorie en in 1975 promoveerde op het gebied van de ideaaltheorie. Het doet mij een bijzonder genoegen dat mevrouw Loonstra in ons midden is. Na mijn promotie was duidelijk dat er voor de algebra in Delft geen toekomst was, en keerde ik terug naar het onderwerp van mijn afstudeerwerk: de coderingstheorie. Op maandag 10 november 1975 nam ik hierover contact op met Prof.dr. J.H. van Lint. Deze nodigde mij uit deel te nemen aan


17

het Seminarium Coderingstheorie in Eindhoven en aan de werkgroep Discrete Wiskunde van het Mathematisch Centrum in Amsterdam. Vanaf november 1975 nam ik deel aan deze bijeenkomsten. Veel huidige collega’s heb ik daar voor het eerst ontmoet, waaronder Hendrik Lenstra en Lex Schrijver. Het was een zeer inspirerende ervaring. Nadien heb ik mij de toen bedreven wijze van het beoefenen van wiskunde altijd tot voorbeeld gesteld. Hooggeleerde Van Lint, beste Jack, graag wil ik mijn dank aan jou en andere genoemde en niet-genoemde collega’s vandaag verwoorden. Jij en anderen, waaronder Dantzig, de vader van de lineaire optimalisatie, en velen van mijn huidige collega’s hebben mij doen inzien dat er geen strikte scheiding is tussen zuivere en niet-zuivere wiskunde. Wiskunde die zijn oorsprong heeft in een echt probleem is daarom niet minder interessant. Juist andersom, het maakt de uitdaging en de voldoening alleen maar groter. Hooggeleerde De Vroedt en Van Zanten, beste Cor en Jan, met dankbaarheid denk ik terug aan de vruchtbare samenwerking met jullie in die tijd. Hooggeleerde Lootsma, beste Freerk, op 11 januari 1982 nodigde jij mij uit toe te treden tot jouw leerstoel in Delft. In september van dat jaar verlegde ik mijn onderzoek naar de wiskundige optimalisatie. Het was inhoudelijk geen echte breuk, maar wekte toch wel enige verbazing. Temeer omdat ik juist in diezelfde tijd (2 april 1982) een interessante generalisatie van de zogenaamde Hartmann-Tzeng bound voor cyclische codes had gevonden. In feite was dit een bijdrage aan de oplossing van het probleem dat ik in mijn afstudeerwerk had bekeken. Na een voordracht in Oberwolfach (6 april 1982) oogstte ik veel waardering; diverse tijdschriften boden aan om de nieuwe grens te publiceren [?, ?]. Het waren voor mij hoogtijdagen. Dankzij Van Lint staat de grens nu bekend als de Roos-bound (Zie bijvoorbeeld [?]). Na de ommezwaai in 1982 begon ik met mij te verdiepen in de lineaire optimalisatie. Dit gebied had de reputatie ‘af ’ te zijn: als onderzoeksgebied werd het zelfs ‘dood’ genoemd. Na het werk van Karmarkar in 1984 bleek het tegendeel. Het gebied beleefde in de jaren daarna een ongekende bloeiperiode. Ik heb daarover hiervoor al het nodige gezegd. Aanvankelijk werd deze ontwikkeling in Nederland nauwelijks opgepakt. In betrekkelijke eenzaamheid heb ik er in de jaren 80 aan gewerkt, vooral gestimuleerd door contacten met collega’s in de Verenigde Staten en Japan. In 1989 kwam er in Delft versterking. Eerst een afstudeerder, Dick den Hertog, en kort daarna Dr. Támas Terlaky, die in dat jaar vanuit de Eötvös Universiteit in Budapest als research fellow voor 1 jaar naar Delft kwam. Dat was het begin van de Optimalisatie Groep in Delft. In de jaren erna ontwikkelde de groep zich tot een plek waar ook veel buitenlandse collega’s graag verbleven. Velen van

18


hen brachten enige tijd in onze groep door. De groep telde daardoor soms wel 12 deelnemers, de AIO’s en postdocs meegerekend. Een woord van dank is op zijn plaats voor de KNAW, de NWO en het Stieltjes Instituut: zonder de steun en erkenning van deze organisaties in de vorm van bezoekersbeurzen, reis- en congressubsidies en onderzoekersbeurzen was onze groep geen lang leven beschoren geweest. Het lopende nationale NWO-project High Performance Methods for Mathematical Optimization biedt ons een uitstekende gelegenheid om de belangstelling ook nationaal te verdiepen. Het is verheugend dat zovele gevestigde en veelbelovende onderzoekers zich in dit project hebben verenigd. Hooggeleerde Lenstra en Van der Vorst, beste Jan Karel en Henk, dank ook aan jullie voor de plezierige samenwerking bij het tot leven roepen van het project. Met ere noem ik onze Rotterdamse collega Dr. Suzhong Zhang die twee maanden geleden de Onderzoekersprijs van de Erasmus Universiteit ontving, ten bedrage van 15.000,–. Helaas zal hij het project verder vanaf een afstand moeten volgen, vanwege zijn benoeming als hoogleraar aan de Universiteit van Hong Kong. Hetzelfde geldt voor Dr. Támas Terlaky, die na 10 jaar Delft per 1 november hoogleraar is aan de McMaster University in Hamilton, Canada. Hooggeleerde Den Hertog, beste Dick, vandaag wil ik ook mijn vreugde uitspreken over jouw benoeming in Tilburg, waar je de opengevallen plaats van de huidige rector magnificus, Prof. Van der Duyn Schouten, gaat bezetten. Ik hoop dat wij spoedig de draad van onze samenwerking weer kunnen oppakken. Mijnheer de rector magnificus, voorzitter en leden van het college van bestuur, graag dank ik u voor uw medewerking aan mijn benoeming. Mijn dank gaat natuurlijk ook uit naar de leden van het algemeen bestuur van het Leids Universiteits Fonds voor de vestiging van de leerstoel en mijn aanstelling als bijzonder hoogleraar. Ik acht mij schuldig het in mij gestelde vertrouwen, door u en anderen die hebben meegewerkt aan de totstandkoming van mijn benoeming, niet te beschamen. Ik dank de leden van het Curatorium van deze bijzondere leerstoel voor hun bereidheid om mij waar nodig met hun adviezen te dienen, en toe te zien op de wijze waarop ik invulling geef aan mijn benoeming; ik hoop op een plezierige samenwerking. Hooggeleerde Zoutendijk, na een volledig professoraat van 1964 tot 1975 heeft u als eerste deze bijzondere leerstoel van 1980 tot 1985 bezet. U hebt


19

uw naam opnieuw aan de leerstoel willen verbinden door toe te treden tot het Curatorium. Dit draagt niet weinig bij aan de mate waarin ik mij vereerd voel, nu ik verantwoordelijk ben voor onderwijs en onderzoek in het vakgebied dat door u in Leiden werd ge¨ıntroduceerd, de lineaire en nietlineaire optimalisatie. Hooggeleerde Hordijk en Tijdeman, beste Arie en Rob, jullie hebben het initiatief genomen om mij voor te dragen voor benoeming op deze leerstoel. Hooggeleerde Cooke, beste Roger, jij hebt vanuit Delft bijgedragen aan dit initiatief. Jullie drieën hebben een nieuw en verrijkend aspect aan mijn leven toegevoegd. Hooggeleerde Van Dijk, beste Gerrit, ik acht mij gelukkig werkzaam te zijn aan een instituut dat onder jouw voortvarende leiding staat, al is het maar voor e´ e´ n dag in de week. Met gepaste bescheidenheid hoop ik bij te dragen aan de faam van het Mathematisch Instituut. Beste andere collegae van het Mathematisch Instituut, ik wil u bij deze gelegenheid bedanken voor de hartelijke manier waarop u mij in uw midden heeft opgenomen. Met mijn specifieke inbreng zal ik mij ervoor inspannen om bij te dragen aan het kwalitatief hoogwaardige onderwijs en onderzoek dat het Mathematisch Instituut kenmerkt. Hooggeleerde Bakker en van Katwijk, beste Eric en Jan. De TU Delft is mijn broodheer en heeft bewilligd in deze onbezoldigde aanstelling. Als toenmalig decaan en vice-decaan van de Faculteit ITS van de TU Delft hebben jullie de cruciale handtekeningen gezet die het mij mogelijk maakten de benoeming in Leiden te aanvaarden, zij het onder de voorwaarde dat het niet ten koste gaat van mijn inzet in Delft. Ik ben jullie dankbaar voor dit gebaar. Een woord aan de studenten. Ik stel jullie aanwezigheid vanmiddag op hoge prijs. Dat geldt natuurlijk voor de Leidse studenten maar ook voor de vele Delftse studenten en oud-studenten. De schoonheid en de relevantie van wiskundige modellen en algoritmen kan mij nog altijd imponeren. Er is geen groter genoegen voor een docent dan te zien dat het enthousiasme voor zijn vak aanslaat bij studenten en dat zij in de praktijk in staat zijn om de aangeleerde technieken met succes te gebruiken. Wat mij betreft hoop ik dat het mij gegeven wordt nog vele jaren met jullie en met de generaties na jullie dit enthousiasme te delen. De moraal van mijn rede was dat het hoofdstuk wiskunde in het boek der natuur een prachtig hoofdstuk is; onze westerse cultuur heeft veel te danken aan mensen die zich in het verleden en heden hebben ingespannen om in dit hoofdstuk door te dringen. Voor het begrijpen van de andere hoofdstukken in het boek der natuur is dit wezenlijk gebleken. Daarom nodig ik geta-

20


lenteerde studenten uit om mee te helpen dit boeiende hoofdstuk verder te ontcijferen. Daarmee is niet alleen een wetenschappelijk belang gediend. Dankzij de geweldige vooruitgang in de computertechnologie bestaat er in het bedrijfsleven een toenemende vraag naar universitair opgeleide wiskundigen die bedreven zijn in het wiskundig modelleren en optimaliseren van de meest uiteenlopende problemen. Tenslotte, Gerda, de laatste zin van mijn rede is voor jou. Over geen zin heb ik langer nagedacht. Uiteindelijk heb ik een zin gevonden waar jullie, Jacoline, Geranda en Marijn, het vast ook mee eens zijn. Het is een zin uit de Spreuken van Salomo: Er zijn veel goede vrouwen, maar jij overtreft ze allemaal. Moge het ons samen en ieder van ons afzonderlijk goed gaan, onder Gods hoede en zegen. Hem alleen zij alle dank en eer. Ik heb gezegd.


21

Aantekeningen Het vermoeden dat bijen hun honingraten op een optimale wijze maken stamt al ´ het begin van onze jaartelling en staat bekend als het honingraat-probleem. van vo´ or Het vermoeden is pas dit jaar bewezen door de wiskundige Thomas Hales. Een interessant overzicht van de geschiedenis van dit vermoeden werd onlangs gepubliceerd door H. Melissen [9]. Melissen wijst erop dat de laatste jaren opmerkelijk veel klassieke vermoedens zijn bewezen: behalve het eerder genoemde vermoeden van Fermat zijn ook vermoedens bewezen van Bieberbach, Kepler, Carmichael, Catalan, Mertens, Dinita, Van der Waerden, Bernstein en Seifert.

Meer gebruikelijk is de historisch gegroeide naam Lineair Programmeren (afk. LP), die sinds de opkomst van de computer echter verwarrend is: ’lineair programmeren’ heeft niets te maken met wat we tegenwoordig ‘programmeren’ noemen: de activiteit van het schrijven van een computerprogramma [20]. De Nederlander Tjalling C. Koopmans was nauw betrokken bij het ontstaan van de Simplex methode. Dantzig bezocht hem in juni 1947 en vertelde hem over zijn werk aan lineaire modellen voor het optimaliseren van militaire operaties. Koopmans herkende als in een flits de betekenis van deze benadering voor economische modellen en vertelde Dantzig dat de economen geen algoritme hadden voor het oplossen van dergelijk modellen. Diezelfde zomer ontdekte Dantzig de Simplex methode. Koopmans leidde een briljante groep van economen die de theorie van de optimale toewijzing van hulpbronnen (‘resources’) ontwikkelde met gebruikmaking van lineaire optimalisatie-modellen. Voor dit werk kreeg hij in 1975 samen met Leonid Kantorovich de Nobelprijs; Koopmans is overigens in 1936 in Leiden gepromoveerd, aan de Faculteit Wiskunde en Natuurwetenschappen. In de herfst van 1947 was er een ander contact met verstrekkende gevolgen. Dantzig bezocht toen John von Neumann. Tijdens dit bezoek werd de relatie duidelijk tussen het werk van Dantzig en de door von Neumann en Oskar Morgenstern ontwikkelde speltheorie. Ook hoorde Dantzig tijdens dit bezoek voor het eerst over Farkas’ lemma en de dualiteitsstelling voor LO.

Zoals MPSX, en later MPSX/370 van IBM, MPS III van Exxon, het UMPIRE system voor de UNIVAX 1108, APX III voor de CDC computers, LAMPS (van John Forrest) en LINDO. Voor de geschiedenis van implementaties van de Simplex methode wordt verwezen naar W. Orchard-Hays [11].

De geschiedenis van de drie eeuwenlange boeiende speurtocht naar het bewijs van de laatste stelling van Fermat is op een ongeëvenaard boeiende en erudiete wijze beschreven door Simon Singh [17]. Het tijdstip heeft Wiles nauwkeurig vastgelegd: 19 september 1994, om half vier ’s morgens. Het was alsof de bliksem insloeg. ‘A totally unexpected, incredible revelation’ noemt hij het.

Van den Beukel [3] zegt in zijn afscheidsrede: ‘Ik heb de documentaire die dit alles in beeld bracht met ingehouden adem, op het puntje van mijn stoel, bekeken.

22


Bekeken? Opgezogen, ingedronken. Ik herkende het van binnen uit: Dit is wetenschap. Ploeteren en te pletter lopen. Wegzinken en weer boven komen. Vallen en moeizaam opstaan. Dromen dromen en visioenen zien.’ Richard S. Westfall werkte 20 jaar aan zijn biografie van Newton [18]. Hij schrijft in een voorwoord: It has been my privilege at various times to know a number of brilliant men, men whom I acknowledge without hesitation to be my intellectual superiors. I have never, however, met one against whom I was unwilling to measure myself, so that it seemed reasonable to say that I was half as able as the person in question, or to a third, or fourth, but in every case a finite fraction. The end result of my study of Newton has served to convince me that with him there is no measure. He has become the wholly other, one of the handful of supreme geniuses who have shaped the category of the human intellect, a man not finally reducible to the criteria by which we comprehend our fellow beings, . . . .

Newton werd aangesteld als ’Warden of the Mint’ op 13 April 1696, door Willem de Derde (de stadhouder-koning) en als ’Master of the Mint’ op 26 December 1699 (brieven 547 en 621 in [15]). Dat hij deze taak serieus nam, en er op bepaalde momenten hogere prioriteit aan gaf dan aan wiskundige zaken blijkt uit een brief (brief 601 in [15]) aan de astronoom Flamsteed. Flamsteed had aan Newton gevraagd of hij Newtons naam mocht noemen in een van zijn publicaties. Newton schreef hem: I do not love to be printed upon every occasion much less to be dunned & teezed by forreigners about Mathematical things or to be thought by our own people to be trifling away my time about them when I should be about ye Kings business. De Koning was Willem de Derde en des Konings zaken het leidinggeven aan detectives en informanten, het verhoren van getuigen die vaak zelf criminelen waren en het veroordelen van valsemunters.

Newton’s mind was equipped with a certain fundamental assumption, common to his age, from which his various lines of investigation flowed naturally: the assumption of the unity of Truth. True knowledge was all in some sense a knowledge of God; Truth was one, its unity guaranteed by the unity of God. Reason and revelation were not in conflict but were supplementary. God’s attributes were recorded in the written Word but were also directly reflected in the nature of nature. In Newton’s conviction of the unity of Truth and its ultimate source in the divine one may find the fountainhead of all his diverse studies ([?]). De Portsmouth collectie bestaat uit honderden manuscripten. Hierin zijn ongeveer 200.000 woorden gewijd aan chronologie en niet minder dan 1.300.000 woorden aan theologie.

Dit moge blijken uit de twee volgende citaten: For the parts of Prophecy are like the separated parts of a watch; they appear confused and must be compared and put together before they can be useful, and those parts are certainly to be put together which fit without constraining ([18], p. 326). In het volgende citaat vergelijkt Newton het onderzoek van de profetie (i.e. visions) met dat van de natuur: Truth is ever to be found in simplicity, and not in the multiplicity and confusion of things. As the world, which to the naked eye exhibits the greatest variety of objects, appears very


23

simple in its internal constitution when surveyed by a philosophic understanding, and so much the simpler by how better it is understood, so it is in these visions. It is the perfection of God’s works that they are all done with the greatest simplicity. He is the God of order and not of confusion. And therefore, as they that would understand the frame of the world must endeavour to reduce their knowledge to all possible simplicity, so it must be in seeking to understand these visions. And they that shall do otherwise do not only make sure never to understand them, but derogate from the perfection of the prophecy ([?], p. 261).

Newton verdedigde het Ariaanse standpunt, versus het Athanasiaanse standpunt dat hij als een perversie van het christelijk geloof beschouwde. In een recente studie [2] stelt de Leidse theoloog A. van de Beek deze discussie opnieuw aan de orde. Het zou mijns inziens interessant zijn om in een volgende druk van dit werk ook het standpunt van Newton besproken te zien.

Newton stond bekend om zijn tegenzin om tot publicatie van zijn resultaten over te gaan. Daardoor is ook de publicatie van zijn hoofdwerk, de Principia, ca. 20 jaar vertraagd en pas op lang aandringen van anderen tot stand gekomen. Deze tegenzin zal ook bij zijn theologisch werk een rol hebben gespeeld. Daarnaast was hij zich echter terdege bewust van het risico dat publicatie met zich mee bracht. Zijn positie als de tweede ‘Lucassian professor in Mathematics at Cambridge’, sinds 1669, hing in 1675 aan een zijden draad omdat hij weigerde de eed af te leggen op de belijdenis van de Anglicaanse kerk. Hij hield er rekening mee dat hij de positie zou verliezen. Maar geheel onverwacht verleende de koning hem vrijstelling van de gebruikelijke eed ([18], p. 333). Het volgende citaat van Newton is in dit verband interessant: And when thou art convinced be not ashamed to profess the truth. For otherwise thou mayst become a stumbling block to others, and inherit the lot of those Rulers of the Jews who beleived in Christ but yet were afraid to confess him least they should be put out of the Synagoge. Wherefore when thou art convinced be not ashamed of the truth but profess it openly and indeavour to convince thy Brother also that thou mayst inherit at the resurrection the promis made in Daniel 12:3, that they who turn many to righteousness shall shine as the starrs for ever and ever. And rejoyce if thou art counted worthy to suffer in thy reputation or any other way for the sake of the Gospel, for then great is thy award. But yet I would not have thee too forward in becoming a teacher, like those men who catch at a few similitudes and scripture phrases, and for want of further knowledge make use of them to censure and reproach superiours and rail at all things that displeas them. Be not heady like them, but first be throughly instructed thy self and that not only in the prophetique Scriptures but more especially in the plain doctrines delivered therein so as to put them in practice and make them familiar and habituall to thy self. And when thou hast thus pulled out the beam out of thine own eye then shalt thou see clearly to pull out the mote of thy Brothers eye. Otherwise how wilt thou say to thy Brother, Let me pull out the mote out of thine eye and behold a beam is in thine own eye [10].

De beroemde Leidse hoogleraar Joseph Justus Scaliger (1540–1609) heeft een standaardwerk [14] geschreven dat nog steeds als een meesterwerk wordt beschouwd op het gebied van de tijdrekening [4] en dat ook door Newton is gebruikt. Deze

24


befaamde Franse humanist werd twee jaar ‘belaagd’ voordat hij toegaf en vanuit Frankrijk naar Leiden kwam voor het op dat moment hoge salaris van 1200 gulden per jaar en op de voorwaarde dat hij geen college hoefde te geven [6]. Zijn beroemdste studenten waren Hugo de Groot die in 1594 op 11-jarige leeftijd als wonderkind naar Leiden kwam en Daniel Heinsius die in 1598 naar Leiden kwam en op 25-jarige leeftijd werd benoemd als hoogleraar Grieks.

Dobbs schrijft: The purpose of attempting to interpret prophecy was not to foretell ‘times and things’, Newton said, nor ‘to gratify men’s curiosities’ about the future. God had given the prophecies so that human beings might match them with their fulfilments and so produce ‘a convincing argument that the world is governed by providence’.Just as historical facts might enable the interpreter of prophecy to choose between possible interpretations of the mysterious prophetic words, so laboratory results might enable the philosophical alchemist to choose between possible interpretations of the occult knowledge buried in alchemic texts. In either case, for Newton, it was only firm correspondence of fact with interpretation that would enable him to do what he most wanted to do: provide an irrefutable demonstration of God’s providential action the world ([?], page 165).

Verbazingwekkend zijn deze interpretaties als men bedenkt dat in 1897 het eerste Internationale Zionistische Congres werd gehouden in Basel, waar Herzl de Joden opriep om terug te keren naar Palestina om daar een Joodse staat te stichten, en verder dat het einde van de Holocaust in 1945 kan worden beschouwd als het einde van ‘de grote verdrukking van de Joden’.

Dantzig schrijft in het voorwoord van zijn klassieke boek over LO: The final test of a theory is its capacity to solve the problems which originated it [?].

Er is sindsdien geweldige vooruitgang geboekt. Dit moge onder andere uit het volgende blijken. In zijn inaugurele rede vermeldt Zoutendijk dat het is gelukt om het handelsreizigersprobleem voor de hoofdsteden van 48 Amerikaanse staten op te lossen [21]. Dat was in 1964 inderdaad een hele prestatie. Zoutendijk vermeldt verder dat dit resultaat werd bereikt door het handelsreizigersprobleem te modelleren als een gemengd geheeltallig lineair optimalisatie-probleem, en dat daarvoor analytische oplossingsmethoden ontwikkeld zijn maar dat de numerieke aspecten van deze methoden vooralsnog weinig hoopgevend zijn. Tegenwoordig is bekend dat het handelsreizigersprobleem een notoir moeilijk probleem is. In feite is het ondanks de vooruitgang in de computertechnologie voor een gemiddelde student tegenwoordig nog steeds een niet geringe prestatie om een handelsreizigersprobleem met 48 steden op te lossen. Dankzij nieuwe modelleertechnieken en nieuwe oplossingsmethoden kunnen tegenwoordig veel grotere problemen worden opgelost. Het huidige record ligt bij 7379 steden[12]. Overigens wordt het vinden van efficiënte algoritmen voor gemengd geheeltallige lineair optimalisatie-problemen nog steeds als een grote uitdaging beschouwd.


25

26


Referenties

[1] M. Aigner and G.M. Ziegler. Proofs from THE BOOK. Springer, Berlin, 1998. [2] A. van de Beek. Jezus Kurios. Uitgeverij Kok, Kampen, NL, 1998. Tweede druk. [3] A. van den Beukel. Pleidooi voor meer nutteloosheid. TU Delft, 1997. Afscheidsrede. [4] N. Dershowitz and E.M. Reingold. Calendrical Calculations. Cambridge University Press, Cambridge, UK, 1997. [5] M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach, 42(6):1115–1145, 1995. [6] J.I. Israel. De Republiek, 1477-1806, Deel I. Van Wijnen, Franeker, NL, 1996. [7] N.K. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4:373–395, 1984. [8] F. E. Manuel. Isaac Newton, Historian. Harvard Uniiversity Press, Cambridge, Massachusetts, 1963. [9] H. Melissen. Honingraatsels. ITW Nieuws, 9:21–23, 1999. [10] Is. Newton. Treatise on revelation. Unpublished manuscript. Cited in Appendix A of [?]. [11] W. Orchard-Hays. History of the development of LP solvers. Interfaces, 20(4):61–73, 1990. [12] G. Reinelt. Tsplib. A library of sample instances for the traveling salesman problem (and related problems) from various sources and of various types maintained by the author at the web site http://softlib.rice.edu/softlib/tsplib/, sept 1999. Universität Heidelberg, Institut für Angewandte Mathematik, Heidelberg Germany. [13] C. Roos, T. Terlaky, and J.-Ph.Vial. Theory and Algorithms for Linear Optimization. An Interior Approach. John Wiley & Sons, London, UK, 1997. [14] J.J. Scaliger. De Emendatione Temporum. ??, ??, 1583 (of 1593?). [15] J.F. Scott (ed.). The correspondence of Isaac Newton, vol IV. Cambridge University Press, Cambridge, UK, 1967.


27

[16] J. Simmons. The Scientific 100. A Ranking of the Most Influential Scientists, Past and Present. Carol Publishing Group, New Jersey, USA, 1996. [17] S. Singh. Fermat’s Enigma: The Quest to Solve the World’s Greatest Mathematical Problem. Walker and Company, New York, 1997. [18] R. S. Westfall. Never at Rest. A biography of Isaac Newton. Cambridge University Press, Cambridge, UK, 1964. [19] M. White. The Last Sorcerer. Perseus Books, Reading, Massachusetts, 1997. [20] H.P. Williams. Model Building in Mathematical Programming. John Wiley & Sons, New York, USA, third edition, 1990. [21] G. Zoutendijk. Informatieverwerking en Wiskunde. Universitaire Pers Leiden, Leiden, NL, 1964. Inaugurele rede.

28


Modelleren en Optimaliseren met Wiskunde Beoefening van Wiskunde in het Spoor van Newton. Rede uitgesproken door

Recommend Documents