Under og efter den anden verdenskrig har der specielt i U.S.A. været et livligt samarbejde mellem matematikere, økonomer, administratorer og andre om udviklingen af en metode, hvis hovedemne er et så centralt økonomisk problem som spørgsmålet om den mest økonomiske fordeling af absolut knappe produktionsmidler.

Metoden er kendt under snart mange betegnelser: Linear programming, activity analysis, mathematical programming eller simpelthen programming, betegnelser som hver for sig søger at fremhæve det karakteristiske ved metoden.

Under hensyntagen til, at metoden efterhånden har vundet interesse herhjemme, vil vi her anvende en fordanskning af den ældste og mest velkendte betegnelse, således at vi i det følgende taler om lineær programmering₁). Denne betegnelse er allerede anvendt²), og vi leverer således ikke noget bidrag til den terminologiske uenighed.

Emnet er allerede meget omfattende og undergår en kraftig udvikling, således at der ikke kan blive tale om her at give en blot nogenlunde fuldkommenfremstilling. Det har derfor i første række været tilsigtet at vise, hvad der karakteriserer 1. p. Selve anvendelsen af 1. p. i praksis fordrerikke anden matematisk viden end kendskab til de fire simple regnearter;men bag dette ligger komplicerede matematiske problemer. Der er i artiklen lagt megen vægt på at begrunde og anskueliggøre metodens virkemåde, og det er tilstræbt i så høj grad som muligt at gennemføre dette ved driftsøkonomiske ræsonnementer og kun benytte matematik, hvor dette uden at vanskeliggøre læsningen er hensigtsmæssigt. Endelig

---

*) Konsulent, cand. oecon.

1) I det følgende kort 1. p.

2) Man kan bl. a. henvise til de i litteraturhenvisningen nævnte artikler af Niels Nielsen.

er der ved en kort gennemgang af begreber og forudsætninger søgt etableretet
grundlag til bedømmelse af metodens anvendelsesmuligheder.

A. Hvad er lineær programmering?

Vi har i indledningen omtalt 1. p. som en metode til behandling af problemer om den optimale anvendelse af absolut knappe produktionsmidler. Sådanne problemer har også været hovedemnet for 1.p.; men det må understreges, at metoden har langt videre perspektiver. Nogenlunde generelt kan man karakterisere 1. p.'s anvendelsesområde som omfattende problemer, der lader sig udtrykke således:

Find et sæt værdier af de variable xi, X2 ■•••, xn, der tilfredsstiller
ligningssystemet.

(1):

og

(2):

samtidig med, at funktionalen

(3):

maximeres eller minimeres.

Vi kan kalde (1) for betingelsessystemet, (2) for ikke-negativitetsbetingelsen
og (3) for fordelagtighedsfunktionalen.

Denne rent matematiske opgave kan interpreteres på overordentlig
mange driftsøkonomiske problemer. For at konkretisere skal vi straks
vise et sådant.

B. Planlægning af produktionsprogram ved faste tildelinger af råstoffer.

I en artikel „Bidragsmetoden og nøglefaktorerne" i dette tidsskrift³) har Niels Nielsen omtalt 1. p. sorn en mulig metode til bestemmelse af det optimale produktionsprogram for en virksomhed, hvis produktionsmuligheder er begrænset ved faste tildelinger af visse råstoffer.

Vi vil her anvende Niels Nielsens exempel som introduktion til forståelsen af 1. p. Med henvisning til artiklen kan vi tillade os at holde fremstillingen på et mere almindeligt niveau uden at opfylde alt for strenge krav om konsekvens.

---

3) Nr. 3, 1955.

En virksomhed har for planlaegningsperioden tildeling af m rastoffer
(Ai, A2, •..., Am) ide absolut faste maengder ai, ac, •••■, am. Disst rastoffer
kan virksomheden anvende til produktion af n varer (Xi, X2,
...., Xn). Til produktion af een enhed af varen Xi anvendes af de
respektive knappe rastoffer an, a2i, ■•••, ami, idet det f erste fodtegn
refererer til rastoffet, andet fodtegn til varen.

Knapheden på råstofferne antages at være så absolut, at kapacitetsproblemer
og andre lignende forhold kan lades ude af betragtning.

Dækningsbidragene for en enhed af hver af varerne er ci, c2, .., ccn4).

Det forudsættes, at varerne kan produceres simultant, og at såvel forbrug som dækningsbidrag for hver vare er ligefrem proportional med den producerede mængde af den enkelte vare og uafhængig af de producerede mængder af de andre varer.

Vi går ud fra, at virksomheden ikke behøver at udnytte råstoftildelingerne
fuldt ud, og at det, der ikke udnyttes, går omkostningsfrit til
spilde - ikke indkøbes.

Virksomhedens problem er nu at fastsætte sit produktionsprogram som
den kombination af de enkelte varer, der - indenfor rammerne af de
faste tildelinger - yder det største totale dækningsbidrag.

De producerede maengder af de enkelte varer betegnes med xi, xs,
■ • • • , Xn.

Matematisk kan problemet udtrykkes således:

Virksomheden må holde sit produktionsprogram indenfor sådanne
rammer, at der ikke forbruges mere af de knappe råstoffer end de givne
tildelinger, altså

(la):

o.s.v. til

Kalder vi de ikke udnyttede mængder af råstofferne for henholdsvis
Xn+i, Xn+2, • • ■ •, Xn+m, kan ulighederne (la) omdannes til ligningerne:

---

4) Vi kan tænke os enhedsdækningsbidraget udtrykt ved varens pris minus summen af råstofomkostninger og alle andre direkte henførlige omkostninger, idet vi med henvisning til det foregående afsnit betragter alle andre omkostninger som upåvirkelige i denne relation. Deter ikke hensigten her at diskutere 1. p. i relation til bidragstanken; indførelsen af dækningsbidragene er alene bestemt af referencen til Niels Nielsens artikel og af ønsket om at operere med eet bestemt mål for fordelagtigheden ved at producere den enkelte vare, jfr. omtalen af fordelagtighedskriteriet i afsnit E.

