NO865150L - Fremgangsmaater og apparat for effektiv ressursallokering. - Google Patents

Description

Teknisk område

Oppfinnelsen angår et system for ressursallokering blant et antall ressursbrukere og, nærmere bestemt,et apparat og fremgangsmåter for den effektive optimalisering av teknologiske og industrielle ressursallokeringer for minimalisering av kostnadene eller maksimalisering av utbyttet ved en slik allokering.

Bakgrunn for oppfinnelsen

Behovet for ressursallokeringsdesisjoner oppstår i

et stort spektrum av teknologiske og industrielle områder, såsom fordeling av overføringsmidler innen overførselssystemer for telefon, styringen av produktassortimentet fra en fabrikk, gruppering av industrielt utstyr, inventarovervåkning og annet. Ressursallokering i denne sammenheng betyr gruppering eller fordeling av spesifikke teknologiske eller industrielle ressurser for tilveiebringelse av spesielle teknologiske eller industrielle resultater.

Ressursallokeringsdesisjoner er typisk underlagt begrensninger knyttet til allokeringene. Ressurser er alltid begrenset i total tilgjengelighet og dessuten kan også anven-delsesmuligheten for en spesiell ressurs i en spesiell anvendelse være begrenset. For eksempel kan den totale trafikk i et telekommunikasjonssystem være begrenset og trafikkapasiteten for hvert enkelt overføringsledd i kommunikasjonssystemet er likeledes begrenset. Hver enkelt allokering av en ressurs kan knyttes til et regnskapsmessig "utbytte", dvs. en kostnad for den bestemte allokering eller en allokeringsgevinst (dvs. profitt). Problemet vil da være å allokere samtlige ressurser for å tilfredsstille alle de gitte begrensninger simultant med en maksimalisering av utbyttet, dvs. en minimalisering av kostnadene eller å bringe utbyttet til et maksimum.

En fremgangsmåte for åoppstille problemene innen allokeringsdesisjon er den såkalte lineære optimaliseringsmodell. En slik modell består av et antall lineære uttrykk som representerer det kvantitative forhold mellom de ulike mulige allokeringer, deres begrensninger og deres kostnader eller fordeler. Dette sett forhold kalles lineært dersom samtlige forhold er summer med konstante koeffisienter multi plisert med ukjente allokeringsverdier som er lik, større eller lik, eller mindre eller lik en konstant. En rekke res-sursallokeringsproblemer kan naturligvis ikke fremstilles i slike lineære forheld, men innbefatter høyere ordens ukjente eller andre ulineariteter innen forholdene som således ikke kan løses med lineære optimaliseringsmetoder.

Det skal bemerkes at de ressursallokeringspro-blemer som nå er omtalt er reelle fysiske problemer i virkelige fysiske systemer. Siden det er riktig at signifikante kvantitative aspekter ved et fysisk problem kan representeres ved hjelp av en lineær optimaliseringsmodell, er hensikten med denne modell å skaffe tilveie optimale verdier som så kan benyttes i den fysiske verden for konstruksjon eller drift av et fysisk system. Typiske eksempler fra teknikkens stand for bruken av slike matematiske modeller for å karakterisere fysiske systemer er anvendelsen av ligninger for konstruksjon av radioantenner eller styring av fremstillingen av gummi ved støping.

I sin tid ble mange av de ressursallokeringspro-blemer som har vært nevnt ovenfor løst med menneskelige ressurser ved hjelp av personers intuisjon og erfaring. Nylig er kvantitative verktøy, såsom statistikk, matematiske modeller, grafer og lineær optimalisering blitt tilgjengelige for å hjelpe enkeltpersoner i slike desisjonsforhold. For eksempel bruker fabrikkanlegg lineære optimaliseringsmodeller for å styre produksjonsforløpene og investeringer som tilfredsstiller salgsbehov og samtidig minimaliserer kostnadene for selve produksjonen og innkjøpene. Tilsvarende benytter et kommuni-kasjonssystem lineære optimaliseringsmodeller for ruting av telefontrafikk over et nettverk av overføringsmidler slik at den totale teletrafikk tilfredsstilles, intet forbindelsesledd for overførsel overbelastes og overførselskostnadene holdes på et minimum.

Det mest kjente forsøk innen teknikkens stand for

å løse allokeringsproblemer oppsatt som lineære optimaliseringsmodeller er kjent som simpleksmetoden oppfunnet av George B. Danzig i 1947 og beskrevet i Linear Programming

and Extensions av oppfinneren og utgitt av Princeton University

Press, Princeton, New Jersey, 1963. Ifølge simpleksmetoden består det første trinn i å velge en mulig startallokering som et utgangspunkt, eventuelt ved å benytte en annen lineær optimaliseringsmodell som da er en variant av den opprinnelige modell. En mulig allokering i dette henseende er en som tilfredsstiller alle begrensninger, men som ikke vites å

være optimal. Påfølgende nye allokeringer identifiseres deretter, hvilke forbedrer den funksjon som skal optimaliseres (den såkalte målfunksjon). Ovenstående prosess gjentas så iterativt, idet det forsøksvis velges nye allokeringer som stadig ligger nærmere den optimale allokering. Denne iterasjon stanses når den aktuelle forsøksvis valgte allokering ikke lenger er en forbedring av den foregående.

Simpleksmetoden kan lettere forstås ved å betrakte den forenklede grafiske fremstilling av en lineær optimaliseringsmodell vist på fig. 2 hvor det er vist en tredimensjonal fremstilling av en konveks polytop 10 med et antall delflater, såsom delflaten 11. Hver av polytopens delflater er en grafisk fremstilling av en del av en av de begrensende faktorer eller forhold i den formelle lineære optimaliseringsmodell. Det betyr at hver lineære begrensning avgrenser et plan i polytopens 10 rom, og en del av dette plan danner da en delflate av polytopen 10. Polytopen 10 er konveks på den måte at en linje som forbinder to vilkårlige punkter på polytopens overflate rommes i selve polytopen.

Her skal det bemerkes at polyto<p>en 10 er vist som

et tredimensjonalt polyeder av tegningsmessige årsaker. Polytopfremstillingen av en lineær optimaliseringsmodell opptas generelt i et hyperrom med så mange dimensjoner som antallet ukjente allokeringsverdier tilsier (som vist

på fig. 2) eller nærmere bestemt antallet begrensende ulikhetsforhold minus antallet begrensende likhetsforhold. Polytopen deler så hyperrommet i en indre hyperregion for sannsynlige eller mulige løsninger i polytopen 10 og en ytre hyperregion for ikke tenkelige eller mulige løsninger utenfor polytopen 10.

Det er vel kjent at optimale ressursallokeringer innen lineære optimaliseringsmodeller gjenfinnes på en poly tops forbindelseslinjer eller -hjørner. I enkelte modeller kan hele forbindelseslinjen mellom to hyperrom-delflater eller til og med en hel slik delflate i polytopen 10 tilsvare de optimale allokeringer, og således kan mer enn ett knutepunkt være optimalt. Strategien ifølge simpleksmetoden er å identi-fisere nærliggende knutepunkter i polytopen 10 ifølge prin-sippet for suksessive approksirnas j oner, hvorved hvert nytt knutepunkt (som hver tilsvarer et nytt mulig sett allokeringer) ligger nærmere, som vurdert i forhold til målfunksjonen, til det optimale punkt 21 enn den foregående allokering. På fig. 2 benyttes simpleksmetoden til en første identifisering av et knutepunkt 12 og deretter følges en vei 13

fra knutepunkt til knutepunkt (14-20) inntil det optimale punkt 21 nås. Simpleksmetoden er derfor begrenset til forflytning på overflaten av polytopen 10 og videre til bevegelse fra ett knutepunkt 12 på polytopen 10 til et neste knutepunkt (dvs. knutepunktet 14). Ved større lineære optimaliseringsproblemer som omfatter tusener, hundretusener eller til og med millioner variable, vil antallet knutepunkter på polytopen øke tilsvarende og i enkelte tilfeller eksponensielt. Lengden av veien 13 øker gjennomsnittlig direkte proporsjonalt med antall variable. Dessuten finnes såkalte "worst case"-problemer (minst gunstige løsning) hvor polytopens topologi er slik at en vesentlig del av knutepunktene må gjennomløpes før det optimale punkt nås.

Som et resultat av dette og av andre faktorer, vil den gjennomsnittlige beregningstid for å løse en lineær optimaliseringsmodell ved hjelp av simpleksmetoden stige mer enn proporsjonalt med kvadratet av antall begrensninger i modellen. Også for allokeringsproblemer av middels størrelse vil denne tid da kunne bli så lang at anvendelsen av modellen ikke lenger er praktisk, dvs. begrensningene vil kunne endres før beregningen av den optimale allokering er gjennomført, eller beregningstiden som trengs for å optimalisere allokeringer ved hjelp av modellen (fortrinnsvis ved hjelp av en datamaskin) blir så lang at den rett og slett ikke står til rådighet for dette formål til en overkommelig pris. Optimale allokeringer kunne tidligere vanligvis ikke utføres i "sanntid" dvs. tilstrekkelig raskt til å gi en mer eller mindre kontinuerlig styring av en pågående prosess, et system eller apparat.

