Zgled:

Naslednji problem zapiši v obliki linearnega programa.

Podjetje Tartuf d.o.o. pakira bele in črne tartufe. Oboje poteka v treh fazah: polnjenje kozarcev, zapiranje kozarcev in lepljenje nalepk na kozarce.

 

Za kozarec belih tartufov potrebujejo 1 minuto za polnjenje, 2 minuti za zapiranje in 1 minuto za nalepko. Za kozarec črnih tartufov pa potrebujejo 2 minuti za polnjenje, 1 minuto za zapiranje in 1 minuto za nalepko.

 

Stroj, ki polni kozarce, je na razpolago 40 minut v vsaki uri; stroj, ki zapira kozarce, je tudi na razpolago 40 minut v vsaki uri; stroj, ki lepi nalepke, pa je na razpolago le 25 minut v vsaki uri. Podjetje ima pri prodaji kozarca belih tartufov dobiček 30 € in pri prodaji kozarca črnih tartufov 20 €. Podjetje želi doseči čim večji dobiček.

 

Rešitev:

Najprej uredimo dane podatke v preglednico:

 

	beli tartufi	črni tartufi	omejitve
Polnjenje kozarcev	1	2	40
Zapiranje kozarcev	2	1	40
Lepljenje nalepk	1	1	25
Dobiček	30	20
Količina izdelkov	x	y

 

a) Določimo namensko funkcijo.

 

Namenska funkcija predstavlja skupni dobiček pri prodaji belih in črnih tartufov.

 

Dobiček z enim kozarcem belih tartufov je 30, torej je dobiček z x kozarci belih tartufov 30x.

Dobiček z enim kozarcem črnih tartufov je 20, torej je dobiček z y kozarci črnih tartufov 20y.

Zato je dobiček z x kozarci belih in y kozarci črnih tartufov enak . Torej je namenska funkcija .

 

Dobiček mora biti maksimalen, zato iščemo maksimum namenske funkcije: .

 

b) Določimo omejitve:

 

• Stroj za polnjenje kozarcev:

Za polnjenje enega kozarca belih tartufov potrebujemo 1 minuto, torej za polnjenje x kozarcev potrebujemo x minut.

Za polnjenje enega kozarca črnih tartufov potrebujemo 2 minuti, torej za polnjenje y kozarcev potrebujemo 2y minut.

Zato potrebujemo za polnjenje x kozarcev belih in y kozarcev črnih tartufov skupno  minut. Ta stroj lahko uporabljamo kvečjemu 40 minut, zato je .

 

• Stroj za zapiranje kozarcev:

Za zapiranje enega kozarca belih tartufov potrebujemo 2 minuti, torej za zapiranje x kozarcev potrebujemo 2x minut.

Za zapiranje enega kozarca črnih tartufov potrebujemo 1 minuto, torej za zapiranje y kozarcev potrebujemo y minut.

Zato potrebujemo za zapiranje x kozarcev belih in y kozarcev črnih tartufov skupno  minut. Ta stroj lahko uporabljamo kvečjemu 40 minut, zato je .

 

• Stroj za lepljenje nalepk:

Za lepljenje nalepk na en kozarec belih tartufov potrebujemo 1 minuto, torej za lepljenje nalepk na x kozarcev potrebujemo x minut.

Za lepljenje nalepk na en kozarec črnih tartufov potrebujemo 1 minuto, torej za lepljenje nalepk na y kozarcev potrebujemo y minut.

Zato potrebujemo za lepljenje nalepk na x kozarcev belih in y kozarcev črnih tartufov skupno  minut. Ta stroj lahko uporabljamo kvečjemu 25 minut, zato je .

 

c) Vse spremenljivke morajo biti nenegativne.

 

V našem primeru imamo le dve spremenljivki, torej: .

 

Linearni program danega problema je torej takšen:

 

(skupni dobiček mora biti maksimalen)

(stroj za polnjenje kozarcev lahko uporabljamo največ 40 minut v vsaki uri)

(za zapiranje kozarcev je stroj na voljo največ 40 minut v vsaki uri)

(za lepljenje nalepk je stroj na voljo največ 25 minut v vsaki uri)

