Jumat, 31 Agustus 2012

[M_S] Fwd: Problem Gila-gilaan itu Terpecahkan (Traveling Salesman Problem)

 


Fwd: Problem Gila-gilaan itu Terpecahkan (Traveling Salesman Problem)
Posted By:Fri Aug 31, 2012 6:54 am  |
---------- Forwarded message ----------
From: Rusdi <>
Date: 2012/8/31
Subject:  Problem Gila-gilaan itu Terpecahkan (Traveling Salesman Problem)
Dari milist sebelah ,,,, 

Sent from my iPad

Begin forwarded message:

From: "syarwani" <syarwani@...>
Date: August 31, 2012 12:19:17 AM GMT+08:00
To: APICS-ID@yahoogroups.com
Subject: IPOMS-APICS Problem Gila-gilaan itu Terpecahkan (Traveling Salesman Problem)
Reply-To: APICS-ID@yahoogroups.com

 
Catatan: sudah dilakukan pengujian untuk problem2 TSP sekala international yg dikenal sukar dan berhasil dipecahkan dengan solusi yg optimal.

MSY
====
Problem Gila-gilaan itu Terpecahkan

Seorang matematikawan ITB menemukan teori baru yang bisa memecahkan
misteri matematika yang selama 200 tahun tak terungkap. Masih perlu
pengujian secara internasional.

Suatu kali, Anda mendapat tugas mengunjungi emapat kota dengan pesawat
carteran. Anda berangkat dari Jakarta. Kota-kota yang harus anda kunjungi,
katakanlah, Surabaya, Denpasar, Ujungpandang, serta Pontianak. Jika Anda
mendapat instruksi untuk menempuh jalur terpendek rute mana yang harus
Anda
lewati?

Kening Anda harus berkerut-kerut lebih dahulu, sebelum jawaban yang pasti
bisa ketemu. Syukur kalau Anda hafal di luar kepala jarak antara satu dan
lain kota. Kalau tidak, Anda harus encari jawaban di buku panduan wisata
atau mengukur skla jarak di peta. Itu baru langkah pertama. Selanjutnya,
Anda mesti menyusun beberapa alternative lintasan dan memilih jalur yang
paling hemat bahan bakar dan murah.

Jika Anda berhasil menemukan jawaban yang tepat dalam waktu singkat, Anda
termasuk kategori manusia cerdas. Betapa tidak, untuk mengunjungi 4
kota itu
ada 12 alternatif lintasan. Dan semua alternative itu harus dijajaki satu
persatu dengan menjumlahkan panjang lintasannya dan membandingkan satu
dengan yang lain.

Problem mencari lintasan semacam itu akan lebih memusingkan jika kota yang
harus disinggahi makin banyak. Ambil contoh, umpamanya trip itu ditambah
dengan Medan .Alternatif lintasan pada enam kota itu, termasuk Jakarta,
jumlahnya menjadi 60. Jika ditambah Padang, misalnya, alternatifnya
menjadi
360 lintasan. Kalau 16 kota?

Konon, problem matematis seperti itu telah ramai diperdebatkan sejak dua
abad silam. Selama ini, "teka-teki" tersebut tak pernah memperoleh jawaban
tuntas. Menghitung jumlah kombinasinya pun sudah pusing, apalagi kalau
harus
menentukan misalnya, lintasan terpendek atau terjauh. Kasus pelik, seperti
mencari lintasan terpendek pada trip ke sejumlah kota, adalah sebuah
contoh
kasus, dari gugus problem sejenis, yang oleh pakar matematika disebut
(nonpolynomial)-complete problem.

Kasus-kasus NP-complete problem ini mempunyai cirri yang khas: sebuah
problem matematik yang jika variabelnya bertambah sedikit saja akan
menyebabkan pertambahan waktu computer yang sangat besar untuk
memcahkannya. Pertambahan waktu yang berlipat-lipat itu tak lain
disebabkan
tidak tersedianya kunci praktis untuk menerobos inti persoalan.

Namun, problem tua itu agaknya kini mulai terkuak. Dr. Anang Zaini
Gani, matematikawan ITB, mengemukakan sebuah teori yang disebut "teori
interaksi", sebagai kunci pemecah NP-complete problem. Bahkan kasus-kasus
paling rumit dalam gugus itu, yang disebut The Trveling Salesman Problem
(TSP), oleh Anang Zaini dikatakan bisa ditembus oleh teori temuannya.
"Teori saya ini mampu memecahkan problem TSP sampai jumlah variable 57
atau lebih,"

