Et eksempel på løsning av et lineært programmeringsproblem ved bruk av MS utmerke

Gården har spesialisert seg på åkerdrift for produksjon av korn, sukkerroer og solsikker. I landbruket Bedriften har 3 200 hektar dyrkbar jord, arbeidsressurser i mengden 7 000 dagsverk og mineralgjødsel i mengden 15 000 c.d.w. Det er nødvendig å finne en kombinasjon av areal som vil sikre maksimal fortjeneste.

Det bør det også tas hensyn til

- området sådd med industrielle avlinger (sukkerroer og solsikker) bør ikke overstige 25% av det totale arealet av dyrkbar jord;

- Gården inngikk en kontrakt om salg av korn til et beløp på 65.000 c.

For å utvikle en økonomisk og matematisk modell er det nødvendig å utarbeide inputinformasjon (tabell 1).

Tabell 1

Indikatorer	Landbruksvekster
	frokostblandinger	sukkerroer	solsikke
Produktivitet, c/ha
Salgspris på 1 centner produkter, rub./c.
Kostnader for salgbare produkter per 1 hektar, tusen rubler.	5,59	20,62	6,73
Kostnader per 1 ha: MDS, tusen rubler.		12,7
arbeidskraft, dagsverk
mineralgjødsel, c.d.v.
Fortjeneste fra 1 ha, gni.	2,89	7,93	3,63

Som ukjente tar vi området under avlinger etter type:

X 1 - kornavlinger

X 2 - sukkerroer

X 3 - solsikke

For å bygge en økonomisk og matematisk modell av problemet, er det nødvendig å ta hensyn til alle forholdene. I i dette tilfellet, i henhold til disse vilkårene, kan fem begrensninger utarbeides:

- summen av arealene tilsådd med jordbruksvekster bør ikke overstige arealet som er tilgjengelig på gården (3200 hektar). Koeffisientene for de ukjente i denne begrensningen karakteriserer forbruket av dyrkbar jord per 1 hektar av hver avling. I dette tilfellet vil de tekniske og økonomiske koeffisientene for de ukjente være lik én. Det totale arealet av dyrkbar mark er registrert på høyre side.

1) X1+X2+X3<=3200

- summen av arealene tilsådd med industrivekster bør ikke overstige arealet som kan avsettes til dette formålet (3200*0,25=800 ha). Koeffisientene for de ukjente i denne begrensningen karakteriserer forbruket av dyrkbar jord tildelt for såing av industriavlinger per 1 hektar av hver industriell landbruksavling. I dette tilfellet vil de tekniske og økonomiske koeffisientene for de ukjente X2 og X3 være lik én, og for ikke-tekniske landbruksavlinger (X3) - null. På høyre side er skrevet det maksimale arealet av dyrkbar jord som kan tildeles for planting av industrielle avlinger.

2) X2+X3<=800

- den tredje og fjerde restriksjonen sikrer at bruken av arbeidsressurser og mineralgjødsel ikke overstiger tilgjengeligheten på gården. Med andre ord, summen av produktene av ressursforbruksrater per 1 hektar på arealet tilsådd med tilsvarende landbruksvekster bør ikke overstige volumet av tilgjengelige ressurser i landbruket. bedriften. Koeffisientene for de ukjente i disse begrensningene vil være ressursforbruket (i den tredje begrensningen - arbeidsressurser, i den fjerde - mineralgjødsel) per 1 hektar avlingsareal. I dette tilfellet er de tekniske og økonomiske koeffisientene hentet fra tabell 1. Tilgjengeligheten av disse ressursene på gården er registrert på høyre side.

3) 1,5Х1+4,5Х2+1,5Х3<=7000

4) 2Х1+15Х2+2,3Х3<=15000

- den femte begrensningen garanterer produksjonen av det planlagte volumet av korn. Koeffisientene for variablene er kornavlingen per 1 hektar jordbruksareal. avlinger Når X1 er ukjent, er dette kornutbyttet (tabell 1). For variablene X2 og X3 er denne koeffisienten null. Kornproduksjonsplanen er skrevet på høyre side.

5) 26Х1>=65000

Som et resultat oppnås et system med fem lineære ulikheter med tre ukjente. Det er nødvendig å finne slike ikke-negative verdier av disse ukjente X1>=0; X2>=0; X3>=0, som ville tilfredsstille dette ulikhetssystemet og sikre maksimal profitt fra planteproduksjonsindustrien som helhet:

Z maks = 2,89Х1+7,93Х2+3,53Х3

Koeffisientene for de ukjente i målfunksjonen er overskuddet mottatt fra 1 hektar areal under avlinger. Disse koeffisientene er beregnet basert på dataene i tabell 1.

Fordi det denne oppgaven løst ved hjelp av MS utmerke , så er det tilrådelig å forberede all inngangsinformasjon for å konstruere en økonomisk og matematisk modell ved å bruke denne bordprosessor(Figur 1). Dette letter ikke bare beregningen av tekniske og økonomiske koeffisienter og andre data, men gjør det også mulig i fremtiden automatisk oppdatering informasjon i den økonomiske og matematiske modellen.

Bilde 1

All utviklet informasjon er oppsummert til en detaljert økonomisk og matematisk modell og lagt inn i MS-arbeidsarket Utmerke. (Fig. 2.)

Figur 2

Det anbefales å legge inn data i modellen i form av lenker til celler med relevant informasjon i regneark eller regneark med innledende informasjon. Figur 3 viser hvordan i en celle F9 Det gis informasjon om forbruket av gjødsel per 1 hektar solsikkesåing.

Figur 3

Til kolonner EN («№»), I("Begrensninger"), MED("Enheter") ogH("Begrensningstype"), de tilsvarende dataene legges direkte inn i modellen (fig. 1). De brukes ikke i beregninger og tjener til informasjonsformål og for å lette forståelsen av innholdet i modellen. Til kolonne Jeg("Omfang av restriksjoner"), lenker legges inn til celler som inneholder informasjon som tilsvarer kolonnenavnet (verdiene til høyresiden av ulikhetene konstruert tidligere).

For de ønskede verdiene til variablene X1, X2, X3 ble forlatt av oss tomme celler- henholdsvis D5, E 5, F 5. Opprinnelig tomme celler program MS Excel oppfatter som celler hvis verdi er null. Kolonne G, kalt av oss " Summen av produkter", er ment å bestemme summen av produkter av verdiene til de ukjente ukjente (celler D5, E 5, F 5) og tekniske og økonomiske koeffisienter i henhold til tilsvarende restriksjoner (linje 6-10) og objektiv funksjon(linje 11). Altså i kolonnen G definert:

- - mengde ressurser brukt (celle G6– totalt areal med dyrkbar jord; G7– dyrkbar jord som kan brukes til å plante industrielle avlinger; G8– arbeidsressurser; G9- mineralgjødsel);

- - mengde produsert korn (celle G10);

- - fortjenestebeløp (celle G11).

Figur 2 viser hvordan i en celle G11 registreringen av summen av produktene av verdiene til variabler er implementert (områder sådd med landbruksavlinger - celler D5, E 5, F 5) for tilsvarende fortjeneste fra 1 hektar av avlingene deres (celler D11, E 11, F 11) ved å bruke MS-funksjonen utmerke « SUMPRODUKT" Siden når du skriver denne formelen, absolutt adressering til celler fra D5 førF 5, kan denne formelen kopieres til andre celler fraG 6 før G10.

Slik bygget referanseplan(Fig. 2) og den første ble oppnådd gyldig løsning. Verdiene av de ukjente X1, X2, X3 er lik null (celler D5, E 5, F 5 -tomme celler), kolonneceller G"Summen av produkter" på tvers av alle begrensninger (linje 6-10) og mållinjen (linje 11) har også nullverdier.

Den økonomiske tolkningen av den første grunnplanen er som følger: gården har ressurser, alle tekniske og økonomiske koeffisienter er beregnet, men produksjonsprosessen har ennå ikke begynt; ressurser ble ikke brukt, og følgelig var det ingen fortjeneste.

For å optimalisere den eksisterende planen, vil vi bruke verktøyet Å finne en løsning, som er i menyen Service. Hvis det ikke er en slik kommando i menyen Service, nødvendig på punktet Overbygg merk av i boksen Å finne en løsning. Etter dette vil denne prosedyren bli tilgjengelig i menyen Service.

Etter å ha valgt denne kommandoen, vil en dialogboks vises (fig. 4).

Figur 4

Siden vi valgte profittmaksimering som et optimaliseringskriterium, i felten Angi målcelle Skriv inn en lenke til cellen som inneholder fortjenesteberegningsformelen. I vårt tilfelle er dette cellen $G$11. For å maksimere verdien av den endelige cellen ved å endre verdiene til de påvirkende cellene (de påvirkende cellene, i dette tilfellet er disse de skiftende cellene, er cellene som er designet for å lagre verdiene til de ukjente ukjente), sett bryteren til posisjon maksimal verdi;

I felt Bytte celler skriv inn referanser til cellene som skal endres, og separer dem med kommaer; eller, hvis cellene er tilstøtende, angir den første og siste cellen, skille dem med et kolon ( $ D$5:$F$5).

I felt Begrensninger angi alle restriksjoner pålagt søket etter en løsning. La oss vurdere å legge til en begrensning ved å bruke eksemplet med å legge til den første begrensningen på det totale arealet av dyrkbar jord.

I kapittel Begrensninger dialogboks Å finne en løsning klikk på knappen Legg til. Følgende dialogboks vises (fig. 5)

Figur 5

I felt Cellereferanse Skriv inn adressen til cellen hvis verdi er begrenset. I vårt tilfelle er dette cellen $ G$6, hvor er formelen for beregning av dyrkbar mark brukt i gjeldende plan.

Velg fra rullegardinlisten betinget operatør <= , som skal være plassert mellom koblingen og begrensningen.

I felt Begrensning Skriv inn en lenke til cellen som inneholder verdien av tilgjengeligheten av dyrkbar jord på gården, eller en lenke til denne verdien. I vårt tilfelle er dette cellen $ jeg $6

Som et resultat vil dialogboksen ha følgende form (fig. 6).

Figur 6

For å godta begrensningen og begynne å legge inn en ny, klikk på knappen Legg til. Andre restriksjoner innføres tilsvarende. For å gå tilbake til dialogboksen Å finne en løsning, trykk på knappen OK.

Etter å ha fulgt instruksjonene ovenfor, vises dialogboksenÅ finne en løsningvil ha følgende form (fig. 7).

Figur 7

For å endre eller fjerne restriksjoner i listen Begrensninger dialogboks Å finne en løsning spesifiser restriksjonen du vil endre eller fjerne. Velg et lag Endring og gjør endringer eller klikk på knappen Slett.

Avmerkingsboks Lineær modell i dialogboksen Alternativer Å finne en løsning(Fig. 8) lar deg angi et hvilket som helst antall begrensninger. Avmerkingsboks Ikke-negative verdier vil tillate oss å overholde betingelsen om ikke-negativitet av variabler (når vi løser problemet vårt, er dette obligatorisk). Du kan la de resterende parametrene være uendret, eller stille inn parametrene du trenger, ved å bruke hjelpen om nødvendig.

Figur 8

For å starte løsningsoppgaven, klikk på knappen Henrette og gjør ett av følgende:

- for å gjenopprette originale data, velg alternativ Gjenopprett opprinnelige verdier.

Figur 9

For å slutte å søke etter en løsning, trykk på tasten ESC.

Microsoft Excel-arket vil bli beregnet på nytt under hensyntagen til de funnet verdiene til de påvirkende cellene. Som et resultat av å løse og lagre søkeresultatene på arket, vil modellen ha følgende form (tabell 10).

Figur 10

I celler D5-F5 verdiene av de nødvendige ukjente oppnås (avlingsarealet er lik: korn - 2500 ha, sukkerroer - 661 ha, solsikke - 39 ha), i celler G6-G9 ressursvolumene som ble brukt ble bestemt (totalt areal med dyrkbar jord - 3200 hektar; område med dyrkbar jord som kan brukes til såing av industrielle avlinger - 700 hektar; arbeidskraft - 6781,9 dagsverk; mineralgjødsel - 15000 c.d.v.) , i celle G10 mengden produsert korn ble etablert (65 000 centners). Med alle disse verdiene når fortjenesten 12603,5 tusen rubler. (celle G11).

Hvis søket ikke fant en løsning som tilfredsstiller de angitte betingelsene, i dialogboksen Løsningssøkeresultater en tilsvarende melding vises (fig. 11).

Figur 11

