BAB 2 LANDASAN TEORI

BAB 2

LANDASAN TEORI

2.1

Konsep Jaringan

Dua buah komputer dikatakan terkoneksi jika bila komputer dapat saling bertukar informasi. Bentuk koneksinya tidak harus melalui kawat tembaga saja, melainkan dapat menggunakan serat optik, gelombang mikro, atau satelit.

Konsep jaringan dibedakan menjadi 2, yaitu: 1. Konsep jaringan berdasarkan letak geografis 2. Topologi jaringan

2.1.1 Konsep Jaringan Berdasarkan Letak Geografis

LAN (Local Area Network)

LAN adalah jaringan komputer yang jaringannya hanya mencakup wilayah kecil; seperti jaringan komputer kampus, gedung, kantor, dalam rumah, sekolah atau yang lebih kecil.

MAN (Metropolitan Area Network)

MAN adalah Suatu jaringan dalam suatu kota dengan transfer data berkecepatan tinggi, yang menghubungkan berbagai lokasi seperti kampus, perkantoran, pemerintahan, dan sebagainya. Jaringan MAN adalah gabungan dari beberapa LAN.

Universitas Sumatera Utara

8

Jangkauan dari MAN ini antar 10 hingga 50 km, MAN ini merupakan jaringan yang tepat untuk membangun jaringan antar kantor-kantor dalam satu kota antara pabrik/instansi dan kantor pusat yang berada dalam jangkauannya.

WAN (Wide Area Network)

WAN adalah jaringan komputer yang mencakup area yang besar sebagai contoh yaitu jaringan komputer antar wilayah, kota atau bahkan negara, atau dapat didefinisikan juga sebagai jaringan komputer yang membutuhkan router dan saluran komunikasi publik.

2.1.2 Topologi Jaringan

Topologi jaringan adalah, hal yang menjelaskan hubungan geometris antara unsurunsur dasar penyusun jaringan, yaitu node, link, dan station. Topologi jaringan dapat dibagi menjadi 5 kategori utama seperti di bawah ini.

1.

Topologi bintang merupakan bentuk topologi jaringan yang berupa konvergensi dari node tengah ke setiap node atau pengguna. Topologi jaringan bintang termasuk topologi jaringan dengan biaya menengah

2.

Topologi cincin adalah topologi jaringan dimana setiap titik terkoneksi ke dua titik lainnya, membentuk jalur melingkar membentuk cincin. Pada topologi cincin, komunikasi data dapat terganggu jika satu titik mengalami gangguan.

3.

Topologi Bus adalah kedua unjung jaringan harus diakhiri dengan sebuah terminator. Barel connector dapat digunakan untuk memperluasnya. Jaringan hanya terdiri dari satu saluran kabel yang menggunakan kabel BNC. Komputer yang ingin terhubung ke jaringan dapat mengkaitkan dirinya dengan mentap Ethernetnya


9

sepanjang kabel. Linear Bus: Layout ini termasuk layout yang umum. Satu kabel utama menghubungkan tiap simpul, ke saluran tunggal komputer yang mengaksesnya ujung dengan ujung. Masing-masing simpul dihubungkan ke dua simpul lainnya, kecuali mesin di salah satu ujung kabel, yang masing-masing hanya terhubung ke satu simpul lainnya.

4.

Topologi mesh menerapkan hubungan antar sentral secara penuh. Jumlah saluran harus disediakan untuk membentuk jaringan Mesh adalah jumlah sentral dikurangi 1 (n-1, n = jumlah sentral). Tingkat kerumitan jaringan sebanding dengan meningkatnya jumlah sentral yang terpasang. Dengan demikian disamping kurang ekonomis juga relatif mahal dalam pengoperasiannya.

5.

Topologi Pohon disebut juga sebagai topologi jaringan bertingkat. Topologi ini biasanya digunakan untuk interkoneksi antar sentral denganhirarki yang berbeda. Untuk hirarki yang lebih rendah digambarkan pada lokasi yang rendah dan semakin keatas mempunyai hirarki semakin tinggi. Topologi jaringan jenis ini cocok digunakan pada sistem jaringan komputer .

Gambar 2.1. Topologi Jaringan


10

2.2

Jaringan Telekomunikasi