(1):

Ingen af de producerede mængder kan være negative, altså

(2):

Det totale dækningsbidrag er efter forudsætningerne en lineær funktional
af de enkelte produktionsomfang.

(3):

At løse virksomhedens problem betyder derfor at maximere (3) under
overholdelse af betingelserne (1) og (2).

Virksomhedens problem er hermed omdannet til en matematisk opgave
af samme form som den, hvorved vi har defineret 1. p.

Vi har således vist, at det i alt fald er teoretisk muligt at udtrykke et
forholdsvist almindeligt driftsøkonomisk problem som en 1. p.-opgave.
Om dette har nogen som helst interesse vil naturligvis afhænge af:
1) om det matematiske problem kan løses,

2) om der findes en praktisk anvendelig, enkel og sikker løsningsmetode.

3) om det i praksis er rimeligt at operere med de forudsaetninger, vi af
hensyn til den matematiske Lasning ma indfare.

C. Løsning af problemet.

Efter omdannelsen af vort økonomiske problem er løsningen en ren matematisk opgave. Vi vil forsøge at forklare de matematiske sætninger, der danner grundlaget for denne løsning ved de økonomiske begreber, vi har indført i vort exempel.

1. Betingelsessystemet og ikke-negativitetsbetingelsen.

Lad os i exemplet antage, at antallet af knappe råstoffer, m, er lig 2. I et 2-dimensionalt koordinatsystem afsætter vi mængderne af råstofferne ud ad hver sin akse (fig. 1), og de for virksomheden gældende knapheder karakteriseres nu ved punktet A med koordinaterne ai og a2.

Om den enkelte produktionsproces har vi gjort den forudsætning, at
forbruget af de knappe råstoffer er ligefrem proportionalt med den produceredemængde
- i det følgende kort betegnet produktionsprocessens

intensitet. En produktionsproces med denne egenskab kan i koordinatsystemetkarakteriseres ved en strale gennem det punkt, der angiver forbrugetaf de knappe rastoffer ved produktion af een enhed af varen - ved intensiteten 1. I figur 1 er vist produktionsproces Xi.

Punkterne på denne stråle svarer til forskellige intensiteter. Markerer punktet 1 således produktion af een enhed af varen med et forbrug på henholdsvis an og a2i vil punktet 2, der karakteriserer produktion af 2 enheder af varen, ligge i den dobbelte afstand fra origon og repræsentere et forbrug på henholdsvis 2 an og 2 a2i.

Vi kan kalde denne forudsætning for produktionsprocessens linearitet
med hensyn til betingelsessystemet.

Det er i exemplet forudsat, at virksomheden ikke behøver at forbruge de disponible mængder af de knappe råstoffer fuldt ud. De ikke anvendte mængder kan vi her betegne med f. ex. xp og xe. Det at lade varierende mængder af råstofferne uanvendt kan i koordinatsystemet karakteriseres ved stråler, der for hvert råstof er sammenfaldende med den respektive

På grund af den billedlige analogi med produktionsprocesser vil det
være hensigtsmæssigt at betegne disse sidste spillerumsprocesser5). Vi

---

5) Disse processer kan i andre exempler have en ganske anden betydning, men i forhold til betingelsessystemet vil deres existens dog altid betyde, at man ikke alene med de egentlige produktionsprocesser behøver at opfylde betingelserne. Der er mulighed for at lade et vist spillerum åbent, som så, for at determinere problemet helt, dækkes af spillerumsprocesserne.

nøjes foreløbig med at markere, at medens en produktionsproces kun, såfremtden forbruger eet knapt råstof og ikke andre, vil ligge på en af akserne og også i disse tilfælde kan Lave en enhed for intensiteten, der er forskellig fra råstoffets enhed, så vil spillerumsprocessen altid ligge på sin respektive akse og have enhed fælles med råstoffet.

Om samspillet mellem produktionsprocesser har vi forudsat, at de enkelte processers forbrug er uafhængigt af de øvrige processers intensiteter. Selv om vi i koordinatsystemet opererer med 2 produktionsprocesser, vil de derfor begge stadig være karakteriseret ved deres individuelle stråler, og deres samlede forbrug findes ved simpelthen at addere de enkelte produktionsprocessers forbrug.

I koordinatsystemet findes dette saimlede forbrug som koordinaterne til resultanten af de 2 produktionsprocesser (kræfternes parallelogram), (fig. 2). Tilsvarende for flere produktionsprocesser og for samspillet med spillerumsprocesser.

Betingelsessystemet (1) forlanger nu, at vi skal finde en kombination
af produktionsprocesser og spillerumsprocesser, hvis resultant netop er
A, virksomhedens knaphedspunkt.

a) Såfremt vi kun har een produktionsproces og ingen spillerumsprocesser,
er dette kun muligt, såfremt A ligger på den stråle, der karakteriserer

b) Har vi 2 produktionsprocesser, kan vi, når vi husker, at ingen af intensiteterne kan være negative, ifølge forudsætning (2), kun opfylde kravet, såfremt A ligger imellem (eller på en af) de to stråler. Både i tilfælde a) og her vil der, såfremt løsningsbetingelsen er opfyldt, også kun være een løsning - een bestemt kombination af produktionsprocessernes intensiteter, der opfylder kravet.

c) Når vi disponerer over mere end 2 processer, vil det tilsvarende
kun være muligt at opfylde kravet, såfremt A ligger imellem (eller
på en af) de 2 yderste stråler. I dette tilfælde vil der imidlertid
som regel være flere mulige kombinationer af produktionsprocesserne,
idet A kan nås dels ved udvælgelse af 2 produktionsprocesser,
som opfylder den under b) nævnte betingelse for løsning, dels
ved kombination af flere end 2 produktionsprocesser, hvoriblandt
mindst 2 opfylder denne betingelse.
Såfremt vi har begge spillerumsprocesserne med, vil det altid være
muligt at finde en løsning f. ex. ved at lade hele råstofkombinationen
uanvendt. Vi har hidtil skelnet mellem produktionsprocesser
og spillerumsprocesser; dette er ikke relevant i denne forbindelse.
Ræsonnementerne gælder stadig, når man i stedet for produktionsprocesser
taler generelt om processer.