En andre metode for anvendelse av lineære optimaliseringsmodeller er blitt kalt ellipsoide-metoden, og denne er lansert av N.Z. Shor i Soviet i 1970 og er beskrevet i en artikkel av L.G. Khachiyan: "A Polynomial Algorithm in Linear Programming" i Doklady Akademiia Nauk SSSR 244: S, sidene 1093-1096 fra 1979 (oversatt i 20 Soviet Mathematics Doklady 1, sidene 191-94, 1979). Ifølge ellipsoidemetoden innesluttes en polytop 30 i samsvar med fig. 3 i en ellipsoide 31 med et sentrum 32. Senteret 32 i ellipsoiden 31 kontrolleres for å fastslå om det ligger innenfor eller utenfor polytopen 30. Dersom sentrum 32 befinner seg utenfor polytopen 30, som tilfellet er på fig. 3, legges et plan 33 gjennom sentrum 32 parallelt med en delflate i polytopen 30<q>g slik at sentrum blir liggende på den motsatte side (yttersiden) av den begrensning som dennedelflate representerer. Det bestemmes så hvilken halvdel av ellipsoiden 31 som inneholder polytopen 30. På fig. 3 er det den øvre halvdel av ellipsoiden 30.

En andre, mindre ellipsoide 34 legges så om den

øvre halvdel av ellipsoiden 31 og med et sentrum 35. På ny kontrolleres sentrum 35 for å fastslå om det ligger på innsiden eller utsiden av polytopen 30. Hvis sentrum 35 ligger på utsiden (som vist på fig. 3), gjentas prosessen ovenfor inntil sentrum ligger innenfor polytopen 30. Når sentrum av den omsluttende ellipsoide så ligger innenfor polytopen 30, trekkes planet gjennom dette sentrum perpendikulært på retningen for målfunksjonen slik at polytopen 30 deles i to deler. Det bestemmes så hvilken av disse to deler som omfatter det optimale knutepunkt, her angitt med henvisningstallet 36. Nok en ellipsoide legges så rundt den halvdel av polytopen 30 som omfatter det optimale knutepunkt 36, et nytt plan føres gjennom denne ellipsoides sentrum, en kontroll utføres for å fastslå hvilken av ellipsoidens halvdeler som omslutter det optimale knutepunkt 36, og denne prosess gjentas helt til sentrum i større eller mindre grad sammenfaller med det optimale knutepunkt 36. Koordinatene for dette knutepunkt

kan så "avrundes" til eksakte verdier for de optimale allokeringer som tilsvarer knutepunktet 36 innenfor nøyaktigheten av det siffersystem som benyttes for fastleggelse av modellen i første tilnærmelse.

Selv om denne metode er teoretisk ganske enkel, skrider ellipsoidemetoden langsommere frem enn simpleksmetoden for de fleste lineære optimaliseringsmodeller av årsaker som er omtalt av R.G. Bland et al., i "The Ellipsoid Method: A Survey" i Operations Research, Vol. 29, nr. 6 (1981), sidene 1 039-1 091 .

En ny og mer effektiv metode eller fremgangsmåte

for benyttelse av lineære optimaliseringsmodeller foreligger følgelig som et behov. For eksempel vil den optimaliserende ruting av fjerntelefontrafikken innenfor et nasjonalt tele-fonnettverk omfatte et særdeles stort antall mulige forbin-delsesveier, hver med tilknyttede kostander og begrensninger. Løsninger av dette spesielle problem må dessuten tilveiebringes innenfor en fornuftig tid, dvs. en tid tilstrekkelig kort til at praktisk nytte kan trekkes ut fra løsningen ved endring av trafikkrutingen slik at de optimale verdier ifølge løsningen kan nyttiggjøres. Det er løsninger av denne type problemer som foreliggende oppfinnelse er rettet mot.

Oversikt over oppfinnelen

I samsvar med den illustrerte gjenstand som foreliggende oppfinnelse representerer, kan en optimal ressursallokering finnes langt hurtigere enn tidligere mulig ifølge de beste ressursallokeringsmetoder innen teknikkens stand. Nærmere bestemt kan benyttelsen av prinsippene i samsvar med foreliggende oppfinnelse føre til løsning av enkelte lineære optimaliseringsmodeller i sanntid, dvs. tilstrekkelig raskt til å muliggjøre større eller mindre grad av kontinuerlig styring av et system eller apparat. Andre allokeringsproblemer kan løses tilstrekkelig hurtig til å gjøre lineære optimaliseringsrutiner økonomisk attraktive i motsetning til de lineære optimaliseringsmetoder i henhold til teknikkens stand som ikke var økonomisk tenkelige. Endelig kan noen allokeringsproblemer som tidligere var ansett så omfattende at lineær optimaliseringsteknikk ikke engang var tenkt mulig, effektivt løses ved anvendelse av den lineære optimaliseringsfremgangsmåte som nå foreligger i samsvar med oppfinnelsen .

Fremgangsmåten for å oppnå disse markant forbedrede fordeler og som vil bli omfattende beskrevet i det følgende, kan forstås ved betraktning av den tredimensjonale polytop 50 på fig. 1. Polytopen 50, såvel som polytopene 10 og 30 på hhv. fig. 2 og 3, har et antall delflater som tilsvarer be-grensningsplanene, et antall kanter som representerer skjæ-ringslinjene mellom de enkelte delplan og et antall knutepunkter eller hjørner som tilsvarer forbindelsen mellom kantene. Hvert punkt på overflaten av polytopen 50 og hvert punkt i det indre av denne representerer en sannsynlig eller mulig allokering av ressurser, dvs. en allokering eller fastlagt fordeling som møter alle gitte begrensninger. Koordinatene for hvert punkt fremstiller da størrelsen av alloke-rings verd i ene .

I samsvar med foreliggende oppfinnelse velges et punkt 51 i polytopens 50 indre som et allokeringsstartpunkt. Påfølgende trinn eller veier 52, 55 og 56 gjennomløpes deretter i det indre av polytopen 50 langs en totalvei som nærmer seg det optimale allokeringspunkt 53. Siden lengden av hvert trinn eller vei ikke begrenses av avstanden mellom^ to nabo-hjørner (som ifølge simpleksmetoden), kan langt større trinn gjennomløpes, færre antall trinn behøves, og tiden som trengs for å finne den optimale allokering kortes ned.

I detalj velges et tilfeldig eller systematisk selektert allokeringspunkt 51 i det indre av polytopen 50

som startpunkt. Ved å benytte en lineær endring av alloke-ringsvariable som opprettholder lineariteten og konveksiteten, kan disse variable i den lineære optimaliseringsmodell trans-formeres slik at startpunktet holdes nær sentrum av den transformerte polytop og samtlige delflater i større eller mindre grad holdes i samme avstand fra sentrum. Denne ekvi-distanseprosedyre kan kalles normalisering, sentrering, ekvidistanse-normalisering, normaliserende transformasjon eller en sentrerende transformasjon. Det neste allokeringspunkt velges ved forflytning i en retning langs den negative gradient

for målfunksjonen i den retning som samsvarer med den maksimale konvergensgradient (direction of the steepest descent) og i en avstand som bestemmes av begrensningene for polytopens "grenseflater" i det flerdimensjonale rom (for ikke å beveges ut av polytopens indre). Endelig utføres en invers transformasjon for å bringe det nye allokeringspunkt tilbake til de opprinnelige variable, dvs. til hyperrommet for den opprinnelige polytop. Ved å bruke det transformerte nye punkt som det neste startpunkt, kan denne prosess gjentas.

Siden hvert trinn foregår radialt innenfor polytopen i stedet for rundt polytopens omkrets, trengs langt færre trinn for å konvergere mot det endelige optimalpunkt.

Når et valgt indre punkt befinner seg tilstrekkelig nær optimalpunktet, dvs. innenfor nøyaktighetsgrensene som er fastlagt når problemet ble oppsatt, kan optimalpunktet bestemmes ved avrunding av de oppnådde verdier til nøyaktighetsgraden for det opprinnelige problem ved fastleggelse av de begrensninger (delflater) som den optimale løsning omfatter eller et annet stoppkriterium som kjennes fra teknikkens stand.

Hovedfordelen med foreliggende oppfinnelse er den hastighet som de variable for ressursallokeringen kan oppnås med. Denne hastighet muliggjør ikke bare en langt mer effektiv beregning av den optimale ressursallokering enn det som tidligere har vært mulig ved hjelp av simpleks- eller ellipsoidemetoden, men det åpnes nå for første gang muligheten av å utføre praktisk ressursallokering i sanntid Foreliggende oppfinnelse gir også for første gang muligheten av ressursallokering i systemer som hittil har vært alt for store til å kunne utføres i løpet av en fornuftig tid ved hjelp av de tidligere kjente metoder.

Muligheten for allokering av ressurser i sanntid dvs. raskt nok til å kunne brukes dynamisk ved styring av en fortløpende prosess, åpner muligheten for styring av optimal allokering og omgruppering av ressurser kontinuerlig etter hvert som de ytre betingelser (begrensninger) endres, innenfor fabrikasjons-, produksjons-, navigasjons- og teletrafikkveis-dirigeringsprosesser. I tillegg kan særdeles store systemer for ressursallokering, hvilke tidligere ikke kunne styres i løpet av en praktisk tilgjengelig tidsperiode, nå hurtig underlegges styring ved å benytte den teknikk som den foreliggende oppfinnelse presenterer.

Kort beskrivelse av illustrasjonene

