Goal Programming (Program Optimasi Tujuan Ganda)

GOAL PROGRAMMING

(Program Optimasi Tujuan Ganda)

Yuhka Sundaya

Artikel ini Saya tulis ketika memelajari riset operasi. 

'Cites :

Sundaya, Y. 2005. Teori dan Latihan Metode Optimasi : Linear Programming. Perpustakaan Pribadi. Cimahi.

Meskipun saat ini solusi masalah optimasi dengan jumlah tujuan yang banyak telah disupport oleh banyak perangkat, namun logika dibalik cara kerja perangkat tersebut perlu dipahami logikanya. Artikel ini semoga bisa membantu memahami logika atau cara kerja optimasi tersebut. Materi pada artikel ini disadur dari :

Taha, H. 1997. Operations Research an Introduction Sixth Edition. Prentice-Hall International. London.

Pendahuluan

Linear Programming berfungsi untuk mencari solusi optimum dengan fungsi tujuan tunggal. Terdapat situasi dimana sebuah sistem mungkin memiliki tujuan berganda. Sebagai contoh, seorang politikus berjanji untuk mengurangi pinjaman nasional dan secara simultan mengurangi penerimaan pajak. Dalam situasi itu tidak mungkin menemukan soulsi tunggal yang mengoptimisasi tujuan yang bertolak belakang. Kita dapat mencari solusi yang kompromis didasarkan pada kepentingan relatif dari masing-masing tujuan.

Teknik goal programming digunakan untuk memecahkan masalah dengan model tujuan berganda. Ide prinsipnya adalah mengkonversi tujuan ganda awal ke dalam sebuah tujuan tunggal. Lebih lanjut, modal akan menghasilkan solusi efisien sebab hal itu tidak mungkin optimum yang terkait dengan masalah yang memiliki tujuan yang saling bertolak belakang.

Formulasi Goal Programming

Gagasan Goal Programming diilustrasikan dengan sebuah contoh. Misalnya, Bandung yang memiliki penduduk sebanyak 20 000 orang. Dewan kota kemudian sedang merumuskan pengembangan penerimaan pajak. Pajak tahunan yang diperoleh dari perumahan sebesar Rp 550 juta. Pajak tahunan dari makanan dan minuman dan penjualan umum sebesar Rp 35 juta dan Rp 55 juta, secara berurutan. Konsumsi gas lokal tahunan diperkirakan sebesar 7.5 juta galon. Dewan kota ingin mengembangkan tingkat pajak di dasarkan atas empat tujuan utama, yaitu :

Penerimaan pajak harus sekurang-kurangnya sebesar Rp 16 juta untuk memenuhi komitmen keuangan kota;

Pajak makanan dan minuman tidak lebih dari 10% dari seluruh pajak yang dikumpulkan;
Pajak penjualan umum tidak lebih dari 20% dari seluruh pajak yang dikumpulkan; dan
Pajak gas tidak lebih dari 0.2 rupiah per galon.

Misalnya, variabel xp, xf, dan xs menunjukkan tingkat pajak (dinyatakan sebagai proporsi) untuk perumahan, makanan dan minuman, serta penjualan umum dan variabel xg sebagai paja gas dalam rupiah per galon.

Tujuan dewan kota dapat dinyatakan sebagai berikut :

550x_p + 35x_f + 55x_s + 0.075x_g ³ 16 ... penerimaan pajak

35x_f ≤ 0.1(550x_p + 35x_f + 55x_s + 0.075x_g) ... pajak makanan dan minuman

55x_s ≤ 0.2(550x_p + 35x_f + 55x_s + 0.075x_g) ... pajak penjualan umum

x_g ≤ 2 ... pajak gas

x_p, x_f, x_s, x_g ³ 0

Kendala tersebut diringkas sebagai berikut :

550x_p +    35x_f + 55x_s + 0.075x_g ³ 16

  55x_p – 31.5x_f + 5.5x_s + 0.0075x_g ³ 0

110x_p + 7x_f – 44x_s + 0.015x_g ³ 0

x_g ≤ 2

x_p, x_f, x_s, x_g ³ 0

