MODEL TELEKOMUNIKASI DAN LOKASI

MODEL TELEKOMUNIKASI DAN LOKASI

TESIS

Oleh JANUASI SIMARMATA 077021060

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009

Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

MODEL TELEKOMUNIKASI DAN LOKASI

TESIS

Diajukan Sebagai Salah Satu Syarat untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh JANUASI SIMARMATA 077021060/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009


Judul Tesis Nama Mahasiswa Nomor Pokok Program Studi

: : : :

MODEL TELEKOMUNIKASI DAN LOKASI Januasi Simarmata 077021060 Matematika

Menyetujui, Komisi Pembimbing

(Dr. Saib Suwilo, M.Sc) Ketua

Ketua Program Studi

(Prof. Dr. Herman Mawengkang)

Tanggal lulus: 27 Mei 2009


(Prof. Dr. Herman Mawengkang) Anggota

Direktur

(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)

Telah diuji pada Tanggal: 27 Mei 2009

PANITIA PENGUJI TESIS Ketua

: Dr. Saib Suwilo, M.Sc

Anggota

: 1. Prof. Dr. Opim Salim S, M.Sc. 2. Prof. Dr. Herman Mewengkang 3. Drs. Marihat Situmorang, M. Kom


ABSTRAK Tesis ini membahas model untuk pola jaringan telekomunikasi dimana terdapat problem lokasi yang dilibatkan. Kemudian bagaimana mengklasifikasikan model ke dalam tiga klas sebagai model dinamik yang tidak berkapasitas dan berkapasitas. Pada tiap klas akan dibahas problem inti yaitu generalisasinya dan metode solusi pada literaturnya. Oleh sebab itu, dipresentasikan relaksasi Lagrange berdasarkan prosedur solusi untuk menyelesaikan formulasi nonlinier ini. Selanjutnya direpresentasikan model Chardaire, P. et al. (1999) untuk mendesain jaringan bintang dengan konsentrator tingkat kedua sebagai contoh tiap terminal dihubungkan pada konsentrator tingkat pertama yang juga dihubungkan pada konsentrator tingkat kedua. Semua konsentrator tingkat kedua dihubungkan pada pusat unit. Tesis ini juga menyajikan formulasi dua program integer dan ditunjukkan bahwa relaksasi linier dari kedua formulasi untuk bound yang sama.

Kata kunci: Telekomunikasi, Lokasi, Jaringan Komputer, Model Tidak Berkapasitas, Model Berkapasitas, Model Dinamik.

i Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

ABSTRACT This thesis reviews the models for telecommunication network design where there is a location problem involved. Then to classify the models into three classes as uncapacitated, capacitated and dynamic models. For each class, we study the core problem, its generalizations and the solution methods in the literature. Thus this thesis presents Lagrangian Relaxation based solution procedure to solve this nonlinear formulation. Then we present a model due to Chardaire, P. et al. (1999) for designing a star network with two levels of concentrators, i.e. each terminal is connected to a first level concentrator which is connected to a second level concentrator. All second level concentrators are connected to a central unit. Finally we propose two integer programming formulations and show that the linear relaxations of both formulations lead to the same bound.

Keyword: Telecommunication, Location, Desain of Network, Uncapacitated Models, Capacitated models, Dynamic Models.

ii Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

KATA PENGANTAR Dengan rendah hati, penulis mengucapkan puji syukur kehadirat Tuhan Yang Maha Esa atas anugra dah berkat-Nya yang telah diberikan, sehingga penulis dapat menyelesaikan tesis ini dengan berjudul Model Telekomunikasi dan Lokasi. Tesis ini merupakan persyaratan penyelesaian studi pada Program Studi Matematika SPs Universitas Sumatera Utara. pada kesempatan ini, penulis menyampaikan ucapan terima kasih dan penghargaan yang sebesar-besarnya kepada : Gubernur Sumatera Utara dan Kepala Bappeda Provinsi Sumatera Utara beserta Staffnya yang telah memberikan Bea Siswa kepada penulis serta Kepala Dinas Pendidikan Kota Medan yang telah memberikan izin kepada Penulis untuk mengikuti perkuliahan di Sekolah Pasca Sarjana Program Studi Magister Matematika Prof. dr. Chairuddin P. Lubis, DTM&H, Sp.A(K) selaku Rektor Universitas Sumatera Utara. Prof. Dr. Ir. Chairun Nisa B., M.Sc selaku Direktur Sekolah Pascasarjana yang telah memberikan kesemaptan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara Medan. Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister Matematika SPs Universitas Sumatera Utara, dan juga sebagai Pembanding yang telah banyak membantu dalam penulisan tesis ini. Dr. Saib Suwilo, M.Sc selaku sekretaris Program Studi Magister Matematika SPs Universitas Sumatera Utara dan juga sebagai ketua komisi pembimbing yang telah banyak membantu dalam penulisan tesis ini.

iii Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

Prof. Dr. Opim Salim S, MSc sebagai anggota komisi pembimbing dan Drs. Marihat Situmorang, M.Kom sebagai Komisi Pembanding yang telah banyak memberi saran dan masukan dalam penulisan tesis ini. Seluruh Staf Pengajar pada Program Studi Matematika SPs Universitas Sumatera Utara, yang telah memberikan ilmunya selama masa perkuliahan. Drs. Daeng Malewa, MM sebagai pengurus Yayasan Perguruan Josua yang telah memberikan kesempatan dan dukungan kepada penulis sehingga dapat menyelesaikan tesis ini. Seluruh rekan-rekan mahasiswa angkatan ke-lima tahun 2007 Program Studi Matematika SPs Universitas Sumatera Utara atas kerjasama dan kebersamaan dalam mengatasi berbagai masalah yang dihadapi selama perkuliahan, sehingga tugas-tugas bersama dapat diselesaikan dengan baik, Misiani, S.Si selaku Staf Administrasi program studi Matematika SPs Universitas Sumatera Utara yang telah memberikan pelayanan yang baik kepada penulis. Secara khusus penulis menyampaikan rasa terima kasih kepada istri tercinta Meri Toropida br. Tampubolon yang banyak memberikan bantuan moril, serta materi dan anakku tersayang Lester Arison H. Simarmata yang telah memberikan dukungan dan semangat kepada penulis, serta seluruh keluarga berkat dorongan dan perhatiannya yang disertai dengan doanya, penulis dapat menyelesaikan pendidikan ini.

iv Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

Penulis menyadari tesis ini masih mempunyai kekurangan, namun demikian harapan penulis semoga tesis ini dapat bermanfaat bagi yang membutuhkannya.

Medan, 27 Mei 2009 Penulis,

Januasi Simarmata

v Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

RIWAYAT HIDUP Januasi Simarmata dilahirkan di Ramunia, Kab. Deli Serdang pada Tanggal 12 Maret 1960 dan merupakan anak ke tiga dari lima bersaudara, dari Ayah DJ. Simarmata (Alm) dan Ibu T.Br. Tampubolon (Almh). Menamatkan Sekolah Dasar (SD) Advent di Ramunia Tahun 1973, Sekolah Menengah Pertama (SMP) Nasional Ramunia Tahun 1977 dan Sekolah Menengah Atas (SMA) Jurusan IPA di SMA Neger 223 Lubuk Pakam. Pada tahun 1980 memasuki perguruan Tinggi FMIPA IKIP Negeri Medan jurusan Matematika dan memperoleh Gelar Sarjana Pendidikan Tahun 1984. pada tanggal 10 Nopember 1986 menikah dengan Meri Toropida br. Tampubolon dan telah dikarunia satu orang anak putra, Lester Arison H. Simarmata, saat ini duduk di Semester II APIKES IMELDA Medan. Tahun 1985 diterima menjadi staf pengajar di SMA Swasta Josua Medan dan Tahun 1990 menjadi PNS ditempatkan di SMK Negeri Kotanopan Tapanuli Selatan kemudian Tahun 1992 kembali bertugas di SMA Swasta Josua Medan. Tahun 2004 dipercaya oleh Pengurus Yayasan Perguruan Josua Medan menjabat sebagai Kepala Sekolah SMK BM Josua Medan kemudian mengikuti pendidikan program Studi Magister Matematika Sekolah Pascasarjana USU Medan tahun 2007.

vi Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

DAFTAR TABEL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ix

DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

x

DAFTAR ISTILAH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

xi

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

3.1 Telekomunikasi dan Jenis-Jenis Telekomunikasi . . . . . . . . . .

13

3.1.1 Jaringan Komputer . . . . . . . . . . . . . . . . . . . . . . . . .

16

3.1.2 Tipe Jaringan Komputer . . . . . . . . . . . . . . . . . . . . .

18

3.1.3 Topologi Jaringan Komputer . . . . . . . . . . . . . . . . . .

20

vii Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

3.1.4 Analisis Pemilihan Topologi . . . . . . . . . . . . . . . . . . .

23

3.2 Program Linier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

3.2.1 Dualitas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

3.2.2 Metode Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

3.3 Program Integer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

BAB 4 MODEL TELEKOMUNIKASI DAN LOKASI . . . . . . . . . . . . . .

40

4.1 Masalah Fasilitas Lokasi yang Uncapacitated (MFLU) . . . . . .

40

4.2 Sifat Polihedral MLKC dan Metode Solusi Exact . . . . . . . . .

50

4.3 Relaksasi Lagrange Berdasarkan Heuristik . . . . . . . . . . . . . .

55

4.4 Generasilasi Model MLKC . . . . . . . . . . . . . . . . . . . . . . . . .

60

4.4.1 MLKC dengan Banyak Tipe Konsentrator . . . . . . . . .

60

4.4.2 MLKC dengan Konsentrator Ganda . . . . . . . . . . . . .

61

4.5 Masalah Fasilitas Lokasi Dinamik . . . . . . . . . . . . . . . . . . . .

62

BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

viii Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

DAFTAR TABEL

Nomor

Judul

3.1

Keuntungan dan Kerugian Jenis Topology . . . . . . . . . . . . . . . .

ix Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

Halaman 24

DAFTAR GAMBAR

Nomor

Judul

Halaman

1.1

Koneksi yang penuh/Jaringan Pohon . . . . . . . . . . . . . . . . . . .

3

1.2

Bintang/Jaringan Bintang . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3

Jaringan Jalur/Bintang . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

3.1

Gambaran Umum Model Komunikasi . . . . . . . . . . . . . . . . . . .

13

3.2

Local Area Network (LAN) . . . . . . . . . . . . . . . . . . . . . . . . . .

19

3.3

Metropolitan Area Network (MAN) . . . . . . . . . . . . . . . . . . . .

20

3.4

Wide Area Network (WAN) . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.5

Topology Bus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

3.6

Topology Bintang (Star) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.7

Topology Cincin (Ring) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

x Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

DAFTAR ISTILAH

MFLU

Masalah Fasilitas Lokasi yang Uncapacitated

MLKC

Masalah Lokasi Konsentrator Capacitated

LAN

Local Area Network

MAN

Metropolitan Area Network

WAN

Wide Area Network

PL

Program Linier

PLBB

Program Linier Bilangan Bulat

PNL

Program Non Linier

PINL

Program Integer Non Linier

MFLD

Masalah Fasilitas Lokasi Dinamik

xi Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

BAB 1 PENDAHULUAN

1.1 Latar Belakang Penggunaan jaringan telekomunikasi telah berubah dalam beberapa dekade terakhir. Konsep jaringan telekomunikasi untuk telepon sekarang sudah ketinggalan jaman. Jaringan telekomunikasi baru tentunya membawa perubahan dengan tidak terdapatnya perbedaaan suara, video atau data trafik. Sebagian besar dari masa depan telekomunikasi akan dijalankan melalui Internet. Revolusi ini yang telah dimulai beberapa tahun yang lalu, ditandai oleh pertumbuhan yang spektakuler dari trafik yaitu trafik meningkat dua kali lipat setiap sepuluh bulan (Gourdin, E. et al, 2001). Faktor penting lain dalam evolusi jaringan, khususnya di Eropa, adalah liberalisasi dari telekomunikasi pasar, memaksa operator untuk menyesuaikan diri dengan cepat ke lingkungan baru yang kompetitif. Konteks untuk pengembangan generasi jaringan telah berubah cukup banyak sehingga menimbulkan masalah baru, yaitu memilih lokasi yang optimal untuk konsentrator node, terutama bila dikombinasikan dengan fitur-fitur lainnya dari jaringan telekomunikasi baru. Ini menjelaskan banyaknya kepentingan peneliti dalam masalah seperti itu. Untuk penelitian sebelumnya telah dilakukan oleh Boffey T.B. et al (1989). Pada umumnya jaringan telekomunikasi, yang trafiknya dikumpulkan dari berbagai sumber, secara progresif digabungkan untuk mengisi link sehingga meningkatkan kapasitas dan akhirnya diteruskan pada terminal. Oleh karena itu, sebagian besar jaringan telekomunikasi secara alami terstruktur dalam hirarki 1 Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

2 lapisan multi-arsitektur. Pada tingkat yang lebih rendah dari sebuah arsitektur tersebut, trafik dikumpulkan untuk dikirim ke suatu tingkat atas. Walaupun jaringan telekomunikasi (suara, video atau data di seluruh negeri atau internasional) biasanya menjadi terstruktur pada banyak tingkat tersebut, sebagian besar masalah desain dianggap oleh perusahaan-perusahaan telekomunikasi hanya bagian dari keseluruhan jaringan. Jaringan telekomunikasi generik terdiri dari jaringan akses yang menghubungkan terminal (pengguna node) ke konsentrators (saklar atau multiplexers) dan jaringan tulang punggung (backbone) yang berhubungan antar konsentrators atau menghubungkannya ke pusat unit (root). Jaringan telekomunikasi berbeda dalam desain jaringan akses dan jaringan backbone. Terminal ini dapat dihubungkan ke konsentrators oleh titik-titik link yang hasilnya dalam topologi bintang atau mungkin dihubungkan oleh link yang banyak menurun dan dapat memiliki pohon, path atau struktur lingkar. Sama halnya terdapat perbedaaan topologies untuk jaringan backbone. Jaringan ini dapat sepenuhnya terhubung. Jika ada sebuah pusat unit, kemudian jaringan backbone dapat berupa bintang, pohon atau path. Ada juga beberapa model di mana terminal dapat terhubung langsung ke pusat unit. Untuk menentukan struktur suatu jaringan, digunakan notasi oleh Klincewicz J.G (1998) yang merupakan ”struktur backbone/struktur jaringan akses”. Misalnya, jaringan pohon/bintang berarti bahwa jaringan backbone adalah pohon dan jaringan akses adalah jaringan bintang, dihasilkan beberapa contoh jaringan telekomunikasi dalam Gambar 1.1 sampai 1.3 berikut:


3

Gambar 1.1 Koneksi yang penuh/Jaringan Pohon

Gambar 1.2 Bintang/Jaringan Bintang

Gambar 1.3 Jaringan Jalur/Bintang


4 Masalah lokasi untuk desain jaringan telekomunikasi kembali ke pada tahun 1960-an ketika Hakimi, (1964 dan 1965) memperkenalkan l-median dan p-median untuk melokasikan pusat saklar dalam jaringan komunikasi. Sejak itu banyak model yang dikembangkan untuk menggunakan desain yang berbeda. Sebelum membahas model ini, berikut terdapat beberapa pertanyaan dasar yang terkait dengan desain jaringan telekomunikasi:

a. berapa konsentrators diperlukan, b. dimana seharusnya konsentrators dilokasikan, c. apa sebaiknya kapasitas dari konsentrators ini, d. bagaimana sebaiknya terminal ditugaskan pada konsentrators, e. bagaimana terminal ditugaskan pada konsentrators yang dihubungkan ke konsentrator dan bagaimana kapasitas dari link, f. bagaimana konsentrators sebaiknya terhubung ke satu sama lain atau ke pusat node dan bagaimana kapasitas dari link yang digunakan.

Sulit untuk mengembangkan model yang dapat memberi jawaban untuk semua pertanyaan di atas secara bersamaan. Jadi, yang biasanya dilakukan dalam desain yang berulang dengan cara sebagai berikut:

a. Memutuskan jumlah lokasi konsentrators dan penugasan dari terminal ke konsentrators. b. Desain jaringan akses


5 c. Desain jaringan backbone.

Ide dari metode yang berulang bahwa setiap lokasi konsentrators dan penugasan dari terminal ke konsentrators dilakukan, maka desain jaringan akses dan desain jaringan backbone menjadi independen dan dapat ditangani secara terpisah. Beberapa model dijumpai dalam literatur hanya menangani tahap lokasi saja, sementara beberapa model yang lain mempertimbangkan tahap lokasi dan desain sekaligus mengasumsikan beberapa topologi untuk jaringan akses dan jaringan backbone. Desain model jaringan telekomunikasi juga berbeda evaluasinya pada proses terbentuknya jaringan. Ketika mengevaluasi suatu desain jaringan, tentunya berhubungan dengan masalah seperti biaya pembentukan jaringan, biaya operasi jaringan, reliabilitasnya dan kemampuan untuk mensuplai kebutuhan terminal dalam kurun waktu yang wajar. Sementara beberapa model hanya tertarik dalam meminimalkan biaya jaringan, beberapa orang lain mempertimbangkan baik biaya jaringan dan rata-rata biaya keterlambatan. Keandalan isu yang biasanya ditangani oleh terhubungnya jaringan terminal pada beberapa konsentrators. Terdapat juga model yang mempertimbangkan pengembangan dari jaringan telekomunikasi dari waktu ke waktu. Model tersebut bersedia untuk mengoptimalkan perluasan kapasitas link atau juga diperbolehkan untuk memasang konsentrators baru. Model ini disebut dinamik. 1.2 Perumusan Masalah Penelitian ini membahas model untuk pola jaringan telekomunikasi dimana terdapat problem lokasi yang dilibatkan. Kemudian bagaimana mengklasifikasikan


6 model ke dalam tiga klas sebagai model dinamik yang tidak berkapasitas dan berkapasitas. Pada tiap klas akan dibahas problem inti yaitu generalisasinya dan metode solusi pada literaturnya. 1.3 Tujuan Penelitian Adapun tujuan dalam penelitian ini adalah untuk menentukan model pada pola jaringan telekomunikasi dimana terdapat problem lokasi yang dilibatkan. Kemudian mengklasifikasikan model ke dalam tiga klas sebagai model dinamik yang tidak berkapasitas dan berkapasitas, dan membahas problem inti yaitu generalisasinya dan metode solusinya. 1.4 Kontribusi Penelitian Adapun kontribusi dalam penelitian ini adalah dapat membantu peneliti atau pembuat keputusan untuk menentukan model dan solusi terbaik yang digunakan pada pola jaringan telekomunikasi. 1.5 Metodologi Penelitian Penelitian ini bersifat literatur dan dilakukan dengan mengumpulkan informasi dari referensi beberapa buku dan jurnal. Penelitian ini awalnya memperkenalkan tentang pengertian telekomunikasi dan jenis-jenis telekomunikasi, jaringan komputer dan tipe jaringan, serta struktur topology dan analisis pilihan topology lalu menjelaskan tentang program integer selanjutnya model yang uncapacitated, dilanjutkan dengan menjelaskan model yang capacitated serta model dinamic. Kemudian akan diperlihatkan model telekomunikasi pada masalah lokasi yang dilibatkan, yang pada akhirnya dilakukan pengambilan kesimpulan.


BAB 2 TINJAUAN PUSTAKA

Model lokasi uncapacitated untuk jaringan telekomunikasi berhubungan dengan lokasi konsentrators dan tugas dari terminal pada konsentrators ini dengan pengasumsian bahwa tidak ada kendala kapasitas untuk konsentrators. Beberapa model juga menentukan link dari jaringan backbone dan jaringan akses. Biasanya model ini menganggap struktur awal utuk jaringan ini. Masalah Fasilitas Lokasi yang Uncapacitated (MFLU) merupakan inti masalah untuk desain dari jaringan telekomunikasi yang uncapacitated. Model ini merupakan generalisasi MFLU atau termasuk dalam MFLU sebagai subproblem. MFLU dapat dinyatakan sebagai berikut: diberikan himpunan terminal N dan menetapkan lokasi mungkin untuk konsentrators M, menentukan jumlah lokasi konsentrators dan menetapkan terminal pada konsentrators ini. Tujuannya adalah untuk meminimalkan jumlah biaya instalasi konsentrators dan biaya layanan terminal melalui konsentrators yang terpasang. Perumusan MFLU adalah sebagai berikut: min

XX i∈N j∈M

+

X

Fj yj

(2.1)

j∈M

Kendala X

xij = 1∀i ∈ N

(2.2)

j∈M

xij ≤ yj

∀i ∈ N, j ∈ M

(2.3)

xij ∈ {0.1} ∀i ∈ N, j ∈ M

(2.4)

yj ∈ {0, 1} ∀j ∈ M

(2.5) 7


8 dimana Cij dinotasikan biaya dari tugas terminal i pada konsentrators di lokasi j, Fj merupakan biaya konsentrators yang ditetapkan pada lokasi j, untuk semua i ∈ N dan j ∈ M. Kendala (2.2) dan (2.4) menyatakan bahwa tiap-tiap terminal akan ditandai tepat pada konsentrator dan kendala (2.3) menyatakan terminal dapat ditandai ke konsentrator hanya jika konsentratornya diinstal. MFLU dapat diselesaikan sebagai langkah prosedur pola iteratif. Kemudian backbone dan jaringan akses dapat didesain secara terpisah. Terdapat juga model yang menganggap lokasi konsentrator dan desain jaringan backbone serta jaringan akses secara terus menerus. Model ini bermacam-macam pemilihan topologi jaringannya. Beberapa jaringan memiliki pusat unit. Jika konsentrator dapat secara langsung dihubungkan pada pusat unit, maka jaringan backbone adalah bintang. Tetapi jika biaya pembangunan link ini tinggi, maka jaringan backbone dapat berupa pohon atau path. Jika tidak terdapat pusat unit, maka konsentrator dihubungkan pada masing-masing. Jika respon waktu dan reliability kritis, maka jaringan dapat menjadi jaringan yang sempurna. Tetapi sekali lagi jika biaya pembangunan link tinggi, maka jaringan dapat dioptimalkan. Beberapa argumen diaplikasikan untuk akses jaringan. Terminal dapat dihubungkan ke konsentrator secara langsung membentuk jaringan bintang disekitar konsentrator. Yang lainnya berupa jaringan pohon atau path. Pada kenyataannya, jika didefinisikan Cij merupakan biaya pembangunan link antar terminal i dan konsentrator j dan Fj merupakan biaya instal konsentrator pada lokasi j dan menghubungkannya pada pusat unit, maka MFLU sesuai pada desain bintang/jaringan bintang. Marianov et al (1996) menyatakan MFLU dengan tambahan kendala menetapkan ambang batas peluang dari seluruh konsentrators yang sibuk. Penelitian


9 tersebut memasukkan kualitas layanan dalam model. Sehingga kendala ditulis dalam bentuk yang patuh dan diasumsikan sebagai M/M/1 sistem antrian. Kemudian ditentukan beberapa kendala dalam rumus p-median dan menghasilkan perhitungan penelitian menggunakan CPLEX versi 3.0 pada model ini. Helme et al (1989) menyatakan desain dari jaringan telekomunikasi satelit. Tiap terminal secara langsung ditugaskan pada konsentrators dan konsentrators secara langsung ditugaskan pada pusat unit membentuk jaringan bintang. Perbedaaan model ini dengan MFLU adalah terletak pada biaya operasi konsentrators. Jika dua terminal ditugaskan pada konsentrators yang sama maka digunakan kapasitas skalar lokal pada konsentrator. Di lain pihak, jika ditugaskan pada dua konsentrators yang berbeda maka digunakan kapasitas dari dua konsentrator tersebut. Untuk menghitung biaya produksi konsentrator, penting untuk membedakan trafik antara terminal yang ditugaskan pada konsentrator yang sama dan trafik antara terminal ditugaskan ke konsentrator yang berbeda. Andaikan C merupakan unit biaya per kapasitas dari konsentrator dan S merupakan unit biaya perkapasitas dari lokal switch pada konsentrator. Didefinisikan tik trafik antara dua terminal i dan k dan ti semua trafik pada terminal i, sebagai contoh: t1 =

X

tik +

k∈N

X

tki

k∈N

Himpunan konsentrator pada node i dapat ditandai dengan notasi Mi . Juga dapat didefinisikan Mik = Mi ∩ Mk . Selanjutnya fungsi biaya pada variant MFLU menjadi: X i∈N

tj

X j∈Mi

Cij xij −(2C−S)

XX

tik

i∈N k∈N

X j∈Mik

xij xkj +

X

Fj yj ( dalam bentuk kuadratik)

j∈M

kendala dan variabel sama seperti MFLU, kemudian dipresentasikan linearisasi untuk problem dan algoritma branch dan bound untuk menyelesaikannya. Selan-


10 jutnya hasil perhitungan diperoleh dengan menggunakan pendekatan eksak dari pada pendekatan heuristik. Sedangkan model capacitated dibangun untuk menentukan lokasi konsentrator dan penugasan terminal tanpa melanggar kapasitas kendala konsentrator. Kapasitas ini dapat didefinisikan dalam bentuk jumlah terminal yang ditugaskan konsentrator atau bentuk dari permintaan terminal. Problem ini sama dengan MFLU dengan sumber tunggal, sebagai contoh tiap titik permintaan dapat ditugaskan pada fasilitas tunggal dan juga disebut dengan Masalah Lokasi Konsentrator Capacitated (MLKC) (Mirzaian (1985), Klincewicz dan Luss (1986)). MLKC didefinisikan sebagai berikut: diberikan himpunan terminal N dengan permintaan yang diketahui d untuk tiap terminal i ∈ N , dan himpunan lokasi konsentrators yang mungkin M dengan kapasitas Qj untuk tiap j ∈ M, tujuannya adalah untuk menetapkan konsentrators dan menugaskan tiap terminal secara langsung ke salah satu konsentrators sehingga biaya total penetapan konsentrators dan biaya penugasan terminal ke konsentrators minimal serta kapasitas konsentrators efesien untuk mensuplai permintaan terminal yang ditugaskan. Parameter dan variabel lain didefinisikan dalam MFLU. MLKC dapat diformulasikan sebagai berikut: min

XX i∈N j∈M


Cij xij +

X j∈M

Fj yj

(2.6)

11 kendala X

xij = 1 ∀i ∈ N

(2.7)

di xij ≤ Qj yj

(2.8)

j∈M

X

∀j ∈ M

i∈N

xij ∈ {0, 1} ∀i ∈ N, ∀j ∈ M yj ∈ {0, 1} ∀j ∈ M

(2.9) (2.10)

kendala (2.7) dan (2.9) menjamin tiap terminal ditugaskan tepat pada konsentrator dan kendala (2.8) menjamin bahwa terminal i ditugaskan ke konsentrator j hanya jika konsentrator diinstal pada lokasi j dan kapasitas dari konsentrator ini dapat mengirim permintaan semua terminal yang ditugaskan. Fungsi biaya (2.6) merupakan jumlah biaya dari penugasan terminal ke konsentrator dan biaya instal konsentrator. Sebagai formula alternatif dapat diperoleh dengan mengganti kendala (2.8) dengan kendala berikut: X

di xij ≤ Qj yj

∀j ∈ M

(2.11)

∀i ∈ N, j ∈ M

(2.12)

i∈N

xij ≤ yj

