Poziva se optimalna vrijednost funkcije cilja. Rješavanje problema linearnog programiranja grafičkom metodom

Konstruirajmo na ravni skup izvodljivih rješenja sistema linearnih nejednačina i geometrijski pronađemo minimalnu vrijednost ciljne funkcije.

Prave linije gradimo u x 1 x 2 koordinatnom sistemu

Nalazimo poluravnine definisane sistemom. Pošto su nejednakosti sistema zadovoljene za bilo koju tačku u odgovarajućoj poluravni, dovoljno ih je provjeriti za bilo koju tačku. Koristimo tačku (0;0). Zamenimo njegove koordinate u prvu nejednakost sistema. Jer , tada nejednakost definira poluravninu koja ne sadrži tačku (0;0). Slično definiramo i preostale poluravnine. Skup izvodljivih rješenja nalazimo kao zajednički dio rezultirajućih poluravnina - ovo je zasjenjeno područje.

Konstruišemo vektor i liniju nultog nivoa okomitu na njega.

Krećući se pravac (5) u pravcu vektora i vidimo da će maksimalna tačka regiona biti u tački A preseka prave (3) i prave (2). Pronalazimo rješenje sistema jednačina:

To znači da smo dobili poen (13;11) i.

Krećući se pravac (5) u pravcu vektora i vidimo da će minimalna tačka regiona biti u tački B preseka prave (1) i prave (4). Pronalazimo rješenje sistema jednačina:

To znači da smo dobili poen (6;6) i.

2. Firma za namještaj proizvodi kombinovane ormare i kompjuterske stolove. Njihova proizvodnja je ograničena dostupnošću sirovina (kvalitetne ploče, okovi) i vremenom rada mašina koje ih obrađuju. Za svaki ormar je potrebno 5 m2 dasaka, za sto - 2 m2. Oprema košta 10 dolara za jedan ormar i 8 dolara za jedan sto. Kompanija može dobiti od svojih dobavljača do 600 m2 ploča mjesečno i pribora u vrijednosti od 2.000 USD. Za svaki ormar potrebno je 7 sati rada mašine, a za sto 3 sata. Mjesečno se može iskoristiti ukupno 840 radnih sati mašine.

Koliko kombinovanih ormara i kompjuterskih stolova kompanija treba da proizvede mesečno da bi povećala profit ako jedan ormar donosi 100 dolara profita, a svaki sto donosi 50 dolara?

• 1. Compose matematički model problem i riješi ga jednostavnim metodom.
• 2. Napravite matematički model dualnog problema, zapišite njegovo rješenje na osnovu rješenja originalnog.
• 3. Utvrditi stepen oskudice korišćenih resursa i opravdati isplativost optimalnog plana.
• 4. Istražiti mogućnosti daljeg povećanja proizvodnje u zavisnosti od upotrebe svake vrste resursa.
• 5. Procijeniti izvodljivost uvođenja nove vrste proizvoda – police za knjige, ako izrada jedne police košta 1 m 2 daske i pribora u vrijednosti od 5$, a potrebno je utrošiti 0,25 sati rada mašine i dobit od prodaje jedna polica je 20 dolara.
• 1. Napravimo matematički model za ovaj problem:

Označimo sa x 1 obim proizvodnje ormara, a x 2 obim proizvodnje stolova. Kreirajmo sistem ograničenja i funkciju cilja:

Zadatak rješavamo simpleks metodom. Zapišimo to u kanonskom obliku:

Zapišimo podatke zadatka u obliku tabele:

Tabela 1

Jer Sada su sve delte veće od nule, onda je dalje povećanje vrijednosti funkcije cilja f nemoguće i dobili smo optimalan plan.

KONTROLNI RAD NA DISCIPLINI:

“METODE OPTIMALNIH REŠENJA”

Opcija br. 8

1. Odluči se grafička metoda problem linearnog programiranja. Pronađite maksimum i minimum funkcije sa datim ograničenjima:

,

.

Rješenje

Potrebno je pronaći minimalnu vrijednost funkcije cilja i maksimum, pod sistemom ograničenja:

9x 1 +3x 2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

