Ytterligere restriksjoner på transportproblemet. Metoden beskrevet ovenfor for å løse transportproblemet har et enklere logisk regneskjema enn potensiell metode

Transportoppgave

Når man skal finne en løsning transportproblem metode differensielle livrenter for det første fordeles en del av lasten på best mulig måte mellom destinasjoner (det såkalte betingede optimal fordeling) og i påfølgende iterasjoner gradvis redusere den totale mengden ikke-allokerte forsyninger. Alternativet for innledende lastfordeling bestemmes som følger. I hver kolonne i transportoppgavedatatabellen finnes den laveste tariffen. De funnet tallene er omgitt av sirkler, og cellene som inneholder de angitte tallene er fylt ut. De maksimalt mulige tallene er skrevet i dem. Som et resultat oppnås en viss fordeling av lastforsyninger til destinasjoner. Denne fordelingen tilfredsstiller generelt ikke begrensningene til det opprinnelige transportproblemet. Derfor bør de neste trinnene være å gradvis redusere ikke-allokerte lastforsyninger slik at de totale transportkostnadene forblir minimale. For å gjøre dette bestemmes overflødige og utilstrekkelige rader.

Linjer som tilsvarer leverandører hvis beholdning er fullt allokert og hvis destinasjoner knyttet til disse kundene ikke er tilfredsstilt av planlagte leverandører, anses som utilstrekkelige. Disse linjene kalles noen ganger også negative linjer. Linjer som ikke er helt oppbrukt regnes som overskudd. Noen ganger kalles de også positive.

Etter at overskytende og utilstrekkelige rader er bestemt, for hver av kolonnene finnes forskjellene mellom tallet i sirkelen og nærmeste tariff skrevet i overskytende rad. Hvis tallet i sirkelen er i den positive linjen, er forskjellen ikke bestemt. Blant de oppnådde tallene, finn de minste. Dette tallet kalles den mellomliggende annuiteten. Etter å ha bestemt den mellomliggende annuiteten, går de videre til et nytt bord. Denne tabellen er hentet fra forrige tabell ved å legge mellomleie til tilsvarende tariffer i negative rader. De resterende elementene forblir de samme. I dette tilfellet anses alle cellene i den nye tabellen som frie. Etter å ha konstruert en ny tabell, begynner cellene å fylles ut. Nå er antallet fylte celler én mer enn på forrige trinn. Denne tilleggscellen er i kolonnen der den mellomliggende annuiteten ble registrert. Alle andre celler er plassert en i hver av kolonnene og den minste for av denne kolonnen tall omsluttet av sirkler. Omgitt av sirkler er to identiske tall i kolonnen der den mellomliggende livrenten ble registrert i forrige tabell.

Siden antallet celler som skal fylles i den nye tabellen er større enn antall kolonner, bør du bruke en spesiell regel når du fyller ut cellene, som er som følger. Velg en bestemt kolonne (rad) der det er én celle med en sirkel merket i. Denne cellen er fylt ut og denne kolonnen (raden) er ekskludert fra vurdering. Etter dette, ta en bestemt rad (kolonne), der det er en celle med en sirkel plassert i den. Denne cellen er fylt ut og ekskludert fra vurdering. denne linjen(kolonne). Fortsetter slik, etter et begrenset antall trinn, fylles alle cellene der sirklene med tallene vedlagt er plassert. Dersom det i tillegg er mulig å fordele all last som er tilgjengelig på avgangspunktene mellom bestemmelsesstedene, så oppnås en optimal plan for transportoppgaven. Hvis den optimale planen ikke oppnås, går de videre til et nytt bord. For å gjøre dette, finn overflødige og utilstrekkelige linjer, mellomleie og bygg på dette grunnlaget nytt bord. I dette tilfellet kan det oppstå noen vanskeligheter med å bestemme tegnet på en streng når det er det ufordelt saldo lik null. I dette tilfellet anses raden som positiv forutsatt at den andre fylte cellen, plassert i kolonnen som er knyttet til denne raden av en annen fylt celle, er plassert i den positive raden.

Hvis, når man bestemmer den optimale planen for et transportproblem ved bruk av den potensielle metoden, noen av sine referanseplan, og så ble det konsekvent forbedret, så ved å finne en løsning på transportproblemet ved metoden med differanseleie, fordeles først en del av lasten mellom destinasjoner på best mulig måte (den s.k. betinget optimal fordeling) og i påfølgende iterasjoner gradvis redusere den totale mengden ikke-allokerte forsyninger. Alternativet for innledende lastfordeling bestemmes som følger. I hver av kolonnene i datatabellen for transportoppgaven finnes minimumstariffen. De funnet tallene er omgitt av sirkler, og cellene som inneholder de angitte tallene er fylt ut. De maksimalt mulige tallene er skrevet i dem. Som et resultat oppnås en viss fordeling av lastforsyninger til destinasjoner. Denne fordelingen tilfredsstiller generelt ikke begrensningene til det opprinnelige transportproblemet. Derfor bør de neste trinnene være å gradvis redusere ikke-allokerte lastforsyninger slik at de totale transportkostnadene forblir minimale. For å gjøre dette må du først bestemme overflødige og utilstrekkelige rader.