atau secara sederhana dengan menambah kendala (2.12) ke formula yang di atas. Sama halnya dengan MFLU, MLKC dapat diselesaikan sebagai tahap pertama dari prosedur iteratif untuk mendesain jaringan telekomunikasi. Lebih lanjut, juga disesuaikan untuk desain topology bintang jika biaya ditentukan secara tepat. MLKC adalah problem inti untuk desain jaringan telekomunikasi capacitated. Model capacitated merupakan generalisasi dari MLKC. Sebagai contoh terda-


12 pat model dimana pembuat keputusan dapat menentukan kapasitas konsentrator yang ditetapkan. Problem ini disebut masalah lokasi konsentrator capacitated banyak tipe (Lee, 1993 dan Amiri, 1997). Monticone et al (1994) menyatakan problem merupakan himpunan pasangan komunikasi terminal yang dapat dihubungkan secara langsung atau menggunakan dua konsentrator secara tepat. Tujuannya adalah meminimumkan biaya yang dibentuk pada link dan biaya yang ditetapkan konsentrator. Ini diasumsikan bahwa teknik reduksi diaplikasikan untuk mengurangi waktu perhitungan. Ketika permintaan terminal meningkat melebihi waktu, mungkin penting untuk memperluas ukuran konsentrator dan kapasitas link pada jaringan. Problem perluasan jaringan yang optimal diberikan perencanaan cakrawala untuk peningkatan permintaan disebut dengan Masalah Lokasi Fasilitas Dinamic atau Masalah Fasilitas Lokasi Multiperiode. Balakrishnan et al (1995) menyatakan perluasan jaringan telekomunikasi. Diasumsikan bahwa tidak terdapat konsentrator dalam jaringan pada permulaan dari perencanaan cakrawala. Problemanya adalah menentukan konsentrator dan memperluas ukuran link dengan meminimumkan biaya pada permintaan projek. Kemudian dibangun metode dekomposisi berdasarkan relaksasi lagrange dan program dinamik.


BAB 3 LANDASAN TEORI

3.1 Telekomunikasi dan Jenis-Jenis Telekomunikasi Telekomunikasi berasal dari kata tele dan komunikasi, tele artinya jauh, sedangkan arti komunikasi adalah perpindahan pengetahuan dari sumber ke penerima termasuk percakapan antar manusia dengan medium udara. Kalau diketahui bahwa komunikasi adalah perpindahan pengetahuan dari sumber pengetahuan ke pihak penerima, maka akan berhubungan dengan hal-hal yang berkenaan dengan pengirimaan (sending), penerimaan (receiving) dan pemrosesan (processing) dari informasi menggunakan perangkat listrik. Jadi kalau digabungkan arti dari katakata telekomunikasi dapat diartikan sebagai sebuah proses pengiriman, penerimaan dan pemrosesan informasi jarak jauh sampai ketujuan dengan menggunakan perangkat listrik tepatnya elektronik, sehingga kata telekomunikasi biasanya mengacu pada komunikasi elektronik jarak jauh

Gambar 3.1 Gambaran Umum Model Komunikasi

13 Januasi Simarmata : Model Telekomunikasi Dan lokasi, 2009 USU Repository © 2008

14 Gambar 3.1 adalah gambaran umum model komunikasi. Dengan model dasar seperti pada gambar di atas sumber informasi dapat sampai ketujuan. Source (sumber informasi) : Sumber informasi adalah perangkat komunikasi yang dapat menghasilkan pesan yang akan disampaikan ketujuan. Sumber-sumber komunikasi dapat berupa telepon, perangkat komunikasi radio, atau dari sebuah komputer. Sumber informasi menghasilkan pesan yang akan dikirim. Dalam ruang lingkup komunikasi elektronik, informasi dinyatakan dengan sinyal listrik berbentuk gelombang sinus/cosinus. Pemancar (Transmitter) adalah sebuah perangkat komunikasi yang dapat menyalurkan sumber informasi ke sistem komunikasi. Pemancar melakukan proses modulasi, yaitu menitipkan pesan pada sinyal pembawa (carrier) agar proses komunikasi dapat berjalan dengan baik. Dalam dunia telekomunikasi yang menggunakan udara maka istilah transmitter dikenal dengan nama pemancar, yang akan memancarkan sumber informasi dari mikropon ke media komunikasi yang berupa gelombang elektromagnetik. Saluran atau media komunikasi, dengan menggunakan saluran ini informasi disalurkan sehingga dapat berhubungan dengan para pengguna telekomunikasi yang lain, contoh dari saluran atau media komunikasi adalah udara, kawat atau fiber optik. Noise (Gangguan komunikasi).

Dalam melaksanakan proses komunikasi

pasti akan mendapatkan gangguan komunikasi, noise merupakan energi yang tidak dikehendaki, biasanya bersifat acak (random), hadir dalam sistem transmisi (saluran) dan membawa akibat yang mengganggu jalannya proses komunikasi. Jenisjenis noise antara lain : noise termal, noise atmosfer, noise extraterestrial (noise


15 matahari, noise cosmis), noise industri dan noise internal. Penerima (receiver) melakukan demodulasi yaitu mengambil kembali pesan yang dititipkan pada sinyal pembawa. Setelah diterima oleh rangkaian penerima maka sinyal tadi akan sampai pada tujuan sehingga proses komunikasi jarak jauh akan sampai dan sinyal isyarat yang dikirimkan akan dimengerti oleh tujuan. Tranduscer. Dalam dunia komunikasi akan mengenal perangkat telekomunikasi yang bernama tranduscer. Tranduscer adalah sebuah perangkat yang mengubah satu besaran menjadi bentuk besaran yang lain (dalam hal kelistrikan besaran yang dimaksud adalah besaran listrik, yaitu kuat arus atau tegangan). Pesan yang dikirim dapat berupa apa saja, misalnya sinyal ucapan atau kata-kata, suara, tulisan, gambar, video dan sebagainya. Komunikasi elektronik membutuhkan transducer untuk mengubah pesan non listrik menjadi pesan-pesan yang bersifat listrik. Contohnya, mikrofon diperlukan untuk mengubah getaran suara menjadi sinyal listrik (audio), kamera video mengubah gambar menjadi sinyal listrik (video). Jenis telekomunikasi dapat dibedakan berdasarkan :

a. Data (sinyal informasi) b. Bentuk sinyal yang dikirim melalui medium c. Medium yang digunakan d. Arah komunikasi


16 Berdasarkan Data (Sinyal Informasi), Komunikasi Analog, Yaitu dengan cara sinyal informasi atau data yang bersifat analog. Komunikasi Digital, yaitu dengan cara sinyal informasi (data) bersifat digital. Berdasarkan Sinyal yang dikirim, yaitu : Komunikasi Base Band, sinyal yang dikirim pada medium tanpa melalui proses modulasi (data dikirim secara langsung). Contoh : ethernet untuk LAN. Komunikasi Broad Band : Sinyal yang dikirim pada medium melalui proses modulasi. Berdasarkan Medium, yaitu : On-wire (menggunakan medium kawat tembaga). Contoh : telepon, Wireless (menggunakan medium udara), Contoh : radio, tv. Namun dengan adanya komunikasi optik, istilah di atas menjadi tidak tepat karena komunikasi optik menggunakan kabel bukan tembaga sehingga istilah diubah menjadi Guided media (kabel tembaga dan kabel optik) dan em Unguided media (udara). Berdasarkan arah komunikasi, yaitu : Simplex (satu arah) Radio broadcasct, TV broadcast. Dupplex (dua arah). Half Dupplex Komunikasi dua arah tetapi bergantian antara Transmitter dan Receiver, Contoh : Radio Komunikasi. Full Duplex. Komunikasi dua arah secara serempak antara Transmitter dan Receiver Contoh : telepon. 3.1.1 Jaringan Komputer Sebuah jaringan adalah sekumpulan peralatan-peralatan (sering juga disebut node) yang terhubung oleh hubungan media. Sebuah node dapat berupa sebuah komputer, printer, dan peralatan apapun lainnya yang mampu mengirimkan dan/atau menerima data yang dibangkitkan oleh node-node lainnya pada


17 suatu jaringan. Dengan demikian jaringan computer adalah sekumpulan computer otonom yang saling terhubung satu dengan yang lainnya menggunakan protocol komunikasi melalui media transmisi pada suatu jaringan komunikasi data (Fauzi dan Suherman, 2006). Jaringan komputer digunakan untuk beberapa tujuan. Bagi perusahaan atau organisasi, jaringan komputer dapat digunakan untuk beberapa tujuan untuk:

1. Berbagi pakai sumber daya (resource sharing). Dengan resource sharing, program, peralatan, atau data dapat digunakan oleh setiap orang yang ada di dalam jaringan, sekalipun jaraknya jauh. 2. Mendapatkan keandalan tinggi (high reliability) dengan memiliki sumbersumber alternatif yang tersedia. Misalnya, semua file dapat disalin ke dua atau tiga komputer, sehingga bila salah satu komputer tidak dapat dipakai, maka salinan yang ada pada komputer lainnya dapat digunakan. Selain itu, antar komputer dapat saling mendukung kerja sehingga dapat mencapai kinerja maksimal. 3. Penghematan uang (saving money). Dengan adanya jaringan komputer, setiap komputer dapat saling mendukung sistem sehingga penggunaan komputer mainframe yang harganya jauh lebih mahal jika dibandingkan dengan kecepatannya dapat dihindarkan. 4. Skalabilitas, yaitu kemampuan untuk meningkatkan kinerja sistem secara berangsur-angsur sesuai dengan beban pekerjaan dengan hanya menambahkan sejumlah prosesor.


18 Bagi masyarakat umum, jaringan komputer dapat menjadi daya tarik seperti:

1. Akses informasi yang berada di tempat yang jauh 2. Komunikasi orang ke orang 3. Hiburan interaktif.

3.1.2 Tipe Jaringan Komputer Secara umum, jaringan komputer dibagi menjadi tiga kategori utama: local area network (LAN), metropolitan area network (MAN), dan wide area network (WAN). Alasan pembagian menjadi tiga kategori utama ini adalah ukuran, kepemilikan, cakupan wilayah, dan arsitektur fisik (Fauzi dan Suherman, 2006). A. Local Area Network (LAN) Sebuah LAN biasanya dimiliki secara pribadi dan merupakan hubungan antar peralatan di dalam sebuah kantor, gedung, atau kampus. LAN dapat hanya berupa hubungan antara dua komputer dan sebuah printer dalam sebuah kantor rumahan (home office) hingga hubungan banyak komputer dan peralatanperalatan lainnya dalam jarak beberapa kilometer. LAN dapat dibedakan dari tiga jenis jaringan lainnya berdasarkan tiga karakteristik :

1. Ukuran 2. Teknologi transmisi 3. Topologi


19

Gambar 3.2 Local Area Network (LAN) B. Metropolitan Area Network (MAN) IEEE mendefinisikan sebuah Metropolitan Area Network (MAN) sebagai sebuah jaringan untuk menghubungkan sekumpulan stasiun-stasiun individual dan jaringan jaringan (sebagai contoh, local area networks (LANs)) yang terletak pada area perkotaan yang sama. Sebuah MAN dirancang untuk memperluas cakupan hingga keseluruhan kota . MAN dapat berupa sebuah jaringan tunggal seperti sebuah jaringan televisi kabel atau dapat berupa sejumlah LAN yang terhubung menjadi satu. Contohnya, sebuah perusahaan dapat menggunakan sebuah MAN untuk menghubungkan antar LAN di seluruh kantor-kantomya dalam sebuah kota seperti yang ditunjukkan pada Gambar 3.


20

Gambar 3.3 Metropolitan Area Network (MAN)

C. Wide Area Network (WAN) Sebuah WAN menyediakan transmisi data, suara, gambar, dan video dalam jarakjauh atas area-area geografis yang luas yang dapat berupa sebuah Negara, benua, atau bahkan seluruh dunia seperti yang ditunjukkan pada Gambar 4.

Gambar 3.4 Wide Area Network (WAN)

3.1.3 Topologi Jaringan Komputer Topologi adalah istilah yang digunakan untuk menguraikan cara bagaimana komputer terhubung dalam suatu jaringan. Topologi umumnya terdiri dari topologi bus, cincin (ring), dan bintang (star) (Fauzi dan Suherman, 2006).


21 A. Topologi Bus Pada topologi bus semua stasiun terhubung ke jalur komunikasi seperti yang diperlihatkan pada Gambar 5. Informasi yang dikirim akan melewati stasiun pada jalur tersebut. Jika alamat data atau informasi yang dikirim sesuai dengan alamat stasiun yang dilewati, maka data atau informasi tersebut akan diterima dan diproses. Jika alamat tersebut tidak sesuai, maka informasi tersebut akan diabaikan oleh stasiun yang dilewati. Topologi ini sangat cocok untuk pembangunan jaringan skala kecil. Jumlah stasiun dapat dikurangi dan ditambah secara fleksibel.

Gambar 3.5 Topology Bus

B. Topologi Bintang (Star) Pada topologi bintang, stasiun-stasiun terhubung pada sebuah stasiun pusat (berupa hub, bridge, atau switch), seperti yang diperlihatkan pada Gambar 6. Stasiun pusat merupakan titik kritis yang berfungsi sebagai pengatur semua komunikasi data yang terjadi dan menyediakan jalur komunikasi khusus antara dua stasiun yang akan berkomunikasi. Oleh karena itu, perlu adanya perhatian dan pemeliharaan terhadap hub, bridge, atau switch tersebut. Banyaknya stasiun yang


22 dapat terhubung tergantung pada jumlah port yang tersedia pada stasiun pusat yang digunakan. Topologi ini mudah untuk dikembangkan, baik penambahan maupun pengurangan stasiun.

Gambar 3.6 Topology Bintang (Star)

