| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | Sv. član | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | Ž - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | Ž - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | Sv. član | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | Ž - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | Ž - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | Ž - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Svrha usluge. Online kalkulator koji se koristi za rješavanje problema linearnog programiranja P-metoda u sledećim oblicima snimanja: osnovni oblik snimanja simpleks metode, u obliku simpleks tabele, u modifikovanoj simpleks metodi.
Uputstva za rješavanje problema dual simplex metoda. Odaberite broj varijabli i broj redova (broj ograničenja), kliknite Dalje. Rezultirajuće rješenje se pohranjuje u Word datoteku (pogledajte primjer rješenja korištenjem dual simplex metode).
Istovremeno, ograničenja poput x i ≥ 0 ne uzimajte to u obzir.Sa ovim kalkulatorom se također koriste sljedeće:
Grafička metoda rješavanja ZLP-a
Rješenje transportnog problema
Rješavanje matrične igre
Koristeći online uslugu, možete odrediti cijenu matrične igre (donje i gornje granice), provjeriti prisutnost sedla, pronaći rješenje za mješovitu strategiju koristeći sljedeće metode: minimaks, simpleks metod, grafički (geometrijski ) metoda, Brownova metoda.
Ekstremum funkcije dvije varijable
Problemi sa dinamičkim programiranjem
Podijelite 5 homogenih partija robe između tri tržišta kako biste ostvarili maksimalan prihod od njihove prodaje. Prihod od prodaje na svakom tržištu G(X) ovisi o broju prodanih serija proizvoda X i prikazan je u tabeli.
| Volumen proizvoda X (u partijama) | prihod G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
U P-metodi optimalni plan se dobija kretanjem duž pseudoplanova. Pseudoplan- plan u kojem su zadovoljeni uslovi optimalnosti, a među vrijednostima osnovnih varijabli x i nalaze se negativni brojevi. Algoritam za dual simpleks metod uključuje sljedeće korake:
- Izrada pseudo plana. Sistem ograničenja originalnog problema dovodi do sistema nejednakosti sa značenjem “≤”.
- Provjera optimalnosti plana. Ako uvjet optimalnosti nije zadovoljen u rezultirajućem referentnom planu, tada se problem rješava simpleks metodom.
- Odabir vodećeg reda i stupca. Među negativnim vrijednostima osnovnih varijabli biraju se najveće u apsolutnoj vrijednosti. Linija koja odgovara ovoj vrijednosti je vodeća.
- Izračun novog referentnog plana. Novi plan se dobija ponovnim izračunavanjem simpleks tabele korišćenjem Jordan-Gaussove metode. Zatim prijeđite na 2. fazu.
Primjer. Preduzeće treba da proizvodi A1 jedinice, A2 jedinice i A3 jedinice prema planu proizvodnje. Svaka vrsta proizvoda može se proizvoditi na dvije mašine.
Kako rasporediti rad mašina tako da ukupno vrijeme utrošeno na izvršenje plana bude minimalno? Date su matrice troškova i vremenski resursi svake mašine. Zapišite model operacije koja se proučava u obliku koji dozvoljava korištenje P-metode.
Poznato je da sadržaj n nutrijenata A, B i C u ishrani treba da bude najmanje m1, m2, m3 jedinica, respektivno. Tri vrste hrane sadrže ove nutrijente. Sadržaj nutritivnih jedinica u jednom kilogramu svake vrste proizvoda prikazan je u tabeli. odrediti dnevnu ishranu koja obezbeđuje potrebnu količinu nutrijenata uz minimalne troškove.
Zadatak: Riješite zadatak koristeći algoritam dual simplex metode.
Svodimo sistem ograničenja na sistem nejednakosti značenja ≤ množenjem odgovarajućih linija sa (-1).
Odredimo minimalnu vrijednost ciljne funkcije F(X) = 4x 1 + 2x 2 + x 3 pod sljedećim uvjetima ograničenja.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Da bismo konstruisali prvi referentni plan, sistem nejednačina svodimo na sistem jednačina uvođenjem dodatnih varijabli (prelazak u kanonski oblik).
U prvoj nejednakosti značenja (≤) uvodimo osnovnu varijablu x 4 . U drugoj nejednakosti značenja (≤) uvodimo osnovnu varijablu x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
Matrica koeficijenata A = a(ij) ovog sistema jednačina ima oblik:
| A= |
|
x 4, x 5,
Uz pretpostavku da su slobodne varijable jednake nuli, dobijamo prvi referentni dizajn:
X1 = (0,0,0,-10,8)
| Osnova | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
Iteracija #1
Plan 0 u simpleks tabeli je pseudoplan, tako da određujemo vodeći red i kolonu.
Vodeći red će biti prvi red, a varijabla x 4 treba biti izvedena iz baze.
3. Definicija nove osnovne varijable. Minimalna vrijednost θ odgovara 2. koloni, tj. varijabla x 2 se mora unijeti u bazu.
| Osnova | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
| θ | 0 | -4: (-1) = 4 | -2: (-1) = 2 | - | - | - |
4. Ponovno izračunavanje simpleks tablice. Izvodimo transformacije simpleks tablice korištenjem Jordano-Gaussove metode.
| Osnova | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
Predstavimo proračun svakog elementa u obliku tabele:
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| -10: -1 | -1: -1 | -1: -1 | 0: -1 | 1: -1 | 0: -1 |
| 8-(-10 1):-1 | 2-(-1 1):-1 | 1-(-1 1):-1 | -1-(0 1):-1 | 0-(1 1):-1 | 1-(0 1):-1 |
| 0-(-10 -2):-1 | -4-(-1 -2):-1 | -2-(-1 -2):-1 | -1-(0 -2):-1 | 0-(1 -2):-1 | 0-(0 -2):-1 |
Iteracija #2
1. Provjera kriterija optimalnosti.
Plan 1 u simpleks tabeli je pseudoplan, tako da određujemo vodeći red i kolonu.
2. Definicija nove slobodne varijable.
Među negativnim vrijednostima osnovnih varijabli biramo najveću u apsolutnoj vrijednosti.
Drugi red će biti vodeći, a varijabla x 5 treba biti izvedena iz baze.
3. Definicija nove osnovne varijable. Minimalna vrijednost θ odgovara trećoj koloni, tj. varijabla x 3 se mora unijeti u bazu.
Na presjeku vodećeg reda i stupca nalazi se razlučujući element (RE) jednak (-1).
| Osnova | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
| θ | 0 | - | - | -1: (-1) = 1 | - | - |
4. Ponovno izračunavanje simpleks tablice. Vršimo transformacije.
| Osnova | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| 10-(-2 0):-1 | 1-(1 0):-1 | 1-(0 0):-1 | 0-(-1 0):-1 | -1-(1 0):-1 | 0-(1 0):-1 |
| -2: -1 | 1: -1 | 0: -1 | -1: -1 | 1: -1 | 1: -1 |
| 20-(-2 -1):-1 | -2-(1 -1):-1 | 0-(0 -1):-1 | -1-(-1 -1):-1 | -2-(1 -1):-1 | 0-(1 -1):-1 |
U osnovnoj koloni svi elementi su pozitivni. Pređimo na glavni algoritam simpleks metode.
Iteracija #3
1. Provjera kriterija optimalnosti.
Među vrijednostima niza indeksa nema pozitivnih vrijednosti. Stoga ova tabela određuje optimalni plan za problem.
| Osnova | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
Optimalni plan se može napisati na sljedeći način: x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22
Evo ručnog (ne apletnog) rješenja dva problema korištenjem simpleks metode (slično rješenju apleta) sa detaljnim objašnjenjima kako bi se razumio algoritam za rješavanje problema korištenjem simpleks metode. Prvi problem sadrži znakove nejednakosti samo “≤” (problem sa početnom osnovom), drugi može sadržavati znakove “≥”, “≤” ili “=” (problem sa umjetnom osnovom), različito se rješavaju.
Simpleksna metoda, rješavanje problema sa početnom osnovom
1)Simpleks metoda za problem sa početnom osnovom (svi znaci ograničenja nejednakosti " ≤ ").
Hajde da upišemo problem kanonski formu, tj. prepisujemo ograničenja nejednakosti u obliku jednakosti, dodajući bilans varijable:
Ovaj sistem je sistem sa bazom (baza 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 koji se rešavaju primenom simpleks metode moraju imati sledeća dva svojstva: - sistem ograničenja mora biti sistem jednačina sa osnovom; -slobodni članovi svih jednačina u sistemu moraju biti nenegativni.
Rezultirajući sistem je sistem sa osnovom i njegovi slobodni termini su nenegativni, tako da možemo primijeniti simpleks metoda. Kreirajmo prvu simpleks tablicu (Iteracija 0) za rješavanje problema simpleks metoda, tj. tabela koeficijenata funkcije cilja i sistem jednačina za odgovarajuće varijable. Ovdje “BP” označava kolonu osnovnih varijabli, “Rješenje” označava kolonu desne strane sistemskih jednačina. Rješenje nije optimalno, jer postoje negativni koeficijenti u z-redu.
iteracija simpleks metode 0
|
Stav |
|||||||
Da bismo poboljšali rješenje, prijeđimo na sljedeću iteraciju simpleks metoda, dobijamo sledeću simpleks tabelu. Da biste to učinili potrebno je da odaberete omogući kolonu, tj. varijabla koja će biti uključena u bazu pri sljedećoj iteraciji simpleks metode. Odabire se najvećim apsolutno negativnim koeficijentom u z-redu (u maksimalnom problemu) - u početnoj iteraciji simpleks metode to je stupac x 2 (koeficijent -6).
Zatim odaberite omogući string, tj. varijabla koja će napustiti bazu pri sljedećoj iteraciji simpleks metode. Odabire se najmanjim odnosom kolone “Odluka” prema odgovarajućim pozitivnim elementima kolone rezolucije (kolona “Ratio”) - u početnoj iteraciji to je red s 3 (koeficijent 20).
Permisivni element je na raskrsnici kolone za razrješenje i reda za razrješenje, njegova ćelija je označena bojom, jednaka je 1. Stoga, pri sljedećoj iteraciji simpleks metode, varijabla x 2 će zamijeniti s 1 u bazi. Imajte na umu da se odnos ne traži u z-stringu; tu se stavlja crtica “-”. Ako postoje identične minimalne relacije, tada se bira bilo koja od njih. Ako su svi koeficijenti u stupcu rezolucije manji ili jednaki 0, tada je rješenje problema beskonačno.
Popunimo sljedeću tabelu “Iteracija 1”. Dobićemo ga iz tabele “Iteracija 0”. Cilj daljih transformacija je da se kolona rezolucije x2 pretvori u jediničnu kolonu (sa jedinicom umjesto elementa rezolucije i nulama umjesto preostalih elemenata).
1) Izračunajte red x 2 tabele “Iteracija 1”. Prvo, podijelimo sve članove reda rješavanja s 3 tablice “Iteracija 0” sa elementom za razrješenje (u ovom slučaju je jednak 1) ove tablice, dobićemo red x 2 u tabeli “Iteracija 1” . Jer razlučujući element u ovom slučaju je jednak 1, tada će se red s 3 tabele „Iteracija 0” poklapati sa redom x 2 tabele „Iteracija 1”. Red x 2 tabele Iteracije 1 dobili smo 0 1 0 0 1 20, preostali redovi tabele Iteracije 1 će se dobiti iz ovog reda i redova tabele Iteracije 0 na sledeći način:
2) Izračunavanje z-reda tabele “Iteracija 1”. Umjesto -6 u prvom redu (z-red) u koloni x2 tabele Iteracije 0, trebalo bi da bude 0 u prvom redu tabele Iteracije 1. Da biste to učinili, pomnožite sve elemente reda x 2 tabele "Iteracija 1" 0 1 0 0 1 20 sa 6, dobićemo 0 6 0 0 6 120 i dodati ovaj red s prvim redom (z - red) tabele "Iteracija 0" -4 -6 0 0 0 0, dobijamo -4 0 0 0 6 120. U koloni x 2 pojavljuje se nula 0, cilj je postignut. Elementi kolone rezolucije x 2 su označeni crvenom bojom.
3) Izračunavanje reda s 1 tabele “Iteracija 1”. Umjesto 1 u s 1 redu tabele “Iteracija 0” treba da stoji 0 u tabeli “Iteracija 1”. Da biste to uradili, pomnožite sve elemente reda x 2 tabele "Iteracija 1" 0 1 0 0 1 20 sa -1, dobijete 0 -1 0 0 -1 -20 i dodajte ovaj red sa s 1 - redom tabela "Iteracija 0" 2 1 1 0 0 64, dobijamo red 2 0 1 0 -1 44. U koloni x 2 dobijamo traženu 0.
4) Izračunajte red s 2 tabele “Iteracija 1”. Na mjestu 3 u s 2 redu tabele "Iteracija 0" treba da stoji 0 u tabeli "Iteracija 1". Da biste to učinili, pomnožite sve elemente reda x 2 tabele "Iteracija 1" 0 1 0 0 1 20 sa -3, dobićemo 0 -3 0 0 -3 -60 i dodati ovaj red sa s 1 - redom tabela "Iteracija 0" 1 3 0 1 0 72, dobijamo red 1 0 0 1 -3 12. U koloni x 2 dobija se tražena 0. Kolona x 2 u tabeli "Iteracija 1" je postala jedinica, sadrži jednu 1, a ostatak 0.
Redovi tabele “Iteracija 1” dobijaju se prema sledećem pravilu:
Novi red = Stari red – (Koeficijent kolone rezolucije starog reda)*(Novi red rezolucije).
Na primjer, za z-string imamo:
Stari z-niz (-4 -6 0 0 0 0) -(-6)*Novi razrješavajući niz -(0 -6 0 0 -6 -120) =Novi z-string (-4 0 0 0 6 120).
Za sljedeće tabele, preračunavanje elemenata tabele se vrši na sličan način, pa ga izostavljamo.
iteracija simpleks metode 1
|
Stav |
|||||||
Rješavanje kolone x 1, rješavanje reda s 2, s 2 napušta bazu, x 1 ulazi u bazu. Na potpuno isti način dobijamo preostale simpleks tabele dok ne dobijemo tabelu sa svim pozitivnim koeficijentima u z-redu. Ovo je znak optimalnog stola.
iteracija simpleks metode 2
|
Stav |
|||||||
Razrješavanje stupca s 3, rješavanje reda s 1, s 1 napušta bazu, s 3 ulazi u bazu.
iteracija simpleks metode 3
|
Stav |
|||||||
U z-redu svi koeficijenti su nenegativni, stoga se dobija optimalno rješenje x 1 = 24, x 2 = 16, z max = 192.
Korak 0. Pripremna faza.
Problem LP svodimo na poseban oblik (15).
Korak 1. Kompajliranje simplex table, što odgovara posebnom obrascu:
|
|
|
|||||
|
|
|
|
|
|||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
Imajte na umu da ova tabela odgovara prihvatljivom osnovnom rješenju 
problemi (15). Vrijednost ciljne funkcije na ovom rješenju 
Korak 2. Provjera optimalnosti
Ako među elementima indeksnog reda postoje simpleks tabele 
tada nema ni jednog pozitivnog elementa 
, pronađeno je optimalno rješenje LP problema:. Algoritam se završava.
Korak 3. Provjera neodlučnosti
Ako među 
postoji pozitivan element 
, i u odgovarajućoj koloni 
nema ni jednog pozitivnog elementa 
, zatim ciljnu funkciju L je neograničen odozdo na dopuštenom skupu. U ovom slučaju ne postoji optimalno rješenje. Algoritam se završava.
Korak 4. Odabir vodeće kolone q
Među elementima 
izaberite maksimalni pozitivan element 
.Ovu kolonu proglašavamo vodećim (dozvoljenim) stupcem.
Korak 5. Izbor vodeće linije str
Među pozitivnim elementima kolone 
pronađite element 
, za koje vrijedi jednakost
.
String str Izjavljujemo da je vodeći (dopuštajući). Element 
Proglašavamo da je to lider (dopušta).
Korak 6. Simpleksna konverzija tablice
Kreiramo novu simpleks tabelu u kojoj:
a) umjesto osnovne varijable 
zapiši 
, umjesto nebazične varijable 
zapiši 
;
b) vodeći element je zamijenjen inverznom vrijednošću 
;
c) svi elementi vodeće kolone (osim 
) pomnoži sa 
;
d) svi elementi vodeće linije (osim 
) pomnoži sa 
;
e) preostali elementi simpleks tabele se transformišu prema sledećoj šemi „pravougaonika“.
Od elementa se oduzima proizvod tri faktora:
prvi je odgovarajući element vodeće kolone;
drugi je odgovarajući element vodeće linije;
treći je recipročan vodeći element 
.
Transformisani element i tri faktora koji mu odgovaraju su upravo vrhovi „pravougaonika“.
Korak 7 Prijelaz na sljedeću iteraciju se vrši vraćanjem na korak 2.
2.3. Algoritam jednostavne metode za maksimalni problem
Algoritam simpleks metode za maksimalni problem razlikuje se od algoritma za minimalni problem samo po predznacima indeksne linije koeficijenata u funkciji cilja 
, naime:
U koraku 2:
:
U koraku 3
. Ciljna funkcija je neograničena odozgo na dopuštenom skupu.
U koraku 4:
.
2.4. Primjer rješavanja problema primjenom simpleks metode
Riješite zadatak napisan u obliku (15).
Kreirajmo simpleks tablicu:
|
|
|
|
|
|
| |||
|
|
|
Budući da su koeficijenti linije ciljne funkcije nenegativni, početno bazno rješenje nije optimalno. Vrijednost funkcije cilja za ovu osnovu L=0.
Odaberite vodeći stupac - ovo je stupac koji odgovara varijabli 
.
Odaberite vodeću liniju. Da bismo to uradili nalazimo 
. Dakle, vodeća linija odgovara varijabli 
.
Simpleks tablicu transformiramo uvođenjem varijable 
u bazu i izlaz varijable 
od osnove. Dobijamo tabelu:
|
|
|
|
|
|
|
| ||
|
|
|
Jedna iteracija metode je završena. Pređimo na novu iteraciju. Dobivena tabela nije optimalna. Osnovno rješenje koje odgovara tabeli ima oblik . Vrijednost funkcije cilja na ovoj osnovi L= -2.
Vodeća kolona ovdje je stupac koji odgovara varijabli 
. Vodeća linija – linija koja odgovara varijabli 
. Nakon izvođenja transformacija, dobijamo simpleks tablicu:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Još jedna iteracija je završena. Pređimo na novu iteraciju.
Linija funkcije cilja ne sadrži pozitivne vrijednosti, što znači da je odgovarajuće osnovno rješenje optimalno, a algoritam se završava.
Za izradu tri vrste košulja koriste se konac, dugmad i tkanina. Zalihe konca, dugmadi i tkanine, norme njihove potrošnje za šivanje jedne košulje navedene su u tabeli. Pronađite maksimalnu dobit i optimalni plan proizvodnje proizvoda koji to osigurava (pronađite).
| majica 1 | majica 2 | majica 3 | Rezerve | niti (m.) | 1 | 9 | 3 | 96 | dugmad (kom.) | 20 | 10 | 30 | 640 | tekstil ( | 1 | 2 | 2 | 44 | Profit (r.) | 2 | 5 | 4 |
Rješenje problema
Izgradnja modela
Kroz i broj košulja 1., 2. i 3. tipa namijenjenih za puštanje.
Tada će ograničenja resursa izgledati ovako:
Osim toga, prema značenju zadatka
Ciljna funkcija koja izražava primljenu dobit:
Dobijamo sljedeći problem linearnog programiranja:
Svođenje problema linearnog programiranja na kanonski oblik
Svodimo problem na kanonski oblik. Hajde da uvedemo dodatne varijable. U ciljnu funkciju uvodimo sve dodatne varijable sa koeficijentom jednakim nuli. Lijevim stranama ograničenja dodajemo dodatne varijable koje nemaju željeni oblik i dobivamo jednakosti.
Rješavanje problema simpleks metodom
Popunite simpleks tabelu:
Budući da problem rješavamo maksimalno, prisustvo negativnih brojeva u indeksnoj liniji pri maksimalnom rješavanju problema ukazuje da nismo dobili optimalno rješenje i da je potrebno preći sa tabele 0. iteracije. do sledećeg.
Na sljedeću iteraciju prelazimo na sljedeći način:
vodeća kolona odgovara
Ključni red je određen minimalnim omjerom slobodnih termina i članova vodeće kolone (simplex relacije):
Na presjeku ključnog stupca i ključnog reda nalazimo omogućavajući element, tj. 9.
Sada prelazimo na kompajliranje 1. iteracije: Umjesto jediničnog vektora, uvodimo vektor .
U novoj tabeli, umjesto elementa omogućavanja pišemo 1, svi ostali elementi ključnog stupca su nule. Elementi niza ključeva podijeljeni su na element enable. Svi ostali elementi tabele se izračunavaju pomoću pravila pravokutnika.
Ključna kolona za 1. iteraciju odgovara
Razlučujući element je broj 4/3. Vektor izvodimo iz baze i umjesto toga uvodimo vektor. Dobijamo tabelu 2. iteracije.
Ključna kolona za 2. iteraciju odgovara
Pronalazimo ključnu liniju, za to definiramo:
Razlučujući element je broj 10/3. Vektor izvodimo iz baze i umjesto toga uvodimo vektor. Dobijamo tabelu 3. iteracije.
| № | BP | c B | A o | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | Simplex | 2 | 5 | 4 | 0 | 0 | 0 | odnos | 0 | x 4 | 0 | 96 | 1 | 9 | 3 | 1 | 0 | 0 | 32/3 | x 5 | 0 | 640 | 20 | 10 | 30 | 0 | 1 | 0 | 64 | x 6 | 0 | 44 | 1 | 2 | 2 | 0 | 0 | 1 | 22 | F j - c j | 0 | -2 | -5 | -4 | 0 | 0 | 0 | 1 | x 2 | 5 | 32/3 | 1/9 | 1 | 1/3 | 1/9 | 0 | 0 | 32 | x 5 | 0 | 1600/3 | 170/9 | 0 | 80/3 | -10/9 | 1 | 0 | 20 | x 6 | 0 | 68/3 | 7/9 | 0 | 4/3 | -2/9 | 0 | 1 | 17 | F j - c j | 160/3 | -13/9 | 0 | -7/3 | 5/9 | 0 | 0 | 2 | x 2 | 5 | 5 | -1/12 | 1 | 0 | 1/6 | 0 | -1/4 | -- | x 5 | 0 | 80 | 10/3 | 0 | 0 | 10/3 | 1 | -20 | 24 | x 3 | 4 | 17 | 7/12 | 0 | 1 | -1/6 | 0 | 3/4 | 204/7 | F j - c j | 93 | -1/12 | 0 | 0 | 1/6 | 0 | 7/4 | 3 | x 2 | 5 | 7 | 0 | 1 | 0 | 1/4 | 1/40 | -3/4 | x 1 | 2 | 24 | 1 | 0 | 0 | 1 | 3/10 | -6 | x 3 | 4 | 3 | 0 | 0 | 1 | -3/4 | -7/40 | 17/4 | F j - c j | 95 | 0 | 0 | 0 | 1/4 | 1/40 | 5/4 |
U indeksnom redu svi pojmovi su nenegativni, pa se dobija sledeće rešenje problema linearnog programiranja (ispisujemo ga iz kolone slobodnih termina):
Potrebno je sašiti 24 košulje 1. vrste, 7 košulja 2. tipa i 3 košulje 3. tipa. U ovom slučaju, primljena dobit će biti maksimalna i iznositi 95 rubalja.
Pomoć u rješavanju svojih problema na ovu temu možete pronaći slanjem poruke na VKontakte, Viber ili popunjavanjem obrasca. Cijena rješavanja domaće zadaće počinje od 7 BYR. po zadatku (200 ruskih rubalja), ali ne manje od 10 bjeloruskih rubalja. (300 RUB) za cijelu narudžbu. Detaljan dizajn. Troškovi online pomoći za ispit (u ovom slučaju potrebno je 100% avansno plaćanje) je od 30 BYR. (1000 ruskih rubalja) za rješavanje tiketa.