Linjer som tilsvarer leverandører hvis beholdning er fullt allokert og hvis etterspørsel fra destinasjonene knyttet til disse kundenes planlagte forsendelser ikke blir møtt, anses som utilstrekkelige. Disse linjene kalles noen ganger også negative linjer. Linjer som ikke er helt oppbrukt regnes som overskudd. Noen ganger kalles de også positive.

Etter at overskytende og utilstrekkelige rader er bestemt, for hver av kolonnene finnes forskjellene mellom tallet i sirkelen og nærmeste tariff skrevet i overskytende rad. Hvis tallet i sirkelen er i den positive linjen, er forskjellen ikke bestemt. Blant de oppnådde tallene, finn de minste. Dette nummeret kalles mellomleie. Etter å ha bestemt den mellomliggende annuiteten, går de videre til et nytt bord. Denne tabellen er hentet fra forrige tabell ved å legge mellomleie til tilsvarende tariffer i negative rader. De resterende elementene forblir de samme. I dette tilfellet anses alle cellene i den nye tabellen som frie. Etter å ha konstruert en ny tabell, begynner cellene å fylles ut. Nå er antallet fylte celler én mer enn på forrige trinn. Denne tilleggscellen er i kolonnen der den mellomliggende annuiteten ble registrert. Alle andre celler er plassert en i hver av kolonnene, og de inneholder de minste tallene for en gitt kolonne, omsluttet av sirkler. Omgitt av sirkler er to identiske tall i kolonnen der den mellomliggende livrenten ble registrert i forrige tabell.

Siden antallet celler som skal fylles i den nye tabellen er større enn antall kolonner, bør du bruke en spesiell regel når du fyller ut cellene, som er som følger. Velg en bestemt kolonne (rad) der det er én celle med en sirkel plassert i den. Denne cellen er fylt ut og denne kolonnen (raden) er ekskludert fra vurdering. Etter dette, ta en bestemt rad (kolonne), der det er en celle med en sirkel plassert i den. Denne cellen er fylt ut og denne raden (kolonnen) er ekskludert fra vurdering. Fortsetter slik, etter et begrenset antall trinn, fylles alle cellene der sirklene med tallene vedlagt er plassert. Dersom det i tillegg er mulig å fordele all last som er tilgjengelig på avgangspunktene mellom bestemmelsesstedene, så oppnås en optimal plan for transportoppgaven. Hvis den optimale planen ikke oppnås, går de videre til et nytt bord. For å gjøre dette, finn overflødige og utilstrekkelige rader, mellomleie, og bygg en ny tabell basert på dette. I dette tilfellet kan det oppstå noen vanskeligheter med å bestemme tegnet til en streng når dens ikke-allokerte resten er null. I dette tilfellet anses raden som positiv forutsatt at den andre fylte cellen, plassert i kolonnen som er knyttet til denne raden av en annen fylt celle, er plassert i den positive raden.

Etter et begrenset antall iterasjoner beskrevet ovenfor, blir den ikke-allokerte resten lik null. Som et resultat oppnås en optimal plan for en gitt transportoppgave.

Metoden beskrevet ovenfor for å løse transportproblemet har en enklere logisk krets beregninger enn den potensielle metoden omtalt ovenfor. Derfor, i de fleste tilfeller, for å finne løsninger på spesifikke transportproblemer ved hjelp av en datamaskin, brukes metoden for differensiell leie.

5.6 Fastsettelse av optimal plan for transportproblemer som har noen komplikasjoner i utformingen.

Når man skal finne en løsning på en rekke spesifikke transportproblemer, er det ofte nødvendig å ta hensyn til ytterligere restriksjoner som ikke ble møtt ovenfor når man vurderer enkle alternativer disse oppgavene. La oss dvele mer detaljert på noen mulige komplikasjoner i formuleringen av transportproblemer.

1. Under noen reelle forhold for godstransport fra et bestemt utgangspunkt , til reisemålet ditt , kan ikke implementeres. For å bestemme optimale planer for slike problemer, antas det at tariffen for transport av en lastenhet fra punkt til punkt , er vilkårlig stor M, og under denne betingelsen kjente metoder finne en løsning på et nytt transportproblem. Med denne forutsetningen er muligheten for transport av last fra punkt til punkt utelukket under den optimale planen for transportoppgaven. . Denne tilnærmingen til å finne en løsning på et transportproblem kalles forbud mot transport eller blokkering den tilsvarende cellen i oppgavedatatabellen.