Fig. 2 er en grafisk fremstilling av den kjente simpleksmetode for bestemmelse av en optimal ressursallokering ifølge lineære optimaliseringsmodeller, fig. 3 er en grafisk fremstilling av den kjente ellipsoidemetode for bestemmelse av optimal ressursallokering for løsning av lineære optimaliseringsproblemer, fig. 1 er en grafisk fremstilling av fremgangsmåten ifølge foreliggende oppfinnelse for bestemmelse av optimal ressursallokering for løsning av lineære optimaliseringsproblemer, fig. 4 er et generelt flytdiagram for den lineære optimaliseringsfremgangsmåte i samsvar med foreliggende oppfinnelse, fig. 5 er et mer detaljert flytdiagram av en variant av fremgangsmåten ifølge oppfinnelsen og som benytter projiserende transformasjoner for bestemmelse av de optimale ressursallokeringer, fig. 6 er et blokkdiagram av et ressursallokeringssystem som anvender fremqangsmåten ifølge fig. 4 eller fig. 5 for styring av ressursallokerin-gene, fig. 7 er en skisse av et forenklet allokeringsproblem for teletrafikkveisdirigering hvor foreliggende oppfinnelse vil kunne anvendes, og fig. 8 er et generelt blokkdiagram av en telefonruteinnretning bygget i samsvar med foreliggende oppfinnelse og som benytter fremgangsmåten ifølge fig.4

eller fig. 5.

Detalj beskrivelse

Den nye fremgangsmåte for å utføre optimale ressursallokeringer ved hjelp av en lineær optimaliseringsmodell vil nå gjennomgås først, og deretter vil anvendelsen av denne metode i teknologiske og industrielle ressursalloke-ringssystemer, apparater og fremstillingsmetoder tas opp.

Den formelle fastleggelse av en lineær optimaliseringsmodell (linear programming model) tar form av en målfunksjon som søkes bragt til sitt maksimum eller minimum,

idet det tas hensyn til et antall begrensningsforhold som uttrykker de fysiske begrensninger som eksisterer i forbindelse med de mulige allokeringer. Disse begrensninger tilsvarer og

representerer så nøyaktig som mulig de aktuelle fysiske begrensninger som foreligger i det fysiske system. I standard vektorangivelse uttrykkes en typisk lineær optimaliseringsmodell som følger: Finn en vektor x av lengde n for

minimalisering av:

underlagt: og

hvor c = (c-|,C2/..., cn) er en vektor for kostnadskoef-fisientene, toppindeksen T representerer en transponert matrise, x = (x-|,X2, ..., xn) , er en vektor for allokeringsverdier, n er antallet slike allokeringsverdier, A =

(a-|i, a-] 2> • • •/ ai j ' • • • > amn' er en Hl ganger n-matrise for begrensningskoeffisientene , b = (b-j, b2, ..., bm) er en vektor med m konstanter, L = (li, 12/ • • •/ ln) og U =

(ui,U2, ..., un) er henholdsvis den nedre og øvre grense for verdiene for x- Typisk begrenses verdiene for komponentene av x (allokeringsverdiene) til ikke-negative verdier, men andre grenser er også mulige. Alle målfunksjoner og alle begrensningsforhold kan reduseres til denne form ved enkel algebraisk omvandling. Begrensninger av formen "større eller lik" kan f.eks. endres til begrensninger av formen "lik" ved addisjon av tilleggsvariable til begrensningsmatrisen. Tilsvarende kan begrensningsuttrykk av typen "mindre eller lik" endres til uttrykk av formen "lik" ved addisjon av gitte slakkvariable ("slack" variables/Schlupfvariable) . Disse teknikker er velkjente innenfor teknikkens stand.

I samsvar med foreliggende oppfinnelse overvinnes ulempene fra både simpleks- og ellipsoide-metodene ved anvendelse av en fullstendig forskjellig strategi for allokering av ressurser med en lineær optimaliseringsmodell. Simpleks-metoden omfatter en usikker antagelse over hvilken av de ulike komponenter x.i av x som vil befinne seg ved grensen (xi =0) i en optimal x, og deretter revideres denne antagelse med en komponent i x ad gangen etter hvert som algoritmen skrider frem, inntil et optimalt sett x-allokeringskomponenter oppnås. Ifølge foreliggende oppfinnelse selekteres komponenter i x hvilke er mulige eller sannsynlige i strengeste forstand (som befinner seg innenfor polytopen), dvs. slik at Ax = b og L < x < U. Med uttrykket "strengt mulig" som vil bli benyttet i det følgende, menes verdier som tilfredsstiller alle begrensninger, men likevel ikke er lik grenseverdiene.

En lineær endring av de variable utføres så for komponentene

i x slik at en enhetsendring av den endrede variable komponent tilsvarer en komponent i x som befinner seg nær grensen og tilbakeføres til en mindre endring i den opprinnelige x-komponent enn en endret komponent som tilsvarer en x-komponent i større avstand fra grensen. Denne prosess kalles normalisering, sentrering, ekvidistanse-normalisering, normaliserende transformasjon eller sentrerende transformasjon, som nevnt tidligere. Retningen for det maksimale konvergenskriterium bestemmes så i de. nye variable og føres tilbake til et "ret-ningstrinn" i de opprinnelige variable. Et trinn utføres så

i denne retning og med en størrelse som sørger for at de nye komponenter i x også er strengt mulige, dvs. lj, < x9Y < U-j_.

Den fremgangsmåte som er omtalt ovenfor er skjematisk angitt på fig. 4. Som vist på denne figur er det først nød-vendig å formulere den lineære optimaliseringsmodell som antydet i blokken 160. Et strengt mulig startpunktxsta<rt>velges så i blokk 161 og det første, gjeldende iterasjonstrinnxcur<r>fastsettes for startpunktet xstart i blokk 162. Den teknikk som benyttes for å velge ut det strengt mulige startpunkt vil omtales i det følgende. Den nedre del av fig. 4, angitt i den strekpunkterte hovedblokk 163, er selve iterasjonsprosessen i fremgangsmåten ifølge foreliggende oppfinnelse.

Blokken 163 for iterasjonsprosedyren (fig. 4) omfatter følgende trinn: Gitt en strengt mulig iterasjon av komponentene x: 1) I blokk 164, velg en endring av de variable som normaliserer den gjeldende eller inneværende iterasjon i forhold til grensene, 2) i blokk 165, beregn retningen for det maksimale konvergenskriterium i de nye variable og overfør denne retning til de opprinnelige variable, 3) i blokk 166, skrid frem i den overførte retning med en verdi som holder den nye iterasjon for komponentene i

x fortsatt strengt mulige, og

4) i desisjonsblokken 167, avslutt iterasjonsprosessen når ingen signifikant forbedring lenger observeres i målfunksjonen. Hvis dette ikke er tilfelle, sett den nye iterasjon x<ny>lik den inneværende iterasjon xcurr i blokken 169 og vend tilbake til blokk 164 for gjentagelse av trinn 1 ) til 4).

En metode for å stoppe iterasjonsprosessen er ved simultan løsning av både den "primale" lineære optimaliseringsmodell og den "duale" modell. Hvis primalmodell uttrykkes som:

Minimaliser:

underlagt:

og kan dualmodellen uttrykkes som: Maksimaliser: underlagt:

Disse to modeller har den samme optimale målfunksjon, men iterasjonsprosessen nærmer seg disse optimale verdier fra ulike retninger. Man kommerså nær som ønsket til de optimale verdier ved selektering av tilstrekkelig små forskjeller mellom den aktuelle verdi for den primale målfunksjon og den aktuelle verdi for den duale målfunksjon. Andre stppprutiner er tilgjengelige innenfor teknikkens stand og kan likeledes anvendes.

Det skal bemerkes at fremgangsmåten ifølge foreliggende oppfinnelse ikke inkluderer forflytning på overflaten av polytopen og det finnes heller ingen begrensninger i trinnstørrelsen ut fra avstanden av tilliggende hjørner i denne. Følgelig kan foreliggende fremgangsmåte i utgangspunktet gi en langt raskere forflytning mot det optimale punkt, og færre trinn kreves. Oppfinnelsen gir således både en betydelig forbedring i hastighet i forhold til de tidligere kjente simpleks- og ellipsoide-metoder for nær sagt alle typer optimaliseringsmodeller, og denne fordel øker med modellens størrelse (antall variable). Det åpnes følgelig for muligheten av å kunne løse lineære optimaliseringsmodeller tilstrekkelig hurtig til at dette kan utføres i dvs. før forholdene endres så mye at løsningen ikke lenger er gyldig eller anvend-bar. I tillegg til dette er det nå mulig å løse større lineære optimaliseringsmodeller (som involverer et særdeles stort antall variable) som ellers ikke tidligere kunne løses innenfor et rimelig kostnadsnivå under benyttelse av simpleks- eller ellipsoidemetodene.

Et av de viktigste forhold ved den fremgangsmåte

som er omtalt ovenfor er valget av endringer i de variable i trinn 1) nevnt ovenfor. Denne endring av de variable kan fremstilles som en diagonalmatrise D. For å kunne utføre normaliseringsfunksjonen ved plassering av den inneværende iterasjon i en avstand som hovedsakelig er den samme til samtlige grenser, må verdien av det _i-te diagonalledd i D

være liten når x±enten er nær L-^eller . Et åpenbart valg for det _i-te diagonalledd i D er:

hvor x<curr>er den gjeldende eller inneværende iterasjon i x. Hvis grensene representerer svært store verdier eller hvis x er ubegrenset i positiv eller negativ retning, bør en passende grense likevel legges ved D-^, dvs.

