Ungarsk løsningsmetode. Ungarsk metode for å løse oppgaveproblemer

Løsningsalgoritme:

1. Vi løser problemet til et minimum. Mål dette trinnet- oppnå maksimalt mulig antall nuller i matrise C. For å gjøre dette finner vi minimumselementet i matrise C i hver rad og trekker det fra hvert element i den tilsvarende raden. På samme måte trekker vi fra det tilsvarende minimumselementet i hver kolonne.

Hvis en ikke-kvadratisk matrise er gitt, gjør vi den kvadratisk ved å sette kostnadene lik maksimalt antall i den gitte matrisen.

2. Hvis det etter å ha fullført det første trinnet er mulig å lage tildelinger, det vil si å velge et nullelement i hver rad og kolonne, vil den resulterende løsningen være optimal. Hvis avtalene ikke kunne gjøres, fortsett til tredje trinn.

3. Ved å bruke minimum antall linjer, krysser vi ut alle nullene i matrisen, og blant de ikke overkryssede elementene velger vi den minste, legger den til elementene som står i skjæringspunktet mellom linjene og trekker den fra alle de ikke kryssede ut elementer. Deretter går du videre til trinn 2.

Ungarsk metode mest effektivt når du løser transportproblemer med heltallsvolumer av produksjon og forbruk.

Eksempel

Oppgaveoppgaven er et spesialtilfelle av transportproblemet, der ai = bj = 1. Derfor kan det løses med transportproblemalgoritmer. La oss vurdere en annen metode, som er mer effektiv og tar hensyn til spesifikasjonene til den matematiske modellen. Denne metoden kalles den ungarske algoritmen.

Den består av følgende trinn:

1) transformasjon av matriserader og kolonner;

2) bestemmelse av formål;

3) modifikasjon av den transformerte matrisen.

1. trinn. Målet med dette trinnet er å oppnå maksimalt mulig antall nullelementer i matrise C. For å gjøre dette trekker du minimumselementet til den tilsvarende raden fra alle elementene i hver rad, og trekker minimumselementet i den tilsvarende kolonnen fra alle elementene. av hver kolonne.

2. trinn. Hvis, etter å ha utført det første trinnet, ett nullelement kan velges i hver rad og hver kolonne i matrise C, vil den resulterende løsningen være en optimal tilordning.

3. trinn. Hvis en tillatt løsning bestående av nuller ikke er funnet, trekker vi minimum antall linjer gjennom noen kolonner og rader slik at alle nuller er krysset ut. Velg det minste ukrysset element. Vi trekker dette elementet fra hvert ukrysset element og legger det til hvert element som står i skjæringspunktet mellom de tegnede linjene.

Hvis etter 3. trinn optimal løsning ikke oppnås, bør prosedyren for å tegne rette linjer gjentas til en akseptabel løsning er oppnådd.

Eksempel.

Fordel ressurser mellom objekter.

Løsning. 1. trinn. Verdiene til minimumselementene i rad 1, 2, 3 og 4 er henholdsvis 2, 4, 11 og 4. Ved å trekke den tilsvarende minimumsverdien fra elementene i hver rad får vi

Verdiene til minimumselementene i kolonnene 1, 2, 3 og 4 er henholdsvis 0, 0, 5, 0. Ved å trekke den tilsvarende minimumsverdien fra elementene i hver kolonne får vi

2. trinn. Ingen fullstendig oppdrag er mottatt og kostnadsmatrisen må endres.

3. trinn. Kryss av kolonne 1, rad 3, rad 2 (eller kolonne 2). Verdien av minimum ukrysset element er 2:

Vi trekker det fra alle ukryssede elementer, og legger det til med alle elementene plassert i skjæringspunktet mellom to linjer, får vi

Svar. Vi leder den første ressursen til det tredje objektet, den andre - til det andre objektet, den fjerde - til det første objektet, den tredje ressursen - til det fjerde objektet. Destinasjonskostnad: 9 + 4 + 11 + 4 = 28.

