Simplex metoda jednostavan je primjer rješenja. Riješite problem linearnog programiranja simpleks metodom

Ako ste već shvatili grafičku metodu za rješavanje problema linearnog programiranja, vrijeme je da prijeđete na simpleks metoda... Za razliku od prvog, on praktično nema ograničenja za zadatak (bilo koji broj varijabli, različite znakove itd.) i mijenja se ovisno o vrsti problema (na primjer, M-metoda ili metoda umjetne osnove).

Prilikom rješavanja problema pomoću simpleks metode, proračuni se obično izvode (radi kompaktnosti i jasnoće) u tablicama (tabelarna simpleks metoda), a posljednja tablica s optimalnim rješenjem sadrži važne dodatne informacije: rješenje dvostrukog problema, bilance resursa , informacije o oskudnim resursima itd., što nam omogućava da provedemo ekonomsku analizu problema linearnog programiranja (vidi primjer 3 ispod).

Primjeri rješavanja problema simpleks metodom izlažu se besplatno radi vaše udobnosti - proučite, tražite slične, riješite. Ako vam je potrebna pomoć oko ovih vrsta zadataka, idite na: Prilagođeno rješenje za linearno programiranje.

Rješavanje problema simpleks metodom: mrežni primjeri

Cilj 1. Kompanija proizvodi police za kupaonice u dvije veličine - A i B. Prodajni zastupnici procjenjuju da se na tržištu može prodati do 550 polica tjedno. Za svaku policu tipa A potrebno je 2 m2 materijala, a za policu tipa B potrebno je 3 m2 materijala. Kompanija može primiti do 1200 m2 materijala sedmično. Za proizvodnju jedne police tipa A potrebno je 12 minuta mašinskog vremena, a za proizvodnju jedne police tipa B - 30 minuta; mašina se može koristiti 160 sati sedmično. Ako je prihod od prodaje polica tipa A 3 novčane jedinice, a od prodaje polica tipa B - 4 den. jedinica, koliko onda polica svake vrste treba proizvesti sedmično?

Sastavljanje matematičkog modela i rješenja LPP -a simpleks metodom (pdf, 33 Kb)

Cilj 2. Riješite problem linearnog programiranja simpleks metodom.

Simplex rješenje na umjetnoj osnovi (pdf, 45 Kb)

Cilj 3. Preduzeće proizvodi 3 vrste proizvoda: A1, A2, A3, koristeći dvije vrste sirovina. Poznati su troškovi sirovina svake vrste po jedinici proizvodnje, zalihe sirovina za planirani period, kao i prihod od jedinice proizvodnje svake vrste.

1. Koliko proizvoda svake vrste mora biti proizvedeno kako bi se postigao maksimalni profit?
2. Odredite status svake vrste sirovine i njenu specifičnu vrijednost.
3. Utvrditi maksimalni interval promjena zaliha svake vrste sirovine, unutar kojeg je struktura optimalnog plana, tj. nomenklatura pitanja se neće promijeniti.
4. Odredite količinu proizvoda i dobit od puštanja u promet povećanjem zaliha jedne od rijetkih vrsta sirovina do najveće moguće (u granicama date nomenklature proizvodnje) vrijednosti.
5. Odredite intervale promjene dobiti od jedinice proizvodnje svake vrste, u kojima se rezultirajući optimalni plan neće promijeniti.

Rješavanje problema linearnog programiranja sa ekonomska analiza(pdf, 163 Kb)

Zadatak 4. Riješite problem linearnog programiranja simpleks metodom:

Rješavanje tabelarnom simpleks metodom s osnovnim pretraživanjem (pdf, 44 Kb)

Zadatak 5. Riješite problem linearnog programiranja simpleks metodom:

Rješavanje tabelarnom simpleks metodom (pdf, 47 Kb)

Zadatak 6. Riješite problem koristeći simpleks metodu, uzimajući u obzir plan dat u stanju kao početni referentni plan:

Ručno simpleks rješenje (pdf, 60 Kb)

Zadatak 7. Riješite problem korištenjem modificirane simpleks metode.
Za proizvodnju dvije vrste proizvoda A i B koriste se tri vrste tehnološke opreme. Za proizvodnju jedinice proizvoda A koristi se oprema prvog tipa a1 = 4 sata, oprema drugog tipa, a2 = 8 sati i oprema trećeg tipa, a3 = 9 sati. Za proizvodnju jedinice proizvoda B koristi se oprema prvog tipa b1 = 7 sati, oprema drugog tipa, b2 = 3 sata i oprema trećeg tipa, b3 = 5 sati.
Za proizvodnju ovih proizvoda oprema prvog tipa može raditi najviše t1 = 49 sati, oprema drugog tipa ne više od t2 = 51 sati, oprema trećeg tipa ne više od t3 = 45 sati.
Dobit od prodaje jedinice gotovog proizvoda A iznosi ALFA = 6 rubalja, a za proizvod B - BETTA = 5 rubalja.
Napravite plan proizvodnje proizvoda A i B, osiguravajući maksimalnu dobit od njihove prodaje.

Rješenje modifikovanom simpleks metodom (pdf, 67 Kb)

Zadatak 8. Naći optimalno rešenje dual simplex metoda

Rješenje metodom dual simpleksa (pdf, 43 Kb)

Primjeri rješavanja problema linearnog programiranja

Metode rješavanja problema linearnog programiranja

Podrška rješenja problema linearnog programiranja

Neka je problem linearnog programiranja dat u kanonskom zapisu

pod uslovima

Označit ćemo skupom rješenja sistema (2) - (3). Pretpostavimo da je, gdje je rang matrice, broj jednadžbi u sistemu (2).