Det er mulig å holde visse ledd i D konstante over mer enn ett iterasjonstrinn, spesielt hvis komponenten ikke har endret seg mye eller hvis den tilsvarende x-komponent befinner seg i stor avstand fra grensen.

Søkeretningen for det neste iterasjonstrinn er

gitt av

hvor I_ er enhetsmatrisen (alle ledd i hoveddiagonalen lik 1 )

og toppindeks T angir at matrisen er transponert (linjer og spalter ombyttet). Fra et EDB-synspunkt er den vanskeligste oppgave invertering av et matriseprodukt og for å kunne utføre dette er det praktisk å anvende suksessiv approksimasjon eller inkrementerende endring.

Verdien for den nye iterasjon kan utrykkes som

hvor a er verdien eller størrelsen av trinnet i den retning som anvises av p_. For å kunne holde den nye iterasjon x<ny>

strengt gyldig eller mulig, må a være mindre enn avstanden til nærmeste grense. Dette kan løses enkelt ved en liten forflytning 6 mot nærmeste grense (dvs. a =

Verdien for S må være mindre enn 1.

Det skal bemerkes at den fremgangsmåte som er beskrevet ovenfor krever et strengt gyldig eller mulig startpunkt, dvs. et punkt som ligger innenfor polytopen. Et slikt punkt kan enkelt fastslås i visse situasjoner, men i det generelle tilfelle vil man ikke være sikker på om det i det hele tatt finnes et slikt mulig område. Et første trinn for anvendelsen av fremgangsmåten som er beskrevet, vil da være å bestemme om det i det hele tatt finnes en løsning for den lineære optimaliseringsmodell og, dersom dette er tilfelle, hvilken verdi et strengt mulig startpunkt får. Fra tidligere kjennes dette som gyldighetskriteriet, og løsningen av dette må vanligvis først finnes før løsningen av selve den lineære optimaliseringsmodell for å komme frem til optimale verdier for ressursfastleggelser.

I fortsatt samsvar med foreliggende oppfinnelse

kan en variasjon av den fremgangsmåte som er beskrevet ovenfor benyttes for løsning av gyldighetskriteriet for lineære optimaliseringsmodeller. Ifølge simpleksmetoden utføres dette ved addisjon av tillagte slakkvariable til begrensningsforholdene og ved den etterfølgende anvendelse av simpleksmetoden vil man kunne finne om summen av disse tillagte variable kan reduseres til null for visse sett allokeringsverdier. Hvis dette ikke er tilfelle, er problemet ugyldig og således ikke løsbart. Hvis summen konvergerer mot null,

vil de allokeringsverdier som tilfredsstiller denne konver-tering kunne benyttes som et startpunkt. I praksis vil en ny målfunksjon benyttes for begrensningsforholdene, dvs. summen av de tillagte variable vil søkes minimalisert.

En tilsvarende strategi benyttes for løsning av gyldighetskriteriet i samsvar med foreliggende oppfinnelse. Siden et strengt mulig startpunkt er nødvendig som utgangspunkt, må den nye målfunksjon settes opp slik at dette kan oppnås. Hvis spesielt den lineære optimaliseringsmodell er løst slik at det i hvert trinn søkes minimalisert avstanden fra grensen for de ugyldige allokeringsverdier, vil de allokeringsverdier som fremkommer fra løsningen av dette gyldighets-kriterium være strengt mulige og kan derfor benyttes som et utgangspunkt for hovedfremgangsmåten. Ifølge dette kan gyldighetskriteriet fastlegges som:

Minimaliser:

underlagt:

og

Startpunktet for denne fremgangsmåte kan være en hvilken som helst verdi av x som tilfredsstiller grensebetingelsene eller begrensningene Ax = b. Nok en utgangsprosedyre er beskrevet i en artikkel av N.K. Karmarkar: "A New Polynomial-Time Algorithm for Linear Programming" i Proceedings of the ACM Symp. on Theory of Computing, 30. april 1984.

En rekke variasjoner av leddene i diagonalmatrisen D er mulige så lenge som normaliseringskriteriene er opprett-holdt. Tilsvarende kan en rekke variasjoner rundt verdien for a tillates såfremt det neste iterasjonstrinn er strengt gyldig, dvs. at dette trinn ikke medfører noen bevegelse ut fra polytopens indre. En slik alternativ tilnærmelse til normalisering er beskrevet i den ovenfor nevnte publikasjon, og den prosedyre som fremgår av denne tillater en endring av de variable (en projiserende transformasjon), idet det utledes den retning som tilfredsstiller kriteriet for den maksimale konvergens for en potensfunksjon (som vil bli omtalt nærmere i det følgende) på basis av denne endring i de variable, hvorved det forflyttes en viss avstand i denne utledede retning slik at det neste iterasjonstrinn fremdeles er strengt gyldig, hvoretter det fremkomne punkt overføres tilbake til de opprinnelige variable. Endringen i de variable som omtales i denne publikasjon velges slik at den inneværende iterasjon x overføres til sentroiden i simpleksmodellen og således på en måte får samme avstand fra alle "ulikhets-begrensninger".

Problemet fastlegges først som:

Minimaliser:

underlagt:

og Heller enn å forsøke å minimalisere c<T>x direkte, angir den publiserte fremgangsmåte trinn som konvergerer en potensfunksjon som defineres som

hvor c er en modifisert form av c som er valgt slik at den optimale løsning _x°Pt av ligning (8) også er en løsning av denne ligning (8) når c erstattes av c og tilfredsstiller: cx°P<t>= 0 og hvor det benyttes en "glidende mål"-metode for å oppnå de nedre og øvre grenser for verdien av den optimale målfunksj on.

I denne artikkel reduseres algebraiske problemer ved å gi begrensningene en spesiell form:

Minimaliser underlagt:

hvor e er en enhetsvektor. Dette foregår ved å addere nok en komponent til x, og tillegge en tilsvarende spalte med null-ledd til A, skalering av A i samsvar med dette, og subtraksjon av be<T>fra resultatet. Med problemet overført til den spesielle form som ligning (10) tilsier, kan fremgangsmåten oppsummeres som vist i flytdiagrammet ifølge fig. 5. Med optimaliserings-modellen oppsatt i denne form, benyttes en passende skalerende matrise for verdiene som fremkommer fra det inneværende ite-ras j onstrinn , dvs. D^i = x^. Problemet overføres videre til et problem ifølge simpleksmodellen for å redusere kompliserte datamaskinberegninger.

På fig. 5 er i blokk 60 vist hvordan det lineære optimaliseringsproblem er oppsatt i standard form. I blokk 61 er et startpunkt x<start>valgt i polytopens indre og hvis mulig i forbindelse med en gyldighetsbestemmelse som antydet ovenfor. Ved å benyttexsta<rt>som det første iterasjonstrinnxcur<r>, skisseres fremgangsmåten for utvikling av det neste iterasjonstrinn x<n>^ i den nedre del av fig. 5, angitt med den strekpunkterte blokk 68. Trinnene i denne blokk er føl-gende :

1 . Velg en diagonalmatrise D hvis i.-te diagonalledd er: d^=x9<urr>. Dette valg bestemmer den projiserende transformasjon for den variable x' ifølge ligningene

og

hvor x' angir de første n komponenter av den (n + 1)-te vektor x'. Denne projiserende transformasjon kan tenkes som en ortogonal transformasjon til en simpleksmodell og derved oppnås den normaliserende eller sentrerende egenskap. Blokk 62 indikerer denne normaliseringstransformasjon av de variable til nullrommet i en affin simpleksmodell. 2. Beregn retningen p_ for den transformerte målfunksjon i samsvar med kriteriet for maksimal konvergens ut fra den inneværende iterasjon, idet denne retning nå føres frem mot sentroiden i simpleksmodellen. Denne retning er gitt av:

hvor

Beregningen er antydet i blokk 63 på fig. 5.

3. Velg en verdi for a (a > 0) slik at

x'nv = x' + ap og slik at x'nY er strengt gyldig, dvs. større enn 0 og hvor samtidig potensfunksjonen g(x') avtar (fortrinnsvis ved konvergering mot et minimum). Potensfunksjonen her er g(x') = f(T(x)), hvor

Dette trinn er vist i blokk 66 på fig. 5.

4. Beregn {x<ny>= T(x'<ny>)} hvor T er gitt av ligningen (14). Dette er vist i blokk 67 på fig. 5.

Etter fullførelsen av den iterasjonsprosess som er antydet i den strekpunkterte blokk 68 på fig. 5, kan et hvilket som helst stoppkriterium, inkludert de som er nevnt ovenfor, benyttes i desisjonsblokken 69. Hvis stoppkriteriet tilfredsstilles i denne blokk 69, er prosedyren fullført og stanser i den avsluttende blokk 70. Hvis stoppkriteriet ikke tilfredsstilles i desisjonsblokken 69, foregår substitusjonen ved at den beregnede neste iterasjon x<n>Y erstatter den gjeldende iterasjon x<curr>i blokk 71 og blokk 62 gjennomløpes på

ny for det neste iterasjonstrinn.

På fig. 6 er vist et system for prosesskontroll

hvor en prosess 80 styres. Prosessen 80 kan være et system for telekommunikasjon, en fremstillingsprosess, en naviga-sjonsprosess eller enhver annen industriell eller teknologisk prosess som ønskes underlagt en optimalisering. Et kostands-register 81 mottar kostnadsdata over linjer 82, hvilke data representerer kostnadene pr. enhet for de forskjellige mulige ressursallokeringer i den styrte prosess 80. Kostnadsdata kan tilføres registeret 81 fra en datamaskin eller fra separate prosesser som bestemmer disse kostnader rent dynamisk. Selv om disse kostnadsdata vanligvis endres relativt langsomt, er det likevel anordnet en mulighet for oppdatering av disse data via en inngangslinje 82 hvis nødvendig. Dersom det finnes grenser (L og U i ligning (1)) forskjellige fra 0 for løsningsverdiene, må disse grenser såvel som kostnadsdata tilføres en styreenhet 85 for den lineære optimalisering via et datainngangsregister, såsom registeret 81.

Tilsvarende er det anordnet et grenseregister 83

for lagring av data for de totale fysiske begrensninger som er tilknyttet hver enkelt ressursallokering. Disse grensedata er likeledes relativt statiske og kan tilføres via en linje 84 til registeret 83 fra en datamaskin eller fra separate prosesser som bestemmer disse grenser. Utgangene fra registrene 81 og 83 tilføres styreenheten 85 som utfører den prosess som er gjennomgått i forbindelse med fig. 4 eller 5. Styreenheten 85 er i den foretrukne utførelsesform en programmert datamaskin som i sitt lager har det program som tilsvarer flytdiagrammet ifølge fig. 4 eller 5. Styreenheten 85 kan også omfatte et kretskompleks av mer maskinvarelignende type bestemt for å utføre prosedyrene ifølge fig. 4 eller 5, et antall parallelle prosessorer for å nyttiggjøre mulighetene for parallell utførelse av prosedyren eller et antall lineære grupperinger som er programmert for dette formål.

Et antall begrensningssensorer 86, 87 ..., 88 er anordnet for dynamisk registrering av begrensningskoeffisientene som representerer de begrensende forhold. Begrensningssensorene 86-88 føler kontinuerlig endringer i omgivelsene for den styrte prosess 80, idet disse endringer påvirker begrensningsforholdene og således må overvåkes for å kunne styre prosessen 80. Hver av begrensningssensorene 86-88 har en tilsvarende differensialdetektor 89, 90, ...,91, indikert med A, og disse detekterer registrerer forandringer i utgangen fra hver av de respektive sensorer 86-88. Et signal som indikerer forandringen fra hver av detektorene 89-91 føres over en skiftlinje 92 til en OG-port 93. Til denne port 93

er også ført en linje 94 fra styreenheten ,85, og på denne linjen 94 tilføres et "utført"-signal som angir avslutningen av optimaliseringsforløpet. Utgangene fra sensorene 86-88 tilføres via de respektive differensialdetektorer 89-91 til styreenheten 85 for den lineære optimalisering.

Under drift føres utgangen fra sensorene 86-88 til styreenheten 85 for å danne koeffisientene i begrensningsmatrisen A i ligning (1). Kostnadsdata i registeret 81 benyttes som kostnadsvektoren (c) i ligning (1) og grensedata i registeret 83 benyttes som begrensningsvektoren (b) i ligning (1). Når disse inngående data er ført til styreenheten 85,

kan denne starte sin prosedyre i samsvar med fig. 4 eller 5

og fremskaffe digitale løsningsverdier (x<1>) for styring av registrene 95, 96, ..., 97. Verdiene i disse registre benyttes så for styring av prosessen 80.

Siden styreenheten 85 ifølge fig. 6 benytter de særdeles raske iterasjonsrutiner ifølge fig. 4 eller fig. 5, oppnås tilgjengelige styreverdier for registrene 95-97 i løpet av svært kort tid. Når grensebetingelsene endres vil videre disse registreres av sensorene 86-88 detekteres av differensialdektorene 89-91 og kunne brukes til delvis åpning av OG-porten 93. Når rutinen i samsvar med fig. 4 eller fig. 5 er fullført, genererer styreenheten 85 styresignaler og overfører dem til registrene 95-97 samtidig som den genererer et åpningssignal over linjen 94 til porten 93 slik at denne OG-port 93 åpnes i samsvar med OG-kriteriet. Deretter repeteres hele iterasjonsforløpet.

Avhengig av problemets kompleksitet (antallet begrensninger som registreres av sensorene 86-88) og stabiliteten av prosessen 80, er det mulig kontinuerlig å utføre styring av prosessen i større eller mindre grad ved hjelp av denne fremgangsmåte. Det er faktisk slik at hvis endringsraten for de omgivende faktorer som registreres av sensorene 86-88 er mindre eller lik driftsraten for styreenheten 85, vil prosessen 80 kunne styres kontinuerlig. Høyere endringsrater i omgivelsene vil innføre diskontinuiteter i styreprosessen, men det vil fortsatt være mulig å utføre en gjennomsnittlig tilnærmet optimal styring av prosessen 80. Når det erfaringsmessig kjennes visse typiske endringer i omgivelsesfaktorene, kan en viss grad av forhåndsinformasjon bygges inn i detektorene 89-91 for å sannsynliggjøre retningen og størrelsen av frem-tidige endringer i utgangene fra sensorene 86-88.

Et typisk problem innen telekommunikasjon hvor foreliggende oppfinnelse kan anvendes er beskrevet i to artikler i The Bell System Technical Journal, Vol. 60, nr.

8, oktober 1981. Den første artikkel "Design and Optimization of Networks with Dynamic Routing" av G.R. Ash et al. (side 1787) beskriver trafikkveisdirigeringsproblemer innen tele-fonteknikk generelt, mens den andre artikkel "Servicing and Real-Time Control of networks with Dynamic Routing" av samme forfatter (side 1821) beskriver et tilknyttet problem hvor det gjelder å redusere til et minimum den tomgangskapasitet som foreligger grunnet feilaktig forhåndsbestemmelse av trafikkintensiteten. Beskrivelsen benytter i det følgende begge disse artikler som referanse.

Som det fremgår av det forenklede oversiktskart på fig. 7, består det amerikanske nasjonale telefonnett av et stort antall overføringsmidler for telekommunikasjon som forbinder et tilsvarende stort antall telefonsentraler. Telefonsamtaler fra ett punkt i nettet må rutes via overføringsmidlene til nærmere bestemte telefonsentraler og

-stasjoner i en annen del av nettverket. Hvert forbindelsesledd i overføringen har en tilknyttet kostnad såvel som en maksimal trafikk-kapasitet eller kapasitetsbegrensning. Trafikkvolumet som for øvrig passerer hvert knutepunkt er

nok en variabel. Telefonnettet skal så benyttes for å rute alle samtaler til det ønskede bestemmelsessted via den rime-ligste rute eller dirigerte trafikkvei uten samtidig å over-stige noen av kapasitetsbegrensningene. I styresystemet for dette telefonnett er målfunksjonen summeringen av alle kostnader for ruting av trafikken over samtlige mulige overfø-ringsledd, dvs. c er kostnadskoeffisienten og x er forbindel-sesleddets trafikkintensitet. Begrensningskoeffisientene (a^j) representerer overføringsleddenes kapasitet (som ikke kan overskrides) og trafikkintensitetene (som må avvikles). Som i det generelle system vist på fig. 6, kan kun tillates positive verdier av overføringsleddenes intensitet (x^>0).

Nærmere bestemt kan et trafikkveisdirigeringssystem for teletrafikk fremstilles som en lineær optimaliseringsmodell som vist i referansen:

Minimaliser:

underlagt:

i = 1 , 2, ..., L; h= 1 , 2,..., H

h = 1 , 2, ... , H; k = 1 , 2 , ... , K

r^k > 0, ai > 0

hvor L = det totale antall forbindelsesledd i nettet,

K = antallet behovspar (tilbudt intensitet),

H = antallet brukstimer,

jf<k>1= antallet ruter eller trafikkveier for

behovsparet k i løpet av timen h,

Pj^= den relative trafikkintensitet på trafikkvei j_ for det punktvise behovspar k på overføringsleddet jl i løpet av timen h,

Mj_ = kostnadsdifferensialet for et overføringsledd uttrykt som et beløp pr. erlang for den avviklede trafikk i overf øringsleddet _i,

R^= den tilbudte intensitet for behovsparet k

i timen h,

r*1, = den avviklede trafikkintensitet over trafikk-veien j_ for behovsparet k i timen h,

Ah. = den tilbudte trafikkintensitet for over-

l

f ørings leddet jL i løpet av timen h,

a± = den maksimale trafikkintensi tet på overføringsleddet i_ over samtlige timer,

= trafikkblokkering på trafikkvei j_ for

behovsparet k i timen h,

b^ = blokkeringen på overf ørings ledd i_- i timen h.

Et system for løsning av denne type lineær optimaliseringsmodell er vist på fig. 8.

Fig. 8 viser således en iterasjonssløyfe for trafikkveisdirigering for et telefonnett 100. Systemet ifølge fig.

6 søker å finne den korteste (mest økonomiske) trafikkvei, dvs. 101, 102, 103 mellom punkter, dvs. 104, 105 i nettet 100. Aksepterbare blokkeringsnivåer er antatt (eller aktuelle blokkeringer er målt i diagrammets blokk 106) og en dirige-ringsenhet 107 danner trafikkveiene 101, 102, 103 som forsøks-ruter (trafikkveistrinn). Dirigeringsenheten 107 bestemmer også den relative trafikkmengde som tilbys hver trafikkvei i ruten for hver enhet for tilbudt trafikkintensitet, hvor denne kontinuerlig tilføres fra trafikkbehovet, angitt ved blokken 109. Styreenheten 108 for lineær optimalisering dirigerer så trafikkvolumet til forsøksrutene for reduksjon av kostnadene for den totale trafikkveisdirigering. Styre-enhetens 108 utgang er den optimale ruteplan som så kan benyttes av rutetabeller i blokken 110 for styring av trafikkvolumet over hvert overføringsledd.

Trafikkveisdirigeringssystemet ifølge fig. 8 kan benyttes for fortløpende styring av telefonnettet eller for styring i regelmessige intervaller. Med de langt raskere prosedyrer som følger flytdiagrammene på fig. 4 og 5, er det nå mulig å benytte systemet ifølge fig. 8 for dynamisk styring av telefonnettet i samsvar med endringer i behovet og den momentane overføringskapasitet i hvert enkelt ledd.

Det kan vises at løsningen for dette dirigeringspro-blem sørger for at hvert enkelt overføringsledd til enhver tid får optimal trafikkintensitet og dette betyr optimal trafikkveisdirigering for samtlige telefonanrop. Siden et nasjonalt telenett omfatter et særdeles stort antall overføringsledd er den tid som trengs for å løse dette problem av stor betydning for den aktuelle anvendbarhet for løsningen. Endringer i trafikkintensiteten, linjebrudd og kostnadsvaria-sjoner knyttet til hvert enkelt overføringsledd påvirker alle den til enhver tid optimale allokering. Trafikkveisdirigering må følgelig utføres før det første oppsatte problem endres vesentlig. Selv om heuristiske metoder kan benyttes i denne sammenheng, er en spesielt hurtig optimaliseringsfremgangsmåte til stor hjelp, spesielt når det gjelder takling av uventede (ikke forutsigbare) trafikktopper.

Øvrige problemer som vil kunne finne sin løsning

ut fra de nye fremgangsmåter som er beskrevet her, omfatter industriell prosesskontroll, organisering av personell for kundetjenester, blanding av ingredienser for å fremstille kommersielle produkter, produktspektra fra oljeraffinerier, fordeling av EDB-tjenester til et større antall brukere,

samt en rekke andre anvendelser. I hvert tilfelle vil kostnaden (eller utbyttet), angitt som faktorer, måles eller bestemmes på annen måte, begrensningsfaktorene må fastlegges og bidraget fra samtlige desisjonsvariable som er tilknyttet disse begrensninger må likeledes måles eller bestemmes. Det som

fremkommer fra utførelsen av fremgangsmåtene er i hvert enkelt tilfelle tilkjennegivelse av et sett styreparametere som, når anvendt til en reell, praktisk situasjon, fører til en optimal prosess eller et optimalt anordnet system.

Man skal merke seg at de matriser som inngår i de fleste praktiske lineære optimaliseringsproblemer er "åpne matriser" (sparse matrices) slik at den teknikk som er særegen for denne type matriser også kan benyttes ved utledning av søkeretningen£i samsvar med fig. 4 og 5.

Ved utvikling av denne nye fremgangsmåte for løsning av lineære optimaliseringsoppgaver, må det forstås at de etterfølgende krav kun gjelder anvendelse av denne nye fremgangsmåte overfor systemer som fastlegger den optimale allokering av ressurser i reelle teknologiske og industrielle sammenhenger som naturlig tilknyttes en lineær fremstilling av de variable og av begrensningene som karakteriserer slike systemer, dvs. fysiske oppstillinger som bestemmer hvordan de aktuelle ressurser skal anvendes for optimalisering av utførelsen av prosesser, maskiner, fremstillinger eller sammensetning av materialer. Alle øvrige anvendelser av denne nye fremgangsmåte, såsom EDB-forskning, algoritme-forskning eller forskningsaktiviteter innen lineær algebra vil ikke utgjøre noen del av foreliggende oppfinnelse. Tilsvarende vil anvendelsen av denne nye fremgangsmåte i ikke-teknologiske eller ikke-industrielle systemer heller ikke utgjøre noen bestanddel av oppfinnelsen.

Claims (34)

1. Fremgangsmåte for allokering av de tilgjengelige overføringsmidler for telekommunikasjon blant de teleabonnenter som på et gitt tidspunkt ønsker teletjenester, for å redusere totalkostnaden for anvendelsen av disse overføringsmidler til et minimum, karakterisert ved å omfatte forsøksvis gjentatt omgruppering av de tilgjengelige telekommunika-sjonsmidler for overføring til abonnentene for å redusere totalkostnaden for hver oppsatt gruppering som velges ved normalisering av den forut oppsatte gruppering med hensyn til allokeringens begrensning, avslutning av den gjentatte omgruppering når totalkostnaden har nådd sin minimalverdi, og allokering av den gruppering av de tilgjengelige telekom-munikasjonsmidler for overføring som er i samsvar med denne minimalverdi.

2. Telekommunikasjonssystem , karakterisert ved et første antall forbindelsesledd som forbinder et andre antall telekommunikasjons-svitsjeknutepunkter, og trafikkveisdirigeringsorganer for dirigering av trafikk i hvert av knutepunktene til^ forbin-delsesleddene for å minimalisere kostnadene knyttet til overførselen av denne trafikk, idet trafikkveisdirigerings-organene omfatter organer for gjentatt selektering av estimater for minimalkostnadsgrupperingen slik at hvert valg ifølge en iterasjonsforskrift tilsvarer verdier for grupperingen hvilke i sin helhet ligger innenfor det multidimensjonale konvekse løsningsrom som representerer løsningen av grupperingenes respektive fysiske begrensninger.

3. Fremgangsmåte for allokering av tilgjengelige teletjenester for brukere blant et antall brukere for å minimalisere kostnaden for overførsel for å tilby disse teletjenester, idet fremgangsmåten er karakterisert ved forsøksvis gjentatt omgruppering av teletjenestene blant brukerne for å redusere kostnadene for hver oppsatt gruppering som velges ut fra sentralisering av den forut oppsatte gruppering med hensyn til allokeringens begrensning, avslutning av den fortløpende gjentatte omgruppering når kostnaden har nådd sin minimalverdi, og allokering av den gruppering av de tilgjengelige teletjenester blant brukerne som er i samsvar med den endelige, iterativt fastlagte gruppering.

4. Fremgangsmåte ifølge krav 3, karakterisert ved at teletjenestene omfatter overføringsmidler for telekommunikasjon og at brukerne omfatter telefonabonnenter.

5. Fremgangsmåte ifølge krav 3, karakterisert ved at teletjenestene omfatter informasj onsbehandlingstj enester.

6. Fremgangsmåte ifølge krav 3, karakterisert ved at teletjenestene omfatter EDB-tj enester.

7. Fremgangsmåte ifølge krav 3, karakterisert ved at teletjenestene omfatter f rems ti Hingst j enester.

8. Optimalisert ressursallokeringssystem, karakterisert ved et første antall fysiske ressurser tilgjengelig for anvendelse, et andre antall ressursbrukere som anvender de fysiske ressurser, og organer for gruppering av ressursbrukerne i forhold til de fysiske ressurser for å bringe kostnadene for overføring av ressursene til et minimum, idet organene for gruppering omfatter organer for forsøksvis og gjentatt selektering av mulige grupperinger ut fra de aktuelle ressursgrupperinger slik at hver av de mulige grupperinger ved hvert iterasjonstrinn sentreres innenfor det indre av et normalisert multidimensjonalt konvekst løsningsrom for de mulige løsninger, og organer for allokering av de fysiske ressurser i samsvar med den endelige, iterativt bestemte forsøksvise gruppering.

9. System ifølge krav 8, karakterisert ved at de fysiske ressurser omfatter teletjenester og at brukerne omfatter telefonabonnenter.

10. System ifølge krav 8, karakterisert ved at de fysiske ressurser omfatter informasjonsbehandlingstjenester.

11. System ifølge krav 8, karakterisert ved at de fysiske ressurser omfatter EDB-tjenester.

12. System ifølge krav 8, karakterisert ved at de fysiske hjelpemidler omfatter fremstillingstjenester.

13. System for optimalisering av forløpet for en styrt prosess i samsvar med et optimaliseringskriterium, karakterisert ved prosess-styreorganer for styring av prosessen i samsvar med sett av styresignaler, et antall sensorer for registrering av variable betingelser som påvirker prosessforløpet, et antall datagivere for fastsettelse av betingelser som påvirker prosessforløpet, og en styreenhet for lineær optimalisering som påvirkes av sensorene og data-giverne for generering av optimale sett styresignaler til styreorganene, idet styreenheten omfatter organer for identi-fikasjon av påfølgende forsøksvis høyst mulige sett styresignaler ifølge en iterasjonsforskrift og selektering av hvert forsøksvise påfølgende sett styresignaler i samsvar med den maksimale konvergensgradient for et normalisert sett av opti-ma liseringskriteriet.

14. Styreenhet for optimalisering av forløpet for et styrt system, karakterisert ved organer for bestemmelse av de fysiske begrensninger og begrensningsgrensene for forløpet av systemet, organer for fastleggelse av målekriterier for egenskapene ved forløpet av systemet, organer for identi-fikasjon av fortløpende forsøksvise sett verdier for styring av forløpet, hvilke verdier strengt tilfredsstiller begrensningene og begrensningsgrensene, organer for normalisering av de forsøksvise sett verdier for styring slik at disse får samme avstand fra begrensningsgrensene, og organer for selektering av hvert neste påfølgende sett normaliserte verdier for styring i samsvar med det foreskrevne målekriterium for systemets egenskaper.

15. Fremgangsmåte for ressursallokering ved benyttelse av en modell for lineær optimalisering, karakterisert ved fastleggelse av en modell for lineær optimalisering omfattende en målfunksjon og et antall begrensninger som adekvat beskriver mulige allokeringer for ressursene, forsøksvis identifisering av en ressursallokering som er strengt mulig, forbedring av den for-søksvise ressursallokering ifølge en iterativ forskrift ved å normalisere den forsøksvis ressursallokering med hensyn til begrensninger og endre denne forsøksvise ressursallokering i den retning som er bestemt av målfunksjonen, og allokering av ressursene i samsvar med den mest forbedrede for-søksvise ressursallokering.

16. Fremgangsmåte for forbedring av metoder innenfor lineær optimalisering for optimalisering av ressursallokering blant et antall brukere, karakterisert ved begrensning av iterasjons-forskriften til å gjelde kun strengt mulig allokeringer, og normalisering av hver strengt mulige allokering med hensyn til dennes begrensninger.

17. System for allokering av teknologiske ressurser blant et antall brukerenheter, karakterisert ved at hver allokering har tilknyttede begrensninger og kvantifiserbare kostnader eller et kvantifiserbart utbytte forbundet med allokeringen, idet systemet omfatter ressursallokeringselementer fordelt ved hjelp av en ressursallokeringsmekanisme som omfatter organer for fremstilling av begrensningene som en flerdimensjonal, konveks polytop med delflater som tilsvarer begrensningene og med en overflate som tilsvarer foretrukne ressursallokeringer, organer for forsøksvis selektering av en allokering for ressursene i samsvar med et utgangspunkt i det indre av polytopen, organer for trinnvis bevegelse fra startpunktet til en følge av punkter i det indre av polytopen, idet hvert påfølgende punkt tilsvarer en mer optimal allokering enn det foregående punkt, og organer for fordeling av elementene i systemet for å tilpasses den foretrukne ressursallokering som fastlegges ved et punkt på overflaten.

18. System for allokering av teknologiske ressurser blant et antall ressursbrukere underlagt begrensninger i tilknytning til allokeringene og på en slik måte at systemet søker å bringe til et minimum totalkostnadene tilknyttet allokeringene, idet allokeringene utledet fra systemet bestemmes i samsvar med en fremgangsmåte som er karakterisert ved 1) fremstilling av begrensningene som en polytop i et flerdimensjonalt hyperrom, 2) fremstilling av allokeringskostnadene^ som en vektor i dette hyperrom, 3) selektering av et allokeringsstartpunkt i det indre av polytopen, 4) normalisering av polytopen slik at allokeringsstartpunktet i det nærmeste sammenfaller med polytopens sentrum, 5) bestemmelse av retningen av kostnadsvektoren projisert i begrensningenes nullrom inne i den normaliserte polytop, 6) selektering av et nytt allokeringspunkt i den normaliserte polytop i en retning motsatt retningen av den projiserte kostnadsvektor, og 7) gjentagelse av trinnene 3) til 6) for dette nye allokeringspunkt.