Masing-masing ketidaksamaan dari model menunjukkan sebuah tujuan yang mana aspirasi dewan kota terpenuhi. Bagaimanapun tujuan tersebut saling bertolak belakang dan pekerjaan yang terbaik adalah mencoba untuk mencapai solusi yang kompromis.

Tahapan untuk mencapai solusi yang kompromis tersebut adalah pertama, masing-masing ketidaksamaan dikonversi ke dalam tujuan yang fleksibel yang mana kendala dapat dilanggar, jika diperlukan. Dalam kasus Kota Bandung, tujuan yang fleksibel dapat dinyatakan sebagai berikut :

550x_p +    35x_f + 55x_s + 0.075x_g + S₁⁺ - S₁^- = 16
  55x_p – 31.5x_f + 5.5x_s + 0.0075x_g + S₂⁺ - S₁^- = 0
110x_p + 7x_f – 44x_s + 0.015x_g + S₃⁺ -  S₃^- = 0
x_g + S₄⁺ - S₄^- = 2
x_p, x_f, x_s, x_g ³ 0
s_i⁺, s_i^- ³ 0, i = 1, 2, 3, 4

Variabel non negatif Si+ dan Si- disebut dengan variabel deviasional sebagai mereka menunjukkan diviasi (penyimpangan) di atas dan di bawah sisi kanan kendala ke “i”. Variabel deviasional Si+ dan Si- bersifat dependen, dan karenanya tidak dapat menjadi variabel basic secara simultan. Artinya bahwa setiap iterasi simplex, satu dari dua variabel deviasional dapat diasumsikan bernilai positif. Jika, ketidaksamaan “i” semula berbentuk ≤ dan si+ nya > 0, kemudian tujuan ke “i” akan dipenuhi, dengan cara lain, jika si- > 0, maka tujuan ke “i” tidak dapat dipenuhi. Esensinya, pengertian variabel deviasional memutuskan kita untuk memenuhi atau melanggar tujuan ke “i”. Inilah bentuk fleksibilitas dari goal programming ketika mencoba untuk mencapai solusi yang kompromis. Secara alamiah salah satu solusi kompromis yang baik adalah menemukan minimisasi dari jumlah dengan mana masing-masing jumlah dilanggar.

Dalam model Kota Bandung sebelumnya, tiga kendala pertama berbentuk “³” dan kendala keempat berbentuk “≤”, keempat variabel deviasional menunjukkan jumlah dengan mana tujuan yang saling terkait dapat dilanggar. Kemudian, solusi kompromis yang harus ditemukan untuk memenuhi keempat tujuan yang memungkinkan sebagai berikut :

Minimisasi G1 = S₁⁺
Minimisasi G2 = S₂⁺
Minimisasi G3 = S₃⁺
Minimisasi G4 = S₄^-

Fungsi tersebut adalah minimisasi syarat ikatan terhadap kendala persamaan dari model.

Bagaimana kita dapat mengoptimisasi model tujuan ganda dengan tujuan yang bertolak belakang ? Dua metode telah dikembangkan untuk memenuhi tujuan ini, yaitu [1] metode pembobotan (weighting method) - WM dan [2] metode pengutamaan (preemtif method) - PM. Masing-masing metode didasarkan atas konversi tujuan berganda ke dalam tujuan tunggal.

Melalui WM, sebuah fungsi tujuan tunggal dibentuk sebagai jumlah bobot dari fungsi yang menunjukkan tujuan dari masalah. Sedangka dalam PM dimulai dengan memprioritaskan atau mengutamakan tujuan dalam susunan yang terpenting. Model kemudian dioptimisasi dengan menggunakan satu tujuan pada suatu waktu, dan dalam beberapa cara bahwa nilai optimum dari tujuan prioritas tertinggi tidak dikurangi oleh tujuan prioritas terendah.

Tujuan kedua metode berbeda. Dalam pengertian bahwa kedua metode tersebut tidak akan secara umum menghasilkan solusi yang sama. Masing-masing metode, bagaimanapun, dapat diklaim superior sebab masing-masing teknik didesain untuk memenuhi kencenderungan pembuatan keputusan tertentu.