Iz sistema kolonastih vektora matrice biramo neki linearno nezavisni podsistem vektora. Postoji zato što. Ovaj sistem čini osnovu u. Označimo sa ,. Nazovimo skup osnovnih vrijednosti indeks, - bazna podmatrica matrice. Pozvat će se koordinate vektora osnovni , ako i neosnovno u suprotnom.

Napišemo sistem (2) u obliku. Podijelili smo pojmove s lijeve strane na osnovne i neosnove

Definirajmo posebno rješenje ovog sistema na sljedeći način. Sve neosnovne varijable stavljamo u (4) jednake nuli. Tada sistem (4) poprima oblik

Nazovimo (5) osnovni podsistem sistem jednadžbi (2). Označimo vektorom koji se sastoji od osnovnih koordinata vektora. Tada se sistem (2) može prepisati u vektorsko-matrični oblik

Pošto je podmatrica osnovna, to je

ne-degenerisan. Dakle, sistem (6) ima jedina odluka... Ovako dobiveno posebno rješenje sistema (2) naziva se referentna odluka problem direktnog linearnog programiranja koji odgovara bazi. (Ponekad se naziva i referentno rješenje osnovni ). Kao što vidite, osnova odgovara jedinom rješenju za podršku. Očigledno je da je broj rješenja za podršku konačan.

Za ovu osnovu definiramo i rješenje za podršku problema dualnog linearnog programiranja. Podsjetimo da dvostruki problem u odnosu na kanonski ima oblik

pod uslovima

Sistem (8) pišemo u obliku

Podsjetimo da je skup rješenja sistema (8) označen sa.

Definirajmo vektor dualnih varijabli iz uvjeta ispunjenosti osnovnih ograničenja u sistemu (9) kao jednakosti. Dobijamo sledeći sistem linearne jednadžbe:

Označavamo vektorom sastavljenim od ba-

vektorske koordinate. Tada se sistem (10) može prepisati u vektorsko-matrični oblik

Sistem (11) također ima jedinstveno rješenje.

Nazovimo to podržavajući (osnovni )odluku problema dualnog linearnog programiranja koji odgovara bazi. Ovo referentno rješenje je također jedinstveno određeno.

Dakle, bilo kojoj bazi odgovaraju dva vektora - dva rješenja za podršku i problemi direktnog i dualnog linearnog programiranja.

Definirajmo dalje sljedeće vrste baza i rješenja podrške. Ako su sve koordinate rješenja za podršku negativne, tada se poziva osnova kojoj ovo rješenje za podršku odgovara prihvatljivo osnovica problem direktnog linearnog programiranja, a naziva se i rješenje za podršku koje odgovara istoj bazi pseudo plan dvostruki zadatak. U stvari, za prihvatljivost osnove dovoljna je nenegativnost osnovnih koordinata. Imajte na umu da je osnovni plan dopušteni vektor problema direktnog linearnog programiranja ().

Ako rješenje za podršku zadovoljava sva ograničenja (9) dualnog problema, tada se osnova kojoj odgovara ovo rješenje za podršku naziva dvostruko dozvoljeno ... U ovom slučaju, vektor se poziva osnovica problem dvostrukog linearnog programiranja i rješenje podrške koje odgovara istoj bazi

pozvao pseudo plan direktan zadatak.

Za dvostruku prihvatljivost osnove dovoljno je zadovoljiti samo neosnovne nejednakosti. Primijetite da je osnovna linija prihvatljivi vektor problema dualnog linearnog programiranja ().

Razlike između lijeve i desne strane nejednakosti (9) označit ćemo sa ,. Tada se dvostruka prihvatljivost osnove može utvrditi provjerom nenegativnosti svih. Imajte na umu da su, kako izravno slijedi iz definicije, svi osnovni zaostaci jednaki nuli ().

Primjer rješavanja direktnih i dualnih problema simpleks metodom

Stoga je dovoljno osigurati da nejednakosti vrijede za sve.

Teorem 1. Neka budei- podrška rješenjima problema linearnog programiranja koji odgovaraju nekoj osnovi, zatim jednakost .

Dokaz . Iz definicija rješenja za podršku lako je doći do jednakosti

odakle slijedi valjanost teoreme.

Teorema 2. (Kriterij optimalnosti rješenja za podršku) Ako je osnovasu istovremeno dopuštene i dvostruko prihvatljive, tada odgovarajuća rješenja podrškeisu rješenja za direktne i dualne probleme linearnog programiranja.

Dokaz. Valjanost ove izjave proizlazi iz teorije dualnosti u linearnom programiranju i Teorema 1.

Teorema 3. Izvodljivo rješenje problema (1) - (3) osnovni je plan problema ako i samo ako je to vrh konveksnog poliedarskog skupa.

Dokaz. Neka bude - osnovni plan problema (1) - (3). Dokažimo to - vrh seta . Po definiciji, osnovni plan – dopušteno rješenje podrške koje odgovara nekoj osnovi, tj – rješenje sistema linearnih jednadžbi u varijablama

Lako je vidjeti da ovaj sistem ima samo jedno rješenje. Dakle, nosiva ravnina lica koja sadrži točku , ima dimenziju 0. Slijedom toga, - vrh seta .

Nazad. Neka bude - vrh seta. Dokažimo to - osnovni plan problema (1) - (3). Budući da je to vrh, to je lice skupa čija je dimenzija jednaka nuli. Dakle, vektor postoji najmanje nula komponenti čiji skup brojeva označavamo . Dakle, – jedino rešenje sistema

gdje . Stoga ostaje da se dokaže da je sistem vektora linearno nezavisan. Pretpostavimo suprotno. Zatim postoje brojevi koji nisu svi jednaki nuli, tako da. dakle

To znači da sistem (12) ima rješenje različito od , što je u suprotnosti sa jedinstvenošću njegovog rješenja. Dakle, osnova je i vektor - odgovarajući osnovni plan problema (1) - (3). Što je bilo potrebno.