Konstruirajmo područje izvodljivih rješenja, tj. Rešimo sistem nejednačina grafički. Da bismo to učinili, konstruiramo svaku pravu liniju i definiramo poluravnine definirane nejednačinama (poluravnine su označene prostim brojem).

Presek poluravni će biti oblast čije koordinate tačaka zadovoljavaju nejednakosti sistema ograničenja problema. Označimo granice površine poligona rješenja.

Konstruirajmo pravu liniju koja odgovara vrijednosti funkcije F = 0: F = 2x 1 +3x 2 = 0. Vektor gradijenta, sastavljen od koeficijenata funkcije cilja, pokazuje smjer minimizacije F(X). Početak vektora je tačka (0; 0), kraj je tačka (2; 3). Pomeraćemo ovu pravu liniju na paralelan način. Budući da nas zanima minimalno rješenje, pomičemo pravu liniju sve dok ona ne dodirne označenu oblast. Na grafikonu je ova prava linija označena isprekidanom linijom.

Pravo
siječe područje u tački C. Pošto je tačka C dobijena kao rezultat preseka pravih (4) i (1), njene koordinate zadovoljavaju jednačine ovih pravih:
.

Nakon što smo riješili sistem jednačina, dobijamo: x 1 = 3,3333, x 2 = 0.

Kako možemo pronaći minimalnu vrijednost ciljne funkcije: .

Hajde da razmotrimo ciljna funkcija zadataka.

Konstruirajmo pravu liniju koja odgovara vrijednosti funkcije F = 0: F = 2x 1 +3x 2 = 0. Vektor gradijenta, sastavljen od koeficijenata funkcije cilja, pokazuje smjer maksimizacije F(X). Početak vektora je tačka (0; 0), kraj je tačka (2; 3). Pomeraćemo ovu pravu liniju na paralelan način. Pošto nas zanima maksimalno rješenje, pomičemo pravu liniju do posljednjeg dodira označenog područja. Na grafikonu je ova prava linija označena isprekidanom linijom.

Pravo
seče područje u tački B. Pošto je tačka B dobijena kao rezultat preseka pravih (2) i (3), njene koordinate zadovoljavaju jednačine ovih pravih:

.

Kako možemo pronaći maksimalnu vrijednost ciljne funkcije: .

odgovor:
I
.

2 . Riješite problem linearnog programiranja korištenjem simpleks metode:

.

Rješenje

Rešimo problem direktnog linearnog programiranja koristeći simpleks metodu, koristeći simpleks tablicu.

Odredimo minimalnu vrijednost funkcije cilja
pod sledećim uslovima-ograničenjima:
.

Da bismo konstruirali prvi referentni plan, sistem nejednačina svodimo na sistem jednačina uvođenjem dodatnih varijabli.

U 1. nejednakosti značenja (≥) uvodimo osnovnu varijablu x 3 sa znakom minus. U 2. nejednakosti značenja (≤) uvodimo osnovnu varijablu x 4 . U 3. nejednakosti značenja (≤) uvodimo osnovnu varijablu x 5 .

Hajde da uvedemo veštačke varijable : u 1. jednakosti uvodimo varijablu x 6 ;

Da bismo problem postavili na minimum, zapisujemo funkciju cilja na sljedeći način: .

Za korištenje umjetnih varijabli uvedenih u funkciju cilja, izriče se takozvana kazna M, vrlo veliki pozitivan broj koji se obično ne specificira.

Rezultirajuća osnova se naziva umjetna, a metoda rješenja naziva se metoda umjetne baze.

Štoviše, umjetne varijable nisu povezane sa sadržajem problema, ali omogućavaju konstruiranje početne točke, a proces optimizacije prisiljava ove varijable da uzmu nulte vrijednosti i osiguravaju prihvatljivost optimalnog rješenja.

Iz jednačina izražavamo umjetne varijable: x 6 = 4-x 1 -x 2 +x 3, koje zamjenjujemo u ciljnu funkciju: ili.

Matrica koeficijenata
ovaj sistem jednačina ima oblik:
.

Rešimo sistem jednačina za osnovne varijable: x 6 , x 4 , x 5.

Uz pretpostavku da su slobodne varijable jednake 0, dobijamo prvu referentni plan:

X1 = (0,0,0,2,10,4)

Osnovno rješenje se naziva dopuštenim ako nije negativno.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Trenutni referentni plan nije optimalan jer u indeksnoj liniji postoje pozitivni koeficijenti. Kao vodeći stupac izabraćemo kolonu koja odgovara varijabli x 2, jer je to najveći koeficijent. Izračunajmo vrijednosti D i a od njih biramo najmanji: min(4:1, 2:2, 10:2) = 1.

Dakle, 2. red je vodeći.

Element za razrješenje je jednak (2) i nalazi se na sjecištu vodeće kolone i vodećeg reda.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Formiramo sljedeći dio tabele simpleksa. Umjesto varijable x 4, plan 1 će uključivati ​​varijablu x 2.

Red koji odgovara varijabli x 2 u planu 1 dobija se dijeljenjem svih elemenata reda x 4 plana 0 sa elementom za razrješenje RE = 2. Umjesto elementa za razrješenje dobijamo 1. U preostale ćelije kolone x 2 upisujemo nule.

Tako se u novom planu 1 popunjavaju red x 2 i kolona x 2. Svi ostali elementi novog plana 1, uključujući elemente indeksnog reda, određeni su pravilom pravokutnika.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1/2 +1 1/2 M

Trenutni referentni plan nije optimalan jer u indeksnom redu postoje pozitivni koeficijenti. Kao vodeći stupac izabraćemo kolonu koja odgovara varijabli x 1, jer je to najveći koeficijent. Izračunajmo vrijednosti D i po redu kao količnik dijeljenja: a od njih biramo najmanji: min (3: 1 1 / 2, -, 8: 2) = 2.

Dakle, 1. red je vodeći.

Element za razlučivanje jednak je (1 1/2) i nalazi se na raskrsnici vodeće kolone i vodećeg reda.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 M

Formiramo sljedeći dio tabele simpleksa. Umjesto varijable x 6, plan 2 će uključivati ​​varijablu x 1.

Dobijamo novu simpleks tabelu:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Među vrijednostima niza indeksa nema pozitivnih vrijednosti. Stoga ova tabela određuje optimalni plan za problem.

Konačna verzija simpleks tablice:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Budući da u optimalnom rješenju nema umjetnih varijabli (jednake su nuli), ovo rješenje je dopušteno.

Optimalni plan se može napisati na sljedeći način: x 1 = 2, x 2 = 2:.

Odgovori:
,
.

3. Kompanija Tri debela isporučuje mesne konzerve iz tri skladišta koja se nalaze u različitim delovima grada u tri prodavnice. Zalihe konzervirane hrane dostupne u skladištima, kao i količine narudžbi iz trgovine i cijene isporuke (u konvencionalnim novčanim jedinicama) prikazane su u transportnoj tabeli.

Pronađite plan transporta koji pruža najniže novčane troškove (izvršite početni plan transporta metodom „sjeverozapadnog ugla“).

Rješenje

Provjerimo neophodan i dovoljan uslov za rješivost problema:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Uslov ravnoteže je ispunjen. Isporučuje jednake potrebe. Stoga je model transportnog problema zatvoren.

Unesimo početne podatke u tabelu distribucije.

Potrebe

Koristeći metodu sjeverozapadnog ugla, napravićemo prvi referentni plan transportnog problema.

Plan se počinje popunjavati iz gornjeg lijevog ugla.

Traženi element je 4. Za ovaj element zalihe su 300, zahtjevi su 250. Pošto je minimum 250, oduzimamo ga: .

			300 - 250 = 50
250 - 250 = 0

Traženi element je jednak 2. Za ovaj element zalihe su 50, zahtjevi su 400. Pošto je minimum 50, oduzimamo ga: .

			50 - 50 = 0
	400 - 50 = 350

Traženi element je 5. Za ovaj element zalihe su 300, zahtjevi su 350. Pošto je minimum 300, oduzimamo ga:

			300 - 300 = 0
	350 - 300 = 50

Element koji tražite je 3. Za ovaj element zalihe su 200, zahtjevi su 50. Pošto je minimum 50, oduzimamo ga:

			200 - 50 = 150
	50 - 50 = 0