Disse simple og trivielle exempler er gennemgået for at skabe grundlag
for et desperat spring til følgende generalisation:

Betingelsessystemet (1) med den yderligere forudsætning (2) kan have ingen, een eller mange løsninger, afhængig af antallet af übekendte og antallet af ligninger (og disses form), d.v.s. antallet af disponible processer og antallet af knaphedsbetingelser (og konstanternes indbyrdes relationer). Såfremt der findes løsninger, vil der endvidere altid blandt disse være løsninger, som kun anvender et antal processer lig antallet af betingelser⁶) (her knappe råstoffer). For hver af de kombinationer, der består af det mindst mulige antal processer, vil der endelig kun være een mulig kombination af de tilhørende intensiteter.

---

6) I visse tilfælde vil færre processer være tilstrækkelige jfr. det matematiske begreb maximalgrad.

For exempel vil der i et tilfælde med 4 råstoffer og 25 processer, såfremt der findes en løsning, heriblandt være mindst een, der kun benytter 4 processer. Man kan ikke udelukke, at der også findes løsninger, der anvender et mindre antal, men 4 er tilstrækkeligt. Går vi nu ud fra, at 4 er det mindste antal, og udtager vi nu sådanne 4, der kan opfylde betingelseskravet, findes der for disse bestemte processer kun een mulig kombination af deres intensiteter, der netop giver A. Udtager vi f. ex. 5, vil disse i almindelighed kunne kombineres på et utal af måder. Dette er et af 1. p.'s basisteorier⁷).

Inden vi forlader denne omtale af betingelsessystemet, skulle vi gerne være i stand til at karakterisere de eventuelle løsninger nærmere. Til dette formål et talexempel med 2 knappe råstoffer, 1 produktionsproces og spillerumsprocesser for begge råstoffer. Konstanterne er samlet i følgende skema.

Betingelsessystemet bliver her

(a):

(b):

hvor (a) refererer til forbruget af Ai, og (b) til A2

Da vi her er interesseret i løsningerne selv, vil vi i et 3-dimensionalt
koordinatsystem afsætte intensiteterne af de tre processer ud ad hver
sin akse (fig. 3).

Betragter vi alene tildelingen af Ai som fast, fastsætter ligning (a), at kun kombinationer, der ligger i plan I (på figuren er vist stykket BGDE) er mulige. Tilsvarende finder vi, at de mulige programmer, såfremt vi kun betragter tildelingen af A2 som fast (ligning (b)), må ligge i plan II (FGHI). Samlet får vi derfor, at de mulige programmer skal ligge på skæringslinien mellem de 2 planer, altså på linien KL, (Xi 0).

---

7) Hele denne fremstilling er naturligvis ikke matematisk korrekt, men forhåbentlig derved i højere grad anskuelsesmæssig tilstrækkelig.

Generaliserer vi dette, kan vi sige, at løsningerne til betingelsessystemet (1) altid vil danne, hvad man i geometrien kalder et konvekst sæt. Dette betyder, at løsningspunkterne altid vil danne en sammenhængende mængde, således at hvis 2 punkter ligger i løsningsmængden, så ligger alle punkter på deres forbindelseslinie også i løsningsmængden. Holder vi os til de tilfælde, hvor antallet af processer og råstoffer begge

er endelige, vil løsningsmængden yderligere have den egenskab, at antallet
af hjørner, endepunkter eller med den i 1. p. almindelige betegnelse
extreme punkter er endeligt.

Da vi ikke kan illustrere i mere end 3 dimensioner, nøjes vi med at
vise et fiktivt billede af en generel løsningsmængde (fig. 4).

I vort 3-dimensionale tilfælde er linien KL altså vor løsningsmængde, og punkterne K og L er de extreme punkter. Den „generelle" løsningsmængde i figur 4 har de extreme punkter A, B, C, D, E, F og G. Lad med en senere forklaring Q og R være almindelige indre punkter.

Til sidst må vi fremhæve en meget væsentlig egenskab ved de extreme
punkter. I figur 3 ser vi, at K kun anvender processerne Xi og X2, medensX3

densX3er 0. Punktet L anvender kun Xs og Xs, medens xi = 0. De løsninger til betingelsessystemet, som kun anvender det mindst mulige antal processer, og som vi tidligere har fremhævet, er netop karakteriseret ved extreme punkter. Punkter inden i sættet anvender flere processer.

Figur 3 viser samtidig, at selv om vi er i stand til at opfylde betingelserne
med 2 processer f. ex. Xi og Xs, er det ikke nødvendigvis muligt
med 2 hvilke som helst processer at gøre. dette. Xi og X3 alene er således

ikke tilstrækkelig. Mindst een kombination af 2 af de 3 processer vil dog
være tilstrækkelig.

Vi kan derfor i almindelighed gaud fra, at antallet af extreme punkter
med m rastoffer og n + m processor er mindre end eller lig antallet
af muligheder for at udvaelge m blandr, n -{- m eller ( m + n |
I m /

2. Fordelagtighedsfunktionalen.

Efter således at have omtalt de mulige programmer, skal vi nu blandt
disse udvælge det (eller de) optimale program(mer). Vi skal maximere
den lineære funktional (3).

I figur 3 skal vi altså finde det punkt på linien KL, hvor (3) bliver maximal. Lad os antage, at vi begynder i punktet L. Vi starter altså med at undlade overhovedet at indkøbe råstofferne. Det totale dækningsbidrag er naturligvis her 0.

Bevæger vi os nu langs linien mod K, d.v.s. substituerer vi Xi for X3 med en samtidig tilpasning af X2, ændres det totale dækningsbidrag. Såfremt Xi har et positivt enhedsdækningsbidrag, vil det totale dækningsbidrag vokse, og da (3) er lineær, vil det vokse, indtil vi når punktet K, som altså er det maximale punkt.

I det generelle tilfælde vil ved indførelsen af Xi - med tilsvarende
ændringer af de i udgangssituationen anvendte processer - det bidrag,

om Xi leverer til det totale dækningsbidrag, modvirkes (eventuelt forbedres)ved ændringerne i udgangssituationens processer. Da der imidlertidom (3) gælder den lineære og den additive forudsætning, foreligger kun følgende 3 muligheder for ændringer i funktionalen ved bevægelse langs en ret linie. Fordelagtighedsfunktionalen må enten

a) vokse proportionalt med bevægelsen,

b) falde proportionalt med bevægelsen,
eller