Imajte na umu da je dopušteno rješenje problema (7), (8) (dualno problemu (1) - (3)) također plan podrške ako i samo ako je to vrh dopuštenog skupa.

Datum objavljivanja: 2015-01-10; Pročitajte: 695 | Kršenje autorskih prava na stranici

Studopedia.org - Studopedia.Org - 2014-2018. (0,005 s) ...

Radi definitivnosti, pretpostavljamo da se problem pronalaženja minimuma rješava.

1. Svedite problem linearnog programiranja na kanonski oblik.

Nakon uvođenja dodatnih varijabli, sustav jednadžbi i linearnu funkciju zapisujemo u obliku koji se naziva prošireni sistem:

Pretpostavljamo da sve dodatne varijable imaju isti predznak kao slobodni članovi; u suprotnom, koristimo tzv M- metoda o kojoj će biti riječi u nastavku.

2. Odredite osnovne i slobodne varijable.

3. Početni prošireni sistem se unosi u prvu simpleks tablicu. Naziva se posljednji red tablice u kojem je dana jednadžba za linearnu funkciju cilja evaluative... Određuje koeficijente ciljne funkcije. U lijevi stupac tablice zapisujemo glavne varijable (osnovu), u nastavku - koeficijente za slobodne varijable. Pretposljednja kolona sadrži besplatne članove proširenog sistema. Posljednja kolona pripremljena je za evaluacijske odnose potrebne za određivanje osnovne varijable na osnovu odnosa (6.29).

4. Odrediti mogućnost rješavanja problema vrijednostima prema teoremama 6.7,…, 6.9.

5. Odaberite rješavajući (podržavajući) element.

Rješavanje proizvodnog problema pomoću tabelarne simpleks metode

Ako kriterij optimalnosti nije zadovoljen (uvjeti teorema 6.7 ili 6.8 nisu ispunjeni), tada najveći negativni koeficijent u apsolutnoj vrijednosti u posljednjem redu određuje rješavajući (potporni) stupac .

Procijenjene relacije za svaku liniju sastavljamo prema sljedećim pravilima:

1 0), ako svi imaju različite znakove;

2 0), ako su svi i;

3 0) ako;

4 0) 0, ako i;

5 0), ako i imaju iste znakove.

Definirajmo. Ako ne postoji konačni minimum, onda problem nema konačni optimum (). Ako je minimum konačan, odaberite liniju q, na kojem je dosegnut (bilo koji, ako ih ima više), i nazivamo ga rješavajući (referentni) niz. Na sjecištu dopuštenog reda i stupca nalazi se dopuštajući (zaokretni) element.

6 0) Idite na sljedeću tablicu prema pravilima:

a) u lijevu kolonu upisujemo novu osnovu: umjesto glavne varijable - varijabla, tj. zamijenimo varijable i;

b) postavite 1 na mjesto nosećeg elementa;

c) na preostalim mjestima referentne linije u novoj tabeli ostavite elemente originalne tabele;

d) postavite odgovarajuće elemente originalne tablice pomnožene s -1 na preostala mjesta u zaokretnoj koloni;

e) na preostala slobodna mjesta elemenata ,, u novoj tabeli upišite brojeve ,,, koji su sljedeći:

Kako bi se pojednostavili izračuni pomoću ovih formula, oni se mogu formulirati kao "Pravila pravokutnika"(Slika 6.8): elementi na dijagonalama pravokutnika s vrhovima (ili ,,,, ili ,,,) se množe (proizvod koji ne sadrži zaokretni element uzima se sa znakom minus) i dobiveni proizvodi se dodaju;

f) podijeliti sve primljene elemente nove tablice u zaokretni element.

7 0) Prema vrijednosti elementa odredite je li pronađena optimalna vrijednost funkcije cilja. U slučaju negativnog odgovora, nastavite s rješavanjem (vratite se na točku 6).

Pirinač. 6.8. Pravilo pravokutnika za definiranje brojeva:

a -, b -, c -.

Razmatra se algoritam za pretvaranje simpleksnih tablica za nedegenerirana dopuštena osnovna rješenja, tj. vrijedi situacija opisana teoremom 6.9. Ako je izvorni problem linearnog programiranja degeneriran, tada se tijekom njegovog rješavanja simpleks metodom mogu pojaviti degenerirana osnovna rješenja. U ovom slučaju mogući su koraci mirovanja simpleks metode, tj. iteracije gdje f(x) se ne mijenja. Moguće je i petlje, tj. beskonačan niz koraka u praznom hodu. Kako bi se to spriječilo, razvijeni su posebni algoritmi - anticikline. Međutim, u velikoj većini slučajeva, koraci u praznom hodu zamjenjuju se koracima sa smanjenjem funkcije cilja, a proces rješenja završava kao rezultat konačnog broja iteracija.

Primjer 6.8. Riješite problem u primjeru 6.7 koristeći simpleks metodu.

Prethodna45678910111213Iduća ⇒

Datum objavljivanja: 2015-01-23; Pročitajte: 174 | Kršenje autorskih prava na stranici

Studopedia.org - Studopedia.Org - 2014-2018. (0.002 s) ...

Početna >> Primjer №3. Simplex metoda. Pronalaženje najveće vrijednosti funkcije (umjetna osnova)

Simplex metoda

Među odabranim koeficijentima reda nema pozitivnih koeficijenata. Stoga se nalazi najveća vrijednost funkcije F.

Odgovor:

x 1 = 3 x 2 = 4

F max = 13

Idite na rješavanje svog problema

© 2010-2018, za sva pitanja pišite na adresu [zaštićena e -pošta]

Zadatak

