mate diskrit graf 1

Upload: k1anditara4380

Post on 09-Jul-2015

195 views

Category:

Documents


7 download

TRANSCRIPT

BAB I PENGENALAN TENTANG APLIKASI MATEMATIKA DISKRET

I.1. Pendahuluan Banyak masalah kehidupan sehari-hari yang dapat diabstraksi sebagai masalah yang berkaitan dengan himpunan benda-benda diskret dan relasi biner pada benda-benda tersebut. Sebagai contoh, marilah kita perhatikan serangkaian pol pendapat umum yang dilakukan untuk menentukan kepopuleran para calon presiden. Dalam setiap pol yang diadakan, ingin diketahui pendapat para pemilih tentang dua di antara para calon, dan lalu ditentukan siapa favoritnya. Hasil polpol tersebut ditafsirkan sebagai berikut : Calon a dianggap lebih favorit daripada calon b jika salah satu di antara tiga kondisi berikut dipenuhi : 1. Calon a lebih favorit daripada calon b di dalam pol yang diadakan antara keduanya. 2. Calon a lebih favorit daripada calon c di dalam sebuah pol, sedangkan calon c lebih favorit daripada calon b di dalam pol yang lain. 3. Calon a lebih favorit daripada calon c, dan calon c lebih favorit daripada calon d, dan calon d lebih favorit daripada calon b di dalam tiga pol terpisah yang diadakan, dan begitu seterusnya. Untuk dua calon tertentu, misalnya kita ingin tahu apakah salah satu lebih kuat daripada yang lain atau tidak. Misalkan S = {a, b, c, ...} himpunan para calon presiden dan R sebuah relasi biner pada S sedemikian rupa sehingga (a,b) ada di dalam R jika pol antara a dan b diadakan dan a terpilih sebagai calon yang lebih favorit. Relasi biner pada suatu himpunan dapat disajikan dalam bentuk tabel atau grafik. Misalkan relasi biner pada Gambar 1.1.a dan Gambar 1.1.b mempresentasikan hasil-hasil pol yang diadakan. Kita lihat bahwa calon a lebih favorit daripada calon e sebab pasangan terurut (a, b), (b, d), (d, e) ada di dalam R.

1

a a a b c d e c (a) Gambar 1.1 Hasil pol yang diadakan (b) d b b e c d e

Sebagai ilustrasi lain, misalkan sejumlah kota dihubungkan oleh jalanjalan raya. Bila diberikan peta jalan-jalan raya tersebut, kita mungkin ingin mengetahui apakah ada rute jalan raya antara kedua kota pada peta tersebut. Dalam berbagai masalah yang berkaitan dengan benda-benda diskret dan relasi biner, representasi grafik seringkali merupakan bentuk penyajian yang memudahkan. Hal ini menuntun kita pada pembelajaran tentang teori graf, suatu pembelajaran tentang aplikasi dari Matematika Diskret.

I.2. Penerapan Graf Dalam Persoalan Matematika Diskret Graf dapat didefinisikan sebagai kumpulan simpul-simpul yang

dihubungkan dengan garis. Simpul biasa dinyatakan dengan istilah verteks dan garis biasa dinyatakan dengan istilah edges atau busur. Contoh : 1.1 Struktur kimia adalah kumpulan atom-atom yang terikat menurut aturan ikatan kimia tertentu. Sebagai contoh, CH4 (Metana) merupakan ikatan kimia yang terdiri dari 1 atom C dan 4 atom H, sehingga terbentuk ikatan seperti di bawah ini.H

H

C

H

H CH4 (Metana) Gambar 1.2

Model Graf

2

Dari ikatan yang ada pada Gambar 1.2, dapat diubah ke dalam model graf seperti gambar di sampingnya. 1.2 Jaringan komunikasi adalah kumpulan beberapa pusat atau stasiun yang dapat berkomunikasi secara langsung.Subscriber Group Switching Centre Local exchange

Gambar 1.3 Jaringan Telepon

Switching Center Gambar 1.4 Jaringan Switching

Model Graf

1.3 Jaringan lalu lintas adalah kumpulan jalan yang saling berhubungan. Jika digambar dalam bentuk graf, simpul melambangkan persimpangan dan busur melambangkan arah lalu lintas.