C. Topologi Cincin (Ring) Jaringan komputer lokal dengan topologi cincin mirip dengan topologi bus, karena sama-sama menggunakan sebuah link fisik tunggal. Pada topologi cincin, kedua stasiun yang berada di ujung saling dihubungkan sehingga menyerupai lingkaran seperti terlihat pada Gambar 7. Setiap informasi yang diperoleh dari jaringan diperiksa alamatnya oleh stasiun yang dilewatinya. Jika bukan untuk stasiun tersebut, maka informasi dilewatkan sampai menemukan alamat yang benar. Setiap stasiun dalam jaringan lokal yang terhubung dengan topologi cincin saling tergantung sehingga jika terjadi kerusakan pada satu stasiun maka seluruh jaringan akan terganggu.


23

Gambar 3.7 Topology Cincin (Ring)

3.1.4 Analisis Pemilihan Topologi Ada beberapa faktor yang dipertimbangkan dalam memilih topologi jaringan, yaitu : biaya, kecepatan, lingkungan, ukuran, dan konektivitas. Selain faktorfaktor di atas, perlu diperhatikan keuntungan dan kerugian dari masing-masing jenis topologi yang ada, seperti yang dijelaskan pada Tabel 1 (Fauzi dan Suherman, 2006).


24

Tabel 3.1 Keuntungan dan Kerugian Jenis Topology Topologi BUS

Keuntungan 1. Hemat Kabel 2. Layout kabel sederhana 3. Mudah dikembangkan 4. Tidak Membutuhkan kendali pusat 5. penambahan atau pengurangan stasiun dapat

CINCIN

BINTANG

dilakukan tanpa mengganggu 1. Hemat Kabel 2. Penataan kabel sederhana 3. Dapat melayani lalu lintas yang padat

1. Paling fleksibel karena pemasangan kabel mudah. 2. Penambahan atau


Kerugian 1. Deteksi dan isolasi keselahan terbatas 2. Kepadatan lalu lintas transmisi data tinggi akan mengurangi kinerja jaringan 3. Keamanan data kurang terjamin jika terjadi tabrakan. 4. Kecepatan data akan menurun jika pemakai bertambah banyak

1. Peka terhadap kesalahan 2. Pengembangan jaringan lebih kaku 3. Kerusakan pada media pengirim atau media stasiun dapat melumpuhkan kerja seluruh jaringan 4. Kinerja lambat karena pengiriman menunggu giliran token 1. Membutuhkan banyak tabel 2. Perlu penanganan khusus untuk bundel kabel.

25 Lanjutan Tabel 3.1 pengurangan stasiun tidak

3. Hub merupakan elemn kritis.

menggangu bagian lain 3. Kontrol terpusat akan memudahkan deteksi dan isolasi kesalah 4. Hub juga berfungsi sebagai multiplexer. 5. Memudahkan pengelolaan jaringan

3.2 Program Linier Problema program linier melibatkan optimisasi dari fungsi objektif linier, dengan subjeknya adalah persamaan linier dan kendala merupakan pertidaksamaan. Program linier mencoba mendapatkan keluaran terbaik (contoh : memaksimumkan laba, mengurangi biaya, dan lain-lain) dengan memberikan beberapa daftar kendala (contoh : hanya bekerja 30 jam/minggu, tidak melakukan hal yang illegal, dan lain-lain), menggunakan model matematika linier. Contoh lainnya ada pada polytope (contoh : polygon dan polyhedral) dan nilai riil fungsi affine f (x1 , x2, ..., xn) = a1x1 + a2x2 + a3x3 + b

didefinisikan pada polytope, tujuannya adalah menemukan titik pada polytope dimana fungsinya mempunyai nilai terkecil atau terbesar. Titik mungkin tidak ada, tapi jika dicari sepanjang vertex polytope maka digaransi menemukan


26 paling sedikit satu darinya. Program linier adalah problema yang dapat diekspresikan dalam bentuk kanonik : max imize cT x subject to Ax ≤ b where

x≥0

x direpresentasikan vektor variabel, c dan b adalah koefisien vektor dan A adalah koefisien matriks. Ekspresi untuk memaksimumkan atau meminimumkan disebut fungsi objektif (cT x). Persamaan Ax ≤ b adalah fungsi kendala yang khususnya polyhedral konvex yang fungsi objektifnya dioptimisasi. Program linier dapat diaplikasikan utnuk bermacam-macam field. Lebih diperluas, program linier digunakan dalam situasi bisnis dan ekonomi, tetapi dapat juga dimanfaatkan untuk beberapa masalah teknik. Beberapa industri menggunakan model program linier dalam transportasi, energi, telekomunikasi dan manufaktur. Dan dibuktikan juga pada problema dalam perencanaan, rute, jadwal, tugas dan desain. Problema dari sistem penyelesaian persamaan linier muncul setelah eliminasi Fourier-Motzkin. Program linier muncul sebagai model matematika yang dibangun selama Perang dunia Ke-II untuk merencanakan pengeluaran dan pendapatan dalam mengurangi biaya untuk tentara dan meningkatkan kerugian dari musuh. Ini tetap menjadi rahasia sampai tahun 1947. setelah perang berakhir banyak industri menemukan dan menggunkannya dalam perencanaan mereka. Penemu dari program linier adalah George B. Dantzig yang memperkenalkan metode simplex tahun 1947, John Von Neumann yang membangun teori dualitas


27 dan Leonid Kantorovich, matematika Rusia yang menggunakan teknik yang sama pada bidang ekonomi sebelum Dantzig dan memenangkan penghargaan Nobel tahun 1975 dalam bidang ekonomi. Contoh Dantzig dalam menemukan tugas terbaik dari 70 orang pada 70 pekerjaan menunjukkan kegunaan dari program linier. Kekuatan perhitung mengharuskan pengujian semua permutasi untuk memilih tugas yang terbaik; jumlah konfigurasi yang mungkin melebihi jumlah partikel diseluruh bidang; kemudian menemukan solusi optimum dengan mengajukan problem ini dan pengaplikasian algoritma simplex.


28 Program linier merupakan salah satu teknik operasi riset yang digunakan paling luas dan diketahui dengan baik. Problema khusus dari program seperti aliran jaringan (network flow) dan aliran multicomodity dianggap cukup penting untuk dibangun dan diteliti algoritma yang khusus untuk solusinya. Terdapat sejumlah algoritma untuk problema optimisasi dalam penyelesaian program linier diantaranya adalah dualitas, dekomposisi, convexity dan generalisasinya. Demikian juga program linier ini juga sangat sering digunakan dalam microekonomi dan manajemen bisnis, yaitu memaksimumkan pendapatan atau meminimumkan biaya dari produksi. Contoh lainnya pada manajemen persediaan, portfolio, manajemen keuangan, sumberdaya manusia, dan merencanakan iklan perusahaan. 3.2.1 Dualitas Setiap program linier disukai sebagai problema primial, dapat dikonversi ke dalam problema dual yang menyediakan batas atas nilai optimal dari problema primal. Dalam bentuk matriks dapat diekspresikan sebagai berikut: maximize cT x subject to Ax ≤ b, x ≥ 0 problema dual yang tepat adalah : minimize bT x subject to AT y ≥ c, y ≥ 0 dimana y digunakan sebagai pengganti variabel vektor. Terdapat dua ide mendasar untuk teori dualitas. Salah satunya adalah dual dari program linier dual semula adalah program linier primal. Penambahannya adalah setiap solusi yang layak untuk program linier memberikan batas pada nilai


29 optimal dari fungsi objektif dualitas. Kelemahan teorema dualitas bahwa nilai fungsi objektif dari dual pada solusi yang layak lebih baik atau sama dengan nilai fungsi objektif dari primal untuk solusi yang layak. Teorema dualitas yang kuat pada saat primal mempunyai solusi optimal x∗ maka dual juga mempunyai solusi optimal y ∗ sehingga cT x∗ = bT y ∗. Program linier dapat juga tidak terbatas dan tidak layak. Teori dualitas mengatakan bahwa jika primal tidak terbatas maka dual tidak layak. Demikian juga jika dual tidak terbatas maka primal harus tidak layak. Atau mungkin juga untuk keduanya dual dan primal tidak layak. 3.2.2

Metode Simplex Karena kesulitan menggambarkan grafik berdimensi banyak maka penyele-

saian masalah program linier yang melibatkan lebih dari dua variabel menjadi tidak praktis atau tidak mungkin. Dalam keadaan ini kebutuhan metode solusi yang lebih umum menjadi nyata. Metode umum ini dikenal dengan nama Algoritma Simplex yang dirancang untuk menyelesaikan seluruh masalah program linier, baik yang melibatkan dua variabel maupun lebih dua variabel. Penyelesaian masalah program linier menggunakan metode simplex ini melalui perhitungan ulang (iteration) dimana langkah langkah perhitungan yang sama diulang berkali-kali sebelum solusi optimum dicapai. Dalam penyelesaian masalah program linier dengan grafik, telah dinyatakan bahwa solusi optimum selalu terletak pada titik pojok ruang solusi. Metode simplex didasarkan pada gagasan ini, dengan langkah-langkah sebagai berikut:


30 1. Dimulai pada suatu titik pojok yang layak, biasanya titik asal (yang disebut sebagai solusi awal). 2. Bergerak dari suatu titik pojok layak ke titik pojok yang lain yang berdekatan, pergerakan ini akan menghasilkan nilai fungsi tujuan yang lebih baik (meningkat untuk masalah maksimasi dan menurun untuk masalah minimasi). Jika solusi yang lebih baik telah diperoleh, prosedur simplex dengan sendirinya akan menghilangkan semua solusi-solusi lain yang kurang baik. 3. Proses ini dilakukan berulang-ulang sampai suatu solusi yang lebih baik tak dapat ditemukan. Proses simplex kemudian berhenti dan solusi optimum diperoleh. Mengubah bentuk baku model program linier ke dalam bentuk tabel akan memudahkan proses perhitungan simplex. Langkah-langkah perhitungan dalam algoritma simplex adalah 1. Berdasar pada bentuk baku, tentukan solusi awal, dengan menetapkan (n − m) variabel nonbasis sama dengan nol. Dimana n jumlah variabel dan m banyaknya kendala. 2. Pilih sebuah entering variabel diantara yang sedang menjadi variabel nonbasis, yang jika dinaikkan di atas nol dapat memperbaiki nilai fungsi tujuan. Jika tak ada, berhenti berarti solusi sudah optimal. Jika tidak dilanjutkan ke langkah 1. 3. Pilih sebuah leaving variabel diantara yang sedang menjadi variabel basis yang harus menjadi nonbasis (nilainya menjadi nol) ketika entering variabel menjadi variabel basis.


31 4. Tentukan solusi yang baru dengan membuat entering variabel dan leaving variabel menjadi nonbasis. Kembali ke langkah 2

3.3 Program Integer Jika variabel tak diketahui diharuskan integer maka problema ini disebut program integer atau program linier integer. Perbedaan dengan program linier adalah dapat diselesaikan lebih efesien pada kasus yang buruk. Problema program integer banyak terjadi pada situasi praktis (dengan variabel terbatas) NP hard . 0 − 1 program integer adalah kasus yang khusus dari program integer dimana variabel diharuskan 0 atau 1. Masalah ini juga diklasifikasikan sebagai masalah yang sulit non polynomial. Jika hanya beberapa variabel tak diketahui diharuskan integer maka problema ini disebut program integer campuran. Hal ini juga merupakan masalah sulit non polynomial. Bagaimanapun terdapat beberapa subklas dari program integer dan program integer campuran bahwa dapat diselesaikan dengan efesien, khususnya masalah di mana matriks kendalanya unimodular dan sisi sebelah kanan dari kendala adalah integer. Program Integer adalah bentuk dari program linier dimana asumsi divisibilitasnya melemah atau hilang sama sekali. Bentuk ini muncul karena dalam kenyataaannya tidak semua variabel keputusan dapat berupa bilangan pecahan. Asumsi divisibilitas melemah artinya sebagian dari nilai variabel keputusan harus berupa bilangan bulat (integer) dan sebagian lainnya boleh berupa bilangan pecahan. Persoalan program integer dimana hanya sebagian dari variabel keputusannya yang harus integer disebut sebagai persoalan Mixed Integer Programming.


32 Tetapi jika seluruh variabel keputusan dari suatu persoalan program linier harus berharga integer, maka persoalan tersebut disebut sebagai persoalan Pure Integer Programming. Dalam hal ini asumsi divisibilitas dari program linier hilang sama sekali. Contoh

Maksimumkanz = 8x1 + 5x2 Kendalax1 + x2 ≤ 6 9x1 + 5x2 ≤ 45 x1, x2 ≥ 0, x2 integer Tampaknya cukup untuk mendapatkan solusi integer dari masalah program linier dengan menggunakan metode simpleks biasa dan kemudian membulatkan nilai-nilai pecahan solusi optimum. Hal ini bukan tugas mudah untuk membulatkan nilai-nilai pecahan variabel basis yang menjamin tetap memenuhi semua kendala dan tidak menyimpang cukup jauh dari solusi bulat yang tepat. Karena itu perlu prosedur yang sistematis untuk mendapatkan solusi bulat optimum terhadap masalah itu. Ada bebebrapa pendekatan solusi terhadap masalah program integer yaitu salah satu diantaranya adalah pendekatan dengan cutting plane. Dalam program linier, metode simpleks didasari oleh pengenalan bahwa pemecahan optimum terjadi di titik ekstrim dari ruang solusi. Hasil yang penting ini pada intinya mengurangi usaha pencarian pemecahan optimum dari sejumlah pemecahan yang tidak terbatas menjadi sejumlah yang terbatas. Sebaliknya Program Linier Integer memulai dengan sejumlah titik pemecahan yang terbatas. Tetapi sifat variabel yang berbentuk bilangan bulat mempersulit perancangan sebuah algorimta yang efektif untuk mencari secara langsung di antara titik integer