Za prodaju tri grupe dobara, trgovačko preduzeće ima tri vrste ograničenih materijalnih i novčanih resursa u iznosu od b 1 = 240, b 2 = 200, b 3 = 160 jedinica. U isto vrijeme, za prodaju 1 grupe proizvoda za 1 hiljadu rubalja. promet se troši na resurs prve vrste u iznosu od 11 = 2 jedinice, resurs druge vrste u iznosu od 21 = 4 jedinice, resurs treće vrste u iznosu od 31 = 4 jedinice. Za prodaju 2 i 3 grupe robe za 1.000 rubalja. promet se troši, odnosno, na resurse prve vrste u iznosu od 12 = 3, a 13 = 6 jedinica, resurse druge vrste u iznosu od 22 = 2, a 23 = 4 jedinice, resurs treće vrste u iznosu od 32 = 6, a 33 = 8 jedinica ... Dobit od prodaje tri grupe robe za 1 hilj.

Simplex metoda za rješavanje LPP -a

trljati promet je, respektivno, c 1 = 4, c 2 = 5, c 3 = 4 (hiljade rubalja). Odredite planirani obim i strukturu prometa tako da profit trgovačkog preduzeća bude maksimalan.

Direktnom zadatku planiranja prometa, rješivo simpleks metodom, šminka dvostruki zadatak linearno programiranje.
Instaliraj konjugirani parovi varijabli direktni i dvostruki zadaci.
Prema konjugiranim parovima varijabli, iz rješenja direktnog problema, dobiti dvostruko rješenje problema u kojem procjena resursa potrošen na prodaju robe.

Rješavanje problema simpleks metodom

Neka x 1, x 2, x 3 - broj prodate robe, u hiljadama rubalja, 1, 2, 3 - njene grupe, respektivno. Tada matematički model problema ima oblik:

F = 4 x 1 + 5 x 2 + 4 x 3 -> max

Rješavamo simpleks metodu.

Uvedite dodatne varijable x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 za pretvaranje nejednakosti u jednakosti.

Uzmite x 4 = 240 kao osnovu; x 5 = 200; x 6 = 160.

Unosimo podatke u simplex table

Simplex tablica broj 1

Funkcija cilja:

0 240 + 0 200 + 0 160 = 0

Rezultate izračunavamo prema formuli:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Budući da postoje negativne ocjene, plan nije optimalan. Najniža ocjena:

Promenljivu x 2 uvodimo u bazu.

Definiramo varijablu koja napušta bazu. Da bismo to učinili, nalazimo najmanji negativni omjer za stupac x 2.

= 26.667

Najmanji negativan: Q 3 = 26,667. Izvodimo varijablu x 6 iz osnove

Podijelite treći red sa 6.
Od prvog retka oduzmite treći red, pomnožen sa 3
Od drugog retka oduzmite treći red pomnožen sa 2

Izračunavamo:

Dobijamo novu tabelu:

Simplex tablica broj 2

Funkcija cilja:

0 160 + 0 440/3 + 5 80/3 = 400/3

Rezultate izračunavamo prema formuli:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1) / 2 + 0 (-1) / 3 + 5 1/6-0 = 5/6

Budući da postoji negativna procjena Δ 1 = - 2/3, plan nije optimalan.

Promenljivu x 1 uvodimo u bazu.

Definiramo varijablu koja napušta osnovu. Da biste to učinili, pronađite najmanji negativni omjer za stupac x 1.

Najmanji negativan: Q 3 = 40. Iz baze izvodimo varijablu x 2

Podijelite 3. red za 2/3.
Od drugog reda oduzmite 3. red, pomnoženo sa 8/3

Izračunavamo:

Dobijamo novu tabelu:

Simplex tablica broj 3

Funkcija cilja:

0 160 + 0 40 + 4 40 = 160

Rezultate izračunavamo prema formuli:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1) / 2 + 0 (-1) + 4 1/4-0 = 1

Budući da nema negativnih ocjena, plan je optimalan.

Rešenje problema:

Odgovor

x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160

Odnosno, potrebno je prodati robu prve vrste u iznosu od 40 hiljada.

trljati Nije potrebno prodavati robu drugog i trećeg tipa. U ovom slučaju maksimalna dobit će biti F max = 160 hiljada rubalja.

Rješenje dvostrukog problema

Dvojni problem je:

Z = 240 y 1 + 200 y 2 + 160 y 3 -> min

Uvedite dodatne varijable y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 za pretvaranje nejednakosti u jednakosti.

Konjugirani parovi varijabli direktnog i dualnog problema imaju oblik:

Iz posljednjeg simpleksa tablice br. 3 izravnog problema nalazimo rješenje dvostrukog problema:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

Odgovor

y 1 = 0; y 2 = 0; y 3 = 1; Z min = 160;

Simplex metoda je računski postupak zasnovan na principu sukcesivnog poboljšanja rješenja pri prelasku s jedne osnovne tačke (osnovnog rješenja) na drugu. U tom slučaju vrijednost funkcije cilja se poboljšava.

Osnovno rješenje je jedno od mogućih rješenja koja se nalaze na vrhovima područja dopuštenih vrijednosti. Provjerom optimalnosti vrha po tjemenu simpleksa, dolazi se do željenog optimuma. Na ovom principu zasniva se simpleks metoda.

Simpleks je konveksni poligon u n-dimenzionalnom prostoru sa n + 1 vrhova koji ne leže u jednoj hiperravni (hiperravnina dijeli prostor na dva poluprostora).

Na primjer, linija budžetskih ograničenja dijeli robu na pristupačnu i nedostupnu.

Dokazano je da ako postoji optimalno rješenje, ono će se nužno naći nakon konačnog broja iteracija (koraka), osim u slučajevima "petlje".

Algoritam simpleks metode sastoji se od nekoliko faza.