Traženi element je 6. Za ovaj element zalihe su 150, zahtjevi su 150. Pošto je minimum 150, oduzimamo ga:

			150 - 150 = 0
		150 - 150 = 0

Potrebe

Laboratorijski rad br. 1. Rješavanje zadataka linearnog programiranja

Cilj rada Sticanje vještina rješavanja problema linearnog programiranja korištenjem grafičkih, simpleks i Excel metoda.

Problem linearnog programiranja je proučavanje načina za pronalaženje maksimalnih ili minimalnih vrijednosti linearne funkcije u prisustvu linearnih ograničenja. Ciljna funkcija je funkcija čija je najveća ili minimalna vrijednost pronađena. Skup vrijednosti varijabli kod kojih se postižu maksimalne ili minimalne vrijednosti naziva se optimalno rješenje (optimalni plan), svaki drugi skup vrijednosti koji zadovoljava ograničenja naziva se dopušteno rješenje (dopustivi plan).

Metoda geometrijskog rješenja I Pogledajmo probleme linearnog programiranja koristeći primjer.

Primjer. Pronađite maksimalnu vrijednost funkcije cilja L=2x 1 +2x 2 pod datim ograničenjima

Rješenje. Konstruirajmo domen rješenja sistema ograničenja, mijenjajući predznake nejednakosti u tačne znake jednakosti:

l 1: 3x 1 -2x 2 +6=0,

l 2: 3x 1 +x 2 -3=0,

l 3:x 1 -3=0.

DWITH

2 0 1 3 X 1

(l 1) (l 3)

Pravo l 1 dijeli ravan X O at u dvije poluravnine, od kojih treba izabrati onu koja zadovoljava prvu nejednakost u sistemu (3). Da bismo to učinili, uzmimo t. O(0; 0) i zamijenite ga u nejednakosti. Ako je to tačno, onda morate zasjeniti poluravninu od prave linije u kojoj se nalazi tzv. O(0; 0). Uradite isto sa ravnim linijama. l 2 i l 3. Područje rješenja nejednačina (3) je poligon ABCD. Za svaku tačku na ravni funkcija L uzima fiksnu vrijednost L=L 1 . Skup svih trenutnih tačaka je prava linija L=c 1 x 1 +c 2 x 2 (u našem slučaju L=2x 1 +2x 2), okomito na vektor WITH(With 1 ;With 2) (WITH(2; 2)), dolazi iz porijekla. Ako se ova linija pomakne u pozitivnom smjeru vektora With, zatim ciljnu funkciju Lće se povećati, inače će se smanjiti. Dakle, u našem slučaju, prava linija na izlazu iz poligona ABCD odluke će ići kroz tzv IN(3; 7,5), te stoga uklj. IN ciljna funkcija uzima maksimalnu vrijednost, tj. L max =2ּ3+2ּ7,5=21. Slično, utvrđuje se da je minimalna vrijednost koju funkcija zauzima D(1; 0) i L min =2ּ1+2ּ0=2.

Algoritam simpleks metode za rješavanje problema linearnog programiranja je sljedeći.

1. Opšti zadatak Linearno programiranje se svodi na kanonski problem (ograničenja sadrže predznake jednakosti) uvođenjem onoliko pomoćnih varijabli koliko ima nejednakosti u sistemu ograničenja.

2. Funkcija cilja se izražava kroz osnovne i pomoćne varijable.

3. Prva simpleks tabela je sastavljena. Promenljive u odnosu na koje je dozvoljen sistem ograničenja upisuju se u bazu (najbolje je uzeti pomoćne varijable kao osnovne). Prvi red tabele navodi sve varijable i pruža kolonu za slobodne termine. Koeficijenti funkcije cilja sa suprotnim predznacima upisani su u zadnji red tabele

4. Svaka simpleks tabela daje rešenje za problem linearnog programiranja: slobodne varijable su jednake nuli, osnovne varijable su jednake slobodnim terminima, respektivno.

5. Kriterijum optimalnosti je odsustvo negativnih elemenata u poslednjem redu tabele za rešavanje maksimalnog problema i pozitivnih elemenata za minimum.

