i
i
“4-1-Vadnal-naslov” — 2009/3/27 — 9:13 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 4 (1976/1977)
Številka 1
Strani 8–13
Alojzij Vadnal:
LINEARNO PROGRAMIRANJE, Naloga o najcenej-
šem prevozu
Ključne besede: matematika.
Elektronska verzija: http://www.presek.si/4/4-1-Vadnal.pdf
c© 1976 Društvo matematikov, fizikov in astronomov Slovenije
c© 2009 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
LIN EARNO PROGRAM IRANJ E
NALOGA O NAJ CENEJ ŠEM PREVOZU
Iz dveh tovarn A in B mora mo prepeljati izde la no blago v me-
sti p in R . Iz tovarne A odpeljemo 16 t , iz tovarne B pa 23 t
bl a ga . V me s to p moramo pri peljati 18 t, v mesto R pa 21 t bl a-
ga . Pri prevozu blaga pl ačamo pre vozne stroške; prevoz 1 t bla-
ga sta~e pri prevozu od A do p 9 di n, od A do R 6 d in, od B do
p 7 din in od B do R 8 din . Ti podatki so pregledno vpis ani v
ta be l i 1. Pri teh podat kih re ši mo nalogo :
Ka ko na j usmerimo prevoz blaga iz tovarn v obe mesti, da bo-
do skupni prevozni strošk i najmanjši?
Mes t o K o l i č i n a
p R
odpeljanega
blaga
A 9 6 16
Tova rn a
'B 7 8 23
Ko li čina
pripelj ane ga 18 21 39
blag a
Tabel a 1. Podatki naloge o najcenej šem prevozu
REš EVANJ E NA LOGE PO ME TODI sT OPALNIKOV
Pri re šev anju na loge po tej metodi si pomagamo s tabeli l .
prirej en o pom ožn o ta be l o 2 . Izmislimo si kakšen s i s t em prevoza,
ki ust re za pogojem obeh to va r n in obe h mest. V ta namen vzame -
mo, da pr e pe l je mo od A do p ka r največ bl aga; ker ga l a hko od-
peljem o iz A najv e č 1 6 t in ker ga moramo prip eljati v P 18 t,
pre peljemo iz A v p 16 t bla ga; to količino vpi š emo v pomožni
tabe l i v sre d i no p reda lč ka (A,P) . Zdaj la hko dol oči mo k ol i č i n e
na vseh dr ugi h pote h pr ep elj anega bl aga . Iz A ne moremo prepe -
l j a t i v R n ič ve č bla ga , ker smo že iz črpali zalogo blaga v A;
iz B lah ko prepelj em o v P sa mo še 2 t blaga; k o nč no prepeljemo
še iz B v R 21 t blaga; t a šte vila vpi š em o v ta be li 2 . v sredi -
8
no ust r eznih pre da l čkov. Tako dobi mo pre vozni sistem, ki mu u-
streza četverica š te vi l
16 O
2 21
in ki ga ponazar j a sl i ka 1. Temu prevo znem u sistemu ust rezajo
skupni prevo zni stro š ki , ki j i h iz ra čunam o takole :
8 1 = 16.9 + 0. 6 + 2. 7 + 21.8 = 326 din
P R
9
0
6
.4 16 16
B 2
7 2l 23
18 2 1
Tab ela 2
Vs a ko četverico števil , ki zado šča vsem pogojem za tovarni
in mesti, imenujemo možno r eš i t ev nalo ge . Izračunano možno re -
šitev podaja tabela 2. i n ponazarj a sl i ka 1 . Razmislimo , ali
moremo to rešitev izbol jšati. Hi t ro s e p r e p r i č a m o , da je to mo-
žno , č e sklepamo ta kole : Pri i zr a ču na ni rešitvi ostaja pot od A
do R neiz koriščena. Zato je edi no m o g oč a sp rememba te re šitve
taka, da usmerimo na to pot ne kaj bl aga, recimo 1 tono . Oa ne
prekršimo pogojev, moramo zato pre pelj a no količino blaga od A
do P zmanj šati za 1 t, od B do P zve čati za 1 t in od B do R
zmanjšati za 1 t . Izr ačuna jm o , za koliko se pri tej spremembi
s pr eme ni j o s kupni pr evozn i st ro š ki . Ke r dodamo na pot i od A do
R 1 t, se stroški zve caJo za 6 di n; ker odvzamemo s poti od A
do P 1 t, se stroški zmanjšajo za 9 di n; ker dodamo na poti od
B do P 1 t , se stro ški povečaj o za 7 di n ; ker odvzamemo s poti
od B do R 1 t, se st r oš ki zmanjš ajo za 8 din . Skupno se t ore j
spremenijo s t r ošk i za
6 - 9 + 7 - 8 = - 4 di n
Pri takem računanju spremembe stroš kov s mo najprej "stopili" v
predalček (A, R) nato pa pre ko predal čkov (A, P), ( B, P) in (B ,R)
nazaj v (A, R); odtod i z ra z metoda s t opa l ni kov .
9
St roške torej l a hko zma nj š am o ! Skupn i prevozni strošk i se
znlzaJO za 4 din, če prepeljemo na poti od A do R 1 tono blaga
več . Zato ravnamo na j bol j gospodarno, če usme r i mo na pot od A
do R kar n a j v e č blaga. Toda več kot 16 t ga ne moremo prepe lja-
ti po te j pot i, ker ga tovar na A ni ma več na za log i ; za to usme-
r imo na pot od A do R 16 t bl aga in sk ladno s pogoji spremen imo
količ ine prepe lja nega blaga še na dr ugih t r e h pot e h . Tako dobi-
mo kot dru go mož no reš itev četverico števil
O 16
18 5
Tej reš i tvi ustrezajo s kupni prevozn i stroš ki
S 2 = 0 . 9 + 16.6 + 18 .7 + 5 .8 = 262 d i n
Dr ugo možno r eši t ev podaja tabe la 3 . in ponazarja s l i ka 2.
Na podobe n nač i n, kakor s mo se pri pr vi mož ni rešitvi mog l i
prepričat i z me t od o stopa lnikov, da l a hko reš itev i zbol j š amo ,
se pri d r ugi možni rešit v i l ah ko prepričamo, da te ne moremo
izbo l jšat i . Prepr ičaj s e sam ! Zato je ta rešitev opt ima lna i n
nal oga je r e š e na ; blago prepe l jemo najb ol j poce ni , če prepe lje-
mo iz A v P 16 t, iz B v P 18 t i n iz B v R 5 t; t a k prevoz
sta ne 262 din ar j ev.
P R
9
16
6
A O 16
7 8
B 18 5 23
18 21
/
/
/
I
/
/
/
R
Ta bel a 3 B 5 1 . 2
Naloga. Pos t avi s i sam kak šno nal ogo
o na j cen ej š em pr evoz u in jo reš i.
Naloga. Reši nal ogo o najce nejše m
prevoz u, ki j o podaja t a bel a:
10
P R
A 2 5 9
B 4 3 16
9 16
Rešitev: 9
O
O
16 ; Ta nal oga je zan i miva za t o, ker razpade opti-
P R
A 1 2 9
B 3 4 16
6 19
malni pre vozni s i s t em v dva med s eboj ne povezan a s i s t ema .
NaZoga. Reši nalog o O na j ce ne j šem
prevozu , ki jo podaja t abela:
Ta naloga je za ni mi va zato , ke r s o
vse r ešitve enako "dobre" .
ANAL I T IčNO REšEV AN J E NALOG E
Rešim o nalogo o najcenej š em pre -
vozu, ki smo jo že r eš i l i po meto ~
d i s t opaln ikav, še analitično . V
t a namen vz amemo, kakor vidimo v
Tabela '3.
P R
9 6
A x 16 - x 16
7 8
B 18-x 5+x 23
18 21
t abeli 3, da prepe ljemo od A do P
nezn ano k ol i čino x ton blaga . Nato
do l o č i m o ob upoštevanju proizvod-
nj e to va rn in potreb mest š e na
drugih treh poteh pr epeljane k oli čine blag a; te znaš a j o 16-x,
18- x in 5+x ton. Vsa ta š t e vi l a vpišem o v tabelo 3 . v sredino
ustreznih p redalčkov . J a sno j e , da ne s me bit i nobena od vpi sa-
nih koli čin blaga negati vna. Od t od s led i, da zado š ča spremen-
lj ivka x h e e na č b a m:
x ~ O, x;; 16, x ~ 18 , 5+x ~ O
č e t r t a nee na čba je izpoln j e na, brž ko j e izpolnjena prva;
zato jo lahko opustim o . Tret j a neena čb a j e izp olnjena , brž ko
je izpolnjena druga ; zato tudi to l ahk o op us t i mo . Pot emtakem
mora ustrezati spr em enljivk a x neena čb a m a:
O ~ x ~ 16
Izračunajmo še skupne prevozn e s tr oš ke pri v tabeli 3. zapi sa-
nem prevoznem si stemu ; ti zna š a j o :
S (x ) = 9x + 6(16 - x ) + 7( 18 - x) + 8( 5 + x) =
( 26 2 + 4x) din
Vidimo , da so pre vozni stroš ki S odvis ni od s pr eme nl j i v ke x.
To odvisn ost ponaza rja dia gr am na s l ik i 3 .
Zdaj lahko f ormuliramo nal ogo o naj cen e j šem pr evozu takole :
Ooločiti moramo vredn ost s pr emen l j i v ke x, ki zado šča ne enačbama
O ;; x ;; 16 tako , da pos tan ej o sku pni prev ozni stro ški S (x) =
11
15 16 X [ t] reš ite v
330
2 50
20 0
S din
262
o
282
5
Sli ka
302
10
= 262 + 4x najmanjši . Ti stroš -
ki so najmanjši in znašajo 262
din, če je vrednost spremen-
ljivke x kolikormogočemajhna ;
tosezgodi, ko je x = O. To vi -
dimo iz izraza 262 + 4x, pa tu -
di iz diagrama na sl iki 3. če
vstavimo v tabelo 3. namesto x
to vrednost, dobimo optimalno
o 16
18 5
za katero so skupni prevozni
stroški najmanjši in znašajo
262 din.
Na l oga . V organizaciji združenega dela je zaposlenih 20 ena-
ko delovnih strugarjev in 10 enako delovnih varilcev. Za struže-
nje potrebuje organizacija 17, za varjenje pa 13 delavcev. če
strugar struži, ustvari svoji organizaciji na dan 1 000 din do-
hodka, če vari, pa samo 600 din; če varilec struži, ustvari 800
din, če vari, pa 1 100 din dohodka. Kako naj razporedi organiza-
cija delavce na delovna mesta, da bodo ustvarili vsi skupaj naj-
večji dohodek? Nalogi ustreza tabela:
Stružni ce Var il ni število
aparati delavcev
Strugarji 1000 600 20
Varilci 800 1100 10
število 17 13
strojev
Optima lna rešitev :
17
O
3
10 ; 29 800 din
Na loga . Pri tej nalogi presodi, koliko lahko pripomore kape-
tan k uspehu šahovskega moštva. Domače moštvo šahovskega kluba
"Milan Vidmar" ima 3 enako močne mojstre (M) in 7 enako močnih
mojstrskih kandidatov ( K). Gostujoče moštvo šah ovskega kluba
"Vasja Pirc" ima 6 enako močnih mojstrov in 4 enako močne moj-
strske kandidate. Domač mojster se lahko nadeja, da bo dobil
povprečno v partiji z gostujočim mojstrom po 0,4 točke, v par-
12
ti ji z gos tu jo č i m mo j s trs ki m kandidato m pa 0 ,9 to č ke ; domač
moj s tr s ki kan d ida t l ah ko upa , da bo dobi l po v p r e č no ~ parti ji z
go s tuj očim mojstr om po 0 ,3 t o č k e, v pa r tij i z g o s t u j o č i m moj-
strskim kand id atom pa 0 ,5 to čk e . Ti podatk i s o z bra ni v tabeli:
"V asja Pir c "
Mojst r i Mo j s trsk i St evil o
kand i da t i i gral cev
" ~l i lan Mojs tri 0 ,4 0,9 3
Vidmar" Moj s t r s ki 0 , 3 0,5 7
kandida ti
š t ev i l o i gr a lcev 4 6
Kapetan domačega mo š tv a ve , da bo r a zv r stil nas pr ot ni ka pe-
tan s voj e moštvo po m oči igr al cev in sic e r na pr ve š t i r i deske
mojs t re i n na zadnj i h šest des k mojstrske ka nd i da t e . Kako na j
r a z pore di ka pe t a n dom a č e mo št vo , da bodo do segli kar največ
t očk , č e sme razporejati i gr al ce po de s kah ne gl ede na šahov sko
ka t egor i jo? Kate r a ra zp or ed i t ev je najbo lj "n e sreč na"?
Reš i t e v. Na jbo lj ugodno i n naj bolj ne ugod no r a zpor ed i t ev po-
daja tabela:
Na jbol j lIs r e čn a ll Naj bol j lIn es re čna ll
r az poredi t e v razporeditev
Deska M. Vidmar V. Pi rc M. Vidmar V. Pirc
1 K M M M
2 K M M M
3 K M M M
4 K M K M
5 K K K K
6 K. K K K
7 K K K K
8 M K K K
9 M K K K
10 M K K K
Pri č a kov a n o
število 5 ,4 4,6 4 ,5 5 ,5
toč k
Alo jzi j Vadnal
13