En av de vanligste årsakene til at det ikke er mulig å finne en optimal løsning, er situasjonen når det som følge av å løse et problem viser seg at det er begrensninger som ikke er oppfylt. Etter å ha lagret den funnet løsningen på arket, må du sammenligne de oppnådde verdiene for kolonnene "Sum of Products" og "Volum of Constraints" linje for linje og sjekke om forholdet mellom dem tilfredsstiller begrensningen i "Type of Constraints" Begrensninger»-kolonnen. Etter å ha funnet uoppfylte restriksjoner, er det nødvendig å finne og eliminere årsakene som gjør det umulig å overholde denne spesifikke betingelsen (dette kan for eksempel være for store eller omvendt svært små planlagte restriksjoner osv.).

Hvis det er mange begrensninger i modellen, er det visuelt ganske vanskelig å sammenligne og sjekke hver linje for nøyaktighet. For å gjøre det enklere, anbefales det å legge til en annen "Validation"-kolonne til modellen, der du bruker MS-funksjoner utmerke « HVIS"Og" RUND» du kan organisere en automatisk sjekk (fig. 12).

Figur 12

Løse lineære programmeringsproblemer i MS Excel

Et verktøy for å løse optimaliseringsproblemer i MS Excel er "Solution Search"-tillegget . Løsningssøkeprosedyren lar deg finne den optimale verdien av formelen i cellen, som kalles målcellen. Denne prosedyren fungerer på en gruppe celler som er direkte eller indirekte relatert til en formel i målcellen. For å oppnå et spesifisert resultat fra formelen i målcellen, endrer prosedyren verdiene i de påvirkende cellene.

Hvis dette tillegget er installert, startes "Søk etter en løsning" fra "Verktøy"-menyen. Hvis det ikke er noe slikt element, bør du utføre kommandoen "Verktøy - Tillegg..." og merke av i boksen ved siden av "Søk etter en løsning"-tillegget.

Løsningen på optimaliseringsproblemet består av tre trinn.

A. Lage en modell av optimaliseringsproblemet.

B. Finne en løsning på optimaliseringsproblemet.

C. Analyse av funnet løsning på optimaliseringsproblemet.

La oss se nærmere på disse stadiene.

Trinn A.

På stadiet for å lage modellen, legges betegnelsene til de ukjente inn, områdene på regnearket er fylt med de første dataene for problemet, og formelen for målfunksjonen legges inn.

Trinn B.

Kommandoen "Tjeneste - Søk etter en løsning" åpner dialogboksen "Søk etter en løsning", som igjen inneholder følgende felt:

"Sett målcelle" - tjener til å spesifisere målcellen hvis verdi skal maksimeres, minimeres eller settes til et spesifisert antall. Denne cellen må inneholde en formel.

"Lik" - tjener til å velge et alternativ for å optimalisere verdien av målcellen (maksimering, minimering eller valg av et gitt tall). For å angi et tall, skriv det inn i feltet.

"Endre celler" - tjener til å indikere celler hvis verdier endres under søket etter en løsning til de pålagte restriksjonene og betingelsen for å optimalisere verdien til cellen spesifisert i feltet "Angi målcelle" er oppfylt.

"Anta" - brukes til å automatisk finne celler som påvirker formelen det refereres til i feltet "Angi målcelle". Søkeresultatet vises i feltet "Changing Cells".

"Begrensninger" - tjener til å vise en liste over grensebetingelser for oppgaven.

"Legg til" - tjener til å vise dialogboksen "Legg til begrensning".

"Rediger" - tjener til å vise dialogboksen "Rediger begrensning".

"Slett" - tjener til å fjerne den angitte begrensningen.

"Kjør" - tjener til å begynne å søke etter en løsning på oppgaven.

"Lukk" - tjener til å gå ut av dialogvinduet uten å starte et søk etter en løsning på oppgaven. Samtidig lagres innstillingene som er gjort i dialogvinduene som vises etter å ha klikket på "Alternativer, Legg til, Endre eller Slett"-knappene.

"Parameters" - tjener til å vise dialogboksen "Løsningssøkealternativer", der du kan laste eller lagre modellen som skal optimaliseres og spesifisere tilgjengelige søkealternativer for løsning.

"Gjenopprett" - tjener til å tømme feltene i dialogvinduet og gjenopprette standardverdiene for løsningssøkeparametrene.

Følg disse trinnene for å løse et optimaliseringsproblem:

1. I "Verktøy"-menyen velger du kommandoen "Søk etter en løsning".

2. I "Angi målcelle"-feltet skriver du inn adressen eller navnet på cellen som inneholder formelen til modellen som skal optimaliseres.

3. For å maksimere verdien av målcellen ved å endre verdiene til de påvirkende cellene, sett bryteren til maksimal verdiposisjon.

For å minimere verdien til målcellen ved å endre verdiene til de påvirkende cellene, sett bryteren til posisjonen som tilsvarer minimumsverdien.

For å sette verdien i målcellen til et visst tall ved å endre verdiene til de påvirkende cellene, sett bryteren til Verdi og skriv inn ønsket tall i det tilsvarende feltet.

4. I feltet "Changing Cells" skriver du inn navnene eller adressene til cellene som skal endres, og skiller dem med kommaer. Cellene som modifiseres må være direkte eller indirekte relatert til målcellen. Opptil 200 variable celler kan installeres.

For automatisk å finne alle celler som påvirker modellformelen, klikk Gjett-knappen.

5. I «Begrensninger»-feltet skriver du inn eventuelle begrensninger som gjelder for søket etter en løsning.

6. Klikk på Kjør-knappen.

For å gjenopprette de opprinnelige dataene, sett bryteren til "Gjenopprett opprinnelige verdier"-posisjon.

Trinn C.

For å vise en siste melding om løsningsresultatet, bruk dialogboksen "Løsningssøkeresultater".

Dialogboksen Løsningssøkeresultater inneholder følgende felt:

"Gjenopprett opprinnelige verdier" - tjener til å gjenopprette de opprinnelige verdiene til de påvirkende modellcellene.

"Rapporter" - tjener til å indikere typen rapport som er plassert på et eget ark i boken.

"Resultater" - brukes til å lage en rapport som består av målcellen og en liste over de påvirkende modellcellene, deres innledende og endelige verdier, samt begrensningsformler og tilleggsinformasjon om de pålagte begrensningene.