6. Za poboljšanje rješenja potrebno je prijeći s jedne simpleks tablice na drugu. Da biste to uradili, pronađite ključnu kolonu u prethodnoj tabeli koja odgovara najmanjem negativnom elementu u poslednjem redu tabele u maksimalnom problemu i najvećem pozitivnom koeficijentu u minimalnom problemu. Zatim se pronađe ključni red koji odgovara minimalnom omjeru slobodnih pojmova prema odgovarajućim pozitivnim elementima ključnog stupca. Na raskrsnici ključne kolone i ključnog reda nalazi se ključni element.

7. Popunjavamo sledeću simpleks tabelu popunjavanjem osnove: varijabla koja odgovara ključnom redu se izvodi iz baze, a na njeno mesto se upisuje varijabla koja odgovara ključnoj koloni. Elementi prethodnog ključnog niza se dobijaju dijeljenjem prethodnog elementa sa ključnim. Elementi prethodnog ključnog stupca postaju nule, osim ključnog elementa, koji je jedan. Svi ostali elementi se izračunavaju pomoću pravila pravokutnika:

8. Transformacija simpleks tablica se vrši dok se ne dobije optimalan plan.

Primjer. Pronađite maksimalnu vrijednost funkcije
, ako su varijable
zadovoljiti sistem ograničenja:

Rješenje. 1. Uvesti nove varijable
, uz pomoć kojih transformišemo nejednakosti sistema u jednačine:

Mijenjamo predznak koeficijenata ciljne funkcije ili ga zapisujemo u obliku
. Popunjavamo prvu simpleks tabelu, u nulti red upisujemo X 1 ,X 2 i (besplatne kvote). U nultom stupcu - X 3 ,X 4 ,X 5 i F. Ovu tabelu popunjavamo koristeći rezultujući sistem jednačina i transformisanu funkciju cilja.

Provjeravamo kriterij optimalnosti da bismo pronašli maksimalnu vrijednost: u posljednjem redu svi koeficijenti moraju biti pozitivni. Ovaj kriterijum nije ispunjen, pa prelazimo na sastavljanje druge tabele.

2. Pronađite razrješavajući element prve tablice kako slijedi. Među elementima posljednjeg reda biramo najveći negativni koeficijent po veličini (ovo je -3) i uzimamo drugi stupac kao razrješavajući. Ako su svi koeficijenti kolone nepozitivni, onda
.

Da bismo odredili red za razrješenje, dijelimo slobodne koeficijente na odgovarajuće elemente kolone za rješavanje i biramo minimalni omjer, a negativne koeficijente ne uzimamo. Imamo
, drugi red je dopušten. Presjek reda i stupca za razrješenje daje element za razrješenje - to je 3.

3. Popunite drugu simpleks tabelu. Promjenljive na čijem presjeku dobijamo razlučujući element se zamjenjuju, tj. I . Razlučujući element zamjenjujemo njegovim inverznim, tj. na. Elementi reda i stupca za razrješenje (osim elementa za razrješenje) podijeljeni su na element za razrješenje. U ovom slučaju mijenjamo predznak koeficijenata stupca rezolucije.

Preostali elementi druge tabele dobijaju se pomoću pravila pravokutnika iz elemenata prve tabele. Za ćeliju koju treba popuniti i ćeliju sa elementom za razrješenje, pravimo pravougaonik. Zatim, od elementa za ćeliju koju treba popuniti, oduzimamo proizvod elemenata druga dva vrha, podijeljen sa elementom za razrješenje. Hajde da prikažemo proračune koristeći ovo pravilo za popunjavanje prvog reda druge tabele:

.

Nastavljamo sa popunjavanjem tabela prema ovim pravilima dok se ne ispuni kriterij. Imamo još dva stola za naš zadatak.

	X 1	X 4					X 3	X 2
X 3						X 1
X 2						X 2
X 5						X 5

4. Rezultat izvršavanja ovog algoritma je zapisan na sljedeći način. U finalnoj tabeli, element na raskrsnici reda
i kolona b, daje maksimalnu vrijednost ciljne funkcije. U našem slučaju
. Vrijednosti varijabli reda jednake su slobodnim koeficijentima. Za naš problem imamo
.