19. System omfattende et første antall ressurser som tilveiebringer et andre antall sluttresultater, idet det benyttes en rekursjonsmetode for allokering av ressursene for å tilveiebringe disse sluttresultater, karakterisert ved at en gitt allokeringsgruppering x <*> erstattes av en forbedret ressursallokeringsgruppering xl + 1 som avledes av x. <i> ut fra ligningen xl + 1=#{ x <l> }, hvorved den avledede ressursallokeringsgruppering føres videre som den nye gitte allokeringsgruppering ved det neste iterasjonstrinn, når funksjonen $ omfatter 1) innføring av de enkelte elementer i den gitte allokeringsgruppering langs diagonalen i en matrise D med for øvrig bare nullelementer, 2) dannelse av en matrise B ved utvikling av matrise-produktet AD og økning av det avledede produkt med en siste rekke n 1 1 ere, 3) tilveiebringelse av en vektor Cp ut fra verdien av[ I -B<T> (BB<T> )B] - <1> Dc hvor I er enhetsmatrisen, 4) divisjon av Cp med dens størrelse for utvikling av en normalisert indikator cp, 5) dannelse av et transformert nytt estimat x_i + ^ fra x ved subtraksjon av aCp fra det normaltransformerte estimat x <1> av2£ hvor a er mindre enn 1 , 6) dannelse av et utransformert nytt estimat av x ved vurdering av Dx <l+> ^/e^Dx <l+> ^ hvor e = (1,1, ...,1), og 7) anvendelse av det nye estimat x <l+> ^ av x i systemet.