3

Contoh :

Gambar 1.5 Jaringan Lalu Lintas

Gambar 1.6 Model Graf Jaringan Lalu Lintas

1.4 Sebuah papan sirkuit adalah kumpulan komponen yang dihubungkan dengan sebuah lintasan konduktor. Jika digambar dalam bentuk graf, simpul melambangkan simpangan dan busur melambangkan terminal dari komponen. Model alternatif lainnya adalah simpul melambangkan komponen dan busur melambangkan lintasan konduktor antara terminalterminal dalam komponen.

Gambar 1.7 Sirkuit dan Model Grafnya

4

Contoh-contoh di atas merupakan beberapa contoh tentang aplikasi graf dalam sistem model yang nyata. Dalam setiap persoalan, graf memberikan sebuah sruktur model tentang sistem yang kita pelajari, menjelaskan interaksi dan hubungan antara berbagai komponen dalam sistem. Sedangkan dalam berbagai persoalan, masalah yang sering muncul dalam pelaksanaannya adalah

mendapatkan sebuah penyusunan yang memenuhi semua permintaan, dan optimal menurut beberapa kriteria seperti harga, pengeluaran atau penampilan. Masalah dasar yang sering muncul pada Matematika Diskret yaitu : 1. Masalah eksistensi Apakah sedikitnya ada satu penyusunan dalam tipe khusus ? 2. Masalah perhitungan Berapa banyak penyusunan dari tipe khusus yang ada ? 3. Masalah optimisasi Diperoleh dengan memilih bentuk dari semua penyusunan yang mungkin untuk tipe yang pasti dan terbaik menurut beberapa kriteria. Kita dapat mengilustrasikan masalah-masalah ini ke dalam contoh berikut : Contoh 1.5 : Masalah Alokasi : Pada permasalahan pengalokasian frekuensi pengangkutan ke stasiun pengirim, dimisalkan ada m saluran (frekuensi) yang mungkin digunakan oleh n stasiun pengirim. Stasiun yang dialokasikan dekat dengan stasiun yang lain dan tidak dapat menggunakan saluran yang sama tanpa menyebabkan percampuran. Jadi, diberikan dua stasiun yang dapat atau tidak dapat dinyatakan bahwa kedua stasiun itu menggunakan saluran yang sama. Sejumlah persoalan terjadi. Masalah Eksistensi : Apakah mungkin untuk mengalokasikan sebuah saluran pada setiap gardu di mana untuk dua stasiun yang berbeda saluran harus mempunyai saluran yang berbeda? Jika ya, bagaimana cara mendapatkan alokasi tersebut ? Masalah Perhitungan : Berapa banyak alokasi yang sesuai ?

5

Masalah Optimasi : Berapa jumlah saluran minimum yang memenuhi kondisi alokasi ? Bagaimana kita dapat memodelkan situasi ini ? Sebuah model graf dapat dikembangkan sebagai berikut. Setiap stasiun dihubungkan oleh simpul dan 2 simpul dihubungkan oleh 1 busur jika dan hanya jika stasiun yang berhubungan tidak menggunakan saluran yang sama. Sebagai contoh, dimisalkan ada 5 stasiun dan informasi yang ada dinyatakan dalam hubungan matriks berikut. 1 1 2 3 4 5 1 0 0 1 2 1 1 1 0 3 0 1 1 1 4 0 1 1 1 5 1 0 1 1 -

Tabel 1.1

1 menunjukkan adanya hubungan (Gardu tidak bisa diberikan pada channel yang sama) dan 0 menunjukkan tidak ada hubungan. Dari informasi yang ada, dapat dibuat model graf seperti di bawah ini. 1

5

2

4Gambar 1.8

3

Penggambaran matriks konflik yang ada ke dalam bentuk graf tentu saja tidak menyelesaikan masalah. Tetapi, aspek visual dari model graf tersebut

6

