Opkut

Országok listájaHungaryMiskolci EgyetemGépészmérnöki és Informatikai KarGazdaságinformatikusOperációkutatásOpkut

Futószalagfeladat: ~ban olyan megoldást keresünk, amelyre egy, a problémát meghatározó mennyiség a lehetQ legkisebb legyen. (elnevezés általában szqk keresztmetszet feladatok). Jelölje I1,& , Ii,& , In a személyeket, J1,& ,Jj,& , Jn a futószalagokon levQ munkahelyeket, munkákat. Legyen adva az alábbi táblázat, amelynek tije"0 (egész) eleme azt jelenti, hogy az Ii munkás a Jj munkát mennyi idQ alatt tudja elvégezni. A személyek, és a munkák számának azonosnak kell lennie.
J1 Jj Jn I1 t11 t1j t1n Ii ti1 tij tin In tn1 tnj tnn A futószalag-feladat megfogalmazása: Rendeljük a személyeket a futószalag munkahelyeihez kölcsönösen egyértelmq módon úgy, hogy a futószalag ütemideje a lehetQ legkisebb legyen. A futószalag ütemidejét, azaz azt az idQt, amikor a futószalag tovább indulhat a leghosszabb mqveleti idQ határozza meg. A hozzárendelést olyan xij döntési változóval jelöljük, melynek értéke xij=1, ha Ii hozzá van rendelve Jj munkához, és xij=0, ha nincs.
Matematikailag: meghatározandó xij úgy, hogy xij=0 vagy 1 minden (i,j) indexpárra  EMBED Equation.3 (i=1,…,n),  EMBED Equation.3 (j=1,…,n) feltételek teljesülése mellett a  EMBED Equation.3  minimális legyen.
Gomory-féle vágás: (1958). A vágási módszer lényege: ha a feladat megoldásakor kapott optimum nem rácspont, a megoldások halmazát szqkítjük  új feltételt vezetünk be, amely levág egy optimumot is tartalmazó szeletet a folytonos tartományból  ezt addig ismételjük, míg az optimum rácspont nem lesz!
Vágási feltétel megfogalmazása: Tekintsük a folytonos feladat optimális megoldását tartalmazó szimplex táblát.
xj xr trj xBr - - Ha minden döntési változó egész akkor = integer optimum. Ha nem tekintsük az optimális szimplex táblának azt a sorát, amelyben a megoldás tört érték. A szimplex tábla ezen sorából kiolvasható egyenlet:  EMBED Equation.3 .Minden törtszám felírható egészrésze és törtrésze összegeként. Egészrész: számtól nem nagyobb legnagyobb egész szám [w]. Törtrész: w-[w], ami mindig 0d" w <1.  EMBED Equation.3 ahol 0
Szállítási feladat: a szállítási feladatpár: Legyenek adottak a T1,& , Ti,& , Tn termelQk, amelyek rendre az a1,& ,ai,& , an kínálattal rendelkeznek és az F1,& ,Fj,& ,Fn fogyasztók, amelyek kereslete a b1,& ,bj,& ,bn, adottak még cij szállítási egységköltségek, amelyek Ti termelQtQl Fj fogyasztóhoz történQ egységnyi mennyiségq áru szállítási költségét jelenti. A megadott adatok nemnegatív egészek.
b1 bj bn F1 Fj Fn a1 t1 c11 c1j c1n ai ti ci1 cij cin an tn cn1 cnj cnn Tegyük fel, hogy összkínálat=összkereslettel, azaz EMBED Equation.3  . Ezt az összefüggést kereslet- kínálat egyensúyának is szokás nevezni.
Primál feladat: Határozzuk meg a szállítást, amely a keresletet és a kínálatot kielégíti és a szállítási összköltség minimális feltéve, hogy a szállítási ktg arányos a szállítási mennyiséggel. Jelölje xij a Ti termelQtQl az Fj fogyasztóhoz szállítandó mennyiséget. A kínálat-kereslet kielégítése azt jelenti, hogyhogy minden termelQtQl a kínálatának megfelelQ mennyiséget el kell szállítani, azaz bármelyik Ti termelQtQl az összes fogyasztóhoz szállított mennyiség összege egyenlQ legyen a Ti termelQ kínálatával. Matematikailag: meghatározandók xij egész számok úgy, hogy  EMBED Equation.3  minden ij-re  EMBED Equation.3  (i=1,& ,m)  EMBED Equation.3  (j=1,& ,n) feltételek teljesülése mellett a  EMBED Equation.3  minimális legyen.
Duál feladat: Tegyük fel, hogy van egy vállalkozó, aki Ti termelQtQl ui áron felvásárolja az áru egységét, majd elszállítja az Fj fogyasztó és ott vj áron eladja a Ti termelQnek. Az ui, vj felvásárlási illetve eladási egységáraknak olyannak kell lenniük, hogy a termelQnek megérje a vállalkozóval való szállítás. (olcsóbb, mintha maga csinálná). vj-uid"cij  minden lehetséges szállítási viszonylatban fenn kell állnia. A vállalkozó megkapja az összes szállítást, az árrendszert úgy fogja meghatározni, hogy max. árbevétele legyen, amit a bevételeinek és kiadásainak különbsége ad meg. Matematikailag: meghatározandók az u1, u2,& , um és v1, v2,& , vn egész számok úgy, hogy vj-uid"cij minden i,j-re feltételek teljesülése mellett a  EMBED Equation.3  maximális legyen.
Szállítási feladatpár alaplemmája: Ha az xij kielégíti a primál feltételeket (azaz xij lehetséges szállítás) és ui, vj kielégíti a duál feltételekt (azaz ui, vj lehetséges árrendszer) akkor  EMBED Equation.3 , egyenlQség akkor és csak akkor áll fenn, ha minden (i, j) indexpárra (cij+ui-vj)xij=0. Biz.: a bizonyítás során elQször a duál majd a primál feltételeket használtuk fel: EMBED Equation.3 
 EMBED Equation.3 . A két oldal akkor és csak akkor lehet egyenlQ, ha a fenti bizonyításban szereplQ e" egyenlQtlenség egyenlQséggel teljesül, azaz  EMBED Equation.3 , amelybQl átrendezéssel kapjuk, hogy  EMBED Equation.3 . Mivel a fenti összeg minden tagjában mindkét tényezQ a primál és a duál feltételek miatt nemnegatív, ezért az összeg mindegyik tagja nemnegatív. Az összeg pedig akkor és csak akkor lehet zérus, ha mindegyik tagja zérus, azaz minden (i,j) indexpárra: (cij+ui-vj)xij=0.