TSP memang boleh disebut problem matematik yang gila-gilaan. Sepintas,
seperti problem mencari lintasan tadi, persoalan tampak sederhana. Tapi
program konvensional pada supercomputer pun bisa dibikin menyerah.
Bayangkan, untuk lima buah variable, supercomputer - dengan kemampuan satu
juta operasi per detik - hanya memerlukan 0,02 detik untuk memcahkan TSP.

Jika peubah bebas itu ditambah menjadi sepuluh, waktu yang diperlukan
untuk
memecahkannya berlipat hingga sepuluh menit. Namun, jika variable itu
digandakan menjadi 50, "Waktu yang diperlukan sampai tahunan,"
kata
Anang Zaini. Maklum, komputer itu harus membandingkan kombinasi-kombinasi
yang jumlahnya mencapai sebuah bilangan yang terdiri atas 65 angka!

Anang Zaini mengembangkan teorinya berdasarkan sebuah gagasan unik: sebuah
angka tidaklah mutlak adanya. "Nilai suatu elemen dalam sistem itu
sesungguhnya relative, tidak absolute," kata Zaini. Kenisbian nilai elemen
sistem itu, kata ayah empat anak ini, tergantung lingkungannya. Maka,
dalam
membangun teorinya, Zaini mengaitkan satu elemen dengan elemen lain
disekelilingnya, sehingga memperoleh koefisien interaksi. Komponen inilah
yang memungkinkan ahli desain industri itu memperoleh nilai-nilai nisbi.

Dalam memecahkan persolan TSP, Zaini tak melakukan pendekatan dengan
matematika tinggi."Cukup dengan aritmatika (ilmu hitung) biasa, " ujarnya.
Elemen TSP biasanya disusun dalam matriks. Ukuran matriks itu tentu
tergantung variable yang ada. Jika peubah bebasnya 50, matriksnya pun
berukuran 50 x50.

Anggota matriks kemudian ditransformasikan dengan mengalikan terhadap
koefisien interaksi. Indeks koefisien itu diperoleh dari penguadratan
anggota matriks terhadap besaran tertentu. Tahap berikutnya, setelah
transformasi, adalah penggarapan terhadap nilai-nilai nisbi dalam tubuh
matriks itu. Dan yang paling penting pada metode interaksi itu, "Hasil
yang
diperoleh dijamin optimal dan eksak," kata Zaini.

Sumber : Tempo



__._,_.___
Recent Activity:
----------------------------------------------------------------------
"Muhammadiyah ini lain dengan Muhammadiyah yang akan datang. Maka teruslah
kamu bersekolah, menuntut ilmu pengetahuan dimana saja. Jadilah guru kembali
pada Muhammadiyah. Jadilah dokter, kembali kepada Muhammadiyah. Jadilah
Meester, insinyur dan lain-lain, dan kembalilah kepada Muhammadiyah"
(K.H. Ahmad Dahlan).

----------------------------------------------------------------------
Salurkan ZAKAT, INFAQ dan SHODAQOH anda melalui LAZIS
MUHAMMADIYAH

No. Rekening atas nama LAZIS Muhammadiyah
1. Bank BCA Central Cikini
    (zakat) 8780040077 - (infaq) 8780040051
2. BNI Syariah Cab. Jakarta Selatan
    (zakat) 00.91539400 -   (infaq) 00.91539411
3. Bank Syariah Mandiri (BSM) Cab. Thamrin
    ( Zakat) 009.0033333 -  (Infaq) 009.00666666
4. Bank Niaga Syariah
    (zakat) 520.01.00186.00.0 - (infaq) 520.01.00187.00.6
5. Bank Muamalat Indonesia Arthaloka
    (Zakat) 301.0054715
6. Bank Persyarikatan Pusat
   (zakat) 3001111110 -  (infaq) 3001112210
7. Bank Syariah Platinum Thamrin
    (zakat) 2.700.002888 -  (infaq) 2.700.002929
8. BRI cab. Cut Meutia
    (zakat) 0230-01.001403.30-9 -    (infaq) 0230-01.001404.30-5

Bantuan Kemanusiaan dan Bencana:
BNI Syariah no.rekening: 00.91539444

DONASI MELALUI SMS
a. Jadikan jum'at sebagai momentum kepedulian,
salurkan donasi anda, ketik: LM(spasi)JUMATPEDULI kirim ke 7505

b. Bantuan kemanusiaan  ketik: LM(spasi)ACK kirim ke 7505

Nilai donasi Rp. 5000, semua operator,belum termasuk PPN

email: lazis@muhammadiyah.or.id
website : www.lazismu.org
.

__,_._,___

Tidak ada komentar:

Posting Komentar