Postoje i drugi načini za sastavljanje i popunjavanje simpleks tabela. Na primjer, za fazu 1, sve varijable i slobodni koeficijenti se zapisuju u nulti red tabele. Nakon što smo pronašli element za razrješenje koristeći ista pravila u sljedećoj tabeli, zamjenjujemo varijablu u nultom stupcu, ali ne i u redu. Podijelimo sve elemente dopuštajuće linije dopuštajućim elementom i upišemo ih u novu tablicu. Za preostale elemente kolone rezolucije pišemo nule. Zatim izvodimo navedeni algoritam uzimajući u obzir ova pravila.

Prilikom rješavanja problema linearnog programiranja za minimum, najveći pozitivni koeficijent se bira u posljednjem redu, a navedeni algoritam se izvodi sve dok u posljednjem redu nema pozitivnih koeficijenata.

Rješavanje problema linearnog programiranja pomoću Excela provodi se na sljedeći način.

Da biste riješili probleme linearnog programiranja, koristite dodatak za pretraživanje rješenja. Prvo morate biti sigurni da je ovaj dodatak prisutan na kartici Podaci u grupi Analiza (za 2003. pogledajte Alati). Ako nedostaje komanda Pronađi rješenje ili grupa Analiza, morate preuzeti ovaj dodatak.

Da biste to uradili, kliknite na Microsoft Office File (2010), a zatim kliknite na dugme Opcije programa Excel. U prozoru s opcijama programa Excel koji se pojavi odaberite okvir Dodaci na lijevoj strani. Na desnoj strani prozora, vrijednost polja Control treba postaviti na Excel dodatke, kliknite na dugme „Idi“ koje se nalazi pored ovog polja. U prozoru dodataka potvrdite izbor u polju za potvrdu pored opcije Pronađi rješenje i kliknite na OK. Tada možete raditi s instaliranim dodatkom Search for Solutions.

Prije nego što pozovete Search for a Solution, morate pripremiti podatke za rješavanje problema linearnog programiranja (iz matematičkog modela) na radnom listu:

1) Odredite ćelije u koje će se za to smjestiti rezultat rješenja; u prvi red upisujemo varijable i ciljnu funkciju. Ne popunjavamo drugi red (promjenjive ćelije) u ovim ćelijama dobićemo optimalan rezultat. U sljedeći red unesite podatke za funkciju cilja, a u sljedeće redove sistem ograničenja (koeficijenti za nepoznate). Desna strana Uvode se ograničenja (slobodni koeficijenti), ostavljajući slobodnu ćeliju nakon snimanja koeficijenata sistema ograničenja.

2) Uvesti ovisnost o varijabilnim ćelijama za ciljnu funkciju i ovisnost o varijabilnim ćelijama za lijeve dijelove sistema ograničenja u preostalim slobodnim ćelijama. Za uvođenje formule zavisnosti, zgodno je koristiti matematičku funkciju SUMPRODUCT.

Zatim morate koristiti dodatak Traži rješenje. Na kartici Podaci, u grupi Analiza odaberite Pronađi rješenje. Pojavit će se okvir za dijalog Traženje rješenja, koji se mora završiti na sljedeći način:

1) Navedite ćeliju koja sadrži funkciju cilja u polju „Optimiziraj funkciju cilja“ (ova ćelija mora sadržavati formulu za ciljnu funkciju). Odaberite opciju za optimizaciju vrijednosti ciljne ćelije (maksimizacija, minimizacija):

2) U polje “Promjena varijabilnih ćelija” unesite ćelije koje želite promijeniti. U sljedeće polje „U skladu sa ograničenjima“ unesite navedena ograničenja pomoću dugmeta „Dodaj“. U prozoru koji se pojavi unesite ćelije koje sadrže formule sistema ograničenja, odaberite znak ograničenja i vrijednost ograničenja (slobodni koeficijent):