Robusthet – Brukes til å generere en rapport som inneholder informasjon om følsomheten til en løsning for små endringer i formelen (Angi målcelle-feltet, dialogboksen Finn løsning) eller i begrensningsformler.

"Begrensninger" - brukes til å lage en rapport som består av en målcelle og en liste over påvirkende modellceller, deres verdier og nedre og øvre grenser. Denne rapporten er ikke generert for modeller hvis verdier er begrenset til mange heltall. Den nedre grensen er den minste verdien som den påvirkende cellen kan inneholde, mens verdiene til de gjenværende påvirkningscellene er faste og tilfredsstiller de pålagte restriksjonene. Følgelig er den øvre grensen den største verdien.

"Lagre skript" - tjener til å vise dialogboksen Lagre skript, der du kan lagre skriptet for å løse problemet for å bruke det senere ved å bruke MS Excel Script Manager.

Et av de mulige problemene og modellene for lineær optimalisering er problemet med produksjonsplanlegging.

Foretaket må produsere produkter av følgende typer: , Dessuten bør mengden av hvert produsert produkt ikke overstige etterspørselen og samtidig ikke være mindre enn planlagte verdier. Går til å produsere produkter m typer råvarer , hvis reserver er begrenset tilsvarende av verdiene Det er kjent for produksjonen Jeg-ro-produkter går i enheter j-th råvarer. Fortjenesten mottatt ved salg av produkter er tilsvarende lik . Det kreves å planlegge produksjonen av produkter på en slik måte at fortjenesten maksimeres og samtidig oppfylles planen for produksjonen av hvert produkt, men etterspørselen etter det ikke overskrides.

Lineær programmering er delen som disiplinen "matematisk programmering" begynte å utvikle seg fra. Begrepet "programmering" i disiplinens navn har ingenting til felles med begrepet "programmering (dvs. kompilere programmer) for en datamaskin", siden disiplinen "lineær programmering" oppsto allerede før tiden da datamaskiner begynte å bli mye brukt i å løse matematiske og tekniske problemer, økonomiske og andre problemer. Begrepet "lineær programmering" oppsto som et resultat av en unøyaktig oversettelse av den engelske "lineær programmering". En av betydningene av ordet "programmering" er å lage planer, planlegge. Følgelig vil den korrekte oversettelsen av "lineær programmering" ikke være "lineær programmering", men "lineær planlegging", som mer nøyaktig gjenspeiler innholdet i disiplinen. Imidlertid er begrepet lineær programmering, ikke-lineær programmering, etc. har blitt allment akseptert i vår litteratur. Lineære programmeringsproblemer er en praktisk matematisk modell for et stort antall økonomiske problemer (produksjonsplanlegging, materialforbruk, transport, etc.). Å bruke den lineære programmeringsmetoden er viktig og verdifull - det optimale alternativet er valgt fra et ganske betydelig antall alternative alternativer. Alle økonomiske problemer som løses ved hjelp av lineær programmering kjennetegnes ved alternative løsninger og visse begrensende forhold. I Excel-regneark kan du søke etter en verdi i målcellen og endre verdien av variabler. I dette tilfellet kan du angi begrensninger for hver variabel, for eksempel en øvre grense. Før du starter søket etter en løsning, er det nødvendig å tydelig formulere problemet som skal løses i modellen, dvs. bestemme betingelsene som skal oppfylles under optimalisering. Utgangspunktet for å finne den optimale løsningen er beregningsmodellen som er laget i arbeidsarket. Løsningssøkeprogrammet krever følgende data. 1. En målcelle er en celle i en beregningsmodell hvis verdier må maksimeres, minimeres eller lik en bestemt spesifisert verdi. Den må inneholde en formel som direkte eller indirekte refererer til cellene som endres, eller den må selv endres. 2. Verdiene i cellene som endres vil bli endret sekvensielt (ved iterasjon) til ønsket verdi er oppnådd i målcellen. Disse cellene må derfor direkte eller indirekte påvirke verdien av målcellen. 3. Du kan angi restriksjoner og grensebetingelser for både målcellene og modifiserte celler. Du kan også angi begrensninger for andre celler. Direkte eller indirekte tilstede i modellen. Programmet gir muligheten til å sette spesielle parametere som bestemmer prosessen med å finne en løsning. Etter å ha angitt alle nødvendige parametere, kan du begynne å søke etter en løsning. Løsningssøkefunksjonen vil lage tre rapporter basert på resultatene av sitt arbeid, som kan markeres i arbeidsboken. Begrensninger er betingelsene som må oppfylles av løsningssøkeverktøyet ved optimalisering av modellen.

En studie av litteraturen viste at:

1. Lineær programmering er en av de første og mest grundig studerte delene av matematisk programmering. Det var lineær programmering som var delen som selve disiplinen "matematisk programmering" begynte å utvikle seg fra.

Lineær programmering er den mest brukte optimaliseringsmetoden. Lineære programmeringsproblemer inkluderer følgende:

• · rasjonell bruk av råvarer og materialer; kutte optimaliseringsproblemer;
• · Optimalisering av produksjonsprogrammet til bedrifter;
• · optimal plassering og konsentrasjon av produksjonen;
• · utarbeide en optimal transportplan og transportdrift;
• · lagerstyring;
• · og mange andre som tilhører feltet optimal planlegging.
• 2. Den grafiske metoden er ganske enkel og intuitiv for å løse lineære programmeringsproblemer med to variabler. Den er basert på den geometriske representasjonen av gjennomførbare løsninger og TF-er for problemet.

Essensen av den grafiske metoden er som følger. I retning (mot retning) av vektoren i ODR søkes det optimale punktet. Det optimale punktet er punktet som nivålinjen går gjennom, tilsvarende funksjonens største (minste) verdi. Den optimale løsningen er alltid plassert på grensen til ODD, for eksempel ved det siste toppunktet av ODD-polygonet som mållinjen vil passere gjennom, eller på hele siden.

Send ditt gode arbeid i kunnskapsbasen er enkelt. Bruk skjemaet nedenfor

Studenter, hovedfagsstudenter, unge forskere som bruker kunnskapsbasen i studiene og arbeidet vil være veldig takknemlige for deg.

postet på http://www.allbest.ru/

postet på http://www.allbest.ru/

Privat utdanningsinstitusjon for høyere utdanning "St. Petersburg University of Management Technologies and Economics"

Institutt for økonomi og ledelse

TEST

Etter disiplin: METODER FOR OPTIMALE LØSNINGER