Telekomunikasi adalah sebuah teknik yang mampu mengubah sistem teknologi informasi. Sangat penting bagi pengguna untuk mengerti beberapa karakteristik penting dari komponen dasar jaringan telekomunikasi. Hal tersebut dapat membantu pengguna untuk berpartisipasi secara efktif dalam membuat keputusan mengenai alternatif telekomunikasi.

Saluran

telekomunikasi

dapat

diartikan

sebagai

data

dan

bentuk

telekomunikasi yang ditransmisikan diantara pengirim dan penerima dalam suatu jaringan telekomunikasi.

Jaringan telekomunikasi secara garis besar dapat dikelompokkan kedalam dua kategori, yaitu jaringan komunikasi switch dan jaringan komunikasi broadcast. Jaringan switch dibagi lagi menjadi jaringan circuit-switching dan jaringan packet switching. Contoh jaringan circuit-switching adalah jaringan telepon, SDH dam jaringan wavelength routing optical. Kemudian jaringan packet switching dibagi lagi menjadi connection-oriented dan jaringan connectionless. Contoh utama jaringan connectionless adalah jaringan IP. JARINGAN TELEKOMUNIKASI

JARINGAN KOMUNIKASI SWITCH

JARINGAN CIRCUIT SWITCH



Jaringan telepon



Jaringan wavelength routing

JARINGAN KOMUNIKASI BROADCAST

JARINGAN PAKET - SWITCH

KARINGAN CONNECTION ORIENTED

JARINGAN CONNECTIONLESS

Gambar 2.2 Klasifikasi Jaringan Telekomunikasi


11

2.2.1 Model Jaringan Telekomunikasi

Secara umum jaringan telekomunikasi dibeberapa pengaturan dimana pengirim mengirimkan pesan kepada penerima melalui saluran yang terdiri dari beberapa tipe medium. Telekomunikasi memungkinkan setiap orang untuk saling berkomunikasi secara cepat dalam jarak yang jauh sekalipun.

Gambar 2.3. Jaringan Telekomunikasi (dari google picture)

Gambar diatas menggambarkan jaringan telekomunikasi yang terdiri dari 5 (lima) kategori komponen dasar: a) Terminal b) Telecommunications Processors c) Media dan saluran telekomunikasi berakhir yang mana data diterima dan dikirim. d) Komputer e) Software pengendali telekomunikasi

2.3

2.3.1

Sinyal Digital dan Analog

Sinyal Digital

Merupakan hasil teknologi yang mengubah sinyal tersebut menjadi kombinasi ututan bilangan 0 dan 1 untuk proses informasi yang mudah, cepat dan akurat. Sinyal tersebut disebut sebuah bit.


12

2.3.2 Sinyal Analog

Sinyal analog adalah merupakan pemanfaatan gelombang elektromagnetik. Proses pengiriman suara, misalnya pada teknologi telepon,dilewatkan melalui gelombang elektromagnetik .

2.4

Media Telekomunikasi

Jenis-Jenis Media Telekomunikasi:

a)

Twisted Pair Wire Cable Komponen ini terdiri dari atas 2 jenis, yaitu Unshielded Twisted-Pair(UTP) dan Shielded (STP).

1. UTP terdiri atas 2,3,4 atau lebih pasang kabel. Tiap pasang kabel dipilin 6 kali per inchi. Hal ini dilakukan untuk menghindari listrik dan impedansi listrik. Sensitif terhadap interferensi listrik, seperti derau listrik oleh cahaya fluorescent atau elevator berjalan.Kabel jenis ini disebut juga dengan Kabel IBM jenis 3.

2. STP pada dasarnya memiliki karakteristik yang sama dengan UTP. Perbedaaannya terletak pada besar kawat dan adanya selubung isolasi yang berfungsi untuk menghindari interferensi listrik.

b)

Coaxial Cable Karakteristik kabel ini terdiri atas 2 kabel yang diselubungi oleh 2 tingkat isolasi. Isolasi pertama (isolasi dalam) adalah isolaso yang menyelubungi kawat tembaga pejal. Selain dilindungi oleh isolator, kawat tembaga pejal ini juga dilindungi oleh kertas timah yang dipasang diatas isolator, untuk melindungi dari pengaruh medan elektromagnet.


13

c)

Fiber Optic Cable Fiber Optic memiliki karakteristik sebagai berikut : Data yang dikirimkan dalam bentuk pulsa cahaya kecepatan transmisinya paling tinggi. Tipis dan flesibel, sehingga mudah dipindahkan. Tidak terganggu oleh cuaca dan panas.