Prva faza. Izgrađen je inicijalni model optimizacije. Nadalje, početna matrica uvjeta pretvara se u reducirani kanonički oblik, koji se ističe među svim ostalim kanonskim oblicima po tome što:

a) desne strane uvjeta (slobodni izrazi bi) su negativne veličine;

b) sami uslovi su jednaki;

c) matrica uslova sadrži potpunu jediničnu podmatricu.

Ako su slobodni članovi negativni, tada se obje strane nejednakosti množe sa - 1, a znak nejednakosti se mijenja. Za pretvaranje nejednakosti u jednakosti uvode se dodatne varijable koje obično označavaju količinu nedovoljno iskorištenih resursa. Ovo je njihov ekonomski smisao.

Konačno, ako nakon dodavanja dodatnih varijabli matrica uvjeta ne sadrži potpunu jediničnu podmatricu, tada se uvode umjetne varijable koje nemaju ekonomsko značenje. Uvode se isključivo radi dobivanja jedinične podmatrice i započinjanja procesa rješavanja problema pomoću simpleks metode.

U optimalnom rješenju problema, sve umjetne varijable (AI) trebale bi biti jednake nuli. Da bi se to učinilo, umjetne varijable se uvode u ciljnu funkciju problema s velikim negativnim koeficijentima (-M) pri rješavanju problema za max, te s velikim pozitivnim koeficijentima (+ M) kada se problem rješava na min. U ovom slučaju, čak i beznačajna vrijednost nulte vrijednosti umjetne varijable naglo će smanjiti (povećati) vrijednost funkcije cilja. Obično bi M trebao biti 1000 puta veći od vrijednosti koeficijenata za glavne varijable.

Druga faza. Konstruira se početna simpleks tablica i pronađeno je neko početno osnovno rješenje. Skup varijabli koje tvore jediničnu podmatricu uzima se kao početno osnovno rješenje. Vrijednosti ovih varijabli jednake su slobodnim članovima. Sve ostale varijable izvan baze su nule.

Treća faza. Osnovno rješenje testira se na optimalnost pomoću posebnih procjena koeficijenata ciljne funkcije. Ako su sve procjene koeficijenata funkcije cilja negativne ili jednake nuli, tada je dostupno osnovno rješenje optimalno. Ako je barem jedna procjena koeficijenta ciljne funkcije veća od nule, tada postojeće osnovno rješenje nije optimalno i mora se poboljšati.

Četvrta faza. Prelazak na novo osnovno rješenje. Očigledno, optimalni plan trebao bi uključivati ​​takvu varijablu koja u najvećoj mjeri povećava ciljnu funkciju. Pri rješavanju problema radi postizanja najvećeg profita, optimalni plan uvodi proizvode čija je proizvodnja najisplativija. To je određeno najvećom pozitivnom vrijednošću procjene koeficijenta ciljne funkcije.

Stupac simplex tablice s ovim brojem na ovoj iteraciji naziva se opća kolona.

Da biste pronašli opći red, svi besplatni članovi (resursi) podijeljeni su u odgovarajuće elemente opće kolone (stopa potrošnje resursa po jedinici proizvoda). Od dobivenih rezultata bira se najmanji. Odgovarajuća linija na ovoj iteraciji naziva se općenita. Odgovara resursu koji ograničava proizvodnju na datoj iteraciji.

Jednostavni element tablice na sjecištu općeg stupca i reda naziva se opći element.

Tada se svi elementi opće linije (uključujući slobodni član) dijele općim elementom. Kao rezultat ove operacije, opći element postaje jednak jedinici. Nadalje, potrebno je da svi ostali elementi općeg stupca postanu jednaki nuli, tj. opšta kolona bi trebala postati pojedinačna. Svi nizovi (osim općeg) pretvaraju se na sljedeći način. Rezultirajući elementi novog retka množe se s odgovarajućim elementom općeg stupca i rezultirajući proizvod se oduzima od elemenata starog retka.

Vrijednosti novih osnovnih varijabli dobivaju se u odgovarajućim ćelijama kolone slobodnih članova.

Peta faza. Dobiveno osnovno rješenje provjerava se na optimalnost (vidi treću fazu). Ako je optimalno, proračuni se zaustavljaju. U suprotnom, potrebno je pronaći novo osnovno rješenje (četvrta faza) itd.

Simplex metoda

Primjer rješavanja optimizacijskih problema linearnog programiranja pomoću simpleks metode

Neka bude potrebno pronaći optimalan plan proizvodnje za dvije vrste proizvoda (x1 i x2).

Početni podaci:

Izgradimo model optimizacije

- ograničenje resursa A;

- ograničenje resursa V.

Dovedimo problem u njegov svedeni kanonski oblik. Da biste to učinili, dovoljno je uvesti dodatne varijable X3 i X4. Kao rezultat toga, nejednakosti se pretvaraju u stroge jednakosti.

Konstruirajmo inicijalnu simpleks tablicu i pronađemo početno osnovno rješenje. To će biti dodatne varijable, jer odgovaraju jediničnoj podmatrici.

1. iteracija. Pronađite opću kolonu i opći red:

Opći element je 5.

2. iteracija. Nađeno osnovno rješenje nije optimalno, jer red ocjena (Fj-Cj) sadrži jedan pozitivan element. Pronađite opću kolonu i opći red:

max (0,0,3, -1,4,0) = 0,2

Nađeno rješenje je optimalno, jer su sve posebne procjene ciljne funkcije Fj - Cj jednake nuli ili negativne. F (x) = 29 x1 = 2; x2 = 5.

11.4. DUAL SIMPLEX METODA

Iz rezultata prethodnih odlomaka proizlazi da se za rješenje izvornog problema može prijeći na dualno i, koristeći procjene njegovog optimalnog plana, odrediti optimalno rješenje izvornog problema.