(vse spremenljivke morajo biti nenegativne)

***

Zgled:

Naslednji problem zapiši v obliki linearnega programa.

Na novoletni razprodaji so ponujali pakete knjig in DVD-jev. Leposlovni paket vsebuje 6 romanov in 3 DVD-je in stane 60 €. Romantični paket pa vsebuje 2 romana in 6 DVD-jev in stane 100 €. Andrej želi kupiti vsaj 28 romanov in 24 DVD-jev. Pri nakupu pa želi imeti čim manjše stroške.

 

Rešitev:

Najprej uredimo dane podatke v preglednico:

 

	leposlovni	romantični	omejitve
romani	6	2	28
DVD-ji	3	6	24
Strošek	60	100
Količina paketov	x	y

 

a) Določimo namensko funkcijo.

 

Namenska funkcija predstavlja skupni strošek pri nakupu leposlovnih in romantičnih paketov.

 

Strošek z nakupom enega leposlovnega paketa je 60, torej je strošek z nakupom x leposlovnih paketov 60x. Strošek z nakupom enega romantičnega paketa je 100, torej je strošek z nakupom y romantičnih paketov 100y. Zato je strošek z nakupom x leposlovnih paketov in y romantičnih paketov enak . Torej je namenska funkcija .

 

Stroški morajo biti minimalni, zato iščemo minimum namenske funkcije: .

 

b) Določimo omejitve:

 

• Romani:

V enem leposlovnem paketu je 6 romanov, torej je v x leposlovnih paketih 6x romanov.

V enem romantičnem paketu sta 2 romana, torej je v y romantičnih paketih 2y romanov.

Zato je v x leposlovnih in v y romantičnih paketih skupaj  romanov.  Ker želimo kupiti vsaj 28 romanov, je .

 

• DVD-ji:

V enem leposlovnem paketu so 3 DVD-ji, torej je v x leposlovnih paketih 3x DVD-jev.

V enem romantičnem paketu je 6 DVD-jev, torej je v y romantičnih paketih 6y DVD-jev.

Zato je v x leposlovnih in v y romantičnih paketih skupaj  DVD-jev.  Ker želimo kupiti vsaj 24 DVD-jev, je .

 

c) Vse spremenljivke morajo biti nenegativne.

 

V našem primeru imamo le dve spremenljivki, torej: .

Linearni program danega problema je torej takšen:

 

(Skupni stroški morajo biti minimalni.)

(Andrej želi kupiti vsaj 28 romanov.)

(Andrej želi kupiti vsaj 24 DVD-jev.)

(Vse spremenljivke morajo biti nenegativne.)

***

Zgled:

Vzemimo zgled s podjetjem Tartuf d.o.o. Tam smo dobili takšen linearni program: 

 

(iščemo maksimum namenske funkcije)

(omejitve)

(pogoj nenegativnosti)

 

Rešimo ta linearni program z grafično metodo.

 

Rešitev:

V koordinatni sistem narišimo množico vseh rešitev sistema linearnih neenačb, ki ga sestavljajo omejitve in pogoj nenegativnosti v linearnem programu:

 

 

 

 

 

 

Množica vseh rešitev danega sistema je konveksen lik ABCDE.

 

Namenska funkcija  doseže maksimum v eni od ekstremnih točk (oglišč) konveksnega lika. V kateri, pa lahko določimo na računski ali grafični način.

 

a) Računski način

 

• Določimo koordinate vseh oglišč konveksnega lika:

C je presečišče premic  in . Iz prve enačbe izrazimo  in ga vstavimo v drugo enačbo: . Dobljeno vrednost pa vstavimo v . Torej: .

D je presečišče premic  in . Iz prve enačbe izrazimo  in ga vstavimo v drugo enačbo:

.

Dobljeno vrednost pa vstavimo v . Torej: .

 

• Izračunajmo vrednost namenske funkcije  v vsakem oglišču konveksnega lika:

 

• Določimo maksimum namenske funkcije:

Namenska funkcija doseže maksimalno vrednost 650 v točki . To pomeni, da bo imelo podjetje Tartuf d.o.o. največji dobiček v primeru, ko bo v eni uri zapakiralo 15 kozarcev belih in 10 kozarcev črnih tartufov. Dobiček bo v tem primeru znašal 650 €.

 

b) Grafični način

 

KORAK 1:
V koordinatni sistem s konveksnim likom ABCDE narišimo še (rdečo) premico z enačbo , torej .

 

KORAK 2:
Ker iščemo maksimum namenske funkcije, moramo to premico vzporedno premakniti čim višje, vendar tako, da bo imela z likom ABCDE vsaj eno skupno točko.

 

Vzporednica rdeče premice z zgoraj opisanimi lastnostmi se lika ABCDE dotika v točki C. To pomeni, da namenska funkcija doseže maksimum v točki C. Izračunajmo koordinate točke C. Točka C je presečišče premic  in . Iz prve enačbe izrazimo  in ga vstavimo v drugo enačbo: . Dobljeno vrednost pa vstavimo v . Torej je točka .

 

Torej je maksimum namenske funkcije enak . To pomeni, da bo imelo podjetje Tartuf d.o.o. največji dobiček v primeru, ko bo v eni uri zapakiralo 15 kozarcev belih in 10 kozarcev črnih tartufov. Dobiček bo v tem primeru znašal 650 €.

***

Zgled:

Vzemimo še zgled z leposlovnimi in romantičnimi paketi. Tam smo dobili takšen linearni program: 

 

(iščemo minimum namenske funkcije)

(omejitvi)

(pogoj nenegativnosti)

 

Rešimo ta linearni program z grafično metodo.

 

Rešitev:

V koordinatni sistem narišimo množico vseh rešitev sistema linearnih neenačb, ki ga sestavljajo omejitve in pogoj nenegativnosti v linearnem programu:

 

 

 

 

Množica vseh rešitev danega sistema je pobarvana konveksna množica.

 

Namenska funkcija  doseže minimum v eni od ekstremnih točk (oglišč) konveksnega lika. V kateri, pa lahko določimo na računski ali grafični način.

 

a) Računski način

 

• Določimo koordinate vseh oglišč konveksne množice točk:

B je presečišče premic  in . Iz prve enačbe izrazimo  in ga vstavimo v drugo enačbo:

.

Dobljeno vrednost pa vstavimo v . Torej: .

 

• Izračunajmo vrednost namenske funkcije  v vsakem oglišču konveksnega lika:

 

• Določimo minimum namenske funkcije:

Namenska funkcija doseže minimalno vrednost 440 v točki . To pomeni, da bo imel Andrej najmanjše stroške, če bo kupil 4 leposlovne in 2 romantična paketa. Stroški bodo v tem primeru znašali 440 €.

 

b) Grafični način

 

KORAK 1:
V koordinatni sistem s konveksno množico narišimo še (rdečo) premico z enačbo , torej .

 

 

KORAK 2:
Ker iščemo minimum namenske funkcije, moramo to premico vzporedno premakniti čim nižje, vendar tako, da bo imela s konveksno množico vsaj eno skupno točko.

 

Vzporednica rdeče premice z zgoraj opisanimi lastnostmi se konveksne množice dotika v točki B. To pomeni, da namenska funkcija doseže minimum v točki B. Izračunajmo koordinate točke B. Točka B je presečišče premic  in . Iz prve enačbe izrazimo  in ga vstavimo v drugo enačbo:

.

Dobljeno vrednost pa vstavimo v . Torej je točka .

 

Torej je minimum namenske funkcije enak . To pomeni, da bo imel Andrej najmanjše stroške, če bo kupil 4 leposlovne in 2 romantična paketa. Stroški bodo v tem primeru znašali 440 €.

***

Zgled:

Vzemimo za zgled poslovanje podjetja Tartuf d.o.o. Tam smo dobili takšen linearni program:

 

(iščemo maksimum namenske funkcije)

(omejitve)

(pogoj  nenegativnosti)

 

Rešimo ta linearni program z metodo simpleksov.

 

Rešitev:

V tem primeru določamo maksimum namenske funkcije, neenačbe v omejitvah pa so oblike . Zato postopamo tako:

 