2. I visse transportoppgaver er det et tilleggsvilkår å sikre transport langs de aktuelle rutene et visst beløp last La, for eksempel, fra avgangspunktet til bestemmelsesstedet er det nødvendig å overføre lastenheter. Deretter skrives det angitte tallet inn i cellen til datatabellen til transportoppgaven, som ligger i skjæringspunktet mellom rad og kolonne, og i fremtiden anses denne cellen som gratis med en vilkårlig stor transporttariff M. For det nye transportproblemet som oppnås på denne måten, finner man en optimal plan, som bestemmer den optimale planen originalt problem.

3. Noen ganger er det nødvendig å finne en løsning på et transportproblem der minst en gitt mengde last skal leveres fra avgangsstedet til destinasjonen. For å bestemme den optimale planen for en slik oppgave, anses det at varens reserver og varens behov er mindre enn de faktiske etter enheter. Etter dette finner man den optimale planen for det nye transportproblemet, ut fra hvilken løsningen på det opprinnelige problemet fastsettes.

4. Ved noen transportproblemer er det nødvendig å finne den optimale transportplanen, forutsatt at det ikke fraktes mer enn lastenheter fra avgangspunktet til destinasjonen, dvs.

Det formulerte problemet kan løses som følger. I tabellen med innledende oppgavedata, for hver begrensning (1), er det gitt en ekstra kolonne, dvs. en ekstra destinasjon er lagt inn. Denne kolonnen registrerer de samme takstene som i kolonnen, med unntak av tariffen i th rad. I tilleggskolonnen i denne linjen regnes tariffen som lik et eller annet vilkårlig stort antall. I dette tilfellet anses behovene til punktet som like, og behovene til den nylig introduserte destinasjonen anses som like. Løsningen på det resulterende transportproblemet kan bli funnet ved metoden for potensialer, og dermed vil den optimale planen bli bestemt eller uløseligheten til det opprinnelige problemet vil bli etablert. Merk at det opprinnelige transportproblemet kun kan løses hvis det finnes minst én referanseplan for det.

Problemet ovenfor kan løses på denne måten. Med hensyn til begrensning (1), konstrueres en referanseplan ved å bruke minimumselementregelen. Dessuten, hvis verdien registrert på dette trinnet inn i den korresponderende cellen av tallet bestemmes kun av begrensning (1), deretter er bare den fylte cellen utelukket fra vurdering. I andre tilfeller fra hensyn utelukker enten en rad eller en kolonne (enten den ene eller den andre).

Dersom det som følge av utarbeidelse av forsyningsplan fordeles alle tilgjengelige beholdninger av avgangspunkt og tilfredsstilles behovene ved destinasjonspunktene, får man en grunnplan for transportoppgaven.

Hvis det i en rad (og derfor i en kolonne) er en ikke-allokert saldo lik , da introduseres en ekstra destinasjon og et ekstra avgangspunkt med krav og forsyninger lik . I en celle i skjæringspunktet mellom en kolonne tilleggspoeng destinasjon og linjen til det ekstra avgangspunktet, anses tariffen lik null. I alle andre celler i en gitt rad og kolonne antas tariffer å være lik et eller annet vilkårlig stort antall M. Det resulterende transportproblemet løses med den potensielle metoden. Etter et begrenset antall trinn fastslås det enten at den opprinnelige oppgaven ikke har en referanseplan, eller dens optimale plan blir funnet. Hvori – optimal plan for det opprinnelige problemet hvis

Teoretisk del

Økonomiske oppgaver redusert til en transportmodell

En transportmodell brukes til å lage den mest økonomiske planen for transport av én type produkt fra flere punkter (for eksempel fabrikker) til leveringssteder (for eksempel lager). Transportmodellen kan brukes når man vurderer en rekke praktiske situasjoner knyttet til lagerstyring, planlegging av skift, tildeling av ansatte til jobber, omsetning av tilgjengelig kapital, regulering av vannføring i magasiner og mange andre. I tillegg kan modellen modifiseres for å imøtekomme transport av flere typer produkter.

Transportproblemet er en oppgave lineær programmering Dens spesifikke struktur tillater imidlertid at simpleksmetoden kan modifiseres på en slik måte at beregningsprosedyrene blir mer effektive. Når man utvikler en metode for å løse et transportproblem, spiller dualitetsteorien en vesentlig rolle.