Fullført:

Student(er) 3 kurs, gruppenr. 19731D/3-2

Kryuk Albina Vladimirovna

Veileder:

Ph.D., førsteamanuensis Zh.M. Kozlova.

Barnaul2016

• Introduksjon
• Konklusjon
• INTRODUKSJON
• Løsningen på et bredt spekter av problemer i den elektriske kraftindustrien og andre sektorer av den nasjonale økonomien er basert på optimalisering av et komplekst sett av avhengigheter beskrevet matematisk ved hjelp av en viss "objektiv funksjon" (TF). Lignende funksjoner kan skrives for å bestemme kostnadene for drivstoff for kraftverk, tap av elektrisitet under transporten fra kraftverket til forbrukerne, og mange andre problematiske oppgaver. I slike tilfeller er det nødvendig å finne CF under visse begrensninger pålagt variablene. Hvis CF lineært avhenger av variablene som er inkludert i sammensetningen og alle begrensninger danner et lineært system av likninger og ulikheter, kalles denne spesielle formen for optimaliseringsproblemet et "lineært programmeringsproblem."
• Emner for prøvearbeidet "Løse lineære programmeringsproblemer i MS Excel", få praktiske ferdigheter i å bruke Microsoft Excel-regneark og løse optimaliseringsproblemer ved lineær programmering.

1. Typiske optimaliseringsproblemer og deres økonomiske og matematiske modeller

Økonomisk-matematisk modellering er prosessen med å uttrykke økonomiske fenomener ved hjelp av matematiske modeller. En økonomisk modell er en skjematisk representasjon av et økonomisk fenomen eller prosess ved bruk av vitenskapelig abstraksjon, en refleksjon av deres karakteristiske trekk. Matematiske modeller er hovedmetoden for å løse problemer med optimalisering av enhver aktivitet. I kjernen er disse modellene et middel for å planlegge beregninger. Deres verdi for økonomisk analyse og optimalisering av beslutninger ligger i det faktum at de lar en vurdere intensiteten til planlagte mål, bestemme den begrensende gruppen av utstyr, typer ressurser, få estimater av deres knapphet, etc. Matematisk modellering av økonomiske fenomener og prosesser gjør det mulig å oppnå en klar forståelse av objektet som studeres, å karakterisere og kvantitativt beskrive dets interne struktur og eksterne sammenhenger. Modell er et betinget bilde av kontrollobjektet /1/.

Den økonomiske og matematiske modellen må være tilstrekkelig til virkeligheten og reflektere de vesentlige aspektene og sammenhengene ved objektet som studeres. La oss merke oss de grunnleggende egenskapene som er karakteristiske for å konstruere en økonomisk og matematisk modell av noe slag. Modelleringsprosessen kan deles inn i tre stadier:

1) analyse av teoretiske mønstre iboende i fenomenet eller prosessen som studeres og empiriske data om dets struktur og funksjoner; basert på slik analyse dannes modeller;

2) identifisering av metoder for å løse problemet;

3) analyse av de oppnådde resultatene.

Det viktigste punktet i den første fasen av modelleringen er den klare formuleringen av det endelige målet med å bygge modellen, samt definisjonen av kriteriet som ulike løsningsalternativer skal sammenlignes med. Slike kriterier i styringssystemet kan være:

a) maksimere den fordelaktige effekten av et produkt samtidig som totalkostnaden begrenses;

b) maksimere firmaets fortjeneste, forutsatt at kvaliteten på produktet ikke reduseres; c) å redusere kostnadene for produktet, forutsatt at kvaliteten ikke reduseres og forbrukerens kostnader ikke øker;

d) økt arbeidsproduktivitet, forbedret bruk av utstyr eller materialer, økt omsetning av arbeidskapital, forutsatt at kvaliteten på varene ikke synker og andre kriterier ikke forringes.

Dermed kan optimaliseringskriteriet være hele eller en hvilken som helst komponent av profitt, produkteffektivitet, markedsvolum, forutsatt at andre komponenter ikke forringes.

For eksempel vil ligningen for den objektive funksjonen (L) og systemet med restriksjoner for å optimalisere selskapets fortjeneste (selv om forfatterne ikke har noen begrensninger på kvaliteten på produktet) ha følgende form:

hvor xj er mengden produserte produkter av den j. typen i naturlige mål;

Pj -- fortjeneste mottatt fra produksjonen av en produktenhet av den jth typen;

aij er forbrukshastigheten til den i-te produksjonsressursen for produksjon av en enhet av den j-te typen produkt;

шj -- reserver av den i-te typen produksjonsressurs for tidsperioden som vurderes.

Ikke alle økonomiske problemer trenger sin egen modell. Noen prosesser er av samme type fra et matematisk synspunkt og kan beskrives med de samme modellene. For eksempel, i lineær programmering, køteori og andre, er det standardmodeller som mange spesifikke problemer reduseres til.

Den andre fasen av modellering av økonomiske prosesser er valg av den mest rasjonelle matematiske metoden for å løse problemet. For eksempel er mange metoder kjent for å løse lineære programmeringsproblemer: simpleks, potensialer osv. Den beste modellen er ikke den mest komplekse og ligner mest på det virkelige fenomenet, men den som lar deg få den mest rasjonelle løsningen og den mest nøyaktige økonomiske estimater. Overdreven detaljering gjør det vanskelig å bygge en modell, og overdreven utvidelse av modellen fører til tap av betydelig økonomisk informasjon og en utilstrekkelig refleksjon av virkeligheten.

Den tredje fasen av modellering er en omfattende analyse av resultatet oppnådd fra å studere det økonomiske fenomenet. Det endelige kriteriet for modellens pålitelighet og kvalitet er praksis, samsvar mellom oppnådde resultater og konklusjoner til reelle forhold, og den økonomiske meningsfullheten til de oppnådde estimatene. Hvis resultatene ikke samsvarer med reelle forhold, er det nødvendig med en analyse av årsakene til avviket, som kan inkludere upålitelig informasjon, inkonsistens av modellen med økonomiske forhold osv. Basert på resultatene av analysen av årsakene til avvik justeres den økonomisk-matematiske modellen og løsningen på problemet gjentas.

La oss løse et typisk optimaliseringsproblem grafisk