a) Neenačbe s pomočjo dopolnilnih spremenljivk pretvorimo v enačbe:

 

 

b) Koeficiente sistema uredimo v začetno simpleksno tabelo:

 

 

c) Poiščemo pivotni element:

 

• izberemo stolpec, ki ima v prvi vrstici najmanjšo vrednost (v našem primeru je to drugi stolpec);

 

• izberemo vrstico: v vsaki (razen v prvi) vrstici izračunamo količnik med vrednostjo v stolpcu b-jev in vrednostjo v izbranem stolpcu; izberemo tisto vrstico, v kateri je ta količnik najmanjši (v našem primeru je to tretja vrstica);

 

 

• »križišče« izbrane vrstice in izbranega stolpca imenujemo pivot;

 

· na mestu pivota ustvarimo enko tako, da celotno vrstico pomnožimo z  (v našem primeru je to  );

 

· na vseh ostalih mestih v izbranem stolpcu s pomočjo linearnih transformacij ustvarimo ničle (v našem primeru tretjo vrstico pomnožimo s 30 in jo prištejemo k prvi vrstici, tretjo vrstico pomnožimo z (-1) in jo prištejemo k drugi vrstici, tretjo vrstico pomnožimo z (-1) in jo prištejemo k zadnji vrstici).

 

 

d) Spet poiščemo pivotni element:

 

• izberemo stolpec, ki ima v prvi vrstici najmanjšo vrednost (v našem primeru je to tretji stolpec);

 

• izberemo vrstico: v vsaki (razen v prvi) vrstici izračunamo ustrezen količnik in izberemo tisto vrstico, v kateri je ta količnik najmanjši (v našem primeru je to četrta vrstica);

 

 

• »križišče« izbrane vrstice in izbranega stolpca imenujemo pivot;

 

• na mestu pivota ustvarimo enko tako, da celotno vrstico pomnožimo z  (v našem primeru četrto vrstico pomnožimo z 2);

 

 

• na vseh ostalih mestih v izbranem stolpcu s pomočjo linearnih transformacij ustvarimo ničle (v našem primeru četrto vrstico pomnožimo s 5 in jo prištejemo k prvi vrstici, četrto vrstico pomnožimo z (-3/2) in jo prištejemo k drugi vrstici, četrto vrstico pomnožimo z (-1/2) in jo prištejemo k tretji vrstici).

 

 

Opisan postopek ponavljamo, dokler so  prvi vrstici negativne vrednosti. V našem primeru v prvi vrstici ni več negativnih vrednosti, torej je postopek končan.

 

Iz razširjene matrike preberemo rešitev:

• V zadnjem stolpcu prve vrstice preberemo maksimalno vrednost namenske funkcije: 650.

 

• V stolpcu, ki predstavlja spremenljivko x (drugi stolpec), poiščemo enko. V našem primeru je enka v tretji vrstici. Zato vrednost spremenljivke x preberemo v zadnjem stolpcu tretje vrstice: x=15.

 

• V stolpcu, ki predstavlja spremenljivko y (tretji stolpec), poiščemo enko. V našem primeru je enka v četrti vrstici. Zato vrednost spremenljivke y preberemo v zadnjem stolpcu četrte vrstice: y=10.

 

To pomeni, da bo imelo podjetje Tartuf d.o.o. maksimalni dobiček v primeru, če bo zapakiralo x=15 kozarcev belih in y=10 kozarcev črnih tartufov na uro. Dobiček bo v tem primeru znašal f=650 €.

***

Zgled:

Poglejmo še Andrejevo kupovanje leposlovnih in romantičnih paketov. Tam smo dobili takšen linearni program:

 

(iščemo minimum namenske funkcije)

(omejitvi)

(pogoj nenegativnosti)

 

Rešimo ta linearni program z metodo simpleksov.

 

Rešitev:

V tem primeru določamo minimum namenske funkcije, neenačbe v omejitvah pa so oblike . Zato se postopek v nekaterih korakih razlikuje od postopka v prejšnjem zgledu.

 