Notater 1. Hvis den opprinnelige matrisen ikke er kvadratisk, må du introdusere fiktive ressurser eller fiktive objekter for å gjøre matrisen kvadratisk.

Oppgaveproblemet

Algoritme for å løse flaskehalsoppgaveproblemet

Problem med flaskehalsoppdrag

FOREDRAG 13. Oppgaveproblemer. Ungarsk algoritme

Dette problemet løses av algoritmen beskrevet ovenfor. Her er produksjonen hennes.

Tilgjengelig n jobber på et eller annet samlebånd og n arbeiderne som må tildeles disse jobbene; kjent ytelse c ij arbeider Jeg på jobb j. Det faktum at, med en viss fordeling til jobber, en arbeider jeg k faller på arbeidsplass jk kan beskrives ved følgende tabell:

Å ha en måte s oppdrag til arbeidsplasser, kan du finne minimumsproduktiviteten som er spesifikk for denne metoden og merke seg at det er denne minimumsproduktiviteten som bestemmer hastigheten og produktiviteten til transportbåndet. Arbeidsplassen der minimumsproduktiviteten er realisert kalles flaskehals i oppdraget.

Målet er å maksimere

Trinn 0. Vi fikser produktivitetsmatrisen og eventuelle oppdrag til jobber. La s- minimum ytelse for dette formålet. La oss bygge arbeidsark samme dimensjoner som matrisen C; i en celle med et tall ( ij) i denne tabellen vil vi sette symbolet “´” hvis ; ellers lar vi denne cellen stå tom.

Trinn 1. Tatt i betraktning regnearket konstruert i forrige trinn som et regneark i algoritmen for å velge den største matchingen i en todelt graf, vil vi finne den tilsvarende største matchingen. Hvis det viser seg n ribber, så gjenopprettes en ny tilordning til jobber basert på dem og med en ny, høyere, minimum ytelse. La oss betegne det igjen med s og tilbake til Trinn 0. Hvis antall kanter er mindre n, da er den eksisterende tilordningen til jobber allerede optimal.

Problemformuleringer:

Eksempel 13.1. Nødvendig for å distribuere m arbeider (eller utøvere) på n maskiner. Jobb Jeg (Jeg=1,...,m), utført på en maskin j(j=1,..., n), er forbundet med kostnader. Oppgaven består i å fordele arbeid på tvers av maskiner (en jobb utføres på en maskin) som tilsvarer minimering totale kostnader c ij.

Eksempel 13.2. C=(c ij) – produksjonskostnad for delen Jeg på maskinen j du må finne fordelingen av maskiner slik at den totale produksjonskostnaden er minimal.

Eksempel 13.3. Transportproblem. Produksjonssteder for varer og forbrukssteder for varer er spesifisert. Det er nødvendig å bestemme den optimale en-til-en-korrespondansen mellom produksjonspunkter og forbrukspunkter, basert på transportkostnadsmatrisen C mellom relevante punkter (dvs. minimer de totale transportkostnadene).

Her representerer verkene "opprinnelsespunktene" og maskinene representerer "destinasjonspunktene". Tilbudet ved hvert kildepunkt er lik 1. På samme måte er etterspørselen ved hvert destinasjonspunkt lik 1. Kostnaden for å "transportere" (feste på) arbeidet Jeg til maskinen j lik c ij. Hvis noe arbeid ikke kan utføres på en bestemt maskin, anses den tilsvarende kostnaden for å være svært et stort antall.

Før du løser et slikt problem, er det nødvendig å eliminere ubalansen ved å legge til fiktivt arbeid eller maskiner avhengig av startforholdene. Derfor, uten tap av generalitet kan vi sette m = n.

La = 0 hvis j-arbeidet mitt blir ikke gjort på Jeg-th maskin, = 1, if j-Jeg jobber utføres på Jeg-te maskinen. Dermed kan løsningen på problemet skrives i skjemaet todimensjonal matrise. En gjennomførbar løsning kalles avtale. En gjennomførbar løsning er konstruert ved å velge nøyaktig ett element i hver rad i en matrise og nøyaktig ett element i hver kolonne i den matrisen.