Det klassiske transportproblemet tar for seg transport (direkte eller med mellompunkter) av en eller flere typer produkter fra opprinnelse til destinasjon. Dette problemet kan endres til å inkludere øvre restriksjoner på gjennomstrømning transportkommunikasjon. Oppdragsproblemet og lagerstyringsproblemet kan betraktes som problemer transporttype. Det er flere typer økonomiske problemer som kan reduseres til en transportmodell:

– optimal fordeling av utstyr;

- dannelse av det optimale personalet i selskapet;

- oppgave planlegging produksjon;

– optimal forskning marked;

– optimal bruk arbeider agenter;

– problemet med produksjonssted;

– oppgaveproblem.

Problemet med å danne den optimale staben til et selskap i generelt syn er formulert som følger.

Selskapet rekrutterer ansatte. Den har n grupper av forskjellige stillinger med bj ledige enheter i hver gruppe, j = 1,...,n. Kandidater til stillinger testes, i henhold til resultatene som de er delt inn i m grupper av ai-kandidater i hver gruppe, i = 1,...,m. For hver kandidat fra den i-te gruppen kreves det visse opplæringskostnader Cij for å besette den j-te stillingen, i=1,...,m; j=1,…,n. (Spesielt noen Cij = 0, dvs. kandidaten tilsvarer fullt ut stillingen, eller Cij = ∞ (Cij = M), dvs. kandidaten kan ikke besette denne stillingen i det hele tatt.) Det kreves å fordele kandidater til stillinger, med minimale utgifter midler til opplæringen deres. La oss late som det totalt antall kandidater tilsvarer antall ledige stillinger. Deretter denne oppgaven tilsvarer transportmodellen. Grupper av kandidater fungerer som leverandører, og grupper av stillinger fungerer som forbrukere. Omskoleringskostnader regnes som transporttariffer. Den matematiske modellen er skrevet som:

Metode for differensiell leie for å løse transportproblemet

Flere metoder brukes for å løse transportproblemer. La oss vurdere løsningen ved å bruke metoden for differensiell leie.

Når man finner en løsning på et transportproblem ved hjelp av metoden med differensiell leie, fordeles først deler av lasten best mellom destinasjoner (den såkalte betinget optimale fordelingen) og i påfølgende iterasjoner reduseres den totale mengden ufordelte leveranser gradvis. Alternativet for innledende lastfordeling bestemmes som følger. I hver av kolonnene i transportoppgavedatatabellen finnes minimumstariffen. De funnet tallene er omgitt av sirkler, og cellene som inneholder de angitte tallene er fylt ut. De maksimalt mulige tallene er skrevet i dem. Som et resultat oppnås en viss fordeling av lastforsyninger til destinasjoner. Denne fordelingen tilfredsstiller generelt ikke begrensningene til det opprinnelige transportproblemet. Derfor, som et resultat av påfølgende trinn, bør ikke-allokerte lastforsyninger gradvis reduseres slik at de totale transportkostnadene forblir minimale. For å gjøre dette må du først bestemme overflødige og utilstrekkelige rader.

Etter at overskytende og utilstrekkelige rader er bestemt, for hver av kolonnene finnes forskjellene mellom tallet i sirkelen og nærmeste tariff skrevet i overskytende rad. Hvis tallet i sirkelen er i den positive linjen, er forskjellen ikke bestemt. Blant de oppnådde tallene, finn de minste. Dette tallet kalles den mellomliggende annuiteten. Etter å ha bestemt den mellomliggende annuiteten, går de videre til et nytt bord. Denne tabellen er hentet fra forrige tabell ved å legge mellomleie til tilsvarende tariffer i negative rader. De resterende elementene forblir de samme. I dette tilfellet anses alle cellene i den nye tabellen som frie. Etter å ha konstruert en ny tabell, begynner cellene å fylles ut. Nå er antallet fylte celler én mer enn på forrige trinn. Denne tilleggscellen er i kolonnen der den mellomliggende annuiteten ble registrert. Alle andre celler er plassert en i hver av kolonnene, og de inneholder de minste tallene for en gitt kolonne, omsluttet av sirkler. Omgitt av sirkler er to identiske tall i kolonnen der den mellomliggende livrenten ble registrert i forrige tabell.