memberikan beberapa pandangan. Sebagai contoh, pembuatan segitiga ke dalam bentuk graf, menunjukkan bahwa kita membutuhkan sedikitnya tiga saluran yang berbeda. Dapatkah kita membuat alokasi, jika kita hanya mempunyai tiga saluran? Bagaimana kita menyelesaikan masalah eksistensi jika kita hanya punya m saluran? Sebuah alokasi mungkin terjadi hanya jika kita dapat mempartisi simpul dalam graf menjadi m himpunan di mana tidak ada dua simpul dalam himpunan yang sama terhubung oleh sebuah busur. Hal inilah yang membawa kita ke konsep pewarnaan. Sebuah graf dikatakan Graf k-colourable jika simpul-simpul dalam graf dapat diwarnai dengan syarat 2 simpul yang adjacent (berdampingan) diwarnai berbeda. Sebagai contoh Graf Gi, i = 1, 2, 3, 4, ... yang disajikan ke dalam Gambar 1.8 mempunyai i-pewarnaan.

G1

G2 Gambar 1.9

G3

G4

Sebuah Combinatorial Design merupakan cara memilih himpunan bagian dari suatu himpunan berhingga jika dan hanya jika beberapa kondisi khusus terpenuhi. Kondisi khusus ini disebut dengan mengeliminasi bias. Contoh 1.6 : Sebuah percobaan yang dilakukan untuk menguji efek samping dari 5 jenis obat terhadap 5 subyek. Dimisalkan obat-obat yang ada diberi label 1,2,3,4,5 dan subyeknya diberi nama A,B,C,D,E. Kemungkinan 1 : A 1 B 2 C 3 D 4 E 5

(Subyek A diberi obat berlabel 1, subyek B diberi obat berlabel 2, dan seterusnya.) Apa yang salah dengan kemungkinan 1 ?

7

Beberapa subyek mungkin alergi terhadap obat tertentu sehingga hasilnya akan bias. Kemungkinan 2 : Memberi setiap subyek setiap jenis obat, 5 hari berturut-turut. S U B Y E K Senin 1 1 1 1 1 HARI Selasa Rabu 2 3 2 3 2 3 2 3 2 3Tabel 1.2

A B C D E

Kamis 4 4 4 4 4

Jumat 5 5 5 5 5

Apakah solusi ini benar ? Hasilnya dapat mengakibatkan bias, karena : (i) Hari-hari tertentu, obat diberikan (Tiap hari sama obat) (ii) Efek dari obat pertama dapat mempengaruhi efek obat terakhir Bagaimana cara menghilangkan bias ? Untuk menghilangkan bias, tidak ada 2 subyek yang mendapatkan jenis obat yang sama pada hari yang sama. Jadi muncul tepat 1 kali pada setiap baris dan kolom. S U B Y E K Senin 1 2 3 4 5 HARI Selasa Rabu 2 3 3 4 4 5 5 1 1 2Tabel 1.3

A B C D E

Kamis 4 5 1 2 3

Jumat 5 1 2 3 4

Inilah solusi yang terbaik. Sejumlah persoalan akan timbul, seperti : 1. Apakah solusinya tunggal ? 2. Apa yang terjadi, jika kita hanya punya 4 subyek ? Bentuk matriks yang diberikan di atas dapat disebut dengan istilah Latin Square. Latin square didefinisikan sebagai suatu bentuk matriks di mana antara satu baris dan satu kolom tidak ada yang sel yang sama.

8

LATIHAN SOAL

1. Gambarkan sebuah graf yang mewakili setiap komponen kimia berikut ! (a)H H H H

H

C

C

C

C

H

H

H

H

H

C4H10 (Butana) (b)H

H

C

H

H

H

H

C

C

C

H

H

H

H C4H10 (Iso-butane)

Susunan di atas mempunyai komposisi yang sama tetapi berbeda bentuk. Dapatkah kamu menjelaskan mengapa hal ini dapat terjadi ? 2. Untuk masing-masing graf di bawah ini, tentukan minimum warna yang dibutuhkan untuk mewarnai simpul-simpul dibawah ini sehingga simpul yang berdampingan dapat diwarnai berbeda.

(a)

(b)

(c)

9

3. Tentukan Latin Square dengan order : (a) 2 (b) 3 (c) 4

4. Dua Latin Square A = (aij) dan B = (bij) dari n order yang sama dikatakan ortogonal jika n2 order yang berpasangan (aij, bij) semuanya berbeda. Tentukan sepasang Latin Square ortogonal order 3 !

10

