Problemi linearnog programiranja izjava o problemu: metode rješenja i formiranje

Za ekonomiste je često potrebno optimizirati proizvodnu funkciju, maksimizirati je ili minimizirati, na primjer, dobit, gubitak ili druge podatke uzimajući u obzir linearno ograničenje. Razumijevanje problema linearnog programiranja i problema postavljanja-za to je potrebno poznavanje osnova matematike i statistike. Zadatak linearnog programiranja (LP) je da definiše funkciju za dobijanje optimalnih podataka. Ovo je jedan od najvažnijih alata za istraživanje poslovanja. Takođe se široko koristi kao pomoć pri donošenju odluka u mnogim industrijama: u oblastima ekonomije, računarstva, matematike i drugih savremenih praktičnih istraživanja.

Karakteristike problema sa linearnim programiranjem

Razlikuju se sljedeće LP karakteristike:

1. Optimizacija. Osnova problema linearnog programiranja i formulisanja problema optimizacije je maksimiziranje ili minimiziranje neke baze podataka koja je predmet istraživanja. Ovo se često nalazi u ekonomiji, poslovanju, oglašavanju i mnogim drugim oblastima koje zahtevaju efikasnost da bi se sačuvali resursi. To uključuje pitanja ostvarivanja dobiti, sticanja resursa, vremena proizvodnje i drugih važnih ekonomskih pokazatelja.
2. Linearnost. Kao što naziv govori, Svi LP zadaci imaju atribut linearnosti. Međutim, ponekad je pogrešno, jer se linearnost odnosi samo na varijable stepena 1, isključujući funkcije stepena, kvadratne korijene i druge nelinearne zavisnosti. Međutim, to ne znači da funkcije LP zadatka imaju samo jednu varijablu. Tretira varijable kao koordinate tačaka na pravoj liniji, isključujući bilo kakvu zakrivljenost.
3. Objektivna funkcija. Osnova linearnih programskih zadataka i formulacija zadataka objektivnosti su varijable koje se mogu mijenjati po volji, na primjer, vrijeme provedeno na radu, proizvedene jedinice robe. Funkcija cilja napisana je velikim slovom "Z".
4. . Svi LP-ovi su ograničeni na varijable unutar funkcije. Ova ograničenja imaju oblik nejednakosti, na primjer, " b<3", gdje b može predstavljati jedinice knjiga koje je autor napisao mjesečno. Ove nejednakosti utvrđuju kako se objektivna funkcija može maksimizirati/minimizirati, jer zajedno definiraju odluka područja.

Uslovi definicija zadataka

Kompanije nastoje postići najveću profitabilnost u svojim aktivnostima, stoga moraju maksimalno iskoristiti svoje raspoložive resurse: ljude, materijale, opremu, fondove i druge. LP je predstavljen kao korisno je alat za određivanje najboljeg rješenja u kompaniji.

Uslovi za obavljanje zadataka linearnog programiranja i postavljanje zadataka su neophodni za dobijte maksimalnu neto dobit. Za rješavanje problema LP-a mora imati:

1. Ograničenja ili ograničeni resursi, na primer, ograničen broj zaposlenih, maksimalan broj kupaca ili ograničenje gubitaka u proizvodnji.
2. Cilj: maksimiziranje prihoda ili minimiziranje troškova.
3. Proporcionalna linearnost. Jednačine koje generišu varijable odlučivanja moraju biti linearne.
4. Ujednačenost: karakteristike varijabli i resursa rješenja su iste. Na primjer, radno vrijeme osobe je jednako produktivno ili je roba napravljena na mašini identična.
5. Djeljivost: proizvodi i resursi se mogu prikazati kao razlomci.
6. Bez negativnosti: rješenja moraju biti pozitivna ili jednaka nuli.

Objektivnost funkcije u formulaciji glavnog problema linearnog programiranja matematički izražava cilj koji treba postići u rješavanju problema. Na primjer, za maksimiziranje profita kompanije ili smanjenje troškova proizvodnje.

Ovo je predstavljeno jednačinom sa varijabilnim rješenjem, gdje: X 1, X 2, X 3, ..., X n-varijable rješenja; C 1, C 2, C 3, ..., C n-konstante.