Noen selskaper produserer to sett med plengjødsel: vanlig og forbedret. Det vanlige settet inneholder 3 kg nitrogen, 4 kg fosfor og 1 kg kaliumgjødsel, og det forbedrede settet inkluderer 2 kg nitrogen, 6 kg fosfor og 3 kg kaliumgjødsel. Det er kjent at noen plener krever minst 10 kg nitrogen, 20 kg fosfor og 7 kg kaliumgjødsel. Et vanlig sett koster 3 den. Enheter, og forbedret - 4 dager. Enhet Hva og hvor mange sett med gjødsel bør jeg kjøpe for å sikre effektiv jordnæring og minimere kostnadene?

Konstruer en økonomisk og matematisk modell av problemet, gi de nødvendige kommentarene til dets elementer og få en løsning ved hjelp av den grafiske metoden. Hva skjer hvis du løser et problem maksimalt, og hvorfor?

La oss formulere et direkte optimaliseringsproblem.

La x1 være antall vanlige sett med gjødsel;

x2 - antall forbedrede gjødselsett.

Og noen plener krever minst 10 kg nitrogengjødsel, derfor:

3x1 + 2x2? 10

4x1 + 6x2 ? 20

Kostnaden for de nødvendige settene med gjødsel vil være:

Dermed får vi følgende økonomiske og matematiske modell av problemet:

min (x) = 3x1 + 4x2

3x1 + 2x2? 10

4x1 + 6x2 ? 20

La oss konstruere løsningsdomenet til begrensningssystemet. For å gjøre dette, vurder likhetene og konstruer grafene deres - rette linjer.

1) 3x1 + 2x2? 10

3x1 + 2x2 = 10

3) x1 + 3x2 ? 7

Ulikheten er ikke tilfredsstilt, noe som betyr at den opprinnelige ulikheten tilsvarer et halvplan som ikke inneholder punktet O(0;0).

x1 = 0 - OX2 aksen.

x2 = 0 - akse OX1.

Følgelig er løsningsområdet til begrensningssystemet kun plassert i første kvartal av det kartesiske koordinatsystemet.

Figur 1. Grafisk løsning av ZLP

Vi finner fellesdelen av alle konstruerte halvplan. Dette er et forhøyet skyggelagt område.

For å finne den optimale løsningen på problemet, la oss grafisk skildre målfunksjonen:

(x) = d1x1 + d2x2

(x) = 3x1 + 4x2

For å gjøre dette konstruerer vi en vektor d, hvis begynnelse er ved punktet (0;0), og slutten i punktet (d1;d2).

Og vi bygger en av målfunksjonsnivålinjene (dette er linjen som målfunksjonen har en konstant verdi på).

For å bestemme minimum av denne funksjonen flytter vi nivålinjen i retning motsatt av vektoren d, og vi ser at den sist kommer i kontakt med løsningsområdet i punkt B, hvor min(x) vil nås.

La oss bestemme koordinatene til punkt B:

3x1 + 2x2 = 10 *(-3)

4x1 + 6x2 = 20

9x1 - 6x2 = -30

4x1 + 6x2 = 20

Vi legger til ligningene ledd for ledd og får:

(x) = 3*2 + 4*2 = 14 (den. enheter)

Så for å minimere kostnadene for gjødsel, må du kjøpe 2 vanlige sett med gjødsel og 2 forbedrede sett med gjødsel. I dette tilfellet vil minimumskostnaden for kjøp av gjødsel være 14 monetære enheter. microsoft excel programmering matematisk

Hvis vi løser dette problemet maksimalt, vil vi ikke finne det endelige optimum, fordi målfunksjonen er ubegrenset, løsningsområdet til begrensningssystemet er uendelig.

2. Lineære programmeringsproblemer, løsning med MS Excel

Lineær programmering er delen som disiplinen "matematisk programmering" begynte å utvikle seg fra. Begrepet "programmering" i disiplinens navn har ingenting til felles med begrepet "programmering (dvs. kompilere programmer) for en datamaskin", siden disiplinen "lineær programmering" oppsto allerede før tiden da datamaskiner begynte å bli mye brukt i å løse matematiske og tekniske problemer, økonomiske og andre problemer. Begrepet "lineær programmering" oppsto som et resultat av en unøyaktig oversettelse av den engelske "lineær programmering". En av betydningene av ordet "programmering" er å lage planer, planlegge. Følgelig vil den korrekte oversettelsen av "lineær programmering" ikke være "lineær programmering", men "lineær planlegging", som mer nøyaktig gjenspeiler innholdet i disiplinen. Imidlertid er begrepet lineær programmering, ikke-lineær programmering, etc. har blitt allment akseptert i vår litteratur. Lineære programmeringsproblemer er en praktisk matematisk modell for et stort antall økonomiske problemer (produksjonsplanlegging, materialforbruk, transport, etc.). Å bruke den lineære programmeringsmetoden er viktig og verdifull - det optimale alternativet er valgt fra et ganske betydelig antall alternative alternativer. Alle økonomiske problemer løst ved hjelp av lineær programmering utmerker seg også ved alternative løsninger og visse begrensende forhold.
I Excel-regneark, ved hjelp av løsningssøkefunksjonen, kan du søke etter en verdi i en målcelle og endre verdien på variabler. I dette tilfellet kan du angi begrensninger for hver variabel, for eksempel en øvre grense. Før du starter søket etter en løsning, er det nødvendig å tydelig formulere problemet som skal løses i modellen, dvs. bestemme betingelsene som skal oppfylles under optimalisering. Utgangspunktet for å finne den optimale løsningen er beregningsmodellen som er laget i arbeidsarket. Løsningssøkeprogrammet krever følgende data. 1. En målcelle er en celle i en beregningsmodell hvis verdier må maksimeres, minimeres eller lik en bestemt spesifisert verdi. Den må inneholde en formel som direkte eller indirekte refererer til cellene som endres, eller den må selv endres. 2. Verdiene i cellene som endres vil bli endret sekvensielt (ved iterasjon) til ønsket verdi er oppnådd i målcellen. Disse cellene må derfor direkte eller indirekte påvirke verdien av målcellen. 3. Du kan angi restriksjoner og grensebetingelser for både målcellene og modifiserte celler. Du kan også angi begrensninger for andre celler. Direkte eller indirekte tilstede i modellen. Programmet gir muligheten til å sette spesielle parametere som bestemmer prosessen med å finne en løsning. Etter å ha angitt alle nødvendige parametere, kan du begynne å søke etter en løsning. Løsningssøkefunksjonen vil lage tre rapporter basert på resultatene av sitt arbeid, som kan markeres i arbeidsboken. Begrensninger er betingelsene som må oppfylles av løsningssøkeverktøyet ved optimalisering av modellen.