Siden antallet celler som skal fylles i den nye tabellen er større enn antall kolonner, bør du bruke en spesiell regel når du fyller ut cellene, som er som følger. Velg en bestemt kolonne (rad) der det er én celle med en sirkel merket i. Denne cellen er fylt ut og denne kolonnen (raden) er ekskludert fra vurdering. Etter dette, ta en bestemt rad (kolonne), der det er en celle med en sirkel plassert i den. Denne cellen er fylt ut og denne raden (kolonnen) er ekskludert fra vurdering. Fortsetter slik, etter et begrenset antall trinn, fylles alle cellene der sirklene med tallene vedlagt er plassert. Dersom det i tillegg er mulig å fordele all last som er tilgjengelig på avgangspunktene mellom bestemmelsesstedene, så oppnås en optimal plan for transportoppgaven. Hvis den optimale planen ikke oppnås, går de videre til et nytt bord. For å gjøre dette, finn overflødige og utilstrekkelige rader, mellomleie, og bygg en ny tabell basert på dette. I dette tilfellet kan det oppstå noen vanskeligheter med å bestemme tegnet til en streng når dens ikke-allokerte resten er null. I dette tilfellet anses raden som positiv forutsatt at den andre fylte cellen, plassert i kolonnen som er knyttet til denne raden av en annen fylt celle, er plassert i den positive raden.

Etter et begrenset antall iterasjoner beskrevet ovenfor, blir den ikke-allokerte resten null. Som et resultat oppnås en optimal plan for en gitt transportoppgave.

Metoden for å løse transportproblemet beskrevet ovenfor har et enklere logisk regneskjema enn den potensielle metoden. Derfor, i de fleste tilfeller, for å finne løsninger på spesifikke transportproblemer ved hjelp av en datamaskin, brukes metoden for differensiell leie.

Et eksempel på å løse et problem.

For transportproblemet, hvis første data er gitt i tabell. 1.2.1, finne den optimale planen ved å bruke differensial annuitetsmetoden.

Tabell 1.2.1 Startdata for transportoppgaven

Løsning. La oss gå videre fra bordet. 1.2.1 til tabell. 1.2.2, legge til en ekstra kolonne for å indikere overskudd og mangel etter rad og en rad for å registrere de tilsvarende forskjellene.

Tabell 1.2.2 Overskridelser og mangler

Utgangspunkter	Destinasjoner	Reserver	Mangel(-), Overskudd(+)
I 1	AT 2	AT 3	AT 4	AT 5
A1			4			+60
A2	1	8		5	3	-80
A3						+20
Behov
Forskjeller			–

I hver kolonne i tabellen. 1.2.2 finner vi minimumstariffene og ringer rundt dem. Fyll ut cellene som inneholder de angitte tallene. For å gjøre dette, skriv det maksimalt tillatte antallet i hver celle. For eksempel, i cellen som ligger i skjæringspunktet mellom rad A 1 og kolonne B 3, skriver vi tallet 120. Et større tall kan ikke plasseres i denne cellen, siden i dette tilfellet vil behovene til destinasjon B 3 bli overskredet.

Som et resultat av å fylle ut cellene nevnt ovenfor, ble det oppnådd en såkalt betinget optimal plan, ifølge hvilken behovene til destinasjoner B 1, B 2, B 3 og B 4 er fullt tilfredsstilt og delvis behovene til destinasjon B 5 . Samtidig er reservene til utgangspunktet A 2 fullt ut fordelt, reservene til utgangspunktet A 1 er delvis fordelt, og reservene til utgangspunktet A 3 forblir helt ufordelt.

Etter å ha oppnådd en betinget optimal plan, bestemmer vi de overflødige og utilstrekkelige linjene. Her er linje A 2 utilstrekkelig, siden reservene til avgangspunkt A 2 er fullt utnyttet, og behovene til destinasjon B5 er delvis tilfredsstilt. Mengden av mangel er 80 enheter.

Linjene A 1 og A 3 er overflødige fordi beholdningen av origo A 1 og A 3 ikke er fullstendig allokert. I dette tilfellet er oververdien av linje A 1 60 enheter, og linje A 3 er 20 enheter. den totale mengden av overskytende 60+20=80 faller sammen med den totale mangelen lik 80.

Etter å ha bestemt overskytende og utilstrekkelige rader for hver av kolonnene, finner vi forskjellene mellom minimumstariffene skrevet i overskytende rader og tariffene i de fylte cellene. I i dette tilfellet disse forskjellene er henholdsvis lik 5,4,2,1 (tabell 1.2.2). For kolonne B 3 er forskjellen ikke definert, siden tallet skrevet i sirkelen i denne kolonnen er i den positive raden. I kolonne B 1 er tallet i sirkelen 1, og i de overflødige radene i cellene i denne kolonnen er det minste tallet 6. Derfor er forskjellen for denne kolonnen 6-1=5. Tilsvarende finner vi forskjellene for andre kolonner: for B 2 12-8 = 4; for B47-5=2; for B 5 4-3=1.

Vi velger den minste av forskjellene som er funnet, som er mellomleien. I dette tilfellet er mellomleien lik 1 og står i kolonne B 5. Etter å ha funnet mellomleien, går vi videre til bordet. 1.2.3

Tabell 1.2.3 Mellomleie