a) Neenačbi s pomočjo dopolnilnih spremenljivk pretvorimo v enačbi:

 

 

 

 

b) Uvedemo umetne spremenljivke, ki jim določimo neko zelo veliko vrednost M. (Tej metodi rečemo »metoda velikega M-ja«.)

 

 

Za M vzemimo npr. dvakratnik največjega koeficienta v namenski funkciji: .

 

 

 

 

c) S pomočjo linearnih transformacij preoblikujemo prvo vrstico tako, da bosta koeficienta pred umetnima spremenljivkama enaka 0.

 

Drugo vrstico, pomnoženo z M (v našem primeru je to 200), prištejemo k prvi vrstici, ostale vrstice pa prepišemo.

 

 

 

 

Tretjo vrstico, pomnožimo z M (v našem primeru je to 200), prištejemo k prvi vrstici, ostale vrstice pa prepišemo.

 

 

 

 

d) Koeficiente sistema uredimo v začetno simpleksno tabelo

 

 

e) Poiščemo pivotni element:

 

• izberemo stolpec, ki ima v prvi vrstici največjo vrednost (v našem primeru je to drugi stolpec);

 

• izberemo vrstico: v vsaki (razen v prvi) vrstici izračunamo količnik med vrednostjo v stolpcu b-jev in vrednostjo v izbranem stolpcu; izberemo tisto vrstico, v kateri je ta količnik najmanjši (v našem primeru je to druga vrstica);

 

 

• »križišče« izbrane vrstice in izbranega stolpca imenujemo pivot;

 

 

· na mestu pivota ustvarimo enko tako, da celotno vrstico pomnožimo z  (v našem primeru je to  );

 

· na vseh ostalih mestih v izbranem stolpcu s pomočjo linearnih transformacij ustvarimo ničle (v našem primeru drugo vrstico pomnožimo z (-1740) in jo prištejemo k prvi vrstici, drugo vrstico pomnožimo z (-3) in jo prištejemo k tretji vrstici).

 

 

f) Spet poiščemo pivotni element:

 

• izberemo stolpec, ki ima v prvi vrstici največjo vrednost (v našem primeru je to tretji stolpec);

 

• izberemo vrstico: v vsaki (razen v prvi) vrstici izračunamo ustrezen količnik in izberemo tisto vrstico, v kateri je ta količnik najmanjši (v našem primeru je to tretja vrstica);

 

 

• »križišče« izbrane vrstice in izbranega stolpca imenujemo pivot;

 

• na mestu pivota ustvarimo enko tako, da celotno vrstico pomnožimo z  (v našem primeru tretjo vrstico pomnožimo z  );

 

 

• na vseh ostalih mestih v izbranem stolpcu s pomočjo linearnih transformacij ustvarimo ničle (v našem primeru tretjo vrstico pomnožimo z (-920) in jo prištejemo k prvi vrstici, tretjo vrstico pomnožimo z (-1/3) in jo prištejemo k drugi vrstici.

 

 

Opisan postopek ponavljamo, dokler so v prvi vrstici (razen na prvem in zadnjem mestu) pozitivne vrednosti. V našem primeru v prvi vrstici (razen na prvem in zadnjem mestu)  ni več pozitivnih vrednosti, torej je postopek končan.

 

Iz razširjene matrike preberemo rešitev:

• V zadnjem stolpcu prve vrstice preberemo minimalno vrednost namenske funkcije: 440.

 

• V stolpcu, ki predstavlja spremenljivko x (drugi stolpec), poiščemo enko. V našem primeru je enka v drugi vrstici. Zato vrednost spremenljivke x preberemo v zadnjem stolpcu druge vrstice: x=4.

 

 

• V stolpcu, ki predstavlja spremenljivko y (tretji stolpec), poiščemo enko. V našem primeru je enka v tretji vrstici. Zato vrednost spremenljivke y preberemo v zadnjem stolpcu tretje vrstice: y=2.

 

 

To pomeni, da bo imel Andrej minimalne stroške v primeru, če bo kupil x = 4 leposlovne pakete in y = 2 romantična paketa. Stroški bodo v tem primeru znašali 440 €.

***