En studie av litteraturen viste at:

1. Lineær programmering er en av de første og mest grundig studerte delene av matematisk programmering. Det var lineær programmering som var delen som selve disiplinen "matematisk programmering" begynte å utvikle seg fra.

Lineær programmering er den mest brukte optimaliseringsmetoden. Lineære programmeringsproblemer inkluderer følgende:

· rasjonell bruk av råvarer og materialer; kutte optimaliseringsproblemer;

· Optimalisering av produksjonsprogrammet til bedrifter;

· optimal plassering og konsentrasjon av produksjonen;

· utarbeide en optimal transportplan og transportdrift;

· lagerstyring;

· og mange andre som tilhører feltet optimal planlegging.

2. Den grafiske metoden er ganske enkel og intuitiv for å løse lineære programmeringsproblemer med to variabler. Den er basert på den geometriske representasjonen av gjennomførbare løsninger og TF-er for problemet.

Essensen av den grafiske metoden er som følger. I retning (mot retning) av vektoren i ODR søkes det optimale punktet. Det optimale punktet er punktet som nivålinjen går gjennom, tilsvarende funksjonens største (minste) verdi. Den optimale løsningen er alltid plassert på grensen til ODD, for eksempel ved det siste toppunktet av ODD-polygonet som mållinjen vil passere gjennom, eller på hele siden.

KONKLUSJON

Ved hjelp av riktig formulering av og tilgjengeligheten av grunnleggende produksjonsparametere, kan vi finne en produksjonsplan som vil oppnå maksimal fortjeneste.

Takket være Excel-programvareproduktet, som er inkludert i MS Office-pakken, akselereres løsningen av problemene flere dusin ganger. Og takket være de nøyaktige matematiske beregningene til denne programvaren, kan vi uten tvil finne de mest nøyaktige forskningsresultatene.

Skrevet på Allbest.ru

...

Lignende dokumenter

Kort informasjon om MS Excel-regneark. Løsning av et lineært programmeringsproblem. Løsning ved hjelp av Microsoft Excel-verktøy for et økonomisk optimaliseringsproblem, ved å bruke eksempelet på et "transportproblem". Funksjoner i MS Word-dokumentdesign.

kursarbeid, lagt til 27.08.2012


Utviklingshistorie og funksjoner til lineær programmering. Studie av betingelsene for typiske oppgaver og evner til en bordprosessor. Løse problemer om kosthold, produksjonsplan, skjæring av materialer og rasjonell transport av last i MS Excel.

kursarbeid, lagt til 28.04.2014


Prinsipper for å løse lineære programmeringsproblemer i Excel-regnearkmiljøet, i Mathcad-pakkemiljøet. Fremgangsmåten for å løse oppgaveproblemet i Excel-regnearkmiljøet. Analyse av økonomiske data ved hjelp av Pareto-diagrammer, evaluering av resultater.

laboratoriearbeid, lagt til 26.10.2013


Algoritme for å løse lineære programmeringsproblemer ved bruk av simpleksmetoden. Konstruksjon av en matematisk modell av et lineært programmeringsproblem. Løse et lineært programmeringsproblem i Excel. Finne profitt og optimal produksjonsplan.

kursarbeid, lagt til 21.03.2012


Studerer og styrker i praksis alle aspekter av den grafiske metoden for å løse lineære programmeringsproblemer om produksjonen av magasinene "Auto Mechanic" og "Tool". Konstruksjon av en matematisk modell. Løse et problem ved hjelp av et Excel-regneark.

kursarbeid, lagt til 06.10.2014


Generelt konsept og kjennetegn ved et lineært programmeringsproblem. Løse et transportproblem ved hjelp av MS Excel. Anbefalinger for å løse optimaliseringsproblemer ved å bruke Solution Search-tillegget. Dobbelt lineær programmeringsproblem.

avhandling, lagt til 20.11.2010


Analyse av den lineære programmeringsmetoden for å løse optimeringsstyringsproblemer. Grafisk metode for å løse lineære programmeringsproblemer. Sjekke den optimale løsningen i MS Excel ved å bruke programvaretillegget "Solution Search".

kursarbeid, lagt til 29.05.2015


Utvikling av tabeller i Excel ved bruk av lineære programmeringsmetoder for å optimalisere ressursforbruket og varelageret for produksjon av produkter: bestemmelse av variabler, struktur av målfunksjonen, konstruksjon av en matematisk modell og flytskjemaer for å løse problemer.

kursarbeid, lagt til 06.07.2010


Metoder for å løse lineære programmeringsproblemer: produksjonsplanlegging, rasjoneringsplanlegging, problemer med skjæring av materialer og transport. Utvikling av en økonomisk-matematisk modell og løsning av oppgaven ved hjelp av datamodellering.

kursarbeid, lagt til 13.03.2015


Grafisk problemløsning. Å tegne en matematisk modell. Bestemme maksimalverdien til objektivfunksjonen. Løsning ved simpleksmetoden med en kunstig basis av det kanoniske lineære programmeringsproblemet. Kontroller optimaliteten til løsningen.

Etter å ha studert algoritmene for "manuelt" å løse lineære programmeringsproblemer, er det nyttig å bli kjent med en måte å forenkle denne prosessen. Det er klart at jo mer komplekst problemet er, jo flere variabler og forhold det inneholder, jo mer kjedelig og tidkrevende vil det være å løse. I slike tilfeller er det praktisk å bruke spesielle matematiske pakker, eller MS Excel-programmet, som er tilgjengelig for mange.

Løs lineære programmeringsproblemer i Excel Det er ganske enkelt: 1) skriv inn de første dataene for problemet og begrensningene, 2) start søket etter en løsning-tillegget, 3) still inn de nødvendige parameterne for løsningen og start kjøringen. Programmet vil velge den optimale løsningen og utstede rapporter for å analysere løsningen på problemet.

Alle disse stadiene med forklaringer og skjermbilder diskuteres mer detaljert nedenfor i eksempler som bruker forskjellige lineære programmeringsproblemer - studer, se etter lignende, løs. Hvis du trenger hjelp til å fullføre oppgavene, gå til: Lineære programmeringstester.

Lineær programmering: eksempler på løsninger i Excel