Utgangspunkter	Destinasjoner	Reserver	Mangel(-), Overskudd(+)
I 1	AT 2	AT 3	AT 4	AT 5
A1			4			+60
A2	2	9		6	4	-60
A3					4	-0
Behov
Forskjeller			–

I denne tabellen, i linjene A 1 og A 3 (som er overflødige), skriver vi om de tilsvarende tariffer fra linjene A 1 og A 3 i tabellen. 1.2.2. elementer av linje A 2 (som var utilstrekkelig) oppnås ved å legge til de tilsvarende tariffer plassert i linje A 2 i tabellen. 1.2.2, mellomliggende livrente, dvs. 1.

I tabell 1.2.3 har antall fylte celler økt med én. Dette skyldes det faktum at antall minstetariffer i hver av kolonnene i denne tabellen har økt med én, nemlig i kolonne B 5 er det nå to minimumselementer 4. Vi omslutter disse tallene i sirkler; cellene de står i bør huskes. Det er også nødvendig å fylle ut cellene som inneholder de laveste tariffene for andre kolonner. Dette er cellene i tabellen. 1.2.3, hvor de tilsvarende tariffer er omgitt av sirkler. Etter at de spesifiserte cellene er bestemt, etablerer vi sekvensen for å fylle dem. For å gjøre dette finner vi kolonner (rader) der det bare er én celle å fylle. Etter å ha identifisert og fylt ut en bestemt celle, ekskluderer vi den tilsvarende kolonnen (raden) fra vurdering og går videre til å fylle ut neste celle. I dette tilfellet fyller vi cellene i følgende rekkefølge. Fyll først ut cellene A 1 B 3, A 2 B 1, A 2 B 2, A 2 B 4, siden de er de eneste cellene som fyller ut kolonnene B 1, B 2, B 3 og B 4. Etter å ha fylt ut de angitte cellene, fyll ut celle A 3 B 5, siden det er den eneste som skal fylles ut i linje A3. Etter å ha fylt ut denne cellen, ekskluderer vi linje A 3 fra vurdering. Da vil det i kolonne B 5 bare være én celle igjen å fylle. Dette er celle A 2 B 5, som vi fyller ut. Etter å ha fylt cellene, setter vi de overflødige og utilstrekkelige linjene. Som det fremgår av tabellen. 1.2.3, er det fortsatt en ufordelt saldo. Derfor er det innhentet en betinget optimal plan for problemet og vi må gå videre til et nytt bord. For å gjøre dette, for hver av kolonnene deres finner vi forskjellene mellom tallet skrevet i sirkelen til denne kolonnen og det minste tallet i forhold til det, plassert i de overflødige radene. Blant disse forskjellene er den minste 1. Dette er mellomleien. La oss gå videre til neste tabell (tabell 1.2.4).

Tabell 1.2.4 Optimal plan for en transportoppgave

Utgangspunkter	Destinasjoner	Reserver	Mangel(-), Overskudd(+)
I 1	AT 2	AT 3	AT 4	AT 5
A1			4
A2	3	10		7	5
A3
Behov

I den nye tabellen oppnås elementene i rad A 2 og A 3 ved å legge til de tilsvarende antall rader A 2 og A 3 (som er utilstrekkelige) i tabellen. 1.2.3 mellomliggende livrente, dvs. 1. Som et resultat, i tabell. 1.2.4 antall celler for fylling økte med én til og ble lik 6. Vi bestemmer de angitte cellene og fyller dem. Først fyller vi cellene A 1 B 3, A 2 B 1, A 2 B 2, A 2 B 4, og deretter A 3 B 5, A 2 B 5, A 1 B 5. Som et resultat blir alle tilgjengelige forsyninger fra leverandører distribuert i henhold til de faktiske behovene til destinasjonene. Antall fylte celler er 7, og de har den minste vekten C ij . Derfor oppnås den optimale planen for det opprinnelige transportproblemet:

Med denne transportplanen er de totale kostnadene:

S=4*120+5*60+1*110+8*90+5*80+3*70+4*20=2300.

Praktisk del

Oppgaven. La det være n kandidater til å utføre disse jobbene. Utnevnelsen av kandidat i til jobb j er forbundet med kostnader C ij (i, j = 1,2,..., n). Det kreves å finne tildelingen av kandidater til alle jobber som gir minimum totalkostnad, mens hver kandidat kan tildeles kun én jobb og hver jobb kan besettes av kun én kandidat. De første dataene er vist i tabellen:

Tabell.2.4 Startdata

A i B j	B1	B2	B3	B4
A1
A2
A3
A4

inndata:

n – antall kandidater og jobber, hele typen data

C (n, n) - kostnader (gni.), ekte type data.

Produksjon:

Smin - totale kostnader (rub.), ekte datatype;