20. Fremgangsmåte for allokering av industrielle ressurser blant et antall ressursbrukere, idet hver allokering har fysiske begrensninger for anvendelsen av ressursen og kvantifiserbare kostnader eller utbytte tilknyttet hver allokering, karakterisert ved 1) fremstilling av de fysiske begrensninger i et system av lineære variable som sammen avgrenser en flerdimensjonal polytop hvis delflater hver tilsvarer en respektive fysisk begrensning, 2) selektering av et forsøksvis sett allokeringer for ressursene, representert ved et punkt idet indre av polytopen som et allokeringsstartpunkt, 3) transformasjon av polytopen slik at allokeringsstartpunktet nær sammenfaller med det geometriske sentrum i den transformerte polytop og slik at polytopens delflater får tilnærmet samme avstand fra polytopens sentrum, 4) forflytning fra allokeringsstartpunktet til et nytt allokeringspunkt i det indre av den omskalerte polytop, men nå nærmere overflaten av denne, 5) transformasjon av dette nye allokeringspunkt tilbake til den opprinnelige polytoprepresentasjon, 6) gjentagelse av trinn 3) til 5) til valget av punktet i det indre av polytopen faller hovedsakelig på dennes overflate, 7) identifisering av allokeringsverdiene tilknyttet dette punkt som hovedsakelig sammenfaller med polytopens overflate, og 8) allokering av ressursene i samsvar med de således tilveiebragte ressursallokeringsverdier.