Prijelaz na dvostruki problem nije potreban, jer ako uzmemo u obzir prvu simpleks tablicu s jedinicom dodatnom osnovom, lako je vidjeti da stupci sadrže izvorni problem, a redovi dvostruki.

Kao što je pokazano, pri rješavanju izravnog problema na bilo kojoj iteraciji razlika, tj. magnitude - koeficijent kod varijable, jednaka je razlici između desne i lijeve strane odgovarajućeg ograničenja dvostrukog problema. Ako pri rješavanju izravnog problema s maksimiziranom funkcijom cilja iteracija ne dovodi do optimalnog rješenja, tada za barem jednu varijablu i to samo za optimalnu za sve razlika.

Uzimajući u obzir ovaj uslov uzimajući u obzir dualnost, možemo pisati

.

Sta ako, onda. To znači da kada je rješenje direktnog problema suboptimalno, rješenje dvojnog problema je nedopustivo. Na drugoj strani at. Otuda slijedi da optimalno rješenje direktnog problema odgovara dopuštenom rješenju dualnog problema.

To je omogućilo razvoj nove metode za rješavanje problema linearnog programiranja, pri čijem se korištenju prvo dobiva neprihvatljivo, ali "bolje od optimalnog" rješenja (u uobičajenoj simpleks metodi prvo se pronalazi dozvoljeno, ali suboptimalno rešenje). Nova metoda tzv dual simplex metoda, osigurava ispunjenje uvjeta optimalnosti rješenja i njegovo sistematsko "približavanje" području izvedivih rješenja. Kada se dobijeno rješenje pokaže prihvatljivim, iterativni proces izračunavanja završava, jer je i ovo rješenje optimalno.

Dual simplex metoda omogućuje rješavanje problema linearnog programiranja, čiji sustavi ograničenja, s pozitivnom osnovom, sadrže slobodne izraze bilo kojeg znaka. Ova metoda vam omogućuje da smanjite broj transformacija ograničenja, kao i veličinu jednostavne tablice. Razmotrimo primjenu dual simplex metode na primjeru.

Primjer... Pronađite minimum funkcije

sa ograničenjima

.

Prijeđimo na kanonski oblik:

sa ograničenjima

Početna simplex tablica je

Početno osnovno rješenjeoptimalno, ali neprihvatljivo.

Kao i uobičajena simpleks metoda, razmatrana metoda rješenja temelji se na korištenju uvjeta prihvatljivosti i optimalnosti.

Uslov prihvatljivosti... Najveća negativna varijabla u apsolutnoj vrijednosti odabrana je kao isključena varijabla (u prisustvu alternativa, izbor se vrši proizvoljno). Ako su sve osnovne varijable negativne, proces računanja završava, jer je dobiveno rješenje izvodljivo i optimalno.

Stanje optimalnost... Varijabla uključena u bazu bira se među varijablama koje nisu bazirane na sljedeći način. Izračunavaju se omjeri koeficijenata lijeve strane-jednadžbe za odgovarajuće koeficijente jednadžbe povezane s isključenom varijablom. Odnosi s pozitivnim ili nultim nazivnikom se zanemaruju. U problemu minimiziranja uvedene varijable, najmanji od navedenih omjera mora odgovarati, a u problemu maksimizacije omjer najmanjeg u apsolutnoj vrijednosti (u prisustvu alternativa, izbor se vrši proizvoljno). Ako su nazivnici svih omjera nula ili pozitivni, problem nema izvodljiva rješenja.

Nakon odabira varijabli koje će biti uključene u bazu i koje će biti isključene radi dobivanja sljedećeg rješenja, izvodi se uobičajena operacija transformacije redova simpleks tablice.

U ovom primjeru isključena varijabla je... Omjeri izračunati za određivanje nove osnovne varijable prikazani su u sljedećoj tablici:

Uključena varijabla je odabrana x 2. Naknadna konverzija nizova rezultira novom simpleks tablicom:

Novo rešenje takođe optimalno, ali još uvijek ne vrijedi. Kao novu isključenu varijablu, odaberite (proizvoljno) x 3 Definirajmo uključenu varijablu.

Ovdje je ručno (ne aplet) rješenje dva problema pomoću simpleks metode (slično rješavanju apleta) sa detaljnim objašnjenjima kako bi se razumio algoritam za rješavanje problema pomoću simpleks metode. Prvi problem sadrži samo znakove nejednakosti "≤" (problem s početnom osnovom), drugi može sadržavati znakove "≥", "≤" ili "=" (problem s umjetnom osnovom), rješavaju se na različite načine .

Simplex metoda, rješavanje problema na početnoj osnovi

1)Simplex metoda za problem s početnom osnovom (svi znakovi ograničenja nejednakosti "≤").

Hajde da upišemo zadatak u kanonski oblik, tj. Ograničenja nejednakosti mogu se prepisati kao jednakosti dodavanjem bilans varijable:

Ovaj sistem je sistem sa bazom (osnove s 1, s 2, s 3, svaka od njih je uključena u samo jednu jednačinu sistema sa koeficijentom 1), x 1 i x 2 su slobodne varijable. Problemi u čijem se rješavanju koristi simpleks metoda moraju imati sljedeća dva svojstva: - sistem ograničenja mora biti sistem jednačina s bazom; - slobodni izrazi svih jednadžbi u sistemu moraju biti negativni.

Rezultirajući sistem je sistem sa osnovom i njegovi slobodni uslovi su negativni, pa se možemo primijeniti simpleks metoda... Sastavimo prvu simpleks tablicu (Iteracija 0) za rješavanje problema na simpleks metoda, tj. tablicu koeficijenata ciljne funkcije i sistem jednadžbi za odgovarajuće varijable. Ovdje "BP" znači stupac osnovnih varijabli, "Rješenje" - stupac desne strane jednadžbi sistema. Rješenje nije optimalno jer postoje negativni koeficijenti u redu z -.