Svako ograničenje je matematički izraženo bilo kojim od ovih atributa:

1. Manje ili jednako (≤). Kada postoji gornja granica, na primjer, Prekovremeni rad Ne može biti duži od 2 sata dnevno.
2. Jednako (=). Označava obavezne odnose, na primjer, konačna dionica jednaka je početnoj dionici plus proizvodnja minus prodaja.
3. Veći ili jednak (≥). Na primer, kada postoji donja granica, proizvodnja određenog proizvoda treba da bude veća od projektovane potražnje.
4. Opšta formulacija problema linearnog programiranja počinje postavljanjem ograničenja.
5. Svaki LP zadatak mora imati jedno ili više ograničenja.
6. Pozitivnost varijabli odlučivanja treba uzeti u obzir unutar ograničenja.

Faze postavljanja zadataka

Opća formulacija linearnog programskog problema i njegova formulacija odnosi se na prijevod stvarnog problema u oblik matematičkih jednačina koje se mogu riješiti.

Koraci u formulaciji problema cjelobrojnog linearnog programiranja:

1. Odredite broj koji otkriva ponašanje objektivne funkcije za optimizaciju.
2. Pronađite skup ograničenja i izrazite ih u obliku linearnih jednačina ili nejednakosti. Ovo će uspostaviti domen u n-dimenzionalnom prostoru optimiziranih funkcija.
3. Neophodno je nametnuti uslov ne-negativnosti na varijable zadatka, odnosno sve moraju biti pozitivne.
4. Izrazite funkciju u obliku linearne jednačine.
5. Grafički ili matematički optimizirajte funkciju kada se izvrši matematička formulacija problema linearnog programiranja.

Grafička metoda

Grafička metoda se koristi za obavljanje LP zadataka u dvije varijable. Ova metoda se ne koristi za riješite probleme, koji imaju tri ili više varijabilnih rješenja.

Standardni problem maksimiziranja nepoznatih LP problema, u kojima se funkcija povećava, podložno ograničenjima obrasca:

x ≥ 0, y ≥ 0, z ≥ 0 i dalja ograničenja oblika:

Ax + By + C z +. , ≤ N,

gdje su A, B, C i N nenegativni brojevi.

Nejednakost bi trebala biti"≤", a ne " = "ili"≥".

Grafička LP metoda sa dvije nepoznanice je sljedeća:

1. Postavi moguća područja grafa.
2. Izračunajte ugaone koordinate tačaka.
3. Zamijenite ih da biste vidjeli optimalnu vrijednost. Ovaj trenutak daje rješenje za LP problem.
4. Minimizirajte funkciju i, ako su njeni koeficijenti nenegativni, rješenje postoji.

Identifikacija postojećih rješenja:

1. Ograničite područje dodavanjem okomite linije desno od krajnje desne tačke ugla i horizontalne linije iznad najviše tačke ugla.
2. Izračunajte koordinate novih ugaonih tačaka.
3. Pronađite tačku ugla sa optimalnom vrijednošću.
4. Ako se odvija na početnoj tački neograničenog domena, onda LP problem ima rješenje u ovom trenutku. Ako ne, , nema optimalno rješenje.

Skiciranje skupa rješenja

Odaberite referentnu tačku i označite blokirano područje.

Nacrtajte područje predstavljeno nejednakošću dvije varijable kada postavljate problem linearnog programiranja. Ukratko, na primer:

1. Nacrtajte pravu liniju dobivenu zamjenom nejednakosti jednakošću.
2. Odaberite kontrolnu tačku, (0,0). Dobar izbor ako linija prolazi kroz početak.
3. Ako Kontrolna tačka zadovoljava nejednakost, tada je skup rješenja cijelo područje na istoj strani linije kao i kontrolna tačka. Inače je s druge strane linije.
4. Prihvatljiva domena je definisana skupom linearnih nejednakosti i predstavlja skup tačaka koje zadovoljavaju sve nejednakosti.
5. Da biste ga nacrtali definiranim skupom linearnih nejednakosti s dvije varijable, izvedite područja predstavljena svakom nejednakošću na istom grafikonu, ne zaboravljajući zasjeniti dijelove ravni koji nisu potrebni.

Simplex metoda za maksimiziranje