Sebagai ilustrasi dikemukakan salah satu contoh persoalan yang diselesaikan dengan menggunakan kedua metode tersebut. Perusahaan TopAd merupakan perusahan periklanan baru dengan 10 orang tenaga kerja telah menerima kontrak untuk mempromosikan produk baru. Agen tersebut dapat mengiklankan melalui radio dan televisi. Tabel berikut menyajikan data mengenai jumlah orang yang dapat dicapai oleh masing-masing bentuk iklan dan biaya serta tenaga kerja yang dibutuhkan.

	Data/Iklan Minimal
	Radio	Televisi
Pembukaan (dalam juta orang)	4	8
Biaya (dalam juta dollar)	8	24
Tenaga Bantuan	1	2

Selanjutnya, dalam kontrak TopAd dilarang untuk menggunakan lebih dari 6 menit dari iklan radio. Dengan penambahan, iklan dalam radio dan televisi perlu untuk mencapai sekurang-kurangnya 45 juta orang. TopAd telah menyusun anggaran untuk proyek tersebut sebesar $100 000. Berapa menit iklan di radio dan iklan di televisi yang harus digunakan oleh TopAd ?

Katakanlah, x1 dan x2 adalah jumlah menit yang dialokasilan untuk iklan di radio dan iklan di televisi secara berurutan. Formulasi goal programming untuk masalah tersebut dinyatakan sebagai berikut :

Minimisasi G1 = S1+ (penuhi tujuan pembukaan)
Minimisasi G2 = S2- (penuhi anggaran tujuan)
Syarat Ikatan :
4x1 + 8x2 + S1+ - S1- = 45 (tujuan pembukaan) ... [1]
8x1 + 24x2 + S2+ - S2- = 100 (tujuan anggaran) ... [2]
x1 + 2x2 ≤ 10 (batasan tenaga kerja) ... [3]
x1 ≤ 6 (batasan radio) ... [4]
x1, x2, S1+, S2+, S1-, S2- ³ 0 ... [5]

Kemudian, TopAd menganggap bahwa tujuan pembukaan dua kali lebih penting dari tujuan anggaran, maka kombinasi fungsi tujuan tersebut dinyatakan sebagai berikut :

Minimisasi Z = 2G1 + G2 = 2S1+ + S2-

Dengan syarat ikatan [1] s.d [5]

Solusi dengan menggunakan program Lindo menghasilkan Z = 10, x1 = 5 menit, x2 = 2.5 menit dan S1+ = 5 juta orang. Seluruh variabel sisanya sama dengan nol.

Dengan demikian, alokasi iklan untuk radio sebanyak 5 menit dan ilan di televisi sebanyak 2.5 menit akan menjaring orang sebanyak [(4x5) + (8x2.5) = 40 juta orang] dengan biaya atas kedua jenis ilan tersebut sebesar [(8x5) + (24x2.5) = 100 ribu).

Kenyataannya bahwa nilai optimum dari Z tidak sama dengan nol, hal itu menunjukkan bahwa sekurang-kurangnya salah satu dari tujuan tidak tercapai. Secara khusus, S1+ = 5, artinya bahwa tujuan pembukaan (dari sekurang-kurangnya 45 juta orang) adalah kehilangan 5 juta individu. Sebaliknya, tujuan anggaran (tidak melebihi $100 000).

Goal Programming hanya menghasilkan sebuah solusi yang efisien terhadap masalah, yang mana tidak secara perlu mencapai optimum. Sebagai contoh, jika misalnya x1 = 6 dan x2 = 2, makaakan menghasilkan tujuan pembukaan yang sama [(4x6) + (8x2) = 40 juta orang), sedangkan biaya akan menurun [(8*6) + (24*2) = 96 ribu). Esensinya, Goal Programming hanya menemukan solusi yang hanya memenuhi tujuan dari model. Beberapa kekurangan dalam mencapai solusi oprimum memunculkan pertanyaan mengenai kemungkinan Goal Programming sebagai sebuah teknik optimasi.

Contoh Aplikasi