c) være konstant,

indtil vi når grænsen for løsningsmængden og ikke kan substituere på
samme måde mere.

I figur 4 vil en bevægelse fra Q til R altid falde under eet af de 3 tilfælde.
Bevæger vi os derefter fra R mod E, vil det tilsvarende gælde.

Vi indser derfor, at fordelagtighedsfunktionalen altid vil have sine extreme værdier i løsningsmængdens extreme punkter, eller, såfremt den antager samme værdi i 2 eller flere extreme punkter, vil have denne samme værdi i alle mellem disse liggende punkter.

Da vi endelig ved, at de extreme punkter repraesenterer kombinationer
af et antal processer hojst lig antallet af betingelsesligninger, vil
det derfor sige, at vi skal sege den optimale losning blandt de hejst
specielle kombinationer. Hver af disse kombinationer giver
kun mulighed for een lesning.

Vi har hermed reduceret opgaven fra en undersøgelse af eventuelt uendelig mange uordnede programmer til et endeligt antal bestemte. Vi skal herefter liste de mulige kombinationer bestående af m af de n + m processer, fixere intensiteterne ved indsættelse i (1) og (2) og gennemprøve alle disse kombinationer i (3).

D. Specielle løsningsmetoder.

I det foregående afsnit har vi angivet betingelserne for, at 1. p.-opgavenhar
løsninger, og vi har vist, hvorledes man kan finde den optimale
løsning. Denne undersøgelse vil dog i almindelighed være meget tidskrævende.1
et tilfælde med blot 9 produktionsprocesser og 6 knappe
råstoffer (med spillerumsprocesser) vil antallet af kombinationer, der
15!
skal gennemarbejdes være ———- eller godt 3000. Muligheden for prak-5!10!

tisk anvendelse er derfor først blevet aktuel ved fremkomsten af specielleløsningsmetoder,

cielleløsningsmetoder,der hurtigt fører gennem undersøgelsen af de
extreme punkter.

Af sadanne metoder kan vi naevne:

1) The Transportation Method.
Denne metode er kun anvendelig i visse tilfeelde, men betyder til
gengaeld her en meget stor beregningsmaessig lettelse8).

2) The Simplex-method, der er udviklet af George B. Dantzig, er helt generel og har derfor en meget stor del af seren for, at 1. p. er andet og mere end et strengt matematisk teoretisk fasnomen. Ved hjaelp af denne metode nar man til malet i lebet af forholdsvis fa trin. Dantzig mener saledes, at man hojst behover at gennemregne et antal tabeller lig antallet af processer⁹).

Vi skal her vise, hvorledes simplexmetoden fungerer.

1. Trin.

Vi begynder med at finde en vilkårlig basisløsning, d.v.s. en af de
extreme løsninger. At finde en sådan giver sig i almindelighed af sig
selv; et par nemme fremgangsmåder er:

1) Har vi spillerumsprocesser svarende til alle de knappe råstoffer,
har vi hermed straks vores basisløsning bestående alene af disse
- i figur 3 den til L svarende løsning.

2) Har vi ikke spillerumsprocesser for alle knappe råstoffer, kan vi indføre nogle hjælpeprocesser ganske svarende til spillerumsprocesserne, men tillagt så store negative dækningsbidrag, at vi sikrer os, at de elimineres ved de følgende operationer.

3) I mange tilfælde er det simpelt blot at udvælge et sæt processer (m) og bestemme de intensiteter, der svarer til det rigtige totale forbrug. Dette sker, idet vi antager, at de valgte processer er de m første, ved løsning af de m ligninger10).

---

8) Metoden er f. ex. beskrevet af W. Cooper og A. Charnes i en artikel „Transportation Scheduling by Linear Programming". Proceedings of the Case Institute Conference on Operation Research in Marketing, (Jan. 1953).

9) Simplex-metoden er nærmere beskrevet i [2], kap. XXI og XXII, samt i [I], Tallene i [ ] henviser til litteraturfortegnelsen sidst i artiklen.

10) Maximalgraden forudsat så stor som muligt, altså lig m.

2. Trin.

Når vi således har udvalgt en basisløsning, bliver problemet fra denne løsning at arbejde os frem til den optimale. Dette sker ved en vandring fra det extreme punkt, som repræsenterer vort basissystem, til et andet ligeledes extremt punkt, der giver en mere optimal værdi for funktionalen. Ved således at vandre gennem stedse mere optimale punkter arbejder vi os efterhånden frem til den optimale løsning. I stedet for at skulle gennemregne samtlige extreme punkter får vi ved den understregede betingelse en udvælgelse, der sikrer en hurtigere vandring til det optimale punkt.

Mere præsist kan dette opspaltes i følgende problemer:

1) Hvorledes kommer man fra det extreme basispunkt til et aiidet
extremt punkt,

når vi samtidig må forlange, at

2) Det nye extreme punkt skal repræsentere et program, der er mere
optimalt end det oprindelige.

ad 1) Vi har tidligere omtalt, at de extreme punkter repræsenterer et program bestående af så få processer som muligt. Da basissystemet opfylder denne betingelse, kan vi nå til det nye system ved at udvælge een proces blandt de ikke benyttede og lade den indgå i det nye system til afløsning for een af processerne i basissystemet.