BAB II GRAF DAN JARINGAN

Pada bab terdahulu diberikan beberapa contoh tentang graf. Dalam bab ini, kita akan melihat beberapa permasalahan khusus dalam rancangan jaringan. Masyarakat modern didominasi oleh sistem jaringan untuk informasi penyaluran, transportasi rakyat, dan penyaluran barang-barang serta energi. Jaringan telekomunikasi dan jaringan komputer adalah contoh umumnya. Secara luas dikatakan, sebuah jaringan adalah sebuah sistem yang melibatkan aliran atau perpindahan komoditas. Komoditas yang dimaksud dapat berupa benda yang dapat disentuh, seperti komponen elektronik, mobil-mobil, kaleng bir, gas alam atau benda yang tidak dapat disentuh seperti informasi, persahabatan dan hubungan kekeluargaan. Jaringan-jaringan ini dapat dimodelkan ke dalam kesatuan matematika yang disebut graf. Seperti yang telah dijelaskan dalam pendahuluan, sebuah graf dapat disebut sebagai kumpulan titik yang disebut simpul dan dihubungkan oleh garis yang disebut busur. Graf dapat digunakan sebagai cara yang sangat sederhana untuk memodelkan banyak jaringan. Sebagai contoh, sebuah jaringan komunikasi dapat dimodelkan ke dalam bentuk graf, dengan simpul menyatakan pusat komunikasi (contohnya, saluran telepon) dan busur menyatakan jaringan komunikasi (contohnya, saluran telegraf). Dalam memodelkan sebuah jaringan dengan graf, simpul dalam graf umumnya dinyatakan dalam bentuk titik yang menyatakan asal aliran serta tempat berakhir (contohnya, stasiun kereta api, terminal, pabrik, gudang, dan lain-lain). Busur dalam graf secara umum menyatakan saluran di mana komoditas berakhir (contohnya, trayek kereta api, rute penerbangan, aliran pipa, dan lain-lain). Sebuah graf memberikan model struktural dari jaringan. Dalam kebanyakan jaringan, metode konstruksi biasanya dinyatakan oleh harga, efisiensi, kehandalan dan kapasitas.

11

II.1. Graf Graf adalah kumpulan simpul atau verteks yang dihubungkan dengan garis atau busur. Definisi 2.1 Graf adalah himpunan busur dan simpul yang banyaknya berhingga dan busurbusurnya menghubungkan sebagian atau keseluruhan pasangan dari simpulsimpulnya. (C.L. Liu) Graf G(V, E) terdiri atas himpunan simpul yang dinyatakan

dengan V = {v1,v2, v3, ..., vn} dan himpunan busur yang dinyatakan dengan E = {e1, e2, e3, ..., en} dengan ei = (vi, vj) merupakan busur yang menghubungkan simpul vi dan simpul vj. Dalam menggambarkan graf, simpul digambarkan dengan lingkaran kecil atau titik tebal dan busur digambarkan dengan garis, dan arah panah pada garis melambangkan arah dari garis tersebut. Nomor atau nama simpul dapat diletakkan di dalam lingkaran kecil atau di tepi titik tebal. Busur (i,j) disebut busur berarah jika terdapat suatu aliran dari simpul i menuju ke simpul j. Dalam hal ini simpul i disebut simpul awal, sumber atau pangkal dan simpul j disebut simpul akhir, ujung, tujuan, atau terminal dari busur (i, j). Jika tidak terdapat aliran dari simpul i ke simpul j, maka busur (i, j) disebut busur tidak berarah. i j i jb. busur berarah Gambar 2.1

ic. busur dua arah

j

a. busur tak berarah

Penulisan simpul dan busur dari graf G (V, E) yang digunakan seperti Gambar 2.1. Jika simpul s telah diberi nomor i maka cukup ditulis i, dan jika simpul s telah diberi nomor j, maka cukup ditulis simpul j. Demikian juga busur yang menghubungkan simpul i dan j cukup ditulis busur (i,j). II.2. Jaringan Suatu jaringan G (V, E, W) terdiri atas himpunan simpul yang dinyatakan dengan V = {v1,v2, v3, ..., vn} dan himpunan busur yang menghubungkan simpul-

12