Formulacija linearnog programskog problema sa matematičkim modelom za maksimizaciju može se izvesti simplex metodom:

1. Pretvorite podatke u sistem jednačina, uvodeći slabe varijable za pretvaranje ograničenja u jednačine i prepišite funkciju u standardni oblik.
2. Napišite originalnu tabelu.
3. Odaberite kolonu preokret, negativni Broj sa najvećom vrijednošću u donjem redu, isključujući krajnji desni unos. Njegova kolona je sažetak. Ako postoje dva kandidata, izaberite jednog. Ako su svi brojevi u donjem redu nula ili pozitivni, isključujući krajnji desni unos, tada je sve spremno i osnovno rješenje maksimizira funkciju cilja.
4. Odaberite štap u koloni. Osa uvek mora biti pozitivan broj. Za svaki pozitivan unos " b "u koloni sažetih podataka izračunava se omjer" A / b", gdje "a" je li odgovor u ovom redu. Minimum se bira iz testnih koeficijenata, tada će odgovarajući broj " b " biti osa.
5. Pomoću štapa očistite kolonu na uobičajen način, pazeći da tačno slijedite upute za formuliranje operacija s redovima opisanim u priručniku za Gauss-Jordan metoda, a zatim zamijenite kolonu oznakom iz kolone.
6. Varijabla koja inicijalno označava zbirni red je odlazna, a varijabla koja označava kolonu dolazi.

Da bi se dobilo osnovno rješenje koje odgovara bilo kojoj tabeli u simplex metodi, sve varijable koje nisu prikazane kao oznake redova su postavljene na nulu. Vrijednost prikazane oznake reda (aktivna varijabla) je broj u krajnjoj desnoj koloni u redu podijeljen brojem u ovom redu u koloni označenoj istom varijablom.

Nestandardna ograničenja

Da bi se riješio problem LP-a sa ograničenjima forme (Ax + By +. , .≥ N)sa pozitivnim N, oduzmite dodatnu varijablu s lijeve strane (umjesto sabiranja slabe varijable). Osnovno rješenje koje odgovara originalnoj tabeli neće biti izvodljivo, jer će neke od aktivnih varijabli biti negativne. Stoga se pravila početnog okretanja razlikuju od gore navedenih.

Zatim su označeni svi redovi koji daju negativnu vrijednost za pridruženu aktivnu varijablu, s izuzetkom cilja. Ako postoje označene linije, morate početi s fazom I.

Faza I. Najveći pozitivan broj nalazi se u prvom redu. Koristite testne koeficijente kao u prethodnom odeljku da pronađete Sažetak U ovoj koloni, a zatim proširite ovaj unos. Ponavljajte dok ne ostanu označene linije, a Zatim prijeđite na fazu II.

Faza II koristi simpleks metodu za standardni problem maksimizacije. Ako postoje negativne vrijednosti u donjem lijevom redu nakon faze i, upotrijebite metodu standardnih problema maksimizacije.

Primer igre koja se može rešiti pomoću simplex metode.

PHPSimplex Online Alat

Trenutno tehnološki alati olakšavaju mnoge vrste profesionalne životne aktivnosti i metode rješavanja LP problema nisu izuzetak. Njihova prednost je, to možete dobiti optimalno rješenje sa bilo kojeg računara s pristupom internetu.

PHPSimplex je odličan online alat za rješavanje LP problema. Ova aplikacija može riješiti probleme bez ograničenja broja varijabli i ograničenja. Za probleme sa dvije varijable demonstrira grafičko rješenje i na jednostavan i razumljiv način predstavlja cijeli proces izračunavanja optimalnog rješenja. Ima prijateljski interfejs, blizak je korisniku, jednostavan je za korišćenje i intuitivan i dostupan je na nekoliko jezika.

WanerMath: aplikacije bez granica

Warneth pruža 2 alata za rješavanje problema linearnog programiranja:

1. Linearni programski grafikon (dvije varijable).
2. Simplex metoda.

Za razliku od drugih alata, gdje su postavljeni samo koeficijenti, ovdje su uključene sve funkcije s varijablama. Ovo ne predstavlja veliku poteškoću za korisnici početnici, pošto postoje upute za upotrebu na web mjestu profila. Osim toga, stranica ima funkciju "primjeri" koja automatski kreira zadatke tako da korisnik može procijeniti svoj rad, na primjer, kada postavlja problem linearnog programiranja transporta.