Szimplex módszer elQbbrehaladási tétele: (1947 Dautzig): A pivot elem választás és pivotálás után: újra primál megengedett táblát kapok (1), az új célfüggvény nem romlik (primál célfüggvény nem növekszik). Biz.:
as b ai tis xi ar trs xr zs-cs z0 Pivot elem legyen trs>0. (1) pivotálás után Ax =b azt kell belátni, hogy x e"0 (b oszlopban minden elem e"0) EMBED Equation.3 , i`"r,  EMBED Equation.3 xs e"0, mert xre"0 és trs>0. xi e"0 is fennáll olyan i indexekre, ahol tisd"0. Azokra az i indexekre, amelyekre tis>0  EMBED Equation.3  átrendezett összefüggésbQl könnyen látható, hogy az xi e"0 akkor áll fenn, ha  EMBED Equation.3 , igaz, mert ez alapján választottuk a pivot elemet. (2) a pivotálás utáni z0 célfv. érték a pivotálási képletekbQl és (zs-cs)>0-ból  EMBED Equation.3 . A z0=cx célfv. értéke nem romlik, általában csökken (csak akkor nem csökken, ha xr=0, azaz ha a bázismegoldás degenerált. xre"0, trse"0, zs-cse"0.

Duál elQbbrehaladási tétele: A duál módszer belépési és kilépési kritériumának alkalmazásával: (1)újra lehetséges duál megoldást kapunk, (2) a duál célfv. értéke nem csökken.
aj as b ar trj trs xr zj-cj zs-cs z0 Pivot elem trsd"0. (1) azt kell belátni, hogy a vizsgált sorban minden elem d"0.  EMBED Equation.3 , trs<0 és zj-cjd"0. zj -cjd"0 minden j elemre. Azokra a j indexekre, ahol trje"0"`bt v | ~ € ‚ Œ Ž ° ² º ¼ Æ È |
€
‚
Î
Ð
æ
è
¬
´
¶
º
¼
À
Â
È
Ê
Î
Ò
Ö
Ú
Þ
â
è
ê
î
ò
ö
ú
þ

















"

&

N

n

¬ ²


óèÝèÑèÝèÑèÑèÑèÑèÑèÑÝèÑèÑèƺƺƺƺƺƺƺƺƺƺƺƺƺƺƺƬžèÑèÝhõ6¡háC6>*CJ
aJ
hõ6¡h#¶6>*CJ
aJ
hõ6¡hk1kCJ
H*aJ
hõ6¡hk1kCJ
aJ
hõ6¡háCCJ
H*aJ
hõ6¡hbêCJ
aJ
hõ6¡háCCJ
aJ
hõ6¡háC5CJ
aJ
>°
²
¸
¾
Ä
Æ
Ì
Ô
÷îîîîKîî¢kd$$If–FÖ ”îÖ\”ÿØVµ3Dÿÿÿÿÿÿÿÿÿÿÿÿ~ÿÿÿÿÿÿÿÿÿÿÿÿ_ÿÿÿÿÿÿÿÿÿÿÿÿ~ÿÿÿÿÿÿÿÿ
tàÖ0ÿÿÿÿÿÿ ö6ööÖÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÖÿÿÿÿÿÿÿÿÿÿÿÿÿÖÿÿÿÿÿÿÿÖÿÿÿÿÿÿÿÿÿÿÿÿÿ4Ö4Ö
laö $Ifgdk1k $a$gdR'ˆ¯ýÔ
Ü
ä
æ
ì
ô
ü