simpul V dinyatakan dengan E = {e1, e2, e3, ..., en} = {(vi, vj) : vi V } dan setiap busur pada jaringan diberikan bobot (W). Dengan kata lain, jaringan merupakan suatu graf yang memiliki bobot pada setiap busurnya. Oleh karena itu, pada umumnya graf dinotasikan dengan G (V, E) dan jaringan dinotasikan dengan G(V, E, W). Jaringan komunikasi jika dibuat dalam bentuk graf, maka simpul melambangkan pusat komunikasi dan busur melambangkan link komunikasi. Contoh : Perusahaan memproduksi l tanaman, P1, P2, ..., Pl yang dibutuhkan m outlets atau pasar M1, M2, ..., Mm. Komoditas khusus disimpan pada n gudang, W1, W2, ..., Wn. Dalam graf, busur melambangkan hubungan transportasi dan simpul melambangkan produksi tanaman, gudang dan pasar. Pada tiap busur, akan ditentukan jumlah maksimum komoditas yang dapat ditransport sepanjang hubungan dan harga transport 1 unit. Pada simpul mewakili: Tanaman Pi, i = 1, 2, ..., l . Kita dapat menentukan bobot sebagai rata-rata produksi tanaman dan harga produksi per unit untuk Pi. Gudang Wj, j = 1, 2, ..., n. Kita dapat menentukan bobot sebagai kemampuan penyimpanan pada gudang Wj dan harga penyimpanan satu unit per waktu. Pasar Mk, k = 1, 2, ..., m, kita dapat menentukan bobot sebagai permintaan per waktu, dan harga penjualan komoditas. Pembahasan selanjutnya tentang seberapa jauh penggunaan graf sebagai model struktural. Sekarang, kita akan membahas beberapa persoalan khusus yang muncul. Persoalan Penghubung Sebuah jaringan komunikasi (contohnya, jaringan telepon) yang

menghubungkan n pusat atau kota T1, T2, ..., Tn harus diinstall. Masing-masing pusat mampu untuk menerima dan menyalurkan informasi. Jadi dua pusat dapat berkomunikasi secara langsung maupun tidak langsung. Diberikan contoh n n matriks C = [cij] di mana cij menyatakan harga penginstallan

13

jaringan komunikasi (contohnya, jaringan telepon) antara pusat Ti dan Tj, disusun menjadi sebuah jaringan untuk mencapai dua tujuan berikut : (i) sedikitnya dua pusat yang dapat berkomunikasi, dan (ii) jumlah biaya instalasi adalah minimum. Berdasarkan Persoalan Penghubung di atas, jika n = 6, dan matriks biayanya adalah : T1 T2 T3 T4 T5 T6 T1 0 5 10 3 T2 5 0 8 4 10 T3 10 8 0 5 15 Tabel 2.1

T4 4 5 0 13 7

T5 10 15 13 0 2

T6 3 7 2 0

Graf yang digambarkan berdasarkan matriks di atas adalah pada Gambar 2.2. di bawah ini :T1 3 10 T6 15 7 2 13 T5 Gambar 2.2 T4 5 4 T3 5 10 T2 8

Biaya yang bertanda artinya pusat yang berhubungan tidak dapat berkomunikasi secara langsung, sehingga kita dapat menghilangkan busur tersebut dari graf kita. Persoalan Lintasan Terpendek Perhatian khusus ditujukan untuk menemukan rute terpendek antara pasangan pusat dalam sebuah jaringan. Contohnya, sebuah perusahaan bisnis besar dengan kantor pusat di New York mempunyai beberapa cabang utama di negara-negara seluruh dunia. Kantor pusat mengkoordinasi seluruh kegiatan operasi perusahaan, dan setiap hari seluruh informasi (meliputi permintaan,

14

penawaran dan biaya) harus diberikan dari kantor pusat ke kantor-kantor cabang. Informasi yang ada dikirimkan via teleks. Diberikan biaya pengiriman pesan melalui teleks antara dua perusahaan, dan ditentukan rute komunikasi termurah dari kantor pusat dan setiap kantor cabang lainnya. Perusahaan perbankan dengan kantor pusat di New York (NY) dan kantor cabang di Paris (P), Zurich (Z), Berlin (B), Tokyo (T), Hongkong(HK) dan Sydney (S). Setiap hari informasi penting (meliputi permintaan, penawaran dan biaya) harus diberikan dari kantor pusat ke kantor-kantor cabang. Informasi yang ada dikirimkan via teleks. Biaya pengiriman pesan antara dua kantor cabang diberikan dalam matriks di bawah ini : NY P Z B T HK S NY 0 8 10 12 10 15 20 P 8 0 2 1 10 10 10 Z 10 2 0 3 12 12 15 B 12 1 3 0 10 10 10 T 10 10 12 10 0 3 5 HK 15 10 12 10 3 0 5 S 20 10 15 10 5 5 0