X (n, n) - jobbkandidatoppdrag, heltallsdatatype.

Hvis man først fant en grunnleggende plan for et transportproblem ved å bruke den potensielle metoden, og deretter ble den konsekvent forbedret, så når man fant en løsning på et transportproblem ved hjelp av metoden med differanseleie, ble første del av lasten fordeles mellom destinasjoner på best mulig måte (den såkalte betinget optimale fordelingen) og i påfølgende iterasjoner reduseres den totale mengden ufordelte forsyninger gradvis. Alternativet for innledende lastfordeling bestemmes som følger. I hver av kolonnene i datatabellen for transportoppgaven finnes minimumstariffen. De funnet tallene er omgitt av sirkler, og cellene som inneholder de angitte tallene er fylt ut. De maksimalt mulige tallene er skrevet i dem. Som et resultat oppnås en viss fordeling av lastforsyninger til destinasjoner. Denne fordelingen tilfredsstiller generelt ikke begrensningene til det opprinnelige transportproblemet. Derfor bør de neste trinnene være å gradvis redusere ikke-allokerte lastforsyninger slik at de totale transportkostnadene forblir minimale. For å gjøre dette må du først bestemme overflødige og utilstrekkelige rader.

Etter at overskytende og utilstrekkelige rader er bestemt, for hver av kolonnene finnes forskjellene mellom tallet i sirkelen og nærmeste tariff skrevet i overskytende rad. Hvis tallet i sirkelen er i den positive linjen, er forskjellen ikke bestemt. Blant de oppnådde tallene, finn de minste. Dette tallet kalles den mellomliggende annuiteten . Etter å ha bestemt den mellomliggende annuiteten, går de videre til et nytt bord. Denne tabellen er hentet fra forrige tabell ved å legge mellomleie til tilsvarende tariffer i negative rader. De resterende elementene forblir de samme. I dette tilfellet anses alle cellene i den nye tabellen som frie. Etter å ha konstruert en ny tabell, begynner cellene å fylles ut. Nå er antallet fylte celler én mer enn på forrige trinn. Denne tilleggscellen er i kolonnen der den mellomliggende annuiteten ble registrert. Alle andre celler er plassert en i hver av kolonnene, og de inneholder de minste tallene for en gitt kolonne, omsluttet av sirkler. Omgitt av sirkler er to identiske tall i kolonnen der den mellomliggende livrenten ble registrert i forrige tabell.

Siden antallet celler som skal fylles i den nye tabellen er større enn antall kolonner, bør du bruke en spesiell regel når du fyller ut cellene, som er som følger. Velg en bestemt kolonne (rad) der det er én celle med en sirkel plassert i den. Denne cellen er fylt ut og denne kolonnen (raden) er ekskludert fra vurdering. Etter dette, ta en bestemt rad (kolonne), der det er en celle med en sirkel plassert i den. Denne cellen er fylt ut og denne raden (kolonnen) er ekskludert fra vurdering. Fortsetter slik, etter et begrenset antall trinn, fylles alle cellene der sirklene med tallene vedlagt er plassert. Dersom det i tillegg er mulig å fordele all last som er tilgjengelig på avgangspunktene mellom bestemmelsesstedene, så oppnås en optimal plan for transportoppgaven. Hvis den optimale planen ikke oppnås, går de videre til et nytt bord. For å gjøre dette, finn overflødige og utilstrekkelige rader, mellomleie, og bygg en ny tabell basert på dette. I dette tilfellet kan det oppstå noen vanskeligheter med å bestemme tegnet til en streng når dens ikke-allokerte resten er null. I dette tilfellet anses raden som positiv forutsatt at den andre fylte cellen, plassert i kolonnen som er knyttet til denne raden av en annen fylt celle, er plassert i den positive raden.

Etter et begrenset antall iterasjoner beskrevet ovenfor, blir den ikke-allokerte resten null. Som et resultat oppnås en optimal plan for en gitt transportoppgave.

Metoden for å løse transportproblemet beskrevet ovenfor har et enklere logisk beregningsskjema enn den potensielle metoden diskutert ovenfor. Derfor, i de fleste tilfeller, for å finne løsninger på spesifikke transportproblemer ved hjelp av en datamaskin, brukes metoden for differensiell leie.

Eksempel (4):

For transportproblemet, hvis første data er gitt i tabell 11, finn den optimale planen ved å bruke metoden for differensiell leie.

Løsning. La oss gå fra tabell 11 til tabell 12, og legge til en ekstra kolonne for å indikere overskudd og mangel etter rad og en rad for å registrere de tilsvarende forskjellene.

Tabell 10.

Utgangspunkter	Destinasjoner
Utgangspunkter



Behov

Tabell 11.

Utgangspunkter

Destinasjoner