Merknad 1 . For en gitt verdi n finnes n! gjennomførbare løsninger.

Matematisk modell oppgaver:

Minimer funksjon , med restriksjoner:

, (12.1)

, (12.2)

Begrensninger (12.1) er nødvendige for å sikre at hver jobb utføres nøyaktig én gang. Begrensninger (12.2) garanterer at hver maskin vil bli tildelt nøyaktig én jobb.

Eksempel 13.4. For å illustrere oppgaveproblemet kan du vurdere en tabell med tre jobber og tre maskiner. Del produksjonskostnad Jeg på maskinen j :

Vi må finne fordelingen av maskiner slik at den totale produksjonskostnaden er minimal.

Den spesifikke strukturen i oppgaveproblemet gjør det mulig å bruke effektiv metodeå løse det.

Notat 2. Den optimale løsningen på problemet vil ikke endres hvis en vilkårlig konstant verdi trekkes fra en hvilken som helst rad eller kolonne i kostnadsmatrisen.

Merknad 2 viser at dersom det er mulig å konstruere en ny matrise med nullelementer og disse nullelementene eller en delmengde av dem tilsvarer en tillatt løsning, så vil en slik løsning være optimal.

.

Optimalt reisemål: , , , andre , .

Dessverre er det ikke alltid mulig å bestemme løsningen så enkelt. For slike tilfeller bør du vurdere følgende algoritme.

Trinn 1.(Reduksjon av rader og kolonner). Målet med dette trinnet er å oppnå maksimalt mulig antall nullelementer i kostnadsmatrisen. For å gjøre dette trekkes minimumselementet i den tilsvarende raden fra alle elementene i hver rad, og deretter trekkes minimumselementet i den tilsvarende kolonnen fra alle elementene i hver kolonne i den resulterende matrisen. Som et resultat oppnås en redusert kostnadsmatrise og fortsetter med å søke etter oppdrag.

Steg 2.(Definisjon av oppgaver). På dette trinnet kan du bruke algoritmen for å finne den "største matchingen med en matrise av en todelt graf (det er andre muligheter), hvis alle =0 i matrisen er erstattet med "1", og >0 med "0" .

Hvis det fulle formålet ikke kan bli funnet, er ytterligere modifikasjon av kostnadsmatrisen nødvendig, dvs. gå til trinn 3.

Trinn 3. (Endring av den reduserte matrisen). For matrisen for reduserte kostnader:

a) Beregn antall nuller i hver ukrysset rad og hver ukrysset kolonne.

b) Kryss ut raden eller kolonnen med maksimalt antall nuller.

c) Utfør trinn a) og b) til alle nuller er krysset ut.

d) Fra alle ukryssede elementer, trekk fra minimum ukrysset element og legg det til hvert element som befinner seg i skjæringspunktet mellom to linjer.

Gå til trinn 2.

Merknad 3.Hvis originalt problem er et maksimeringsproblem, bør alle elementene i kostnadsmatrisen multipliseres med (-1) og legges til med tilstrekkelig et stort antall slik at matrisen ikke inneholder negative elementer. Problemet bør da løses som et minimeringsproblem.

Eksempel 13.5. La oss demonstrere driften av den ungarske algoritmen ved å bruke eksemplet på et tildelingsproblem med følgende kostnadsmatrise:

.

Iterasjon 1

Trinn 1. Reduksjon av rader og kolonner.

Verdiene til minimumselementene i rad 1, 2, 3 og 4 er henholdsvis 2, 4, 11 og 4. Ved å trekke den tilsvarende minimumsverdien fra elementene i hver rad, får vi følgende matrise:

.

Verdiene til minimumselementene i kolonnene 1, 2, 3 og 4 er henholdsvis 0, 0, 5 og 0. Ved å trekke den tilsvarende minimumsverdien fra elementene i hver kolonne, får vi følgende matrise.