Tabel 2.2

Graf yang digambarkan berdasarkan matriks di atas adalah pada Gambar 2.3. di bawah ini : 10 P10

1

B10 3 10 10T

2

10

8 12 10NY

20 15 10HK

5 3

S5 15 12Gambar 2.3

Z

12

Seperti contoh terdahulu, model graf ini memberikan himpunan semua hubungan yang mungkin dan permasalahannya adalah memilih sebuah

15

himpunan bagian dari himpunan ini yang menunjukkan bahwa jaringan yang ada sesuai dan jumlah biaya dari pengiriman informasi dari kantor pusat ke kantor cabang dapat diminimalkan. Persoalan Aliran Maksimum Persoalan dasar dimulai dengan menentukan jumlah aliran maksimum yang dapat dikirim antara pasangan pusat dalam jaringan. Sebagai contoh sebuah jaringan telepon menghubungkan n pusat (sambungan telepon) T1, T2, ..., Tn. Jumlah maksimum panggilan langsung yang disebut cij dapat dibuat per unit waktu antara Ti dan Tj, tergantung jumlah saluran yang menghubungkan dua pusat. Setiap pusat tentu saja dapat menerima dan mengirim panggilan. Diberikan matriks C = [cij]. Permasalahannya adalah menentukan jumlah panggilan maksimum yang dapat terjadi antara dua pusat yang diberikan. Sesuai contoh jika n = 6 dan kapasitas matriks C diberikan seperti di bawah ini 0 40 80 C= 0 0 0 40 80 0 0 0 0 20 60 20 0 20 0 20 100 0 60 20 0 20 80 20 100 20 0 50 0 0 80 50 0

Jaringan yang ada dapat digambarkan sebagai berikut :

C2 40 C1 80 C3 20

60 20

C4 80 20 C6 50 C5

20 100Gambar 2.4

Perkembangan teori graf diawali dari teka-teki (puzzle). Salah satu tekatekinya adalah masalah jembatan Konigsberg. Solusi dari teka-teki ini mengilhami beberapa konsep dasar dalam teori graf.

16

Sebuah rencana kota tua Konigsberg (sekarang Kaliningrad) di Prussia Timur dan sungai Pregel (sekarang Pregolya) dengan tujuh jembatan perentang ditunjukkan pada Gambar 2.5. Hal ini menunjukkan bahwa masyarakat Konigsberg dapat menghibur diri mereka dengan mengelilingi kota dan menyeberangi tujuh jembatan tepat satu kali. Pada tahun 1736 Leonhard Euler, seorang matematikawan dari Swiss, dalam artikel perdananya mengembangkan sebuah metode untuk menyelesaikan persoalan umum ini. C

A

B

DGambar 2.5

Metode Euler menjelaskan bahwa setiap daratan dinyatakan dengan simpul dan setiap jembatan dinyatakan dengan busur yang menghubungkan simpul-simpul. Berdasarkan informasi tersebut, dapat dibuat graf seperti di bawah ini : C

A

B

DGambar 2.6

Hal inilah yang membuat hasil kerja Euler memberikan konsep penting dalam graf Eulerian yang muncul dalam kehidupan modern sekarang. Aplikasi hal ini dalam teori graf seperti pengiriman surat, pengeplotan mesin dan masih banyak lagi. Aplikasi ini akan dibahas dalam Bab 6.

17

LATIHAN SOAL