33 yang layak dari ruang penyelesaian. Terdapat dua metode untuk menghasilkan batasan-batasan khusus yang akan memaksa pemecahan optimum dari masalah program linier yang dilonggarkan untuk bergerak kearah pemecahan integer yang diinginkan yaitu metode Bidang Pemotong (Gomory Cutting Plane) dan metode Branch and Bound. Algoritma lanjutan untuk menyelesaikan program linier integer adalah :

a. Metode Cutting Plane b. Metode Branch and Bound c. Metode Branch and Cut d. Metode Branch and Price

Metode Gomory (Cutting Plane Algorithm) Suatu prosedur sistematik untuk memperoleh solusi integer optimum terhadap program integer murni pertama kali dikemukakan oleh R. E. Gomory pada tahun 1958. kemudian prosedur ini diperluas untuk menangani kasus yang lebih sulit yaitu, mixed integer programming. Langkah-langkah prosedur Gomory yang dilakukan sebagai berikut :

1. Selesaikan masalah program integer dengan menggunakan metode simpleks. Jika masalahnya sederhana, dapat diselesaikan dengan pendekatan grafik, sehingga pendekatan kurang efisien. 2. Periksa solusi optimum yang telah diperoleh. Jika variabel keputusan yang diharapkan telah memenuhi persyaratan integer, penyelesaian optimum mixed


34 integer telah diperoleh dan proses penyelesaian berhenti. Jika tidak demikian maka diteruskan ke tahap 3. 3. Buatlah suatu kendala Gomory (suatu bidang pemotong atau cutting plane) dan cari solusi optimum melalui metode dual simpleks. Selanjutnya kembali ke tahap 2.

Pembentukan kendala Gomory adalah begitu penting sehingga memerlukan perhatian khusus. Misalkan tabel optimum masalah program linier yang disajikan berikut merupakan solusi optimum kontinu. Secara histories, metode bidang pemotong adalah metode pertama kali yang diperkenalkan dalam literature OR. Oleh karena itu, maka yang disajikan dalam tulisan ini adalah bagaimana menemukan penyelesaian optimal yang integer dengan menggunakan algoritma bidang pemotong. Gagasan dari algoritma bidang pemotong adalah mengubah himpunan cembung dari bidang pemecahan sehingga titik ekstrem yang sesuai menjadi semuanya integer. Perubahan seperti ini dalam batas ruang pemecahan masih tetap menghasilkan sebuah himpunan cembung. Juga perubahan ini harus dilakukan tanpa mengiris setiap pemecahan integer yang layak dari masalah semula. Pendekatan Branch And Bound Branch and Bound untuk memecahkan pemrograman liniar bilangan bulat (PLBB) telah dikembangkan melalui Land et al (1960). Metode, yang secara langsung dihubungkan dengan simpleks metode untuk pemrograman linier (PL), kemudian dimodifikasi oleh Dakin (1965) dan telah dengan sukses menerapkan di dalam kitab undang-undang hukum dagang banyak orang untuk memecahkan


35 permasalahan PLBB. Prinsip metode itu sendiri sungguh sederhana, tetapi meskipun demikian alat yang sangat bermanfaat untuk memecahkan permasalahan terpisah. Ketika dipertimbangkan dalam konteks lebih luas, secara teoritis, Branch and Bound mungkin digunakan untuk memecahkan masalah optimisasi manapun. Efisiensi algoritma jenis ini sebagian besar tergantung pada detil itu, terutama pada kalkulasi Bound bagian atas dan yang lebih rendah, pada separasi menetapkan dan, akhirnya, pada aturan pilihan yang berbeda menggunakan untuk menentukan solusi yang berikutnya mulai dipertimbangkan dan variabel yang berikutnya ke Branch terpasang. Gagasan yang umum digunakan untuk metode untuk PLBB dapat diuraikan sebagai berikut. Pertimbangkan suatu masalah PLBB. max F (x) = cT x

(3.1)

Ax = b

(3.2)

l≤x≤u

(3.3)

berlaku hanya jika :

xj integer, J ∈ J 0 ⊂ J

Dimana A adalah matrik m×n, cT adalah transpos dari c dan c adalah vektor n × l, dan J = (1, 2, . . . , n). Proses dari metode awal dengan menyelesaikan (3.1) - (3.3) program linier secara kontinu, abaikan syarat-syarat integral. Andaikan solusi xj , j ∈ J 0 , tidak semua integer. xj = [xj ] + fj , 0 ≤ fj ≤ 1


(3.4)

36 untuk beberapa j ∈ J 0

dimana [xj ] adalah komponen integer dari [xj ], solusi kontinu untuk program linier, dan fj adalah komponen bagian yang kecil. Gagasan untuk menghasilkan dua subproblem masing-masing dengan penambahan pembuktian lj ≤ xj ≤ [xj ]

(3.5)

[xj ] + 1 ≤ xj ≤ uj

(3.6)

dan

Karena variabel tertentu j ∈ J. Proses menyelesaikan masalah disebut Branching. Masing-Masing ini subproblema dipecahkan lagi sebagai PL kontinu. Proses dari Branching dan pemecahan suatu sequance dari permasalahan kontinu untuk variabel yang berbeda j ∈ J 0 dan bilangan bulat yang berbeda bxj c. Secepatnya, disediakan daftar alternatif subproblema untuk diselidiki, dengan PL yang kontinu yang pertama dimasukkan. Struktur metode yang logis sering diwakili sebagai pohon. Masing-Masing tangkai pohon menghadirkan suatu subproblem. Ketika subproblema manapun, atau tangkai pohon, diselidiki subproblema manapun yang dihasilkan dihubungkan kepada tangkai pohon dengan Branch. Jika salah satu dari tiga ukuran-ukuran di bawah ini dicukupi, Branch dari tiap tangkai pohon akan berakhir.


37 1. Subproblema tidak mempunyai solusi fisibel 2. Solusi subproblema tidak ada lebih baik daripada integer-fisibel solusi terbaik yang dikenal sekarang. 3. Solusi adalah integer-fisibel, i.e., xj , j ∈ J 0 mempunyai nilai-nilai bilangan bulat (menyediakan suatu integer-fisibel, solusi ada). Itu adalah jelas, bahwa efektivitas dari prosedur seperti itu adalah sangat dependen. 4. Variabel yang mana harus bercabang, dan 5. Subproblema yang mana harus diselidiki berikutnya.

Sebab perhatian sebagian besar pada atas permasalahan PINL, itu bermanfaat untuk melihat bagaimana di atas pendekatan mungkin sesuai dikerjakan seperti permasalahan itu. Secara teoritis, pendekatan Branch dan Bound tidak mempunyai berbagai kesulitan untuk memecahkan permasalahan PINL. Khususnya, akan mudah untuk mengamati bahwa batas (3.5) dan (3.6) menjauhi linieritas. Pendekatan yang umum ditujukan di atas untuk PLBB dapat secara langsung diperluas kepada kasus nonlinier, kecuali prosedur untuk memecahkan subprolem dan masing-masing tangkai pohon. Itu dipahami bahwa permasalahan yang kontinu pada tangkai pohon masing-masing adalah nonlinier yang memprogram permasalahan (PNL), yang dihasilkan dengan kebutuhan integralisasi suatu masalah PINL. Berbagai kesulitan boleh muncul dalam posisi ini, ketika memecahkan suatu masalah PNL tidaklah sangat mudah untuk memecahkan PL, terutama sekali, dalam menemukan solusi optimal yang global. Oleh karena


38 itu menghitung kelayakan dari pendekatan ini akan tergantung pada bagaimana dipecahkan masalah PNL itu, dengan batasan Bound tambahan (3.5) atau (3.6) pada tangkai pohon masing-masing. Bagaimanapun, metode Branch dan Bound mempunyai fleksibilitas untuk berhubungan dengan suatu variasi yang besar masalah nonlinier, metode yang ada disediakan untuk memecahkan kontinu nonlinier subproblem yang efesien. Oleh karena itu tidaklah mengejutkan bahwa banyak peneliti sudah menggunakan pendekatan ini untuk memecahkan beberapa permasalahan PINL. Seperti ditunjukkan di atas suatu pemilihan yang baik variabel Branch, seperti halnya, subproblem untuk diselidiki berikutnya, akan mempunyai efek penting pada keseluruhan capaian suatu strategi Branch dan Bound. Gupta et al (1985) sudah menyelidiki strategi yang berikut untuk pemilihan variabel Branch.

1. Pilih variabel bilangan bulat dengan index paling rendah. 2. Pilih kebanyakan variabel bilangan bulat pecahan 3. Penggunaan Pseudo-Cost Konsep Benichou. et al. ( 1971). Konsep ini adalah untuk mengukur rata-rata dari yang diamati ternyata berubah di (dalam) nilai fungsi objektif dalam kaitannya dengan memaksa suatu noninteger bagi suatu nilai bilangan bulat. Pilih pseudo-cost yang paling besar.

Mereka sudah menggunakan yang berikut ini untuk pemilihan dari Branch tangkai pohon:

1. Branch dari tangkai pohon dengan yang terikat paling rendah. 2. Branch dari tangkai pohon yang paling baru.


39 3. Menggunakan estimasi - estimasi.

Dalam kaitan dengan waktu perhitungan, mereka menyimpulkan bahwa strategi menggunakan variabel bilangan bulat yang paling kecil adalah yang terbaik diantara tiga pilihan untuk memilih variabel yang berBranch itu. Dan Branch dari tangkai pohon yang paling baru adalah yang strategi terburuk untuk memilih tangkai pohon untuk diselidiki berikutnya. Korner, F. ( 1983) telah mengusulkan aturan Branch lain untuk bilangan bulat yang tidak dibatasi masalah optimisasi kuadrat, yaitu, ke variabel Branch xj yang pertama jika (Q−1 )jj ∈ (Q−1 )ii untuk semua i. Di mana Q adalah matriks simetrik yang positif dan fungsi objektif yang terbatas . Karena secara linier membatasi masalah, Berrada, M. et al (1986) menggunakan Branch dan Bound untuk memecahkan mesin yang memuat masalah dalam fleksibel sistem produksi.


BAB 4 MODEL TELEKOMUNIKASI DAN LOKASI

4.1 Masalah Fasilitas Lokasi yang Uncapacitated (MFLU) Chung et al. (1992) membangun model untuk desain tipe jaringan penuh atau jaringan bintang, contohnya semua konsentrator dihubungkan untuk tiap terminal yang ditugaskan ke konsentrator secara langsung dihubungkan pada konsentrator ini. Kemudian diformulasi dimana fungsi biaya termasuk ke dalam biaya konsentrator yang diinstal. Sehingga model sama dengan MFLU kecuali fungsi P P biaya juga termasuk dalam bentuk j∈J l∈J Bjl yj yl dimana Bji adalah biaya penghubung konsentrator j dan l. Sehingga total fungsi biaya merupakan kuadratik. Pada bagian ini, formulasinya dilinearisasi dan prosedur solusi berdasarkan dual serta hasil perhitungan juga diberikan. Mateus et al. (1994) mendesain jaringan pohon. Kemudian membentuk desain problem dalam tiga tahap yang terpisah. Tahap lokasi terdiri dari MFLU diP mana jumlah konsentrator yang diinstal dibatasi, sebagai contoh: kendala j∈M yj ≤ k ditambahkan ke MFLU. Konsentrator dilokasikan dan terminal ditugaskan ke konsentrator. Tiap terminal i terhadap permintaan ti . Sehingga tujuan utamanya untuk membangun akses jaringan topology dan dimensinya. Untuk tiap konsentrator dan himpunan terminal ditugaskan, masalahnya adalah menemukan biaya jaringan pohon yang minimum dengan konsentrator sebagai akar. Kapasitas kendala yang diinstal pada tiap link sebaiknya sesuai permintaan. Andaikan G = (N, A) adalah subgraph untuk konsentrator p. Andaikan T P merupakan


41 himpunan terminal yang ditugaskan ke p. Formulasinya sebagai berikut: min

X

Vij fij +

(i,j)∈A

X

Bij zij

(4.1)

(i,j)∈A

kendala X

min

Vij fij +

(i,j)∈A

X

fji −

(j,i)∈A

X

X

Bij zij

(4.2)

(i,j)∈A

X

fij = ti

∀i ∈ T p

(4.3)

fij = 0

∀i ∈ N\(T p ∪ {p})

(4.4)

(i,j)∈A

fji −

(j,i)∈A

X (i,j)∈A

¯ ij fij ≤ Mz fij ≥ 0 zij ∈ {0, 1}

∀(i, j) ∈ A ∀(i, j) ∈ A ∀(i, j) ∈ A

(4.5) (4.6) (4.7)

(4.2) dimana fij adalah aliran pada arc (i, j).    1, jika arc (i, j)digunakan zij   0, lainnya ¯ adalah konstanta yang cukup besar. Untuk tiap arc (i, j), dengan dan M variabel biaya Vij dan biaya tetap Bij . Kendala formulasi (4.2), (4.3) dan (4.4) merupakan aliran kendala yang konservatif. Kendala (4.5) menyatakan bahwa terdapat aliran pada arc (i, j) hanya jika arc ini digunakan dalam jaringan. Untuk menyelesaikan model ini secara langsung dengan mengurangi graph ke perkiraan graph G0 = (N 0 , A0) dimana N 0 = T P ∪{p}. Graph G0 merupakan graph


42 lengkap dimana tiap panjang arc sesuai dengan jarak path terpendek antara kepala dan ekornya. Kemudian model diselesaikan dengan mereduksi graph. Aliran kendala konservatif menjadi sebagai berikut: X

X

fpi =

X

ti

i∈T p

(p,i)∈A0

X

fji −

(j,i)∈A0

fij = ti

∀i ∈ T p

(i,j)∈A

dengan kendala sebagai berikut: X

zji = 1

∀i ∈ T p

j∈N 0 \{i}