d)

Wireless Wireless memiliki karakteristik : Tidak menggunakan kabel, kerna data dikirimkan dalam bentuk gelombang atau inframerah. Setiap workstation berhubungan dengan hub atau concentrator melalui gelombang radio atau inframerah.

2.5

Protokol dan Arsitektur Jaringan

Protokol adalah sebuah set standar dari aturan dan prosedur untuk mengendalikan komunikasi didalam jaringan. Standar-standar ini diperuntukkan hanya pada satu peralatan manufaktur saja atau satu macam jenis telekomunikasi. Bagian dari tujuan jaringan arsitektur telekomunikasi adalah untuk menciptakan suatu standarisasi lebih dan kecocokkan diantara protocol komunikasi.

Tujuan dari arsitektur jaringan adalah untuk mengenalkan sebuah keterbukaan, simple, fleksibel dan lingkungan telekomunikasi yang efisien. Hal ini akan menjadi sempurna dengan penggunaan protocol standar. Standar komunikasi

yang

berhubungan langsung antara hardware dan software, dan desain standar hubungan antara pengguna dan system computer.

2.6

Routing

Router adalah sebuah alat yang mengirimkan paket data melalui sebuah jaringan atau internet menuju tujuannya, melalui sebuah proses yang dikenal sebagai routing. Routingmerupakan sebuah mekanisme yang digunakan untuk mengarahkan dan


14

menentukan jalur yang akan dilewati paket dari satu device ke device yang berada di jaringan lain. Definisi lain dari routing adalah proses untuk memilih jalur (path) yang harus dilalui oleh paket. Jalur yang terbaik tergantung pada beban jaringan, panjang datagram, type of service requested dan pola trafik. Pada umumnya skema routing hanya mempertimbangkan jalur terpendek (the shortest path). Sedangkan switching merupakan perpindahan paket dari satu interface ke interface lain.

Didalam routing dikenal 2 bentuk routing, yaitu:

1. Direct Routing

Direct routing adalah paket dikirimkan dari satu mesin ke mesin lain secara langsung (host berada pada jaringan fisik yang sama) sehingga tidak perlu melalui mesin atau gateway.

2. Indirect Routing

Indirect routing adalah paet dikirimkan dari suatu mesin ke mesin lain yang tidak terhubung langsung (berbeda jaringan) sehingga paket akan melewati satu atau lebih gatewayatau networkyang lain sebelum sampai ke mesin yang dituju.

2.6.1

Tabel Routing

Router merekomendasikan tentang jalur yang digunakan untuk melewatkan oaket berdasarkan informasi yang terdapat pada table routing.

Informasi yang terdapat pada table routing dapat diperoleh secara static routingmelalui perantara administrator dengan cara mengisi table routing secara manual ataupun secara dynamic routingmenggunakan protocol routing agar dapat mengetahui alamat tujuan dan memelihara table routing.


15

Table routing pada umumnya berisi informasi tentang: 1. Alamat network tujuan 2. Interface routeryang terdekat dengan network tujuan 3. Metric, yaitu sebuah nilai yang menunjukkan jarak untuk mencapai network tujuan. Metric tersebut menggunakan teknik berdasarkan jumlah lompatan (hop count).

2.6.2 Routed Protocol Routed Protocol (protocol yang diroutingkan) maksudnya adalah protocol – protocol yang dirutekan oleh sebuah router. Jadi protocol ini tidak digunakan untuk membuild routing tables, melainkan dipakai untuk addressing (pengalamatan). Karena digunakan untuk addressing, maka yang menggunakan routed protocol adalah end devices(laptop, mobile phone desktop, dll). Router akan membaca informasi dari protocol ini sebagai dasar untuk mengirimkan paket. Contoh routed protocol adalah IP, NetbUI, IPX, Apple Talk dan DECNet.

2.6.3 Routing Protocol

Routing Protocol maksudnya adalah protocol yang merouting. Routing protocol digunakan oleh router – router untuk memelihara / meng-updateisi routing table. Pada dasarnya sebuah routing protocol menentukan jalur (path) yang dilalui oleh sebuah paket melalui sebuah internetwork. Contoh routing protocol adalah RIP, IGRP, EIGRP, dan OSPF.