Meningsfull formulering av problemet. Det er n biler i foreningen, hver i stand til å transportere Q i tonn last per måned (i = 1,2,..., n). Med deres hjelp er det nødvendig å sikre transport av varer (trelast, skruer, etc.) fra leverandører til forbrukere ved å n ruter i mengden R j tonn per måned (j = 1,2,..., n).
Oppgaven er å transportere alt godset med minimale kostnader, for å gjøre dette må hver bil sendes langs sin rute. Hvis bilens evne til å transportere last er lavere enn forbrukerens behov for denne lasten, da denne ruten kjøretøyet kan ikke tildeles. Derfor blir det satt sammen en matrise C som karakteriserer kostnadene i-th bil, hvis den er tildelt j-th rute.

Ungarsk metode for å løse oppgaveproblemer

Algoritme for den ungarske metoden.

Oppgaveproblemet er et spesialtilfelle av transportproblemet, så enhver algoritme kan brukes til å løse det lineær programmering, men det er mer effektivt Ungarsk metode.

De spesifikke egenskapene til oppgaveproblemer ga opphav til fremveksten av en effektiv ungarsk metode for å løse dem. Hovedideen med den ungarske metoden er å flytte fra originalen kvadratisk matrise verdi C til dens ekvivalente matrise Ce med ikke-negative elementer og et system med n uavhengige nuller, hvorav ikke to tilhører samme rad eller samme kolonne. For en gitt n er det n! gjennomførbare løsninger. Hvis vi i oppdragsmatrisen X ordner n enheter slik at det i hver rad og kolonne kun er én enhet, arrangert i samsvar med de lokaliserte n uavhengige nullene til den ekvivalente kostnadsmatrisen Se, så får vi gjennomførbare løsninger på tildelingsproblemet.

Det bør tas i betraktning at for ethvert ugyldig oppdrag antas den tilsvarende kostnaden betinget å være lik et tilstrekkelig stort antall M i minimumsproblemer. Hvis den opprinnelige matrisen ikke er kvadratisk, bør et ekstra nødvendig antall rader eller kolonner introduseres, og elementene deres skal tildeles verdier bestemt av betingelsene for problemet, muligens etter reduksjon, og de dominerende alternativene, dyre eller billig, bør utelukkes.

UNGARSK METODE

Den ungarske metoden er en av de mest interessante og vanligste løsningsmetodene transportoppgaver.

La oss først vurdere hovedideene til den ungarske metoden ved å bruke eksempelet på å løse et valgproblem (oppgaveproblem), som er et spesialtilfelle av T-problemet, og deretter generalisere denne metoden for et vilkårlig T-problem.

Ungarsk metode for oppgaveproblemet

Formulering av problemet. La oss anta at det er det ulike arbeider og mekanismer, som hver kan utføre hvilken som helst jobb, men med ulik effektivitet. Vi betegner ytelsen til mekanismen når du utfører arbeid, og = 1,...,n; j = 1,...,n. Det kreves å fordele mekanismene mellom jobbene på en slik måte at den totale effekten av bruken av dem maksimeres. Denne oppgaven kalles valg problem eller oppdragsproblem.

Formelt er det skrevet slik. Du må velge følgende sekvens av elementer fra matrisen

slik at summen er maksimal og samtidig fra hver rad og kolonne MED bare ett element ble valgt.

La oss introdusere følgende konsepter.

Null matriseelementer MED kalles uavhengige nuller hvis for noen rad og kolonne i skjæringspunktet som elementet er plassert ikke inneholder andre slike elementer.

To rektangulære matriser MED Og D kalles ekvivalente ( C ~ D), hvis for alle jeg, j. Tildelingsproblemer definert av ekvivalente matriser er ekvivalente (det vil si at de optimale løsningene for en av dem vil være optimale for den andre, og omvendt).

Beskrivelse av den ungarske metodealgoritmen