yang menyatakan jumlah arc yang masuk tiap node adalah 1. Kemudian dipresentasikan tipe heuristik dan arc substitusi heuristik untuk menyelesaikan model tersebut. Selanjutnya dikonversikan solusi pada graph reduksi untuk solusi graph asli. Tahap ketiga, problema meliputi desain jaringan backbone yang dimodelkan dan diselesaikan dengan cara yang sama pada tahap kedua. Pirkul et al (1992) mendesain jaringan bintang menggunakan algoritma dua tahap. Pada tahap pertama, menggunakan algoritma sweep untuk membagi kumpulan node dalam daerahnya. Pada tahap kedua, dibangun tiap daerah formulasi untuk menentukan path dari node daerah ke pusat node sehingga semua node pada path ini merupakan lokasi konsentrator dan terminal dalam daerah dihubungkan ke konsentrator via titik-titik link. Modelnya sebagai berikut: min

XX

Cij xij +

i∈N j∈M

Kendala


X j∈M,j6=s,t

Fj yj +

XX j∈M l∈M

Bjl zjl

(4.8)

43

X

xij = 1

∀i ∈ N

(4.9)

j∈M

xij ≤ yj X zsj = 1

∀i ∈ N, j ∈ M, j 6= s, t

(4.10) (4.11)

j∈M

X

zjt = 1

(4.12)

j∈M

X

zlj −

j∈M

X

zjl = 0

∀l ∈ M, l 6= s, t

(4.13)

j∈M

XX

zjl ≤ |Q| − 1

∀Q ⊆ M

(4.14)

∀j ∈ M, j 6= s, t

(4.15)

∀i ∈ N, j ∈ M

(4.16)

j∈Q l∈Q

yj =

X

zjl

l∈J

xij ∈ {0, 1} yj ∈ {0, 1}

∀j ∈ M

(4.17)

zjl ∈ {0, 1}

∀j, l ∈ M

(4.18)

dimana

zjl =

   1, jika node j dan l dihubungkan dengan link path backbone   0, untuk lainnya

N adalah kumpulan terminal dan M adalah kumpulan konsentrator dalam daerah. Biaya pembangunan link (j, l) adalah Bjl . Vektor z sesuai dengan kendala (4.11), (4.12), (4.13) dan (4.18) mendefinisikan sebuah path dari permulaan node s ke pusat node t. Node s dan t tidak merupakan lokasi untuk menerima konsentrator. Kendala (4.14) mengeliminasi subtour pada path ini. Kendala (4.15) menyatakan bahwa node pada path backbone jika dan hanya jika konsentrator


44 diinstal pada node ini. Model ini diselesaikan untuk tiap daerah secara terpisah. Fungsi biaya terdiri dari biaya konsentrator, biaya penugasan terminal ke konsentrator dan biaya instal link dari path backbone. Karena formulasi ini memiliki keduanya yaitu masalah path terpendek dan MFLU. Kemudian mengaplikasikan relaksasi lagrange untuk menggabungkan masalah dalam dua masalah. Selanjutnya diselesaikan masalah dual lagrange dengan optimisasi subgradien, lalu mengenarisasikan solusi yang layak dan merepresentasikan hasil perhitungan. Current et al (1991) menganggap masalah tertutup dimana konsentrtaor dihubungkan ke yang lain dengan path dari arc yang utama dan terminal dihubungkan ke konsentrator dengan path dari arc yang kedua. Tujuannya adalah untuk desain topology untuk meminimumkan biaya konsentrator dan biaya arc utama dan kedua yang digunakan untuk membangun link. Diasumsikan M = N . Modelnya sebagai berikut: min

XX

Cij xij +

i∈M j∈M

X

Fj yj +

j∈M

XX

Bjl zjl

(4.19)

j∈M l∈M

kendala X

xij + yj = 1

∀i ∈ M

(4.20)

j∈M

XX

xij ≤ |Q| − 1

∀Q ⊆ M

(4.21)

i∈Q j∈Q

yj ≤

X

zjl

∀j ∈ M

(4.22)

l∈M

(4.11) − (4.14) dan (4.16) − (4.18) vektor z mendefinisikan path utama dan kendala (4.20) dan (4.21) menjamin


45 bahwa node merupakan konsentrator yang dihubungkan kepada konsentrator dengan path dari arc kedua. Kendala (4.22) menyatakan bahwa tiap konsentrator sebaiknya berada pada path utama. Berbeda dari kendala (4.15), kendala ini mengijinkan terminal pada path kedua. Untuk menyelesaikan masalah ini, direpresentasikan dua heuristik berdasarkan relaksasi lagrange dan juga menyediakan hasil perhitungan. Lee et al. (1996) menganggap desain jaringan dengan jaringan akses adalah bintang dan konsentrator dihubungkan ke yang lainnya dengan meminimumkan spanning tree. Kemudian diformulasi untuk menentukan jaringan bintang/pohon yang meminimumkan biaya penginstalan konsentrator, biaya penugasan terminal ke konsentrator dan biaya pembangunan link spanning tree. Model ini sama dengan model yang diberikan Pirkul et al (1992) jika diganti kendala (4.11)-(4.13) yang menyatakan bahwa z mendefinisikan path yang melewati semua konsentrator dengan kendala: XX j∈M l∈M

zjl =

X

yj − 1

j∈M

yang mengimplikasikan bahwa z adalah vektor insiden dari spanning tree semua konsentrator. Dalam kenyataannya, model sekarang ini merupakan generalisasi dari yang lain. Kemudian mengaplikasikan relaksasi lagrange pada model ini untuk seluruh kendala kecuali pada satu pernyataan yaitu z mendefinisikan spanning tree sehingga menghasilkan masalah yaitu meminimumkan masalah spanning tree. Selanjutnya menyelesaikan dual lagrange dengan optimisasi subgradien, mempresentasikan heuristik untuk mengkonversikan solusi lagrange kepada solusi primal yang layak dan menyediakan hasil perhitungan.


46 Gavish (1992) memformulasikan masalah terhadap terminal yang dihubungkan ke konsentrator via link multidrop yang berkapasitas, dan konsentrator dihubungkan pada pusat unit dengan titik-titik link. Hasilnya dalam jaringan bintang/pohon. Fungsi objektif meliputi biaya pembangunan link dan penginstalan konsentrator. Terdapat tipe link yang berbeda dengan biaya dan kapasitas yang berbeda. Andaikan L menotasikan kumpulan jenis link yang berbeda. Berikut formulasinya: min

XXX

Cijl xijl +

i∈N j∈M l∈L

XX

(Fj + Cj1l )yjl

(4.23)

j∈M l∈L

kendala X X

xijl = 1

∀i ∈ N

(4.24)

j∈M ∪N l∈L

X

yjl ≤ 1

∀j ∈ M

(4.25)

l∈L

X

fij −

j∈M ∪N

X

fij ≤

i∈N

fij ≤

X

fji = ti

∀i ∈ N

(4.26)

∀j ∈ M

(4.27)

∀i ∈ N, j ∈ M ∪ N

(4.28)

∀i ∈ N, j ∈ M, l ∈ L

(4.29)

j∈N

X

Qj1l yjl

l∈L

X

Qijl xijl

l∈L

xijl ∈ {0, 1} yjl ∈ {0, 1} fij ≥ 0

∀j ∈ M, l ∈ L

(4.30)

∀i ∈ N, j ∈ M

(4.31)

dimana node 1 ∈ M merupakan pusat unit, Cijl adalah biaya penginstalan link dari tipe l antara node i dan j. Volume trafik dibangun dengan terminal i adalah ti . Maksimum trafik yang sesuai tipe l berada antara node yang dinotasikan


47 dengan Qijl . Variabelnya didefinisikan sebagai berikut:    1, jika terminal i dihubungkan ke konsentrator j dengan link tipe l xijl =   0, untuk lainnya    1, jika terminal j dihubungkan ke pusat unit dengan link tipe l yjl =   0, untuk lainnya dan fij merupakan aliran pada arc (i, j). Kendala (4.24) menyatakan tiap terminal sebaiknya dihubungkan ke konsentrator atau terminal lain menggunakan link tipe tunggal. Sama halnya, kendala (4.25) menyatakan tiap konsentrator dapat dihubungkan ke pusat unit menggunakan link tipe tunggal. Kendala (4.26) merupakan kendala aliran konversi. Kendala (4.27) menyatakan bahwa aliran dalam konsentrator sebaiknya tidak lebih besar daripada link yang menghubungkan konsentrator ini ke pusat unit dapat didukung. Kendala (4.28) adalah kendala kapasitas link antara terminal dan konsentrator dan untuk link antara terminal. Gavish (1992) mendiskusikan evolusi jaringan topology dan proses desain jaringan. Kemudian memformulasikan model untuk mendesain jaringan dengan jaringan topology. Andaikan P menyatakan kumpulan pasangan komunikasi. Untuk tiap pasangan komunikasi p dari node, selanjutnya mendefinisikan kumpulan route Rp yang dapat mendukung trafik antara node ini. Didefinisikan R = ∪p∈P Rp .Lr merupakan semua link dengan route r. Masalahnya adalah memilih route dan menginstal konsentrator dan link dari route untuk meminimalkan biaya total penginstalan konsentrator dan link, biaya transfer trafik dan biaya keterlambatan pesan, sehingga trafik antara pasangan komunikasi ini dapat mengalir. Ini diasumsikan bahwa pesan mempunya panjang berdistribusi eksponensial. Masa-


48 lah ini didefinisikan melebihi graph G = (M, A). Modelnya sebagai berikut: min

X

X

Fj yj +

j∈M

Cij zij +

(i,j)∈A

X

X

Tij fij (xr ) + D

(i,j)∈A

fij (xr )/(fij (xr ) − Qij )

(i,j)∈A

(4.32) kendala X

xr = 1

∀p ∈ P

(4.33)

r∈Rp

xr ≤ zij

∀(i, j) ∈ Lr , r ∈ R

(4.34)

zij ≤ yi

∀(i, j) ∈ A

(4.35)

zij ≤ yj

∀(i, j) ∈ A

(4.36)

xr ∈ {0, 1}

∀r ∈ R

(4.37)

yj ∈ {0, 1}

∀j ∈ M

(4.38)

zij ∈ {0, 1}

∀(i, j) ∈ A

(4.39)

(4.36) dimana

xr =

yj =

zij =

   1, jika route r yang dipilih

  0, untuk lainnya    1, jika konsentrator ditempatkan pada lokasi j   0, untuk lainnya    1, jika link (i, j) diinstal   0, untuk lainnya

dan fij (xr ) adalah traffic pada arc (i, j) yang merupakan fungsi linier dari xr dan fij (xr )/(fij (xr ) − Qij ) merupakan rata-rata keterlambatan pada arc (i, j) dengan Qij merupakan link kapasitas (i, j). Biaya per unit trafik pada arc (i, j) adalah Tij dan biaya per unit keterlambatan adalah D.


49 Kendala (4.33) menyatakan bahwa tiap pasangan komunikasi dari node, route sebaiknya dipilih. Kendala (4.34) menyatakan jika route r dipilih maka semua link pada route sebaiknya diinstal dan dengan kendala (4.35) dan (4.36) jika node merupakan kepala atau ekor dari link yang diinstal maka sebaiknya kendala tersebut menerima konsentrator. Oleh sebab itu, dipresentasikan relaksasi Lagrange berdasarkan prosedur solusi untuk menyelesaikan formulasi nonlinier ini. Sehingga merepresentasikan model Chardaire et al. (1999) untuk mendesain jaringan bintang dengan konsentrator tingkat kedua sebagai contoh tiap terminal dihubungkan pada konsentrator tingkat pertama yang juga dihubungkan pada konsentrator tingkat kedua. Semua konsentrator tingkat kedua dihubungkan pada pusat unit. Kemudian dipresentasikan formulasi dua program integer dan ditunjukkan bahwa relaksasi linier dari kedua formulasi untuk bound yang sama. Andaikan N merupakan himpunan terminal, M himpunan konsentrator tingkat pertama yang mungkin dan K merupakan himpunan konsentrator tingkat kedua yang mungkin. Berikut formulasi dari Chardaire et al. (1999): min

XX

Cij xij +

i∈N j∈M

XX

X

Bjk yjk +

j∈M k∈K

Fk zk

(4.40)

k∈K

kendala X

xij = 1

∀i ∈ N

(4.41)

j∈M

xij ≤

X

yjk ∀i ∈ N, ∀j ∈ M

(4.42)

∀j ∈ M, ∀k ∈ K

(4.43)

k∈K

yjk ≤ zk

(4.44)


50 X

yjk ≤ 1

∀j ∈ M

(4.45)

xij ∈ {0, 1}

∀i ∈ N, ∀j ∈ M

(4.46)

yjk ∈ {0, 1}

∀j ∈ M, ∀k ∈ K

(4.47)

zk ∈ {0, 1}

∀k ∈ K

(4.48)

k∈K

dimana Cij merupakan biaya dari terminal i ke konsentrator tingkat pertama j, Bjk merupakan jumlah biaya pengaturan konsentrator tingkat pertama pada lokasi j dan dihubungankan pada konsentrator tingkat pertama ke konsentrator tingkat kedua k dan Fk didefinisikan biaya penginstalan konsentrator tingkat kedua pada lokasi k. Variabelnya didefinisikan sebagai berikut:

yjk

   1, jika konsentrator tingkat pertama j dihubungkan ke    = konsentrator tingkat kedua      0, untuk lainnya

untuk semua j ∈ M dan k ∈ K    1, jika konsentrator tingkat kedua diinstal pada lokasi k zk =   0, untuk lainnya untuk semua k ∈ K

4.2 Sifat Polihedral MLKC dan Metode Solusi Exact Definisi dasar mengacu pada Nemhauser et al (1988) tentang kesahan dan segi definisi pertidaksamaan untuk MLKC. Jika kendala kesatuan (2.9) pada variabel xij diganti dengan kendala 0 ≤


51 xij ≤ 1,

∀i, j. Problema hasilnya adalah Masalah Fasilitas Lokasi Capacitat-