iteracija simpleks metode 0

Da bismo poboljšali rješenje, prijeđimo na sljedeću iteraciju simpleks metoda, dobivamo sljedeću simpleks tablicu. Da biste to učinili, morate odabrati dozvoljena kolona, tj. varijabla koja će biti uključena u bazu pri sljedećoj iteraciji simplex metode. Odabire se najvećim modulo negativnim koeficijentom u z -retku (u maksimalnom problemu) -u početnoj iteraciji simplex metode, ovo je stupac x 2 (koeficijent -6).

Zatim se odabire dozvoljeni niz, tj. varijabla koja će izaći iz baze pri sljedećoj iteraciji simplex metode. Odabire se prema najmanjem omjeru stupca "Odluka" prema odgovarajućim pozitivnim elementima stupca koji rješava (stupac "Ratio") - u početnoj iteraciji to je red s 3 (koeficijent 20).

Dopuštajući element nalazi se na sjecištu stupca za rješavanje i rešavajući red, njegova ćelija je istaknuta, jednaka je 1. Stoga će se pri sljedećoj iteraciji simplex metode varijabla x 2 zamijeniti u bazi s 1. Imajte na umu da se relacija ne traži u z-liniji; tu se stavlja crtica "-". Ako postoje identični minimalni odnosi, bira se bilo koji od njih. Ako su u koloni za rješavanje svi koeficijenti manji ili jednaki 0, tada je rješenje problema beskonačno.

Popunimo sljedeću tablicu "Iteracija 1". Dobit ćemo ga iz tablice "Iteracija 0". Cilj daljnjih transformacija je pretvoriti rješavajući stupac x 2 u jedan (s jednim umjesto razlučivog elementa i nulama umjesto drugih elemenata).

1) Proračun reda x 2 tabele "Iteracija 1". Prvo dijelimo sve članove rješavajućeg reda s 3 tablice "Iteration 0" tačkom za rješavanje (u ovom slučaju je jednaka 1) ove tablice, dobivamo red x 2 u tablici Iteration 1. Jer rješavajući element u ovom slučaju jednak je 1, tada će se red s 3 tablice "Iteracija 0" podudarati s retkom x 2 tablice "Iteracija 1". Primili smo red x 2 tabele "Iteracija 1" 0 1 0 0 1 20, ostatak redova tabele "Iteracija 1" će se dobiti iz ovog reda i redovi tabele "Iteracija 0" na sljedeći način:

2) Proračun z-reda tabele "Iteracija 1". Umjesto -6 u prvom redu (z -red) u koloni x 2 tablice Iteracija 0, trebalo bi biti 0 u prvom redu tablice Iteracija 1. Da bismo to učinili, množimo sve elemente reda x 2 tablice "Iteracija 1" 0 1 0 0 1 20 sa 6, dobivamo 0 6 0 0 6 120 i dodajemo ovaj red s prvim redom (z - red) tabele "Iteracija 0" -4 -6 0 0 0 0, dobijamo -4 0 0 0 6 120. Nula 0 se pojavila u koloni x 2, cilj je postignut. Dozvoljeni elementi stupa x 2 označeni su crvenom bojom.

3) Proračun reda s 1 tabele "Iteracija 1". Na mjestu 1 u s 1 red tablice "Iteracija 0", mora biti 0 u tablici "Iteracija 1". Da bismo to učinili, množimo sve elemente reda x 2 tablice "Iteracija 1" 0 1 0 0 1 20 sa -1, dobivamo 0 -1 0 0 -1 -1-20 i dodajemo ovaj red sa s 1 - red tabele "Iteracija 0" 2 1 1 0 0 64, dobijamo red 2 0 1 0 -1 44. U koloni x 2 dobijamo traženo 0.

4) Proračun reda s 2 tabele "Iteracija 1". Na mjestu 3 u s 2 redu tabele "Iteracija 0", mora biti 0 u tabeli "Iteracija 1". Da bismo to učinili, množimo sve elemente reda x 2 tablice "Iteracija 1" 0 1 0 0 1 20 sa -3, dobivamo 0 -3 0 0 -3 -60 i dodajemo ovaj red sa s 1 - red tabele "Iteracija 0" 1 3 0 1 0 72, dobijamo red 1 0 0 1 -3 12. U koloni x 2 dobija se željena 0. Kolona x 2 u tabeli "Iteracija 1" postala je jedna , sadrži jedan 1, a ostatak 0.

Redovi tablice "Iteracija 1" dobivaju se prema sljedećem pravilu:

Novi red = Stari red - (Faktor kolone rezolucije starog reda) * (Novi red rezolucije).

Na primjer, za z-liniju imamo:

Stara z -linija (-4 -6 0 0 0 0) -( -6) * Nova linija za rješavanje -(0 -6 0 0 -6 -120) = Nova z -linija (-4 0 0 0 6 120).

Za sljedeće tablice ponovno izračunavanje elemenata tablice vrši se na isti način, pa ga izostavljamo.

iteracija simpleks metode 1

Dopuštajući stupac x 1, rješavajući red s 2, s 2 napušta bazu, x 1 ulazi u bazu. Na potpuno isti način dobivamo ostatak simpleks tablica dok ne dobijemo tablicu sa svim pozitivnim koeficijentima u z-retku. Ovo je znak optimalnog stola.

iteracija simpleks metode 2

Rješavajući stupac s 3, rješavajući red s 1, s 1 napušta bazu, s 3 ulazi u bazu.

iteracija simpleks metode 3