3) Označite polje za potvrdu “Neograničene varijable nenegativne”. Odaberite metodu rješenja "Traženje rješenja za linearne probleme pomoću simpleks metode." Nakon klika na dugme „Pronađi rešenje“, počinje proces rešavanja problema. Kao rezultat, pojavljuje se dijaloški okvir "Rezultati pretraživanja rješenja" i originalna tablica s popunjenim ćelijama za varijabilne vrijednosti i optimalnu vrijednost funkcije cilja.

Primjer. Riješite problem linearnog programiranja pomoću dodatka za Excel rješenje: pronađite maksimalnu vrijednost funkcije
pod ograničenjima

,

;

,
.

Rješenje. Da bismo riješili naš problem, izvršimo navedeni algoritam na Excel radnom listu. Unesite početne podatke u obliku tabele

Uvodimo zavisnosti za funkciju cilja i sistem ograničenja. Da biste to učinili, unesite formulu =SUMPROIZVOD(A2:B2;A3:B3) u ćeliju C2. U ćelijama C4 i C5, respektivno, formule su: =SUMPROIZVOD(A2:B2,A4:B4) i =SUMPROIZVOD(A2:B2,A5:B5). Kao rezultat, dobijamo sto.

Pokrenite naredbu “Traži rješenje” i popunite prozor Traži rješenje koji se pojavljuje na sljedeći način. U polje "Optimiziraj funkciju cilja" unesite ćeliju C2. Odaberite optimizaciju vrijednosti ciljne ćelije “Maksimalno”.

U polje "Promjena varijabilnih ćelija" unesite promjenjive ćelije A2:B2. U polje „U skladu sa ograničenjima“ unesite navedena ograničenja pomoću dugmeta „Dodaj“. Reference na ćeliju $C$4:$C$5 Reference na ograničenja =$D$4:$D$5 između njih znak<= затем кнопку «ОК».

Označite potvrdni okvir “Neograničene varijable nenegativne”. Odaberite metodu rješenja "Traženje rješenja za linearne probleme pomoću simpleks metode."

Klikom na dugme „Pronađi rešenje“ započinje proces rešavanja problema. Kao rezultat, pojavljuje se dijaloški okvir "Rezultati pretraživanja rješenja" i originalna tablica s popunjenim ćelijama za varijabilne vrijednosti i optimalnu vrijednost funkcije cilja.

U dijaloškom okviru “Rezultati pretraživanja rješenja” sačuvajte rezultat x1=0,75, x2=0,75, F=1,5 - jednak maksimalnoj vrijednosti funkcije cilja.

Zadaci za samostalan rad

Vježba 1. Koristeći grafičke, simpleks metode i Excel alate, pronađite maksimalnu i minimalnu vrijednost funkcije F(x) pod datim sistemom ograničenja.

1. F(x)=10x 1 +5x 2 2. F(x)=3x 1 -2x 2

3. F(x)=3x 1 +5x 2 4. F(x)=3x 1 +3x 2

5. F(x)=4x 1 -3x 2 6. F(x)=2x 1 -x 2

7. F(x)=-2x 1 +4x 2 8. F(x)=4x 1 -3x 2

9. F(x)=5x 1 +10x 2 10. F(x)=2x 1 +x 2

11. F(x)=x 1 +x 2 12. F(x)=3x 1 +x 2

13. F(x)=4x 1 +5x 2 14. F(x)=3x 1 +2x 2

15. F(x)=-x 1 -x 2 16. F(x)=-3x 1 -5x 2

17. F(x)=2x 1 +3x 2 18. F(x)=4x 1 +3x 2

19. F(x)=-3x 1 -2x 2 20. F(x)=-3x 1 +4x 2

21. F(x)=5x 1 -2x 2 22. F(x)=-2x 1 +3x 3

23. F(x)=2x 1 +3x 2 24. F(x)=4x 1 +3x 2

25. F(x)=-3x 1 -2x 2 26. F(x)=-3x 1 +4x 2

27. F(x)=-2x 1 +4x 2 28. F(x)=4x 1 -3x 2

29. F(x)=-x 1 -x 2 30. F(x)=-3x 1 -5x 2

Kontrolna pitanja.

1. Koji se problemi nazivaju problemi linearnog programiranja?

2. Navedite primjere problema linearnog programiranja.

3. Kako se rješava problem linearnog programiranja korištenjem grafičke metode?