Algoritmen består av et innledende stadium og ikke mer enn ( n-2) sekvensielle iterasjoner. Hver iterasjon er assosiert med ekvivalente transformasjoner av matrisen oppnådd som et resultat av forrige iterasjon, og med valget av maksimalt antall uavhengige nuller. Det endelige resultatet av iterasjonen er en økning i antall uavhengige nuller med én. Så snart antallet uavhengige nuller blir likt n, problemet med valg er løst, og beste alternativet tilordninger bestemmes av posisjonene til de uavhengige nullene i den siste matrisen.

Innledende fase. Finn det maksimale elementet i j- m kolonne og alle elementene i denne kolonnen trekkes sekvensielt fra maksimum. Denne operasjonen utføres på alle kolonnene i matrisen MED. Som et resultat dannes en matrise med ikke-negative elementer, i hver kolonne som det er i det minste, en null.

Deretter vurderer vi Jeg- rad i den resulterende matrisen, søk etter minimumselementet a i og trekk minimum fra hvert element i denne raden. Denne prosedyren gjentas med alle linjer. Som et resultat får vi matrisen MED 0 (MED 0 ~ C), som hver rad og kolonne har minst én null. Beskrevet konverteringsprosess MED V MED 0 kalles en matrisereduksjon.

Finn en vilkårlig null i den første kolonnen og merk den med en stjerne. Deretter ser vi på den andre kolonnen, og hvis det er en null i den plassert i en rad der det ikke er null med en stjerne, markerer vi den med en stjerne. På samme måte ser vi gjennom alle kolonnene i matrisen én etter én MED 0 og merk følgende nuller med en "*" hvis mulig. Åpenbart, nullene i matrisen MED 0 merket med en stjerne er uavhengige. Dette avslutter den foreløpige fasen.

(k+1) iterasjonen. La oss anta det k-Iterasjonen er allerede utført og som et resultat er matrisen oppnådd MEDk. Hvis den inneholder nøyaktig n nuller etterfulgt av en stjerne, avsluttes løsningsprosessen. Ellers går vi til ( k+1) - den iterasjonen.

Hver iterasjon starter med det første og slutter med det andre trinnet. Mellom dem kan et par stadier utføres flere ganger: den tredje - den første. Før iterasjonen starter, markerer "+"-tegnet kolonnene i matrisen MEDk, som inneholder nuller med stjerner.

Første etappe. Se umarkerte kolonner MEDk. Hvis det ikke er null elementer blant dem, fortsett til tredje trinn. Hvis den uvalgte null i matrisen MEDk oppdages, er ett av to tilfeller mulig: 1) en linje som inneholder en uvalgt null inneholder også en null med en stjerne; 2) denne linjen inneholder ikke en null med en stjerne.

I det andre tilfellet går vi rett til andre trinn, og markerer denne null med et slag.

I det første tilfellet er denne uvalgte nullen markert med et strek, og linjen den er inneholdt i er uthevet (med et "+"-tegn til høyre for linjen). De ser gjennom denne linjen, finner en null med en stjerne og ødelegger "+"-tegnet fra utvalget av kolonnen som inneholder denne nullen.

Deretter ser de gjennom denne kolonnen (som allerede er fjernet fra valget) og ser etter den uvalgte nullen (eller nullene) der den er plassert. Denne nullen er markert med et strek og linjen som inneholder en slik null (eller nuller) er uthevet. Så ser de gjennom denne linjen og ser etter en null med en stjerne i.

Denne prosessen, i et begrenset antall trinn, ender med ett av følgende utfall:

1) alle nuller i matrisen MEDk fremhevet, dvs. er i de uthevede radene eller kolonnene. I dette tilfellet går de videre til tredje trinn;

2) det er en uvalgt null på en linje der det ikke er en null med en stjerne. Deretter går de videre til andre etappe, og markerer denne nullen med et slag.

Andre fase. På dette stadiet konstrueres følgende kjede av matrisenuller MEDk: en innledende null med et primtall, en null med en stjerne plassert i samme kolonne som en innledende null med et primtall i samme rad som en innledende null med en stjerne, osv. Så kjeden dannes ved å flytte fra 0 " til 0 * langs kolonnen, fra 0 * til 0 " langs raden, etc.