ad 2) Denne ombytning af processer må foretages således, at vi sikrer
os overholdelse af punkt 2). Vi må derfor besvare følgende spørgsmål:

a) Er det muligt at foretage en sådan udvælgelse blandt de ikke benyttede
processer, at punkt 2) opfyldes, eller er vi allerede i den
optimale situation?

b) Hvilken proces skal vi vælge at indføre?

c) Hvilken proces fjerner vi fra programmet?

For så nemt som muligt at besvare disse pørgsmål opstiller vi vort
basissystem i en såkaldt simplextabel.

Ved opstillingen af denne første simplextabel er vi gået ud fra vort
exempel, og vi har benyttet spillerumsprocesserne som basissystem. Kun
en del af tabellen er naturligvis vist.

I tabellens 2. søjle er de benyttede basisprocesser angivet; i 1. søjle
de tilsvarende enhedsdækningsbidrag, som her alle er lig 0. I 2. række

er knaphedspunktet og samtlige mulige processer opført; i 1. række de tilsvarendeenhedsdækningsbidrag.

I 3. søjle finder vi de intensiteter af basisprocesserne, der netop giver
A. Når vi benytter spillerumsprocesserne, som netop har enhed fælles
med de tilsvarende råstoffer, får vi selvfølgelig her de tildelte mængder.

I de følgende søjler er for hver af de mulige processer angivet de intensiteter af basisprocesserne, der svarer til een enhed af den respektive proces i 2. række. Eller sagt på en anden måde, de intensitetsreduktioner af basisprocesserne, som indførelse af een enhed af de respektive processer på grund af begrænsningerne ville medføre. Indførelse i basisprogrammet, som netop fuldt anvender hele A, af een enhed af XX_{n +i} vil naturligvis betyde, at een enhed af XX_{n +i} i basisprogrammet må gå ud; for de øvrige basisprocesser sker der intet ved indførelsen af XX_{n +i.}

Indførelse af een enhed af Xi vil nødvendigvis føre til, at den basisproces, der svarer til råstof Ai, må reduceres med det, som Xi bruger af dette råstof. Tilsvarende for de andre basisprocesser, og vi får derfor, at det der skal stå under processerne netop er deres forbrugskonstanter.

Det må understreges, at disse konstanter netop angiver intensitetsreduktioner
for basisprocesserne ved indførele af een enhed af den pågældende
proces med basissystemet som udgangspunktll).

I nederste række er angivet følgende:

Under A-søjlen summen af enhedsdækningsbidragene fra 1. søjle multipliceret med de tilsvarende intensiteter i A-søjlen, eller med andre ord det totale dækningsbidrag for basisprogrammet. I dette tilfælde, hvor basisprogrammet lader samtlige tildelinger übenyttede, selvfølgelig lig 0.

Under processøjlerne er angivet z - c; z markerer summen af enhedsdækningsbidragene fra 1. søjle multipliceret med de tilsvarende intensitetsreduktioner under processen, zj angiver derfor den samlede virkning (reduktion) på det totale dækningsbidrag som følge af, at basisprocesserne reduceres for at give plads for een enhed af Xj. Trækker man herfra processen Xj's enhedsdækningsbidrag c, bliver det samlede resultat nettoreduktionen af det totale dækningsbidrag ved indførelse af een enhed af processen med basisprogrammet som udgangspunkt.

Når man benytter spillerumsprocesserne som basisprogram, er opstillingen af denne 1. simplextabel blot en indførelse af de kendte konstanter i skemaet plus nogle simple regninger for den nederste rækkes vedkommende.

Ud fra denne tabel er vi imidlertid i stand til at besvare spørgsmålene
om overgangen til det nye program (2 a), b) og c) på side 204).

ad a) For nettoreduktionerne af det totale dækningsbidrag i nederste
række, og for intensitetsreduktionerne i søjlerne gælder følgende gensidigt
udelukkende og eneste muligheder:

---

11) Slfrcmt vi ikke havde anvendt spillerumsprocesserne (eller hjselpeprocesser), men m vilkarlige processer som basissystem, matte vi for at finde disse konstanter have last n+ m+l ligningssystemer. Hvis de q farste processer var basisprocesser for konstanterne under X_k f. ex.: a_ll *1 + al2a₁₂ X2X₂ + + a_lq Xq = ai_k a2la₂₁ x_l + a22a₂₂ X2X₂ + + a_2q f TXT_X a_ml x_l + a_m2 X2X₂ + +aq+ a_mq x_q = a_mk

I: Samtlige nettoreduktioner er 0.

Det er således ikke muligt ved indførelse af nye processer i basisprogrammet
at nå til en mere optimal løsning. Vi befinder os i den optimale

II: En eller flere af nettoreduktionerne er < 0.

Indførelsen af en af disse processer vil derfor føre til en forøgelse af
det totale dækningsbidrag og dermed til en mere optimal løsning.

Vi må dog her sondre mellem:

1. Alle intensitetsreduktioner er 0 for mindst een af processerne
med nettoreduktioner < 0. Indførelsen af en af disse processer
vil altså på grund af begrænsningerne medføre, at intensiteterne af
nogen af basisprogrammets processer må reducere for at give plads
for den nye proces. Vi kan derfor fortsætte indførelsen af den nye
proces ad infinitum og sålede:; øge det totale dækningsbidrag
i det uendelige.
Det siger sig selv, at forekomsten af en sådan situation i praksis vil
være ulogisk. Dens forekomst vil som regel betyde, at en regnefejl
har indsneget sig, eller at problemet er opstillet forkert, f. ex.
ved at man har overset en knaphedsfaktor.

2. Nogle intensitetsreduktioner i samtlige søjler under processer med
nettore duktioner < 0 er > 0.
Indførelsen af en af disse processer vil derfor på grund af begrænsningerne
nødvendiggøre en reduktion af en eller flere af
basisprocesserne. Når indførelsen af processen er drevet så langt
at een af basisprocesserne helt er fjernet fra programmet, støder
vi igen mod begrænsningerne; vi har nået et nyt extremt punkt.