2.6.4 Router

Router memiliki kemmpuan untuk melewatkan paket IP dari satu jaringan ke jaringan lain yang memiliki banyak jalur diantara keduanya. Router – router yang saling berhubungan dalam jaringan telekomunikasi turut serta dalam sebuah algoritma


16

routing terdistribusi unutk menentukan jalur terbaik yang dilalui paket IP dari satu system ke system lain. Router dapat digunakan untuk menghubungkan sejumlah LAN terisolasi dengan baik dari trafik yang dibangkitkan oleh LAN lain. Jika dua atau lebih LAN terhubung oleh router, setiap LAN dianggap sebagai subnetwork yang berbeda. Hamper sama dengan bridge, router dapat menghubungkan interface jaringan yang berbeda.

Router umum dipakai terdiri dari dua jenis, yaitu dedicated (buatan pabrik) dan PC router. PC dapat difungsikan sebagai router sepanjang ia memiliki lebih dari satu interface jaringan, mampu melewatkan paket IP, serta menjalankan program untuk mengatur routing paket.

2.7

Program Linier

Dalam

matematika,

pemograman

linier

adalah

metode

matematik

dalam

mengalokasikan sumber daya yang terbatas untuk mencapai tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. Dalam menyelesaikan suatu permasalahan, program linier juga menggunakan teknik optimasi yang melibatkan variabel-variabel linier. Dalam model pemograman linier dikenal dua macam fungsi, yaitu fungsi objektif (objective function) dan fungsi kendala (constraint variabel) yang linier.

Dalam pemrograman linier dikenal beberapa karakteristik dari pemrograman linier yaitu : a. Sifat liniearitas

Sifat linearitas yaitu sifat dalam menyelesaikan suatu kasus dengan memeriksa keliniearan menggunakan grafik (diagram pencar) ataupun menggunakan uji hipotesa dimana secara teknis, linearitas ditunjukkan oleh adanya sifat proposionalitas, addivitas, divisbilitas dan kepastian fungsi tujuan dan pembatas.


17

b. Sifat proposional

Sifat proposional merupakan sifat yang akan dipenuhi jika kontribusi variabel pada fungsi tujuan atau penggunaan sumber daya yang membatasi proposional terhadap level nilai variabel.

c. Sifat additivitas

Sifat addivitas yaitu sifat ini mengasumsikan bahwa tidak ada bentuk perkalian silang diantara berbagai aktivitas, sehingga tidak akan ditemukan bentuk perkalian silang pada model, sifat ini berlaku baik bagi fungsi tujuan maupun pembatas (kendala) akan dipenuhi jika fungsi tujuan merupakan penambahan langsung kontribusi masing-masing variabel keputusan. Untuk fungsi kendala, sifat addivitas dipenuhi jika nilai kanan merupakan total penggunaan masingmasing

variabel

keputusan.

Jika

dua

variabel

keputusan

misalnya

merepesentasikan dua produk substitusi, dimana penigkatan volume penjualam salah satu produk akan mengurangi volume penjualan produk lainnya dalam pasar yang sama, maka sifat addivitas tidak terpenuhi.

d. Sifat divisibilitas

Sifat divisibilitas merupakan unit aktivitas dapat dibagi ke dalam sembarang level fraksional, sehingga nilai variabel keputusan non integer dimungkinkan.

e. Sifat kepastian

Sifat kepastian menunjukkan bahwa semua parameter model berupa konstanta. Artinya koefisien fungsi tujuan maupun fungsi pembatas merupakan suatu nilai pasti, bukan merupakan nilai dengan peluang tertentu.

Keempat asumsi (sifat) ini dalam dunia nyata tidak selalu dapat dipenuhi. Untuk meyakinkan dipenuhinya keempat asumsi, dalam pemrograman linier diperlukan analisi sensivitas terhadap solusi optimal yang diperoleh.


18

2.7.1

Formulasi Permasalahan

Urutan pertama dalam penyelesaian adalah mempelajari sistem relevan dan mengembangkan pernyataan permasalahan yang dipertimbangakan dengan jelas. Penggambaran sistem dalam pernyataan ini termasuk pernyataan tujuan, sumber daya yang membatasi, alternatif keputusan yang mungkin (kegiatan atau aktivitas), batasan waktu pengambilan keputusan, hubungan antara bagian yang dipelajari dan bagian lain dalam perusahaan, dan lain-lain.