Det kan bevises at den beskrevne algoritmen for å konstruere en kjede er entydig og endelig, og kjeden begynner og slutter alltid med en null med et primtall.

Deretter plasserer vi stjerner over elementene i kjeden som er på odde steder (0 "), og ødelegger dem over partallselementene (0 *). Deretter ødelegger vi alle strekene over elementene MEDk og "+"-symboler. Antall uavhengige nuller vil økes med én. På dette ( k+ 1) -te iterasjon er fullført.

Tredje trinn. De flytter til dette stadiet etter den første hvis alle matrisen er null MEDk fremhevet. I dette tilfellet blant de uvalgte elementene MEDk velg minimum og angi det h (h>0). Deretter trekker de fra h fra alle matriseelementer MEDk plassert i umarkerte rader og lagt til alle elementer som ligger i valgte kolonner. Som et resultat oppnås en ny matrise MED "k, tilsvarende MEDk. Merk at med dette

transformasjon, alle nuller med en stjernematrise MEDk forbli null i MED " k , i tillegg vises nye uvalgte nuller i den. Derfor går vi tilbake til den første fasen. Etter å ha fullført den første fasen, avhengig av resultatet, går de enten videre til den andre fasen eller går tilbake til den tredje fasen.

Etter endelig antall repetisjoner, vil neste første etappe definitivt ende med en overgang til andre etappe. Etter utførelse vil antallet uavhengige nuller øke med én og ( k+ 1) - den første iterasjonen vil bli fullført.

Eksempel 3.4. Løs oppgaveoppgave med matrise

Når vi løser problemet bruker vi følgende notasjon:

Valgtegnet "+" som skal destrueres er ringlet inn; Kjeden, som før, er indikert med piler.

Innledende fase. Vi finner det maksimale elementet i den første kolonnen - 4. Trekk fra det alle elementene i denne kolonnen. På samme måte for å få andre, tredje, fjerde og femte kolonne ny matrise trekk fra alle elementene i disse kolonnene fra henholdsvis n" fem, tre, to og tre. Vi får matrisen MED "(C"~C). Siden i hver linje MED " er null, da MED " = MED 0 og matrisereduksjonsprosessen avsluttes. Deretter ser vi etter og markerer med "*" uavhengige nuller inn MED 0 fra første linje.

Første iterasjon. Første etappe. Vi markerer den første, andre og fjerde kolonnen i matrisen med et "+"-tegn MED 0 som inneholder 0 * .

Vi ser gjennom den uvalgte tredje kolonnen, finner en uvalgt null i den MED 23 = 0, merk det med et slag og marker den andre linjen med et "+"-tegn. Vi ser gjennom denne linjen og finner elementet i den MED 22 = 0 * og ødelegg valgmerket for den andre kolonnen som inneholder 0 * . Så ser vi på den andre kolonnen - det er ingen uvalgte elementer i den. Vi går videre til den siste uvalgte kolonnen (den femte), og ser etter umarkerte nuller i den. Siden det ikke er noen uvalgte nuller, går vi videre til det tredje trinnet.

Tredje trinn. Finne minimumselementet i den uvalgte delen av matrisen MED 0 (dvs. elementer som ligger i kolonner og rader som ikke er merket med et "+"-tegn). Det er likt h = 1.

Trekke fra h= 1 fra alle elementene i umarkerte rader (dvs. alle unntatt den andre) og legg til alle elementene i de valgte kolonnene (første og fjerde). La oss få matrisen MED " 1 og gå videre til første trinn.

Første etappe. Før vi starter den, markerer vi igjen den første, andre og fjerde kolonnen med et "+"-tegn. Vi ser gjennom den uvalgte tredje kolonnen, finner en uvalgt null i den MED 23 = 0, merk det med et strektegn. Siden den andre linjen har 0 * (element MED 22), velg deretter den andre raden med et "+"-tegn, og ødelegg deretter seleksjonstegnet i den andre kolonnen, der 0 * ligger. Så ser vi på den andre kolonnen og finner en uvalgt null i den MED 12 = 0, merk det med et strektegn. Fordi den første linjen har en null med en stjerne MED 14 = 0 *, så markerer vi det med "+"-tegnet og ødelegger seleksjonstegnet i den fjerde kolonnen, der dette 0 *-tegnet var plassert. Deretter går vi gjennom den fjerde kolonnen og finner en uvalgt null i den MED 54 = 0. Siden det ikke er en null med en stjerne på linjen der den er plassert, og markerer denne 0 med et slag, går vi videre til andre trinn.

Tenk på følgende eksempel. La det være fem personer til å utføre fem forskjellige jobber. Fra rapporteringsdataene vet vi hvor mye tid det tar hver av dem å fullføre hver jobb. Disse dataene er vist i tabellen.

utøvere
behov

I i dette tilfellet verdiene representerer tiden hver arbeider har brukt på hver av jobbene, og verdiene er enten 1 eller 0, med 1 hvis arbeider i er tildelt jobb j og 0 i alle andre tilfeller. Dermed reduseres problemet til å minimere funksjonen. kostnadslinje lineær programmering

underlagt følgende restriksjoner.

Det er klart at hvis vi forkaster den siste tilstanden og erstatter den med betingelsen

Dette resulterer i et transportproblem der alle behov og alle ressurser er lik ett. I den optimale løsningen er alle enten et heltall eller null, hvor ett er det eneste mulige heltall. Å løse transportproblemet under disse forholdene fører altså alltid til likhet.

På grunn av degenerasjon viser imidlertid metoder for å løse transportproblemer ved oppdragsproblemet å være ineffektive. For enhver tildeling faller forsyninger etter rad alltid automatisk sammen med etterspørsel etter kolonne, og derfor får vi, i stedet for 2n-1, n verdier som ikke er null. I denne forbindelse er det nødvendig å fylle matrisen med n-1-verdier av e, og det kan vise seg at ikke-null-verdier bestemmer den optimale løsningen, men sjekken oppdager den ikke, siden verdiene ​av e er plassert feil.

Metoden for å løse oppgaveoppgaven er basert på to ganske åpenbare teoremer. Den første av dem sier at løsningen ikke vil endres hvis en konstant legges til eller trekkes fra en kolonne eller rad i matrisen. Denne teoremet er presist formulert som følger:

Teorem 1.

Hvis minimerer

for alle, som f.eks

minimerer da også funksjonaliteten

hvor foran alle

Teorem 2.

Hvis alt er mulig, er det mulig å finne et slikt sett

da er denne løsningen optimal.

Det andre teoremet er åpenbart. For å bevise det første teoremet, merker vi det

På grunn av det faktum at mengdene som trekkes fra Z for å oppnå ikke er avhengige av, når den et minimum når Z minimeres, og omvendt.

Løsningsmetoden som er utviklet er å legge til konstanter til radene og kolonnene og trekke dem fra radene og kolonnene til et tilstrekkelig antall verdier forsvinner til å gi en løsning lik null.

Å finne en løsning begynner med å trekke det minste elementet fra hver rad og deretter fra hver kolonne. Tabellen viser resultatene for eksempelet ovenfor.

Tabell A)

utøvere		trukket fra

Tabell B)

