Metode Big-M

Pengantar Optimisasi Metode Big-M untuk Program Linier 

Jika kita sudah mempelajari simplex. Itu adalah dasar dari optimisasi program linier. Memaksimumkan atau meminimumkan fungsi objektif. Metode tabel sendiri tidak lain adalah simplex yang dibentuk tabel untuk memudahkan perhitungan. Bagaimana dengan metode Big-M? adakah bedanya dengan simplex? Tentu saja.. walaupun sama-sama menyelesaikan masalah program linier.

Metode simplex tidak bisa menyelesaikan program linier dengan cepat jika kita menghitung manual. Makanya kita menggunakan metode tabel. Tapi kelemahan metode tabel ini. BFS awalnya harus identitas. Tidak selamanya program linier yang ditambahkan slack variabel bisa memiliki BFS awal yang identitas.

Minimumkan

 Dengan kendala:

Sekarang kendala kita jadikan bentuk baku dan fungsi objektifnya menjadi sama dengan 0:

Minimumkan

Dengan kendala:

Saya akan memilih basis awal/BFS awal 3,4,5 seperti biasa dari slack variabel. Maka tabel awalnya akan begini:

BFS awal bukan identitas. Kita tidak boleh mengalikan -1 pada baris variabel  dan  karena akan berakibat R menjadi negatif. Sementara dalam metode tabel, pada pertukaran basis; jangan sampai nilai R negatif karena bisa mengakibatkan beberapa basis tidak bisa keluar, dan ini bisa berakibat fatal, anda akan berputar terus-terusan tanpa dapat solusi optimal atau solusi optimal bisa salah.

ITULAH kelemahan metode tabel jika BFS awal bukan identitas anda akan terjebak di looping selamanya, 1 masuk 4 keluar, lalu berikutnya 2 masuk 1 keluar. Lalu 4 masuk lagi 2 keluar. Begitu terus seperti terjebak di labirin. Atau proses stop tapi ternyata solusi tidak optimal.

Untuk kasus seperti ini dimana variabel basis anda bukan identitas dibuatlah metode Big-M. kita sudah punya slack variabel. Tapi kita menginginkan basis awal yang identitas. Jadi perlu ditambahkan artificial variabel, banyak banget ya? Tenang artificial variabel ini hanya agar kita bisa memiliki basis awal yang identitas. Sesudah itu kita kembali dengan metode tabel.

Algoritma Metode Big M:

Minimumkan

Dengan kendala:

1.Menambahkan artificial variabel agar BFS bisa menjadi identitas

Tambahkan artificial variabel dan jadikan ke bentuk:

Minimumkan

Dengan kendala:

adalah artificial variabel. Sehingga BFS awal kita bisa menjadi identitas. Dan mudah untuk mencari solusi optimumnya.

Artificial variabelnya akan kita paksa jadi 0 selama proses Big-M ini. Harus ya.. dipaksa.. Ya dengan kata lain Big-M itu proses mengutak-atik agar metode simplex atau tabel bisa dilakukan.

2.Buat tabel awalnya

Seperti biasa saya titik-titik karena isinya nanti itu konstanta dari fungsi objektif dan kendala program linier.  Sementara baris z yang berada di kolom artificial variabel diberi tanda –M. itulah M kita. Big-M. M besar. Menang, MENANG.

Maksud dari Big-M ini adalah menambahkan konstanta M, sebuah bilangan bulat positif yang sangat besar, sangat sangat sangat besar sekali. Gausah dibayangkan... 9793865864823648236423, bahkan lebih besar dari itu.

M itu merupakan alat bantu. Agar program linier bisa diselesaikan dengan simplex atau tabel. Jika suatu program linier bentuknya walau sudah ditambah slack variabel tidak bisa diselesaikan: looping atau solusi optimalnya salah. Metode Big-M ini digunakan agar solusinya konvergen ke solusi optimal dengan simplex.