Penetapan tujuan yang tepat merupakan aspek yang sangat penting dalam formulasi masalah. Untuk membentuk tujuan optimalisasi, diperlukan identifikasi anggota manajemen yang benar-benar akan melakukan pengambilan keputusan dan mendiskusikan pemikiran mereka tentang tujuan yang ingin dicapai.

Pemograman linier dapat direpresentasikan dalam notasi matematis sebagai berikut :

Dalam hal ini, koefisien dan

adalah vektor variabel, sedangkan

dan

adalah vektor

adalah matrix koefisien. Fungsi objektifnya adalah ekspresi yang

hendak dimaksimalkan atau diminimalkan (yaitu

). Persamaan

adalah

fungsi kendala yang menunjukkan polihedron konveks tempat fungsi objektifnya dioptimasi.

2.7.2

Pembentukan Model Matematik

Tahap berikutnya yang harus dilakukan setelah memahami permasalahan optimasi adalah membuat model yang sesuai untuk analisis. Pendekatan konvensional riset operasional

untuk

pemodelan

adalah

membangun

model

matematik

yang

menggambarkan inti permasalahan. Kasus dari bentuk cerita diterjemahkan ke model


19

matematik. Model matematik merupakan representasi kuantitatif tujuan dan sumber daya yang membatasi sebagai fungsi variabel keputusan. Model

matematika

permasalahan optimal terdiri dari dua bagian. Bagian pertama memodelkan tujuan optimasi. Model matematik tujuan selalu menggunakan bentuk persamaan. Bentuk persamaan digunakan karena kita ingin mendapatkan solusi optimum pada satu titik. Fungsi tujuan yang akan dioptimalkan hanya satu. Bukan berarti bahwa permasalahan optimasi hanya dihadapkan pada satu tujuan. Tujuan dari suatu usaha bisa lebih dari satu. Tetapi pada bagian ini kita hanya akan tertarik dengan permasalahan optimal dengan satu tujuan.

Bagian kedua merupakan model matematik yang merepresentasikan sumber daya yang membatasi. Fungsi pembatas bisa berbentuk persamaan (=) atau pertidaksamaan (≤ atau ≥). Fungsi pembatas disebut juga sebagai konstrain. Konstanta (baik sebagai koefisien maupun nilai kanan) dalam fungsi pembatas maupun pada tujuan dikatakan sebagai parameter model. Model matematika mempunyai beberapa keuntungan dibandingakan pendeskripsian permasalahan secara verbal. Salah satu keuntungan yang paling jelas adala model matematik menggambarkan permasalahan secara lebih ringkas. Hal ini cenderung membuat struktur keseluruhan permasalahan lebih mudah dipahami, dan membantu mengungkapkan relasi sebab akibat penting. Model matematik juga memfasilitasi yang berhubungan dengan permasalahan dan keseluruhannya dan mempertimbangkan semua keterhubungannya secara simultan. Terakhir, model matematik membentuk jembatan ke penggunaan teknik matematik dan komputer kemampuan tinggi untuk menganalisis permasalahan.

Di sisi lain, model matematik mempunyai kelemahan. Tidak semua karakteristik sistem dapat dengan mudah dimodelkan menggunakan fungsi matematik. Meskipun

dapat

dimodelkan

dengan

fungsi

matematik,

kadang-kadang

penyelesaiannya sulit diperoleh karena kompleksitas fungsi dan teknik yang dibutuhkan.


20

Bentuk umum pemrograman linier adalah sebagai berikut : Fungsi tujuan :

Maksimumkan atau minimumkan z = c1x1 + c2x2 + ... + cnxn Sumber daya yang membatasi : a11x1 + a12x2 + ... + a1nxn = /≤ / ≥ b1 a21x1 + a22x2 + … + a2nxn = /≤ / ≥ b2 … am1x1 + am2x2 + … + amnxn = /≤ / ≥ bm x1, x2, …, xn ≥ 0 Simbol x1, x2, ..., xn (xi) menunjukkan variabel keputusan. Jumlah variabel keputusan (xi) oleh karenanya tergantung dari jumlah kegiatan atau aktivitas yang dilakukan untuk mencapai tujuan.

Simbol c1,c2,...,cn merupakan kontribusi masing-masing