utøvere
trukket fra

Totalt 10 enheter ble trukket fra kolonnene og radene. Derfor, for å evaluere en løsning oppnådd ved hjelp av tabell (B), er det nødvendig å legge til 10 enheter til resultatet

Først og fremst streber de etter å finne en løsning som bare inkluderer de cellene i tabell (B) som inneholder null elementer, siden en slik løsning, hvis den kan finnes, vil være den beste av alle mulige. Det er imidlertid tilfeller hvor flere løsninger har samme kvalitet. En akseptabel løsning er markert i tabell (B) med parentes. For å avgjøre om løsningen kan forbedres, brukes imidlertid følgende algoritme.

La oss først merke oss at enhver ytterligere subtraksjon fra en rad eller kolonne, selv om det kan føre til utseendet av nye nuller, fører uunngåelig til utseendet av negative elementer, slik at nullløsningen nå ikke nødvendigvis er optimal. Negative elementer kan imidlertid elimineres ved å legge til tilsvarende tall i radene eller kolonnene. Hvis du for eksempel trekker 2 fra kolonne 1 i tabell (B), så vil element 2 dukke opp i rad 1. Legger du nå 2 til rad 1, får du igjen en matrise med ikke-negative elementer. Utfordringen er å få nye nuller på den angitte måten, men oppnår samtidig til slutt en matrise som inneholder en løsning som kun består av nuller. Det kan bevises at algoritmen beskrevet nedenfor gir en løsning på dette problemet.