Kalau anda penasaran maksud dan penjelasan M ini. Bisa dicari sendiri. Baca bukunya, saya bikin blog bukan copas buku.

Kalikan baris basis artificial variabelnya dengan M lalu tambahkan ke baris z

Jika bingung lebih baik liat contoh nanti. Di buku juga langsung contoh ga ada dikasih algoritma kaya saya gini.

Setelah tahap ketiga ini anda langsung gunakan metode tabel, tahap pencarian basis baru, ditukar lalu sampai dapat solusi optimal.

Sedikit kan? Namanya saja metode Big-M itu pengantar menuju metode simplex atau tabel. Saya sering tulis tabel karena kalau saya pakai simplex ribet ngitungnya. Tapi sama saja mau pakai simplex atau tabel habis ini, kan metode tabel itu SIMPLEX yang DITABELKAN.

SELESAI

Sekarang kita langsung contoh coba Big-M ini benar ga nih? Atau cuma gede otot doank otak kosong. Big-Muscle

Minimumkan

Dengan kendala:

1.Menambahkan artificial variabel agar BFS bisa menjadi identitas

Sekarang agar bisa dapat basis awal identitas, maka perlu ditambah artificial variabel:

Minimumkan

Dengan kendala:

2.Buat tabel awalnya

3.Kalikan baris basis artificial variabelnya dengan M lalu tambahkan ke baris z

Variabel artificial itu hanya variabel 6 dan 7 ya jadi kalikan baris variabel 6 dan 7 dengan M lalu ditambahkan ke baris z hasilnya adalah:

Ini adalah tabel yang sudah bisa di-metode tabelkan / disimplexkan.

4. Metode tabel siap dimulai

Anda gabosen kan dengan metode tabel? Malah enak minta nambah? Cari basis baru liat baris z paling maksimum yang lebih besar dari 0 lalu dari yang harus dikeluarkan dari basis. Untuk ditukar. Terus ganti jadi tabel iterasi kedua, ulang lagi cari basis baru; sampai baris z tidak ada lagi yang lebih besar dari 0, alias tidak ada lagi basis baru yang bisa masuk.

Sebenarnya jika anda simak baik-baik memang benar metode Big-M ini pengantar menuju metode tabel/simplex. Karena ujung-ujungnya kita akan pakai lagi metode tabel. Karena memang untuk mencari solusi optimal program linier baru satu metode yang ada yaitu SIMPLEX. Tabel itu versi mudah simplex jadi ngitungnya gampang. Nanti jika ada yang mau bikin metode menyelesaikan program linier namanya jangan menipu kaya gini ya.. simplex tapi ribet.

Saya tandai baris dan kolom pivotnya sisanya anda hitung sendiri. Cek apakah hitungan anda sudah benar. saya tandai langsung saja semua ya.

Tabel Iterasi ke 2:

Tabel Iterasi ke 3:

Tabel Iterasi ke 4:

Tabel Iterasi ke 5:

Sudah selesai akhirnya..

Jadi solusi optimal dengan fungsi objektif akan minimum bernilai -6, untuk nilai variabel:

Dan juga nonbasis termasuk slack dan artificial variabelnya akan sama dengan 0:

Minimumkan

Nilai tersebut adalah yang paling minimum sekaligus juga memenuhi kendala.

Yang penting kan diawal itu yang ditanya hanya 2 variabel. Lalu kita tambahkan slack variabel, lalu ada lagi artificial variabel. Penambahan variabel macam-macam ini sebenarnya tidak merubah masalah optimisasi yang kita punya.

Jadi jika tadi sudah didapat BFS optimal itu adalah variabel 2,3,4 dengan nilai:

Otomatis variabel lain bernilai 0.

Selain optimal, nilainya akan memenuhi kendala:

Yang saya maksud tidak merubah masalah optimisasi itu, seperti ketika masalah maksimum jadi minimum; tidak akan merubah hasilnya, cuma dikali minus nilai optimal akhirnya saja. Begitu juga pada kendala, jika kendala yang sudah ditambah slack dan artificial variabel terpenuhi. Kendala awal(dari masalah optimisasi yang sebenarnya) pasti terpenuhi juga.