variabel keputusan terhadap tujuan, disebut juga koefisien fungsi tujuan pada model matematiknya.Simbol a11, ...,a1n,...,amn merupakan penggunaan per unit variabel keputusan akan sumber daya yang membatasi, atau disebut juga sebagai koefisien fungsi kendala pada model matematiknya. Simbol b1,b2,...,bm menunjukkan jumlah masing-masing sumber daya yang ada. Jumlah fungsi kendala akan tergantung dari banyaknya sumber daya yang terbatas. Pertidaksamaan terakhir (x1, x2, …, xn ≥ 0) menunjukkan batasan non negatif. Membuat model matematik dari suatu permasalahan bukan hanya menuntut kemampuan matematik tapi juga menuntut seni permodelan. Menggunakan seni akan membuat permodelan lebih mudah dan menarik.

Kasus pemrograman linier sangat beragam. Dalam setiap kasus, hal yang penting adalah memahami setiap kasus

dan memahami konsep permodelannya.

Meskipun fungsi tujuan misalnya hanya mempunyai kemungkinan bentuk maksimisasi atau minimisasi, keputusan untuk memilih salah satunya bukan pekerjaan mudah. Tujuan pada suatu kasus bisa menjadi batasan pada kasus yang lain. Harus


21

hati-hati dalam menentukan tujuan, koefisien fungsi tujuan, batasan dan koefisien pada fungsi pembatas.

Pemograman linier dapat diterapkan pada berbagai bidang studi. Metode ini paling banyak digunakan dalam bisnis dan ekonomi namun juga dapat dimanfaatkan dalam sejumlah perhitungan ilmu teknik. Misalnya dalam ekonomi, fungsi tujuan dapat berkaitan dengan pengaturan sevara optimal sumber-sumber daya untuk memperoleh keuntungan maksimal atau biaya minimal sedangkan fungsi batasan menggambarkan batasan-batasan kapasitas yang tersedia yang dialokasikan secara optimal keberbagai kegiatan. Industry yang memanfaatkan pemograman linier diantaranya adalah transportasi, energy, telekomunikasi dan manufaktur. Pemograman linier juga terbukti berguna dalam membuat model berbagai jenis masalah dalam perencanaan perancangan rute, penjadwalan, pemberian tugas dan desain.

2.8

Jenis – Jenis Program Integer

Banyak aplikasi kegunaan dari integer programming, misalnya dalam perhitungan produksi sebuah perusahaan manufaktur, dimana hasil dari perhitungannya haruslah bilangan bulat, karena perusahaan tidak dapat memproduksi produknya dalam bentuk setengah jadi. Misal perusahaan perakitan mobil tidak dapat merakit 5,3 mobil A dan 2,5 mobil B perhari, tetapi haruslah bilangan bulat, dengan metode pembulatan, bias kita hasilkan misalnya 5 mobil A dan 2 mobil B per hari, tetapi apakah metode pembulatan ini efisien?.

Terdapat 3 macam permasalahan dalam pemrograman integer, yaitu: 1. Pemrograman Bulat Murni, yaitu kasus dimana semua variabel keputusan harus berupa bilangan bulat.

2. Pemrograman Bulat Campuran, yaitu kasus dimana beberapa, tapi tidak semua, variabel keputusan harus berupa bilangan bulat.


22

3. Pemrograman Bulat Biner (Binary Integer), yaitu kasus dengan permasalahan khusus dimana semua variabel keputusan harus bernilai 0 dan 1.

2.8.1

Program Integer Murni (Pure Integer Programming)

Menurut Hillier dan Lieberman (1994), model matematika untuk pemrograman bilangan bulat sama dengan model pemrograman linear, dengan penambahan satu batasan yaitu batasan bahwa semua atau sebagian nilai variabelnya berupa bilangan bulat. Jika semua nilai variabelnya bilangan bulat, maka pemrograman ini disebut pemrograman bilangan bulat murni,

Program Integer dibutuhkan ketika keputusan harus dilakukan dalam bentuk bilangan bulat (bukan pecahan yang sering terjadi bila kita gunakan metode simpleks).Model matematis dari pemrograman bulat sebenarnya sama dengan model linier programming, dengan tambahan batasan bahwa variabelnya harus bilangan bulat.

Bentuk umum dari program integer murni adalah : Optimasikan ∑ Dengan kendala ∑