ad b) Såfremt flere af de ikke benyttede processer har nettoreduktioner,
der er mindre end 0, skal vi altså træffe et valg mellem disse12).
Hvilken af dem skal vi indføre i systemet?

Formålet med at udvælge en bestemt proces måtte være at nå det optimale program gennem så få tabeller som muligt. Vi er imidlertid ikke i stand til at angive retningslinier herfor. Selv om man anvender den proces, der har den mest negative nettoreduktion, er det ikke afgjort,

---

12) Samtlige basisprocesser må naturligvis have nettoreduktioner lig 0. Afvigelser herfra ville betyde, at betingelsessystemet ikke var opfyldt, intensiteterne måtte ndres, samtlige disse nettoreduktioner var lig 0, med andre ord indtil vi befandt os i det extreme punkt.

at vi herved opnår det ønskede. Vi kan kort sige det således, at vi eventuelthurtigere støder mod begrænsningerne, eller at vi måske når et extremt punkt, hvorfra vejen til det optimale er længere end fra et andetextremt

Når vi nu intet bestemt kan sige, kan vi ikke gøre noget bedre end
at vælge processen med den mest negative nettoreduktion til indførelse.
Lad os antage, at denne proces er Xk i 1. simplextabel.

ad c) Hvilken proces, lad os kalde den Xr, skal vi fjerne af hensyn til
indførelsen af Xk?

Vi har tidligere under 11, 2, omtalt, at vi er i stand til at indføre mere
og mere af Xk, indtil intensiteten af een af basisprocesserne er reduceret
til 0. Med udvælgelsen af Xk er Xr altså fastlagt.

Vi dividerer de positive elementer i søjlen Xk op i de tilsvarende
intensiteter i søjlen under A og vælger Xr som den basisproces, der har
det mindste af disse forhold13).

Efter at have udvalgt de 2 processer skal vi nu finde konstanterne for det nye program. Vi har set, hvorledes den 1. simplextabel for vort basissystem indeholdt alle nødvendige oplysninger. Vi skal opstille en ny simplextabel for det nye system, der består af processerne i basissystemet med undtagelse af Xr, men i stedet med Xk.

Lad os betegne samtlige elementer i 1. simplextabel med hvor i angiver raekken (basisprocessen) og j sejlen (en mulig proces). Lad sojien under A have nummer 0 blandt sejlerne og den nederste raekke nummer 0 blandt raekkerne.

Udregningen af konstanterne i den nye tabel lettes nu betydeligt ved
at anvende følgende formler.

hvor a* betegner elementerne i den nye tabel

Med den angivne nummerering af søjler og rækker kan formlerne anvendes til udregning af alle konstanter i den nye tabel. Formlerne kan, når man erindrer elementernes betydning, udledes ved driftsøkonomiske

Degeneration.

Under bestemmelsen af Xr har vi nævnt, at flere af basisprocesserne

---

13) Angående det tilfælde, hvor mere end een basisproces har dette mindste forhold, se næste afsnit om degeneration.

kunne have samme mindste forhold. Ved indførelsen af Xk vil derfor mere end een af basisprocesserne gå ud. Dette betyder, at vi med Xk og de resterende basisprocesser alene kan opfylde betingelserne. Med mindre end m kan vi imidlertid ikke udtrykke en enhed af samtlige mulige processer. Vi kan ikke få fat i, hvilke intensitetsreduktioner indførelsen af een enhed af for exempel Xj vil nødvendiggøre. Vi kan derfor ikke på samme måde finde de nye Xk og X_r.

Vil vi derfor bevare simplexmetodens anvendelighed i sådanne tilfælde, må vi sikre os, at ikke mere end een basisproces går ud. Dette problem er løst af A. Gharnes¹⁴), som har vist, at simplexmetoden er generelt anvendelig, såfremt man blot yderligere overholder følgende regler:

1) Rækkefølgen af processerne i2. række og dermed af søjlerne holdes
konstant hele undersøgelsen igennem.

2) Vi må vælge, hvilken af de basisvektorer, der har det samme mindste forhold, vi skal lade gå ud. De andre må vi lade blive, selv om de har 0 i søjlen under A. For at afgøre hvilken divideres alle elementer i en af de rækker, der står ud for en af de aktuelle basisprocesser med det tilsvarende element i den k'te søjle. Dette gennemføres for alle de aktuelle rækker. Vi sammenligner nu de fremkomne rækker af forhold, idet vi begynder fra venstre og går mod højre. Første gang vi møder en forskel mellem forholdene i rækkerne, standser vi og r vælges ved det forhold, der her er mindst. En sådan forskel må nødvendigvis indtræde, og r er derfor fuldstændig determineret ved denne regel.

Fremgangsmåden ved udledningen af et optimale program er altså
følgende:

1) Udvælg et basisprogram bestående af m processer og opstil den
første simplextabel.

2) Vi undersøger, om I eller 11. 1. foreligger; såfremt dette er til
fældet, er opgaven løst.

3) Såfremt 11. 2. foreligger, udvælger vi Xk og Xr efter de angivne
kriterier og opstiller efter formlerne og med overholdelse af de
angivne regler den nye simplextabel.

4) Denne tabel undersøges som under 2) beskrevet 0.5.v., indtil vi

---

14) [1] og [5]

efter et antal simplextabeller mindre end antallet af processer
standser ved I eller 11. 1.

E. Begreber, forudsætninger og anvendelsesområde.

Er opstillingen af denne slags modeller nu andet og mere end et morsomt teoretisk tankespil? Dette vil selvsagt afhænge af, om man i praksis er i stand til med tilstrækkelig tilnærmelse at indpasse virkelighedens forhold i det matematiske 1. p.-system.

Efter den foregående fremstilling er det rimeligt at opspalte 1. p.problemet
i følgende 3 hovedelementer:

1) Procesbegrebet.

2) Fordelagtighedskriteriet.

3) Betingelsessystemet.