U z-redu svi koeficijenti su negativni, pa se dobiva optimalno rješenje x 1 = 24, x 2 = 16, z max = 192.

Za proizvodnju tri vrste košulja, niti, gumba i tkanina koriste se. Zalihe niti, dugmadi i tkanina, njihova potrošnja za šivanje jedne košulje prikazane su u tablici. Pronađite maksimalnu zaradu i optimalan plan objavljivanja proizvoda koji to osigurava (pronađite).

Rješenje problema

Izgradnja modela

Kroz i broj majica 1., 2. i 3. vrste, namijenjene za otpuštanje.

Tada će ograničenja resursa izgledati ovako:

Osim toga, u smislu problema

Ciljna funkcija koja izražava ostvareni profit:

Dobivamo sljedeći problem linearnog programiranja:

Svođenje problema linearnog programiranja u kanonski oblik

Dovedimo problem u kanonsku formu. Uvedimo dodatne varijable. U funkciju cilja uvodimo sve dodatne varijable s koeficijentom jednakim nuli. Dodajemo dodatne varijable lijevoj strani ograničenja koja nemaju željeni oblik i dobivamo jednakosti.

Rješavanje problema simpleks metodom

Popunimo simpleks tabelu:

Budući da rješavamo maksimalni problem, prisustvo negativnih brojeva u indeksnom retku pri rješavanju maksimalnog problema ukazuje na to da nismo dobili optimalno rješenje i da je potrebno prijeći iz tablice 0 -te iteracije na sljedeću.

Prijelaz na sljedeću iteraciju izvodi se na sljedeći način:

vodeće kolone

Ključni red određen je minimalnim omjerom slobodnih članova i članova vodeće kolone (simpleksni odnosi):

Na sjecištu stupca ključa i linije ključa nalazimo rješavajući element, tj. devet.

Sada počinjemo sa crtanjem prve iteracije: Umjesto jediničnog vektora, unosimo vektor.

U novoj tablici, umjesto rješavajućeg elementa, napišite 1, svi ostali elementi stupca ključa su nulirani. Elementi ključnih ključeva podijeljeni su u dozvolu. Svi ostali elementi tablice izračunavaju se prema pravougaoniku.

Stupac ključa za podudaranja prve iteracije

Dozvoljeni elementi su broj 4/3. Izvodimo vektor iz osnove i umjesto toga unosimo vektor. Dobijamo tabelu druge iteracije.

Stupac ključa za podudaranja druge iteracije

Pronalazimo niz ključeva, za to definiramo:

Rješavajući element je broj 10/3. Izvodimo vektor iz osnove i umjesto toga unosimo vektor. Dobivamo tablicu 3. iteracije.

Svi izrazi u indeksnom retku su negativni, pa se dobiva sljedeće rješenje problema linearnog programiranja (ispisujemo ga iz kolone slobodnih pojmova):

Potrebno je sašiti 24 majice tipa 1, 7 majica tipa 2 i 3 majice tipa 3. U tom će slučaju rezultirajuća dobit biti maksimalna i iznosit će 95 rubalja.

Ako trebate riješiti problem linearnog programiranja pomoću simpleks tablica, tada će vam naša mrežna usluga biti od velike pomoći. Simplex metoda podrazumijeva sekvencijalno nabrajanje svih vrhova raspona dopuštenih vrijednosti kako bi se pronašao vrh u kojem funkcija ima ekstremnu vrijednost. U prvoj fazi nalazi se neko rješenje koje se poboljšava u svakom sljedećem koraku. Ovo rješenje se naziva osnovnim. Evo slijeda radnji pri rješavanju problema linearnog programiranja pomoću simpleks metode:

Prvi korak. U sastavljenoj tabeli prije svega morate pogledati kolonu sa besplatnim članovima. Ako u njemu postoje negativni elementi, potrebno je prijeći na drugi korak, ako ne, onda na peti.

Drugi korak. U drugom koraku potrebno je odlučiti koju varijablu isključiti iz osnove, a koju uključiti kako bi se ponovo izračunala simpleks tablica. Da biste to učinili, pregledajte kolonu s besplatnim članovima i u njoj pronađite negativan element. Linija s negativnim elementom nazivat će se vodeća linija. U njemu nalazimo maksimalni negativni element u apsolutnoj vrijednosti, odgovarajući stupac - sljedbenik. Ako među slobodnim članovima postoje negativne vrijednosti, ali ne u odgovarajućem redu, tada takva tablica neće imati rješenja. Promjenom u vodećem redu, onaj u koloni slobodnih članova isključuje se iz osnove, a varijabla koja odgovara vodećem stupcu uključuje se u bazu.

Tabela 1.

Treći korak. U trećem koraku ponovno izračunavamo cijelu simpleks tablicu pomoću posebnih formula, koje se mogu vidjeti pomoću.

Četvrti korak. Ako nakon ponovnog izračuna negativni elementi ostanu u koloni slobodnih članova, idite na prvi korak, ako ih nema, na peti.

Peti korak. Ako ste dosegli peti korak, onda ste našli rješenje koje je prihvatljivo. Međutim, to ne znači da je optimalno. To će biti optimalno samo ako su svi elementi u F-redu pozitivni. Ako to nije slučaj, tada je potrebno poboljšati rješenje za koje nalazimo vodeći red i stupac za sljedeće preračunavanje prema sljedećem algoritmu. U početku nalazimo minimalni negativni broj u retku F, isključujući vrijednost funkcije. Stupac s ovim brojem bit će vodeći. Da bismo pronašli vodeći red, nalazimo omjer odgovarajućeg slobodnog člana i elementa iz vodećeg stupca, pod uvjetom da su pozitivni. Minimalni odnos omogućit će vam da odredite vodeći red. Ponovo izračunavamo tablicu koristeći formule, tj. idite na korak 3.