Feil

overskytende (

Behov

Forskjell

I hver av kolonnene i Tabell 12 finner vi minimumstariffene og ringer rundt dem. Fyll ut cellene som inneholder de angitte tallene. For å gjøre dette, skriv det maksimalt tillatte antallet i hver celle. For eksempel, i cellen som ligger i skjæringspunktet mellom raden og kolonnen, skriver vi tallet 120. Et større tall kan ikke plasseres i denne cellen, siden i dette tilfellet vil behovene til destinasjonen overskrides.

Som et resultat av å fylle ut cellene nevnt ovenfor, oppnås en såkalt betinget optimal plan, i henhold til hvilken behovene til destinasjonene er fullt tilfredsstilt og delvis behovene til destinasjonen . Samtidig ble reservene til utgangspunktet fullstendig distribuert, delvis - forsyningene til utgangspunktet, og beholdningene til utgangspunktet forble helt udedelt.

Etter å ha oppnådd en betinget optimal plan, bestemmer vi de overflødige og utilstrekkelige linjene. Her er linjen utilstrekkelig , siden reservene til utgangspunktet er fullt utnyttet, og destinasjonens behov er delvis tilfredsstilt. Mengden av mangel er 80 enheter.

Strenger Og er overflødige fordi aksjene ved opprinnelsen Og ikke fullstendig distribuert. I dette tilfellet, mengden av linjeoverskudd er lik 60 enheter, og linjen er lik enheter Den totale mengden overskytende faller sammen med den totale mengden mangel, lik.

Etter å ha bestemt overskytende og utilstrekkelige rader for hver av kolonnene, finner vi forskjellene mellom minimumstariffene skrevet i overskytende rader og tariffene i de fylte cellene. I dette tilfellet er disse forskjellene henholdsvis 5, 4, 2, 1 (tabell 11). Forskjellen er udefinert for kolonnen fordi det sirklede tallet i den kolonnen er i den positive raden. I en kolonne er tallet i sirkelen likt, og i de overflødige radene i cellene i en gitt kolonne er det minste tallet tallet. Derfor er forskjellen for denne kolonnen lik. Vi finner på samme måte forskjellene for andre kolonner: for; Til; Til. .

Vi velger den minste av forskjellene som er funnet, som er mellomleien. I dette tilfellet er mellomleien lik og står i kolonnen . Etter å ha funnet mellomleien, går vi videre til tabell 11.

I denne tabellen, i rader og (som er overflødige) skriver vi om de tilsvarende tariffer fra rad Tabell 10. Elementene i linjen (som var utilstrekkelig) oppnås ved å legge til de tilsvarende tariffer i linjetabellen. 10, mellomliggende livrente, dvs.

I tabellen 11 økte antallet fylte celler med én. Dette skyldes det faktum at antallet minimumstariffer i hver av kolonnene i denne tabellen har økt med én, nemlig at kolonnen nå har to minimumselementer. Vi omslutter disse tallene i sirkler; cellene de står i må fylles. Det er også nødvendig å fylle ut cellene som inneholder de laveste tariffene for andre kolonner. Dette er cellene i tabellen. 11 hvor de tilsvarende tariffer er omgitt av sirkler.

Tabell 11.

Utgangspunkter

Destinasjoner

Feil

overskytende (

Behov

Forskjell

Etter at de spesifiserte cellene er bestemt, etablerer vi sekvensen for å fylle dem. For å gjøre dette finner vi kolonner (rader) der det bare er én celle å fylle. Etter å ha identifisert og fylt ut en bestemt celle, ekskluderer vi den tilsvarende kolonnen (raden) fra vurdering og går videre til å fylle ut neste celle. I dette tilfellet fyller vi cellene i følgende rekkefølge. Først fyller vi cellene ,,,, siden de er de eneste cellene som fyller ut kolonnene. Etter å ha fylt de angitte cellene, fyll cellen, siden det er den eneste som fyller ut raden . Etter å ha fylt ut denne cellen (tabell 2.16), ekskluderer vi linjen fra vurdering . Da er det bare én celle igjen i kolonnen som skal fylles. Dette er et bur , som vi fyller ut. Etter å ha fylt cellene, satte vi redundante og utilstrekkelige linjer (tabell 11). Som det fremgår av tabell 11 er det fortsatt en ufordelt saldo. Følgelig er det oppnådd en betinget optimal plan for problemet og vi må flytte til et nytt bord. For å gjøre dette finner vi for hver av kolonnene forskjellene mellom tallet skrevet i sirkelen til denne kolonnen og det minste tallet i forhold til det, plassert i de overflødige radene (tabell 11). Blant disse forskjellene er den minste . Dette er mellomleie. La oss gå videre til et nytt bord (tabell 12).