En omtale af disse 3 hovedelementer vil tjene som svar på det spørgsmål,
vi ovenfor har stillet os.

1. Procesbegrebet.

I vort specielle exempel har vi talt om produktionsprocesser - produktion af en vare - og spillerumsprocesser, der blot fortæller, hvormeget af tildelingerne af de enkelte råstoffer, man ikke udnytter. Lægger man imidlertid vægt på, at 1. p.'s anvendelsesområde er alle sådanne problemer, som lader sig udtrykke som en matematisk opgave af den angivne art, er det klart, at procesbegrebet får et meget videre omfang.

Det vil sikkert være på sin plads her at nævne nogle af de forskellige
indhold, man ved allerede foretagne praktiske undersøgelser har tildelt
begrebet.

Fra en planlægning af luftbroen til Berlin kan det således nævnes, at man som processer har opereret med komplekser som „Supplying Berlin", „Flying the Airlift", „Constructing runways in Berlin" o. lign. I diætproblemet er en proces simpelthen det at anvende en bestemt fødevare i kostplanenls). Procesbegrebet kan således bringes til anvendelsemed et meget forskelligartet indhold, og det er derfor rimeligt

---

15) I diætproblemet søger man den billigste kostration ved sammensætning af visse fødevarer. Kostrationen skal opfylde visse minimumskrav (og maximumskrav) med hensyn til vitaminindhold, kalorieindhold o. lign.

meget generelt at definere en proceis som en speciel metode til udførelsenaf
en bestemt opgave16).

I 1. p. optræder processen i to forskellige relationer, nemlig i

1) fordelagtighedskriteriet (2) og i

2) betingelsessystemet (1)

2. Fordelagtighedskriteriet.

Den enkelte proces er forlenet med en ganske bestemt fordelagtighed
pr. enhed, og om denne fordelagtighed gælder de 2 forudsætninger,
linearitetsbetingelsen og additivitetsbetingelsen.

Hvorledes man i den enkelte opgave udtrykker denne fordelagtighed er i og for sig ikke afgørende. I exemplet har vi anvendt varens enhedsdækningsbidrag som et samlet udtryk for den enkelte proces fordelagtighed. Man kan naturligvis udmærket ved opstillingen af problemet spalte fordelagtigheden op ved at anføre en række forbrug og priser, tildele de knappe råstoffer en pris 0.5.v.; men man må så indføre forudsætninger om konstante enhedsforbrug, konstanter priser o. lign.

I diætproblemet, hvor man som sagt søger den billigste kostration og
derfor skal minimere fordelagtighedsfunktionalen, er den enkelte proces
fordelagtighed negativ - udtrykt ved fødevarens pris.

Det principielle bliver dog under alle omstændigheder, at der til
hver proces er knyttet en bestemt enhedsfordelagtighed.

Det følger heraf ,at man ved en isoleret betragtning i maximeringsopgaver
vil anvende samtlige processer med positiv fordelagtighed ad infinitum;
de med negativ fordelagtighed vil slet ikke blive anvendt.

Først ved indførelsen af betingelsessystemet får problemet derfor økonomisk perspektiv. Samtlige processer må inddrages i dette betingelsessystem - i exemplet må alle processer forbruge mindt eet af de knappe råstoffer - ellers er problemet ikke determineret.

3. Betingelsessystemet.

I det foregående har vi benyttet rå.stofknapheder som exempel på forhold, der kan udtrykkes gennem betingelsessystemet. Vi skal ganske summarisk nævne en række andre forhold, der exempelvis kan danne den reelle baggrund for betingelsessystemet i andre opgaver:

1) Produktionsbetingelser, kvalitetsbetingelser.

---

16) Jfr. [2] p. 1. I 1. p. anvender man ofte betegnelsen activity.

2) Kapacitetsgrænser for afdelinger eller maskiner.

3) Likviditetsknaphed

4) Mindsteproduktion af en vare af hensyn til good-will eller leve
ringsforpligtelser.

5) Leverandørens kapacitet.

6) Legale påbud.

7) I dynamiske modeller den ene periodes afhaengighed af den foregaende
periodes produktion og forbrug.

Såvel interne som externe forhold kan altså danne grundlaget for betingelsessystemet. Ligesom ved fordelagtighedsfunktionalen er det af hensyn til den matematiske løsning en forudsætning, at processernes intensiteter indgår i betingelsessystemet på en sådan måde at

1) Lineariteten

og 2) Additiviteten
overholdes.

Hvad dette betyder, vil naturligvis være forskelligt efter, hvad betingelsessystemet dækker over. Generelt kan man sige, at der til hver proces må være knyttet et antal konstanter svarende til antallet af betingelser; disse konstanter må være upåvirkede af den enkelte og de øvrige processers intensiteter. Såfremt en proces ikke påvirkes af en betingelse, er den tilsvarende konstant lig O17).O¹⁷).

Betingelsessystemet udgør som nævnt det økonomiske element i 1. p.modeller. Hvor det uden det for den enkelte proces var et enten eller, er der med dets indførelse sat bestemte grænser, der gør en udvælgelse af processer og en fixering af intensiteter nødvendig.

Ved linearitets- og additivitetsbetingelserne for fordelagtighedsfunktionalen fjerner vi den økonomiske variation i produktionsomfang og i substitution. Som modstykke til dette har vi for linearitetsbetingelsen den enkelt proces betingelseskonstanter i forhold til begrænsningerne og for additivitetsbetingelsen processernes „konkurrerende beslaglæggelse af kapacitet".

I denne forbindelse er det meget væsentligt at bemærke, at netop
betingelsessystemet giver os en mulighed for at begrænse den restriktivevirkning
af forudsætningerne. En tilpasning mellem de virkelige

---

17) Hele denne samling af konstanter plus konstanterne på højre side af lighedstegnene i betingelsessystemet betegnes i almindelighed i 1. p.-litteraturen for „teknologien".

forhold og processernes forudsatte linearitet og additivitet både med
hensyn til fordelagtighed og betingelser (f. ex. forbrug og gevinst) kan
opnås ved en opdeling af processerne.