1. Tegn minimum antall horisontale og vertikale linjer som skjærer alle nullene minst én gang. Å utføre dette trinnet på tabell (B) gir resultatet i tabell 1.

Tabell 1

Merk at i dette tilfellet brukes bare fire linjer, og derfor inneholder ikke nullcellene den optimale løsningen.

• 2. Velg det minste elementet som ingen linje er trukket gjennom. I eksemplet er det 1 i celle (5,2).
• 3. Trekk dette tallet fra alle elementene som ingen linjer er trukket gjennom, og legg det til alle elementene som to linjer er trukket gjennom. Dette eksemplet gir resultatet vist i tabell 2.

tabell 2

Dette trinnet skal resultere i at en null vises i en celle der det ikke var noen tidligere. I eksemplet under vurdering er dette celle (5,2).

4. Finn ut om det er en løsning blant det nye settet med nuller. Hvis en løsning ikke blir funnet (i dette eksemplet er det ingen), gå tilbake til trinn 1 og utfør alle påfølgende trinn til en løsning er funnet. Fortsetter vi å vurdere dette eksemplet, får vi resultatet vist i tabell 3.

Tabell 3

Denne tabellen inneholder allerede en løsning, merket med parentes og har en verdi på 13, som er 1 bedre enn originalen gjennomførbar løsning. , .

Eksempel 2.

Fire studenter og fire typer arbeid ble presentert. Følgende tabell tilsvarer kostnadsmatrisen for dette problemet.

La oss utføre det første trinnet i algoritmen.

La oss nå trekke fra minimumskostnader fra elementene i de tilsvarende radene.

På det andre trinnet i algoritmen finner vi minimumsverdier etter kolonner og trekk dem fra elementene i de tilsvarende kolonnene. Som et resultat får vi matrisen presentert i følgende tabell.

I den siste matrisen tillater ikke arrangementet med nullelementer å tildele en jobb til hvert barn. For eksempel, hvis vi tildeler Dasha å rengjøre garasjen, er den første kolonnen ekskludert fra videre vurdering, og da vil det ikke være nullelementer i Allas rad.

• 1) I den siste matrisen tegner vi minimum antall horisontale og vertikale linjer langs radene og kolonnene for å krysse ut alle nullelementer.
• 2) Finn det minste elementet som ikke er krysset ut, og trekk det fra de gjenværende elementene som ikke er krysset ut, og legg det til elementene som befinner seg i skjæringspunktet mellom de tegnede linjene.

I problemet dette eksemplet tre rette linjer kreves, dette fører til følgende tabell:

Det minste ukryssede elementet er lik 1. Vi trekker dette elementet fra de gjenværende ukryssede elementene og legger det til elementene som ligger i skjæringspunktet mellom linjer. Som et resultat får vi matrisen presentert i følgende tabell.

Den optimale løsningen vist i tabellen foreslår Dasha å rengjøre garasjen, Katya å klippe plenen, Alla å vaske bilene og Sasha å gå tur med hundene. Tilsvarende verdi objektiv funksjon tilsvarer 1+10+5+5=21. Den samme verdien kan oppnås ved å summere verdiene til og og verdien av elementet som er den minste blant alle de som ikke er krysset ut.