ed (MFLC). Perbedaannya adalah pada MFLC diijinkan untuk mensuply permintaan terminal lebih dari satu konsentrator. Sebagaimana MFLC merupakan relaksasi MLKC, pertidaksamaan yang sah untuk MFLC juga sah untuk MLKC. Lebih dari itu, pada kondisi yang sama, segi definisi pertidaksamaan untuk MFLC merupakan segi definisi MLKC. Aardal et al. (1995) mempelajari pertidaksamaan yang sah dan segi polytope diasosiasikan ke MFLC, sehingga definisi domain X yang layak adalah: X

vij = di

∀∈N

j∈M

vj =

X

vij

∀j ∈ M

X

vj = d(N )

i∈N

j∈M

vj ≤ Qj yj

∀j ∈ M

vij ≥ 0 ∀i ∈ N ∀j ∈ M 0 ≤ yj ≤ 1 ∀j ∈ M yj integer ∀j ∈ M P di . dimana vij merupakan aliran terminal i dan konsentrator j dan d(S) = i∈S P Qk − Andaikan polytope P X merupakan hull konvex X. Diasumsikan bahwa k∈M

Qj ≥ d(N ) untuk semua j ∈ M. Dimensi dari P X adalah mn + m − n, berikut hasil Aardal et al. (1995): Knapsack Facets : Andaikan J ⊂ M sehingga

P j∈J

Qj >

P

Qj −d(N ). Kumpu-

j∈M

lan J disebut permukaan yang mengacu kepada N dan M dan minimal permukaan P P Qj ≤ Qj − d(N ). Karena kapasitas konjika untuk semua S ⊂ J, sehingga j∈S


j∈M

52 sentrator dalam M/J tidak cocok untuk mensuply semua permintaan terminal, P yj ≥ 1 paling tidak satu konsentrator pada J yang telah diinstal. Sehingga j∈J

sah. Pada kenyataannya pada beberapa kondisi. Pertidaksamaan menyebabkan segi dari P X. Teorema 4.1 Jika J merupakan minimal permukaan yang mengacu pada M dan P P Qj +Qmin > d(N ), maka yj ≥ 1 mendefinisikan N , Qmin = minj∈J Qj dan j∈J

j∈M \J

segi dari conv(X ∪ {y ∈ {0, 1}m : yj = 1∀j ∈ M\j}). Permukaan pertidaksamaan Knapsack dapat digeneralisasikan dengan mengambil M 0 ⊂ M dan J 0 yang merupakan minimal permukaan yang mengacu pada N dan M 0 dan mengaplikasikan rangkaian daya angkat ke variabel yj = 0 pada M/M 0 dan yj = 1 pada M 0 /J 0 . Hasil pertidaksamaan yang mendefinisikan segi P X adalah dalam bentuk berikut: X

X

βj yj +

j∈M 0 \j 0

αj yj +

j∈M \M 0

X j∈J 0

yj ≥ 1 +

X

βj

j∈M 0 \j 0

P

Aliran Permukaan Pertidaksamaan : Subset J ⊂ M sehingga λ =

Qj −

j∈J

d(N ) > 0 disebut kumpulan aliran permukaan yang mengacu pada M dan N. Ini berarti nilai maksimumnya adalah jumlah aliran konsentrator pada kumpulan J dan mengambil d(N ). Jika ditutup salah satu konsentrator dalam kumpulan J katakan j, maka maksimum ini tidak akan berubah jika Qj ≤ λ dan akan menurun menjadi Qj − λ lainnya. Pengamatan ini menghasilkan teorema berikut: Teorema 4.2 Andaikan J merupakan aliran permukaan yang mengacu pada M P Qj > d(N ) + Qk untuk semua k ∈ J. Maka dan N sehingga max Qj > λ dan j∈J

j∈M

aliran permukaan pertidaksamaan adalah: X j∈J

vj +

X