1. Sebuah perusahaan minuman mempunyai 3 jenis minuman B1, B2, dan B3. Masing-masing minuman mempunyai kapasitas produksi 5000 karton per bulan. Perusahaan mempunyai outlet di Louisville (M1), Plains (M2), Pittsburg (M3) dan St. Louis (M4) yang membutuhkan 1.500, 3.500, 2.000, dan 2.500 karton per bulan. Biaya pengiriman per 100 karton minuman Bi, i = 1, 2, 3, ke outlet-outlet Mj, j = 1, 2, 3, 4 diberikan dalam matriks di bawah ini : M1 M2 M3 M4 B1 5 30 15 20 B2 8 25 18 17 B3 12 35 20 25 a. Gambarkan graf berbobot untuk menunjukkan situasi di atas ! b. Permasalahan optimasi apa yang akan muncul ? 2. Seorang penjual koran bertanggung jawab dalam mengirimkan koran-koran ke rumah-rumah yang ditunjukkan dalam map ini pada sore hari. Karena kemacetan lalu lintas, dia tidak dapat menyeberang jalan kembali dan tidak dapat mengirimkan koran ke rumah-rumah di seberang jalan. Jadi ia harus berjalan sebanyak dua kali. Apakah mungkin bagi penjual koran untuk menentukan rute terpendek agar ia dapat berjalan di jalan itu tepat hanya satu kali ?

18

3. Air dikirimkan dari sumber penampungan utama D ke sebuah penampungan cabang lainnya, R, melalui sebuah saluran pipa yang terdiri atas 5 stasiun pemompa P1, P2, ..., P5. Rata-rata air yang dialirkan antara berbagai stasiun per hari dalam jutaan liter disajikan dalam tabel di bawah ini. D P1 P2 P3 P4 P5 R D 0 230 200 170 0 0 0 0 0 100 0 200 0 P 0 1 P2 0 0 0 0 0 160 180 P3 0 0 0 0 0 150 0 P4 0 0 0 0 0 0 200 P5 0 0 0 0 0 0 250 R 0 0 0 0 0 0 0 Permasalahannya adalah untuk memaksimumkan aliran air per hari dari sumber penampungan utama ke penampungan cabang lainnya. (a) Gambarkan jaringannya ! (b) Dimisalkan sebuah penampungan R` ditambahkan ke dalam jaringan. Stasiun pemompa P3, P4 dan P5 dihubungkan ke R` dengan saluran pipa yang mempunyai kapasitas 50, 75, dan 100 juta liter per hari. Bagaimana perubahan yang terjadi pada jaringan? Permasalahan optimasi apa yang muncul ? (c) Dimisalkan pompa P4 mempunyai kapasitas maksimum 280 juta liter per hari dan kapasitas pipa tidak berubah. Bagaimana jaringan dalam soal (a) akan berubah ? 4. Perpustakaan universitas dikelompokkan ke dalam empat fasilitas, dengan nama Catalog (C), Photocopy (P), Jurnal (J) dan Buku baru (B). Sebuah investigasi menjelaskan permintaan harian, dan jumlah peredaran setiap pasangan fasilitas : E C P J B E 200 4 80 32 C 200 77 125 42 P 4 77 64 19 J 80 125 64 26 B 32 42 19 26

19

E menyatakan jalan masuk. Diputuskan untuk mengatur fasilitas-fasilitas ke dalam bentuk jalan, dengan tujuan memaksimumkan jumlah nilai pasangan fasilitas yang berdampingan. Gambarkan model graf untuk persoalan ini ! 5. Sebuah universitas mensponsori seminar setengah hari tentang Optimasi Kombinatorial. Ada tujuh pembicara, masing-masing dari mereka berbicara selama 1 jam. Seminar ini memerlukan waktu lebih dari 4 jam dan oleh karena itu beberapa pembicara harus menjadwalkan waktunya pada jam yang sama. Matriks berikut memberikan hubungan antara para pembicara dalam seminar. 1 menunjukkan pembicara tidak dapat menjadwalkan pada waktu yang sama dan - menunjukkan tidak ada hubungan. 1 1 2 1 3 4 5 1 6 7 1 2 1 3 1 1 1 1 4 1 1 1 5 1 1 1 1 1 6 1 1 1 7 1 1 1

a. Gambarkan matriks di atas ke dalam bentuk graf ! b. Dapatkan seminar diatur dalam waktu yang spesifik ?

20