JSimplex je još jedan online alat. Omogućava vam rješavanje LP problema bez ograničavanja broja varijabli. Ima jednostavan kontrolni interfejs u kojem se predlaže da se odredi Svrha i broj varijabli. Korisnik zapisuje koeficijente objektivne funkcije, ograničenja i klikove na "riješi". Biće prikazana integracija, proračun optimalne varijante i rezultati svake varijable.

Kao što vidite, ovi alati su izuzetno korisni za lako učenje procedura rješenja za linearno programiranje.

Jednostavan primjer LP-a

Kompanija proizvodi prenosive i kalkulatore za naučna istraživanja. Dugoročne prognoze ukazuju na očekivanu dnevnu potrebu za 150 naučnih i 100 prenosnih kalkulatora. _dnevno proizvodni kapacitet dnevno omogućava proizvodnju ne više od 250 naučnih i 200 prenosnih kalkulatora.

Za ispunjavanje ugovora o isporuci potrebno je izdati najmanje 250 kalkulatora. Implementacija jednog dovodi do gubitka od 20 rubalja, ali svaki ručni kalkulator donosi profit od 50 rubalja. Za ostvarivanje maksimalne neto dobiti potrebno je izvršiti obračun.

Algoritam za izvršavanje primjera izjave problema linearnog programiranja:

1. Varijable odluke. Budući da je postavljen optimalni broj kalkulatora, oni će biti varijable I u ovom problemu: x je broj naučnih kalkulatora, y je broj prenosivih.
2. Oni postavljaju ograničenja, Budući da kompanija ne može proizvesti negativan broj kalkulatora dnevno, prirodna granica će biti: x ≥ 0, y ≥ 0.
3. Donja granica: x ≥ 150, y ≥ 100.
4. Postavite gornju granicu za ove varijable zbog ograničenja proizvodnje od strane kompanije: x ≤ 250, y ≤ 200.
5. Zajedničko ograničenje vrijednosti ` x ` i ` y ` zbog minimalne narudžbe za otpremu: x + y ≥ 250
6. Optimizirajte funkciju neto dobiti: P = - 20x + 50y.
7. rješenje problema: maksimiziranje P = —20x + 50y, pod uslovom da 150 ≤ x ≤ 250; 100 ≤ y ≤ 200; x + y ≥ 250.

Područja primjene

Među aplikacijama linearnog programiranja, najčešće:

1. Kumulativno planiranje prodaje i operacija. Cilj je minimizirati troškove proizvodnje u kratkom roku, na primer, tri i šest meseci zadovoljavajući očekivanu potražnju.
2. Planiranje proizvoda: pronađite optimalnu kombinaciju proizvoda, s obzirom da zahtevaju različite resurse i imaju različite troškove. Kao primjer, možete pronaći optimalnu mješavinu hemijskih elemenata za benzin, boje, ljudsku ishranu i stočnu hranu.
3. Proizvodni tok: odrediti optimalni tok za proizvodnju proizvoda koji mora uzastopno proći kroz nekoliko tokova posla, pri čemu svaki ima svoje troškove i proizvodne karakteristike.
4. Formulacija linearnog programiranja problema transporta, raspored transporta. Metoda se koristi za programiranje nekoliko ruta određenog broja vozila za opsluživanje kupaca ili primanje materijala koji će se prevoziti između različitih lokacija. Svako vozilo može imati različitu nosivost i performanse.
5. Upravljanje zalihama: određivanje optimalne kombinacije proizvoda koji će biti na lageru u prodajnoj mreži.
6. Kadrovsko programiranje: izrada kadrovskog plana koji vam omogućava da zadovoljite očekivanu varijabilnu potražnju za stručnjacima sa minimalnim mogućim brojem zaposlenih.
7. Kontrola otpada: koristeći linearno programiranje, možete izračunati kako smanjiti otpad na minimum.

Ovo su neki od najčešći aplikacije u kojima se koristi linearno programiranje su. Generalno, svaki problem optimizacije koji zadovoljava gore navedene uslove može se riješiti uz njegovu pomoć.