4. Opisati algoritam simpleks metode za rješavanje problema linearnog programiranja.

5. Opišite algoritam za rješavanje problema linearnog programiranja koristeći Excel.

Federalna agencija za obrazovanje

Državna budžetska obrazovna ustanova

visoko stručno obrazovanje

"Omski državni tehnički univerzitet"

RAČUNSKI I GRAFIČKI RAD

po disciplini"TEORIJA OPTIMALNOG UPRAVLJANJA »

na temu"METODE OPTIMIZACIJE I ISTRAŽIVANJE OPERACIJA »

opcija 7

Završeno:

dopisni student

Grupa 4. godine ZA-419

Puno ime: Kuzhelev S. A.

Provjereno:

Devyaterikova M. V.

Omsk – 2012
^

Zadatak 1. Grafička metoda za rješavanje problema linearnog programiranja.

7) 7x 1 + 6x 2 → maks 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

Korak 1: Izgradnja izvodljivog regiona

Uslovi za nenegativnost varijabli i kvadrata ograničavaju raspon njihovih dozvoljenih vrijednosti na prvi kvadrant. Svako od preostale četiri ograničenja nejednakosti modela odgovara određenoj poluravni. Presek ovih poluravnina sa prvim kvadrantom formira skup izvodljivih rešenja problema.

Prvo ograničenje modela ima oblik . Zamenivši u njemu znak ≤ znakom =, dobijamo jednačinu . Na sl. 1.1 definira pravu liniju (1), koja dijeli ravan na dvije poluravnine, u ovom slučaju iznad i ispod nje. Odabrati koji od njih zadovoljava nejednakost , zamijenite u njega koordinate bilo koje tačke koja ne leži na datoj pravoj (na primjer, ishodište X 1 = 0, X 2 = 0). Pošto smo dobili tačan izraz (20 0 + 6 0 = 0 ≤15), tada poluravnina koja sadrži početak koordinata (označena strelicom) zadovoljava nejednakost. Inače, još jedan poluravan.

Na sličan način postupamo s preostalim ograničenjima problema. Formira se presek svih konstruisanih poluravnina sa prvim kvadrantom A B C D(vidi sliku 1). Ovo je izvodljivo područje problema.

Korak 2. Crtanje linije nivoa Linija nivoa Funkcija cilja je skup tačaka u ravni u kojima funkcija cilja poprima konstantnu vrijednost. Takav skup je dat jednadžbom f ( x) = konst. Stavimo npr. konst = 0 i nacrtajte liniju na nivou f ( x) = 0, tj. u našem slučaju prava linija 7 x 1 + 6x 2 = 0.

Ova linija prolazi kroz ishodište i okomita je na vektor. Ovaj vektor je gradijent funkcije cilja u tački (0,0). Gradijent funkcije je vektor vrijednosti parcijalnih izvoda date funkcije u točki o kojoj je riječ. U slučaju LP problema, parcijalni izvod funkcije cilja jednaki su koeficijentima Cja, j = 1 , ..., n.

Gradijent pokazuje smjer najbržeg rasta funkcije. Pomicanje linije razine ciljne funkcije f ( x) = konst. okomito na smjer gradijenta, nalazimo posljednju tačku u kojoj se on siječe sa regijom. U našem slučaju, ovo je tačka D, koja će biti maksimalna tačka funkcije cilja (vidi sliku 2)

Leži na presjeku linija (2) i (3) (vidi sliku 1) i specificira optimalno rješenje.

^ Imajte na umu da ako želite pronaći minimalnu vrijednost funkcije cilja, linija nivoa se pomiče u smjeru suprotnom od smjera gradijenta.

^ Korak 3. Određivanje koordinata maksimalne (minimalne) tačke i optimalne vrijednosti funkcije cilja

Da biste pronašli koordinate tačke C, potrebno je riješiti sistem koji se sastoji od jednadžbi koje odgovaraju pravim linijama (u ovom slučaju jednačine 2 i 3):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Dobijamo optimalno rješenje = 1,33.

^ Optimalna vrijednost funkcije cilja f * = f (X*) = 7 * 0 + 6 * 1,33 = 7,8