Det kan således være rimeligt at opdele en proces efter, om den udføres i normal arbejdstid eller ved overarbejde, om det drejer sig om produktion af de første 1000 stk., hvor man kan påregne at afsætte til en stykpris på 200 kr., eller de næste 500 stk., som man antager at måtte sælge for 175 kr. pr. stk.

To processer kan opdeles i 4 med. en samtidig opdeling af et fælles råstof i 2 med den begrundelse, at råstoffet må indkøbes til 400 kr. pr. ton for de første 5000 tons, men derefter kan fåes for 350 kr. pr. ton o.s.v.

De enkelte processer opdeles i nye processer hver med sine betingelsesog
fordelagtighedskonstanter, og der indføres nye betingelser, som sikrer,
at processerne bringes til anvendelse i den rigtige rækkefølge.

Dette er som bekendt i overensstemmelse med de kompromisser, man i praksis ofte indgår. Teoretisk set er der intet i vejen for, at man på denne måde kunne dække de faktiske forhold, men i praksis skal man jo før eller siden til at løse den matematiske opgave. Man må derfor, selv om man med hulkort- og elektronregnemaskiner kan klare store opgaver, i den enkelte situation afveje forholdene mod hinanden.

På grund af den usikkerhed, der ligger i problemernes natur, vil det ofte være rimeligt at operere med forholdsvis grove modeller. Ved planlægningen af luftbroen til Berlin havde man først opstillet en detailleret model, som man imidlertid af beregningsmæssige grunde reducerede. Man opnåede alligevel realitiske og værdifulde oplysninger¹⁸).

I øvrigt har man fundet metoder, hvorved man i specielle tilfælde kan løse problemer af ikke lineær art. Med det vi ovenfor har sagt om forholdet mellem betingelsessystem og forudsætninger in mente, forekommer det dog fornuftigt som Dorfrnan at betegne forudsætningerne som: „convenient in practice, not essential in theory"l9).

For yderligere at understrege den økonomiskabende betydning betinsessystemetkan tildeles eller mere generelt sagt for at illustrere den sammenhæng, der er mellem samtlige 1. p.-begreber, kan vi nævne, at man udmærket kan operere med processer med negativ fordelagtighed. Processer, hvis eneste berettigelse i systemet består i, at de præsterer afkast,som kan konsumeres af processer med positiv fordelagtighed. Vi

---

18) [2] p.p. 202.

19) [3] p. 93.

har nævnt, at der i luftbro-modellen indgik processer som „constructing
runways in Berlin".

En simpel følge af disse ræsonnementer er en udvidelse fra at betragte
processernes betingelseskonstanter alene i forhold til de i udgangssituationen
givne konstanter (højre side af betingelsesligningerne).

Processernes elementer opdeles i input og output og på tværs heraf
i primary, intermediate og final factors, hvor de 2 første begreber må ses
i relation til den enkelte proces, de 3 sidste til problemet som helhed.

Intermediate factors optræder som output i visse processer, som input i andre. Den omkostning, der er forbundet med at opnå en intermediate factor som output, viser sig i 1. p.-modellen dels som en eventuel negativ fordelagtighed for processen (real cost) dels som en beslaglæggelse af primary factors (opportunity cost). På „indtægtssiden" viser processens resultat sig som en forøgelse af mulighederne for anvendelse af andre processer.

Final factor indgår alene i fordelagtighedskriteriet.

Vi har hermed skitseret det centrale i hele den iagttagelsesmåde, der er særkendet for ).. p. Det økonomiske element kommer ikke alene frem i fordelagtighedsfunktionalen, men i mindst lige så høj grad i betingelsessystemet i forbindelse med processernes samspil. Dette er i fuld overensstemmelse med det generelle økonomiske princip, at knaphed i videste forstand er begrundelsen for enhver form for økonomi.

Afsluttende bemærkninger.

De sidste bemærkninger antyder, at 1. p. snarere end at være en speciel metode må betragtes som en teori. Hvorvidt det bliver den afløser for marginalteorien, som mange spår, er et spørgsmål, som de kommende år skal besvare.

L. p. er i hvert fald fra pionerernes side ment som et svar på de krav, man i praksis stiller til en driftsøkonomisk teori. Man har direkte mødt problemerne og hertil søgt at udvikle et apparat, der var simpelt og handy.

L. p. er hovedsagelig blevet anvendt i U.S.A. af de store statsinstitutioner (Air Force) og indenfor visse storindustrier (olie). Herhjemme foligger kun enkelte forsøg, men det må afgjort være af den største betydning, om man snarest fik høstet de erfaringer, som skal betinge og belyse mulighederne for en fremtidig anvendelse.

LITTERATURHENVISNING

Litteraturhenvisning.

[1] A. Charnes, W. W. Cooper and A. Henderson: „An Introduction to Linear
Programming".

[2] Tjalling C. Koopmans: „Activity Analysis of Production and Allocation".
[3] Robert Dorfman: „Application of Linear Programming to the theory of the firm".

[4] A. Charnes, W. W. Cooper and B. Mellon: „Blending Aviation Gasolines", Econometrica

Der er her kun nævnte 3 standardværker - der forøvrigt indeholder omfattende litteraturhenvisninger
- og et referat af en praktisk anvendelse.

danske tidsskriftsartikler kan nævnes:

[5] Sven Danø: „Linear programming i produktionsteorien, I, II og 111.
Nationaløkonomisk Tidsskrift, numrene 3-4, 1955, 5-6, 1955 og 1-2, 1956.

[6] Sven Danø og David Gale: „Linear programming: An introduction to the methods".
Nordisk Tidsskrift for teknisk Økonomi, nr. 40, 1954.

[7] Niels Nielsen: „Lineær programmering", Nordisk Tidsskrift for teknisk Økonomi,
nr. 42, 1955.

[8] Niels Nielsen: „Nogle driftsøkonomiske anvendelse af lineær programmering".
Mercantilia, nr. 1, 1956.