Cek saja masukkan:

dan

Pasti terpenuhi..

Sebenarnya selain metode Big-M ini ada juga metode dua fase. Tapi sama saja. Metode dua fase dan Big-M merupakan pengantar menuju metode simplex atau tabel. Saya buat artikel Big-M karena ini lebih singkat algoritmanya. Jika menggunakan metode dua fase juga hasilnya pasti sama. Kan intinya mencari nilai optimum. Hanya saja kalau dua fase dibagi dua tahap menghitung tabelnya, tahap pertama menghilangkan artificial variabel lalu baru masuk ke simplex. Kalau Big-M bisa langsung saja tidak usah pakai 2 tahap.

Ini pasti artikel tentang metode pengantar optimisasi paling singkat. Yaiyalah tapi kan isinya itu kalau anda mau ngerti anda perlu baca yang artikel metode tabel dulu. Kalau ga nanti bingung.. ajaib tabelnya bisa berubah. Disini juga ga saya jabarkan perubahan isi tabelnya karena itu jadi latihan anda. jangan malas. Nanti alzheimer lho. Ga nyumpahin, tapi kenyataan. Coret-coret hitung, metode tabel itu mudah.

Artikel simplex juga perlu dibaca karena itu adalah dasarnya. Metode tabel kan dibuat berdasarkan simplex. Coba tebak saya udah bilang berapa kali metode tabel itu adalah simplex yang ditabelkan? Pasti lebih dari sekali dua kali. Karena penting anda tahu metode untuk mencari nilai optimum suatu program linier itu baru satu saja yaitu simplex. Sisanya adalah pengantar ke simplex, atau modifikasi simpel dari simplex = tabel.

Soalnya saya dapat kabar burung kalau ada yang kira metode tabel itu beda dari simplex. Saya memang ga pernah tulis notasi simplex seperti B, A perkalian vektor c transpose, dll pada metode tabel. Karena itu ada dibuku. Isi dari tabel itu sebenarnya vektor c transpose, dan kolom R isinya vektor b, dll. Kalau saya bilang gitu pada artikel metode tabel bukannya anda jadi pusing? Saya langsung kasih tahu aja cara hitungnya gimana yang gampang. Anda penasaran ya baca bukunya kenapa bisa dibuat tabel begitu dari metode simplex.

Tapi saya berani jamin anda lebih ngerti baca artikel saya tentang metode tabel. Dibanding di buku. Karena saya juga beranjak dari gatau, lugu, nanya ke adik kelas. Ih anak mat 2011 dan 2012 menjanjikan semua.. pintar-pintar. Nanya acak aja pasti bisa jawab. Jadi kalau dikelas ga ngerti, tanya mereka.. trus catat.. dirumah dikerjain lagi sampai bisa. Ternyata dapat sendiri cara yang gampang ngerjainnya. Ini sebenarnya juga berkat mereka kalau aku ga ngerti metodenya gimana, kan aku juga gabisa nulis blog ini. Ga kaya orang yang nulis blog copas dari dosen lah. Ngerti ga ngerti artikelnya ada..

Ya sekalian lah, kan selasa besok mau UTS, bahannya dari simplex, tabel sampai Big-M. aku gausah baca buku. Aku mau print artikelku sendiri. Itulah gunanya kalau ngerti jangan cuma untuk diri sendiri. Tulis lagi.. bahkan aku jadiin blog, gratis orang boleh liat, tapi jangan dicopas tanpa izin. Jika suatu hari nanti kalau lupa, aku baca artikelku lagi aku bakal inget dan ngerti, selain bahasanya enak. Penjelasannya lugas, sistematis dan ga kaku.

Sumber : http://monyetlogam.blogspot.co.id/2014/10/pengantar-optimisasi-metode-big-m-untuk_21.html