(Qj − λ) + (1 − yj ≤ d(N )

j∈J


53 yang mendefinisikan segi P X. Efektivitas Kapasitas Pertidaksamaan: Andaikan J ⊆ M dan K ⊆ N . Untuk setiap j ∈ J memilih Kj ⊆ K. Definisikan Q¯j = min{Qj , d(Kj )}. J P merupakan aliran permukaan yang mengacu pada M dan K jika λ = Q¯j − j∈J

d(K) > 0. Teorema 4.3 Andaikan J ⊂ M merupakan aliran permukaan yang mengacu pada M dan K. Andaikan Q ⊂ J merupakan kumpulan konsentrator untuk Q¯j < Qj . P Diasumsikan k ∈ M Qk > Qj + d(N ) untuk semua j ∈ M . Pertidaksamaannya adalah: XX j∈J i∈Kj

vij +

X

(Q¯j − λ) + (1 − yj ) ≤ d(K)

j∈J

yang mendefinisikan segi P X jika dan hanya jika ∀j1 , j2 ∈ Q, Kj1 ∪ Kj2 = ∅ Kj = K

j ∈ J\Q

∪j∈QKj ⊂ K Q¯j > λ∀j ∈ Q |K| ≤ 1 ⇒ ∃j ∈ J\QwithQj > λ. Submodular Pertidaksamaan: Sebuah fungsi f pada N = {1, . . . , n} merupakan submodular jika f (A)+f (B) ≥ f(A∪B)+f (A∩B) untuk semua A, B ⊆ N. Definisikan φj (A) = f(A ∪ {j} − f(A) untuk j ∈ N\A sebagai fungsi naik. Andaikan K ⊆ N, j ⊆ M dan Kj ⊆ K untuk semua j ∈ J. Fungsinya adalah sebagai berikut: f (J ) = max

XX j∈J i∈Kj


vij

54 kendala X

vij ≤ Q¯j yj ∀j ∈ J

i∈Kj

X

vij ≤ di ∀i ∈ K

j∈J,i∈Kj

vij ≥ 0 ∀i ∈ K, j ∈ J yj = 1 ∀j ∈ J merupakan submodular pada M. Teorema 4.4 Andaikan K ⊆ N, j ⊆ M dan Kj ⊆ K untuk semua j ∈ J. Submodular pertidaksamaan adalah: XX

vij +

j∈J i∈Kj

X

φj (J \{j})(1 − yj ) ≤ f (J )

j∈J

sah untuk P X. Leung et al (1989) mempelajari kesahan pertidaksamaan dan segi MFLC dimana semua konsentrator mempunyai kapasitas yang sama. Berikut domain F yang layak: xij ≤ yj X

∀i ∈ N, j ∈ M xij ≤ 1 ∀i ∈ N

j∈M

X

di xij ≤ Qyj

∀j ∈ M

i∈N

xij ≥ 0 ∀i ∈ N, j ∈ M yj ≤ 1 ∀j ∈ M yj integer ∀j ∈ M


55 dan hull konvex P F dari F . Kemudian mendefinisikan family baru dari segi definisi pertidaksamaan disebut residual kapasitas pertidaksamaan sebagai berikut: XX

di xij r

i∈N j∈M

X

yj ≤ Dr dD/K e

(a)

j∈M

dimana N ⊂ N , M ⊂ M, D =

P

dan r = D( mod K) dengan r = K jika D

i∈N

merupakan banyaknya K. Kemudian r dapat diinterpretasikan sebagai residual permintaan yang sesuai dengan konsentrator terakhir ketika dD/K e 1 konsentrator mensuply permintaan dengan kapasitas yang penuh. Pertidaksamaan (a) adalah sah dan mendefinisikan segi P F ketika 1 ≤ r ≤ K − 1 dan |M| ≥ dD/K e. Leung G. et al (1989) juga menganggap hull konvex F dengan penambahan kendala bahwa xij merupakan variabel integer, sebagai contoh conv(F ∩ {xij ∈ {0, 1}∀i ∈ N, ∀j ∈ M}). Residual kapasitas pertidaksamaan juga sah untuk polihedron tetapi tidak dari segi definisi pada kasus yang umum. Dalam kasus ini, permintaan terminal adalah sama, diasumsikan bahwa tiap terminal mempunyai unit permintaan dan kapasitas dalam bentuk jumlah terminal yang ditugaskan. Kemudian pertidaksamaannya menjadi: XX i∈N j∈M

xij − r

X

yj ≤ |N| − r d|D|/K e

(b)

jinM

Teorema 4.5 Pertidaksamaan yang sah (b) merupakan segi definisi untuk MLKC ketika permintaan semua terminal sama. 4.3 Relaksasi Lagrange Berdasarkan Heuristik Empat relaksasi lagrange pada Masalah Lokasi Konsentrator Capacitated (MLKC) harus ditemukan. Pertama diperoleh dengan mendualkan kendala kapasitas (2.11). Andaikan v ≥ 0 dinotasikan sebagai vektor dari perkalian lagrange.


56 Untuk vektor v ≥ 0, direlaksasikan masalah sebagai berikut: LR(v) min

P P

(Cij + vj di )xij +

i∈N j∈M

P j∈J

Fj yj −

P

vj Qj

j∈M

kendala (2.7), (2.9), (2.10), (2.12) yang merupakan MFLU. Dual lagrangenya adalah: LD(v) = max LR(v) v≥0

Mirzaian (1985) memformulasikan masalah dimana semua konsentrator memiliki kapasitas yang sama dan tiap terminal menempatkan permintaan unit sehingP xij ≤ Qyj ∀j ∈ M. Pada formulasi ini, ga kapasitas kendala (2.8) menjadi i∈N

terminal diijinkan/ditugaskan langsung ke pusat unit. Kasus khusus ini, relaksasi lagrange diperoleh dengan mendualkan kendala kapasitas (2.8) pada MLKC yang memberikan batas yang sama sebagai masalah relaksasi program linier. Klincewicz et al (1986) membangun relaksasi lagrange berdasarkan heuristik untuk MLKC. Relakasi lagrange diaplikasikan dengan mendualkan kapasitas kendala dan menyelesaikan subproblem MFLU dengan dual naik dan dual algoritma penyesuaian dari Erlenkotter (1978) tanpa fase branch dan bound. Sebuah prosedur tambahan yang menambahkan fasilitas pada waktu yang digunakan untuk membangun solusi yang layak dan batas atas masalah. Kemudian relaksasi lagrange heuristi dimulai dengan variabel dual yang menuju ke 0, jika hasil MFLU memberikan solusi yang layak untuk masalah asli, maka prosedur selesai. Untuk lainnya jika variabel dual untuk melanggar kendala yang meningkat pada nilai minimum sehingga beberapa terminal ditandai ke konsentrator lain. Sehingga


57 algoritma menswitch ke subgradien optimmisasi dan menghasilkan sampai ratio antara batas bawah dan atas lebih kecil daripada nilai atau solusi penting lebih buruk daripada masalah sebelumnya atau jumlah maksimum dari iterasi telah dicapai. Ketika fase subgradien optimisasi berakhir, jika solusi layak ditemukan kemudian penyesuaian heuristik dapat mengupdate penugasan terminal yang diaplikasikan untuk memperbaiki solusi. Heuristik relaksasi lagrange gagal menemukan solusi layak hanya untuk 24 masalah Klincewicz et al (1986) menggunakan algoritma tersebut. DarbyDowman et al (1988) mendefinisikan klas problema untuk relaksasi lagrange dimana kendala kapasitas didualkan akan menghasilkan solusi yang tak layak tanpa memperhatikan nilai perkaliannya. Batas bawah L pada jumlah konsentrator yang diinstal dapat dihitung sebagai berikut: Andaikan Q(j) menotasikan kaP di menotasikan permintaan total. Maka L pasitas terbesar ke-j dan D = i∈N

ditentukan menggunakan hubungan berikut: L−1 X

Q(j) < D ≤

j=1

Berikutnya, andaikan

+(n−1) P

L X

Q(j)

j=1

menotasikan penjumlahan dari (n −1) kesatuan yang

paling positif. Jika terdapat kurang dari (n − 1) kesatuan yang positif, maka operator menotasikan jumlah semua kesatuan yang positif. Pertidaksamaannya sebagai berikut: +(n−1)

Fq >

X

(Cip − Ciq )

(4.49)

i∈N

jika pertidaksamaan (4.48) sesuai untuk semua p, q ∈ M, maka solusi masalah relaksasi hanya satu konsentrator yang diinstal, dan akan memiliki solusi dengan paling banyak (L − 1) konsentrator yang diinstal.


58 Relaksasi lagrange yang kedua untuk MLKC diperoleh dengan mendualkan penugasan kendala (2.7) dengan pengali lagrange u. Vektor u menghasilkan problema sebagai berikut: LR(u) min

P P

(Cij + ui )xij +

i∈N j∈M

P

Fj yj −

j∈J

P

ui

i∈N

kendala (2.8), (2.9), (2.10), (2.12) Dual lagrangenya adalah: LD(u) = max LR(u) u

Pirkul, H. (1987) membangun heuristik berdasarkan relaksasi. Problema LR(u) didekomposisikan pada m problema knapsack untuk tiap konsentrator sebagai berikut: LRj (u) = min

P

(Cij − ui)xij + Fj yj

i∈N

kendala P di xij ≤ Qj yj i∈N

xij ≤ yj

i∈N

xij ∈ {0, 1}

∀i ∈ N, yj ∈ {0, 1}

Jika solusi optimal untuk problema knapsack adalah positif maka konsentrator j diinstal. Lainnya untuk yj adalah 0. Dual lagrange diselesaikan menggunakan subgradien optimisasi. Sridharan (1993) menanggapi beberapa relaksasi lagrange dan menggunakan sejumlah kendala kapasitas, X j∈M


Qj yj ≥

X i∈N

di

(4.50)

59 untuk memperkuat formulasi. Relaksasi LR(u) dengan penambahan kendala (4.49) medekomposisikan ke dalam m problema bebas knapsack untuk tiap j, khususnya:

P

LR(u) = min

LRj (u)yj +

j∈M

P

ui

i∈N

kendala (2.10), (4.49) dimana LRj (u) = min

P

(Cij − ui)xij + Fj

i∈N

kendala P di xij ≤ Qj i∈N

xij ∈ {0, 1}

∀i ∈ N

Andaikan x∗ merupakan solusi optimal untuk LRj (u) dan y ∗ merupakan solusi optimal pada LR(u) untuk u yang tetap. Maka solusi optimal untuk LR(u) diberikan dengan yj = yj∗ dan

xij =

   x∗ , jika y ∗ = 1 ij j

  0, untuk lainnya

Relaksasi lagrange ini memiliki batas yang lebih baik dibandingkan dengan batas relaksasi program linier kecuali di = d ∀i ∈ N dan Qj ( mod d) = 0 ∀j ∈ M. Heuristik menggunakan LR(u) tidak hanya pada batas bawah problema tetapi juga menetapkan yj dan kemudian menuju pada sumber problema transportasi yang didefinisikan pada himpunan konsentrator untuk yj = 1. Dan tentunya menghasilkan batas atas.


60 4.4 Generasilasi Model MLKC

4.4.1 MLKC dengan Banyak Tipe Konsentrator MLKC dengan banyak tipe konsentrator merupakan generalisasi dari MLKC yang tiap kandidat lokasi diberikan kumpulan tipe konsentrator dengan kapasitas dan biaya yang berbeda. Sehingga keputusan menentukan lokasi dan tipe konsentrator dan menugaskan terminal ke subjek konsentrator untuk kendala kapasitas. Model masalahnya sebagai berikut: min

XX

Cij xij +

i∈N j∈M

XX

Fjk yjk

j∈M k∈K

kendala X

xij

∀i ∈ N

j∈M

X

yjk ≤ 1 ∀j ∈ M

k∈K

X

di xij ≤ Qjk yjk

∀j ∈ M, k ∈ K

i∈N

xij ∈ {0, 1} ∀i ∈ N, j ∈ M yjk ∈ {0, 1} ∀j ∈ M, k ∈ K

dimana K merupakan kumpulan tipe konsentrator, Fjk merupakan biaya penginstalan konsentrator dari tipe k pada lokasi j, Qjk merupakan kapasitas konsentrator dari tipe k pada lokasi j dan    1, jika tipe konsentrator k diinstal pada lokasi j yjk =   0, untuk lainnya


61 untuk semua j ∈ M dan k ∈ K. Untuk masalah ini, Lee, C. Y. (1993) mengajukan algoritma berdasarkan dekomposisi silang, yang dikombinasikan dengan Dekomposisi Benders dan Relaksasi Lagrange.

4.4.2 MLKC dengan Konsentrator Ganda Pada MLKC, tiap terminal ditugaskan pada konsentrator tunggal, untuk meningkatkan kehandalan jaringan, pembuat keputusan lebih suka menugaskan terminal pada lebih dari satu konsentrator. Tang et al. (1978) menyatakan bahwa untuk menghubungkan terminal i secara tepat ke konsentrator βi . Model ini sama dengan MLKC kecuali penugasan kendala (2.7) yang diganti dengan X

xij = βi

∀i ∈ N

j∈M

Model ini mengasumsikan bahwa kapasitas konsentrator dalam bentuk jumlah terminal yang ditugaskan. Pirkul et al. (1988) mempelajari problema dimana tiap terminal ditugaskan pada dua konsentrator, satu pada jaringan utama dan kedua pada jaringan pendukung. Tiap terminal membutuhkan tugas ke k konsentrator. Selanjutnya menggunakan relaksasi lagrange dengan kendala jaringan utama dan pendukung yang didualisasikan. Kemudian mengurangi problema ke dalam problema bebas knapsack untuk tiap konsentrator. Dual lagrange diselesaikan dengan subgradien optimisasi dan heuristik untuk membangun solusi layak di tiap iterasi dari subgradien optimisasi yang diberikan.


62 4.5 Masalah Fasilitas Lokasi Dinamik Masalah Fasilitas Lokasi Dinamik (MFLD) adalah ketika permintaan terminal meningkat melebihi waktu, tentunya diperlukan memperluas ukuran konsentrator dan kapasitas link dalam jaringan. Masalah perluas jaringan secara optimal melebihi jangkauan perencanaan untuk meningkatkan permintaan. Shulman (1991) menganggap bahwa MFLD adalah terdapat konsentrator dari tipe yang berbeda. Kemudian menentukan batas atas pada jumlah konsentrator yang akan diinstal pada lokasi yang diberikan. Tujuannya untuk meminimumkan biaya penginstalan konsentrator, biaya dari permintaan yang dikirim dari terminal dan biaya operasi. Diasumsikan bahwa permintaan terminal boleh disupply dengan beberapa terminal. Dua kasus akan muncul, kasus pertama merupakan pencampuran tipe konsentrator yang berbeda pada lokasi diijinkan, dan kasus kedua hal tersebut tidak diijinkan. Chardaire et al (1996) membangun model untuk menentukan kapan dan dimana untuk menginstal konsentrator bersyarat pada lingkungan dan dimana permintaan terminal meningkat. Tujuannya adalah meminimumkan biaya pengisntalan konsentrator baru, operasi dan biaya penugasan terminal.


BAB 5 KESIMPULAN

5.1

Kesimpulan

a. Chung et al. (1992) membangun model untuk desain tipe jaringan penuh atau jaringan bintang, contohnya semua konsentrator dihubungkan untuk tiap terminal yang ditugaskan ke konsentrator secara langsung dihubungkan pada konsentrator ini. Kemudian diformulasi dimana fungsi biaya termasuk ke dalam biaya konsentrator yang diinstal. Sehingga model sama dengan P P MFLU kecuali fungsi biaya juga termasuk dalam bentuk j∈J l∈J Bjl yj yl dimana Bjt adalah biaya penghubung konsentrator j dan /. Sehingga total fungsi biaya merupakan kuadratik. Pada bagian ini, formulasinya dilinearisasi dan prosedur solusi berdasarkan dual serta hasil perhitungan juga diberikan. b. Oleh sebab itu, dipresentasikan relaksasi Lagrange berdasarkan prosedur solusi untuk menyelesaikan formulasi nonlinier ini. Sehingga merepresentasikan model Chardaire et al. (1999) untuk mendesain jaringan bintang dengan konsentrator tingkat kedua sebagai contoh tiap terminal dihubungkan pada konsentrator tingkat pertama yang juga dihubungkan pada konsentrator tingkat kedua. Semua konsentrator tingkat kedua dihubungkan pada pusat unit. Kemudian dipresentasikan formulasi dua program integer dan ditunjukkan bahwa relaksasi linier dari kedua formulasi untuk bound yang sama.


64 c. Masalah Fasilitas Lokasi Dinamik (MFLD) adalah ketika permintaan terminal meningkat melebihi waktu, tentunya diperlukan memperluas ukuran konsentrator dan kapasitas link dalam jaringan. Masalah perluas jaringan secara optimal melebihi jangkauan perencanaan untuk meningkatkan permintaan. d. Shulman (1991) menganggap bahwa MFLD adalah terdapat konsentrator dari tipe yang berbeda. Kemudian menentukan batas atas pada jumlah konsentrator yang akan diinstal pada lokasi yang diberikan. Tujuannya untuk meminhnumkan biaya ffenginstalan konsentrator, biaya dari permintaan yang dikirim dari terminal dan biaya operasi. Diasumsikan bahwa permintaan terminal boleh disupply dengan beberapa terminal. Dua kasus akan muncul, kasus pertama merupakan pencampuran tipe konsentrator yang berbeda pada lokasi diijinkan, dan kasus kedua hal tersebut tidak diijinkan.


DAFTAR PUSTAKA

Amiri A., 1997, ”Solution procedures for the service system design problem”, Computers and operations research, 24: 49-60. Aardal K., Phocet Y., and Wolsey L. A., 1995, ”Capacitated facility location: valid inequalities and facets”, Mathematics of operations research, (20), 562-582. Balakrishnan A., Magnanti T. L., and Wong R. T., 1995, ”Decomposition algorithm for local access telecommunications network expansion planning”, Operations Research, 43: 58-76. Benichou, M., Gauthier, J. M., Girodet, P., Hentges, G., Ribiere, G. and Vincent, O., 1971, ”Experiments in Mixed-Integer Linear Programming”, Mathematical Programming. 1:76-94. Berrada, M. and Stecke, K. E. A., 1986, ”Branch and Bound Approach for Machine Load Balancing in Flexible Manufacturing Systems”, Management Sci. 32: 1316-1335. Boffey T. B., 1989, ”Location problems arising in computer network”, Journal of operations research society, 40: 347-354. Chardaire P., Lutton J. L., and Sutter A., 1999, ” Upper and lower bounds for the two-level simple plant location problem”, Annals of Operations Research, (86), 117-140. Chardaire P., Sutter A., and Costa M. C., 1996, ” Solving the dynamic facility location problem”, Networks, (28), 117-124. Chung, S., Myung, Y., and Tcha, D., 1992, ”Optimal Design of a Distributed Network with a Two-Level Hierarchical Structure”, European Journal of Operation Research, (62): 105-115. Current, J., and Pirkul, H., 1991, ”The Hierarchical Network Design Problem with Transshipment Facilities”, European Journal of Operations Research, (52): 338-347. Dakin, R. J. A., 1965, ”Tree Search Algorithm for Mixed Integer Programming”, Computer Journal 8: 250-255. Darby-Dowman K., and Lewis H. S., 1988, ”Lagrangian relaxation and the single source capacitated facility location problem”, Journal of operational research society, (39), 1035-1040. Erlenkotter D., 1978, ”A dual based procedure for uncapacitated facility location”, Operations research, (26), 992-1009. Fauzi, R dan Suherman, 2006, ”Jaringan Telekomunikasi”, Teksbook e-learning Departemen Teknik Elektro, Fakultas Teknik Universitas Sumatera Utara.


66 Gavish, B., 1982, ”Topological Design of Centralizad Computer Networks: Formulation and Algorithms”, Networks, (12): 355-377. Gavish, B., 1992, ”Topological Design of Computer Communication NetworksThe Overall Design Problem”, European Journal of Operation Research, (58): 149-172. Gourdin, E., Labbe, M., and Yaman, H., 2001, ”Telecommunication and Location”, France Telecom R&D, DAC/OAT Universite Libre de Bruxelles Service de Mathematiques de la Gestion, Belgium. Gupta, O.K. and Ravindran, A., 1985, ”Branch and Bound Experiments in Convex Nonlinear Integer Linear Programming”, Management Science, 31:1533-1546. Hakimi S. L., 1964, ”Optimum locations of switching centers and the absolute centers and medians of a graph”, Operations research, 12: 450-459. Hakimi S. L., 1965, ”Optimum distribution of switching centers in a communication network and some related graph theoretic problems”, Operations research, 13: 462-475. Helme M. P., and Magnanti, T. L., 1989, ”Designing satellite communication networks by zero-one quadratic programming”, Networks, 19: 427-450. Klincewicz J. G., 1998, ”Hub location in bacbone/tributary network design: a review”, Location science, 6: 307-335. Klincewicz J. G., and Luss H., 1986, ”A lagrangian relaxation heuristic for capacitated facility location with single source constraint”, Journal of operational research society, 37: 495-500. Korner, F., 1983, ”An efficient Branch and Bound Algorithm to Solve Quadratic Integer Programming Problem”, Computing 30: 253-260. Land, A. H. and Doig, A. G., 1960, ”An Automated Method for Solving Discrete Programming Problems”, Econometrics 28: 497-520. Lee C. Y., 1993, ”An algorithm for the design of multitype concentrator networks”, Journal of operational research society, 44: 471-482. Lee, Y., Lim, B. H., and Park, J. S., 1996, ”A Hub Location Problem in Designing Digital Data Service Networks: Lagrangian Relaxation Approach”,Location Science, (4): 185-194. Leung J. M. Y., and Magnanti T. L., 1989, ”Valid inequalities and facets of the capacitated plant location problem”, Mathematical programming, (44), 271291. Marianov V. and Rios M., 1996, ”Queueing-plant location and queueing p-median models for the design of circuit switched telecommunications networks with constrained buffer (cell queue) length at switches”, Proceedings ALIO-EURO conference, Valparaiso, Chile, 115-127.


67 Mateus, G. R., Cruz, F. R. B., and Luna, H. P. L., 1994, ”An Algorithm for Hierarchical Network Design”, Location Science, (2): 149-164. Mirzaian A., 1985, ”Langrangian relaxation for the star-star concentrator location problem: approximation algorithm and bounds”, Networks, 15: 1-20. Monticone L. C. and Funk, G., 1994, ”Application of the facility location problem to the problem of locating concentrators on an FAA microwave system”, Annals of operations research, 50: 437-454. Nemhauser G. L., and Wolsey L. A., 1988, ”Integer and combinatorial optimization”, Wiley, New York. Pirkul H. 1987, ”Efficient algorithms for the capacitated consentrator location problem”, Computers and operations research, (14), 197-208. Pirkul, H., and Nagarajan, V., 1992, ”Locating Concentrators in Centralized Computer Network”, Annals of Operations Research, (36): 247-262. Pirkul H., Narasimhan S., and De P., 1988, ”Locating concentrators for primary and secondary coverage in a computer communications network”, IEEE transactions on communications, (36), 450-458. Shulman A., 1991, ”An Algorithm for solving dynamic capacitated plant location problems wth discrete expansion sizas” Operations research, (39), 423-436. Sridharan R., ”A lagrangian heuristic for the capacitated plant location problem with single source constraints”, European journal of operations research, (66), 305-312. Tang D. T., Woo L. S., and Bahl L. R., 1978, ”Optimization of teleprocessing networks with concentrators and multiconnected terminals”, IEEE transactions on computers, (27), 594-604.


MODEL TELEKOMUNIKASI DAN LOKASI

Recommend Documents