21. System for allokering av industrielle ressurser blant et antall ressursforbrukere, idet hver ressursallokering er underlagt fysiske begrensninger og har kvantifiserbare kostnader i tilknytninger til allokeringen, og hvor systemet tilveiebringer allokeringer for ressursene ut fra bestemmelse i samsvar med en fremgangsmåte som er karakterisert ved 1 ) fremstilling av de fysiske begrensninger ifølge et system av lineære variable som avgrenser et lukket, konvekst, flerdimensjonalt legeme, 2) selektering av en ressursallokering som samsvarer med et punkt i det indre av det flerdimensjonale legeme som et startpunkt, 3) transformasjon av det lukkede legeme for å bringe det selekterte startpunkt nær det geometriske sentrum i det transformerte legeme og slik at delflatene av legemet hovedsakelig får samme avstand fra legemets sentrum, 4) selektering av en ny ressursallokering i samsvar med et nytt punkt i det indre av det omskalerte lukkede legeme, men nå nærmere dettes overflate enn startpunktet, 5) gjentagelse av trinn 3) og 4) med den nye res-6 sursallokering til valget faller på en allokering som hovedsakelig samsvarer med et punkt på legemets overflate, og tilpasning av systemet for å allokere ressursene i samsvar med den endelige ressursallokering som bringer punktet til legemets overflate. .0

22. Styreenhet for lineær optimalisering for anvendelse sammen med en standard datamaskin, karakterisert ved et EDB-lagringsmedium med et dataprogram for utførelse av datamaskinen, idet pro- .5 grammet omfatter organer for prosessering av et antall lineære sammenhenger som avgrenser en flerdimensjonal konveks polytop som fremstiller settet mulige løsninger for antallet lineære sammenhenger, og organer innrettet for optimalisering av en funksjon og identifisering av det punkt på polytopens hyper- <?> 0 grenseflate som fremstiller den optimale løsning for antallet lineære sammenhenger ved utvikling i etterfølgende trinn langs en strengt mulig løsningsvei som i sin helhet er inne-sluttet i det indre av polytopen. 25

23. Fremgangsmåte for allokering av fysiske ressurser blant et antall ressursbrukere som er gjenstand for begrensninger tilknyttet allokeringene og på en slik måte at kostnadene for de tilknyttede allokeringer bringes til et minimum, karakterisert ved 3 <0> 1) fremstilling av begrensningene som en polytop i et hyperrom, 2) fremstilling av allokeringskostnadene som en vektor i hyperrommet, 3) selektering av et allokeringsstartpunkt i det 35 indre av polytopen, 4) transformasjon av polytopen til et ekvivalent rom hvor allokeringsstartpunktet nær faller sammen med poly topens sentrum, 5) bestemmelse av kostnadsvektorens retning i det ekvivalente rom, 6) selektering av et nytt allokeringspunkt i det ekvivalente rom i en retning motsatt kostnadsvektorens retning, 7) transformasjon av det nye allokeringspunkt tilbake til polytopens opprinnelige hyperrom, og 8) gjentagelse av trinn 4) til 7) for det nye allokeringspunkt.