23

2.8.2

Program Integer Campuran

Program integer campuran adalah masalah integer programming dengan beberapa variabel keputusannya dibatasi sebagai bilangan bulat, dan sementara yang lain tidak.

Bentuk umum dari program integer campuran adalah Optimasikan ∑

∑

Dengan kendala ∑

2.8.3

∑

Binary Integer Programming

Model pemrograman bulat dapat juga digunakan untuk memecahkan masalah dengan jawaban ya atau tidak (yes or no decision), untuk model ini variabel dibatadi menjadi dua, misal 1 dan 0, jadi keputusan ya atau tidak diwakili oleh variabel, katakanlah,

,

menjadi : {

Model ini sering disebut sebagai model pemrograman bulat biner.

Adapun bentuk umum dari binary integer programming adalah Optimasikan


24

∑

2.9

Konsep Dasar Graf

Graf G didefinisikan sebagai pasangan terurut himpunan (V,E) yang dalam hal ini V = {

} adalah himpunan tak kosong dan anggota-anggotanya dinamakan

simpul (vertex) dan E = {

} adalah himpunan sisi (edge) yang

menghubungkan sepasang simpul. Graf G dilambangkan dengan G = (V,E) menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan tdak memiliki sisi satu pun, tetapi simpulnya harus ada minimal satu. Gelang (loop) adalah sebuah sisi yang berawal dan berakhir pada simpul yang sama. Sisi paralel adalah dua buah sisi yang berbeda yang menghubungkan simpul yang sama. Dua buah simpul pada graf tak berarah G dikatakan bertetangga (adjacent) bila keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain, bertetangga dengan

jika (

Untuk sebarang sisi e =( dan

) adalah sebuah sisi pada graf G.

), sisi e dikatakan bersisian (incident) dengan

. Simpul terpencil (isolated vertex) adalah simpul yang tidak mempunyai sisi

yang bersisian dengannya atau dapat juga dinyatakan bahwa simpul terpencil adalah simpul yang bertetangga dengan simpul-simpul lainnya. Graf yang himpunan sisinya merupakan himpunan kosong disebut sebagai graf kosong (null graph) dan ditulis sebagai

, yang dalam hal ini n adalah jumlah simpul.

Misalkan G adalah suatu graf. Graf H dikatakan subgraf G jika: a. V(H)

V(H)

b. E(H)

E(G)

c. Setiap sisi dalam H mempunyai simpul ujung yang sama dengan sisi dalam G.


25

2.10 Jenis – Jenis Graf

Graf sederhana (simple graph) adalah graf yang tidak mengandung gelang (loop) maupun sisi ganda.

Gambar 2.4 Graf Sederhana

Graf tak sederhana (unsimple graph) adalah graf yang mengandung gelang (loop) maupun sisi ganda. Ada 2 macam graf tak sederhana yaitu : 1. Graf ganda (multigraph), yaitu graf yang mengandung sisi ganda. Sisi ganda yang menghubungkan sepasang simpul bisa lebih dari dua buah. 2. Graf semu (pseudograph), yaitu graf yang mengandung gelang (loop).

Gambar 2.5 Graf Ganda dan Graf Semu

Graf berhingga (limited graph) adalah graf yang jumlah simpulnya berhingga.

Graf tak berhingga (unlimited graph) adalah graf yang jumlah simpulnya tidak berhingga banyaknya.

Graf berarah (directed graph) adalah graf yang setiap sisinya diberikan orientasi arah. Kita sebut sisi berarah pada graf dengan sebutan busur. Pada graf berarah, ( , (

) menyatakan dua buah busur yang berbeda, dengan kata lain (

) dan )


26

(

). Untuk busur (

), simpul

dinamakan simpul asal dan simpul

dinamakan simpul terminal (simpul akhir).

Gambar 2.6 Graf Berarah

Graf tak berarah (undirecred graph) adalah graf yang sisinya tidak mempunyai orientasi arah. Pada graf tak berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, (

)

(

) adalah sisi yang sama.

Gambar 2.7 Graf Tak Berarah

Graf G dikatakan graf berbobot jika setiap sisinya diberi bobot (bilangan). Jika sisi diberi label k, maka bobot sisi

adalah k.

Gambar 2.8 Graf Berbobot


BAB 2 LANDASAN TEORI

Recommend Documents