ööSöööö¢kd$$If–FÖ ”îÖ\”ÿØVµ3Dÿÿÿÿÿÿÿÿ~_~
tàÖ0ÿÿÿÿÿÿ ö6ööÖÿÿÿÿÿÿÿÖÿÿÿÿÖÿÿÿÿÿÿÿÖÿÿÿÿ4Ö4Ö
laö $Ifgdk1k











$

\SSSS $Ifgdk1k¢kd$$If–FÖ ”îÖ\”ÿØVµ3Dÿÿÿÿÿÿÿÿ~_~
tàÖ0ÿÿÿÿÿÿ ö6ööÖÿÿÿÿÿÿÿÖÿÿÿÿÖÿÿÿÿÿÿÿÖÿÿÿÿ4Ö4Ö
laö$

&

Œ¦¦C D \TLTTC $IfgdÃoù $a$gdüe $a$gdR'¢kd
$$If–FÖ ”üÖ\”ÿØVµ3Dÿÿÿÿÿÿÿÿ~_~
tàÖ0ÿÿÿÿÿÿ ö6ööÖÿÿÿÿÿÿÿÖÿÿÿÿÖÿÿÿÿÿÿÿÖÿÿÿÿ4Ö4Ö
laö

"`jlprt~ŠŒÌÐèì,-./:;NOPQ\|}óèÝÑèÝèóèÝèÆÝƺƺƯ èŽ} è èkZ èÆ è!j}hõ6¡hüeCJ
EHäÿUaJ
#jñ¥J
hõ6¡hbêCJ
UVaJ
!jhõ6¡hüeCJ
EHâÿUaJ
#j¨¥J
hõ6¡hbêCJ
UVaJ
jhõ6¡hbêCJ
UaJ
hõ6¡hR'CJ
aJ
hõ6¡hÇ(ªCJ
H*aJ
hõ6¡hÇ(ªCJ
aJ
hõ6¡háCCJ
H*aJ
hõ6¡háCCJ
aJ
hõ6¡hbêCJ
aJ
hõ6¡hbêCJ
H*aJ
"‘’“ž¦·\^¤¦B E F J K M O Q S V X c h m „ £ ¥ ­ » Ä 467JKíÜÍ·«· ·•·•‰•‰•‰•‰•~ ~•·•·•·•·•o•]#j|¬J
hõ6¡h|5ÀCJ
UVaJ
jhõ6¡h5#JCJ
UaJ
hõ6¡h« *CJ
aJ
hõ6¡h5#JCJ
H*aJ
hõ6¡h5#JCJ
aJ
hõ6¡hÆy%CJ
aJ
hõ6¡hÇ(ª5CJ
aJ
hõ6¡hÇ(ªCJ
aJ
hõ6¡hbêCJ
aJ
jhõ6¡hbêCJ
UaJ
!j÷hõ6¡hüeCJ
EHðÿUaJ
#js¦J
hõ6¡hk1kCJ
UVaJ
#D G H I L P T óóTKóK $IfgdÃoùžkd‹
$$If–FÖ ”ÈÖF”ÿ»§€'ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ€ìÿÿÿÿÿÿÿÿÿÿÿÿ€vÿÿÿÿÿÿÿÿÿÿÿÿ
tàÖ0ÿÿÿÿÿÿ öööÖ

ÿÿÿÿÿÿÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÿÿÿÿÿÿ4Ö4Ö
laöpÖÿÿÿÿÿÿÿÿÿÿÿÿÿÿ

$$Ifa$gd5#JT U V j k `WQQ$If $IfgdÃoùžkdD

$$If–FÖ ”–ÖF”ÿ»§€'ÿÿÿÿÿÿÿÿÿÿÿÿ€ì€v
tàÖ0ÿÿÿÿÿÿ öööÖ

ÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÖ

ÿÿÿ4Ö4Ö
laöpÖÿÿÿÿÿÿÿÿÿÿÿÿÿÿk l ðò
qigiaaaaa$If $a$gdR'Žkdï

$$If–FÖ ”ÖF”ÿ»§'ÿÿÿÿÿÿÿÿÿÿÿÿìv
tàÖ0ÿÿÿÿÿÿ öööÖ

ÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÖ

ÿÿÿ4Ö4Ö
laö KLMN8:<>NR^bfhŽ’”ü¼¾äîßÔɾɯ¾Œ¯¾€¾€¾¯¾n]¯RÉCRjhõ6¡h²JbCJ
UaJ
hõ6¡h²JbCJ
aJ
!j9hõ6¡hüeCJ
EHàÿUaJ
#jã®J
hõ6¡h²JbCJ
UVaJ
hõ6¡h|5ÀCJ
H*aJ
!j hõ6¡hüeCJ
EHàÿUaJ
#jQ­J
hõ6¡h|5ÀCJ
UVaJ
jhõ6¡h|5ÀCJ
UaJ
hõ6¡h|5ÀCJ
aJ
hõ6¡hÇ(ªCJ
aJ
hõ6¡h5#JCJ
aJ
jhõ6¡h5#JCJ
UaJ
!js
hõ6¡hüeCJ
EHàÿUaJ
äæèêôöVZdÐÒøúüþ„†ØòN\îðò NtvíÜͶ¶«Í™ˆÍ«Â«Â«Â«Â«}«qeZ«Nhõ6¡hl«CJ
H*aJ
hõ6¡h’ CJ
aJ
hõ6¡h’ 5CJ
aJ
hõ6¡hl«5CJ
aJ
hõ6¡hÇ(ªCJ
aJ
!jþhõ6¡hüeCJ
EHàÿUaJ
#j[°J
hõ6¡h²JbCJ
UVaJ
hõ6¡hl«CJ
aJ
hõ6¡h²JbCJ
H*aJ
hõ6¡h²JbCJ
aJ
jhõ6¡h²JbCJ
UaJ
!jchõ6¡hüeCJ
EHàÿUaJ
#j˜¯J
hõ6¡h²JbCJ
UVaJ
v€‚ŒŽ¤ÊÌÔÖàâ"$,.68|~†ˆ’°´28è



- "$&(*,/023579;=?BCEFHJLNPRT^õéõéÞõéõéõéõéõéõéõéõéõéõéõéõéõÞõÞõÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓÇÓõhõ6¡hR'CJ
H*aJ
hõ6¡hR'CJ
aJ
hõ6¡h’ CJ
aJ
hõ6¡hl«CJ
H*aJ
hõ6¡hl«CJ
aJ
N ICCCCC$Ifµkdš$$If–FÖ ”Ör”ÿ¯ºîKïÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿáÿÿÿÿÿÿÿÿÿÿÿÿý
tàÖ0ÿÿÿÿÿÿ ö6ööÖ ÿÿÿÿÿÿÿÿÿÿÿÖ ÿÿÿÿÿÿÿÿÿÿÿÖ ÿÿÿÿÿÿÿÿÿÿÿÖ ÿÿÿÿÿÿÿÿ4Ö4Ö
laö!%)-ICCCCC$Ifµkdi$$If–FÖ ”îÖr”ÿ¯ºîKïÿÿÿÿÿÿÿÿÿÿÿÿáÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿýÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ
tàÖ0ÿÿÿÿÿÿ ö6ööÖ ÿÿÿÿÿÿÿÿÿÿÿÖ ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÖ ÿÿÿÿÿÿÿÿÖ ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ4Ö4Ö
laö-.148<@ICCCCC$Ifµkdb$$If–FÖ ”îÖr”ÿ¯ºîKïÿÿÿÿáÿÿÿÿÿÿÿÿý
tàÖ0ÿÿÿÿÿÿ ö6ööÖ ÿÿÿÿÿÿÿÿÖ ÿÿÿÿÿÖ ÿÿÿÿÿÿÿÿÿÿÿÖ ÿÿÿÿÿ4Ö4Ö
laö@ADGKOSICCCCC$Ifµkd1$$If–FÖ ”Ör”ÿ¯ºîKïÿÿÿÿÿÿÿÿáÿÿÿÿÿÿÿÿý
tàÖ0ÿÿÿÿÿÿ ö6ööÖ ÿÿÿÿÿÿÿÿÿÿÿÖ ÿÿÿÿÿÖ ÿÿÿÿÿÿÿÿÿÿÿÖ ÿÿÿÿÿ4Ö4Ö
laöSTæB$$*z-n1IAA999 $a$gdô>€ $a$gdFQµkdä$$If–FÖ ”Ör”ÿ¯ºîKïÿÿÿÿáÿÿÿÿÿÿÿÿý
tàÖ0ÿÿÿÿÿÿ ö6ööÖ ÿÿÿÿÿÿÿÿÿÿÿÖ ÿÿÿÿÿÖ ÿÿÿÿÿÿÿÿÖ ÿÿÿÿÿ4Ö4Ö
laö^†‡š›œæô°-²-¶- $ ü Ž!!4"6"^"b"¤"ª"Ø"Ú"##õæõÔÃæõµªžªžªžª“‡“‡“ª|p|a“O#j‡¶J
hõ6¡hR'CJ
UVaJ
jhõ6¡hR'CJ
UaJ
hõ6¡hkwOCJ
H*aJ
hõ6¡hkwOCJ
aJ
hõ6¡hR'CJ
H*aJ
hõ6¡hR'CJ
aJ
hõ6¡hl«CJ
H*aJ
hõ6¡hl«CJ
aJ
hõ6¡hl«6>*CJ
aJ
!j¥-hõ6¡hüeCJ
EHâÿUaJ
#j™³J
hõ6¡h’ CJ
UVaJ
jhõ6¡h’ CJ
UaJ
hõ6¡h’ CJ
aJ
###"#$#J#L#N#P#R#f#h#Ž##’#”#ì#î# $$$$<$>$@$îßÔÅÔ³¢Å—ÔÅԅtÅÔÅÔbQÅԗF hõ6¡hl«CJ
aJ
!j])hõ6¡hüeCJ
EHâÿUaJ
#j=·J
hõ6¡h- CJ
UVaJ
!jå&hõ6¡h- CJ
EHäÿUaJ
#jò¶J
hõ6¡h- CJ
UVaJ
hõ6¡hkwOCJ
aJ
!jm$hõ6¡h- CJ
EHâÿUaJ
#j³¶J
hõ6¡h- CJ
UVaJ
jhõ6¡h- CJ
UaJ
hõ6¡h- CJ
aJ
jhõ6¡hR'CJ
UaJ
!j4"hõ6¡hR'CJ
EHòÿUaJ
@$B$Z$²$´$Î$Ð$B%D%°%²%¸%º%¸&ø&ú&þ&''''n'x'~'„'ð())$)&)0)2)<)>)D)F)P)R)„)†)Š)Œ))–)ô)ö) ****$*%*6*õçÜÐÜÐÜÐÜÐÜÐÜõÐÜÐõÜÐÜõÜõÜõÄõÄõÄõÄõÄõÄõÄõÄõÄõµõ£’µõ„çhõ6¡hFQ6>*CJ
aJ
!jç+hõ6¡hMF‰CJ
EHâÿUaJ
#jµ¸J
hõ6¡hMF‰CJ
UVaJ
jhõ6¡hFQCJ
UaJ
hõ6¡hFQCJ
H*aJ
hõ6¡hkwOCJ
H*aJ
hõ6¡hkwOCJ
aJ
hõ6¡hkwO6>*CJ
aJ
hõ6¡hFQCJ
aJ
46*9*E*N*P*n*o*x*z*•*–*™*š*á*â*ã*ö*÷*ø*ù*û*„,ˆ,Œ,Ž,’,”,˜,œ,H-J-p-r-t-v-x-òäÙÍÙÂÙÍÙÍÙÍÙ³¡³ÂÙÍÙÍÙÍÙÍÙ³Â~m³b hõ6¡hÆy%CJ
aJ
!j‚1hõ6¡hüeCJ
EHâÿUaJ
#jËàJ
hõ6¡hÆy%CJ
UVaJ
!j.hõ6¡hüeCJ
EHâÿUaJ
#j;¹J
hõ6¡hMF‰CJ
UVaJ
jhõ6¡hMF‰CJ
UaJ
hõ6¡hMF‰CJ
aJ
hõ6¡hkwOCJ
H*aJ
hõ6¡hkwOCJ
aJ
hõ6¡hkwO6>*CJ
aJ
hõ6¡hMF‰6>*CJ
aJ
#x-z-|-¢-¤-¦-¨-¬-N.R.ª.¬.Ò.Ô.Ö.Ø.$/&/L/N/õæÛɸ止­¢“­p“­aVD#já»J
hõ6¡hYCJ
UVaJ
hõ6¡hYCJ
aJ
jhõ6¡hYCJ
UaJ
!j¾7hõ6¡hüeCJ
EHâÿUaJ
#jd»J
hõ6¡hMF‰CJ
UVaJ
jhõ6¡hMF‰CJ
UaJ
hõ6¡hkwOCJ
aJ
hõ6¡hMF‰CJ
aJ
!j”4hõ6¡hüeCJ
EHâÿUaJ
#jÊàJ
hõ6¡hÆy%CJ
UVaJ
hõ6¡hÆy%CJ
aJ
jhõ6¡hÆy%CJ
UaJ
hõ6¡hüeCJ
aJ
N/P/R/X/N1R1V1X1\1^1b1f1l1n1¼1|2„233(3*3.3236383>3@3D3H3L3N3V3X3\3^3b3d3h3Ž3’3<4>4îßÔɽɽɽɽɲ¦››„›„›„›„›„›„›„›„›„›„›xijhõ6¡hµkCJ
UaJ
hõ6¡hµkCJ
H*aJ
hõ6¡hô>€CJ
H*aJ
hõ6¡hµkCJ
aJ
hõ6¡hô>€CJ
aJ
hõ6¡hô>€5CJ
aJ
hõ6¡hl«CJ
aJ
hõ6¡hkwOCJ
H*aJ
hõ6¡hkwOCJ
aJ
hõ6¡hYCJ
aJ
jhõ6¡hYCJ
UaJ
!jÊ:hõ6¡hüeCJ
EHâÿUaJ
)n133 3$3&3,343:3÷ëëë[ëëëkd¸=$$If–FÖ ” ÖF”ÿ6§¢ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿqÿÿÿÿÿÿÿÿÿÿÿÿvÿÿÿÿÿÿÿÿÿÿÿÿ
tàÖ0ÿÿÿÿÿÿ ö6ööÖ

ÿÿÿÿÿÿÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÿÿÿÿÿÿ4Ö4Ö
laö

$$Ifa$gdô>€ $a$gdô>€:3<3B3J3P3occc

$$Ifa$gdô>€kd[>$$If–FÖ ” ÖF”ÿ6§¢ÿÿÿÿÿÿÿÿÿÿÿÿqÿÿÿÿvÿÿÿÿ
tàÖ0ÿÿÿÿÿÿ ö6ööÖ

ÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÿÿÿÿÿÿÖ

ÿÿÿ4Ö4Ö
laöP3R3T3`3f3occc

$$Ifa$gdô>€kd

?$$If–FÖ ”,ÖF”ÿ6§¢ÿÿÿÿÿÿÿÿÿÿÿÿqÿÿÿÿvÿÿÿÿ
tàÖ0ÿÿÿÿÿÿ ö6ööÖ

ÿÿÿÿÿÿÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÖ

ÿÿÿ4Ö4Ö
laöf3h3à8â8B:D:J:P:T:oggg[[[[

$$Ifa$gdˆl] $a$gdô>€kd½?$$If–FÖ ”,ÖF”ÿ6§¢ÿÿÿÿÿÿÿÿÿÿÿÿqv
tàÖ0ÿÿÿÿÿÿ ö6ööÖ

ÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÖ

ÿÿÿÿÿÿÖ

ÿÿÿ4Ö4Ö
laö>4d4f4h4j4n4x4z4 4¢4¤4¦4¨4ª4À4Â4Ð4Ô4Þ4à4054585<5€5„5Š5Œ5²5´5õãÒÃõ¸©¸—†©¸z¸z¸z¸z¸z¸o¸z¸©¸]#j¯ÂJ
hõ6¡hè}CJ
UVaJ
hõ6¡hè}CJ
aJ
hõ6¡h£9%CJ
H*aJ
!jÒBhõ6¡h£9%CJ
EHâÿUaJ
#jÕÀJ
hõ6¡h£9%CJ
UVaJ
jhõ6¡h£9%CJ
UaJ
hõ6¡h£9%CJ
aJ
jhõ6¡hµkCJ
UaJ
!jD@hõ6¡hµkCJ
EHâÿUaJ
#jë¾J
hõ6¡hµkCJ
UVaJ
hõ6¡hµkCJ
aJ
´5¶5¸5$6&6T6V6|6~6€6‚677v7x7|7~7Ž77¶7¸7º7¼7Æ7È7b8d8¶8¸8Â8Æ8Ð8Ò8Ö8Ø8Þ8à8îßÔÈÔ¹Ô§–¹ÔÈÔÈÔÈԹԄs¹ÔÈÔÈÔÈÔÈÔÈÔÈÔh hõ6¡hô>€CJ
aJ
!jJhõ6¡hè}CJ
EHâÿUaJ
#j<ÄJ
hõ6¡hè}CJ
UVaJ
!j
Hhõ6¡hè}CJ
EHâÿUaJ
#jTÃJ
hõ6¡hè}CJ
UVaJ
jhõ6¡hè}CJ
UaJ
hõ6¡hè}CJ
H*aJ
hõ6¡hè}CJ
aJ
jhõ6¡h£9%CJ
UaJ
!j=Ehõ6¡hè}CJ
EHàÿUaJ
$à8â899b9¦9´9ú9F:H:L:N:X:Z:^:b:x:z:~:€:„:†:Š:Œ::’:°:´:¼:Â:6;8;^;`;b;d;j;n;|;~;‚;„;Ž;;–;˜;ú;ü;<‚óçÜÑÆÑÆѺѺѺѺѺѺѺѺѺѺÑÆѫљˆ«ÑºÑºÑºÑºÑºÑºÑ†U!jtOhõ6¡hüeCJ
EHâÿUaJ
#jKÇJ
hõ6¡hˆl]CJ
UVaJ
jhõ6¡hˆl]CJ
UaJ
hõ6¡hˆl]CJ
H*aJ
hõ6¡h(@CJ
aJ
hõ6¡hˆl]CJ
aJ
hõ6¡hè}CJ
aJ
hõ6¡hè}5CJ
aJ
hõ6¡hˆl]5CJ
aJ
1T:V:\:d:l:r:\PPPP

$$Ifa$gdˆl]¢kd\M$$If–FÖ ”»Ö\±ï€ïÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ€˜ÿÿÿÿÿÿÿÿÿÿÿÿ€ôÿÿÿÿÿÿÿÿÿÿÿÿ€ôÿÿÿÿÿÿÿÿÿÿÿÿ
tàÖ0ÿÿÿÿÿÿ ö6ööÖÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÖÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÖÿÿÿÿÿÿÿÖÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ4Ö4Ö
laölr:t:v:‚:Ž:”:\PPPP

$$Ifa$gdˆl]¢kdN$$If–FÖ ”“Ö\±ï€ïÿÿÿÿÿÿÿÿÿÿÿÿ€˜€ô€ô
tàÖ0ÿÿÿÿÿÿ ö6ööÖÿÿÿÿÿÿÿÖÿÿÿÿÿÿÿÖÿÿÿÿÿÿÿÖÿÿÿÿ4Ö4Ö
laöl”:–:¬†®†¾‰8þ¨‘¸“²–\TTTTTTTT $a$gdô>€¢kdÔN$$If–FÖ ”ÕÖ\±ï€ïÿÿÿÿÿÿÿÿÿÿÿÿ€˜€ô€ô
tàÖ0ÿÿÿÿÿÿ ö6ööÖÿÿÿÿÿÿÿÖÿÿÿÿÿÿÿÖÿÿÿÿÿÿÿÖÿÿÿÿ4Ö4Ö
laöl és tri<0  EMBED Equation.3 átrendezett összefüggésbQl könnyen belátható, hogy az zj -cjd"0 akkor áll fenn, ha  EMBED Equation.3 , ami pontosan a belépési kritériumnak felel meg. Tehát a belépési kritériummal azt biztosítjuk, hogy a pivotálás után újra duál megengedett szimplex táblát kapjunk. (2) a pivotálás utáni zo célfv. érték a pivotálási képletekbQl és xr<0-ból  EMBED Equation.3 z0=yb duál cél fv. érték általában növekszik, abban az esetben nem növekszik csupán, ha zs-cs=0. Tehát a kilpési kritériummal azt biztosítjuk, hogy a duál feladat célfv.-ének értéke ne romoljon.

Externális pont: Az  EMBED Equation.3 pont a C konvex halmaz externális pontja, ha a C-nek nincs olyan két pontja, hogy az  EMBED Equation.3 pont a két pontot összekötQ szakasz belsQ pontja legyen. Képletben megfogalmazva az  EMBED Equation.3 pont a C halmaz externális pontja, ha nincs olyan  EMBED Equation.3 és  EMBED Equation.3 , amelyre  EMBED Equation.3 .
Externális irány: A C konvex halmazban egy d nemzérus vektort iránynak nevezünk, ha minden  EMBED Equation.3 ponthoz tartozó  EMBED Equation.3 pont is a C konvex halmaz eleme minden  EMBED Equation.3 esetén. A C konvex halmaz egy d irányvektorát externális iránynak nevezzük, ha C-nek nincs olyan két, nem egyirányba mutató irányvektora, hogy a d irány a két irány között legyen. (externális iránya korlátos halmaznak nem lehet).
Konvex politop: konvex politopnak azt a konvex poliédert nevezzük, amely korlátos. A konvex politpot a korlátosság miatt minden oldalról hipersíkok határolják. Bármely pontja felírható a csúcspontjainak (externális pontjainak) konvex lineáris kombinációjaként. Csúcspontjai: x1, x2, & , xm, akkor tetszQleges x pontja felírható:  EMBED Equation.3 .
Konvex poliéder: véges sok féltér metszetét konvex poliédernek nevezzük. A konvex poliéder egy speciális konvex halmaz és ennek az externális pontjait csúcspontoknak vagy csúcsoknak nevezzük. Pl.: Ax=b, Ax=b xe"0.
Konvex kónusz: véges sok homogén féltér metszetét konvex kónusznak nevezzük. Ez egy speciális konvex poliéder, amely az origót mindig tartalmazza. Összes externális irányt d1, d2, & , dk jelöli, akkor egy konvex kónusz tetszQleges x pontja:  EMBED Equation.3 
Karakterizációs tétel: Legyen adott egy konvex poliéder az Ax=b, xe"0 formában. Konvex poliéder externális pontjai: x1, x2, & , xk, konvex poliéder externális irányai: d1, d2, & , dp. A konvex poliéder tetszQleges x pontja felírható az externális pontok konvex lineáris kombinációjaként és az externális irányok nemnegatív lineáris kombinációjának összegeként EMBED Equation.3 .
Standard LP feladatpár+alaplemma: Feltételi fv.-ek és a célfv. is lineáris. Standard alak: minden feltétel egyenlQséggel van megfogalmazva az ismeretlenekre nemnegativitási feltétel van kikötve, és a célfv. minimumát keressük. Primál: Ax=b, xe"0, cx min. Duál: yAd"c, yb max. Alaplemma: célfv.-ek kapcsolatát fejezi ki. Ha  EMBED Equation.3 és  EMBED Equation.3 , akkor cxe"yb és egyenlQség akkor és csak akkor áll fenn, ha  EMBED Equation.3 minden j indexre. Biz.: ha  EMBED Equation.3 , akkor yAd"c teljesül. Szorozzuk be az egyenlQtlenséget az xe"0 vektorral, ekkor (yA)xd"cx, amellyel ekvivalens az y(Ax)d"cx. Ha x olyan, hogy az xe"0 mellett az Ax=b is teljesül, azaz  EMBED Equation.3 , akkor az elQzQ egyenlQtlenségbQl a bizonyítandó ybd"cx összefüggés adódik. Az egyenlQség bizonyításához az (yA)xd"cx összefüggésbQl indulunk ki és rendezzük (yA-c)xd"0 alakra, amely felírható a következQ alakban:  EMBED Equation.3 . A szummában szereplQ tényezQk közül  EMBED Equation.3  és  EMBED Equation.3 miatt yaj-cjd"0, xje"0, így e tényezQk szorzata nem pozitív. Nempozitív tagok összege pedig akkor és csak akkor lehet zérus, ha mindegyik tag zérus, vagyis ha (yaj-cj)xj=0, minden j=1, 2, & , n indexre. Alaplemma következménye: ha  EMBED Equation.3  és  EMBED Equation.3 és cx*=by*, azaz a két feladat célfv.-nek értéke megegyezik, akkor x* és y* megoldások optimálisak.
Hozzárendelési feladatpár: jelölje I1, I2,& , In a személyeket, J1, J2, & , Jn a munkahelyeket. Legyen adva az alábbi táblázat, amelynek tije"0 eleme azt jelenti, hogy az Ii munkás a Jj munkát mennyi idQ alatt tudja elvégezni. A személyek és a munkák számának azonosnak kell lennie.
J1 Jj Jn I1 t11 t1j t1n Ii ti1 tij tin In tn1 tnj tnn Primál feladat: Rendeljük a személyeket a munkahelyekre úgy, hogy egy személy egy munkahelyen dolgozzon, egy munkahelyre egy személy kerüljön és a munkavégzés összideje a lehetQ legkisebb legyen. A hozzárendelést egy xij döntési változóval jelöljük. Legyen xij=1, ha az Ii személy hozzá van rendelve a Jj munkához és xij=0, ha az Ii személy nincs hozzárendelve a Jj munkához. Az a feltétel, hogy az Ii személy egy munkahelyen dolgozzon úgy fogalmazható meg, hogy az xij döntési változók i-edik sorbeli összege1. Az a feltétel pedig, hogy a Jj munkát egy személy végezze úgy fogalmazható meg, hogy az xij döntési változók j-edik oszlopbeli összege 1. A munkavégzés összidejét azon tij idQértékek összege adja, amelyekre xij=1, ez pedig ekvivalens a t11x11+t12x12+& +tnnxmm összeggel. Matematikailag: meghatározandó xij úgy, hogy xij=0 vagy 1 minden (i,j) indexpárra  EMBED Equation.3 (i=1,& ,n),  EMBED Equation.3 (j=1,& ,n) feltételek teljesülése mellett a  EMBED Equation.3 minimális legyen. A hozzárendelési feladat a szállítási feladat azon speciális esete, amikor minden ai=1 és minden bj=1.
Duál feladat: A hozzárendelési feladat duál feladata a szállítási feladat duál feladatából könnyen származtatható és az alábbi alakban írható: meghatározandók az u1, u2,& ,un és v1, v2,& , vn egész számok úgy, hogy vj-uid"tij minden (i,j) indexpárra feltételek teljesülése mellett a  EMBED Equation.3 maximális legyen.

Hasonló témájú dokumentumok

Kidolgozott feladatok

- 2012-01-22 08:52:51

Lineáris algebra és operációkutatás

- 2009-02-01 19:21:33

A mások által feltöltött dokumentumokat értékelheted. Ha úgy ítéled meg, hogy a vizsgára való felkészülés szempontjából hasznos volt egy dokumentum, akkor adj rá sokcsillagos értékelést.
Ha hibákat tartalmaz, vagy egyéb probléma van vele, akkor keveset.
A dokumentumok sorrendje az értékelések alapján adódik. Ami fentebb van a listában, azt hasznosabbnak ítélték társaid. Az új dokumentumok pedig (értékelések hiányában) szintén a lista tetején kezdenek.

Hozzászólások

Ha észrevételed van egy dokumentummal kapcsolatban (például hibát találtál benne), akkor a Hozzászólások részben jelezheted. Az olyan jellegű kérdéseket mint pl.: A 2. feladat 4. sorából milyen átalakítással jutottunk az 5. sorban szereplő képlethez? - szintén ide érdemes írni

Egy tipp az oldalhoz! - Üzenj az összes olyan hallgatónak aki felvett egy bizonyos tantárgyat! Hasznos lehet ha egy tárggyal kapcsolatban olyan kérdéseid merülnek fel mint pl

• Hol lesz a vizsgamegtekintés?
• Meddig kell tudni az anyagot?
• Mely részeket adták le előadáson a könyből?
• stb...

Az üzeneted így ahhoz a célcsoporthoz jut el, akik együtt hallgatják veled a tárgyat. Ehhez kattints az Üzenetekre, ezután válaszd ki a tantárgyat a saját tárgyaid közül, majd kattints az Üzenet írására.

1 eloadas 1-8 architekturak bce kik deindividuáció dia elméleti kérdések fogalmak fogyasztói föld földtan füst hallás házi doga hőtan inflog innováció képlékenyalakítás ket kiadott kidolgozott tételek labor lengyel ferenc lm görbe logisztika lowie ma marketing tétel mikroökonómia mintavizsga munkafüzet növények objektum orientált órai előadás ökológia önkormányzat pénzügy polgár pót számtek szocializáció szocioógia tájékoztató tanulás tematika tereptan üzleti etika valszám védett területek vizsgakérdés