24. Fremgangsmåte for allokering av industrielle eller teknologiske ressurser Xi (i = 1 > n) blant et antall ressursbrukere som er gjenstand for begrensninger A^ jX j_ i bj og Xj_ * 0 (i = 1 , n; j = 1 , m) slik at en kostnadsf unksjon c-L ^xi optimaliseres, karakterisert ved 1) selektering av et startallokeringspunkt start . start start start. , . , c , . ■-, , x = (x^ ' x2 ' ' * *' Xn tilfredsstiller begrensningene,2) anvendelse av den projiserende tranformasjon

hvor , . , start start start, e = ( 1 , 1 , 1 , ... , 1 ) , for å transformere begrensningene til et affint rom med x <sta> rt nær dets sentrum, 3) bestemmelse av kostnadsfunksjonsvektoren Cp i det affine rom ved hjelp av forholdet Cp = {I - B <T> (BB <T> )- <1> B}Dc hvor I er enhetsmatrisen, c er kostnadsvektoren, D er definert ovenfor, og r _ AD B - T, e 4) normalisering av kostnadsfunksjonsvektoren Cp ved hjelp av forholdet

5) selektering av et nytt allokeringspunkt b' i det affine rom, gitt avb' = x'start - ar£p, hvor r er radius for største innskrevne hypersfære i det affine rom og er gitt av

a er mindre enn 1, 6) tilbaketransformasjon av det nye allokeringsstartpunkt til det opprinnelige hyperrom ved hjelp av trans-formasjonen

7) gjentagelse av trinn 2) til 6) hvor b erstatter aQ som det nye startallokeringspunkt.

25. Fremgangsmåte for forbedring av totalkostnadene i et system med et antall n industrielle ressurser som står i innbyrdes forhold for å oppnå et antall teknologiske sluttresultater bj , idet hver av ressursene gir et bidrag til hvert av sluttresultatene med en tilhørende kostnadskoeffisient og hvor hver av ressursene er underlagt begrensninger som kjennetegner systemet, hvor en vektor b representerer antallet sluttresultater, en vektor x representerer settet nødvendige bidrag fra antallet ressurser, en vektor c representerer settet kostnadskoeffisienter, og matrisen A representerer systemets begrensninger, karakterisert ved selektering av et sett bidrag x <curr> som tilfredsstiller systemets begrensninger som et sannsynlig (current) estimat av x, innsetting av det sannsynlige estimat xGurr langs diagonalen i en matrise D som for øvrig har leddene 0, dannelse av en matrise B ved utvikling av matrise-produktet AD og økning av dette produkt med en siste rekke med n 1'ere, utvikling av en indikatorvektor Cp ved vurdering av[ I-B<T> (BB<T> )- <1> b]D c, hvor I er enhetsmatrisen. divisjon av Cp med denne vektors størrelse for å danne en normalisert indikator-eller enhetsvektor Cp, dannelse av et transformert nytt estimat x^ av x ved å subtrahere acp fra e/n, hvor a er mindre enn 1, dannelse av et utransformert nytt estimat x <n> Y av x ved vurdering av Dx'/e Dx', hvor e = {1,1, ... 1>, og innføring av det nye estimat x <n> Y av x i systemet.

26. Fremgangsmåte for allokering av industrielle eller teknologiske ressurser, karakterisert ved bestemmelse av verdier for de variable som er tilknyttet ressursene, idet et sett mulige kombinasjoner av de variable utgjør et konvekst sett og hvor bestemmelsen utføres slik at en målfunksjon av de variable søkes optimalisert, hvorved bestemmelsen videre omfatter en følge av trinn slik at forsøksvise verdier for de variable i hvert trinn erstatter de tidligere verdier, og hvor denne substitusjon av variable er basert på et retnings-valg i et sett oppnådd ved sentralisering av det konvekse sett.

27. Fremgangsmåte for optimalisering av ressursallokering i et system som er kjennetegnet ved en lineær målfunksjon hvis enkelte elementer representerer en spesifikk ressursallokering tilknyttet en individuell entitet i systemet og som omfatter en variabel og en kjent variabel koeffisient samt ved én eller flere lineære begrensningskurver uttrykt ved hjelp av én eller flere av målfunksjonens variable, karakterisert ved 1) bestemmelse av en startverdi for hver av målfunksjonens variable slik at en vektor i et hyperrom med n dimensjoner fastlagt ved at startverdiene befinner seg i det indre av en polytop avgrenset ved disse lineære begrensningskurver, 2) transformasjon av polytopen som omfatter startvektoren og de lineære begrensningskurver til et simpleksrom S{x I x <>> = 0, Exi = 1} med begynnelsespunktet for startvektoren nær simpleksrommets sentrum, 3) projisering av den transformerte startvektor ortogonalt til simpleksrommet, 4) bestemmelse av retningen for den projiserte transformerte startvektor i simpleksrommet, 5) bestemmelse av et nytt begynnelsespunkt for en ny startvektor ved forflytning fra simpleksrommets S sentrum e/n til en retning motsatt den bestemte retning og med en avstand i simpleksrommet som er lik et multiplum av radius for den største hypersfære som ligger innskrevet i simpleksrommet og har sitt sentrum i begynnelsespunktet for den transformerte startvektor, 6) tilbaketransformasjon av det nye begynnelsespunkt til det opprinnelige hyperrom for polytopen, 7) gjentagelse av trinn 2) til 6), idet målfunksjonens startverdier erstattes av de verdier som fremkommer fra det transformerte nye startpunkt til en tilfredsstillende minimalisering er oppnådd for målfunksjonen, og allokering av systemets ressurser til de individuelle entiteter i systemet i samsvar med målfunksjonens endelige elementverdier.

28. Fremgangsmåte ifølge krav 27, idet trinn 2) karak-teriseres ved generering av en matrise B ved multiplikasjon mellom en diagonalmatrise for startverdiene for målfunksjonens variable med en matrise for koeffisientene for de lineære begrensningskurver, og addisjon av en ytterligere nederste rekke hvor hvert ledd består av verdien 1,til matrisen B.

29. Fremgangsmåte ifølge krav 27, idet trinn 3) er karakterisert ved beregning av den ortogonale projeksjon av den transformerte startvektor fra matriseligningen [I-B<T> (BB<T> )~ ^B] multiplisert med diagonalmatrisen for de variable startverdier multiplisert med startvektoren, hvor 1^ er enhetsmatrisen og BT er den transponerte matrise til B-matrisen, og deretter normalisering av den ortogonale projeksjon.

30. Fremgangsmåte ifølge krav 27, idet trinn 5) er karakterisert ved beregning av en ny transformert startvektor fra verdien av (x <start> _ ar) multiplisert med den transformerte kostnadsvektor, hvorx start _ e/n, r er radius for den innskrevne hypersfære og a er en gitt konstant.

31. Fremgangsmåte ifølge krav 30, karakterisert ved beregning av denne radius ut fra formelen

32. Fremgangmåte for optimalisering av en allokering av ressurser i et system som er kjennetegnet ved en målfunksjon i et hyperrom med n dimensjoner og hvor hvert element i målfunksjonen representerer en spesifikk ressursallokering tilknyttet en individuell entitet i systemet og omfatter en variabel og en kjent variabel koeffisient samt ved én eller flere begrensende forhold uttrykt ved hjelp av én eller flere av målfunksjonens variable, karakterisert ved 1) bestemmelse av en startverdi for hver av målfunksjonens variable slik at en startvektor bestemt av_ startverdiene faller innenfor en polytop avgrenset av de begrensende forhold, 2) transformasjon av polytopen med startvektoren og de begrensende forhold til et simpleksrom S = {x I Xi <*> = 0, Zxi = 1} i hvilket den transformerte startvektor bringes nær simpleksrommets sentrum, 3) projisering av den transformerte vektor for målfunksjonen ortogonalt til nullrommet for de transformerte begrensende forhold, 4) bestemmelse av retningen for projeksjonen av den transformerte målfunksjon, 5) bestemmelse av en ny verdi for hver av målfunksjonens variable ved forflytning fra sentrum e/n av simpleksrommet en avstand lik et gitt multiplum av radius for den største hypersfære som innsluttes i simpleksrommet og som har sentrum i begynnelsespunktet for den transformerte startvektor , 6) tilbaketransformasjon av de nye verdier til de opprinnelige variable, 7) gjentagelse av trinn 2) til 6), idet de nye verdier innsettes i substitusjon for de opprinnelige verdier for målfunksjonens variable inntil en tilfredsstillende minimalisering av målfunksjonen oppnås, og 8) allokering av systemets ressurser til de individuelle entiteter i systemet i samsvar med de engelige verdier for målfunksjonens elementer.

33. Fremgangsmåte ifølge krav 32, idet trinn 2) er karakterisert ved generering av en matrise B ved multiplikasjon av diagonalmatrisen for startverdiene for målfunksjonens variable med en matrise for koeffisientene for de begrensende forhold, og addering av en ytterligere nederste rekke til matrisen B, idet hvert ledd i rekken består av verdien 1.

34. Fremgangsmåte ifølge krav 32, idet trinn 3) er karakterisert ved beregning av den ortogonale projeksjon av den transformerte startvektor fra matriseligningen[ I-B <T> (B B <T> )~ ^B] multiplisert med startvektoren, hvor I er enhetsmatrisen og B^ er den transponerte matrise til B-matrisen, og deretter normalisering av den ortogonale projeksjon på en gitt måte.