Oppgave 1. Bygg en matematisk modell av problemet og løs den ved hjelp av Excel. Skriv ned det tilhørende problemet. Gjennomfør en analyse og trekk konklusjoner basert på de oppnådde resultatene.
En møbelfabrikk bruker ulike ressurser på å produsere bord og skap. Satsene for ressursutgifter for ett produkt av en gitt type, fortjeneste fra salg av ett produkt og den totale mengden tilgjengelige ressurser av hver type er vist i tabellen.
Bestem hvor mange bord og skap fabrikken skal produsere for å maksimere fortjeneste fra salg.

Oppgave 2. Verkstedet produserer 8 forskjellige typer deler til motorene A, B, C1, C2, C3, D, E6, F, og har følgende flåte på 7 typer universalmaskiner til disposisjon: 2 stk. -ADF, 3 stk. -SHG, 3 stk. -BSD, 1 stk. -AVP, 1 stk. -BFG, 3 stk. -ABM, 2 stk. -RL.
Tiden det tar å behandle en enhet av hvert produkt på hver maskin, bidraget til profitt ved å produsere en enhet av hvert produkt og markedsetterspørselen for hvert produkt per måned er gitt i tabellen.
Verkstedet er i drift 12 timer i døgnet. Hver måned inneholder 26 virkedager. For å forenkle problemet, tror vi at en vilkårlig rekkefølge av bearbeiding av deler på forskjellige maskiner er mulig.
Lag en optimal produksjonsplan.
Bestem hvilke produkter som er begrenset i produksjon av markedet, og hvilke som er begrenset av verkstedets tekniske muligheter. Hvilke maskinressurser bør økes først for å maksimere fortjenesten (gitt markedsbehov)?
Er det et produkt som er ulønnsomt å produsere? Hvorfor? Hva må endres for å gjøre alle produkter lønnsomme å produsere?

Oppgave 3. Det er nødvendig å lage den billigste dietten for kyllinger som inneholder den nødvendige mengden av visse næringsstoffer tiamin T og niacin N. Diettens næringsverdi (i kalorier) må ikke være mindre enn den spesifiserte. Kyllingblandingen er laget av to produkter - K og S. Innholdet av tiamin og niacin i disse produktene er kjent, samt næringsverdien av K og S (i kalorier). Hvor mye K og C bør tas for én porsjon kyllingfôr slik at kyllingene får dosen av stoffene H og T og kalorier (eller mer) de trenger, og kostnaden per porsjon er minimal? De første dataene for beregningene er gitt i tabellen.

Oppgave 4. Computer Service-selskapet leverer nøkkelferdige datamaskiner i fire grunnleggende konfigurasjoner: "hjemme", "spill", "kontor" og "ekstrem". Gjennomsnittlig tid brukt på å montere, teste og koble til datamaskiner er kjent. Hver datamaskin gir et visst nivå av fortjeneste, men etterspørselen er begrenset. I tillegg, i planleggingsperioden, er ressursen på arbeidstimer som er tildelt for å utføre hver produksjonsoperasjon begrenset. Bestem hvor mange datamaskiner av hver type som må produseres i planleggingsperioden, med mål om å maksimere fortjenesten.

Oppgave 5. Sagbruket mottar 10 m lange plater Sagbruket skal i følge kontrakten forsyne kunden med minst 100 5 m lange plater, og minst 300 3 m lange plater oppfylle vilkårene i kontrakten ved å kutte minst antall brett?

Oppgave 6. Eurostroytour-selskapet organiserer utfluktsbussturer over hele Europa. Selskapet har mottatt 4 nye busser og planlegger å sende dem på ruter til Frankrike, Italia, Tsjekkia og Spania. Hver buss betjenes av 2 sjåfører. Selskapet inviterte 8 sjåfører, i ulik grad kjent med veiene i europeiske land (i prosent av ekskursjonsruten).
Det er nødvendig å fordele sjåførene slik at den samlede hastigheten på ruteutviklingen er maksimal.

Oppgave 7. Løs problemet ved å bruke branch and bound-metoden, løs individuelle problemer med lineær ikke-heltallsprogrammering ved å bruke funksjonen "Søk etter en løsning" i Microsoft Excel (i tilfelle det aller første LP-problemet produserer en heltallsløsning, og ikke tillater problemet forgrenes eller de opprinnelige betingelsene endres litt).
Sammensetningen av maten til menigheten reguleres av det øverste hovedkvarteret til den øverstkommanderende, som setter de lavere daglige ernæringsstandardene for hovedkomponentene: 1500 kilokalorier, 100 g proteiner, 280 g karbohydrater, 90 g fett, 1 kg vann. Det er 4 typer produkter i varehusene som gis til forsvarerne av moderlandet i tørre rasjoner: lemonade, lapskaus i små krukker, standardiserte sett med skorper og bjørnebærpaier. Kostnaden for disse fire produktene er henholdsvis 12 rubler, 34 rubler, 3 rubler. og 20 gni. Hva er minimumsbeløpet en offiser bør bruke på å mate en soldat?

Oppgave 8. Bedriften produserer to typer produkter: Produkt 1 og Produkt 2. For å produsere en enhet av Produkt 1, er det nødvendig å bruke 11 kg råvarer av den første typen, 21 kg råvarer av den andre typen, 31 kg råvarer av den tredje typen.
For å produsere en enhet av produkt 2, er det nødvendig å bruke 12 kg råvarer av den første typen, 22 kg råvarer av den andre typen, 32 kg råvarer av den tredje typen.
Produksjonen forsynes med råvarer av hver type i mengder på henholdsvis b1 kg, b2 kg, b3 kg.
Markedsprisen på en enhet av produkt 1 er c1 tusen rubler, og en enhet av produkt 2 er c2 tusen rubler.
Påkrevd:
1) bygge en økonomisk og matematisk modell av problemet;
2) utarbeide en produksjonsplan for produkter som sikrer maksimal inntekt fra salget ved hjelp av en grafisk metode for å løse et lineært programmeringsproblem.
3) utarbeide en plan for produksjon av produkter som sikrer maksimale inntekter fra salg ved hjelp av en tabellformet simpleks - en metode for å løse et lineært programmeringsproblem.
4) utarbeide en plan for produksjon av produkter som sikrer maksimal inntekt fra salget, ved å bruke tillegget "Solution Search" i MS EXCEL-miljøet.