Cím: SZÁMÍTÁSTECHNIKAI ROVAT
Füzet: 1979/október, 74 - 76. oldal  PDF  |  MathML 

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

(Rovatvezető: Ada-Winter Péter)
 

A KÖMAL 1979/2. számában kitűzött SZ9 jelű feladat megoldása
 

A kitűzött feladat szövege az alábbi volt:
 

Egy vegyi üzem négyféle alapanyagból háromféle terméket állít elő. Az alábbi táblázat azt mutatja, hogy az egyes termékek egy kilogrammnyi mennyiségéhez hány kilogramm alapanyag felhasználása szükséges.
 


Termék\AlapanyagABCD1.0,40,40,00,82.0,20,20,70,63.0,10,80,50,4


 


Az alapanyagok árát és a naponta beszerezhető maximális nyersanyagmennyiséget az alábbi táblázatban látjuk:
 


ABCDFt/kg0,720,131,50,85Nap/kg10001000600800

 


Mennyit kell termelni naponként az egyes termékekből ahhoz, hogy a nyersanyag-felhasználás összköltsége maximális legyen ?
 

Megoldás: A táblázatból kiszámítható a háromféle termék egy-egy kg-jához szükséges nyersanyagok ára. Így pl. az 1. termékre:
0,4⋅0,72+0,4⋅0,13+0,8⋅0,85=1,02Ft/kg.

Hasonlóan a második termékre 1,73 és a 3. termékre 1,266Ft/kg adódik. Ennek alapján az összes felhasznált nyersanyag árát a
z=1,02x1+1,73x2+1,266x3


kifejezés adja meg, ahol x1,x2 és x3 a termelt termékek kg-ban kifejezett mennyisége. Ha z-t mint e változók függvényét tekintjük, akkor a feladat olyan termékmennyiségek keresése, amelyek z-nek maximális értékét adják. Ezt nevezzük optimális megoldásnak. Minden egyéb megoldást lehetséges megoldásnak nevezünk. Készítsük el az alábbi táblázatot, és próbáljuk egy lehetséges megoldás adataival kitölteni.
 
 1. táblázat



 

Mivel az x1 termék C-ből nem használ, célszerű ezzel kezdeni a nyersanyag ,,kiosztását". Kezdjük tehát az x2-vel. Tegyük erre a legszűkösebben rendelkezésre álló nyersanyag egész mennyiségét, 600 kg-ot. Ekkor x2-ből 600:0,7=357,143 kg termelhető, amihez viszont A-ból 171,429 kg, B-ből ugyanennyi, és D-ből 514,286 kg szükséges. Miután C-ből a teljes készlet elfogyott, a maradék anyagokból csak x1 állítható elő. Ennek korlátot szab, hogy D-ből 800-514,286=285,714 kg áll rendelkezésre, amiből (0,8-del osztva) 357,143 kg termék készülhet. Ehhez A-ból és B-ből egyenként 142,857 kg szükséges. A kapott adatokkal kitöltve a táblázatot, a 2. táblázat áll elő.
 



 

 

 

Mármost ebből a lehetséges megoldásból kiindulva próbáljunk meg egy ,,jobb" megoldást csinálni. (Olyat, amelynél z értéke nagyobb.) Vizsgáljuk meg, hogy ha az x2 termékből 1 kg-mal kevesebbet termelnénk, akkor ‐ a felszabaduló nyersanyagot x1-ben és x3-ban felhasználva ‐ magasabb lenne-e az összesen felhasznált nyersanyag ára. Ezt mutatja meg (az előzőhöz hasonló módon végigszámolva) a 3. táblázat.
 



 

A rovatokban a táblázatban szereplő mennyiségeknek a 2.-beli megfelelő értékektől való előjeles eltérése áll. Ezekből a legfeltűnőbb az, hogy az x2 mennyiségének 1 kg-mal való csökkentése az x1-nek 0,05 kg-nyi és az x3-nak 1,4 kg-nyi növekedésével jár együtt, ha a felszabaduló nyersanyagokat ezek termelésére fordítjuk.
Ennek megfelelően a z értéke is nő Könnyen belátható, hogy x1 további csökkentésével a Δ-hoz tartozó mennyiségek lineárisan változnak. Ebből következik, hogy most már csak azt kell megállapítani, hogy x2 termelését hány kg-mal csökkentsük a másik két termék javára. A csökkentésnek a B-hez tartozó korlát szab határt. Miután a 2. tábla szerinti maradék 685,714 kg, a 3-ban a megfelelő csökkenés 0,94, ezért ennek 729,48297-szerese fogyasztható még el. Ha most a 3-beli Δ értékeket ezzel az arányossági tényezővel szorozzuk és a 2-beli alapértékekhez hozzáadjuk, megkapjuk a 4. táblázatot, amelyet csak részben volt érdemes kitölteni. Belátható, hogy az ebben szereplő z a lehető legnagyobb, mivel bármilyen, a korlátok közt tartott termékmennyiség változtatása csak ronthat rajta.
 



 

Feladatok
 

Sz. 9. (Újból kitűzve.) Oldjuk meg a feladatot Prékopa Andrásnak a KÖMAL 1979. 4-5. számaiban megjelent cikke alapján, vagy Csath Magdolna: Operációkutatás (1972. Számítástechnikai Oktató Központ) c. könyv 75.‐98. old. alapján Adják meg a beküldők megoldásban, hogy melyik forrást használták fel segítségül.
Sz. 14. Program készítendő, mely legfeljebb 30 síkbeli koordinata-ponthoz kiszámítja, hogy melyek tartoznak e ponthalmazt burkoló konvex poligon csúcspontjaihoz, ill. a burokhoz, és melyek helyezkednek el a burkon belül. Input: 3≤n≤30 az első kártyán, majd további n számú kártyán a koordináták, amelyeket F10.3 specifikációval kezelünk. Output: a beolvasott pontok, feliratkozva, külön listán a burkoló pontjai és külön a belsejében levő pontok listája.
 

Beküldési határidő: 1979. november 30.
 
A feladatmegoldások a következő címre küldhetők:
Ada-Winter Péter,
MÜM Számítástechnikai Intézet
Budapest, VIII.
Reguly Antal u. 57-59.
1089.