ANALYSIS SENSITIVITAS PADA PROGRAM INTEGER CAMPURAN

Analysis Sensitivitas pada Program Integer Campuran Faigiziduhu Bu’ulolo

ANALYSIS SENSITIVITAS PADA PROGRAM INTEGER CAMPURAN Faigiziduhu Bu’ulolo Department Mathematik, Universitas Sumatera Utara, Medan 20155 Indonesia Abstrak: Metode Simpleks merupakan teknik untuk memecahkan persoalan program linear yang mempunyai jumlah variable keputusan dan pembatas yang besar, dimana penyelesaiannya merupakan prosedur aljabar yang bersifat iterative. Selanjutnya dilakukan langkah-langkah prosedur Gomory Cutting agar memenuhi variable keputusan yang dikehendaki integer. Jika tidak, suatu kendala Gomory baru dibuat lagi dari tabel yang dihasilkan dan metode dual simpleks digunakan lagi untuk mengatasi ketidaklayakan. Analisis sensitivitas yang dilakukan untuk mengetahui perubahan parameter dan pengaruh perubahan terhadap koefisien-koefisien variable keputusan yang kontinu dari fungsi tujuan setelah diperoleh penyelesaian optimal. Penentuan besarnya perubahan koefisien fungsi tujuan c dari nilai cj menjadi (cj + q) dapat diperoleh dalam batas-batas yang ditetapkan oleh semua variable nonbasis. Batas atas atau batas bawah nilai q gunakan formula CNBV = CBV . B-1 . ∝NBV – CNBV untuk variable nonbasis pada penyelesaian optimal Metode Simpleks dan Metode Gomory. Kata kunci: Simplex Method, Gomory’s Cutting Plane, Integer Program.

1.

Pendahuluan Dalam beberapa aplikasi pemrograman linear terdapat kebutuhan tidak hanya untuk mengoptimalkan fungsi tertentu dengan kondisikondisi tertentu, akan tetapi juga mengevaluasi pengaruh kondisi masalah yang terdapat dalam solusi optimal. Misalnya, hasil pembelian bahan mentah dari sumber lain yang menyebabkan koefisien fungsi tujuan cj berubah. Teknik untuk menyelesaikan masalah tersebut masuk kedalam kategori analisis sensitivitas dan pemrograman parametrik yang tergantung pada apakah perubahan dalam koefisien tersebut diskrit atau kontinu. Dengan menggunakan metode simpleks untuk menyelesaikan persoalan program linear yang merupakan prosedur aljabat yang bersifat iteratif, yang bergerak selangkah demi selangkah, dimulai dari suatu titik ekstrem pada daerah feasible (ruang solusi) menuju ke titik ekstrem yang optimum. Apabila pada suatu iterasi didapat persoalan program linear yang sudah optimum (berdasarkan kondisi optimalisasi), tetapi belum feasibel (ada pembatas nonnegative yang tidak terpenuhi), maka persoalan tersebut harus diselesaikan dengan menggunakan metode dual simpleks. Metode dual simpleks sangat penting untuk digunakan dalam analisis sensitivitas. Pemrograman linear integer (integer linear programming/ILP) pada intinya berkaitan dengan program-program linear dimana beberapa atau semua variable memiliki nilai-nilai integer (bulat( atau diskrit. Sebuah ILP dikatakan bersifat campuran atau murni bergantung pada apakah beberapa atau semua variabel tersebut dibatasi pada nilai-nilai integer. Walaupun beberapa algoritma telah dikembangkan untuk ILP, tidak satupun metode ini sepenuhnya andal dari sudut perhitungan, terutama sementara jumlah variabel integer meningkat. Pola program linear terdapat metode simleks sebagai metode baku 78

untuk menyelesaikan problem, namun pada program integer tidak terdapat suatu metode baku. Analisis sensitivitas adalah analisis yang dilakukan untuk mengetahui akibat/pengaruh dari perubahan yang terjadi pada parameter-parameter adalah solusi optimal yang telah dicapai. Perubahan yang dimaksud pada analisis sensitivitas adalah perubahan koefisien fungsi tujuan untuk variabel basis yang mempengaruhi solusi optimal. Pada program linear dengan metode simpleks dapat diperoleh formula untuk mengetahui rentang perubahan sehingga penyelesaian baru tetap dipertahankan. 2.

Batas Aman dalam Linear Program Integer Campuran Penyelesaian program linear integer campuran saat ini didasarkan pada pelaksanaan pada program linear yang menggunakan floating point arithmetic. Terkadang hal ini memberikan penyelesaianpenyelesaian yang salah, bahkan untuk masalahmasalah diamna koefisien dan semua komponen penyelesaian adalah integer kecil. Diperlihatkan betapa mudahnya dengan menggunakan aritmetika lingkaran dan interval, sebelum dan setelah proses program linear yang timbul dalam sebuah kerangka dalam menjamin bahwa tidak ada penyelesaian yang hilang, setidaknya untuk program-program integer campuran dimana semua variabel dapat dibatasi dengan batas-batas ukuran yang sesuai. Dalam program integer campuran oleh Wosley secara khusus digunakan untuk mencari batas-batas yang lebih rendah dalam objektif. Akan tetapi, adalah memungkinkan setelah memproses hasil perkiraan memperoleh batas-batas yang tepat untuk fungsi objektif tersebut menggunakan pembulatan terarah untuk memastikan keakuratan matematik dari setiap langkah dari proses tersebut.

Jurnal Sistem Teknik Industri Volume 6, No. 4 Oktober 2005

Bentuk standar Min cTx ……………………………(1) Kendala Ax = b, x > 0 Bentuk dualnya : Max bTy Kendala AT y < c ……………………..(2) Sekarang diandaikan bahwa y adalah sebuah pendekatan penyelesaian dari masalah dual dan r > ATy – c adalah sebuah batas atas yang tepat untuk residual AT y – c. Maka c > AT y - r, sehingga cT x > (AT y – r)T x = yT Ax – rT x = yT b – rT x Jika diandaikan batas atas yang tepat adalah : x < x Dan dituliskan r± = max (± r, 0) cTx > yTb – rT x > yT b – rT x ………….(3) 3.

Pembulatan Integer Campuran Pemotongan pembulatan integer campuran dan Gomory Cutting Plane yang dibuat dapat dihasilkan melalui pembulatan integer (Marchand & Wosley). Pembulatan integer campuran adalah sebuah teknik untuk membuat potongan-potongan - potongan yang didasarkan pada lemma berikut : n

Lemma : Andaikata s > 0, a ∈ ℜ , ∝ ∈ ℜ dan didefenisikan

⎡α ⎤ = ⎢ ⎥ ∈ 0,1 , β := (2q − 1)α + 2sq (1 − q ) s ⎣s⎦ ⎢α ⎥ ⎡α ⎤ a = s ⎢ ⎥, α : = s ⎢ ⎥ ⎣s⎦ ⎢s⎥

q :=

α

b : = a - a − q (a − a ) + a − q (a + a ) Maka 0 ≤ z ∈ Zn ⇒ a T z - α ≥ b T z + β

(4)

Bukti : Ditunjukkan dengan zL sebagai sub vector dari z yang disimbolkan dengan L. Untuk sembarang partisi dari {l, …………., n} ke dalam jumlah dua himpunan L, U : T

α : α TL Z L + α U Z U adalah sebuah bilangan

perkalian integral s. Sekarang

α := ⎣α / s ⎦ dan α = ⎡α / s ⎤

adalah

pengali integral yang sama atau berhubungan dengan s, oleh karena itu ketidaksamaan

(

] [

α ∈ α ,α .

)

α - α ≥ (1 - 2q ) α − α + 2 sq(1q )

Jadi memenuhi

(5)

Dengan menggunakan persamaan (5) dan ketidaksamaan segitiga siku-siku, maka dapat diperoleh :

(

)

aT Z − α ≥ α − α − (a − a )L Z L − a − α U ZU Y

(

T

)

≥ (1 - 2q ) α − α + 2 sq (1 − q ) − (a − a )L

(

)

T

T

- α − α U zU = b L z L + bU zU + β Dimana

b = (2 − 2q )a − a dan b = a − 2q a

{

(

Jika dimisalkan L = k α k − α k < q α k − α k

)}

dan U = { 1 : n} / L, maka dapat diperoleh bL = bL dan bU = bU 4. Penyelesaian Dua Program Integer Campuran Sebuah program integer mempunyai bentuk : Min z = cx Kendala Ax > ∝ (6) 0<x ∝, 0< x < h) →cx >z Dimana D = D1 x ………. X Dk x Rn-k Sebuah penyelesaian dari dual (7) dapat diperoleh dengan pencabangan branch and bound berikut ini. Pada setiap daun noktah pada pohon, pertidaksamaan pengganti yang diturunkan bertentangan dengan pemotongan cabang dalam hasil pada noktah. Pengganti akan menjadi kombinasi tak linear dari beberapa konstrain dan fungsi objektif yang mungkin. Sebuah klausa salah yang diartikan dari pengganti. Pada setiap noktah dari pohon and bound, himpunan konstrain original dikuatkan dengan pemotongan cabang dari bentuk xj < v atau xj > v + 1, variable refleksi telah ditetapkan sepanjang path sampai akar noktah. Relaksasi kontinu dari problem ini dibentuk dengan menggunakan pengintegralan untuk x1, ………………………xk. Problem relaksasi dapat ditulis : Min z = cx Kendala Ax > ∝, Bx> b 0<x b memuat pemotongan cabang yang dipilih. 5.

Analisis Sensitivitas pada Program Integer Campuran Teorema daulitas mengatakan bahwa jika himpunan dari variable basis feasible, maka variable basis akan optimal jika dan hanya jika penyelesaian dual yang bersankgutan adalah dual feasible. Hal ini dapat digunakan untuk menyelesaikan analisis sensitivitas yang berkaitan dengan perubahan pada 79


koefisien fungsi tujuan pada variable basis yang kontinu. Jadi perubahan ini tidak akan menganggu fisibilitas dari variable basis, sehingga penyelesaian basis saat ini tetap optimal yaitu cBV. B-1. Teorema : Untuk setiap j, 1 < j < n, Cj = cj-cB B-1 A(j) = cj cBA*(j) Bukti : Tetapkan j, 1 < j < n. Andaikan vector kolom awal b dalam teorema-3 diatas adalah A(j) dan konstanta awal z0 sama dengan cj. Kemudian, b yang dihasilkan akan berupa A*(j) dan zo* yang dihasilkan akan berupa xj*. Selanjutnya teorema-3 yang digunakan pada masalah pemrograman linear dari minimize z dengan z = -z0 + c1x1 + c2x2 + ………………….+cnxn dengan kendala AX = A(j), X > 0, berimplikasi dengan c* = cj – cBA*(j). Hasilnya adalah c* = c – cBA* = c – cBB-1A Perubahan dalam Fungsi Objektif Andaikan bahwa masalah pemrograman linear meminimumkan z = cX – z0 berada pada AX = b, X> 0, telah diselesaikan dengan table akhir yang diberikan oleh :

selanjutnya, jika q adalah positif, maka ketidaksamaan ini akan selalu dipenuhi, sehingga koefisien biaya dari variabel nonbasis dapat ditambah tanpa batasan dengan tidak mempengaruhi solusi optimal. Meskipun demikian, begitu cs dikurangi oleh jumlah yang lebih dari c*s, maka lebih banyak iterasi dari metode simpleks dapat diperlukan untuk menyelesaikan masalah tersebut. Sekarang pertimbangan kasus dimana xs adalah variable basis. Anggaplah xs adalah variable yang dipisahkan dalam baris ke-r dari table akhir. Kemudian cB dan cB keduanya hanya berbeda dari komponan ke-r, dengan komponen ke-r dari CB + q dimana q komponen yang berkoresponden dari cB. Dengan menggunakan *

c = c − c B A* , untuk j ≠ s c

6.

A* C*

B* Zo*

Andaikan bahwa X* adalah solusi layak dasar yang berhubungan dengan X* = [x1,x2, ………….xn] didefenisikan oleh :

⎧b *k , x j adalah variabel basis dalam ⎪ persamaan ke - k pada akhir ⎪ * x* j = ⎨ ⎪0, x j adalah variabel non basis ⎪ pada tabel akhir ⎩ Diandaikan bahwa biaya awal cj diubah yaitu koefisien cx ditambah dengan q, sehingga koefisien baru cs = cs + q. Satu- satunya data yang dipengaruhi oleh perubahan ini adalah baris bawah dari table akhir solusi optimal, sehingga X* masih merupakan solusi dasar yang memungkinkan. Variabel baru yang masuk dalam basis dapat ditunjukkan dalam baris akhir oleh c dan z0. Kemudian X* masih akan merupakan solusi optimal jika c > 0. Untuk menentukan c > 0, pertimbangkan dua kasus. Anggaplah terlebih dahulu bahwa xs adalah variable non basis dalam table akhir. Dengan mengetahui vector CB yang didefinisikan, tidak berubah edngan perubahan cs sehingga dari C* = c – cBB-1 A = c – cBA* Maka satu-satunya perubahan Cs dari c* akan berada dalam komponen ke-s dengan : cs = cs + q - cBA*(s) cs = c*s + q (9) oleh karena c*s > 0, maka c*s + q> 0, yaitu q > - c*s. 80

c

* j

= c j − c B A*(U ) − q.α * rj = c * j − q.ε

s

= c s − c B A*( s ) − q.α * rs

*

*

rj

= c s + q − c B A*( s ) − q

Dan

= c *s = 0 Karena

α rs* = I

dan c rs = 0 , sehingga xs adalah *

variable basis yang dipisahkan dalam baris ke-r. *

selanjutnya agar semua c j > 0 , maka q.a*rj < c*j Untuk semua j, 1 < j < n, j ≠ s Jika

α rj*

α rs* = 0 ,

maka harus dimiliki bahwa q < c*j I

Karena ini harus digunakan untuk semua

α > 0 , maka penyelesaian memenuhi q < Min {c*j * rs

I ∝*rj I 0, j ≠ s}.

α rs* = 0 ,

Demikian juga jika memenuhi q >

c*j

dimiliki q > Max 7.

I

α

{c*j

I

* rj

maka q harus

dan dengan demikian harus

∝*rj < 0,

j ≠ s}.

Metode Pemecahan Program Integer Dalam program linear, metode simpleks didasari oleh pengenalan bahwa pemecahan optimum terjadi di titik ekstrem dari ruang solusi. Hasil yang penting ini intinya mengurangi usaha pencarian pemecahan optimum dari sejumlah pemecahan yang tidak terbatas menjadi sejumlah yang terbatas. Sebaliknya Integer Linear Programming (ILP) memulai dengan sejumlah titik pemecahan yang terbatas. Tetapi sifat variable yang berbentuk integer mempersulit perancangan sebuah algoritma yang efektif untuk mencari secara langsung di antara titik integer yang layak dari ruang penyelesaian. Terdapat dua metode untuk menghasilkan batasan-batasan khusus yang akan memaksa pemecahan optimum dari masalah program linear yang dilonggarkan untuk bergerak kearah pemecahan integer yang diinginkan yaitu metode Branch and


Bound dan metode Bidang Pemotong (Gomory Cutting Plane). Metode Gomory (Cutting Plane Algorithm) Suatu prosedur sistematik untuk memperoleh solusi integer optimum terhadap pure integer programming pertama kali dikemukakan oleh R.E. Gomory pada tahun 1958. kemudian prosedur ini diperluas untuk menangani kasus yang lebih sulit, yaitu mixed integer programming. Pembentukan kendala Gomory adalah begitu penting sehingga memerlukan perhatian khusus. Secara historis, metode bidang pemotong adalah metode pertama yang diperkenalkan dalam literature OR. Oleh karena itu, maka yang disajikan dalam tulisan ini adalah bagaimana menemukan penyelesaian optimal yang integer dengan menggunakan metode algoritma bidang pemotong. Perincian algoritma fraksional pertama membahas masalah LP yang dilonggarkan dipecahkan yaitu dengan mengabaikan kondisi integer, tidak ada lagi yang perlu dilakukan. Sebaliknya batasan sekunder yang akan memaksa pemecahan bergerak kea rah pemecahan integer dikembangkan sebagai berikut. Anggaplah table-1 merupakan tabel optimal terakhir untuk program linear diketahui. Variable xi, (I = 1, 2, ……………m) mewakili variable basis dan variable wj (j = 1, ………….n) adalah variable nonbasis. Variable-variabel ini telah diatur demikian untuk kemudahan. Pertimbangkan persamaan ke-I dimana variable dasar xI dimana variable dasar xi memiliki nilai noninteger. n

j =1

n

…

1

…

0

xm

0

…

0

…

1

(16)

j =1

Batasan terakhir ini ditulis dalam bentuk : n

S i = ∑ f ij w j − fi (pemotongan fraksional) (17) j =1

Dimana Si adalah variable slack nonnegative yang berdasarkan defenisinya haruslah sebuah integer. Persamaan batasan ini mendefenisikan pemotong fraksional untuk wj = 0 dan Si = -fi yang tidak layak. Ini berarti bahwa batasan baru tersebut tidak dipenuhi oleh pemecahan yang diberikan. Metode dual simpleks dapat dipergunakan untuk ketidaklayakan ini adalah yang setara dengan memotong bidang pemecahan kea rah pemecahan integer yang optimal. Jika pemecahan baru (setelah menerapkan dual simpleks) adalah integer, maka proses iterasi berakhir. Jika tidak sebuah pemotong fraksional baru akan dikembangkan dari tabel yang dihasilkan dan metode dual simpleks diperguanakn sekali lagi untuk ketidaklayakan ini. Prosedur ini diulangi sampai pemecahan integer dicapai. Tetapi jika salah satu iterasi algoritma dual simpleks tersebut menunjukkan bahwa tidak ada pemecahan yang layak, maka masalah tersebut tidak memiliki pemecahan integer yang layak.

Dimana N = [α] adalah integer terbesar sedemikian rupa sehingga N < α. Disimpulkan bahwa 0 < fi < 1 dan 0 < fij < 1 ; yaitu fi adalah pecahan yang positif secara ketat dan fy adalah pecahan nonnegative. Jadi baris sumber menghasilkan

0

integer

n

f i = ∑ f ij w j ≤ 0

[ ]

xi

haruslah

berdasarkan pengembangannya, satu kondisi untuk memenuhi sifat integer ini menjadi

f y = α i j = ε i j (bagian pecahan dari α ij ) (13)

x1

f i = ∑ f ij w j j =1

α ij = [α i j ] = f y

0

(15)

n

Karena

dan

…

(14)

j =1

β i = [β i ] = fi fi = β i − [β i ] (bagian pecahan dari β i ) (12)

0

[ ]

wj > 0

ij

Akibat f i − ∑ f ij w j < f i < 1

Anggaplah

…

j =l

∑f

β noninteger (baris sumber)

1

j =l

n

j =1

Tabel 1. Penyelesaian optimal metode simpleks Dasar … xi … xm x1 Z 0 … 0 … 0

n

Agar semua variable xi dan wj adalah integer, maka sisi kanan dari persamaan (14) haruslah integer yang pada gilirannya menyiratkan bahwa sisi kiri harus pula integer. Dengan diketahui fij > 0 dan j > 0 untuk semua i dan j dapat disimpulkan bahwa

8.

xi = β i − ∑ α i j w j

n

fi − ∑ f if w j = xi − [β i ] + ∑ α i j w j

W1

c1

α α

… …

1 1 1 1

…

α m1

…

…

… …

Wn

j 1 j i

…

α 1n α in

β1

α mj

…

α mn

βn

wi

c1

α α

…

cn

Pemecahan βn

βi

81


9.

Analisis Sensitivitas Terhadap Koefisien Fungsi Objektif Variabel Basis. Untuk memahami prinsip-prinsip dasar dalam menjalankan analisis sensitivitas akan dijelaskan melalui suatu kasus dengan sebuah contoh tentang Stategis Bauran Keuangan.

Maks. Kendala

8x1+6,5x2+20x3+17x4

12x1+12x2+25x3+25x4<2500 x1+x2+x3 +2x4<150 50x1 + 100x3 <3000 50x2 + 1004 <10000 x1 + x2 > 50 x3 + x4 > 25 -8x1+45x2-20x3+86x4 < 3000 x1,x2,x3x4 > 0, dan x4 integer Dengan menggunakan metode simpleks penyelesaian optimalnya diperoleh setelah

Dari tabel-3 menunjukkan bahwa Zj – Cj > 0, maka iterasi selesai dan penyelesaian optimal telah dicapai dengan nilai x1 = 50, x3 = 5, x4 = 40,698, x5= 757,558, x6 = 8,605, x8 = 5930,233, x10 = 20,698, x2 = x7 = x9 = x11 = 0 dan nilai fungsi objektif maks z = 1191,860. 10. Penyelesaian Dengan Gomory Cutting Plane Penyelesaian optimal yang diperoleh pada tabel-3 di atas memperlihatkan bahwa belum memenuhi persyaratan awal terhadap variable keputusan x4 yang harus integer. Dalam hal ini variable keputusan x4 yang harus dipilih untuk memperoleh pencapaian 82

melakukan perhitunga pada iterasi 6 yang dapat dilihat pada tabel 2 dengan langkah awal dikonversi pada bentuk standar. Kendala 5 dan 6 yang pembatasan > dikalikan dengan (-1), bentuk kanoniknya diperlihatkan pada tabel-2. Dengan memperhatikan kembali tabel-2 bahwa variable-variabel awalnya tidak memberikan penyelesaian awal yang feasible (x9 dan x10 berharga negative) tetapi koefisien persamaan z sudah memenuhi kondisi optimalitas, maka persoalan tersebut harus diselesaikan dengan menggunakan metode dual simpleks. Pada iterasi pertama x9 (=-50) sebagai leaving variable, sedangkan entering variable dipilih berdasarkan rasio terkecil antara baris z dengan baris x9 yaitu min ⎧⎨−8, −6,5⎫⎬ = 6,5 ⎩−1 −1 ⎭

Dengan demikian x2 terpilih sebagai entering variable.

penyelesaian integer optimum. Jadi persamaan x4 pada tabel-3 terpilih untuk menurunkan persamaan pembatas baru. n

xi = β i − ∑ α i j w j j =1

x4 + 0,5 x2 + 0,002x7 + 0,023 x9 + 0,012 x11 = 40,698 x4 + 0,5 x2 + 0,002 x7 + 0,023 x9 + 0,012 x11 = 40 + 0,698 Persamaan pembatas barunya adalah : n

S i = ∑ f ij w j − f i j =1

S1 − 0,5 x 2 − 0,002 x7 − 0,023x9 − 0,012 x11 = −0,698

(18)


Persamaan (18) ini dimasukkan ke dalam tabel3, sehingga diperoleh tabel baru yaitu tabel-4. baris S1 pada tabel-4, dalam hal ini pembatas baru tidak memenuhi penyelesaian semula sehingga untuk mengatasi ketidaklayakan ini dapat digunakan metode dual simpleks, yang pada dasarnya sama dengan memotong ruas penyelesaian hingga diperoleh penyelesaian integer optimum. Dengan metode dual simpleks diperoleh tabel-5, yang menunjukkan bahwa penyelesaian integer optimum telah dicapai dengan x1 = 48,604, x2 = 1,396, x3 = 5,698 = 40 dan maks z = 1191,86. 11. Menentukan interval Koefisien cj Fungsi Tujuan Selanjutnya analisis sensitivitas dilakukan pada penyelesaian optimal yang diperoleh pada tabel-5 untuk mengetahui akibat atau pengaruh dari

perubahan yang terjadi pada koefisien fungsi tujuan untuk variable basis kontinu terhadap penyelesaian optimal yang telah dicapai. Untuk memahaminya pembahasan ini bertitik tolak pada penyelesaian tabel-5. Dapat diketahui bahwa perubahan nilai c dari cj menjadi (cj + Δ) tidak mengubah harga B-1 dan b. Karena itu, ruas kanan untuk tabel BV, yaitu B-1b, tidak akan berubah sehingga BV tetap layak. Mengubah nilai cj koefisien fungsi tujuan variable basis artinya mengubah cBV sehingga beberapa koefisien pada baris z dari variable non basis pada tabel optimal akan berubah. Misalkan yang dirubah adalah koefisin c1 yaitu dari 8 menjadi (8 + Δ), maka cBV yang baru adalah:

83


a.

c*1 = cBV. B-1 . α1 – c1 = [ 0 0 (0,234 – 0,004Δ) 0 (2,3911,046Δ) 0 (0,204-0,024Δ) 2Δ] 0 1 0 0 0 0 0 ]T -0 = 0,234 – 0,004 Δ Karena c*1 > 0, maka -0,004 Δ > - 0,234 → Δ < 58,5

b.

c*9 = cBV . B-1 . α9 - c9 = [ 0 0 (0,234 – 0,004 Δ) 0 (2,391-1,046Δ) 0 (0,204-0,024Δ) 2Δ] [ 0 0 0 0 1 0 0 0 ]T – 0 = 2,391 - 1,046 Δ Karena c*9 > 0, maka -1,046 Δ > -2,391 → Δ 2,286

c.

c*11 = cBV . B-1 . α11 - c11 = [0 0 (0,234 – 0,004 Δ) 0 (2,391-1,046Δ) 0 (0,204-0,024Δ) 2Δ] [ 0 0 0 0 0 0 1 0]T – 0 = 0,204 – 0,024 Δ Karena c*11 > 0, maka -0,024 Δ > -0,204 → Δ < 8,5

d.

c*si = cBV. B-1 . αsi – csi = [ 0 0 (0,234-0,004Δ) 0 (2,391-1,046Δ) 0 (0,204-0,02Δ) 2Δ] [0 0 0 0 0 0 0 1]T – 0 =2Δ Karena c*si > 0, maka 2 Δ > 0

Dari harga Δ di atas, interval yang memenuhi keempat pertidaksamaan adalah 0 < Δ < 2,286. Artinya c1 turun sebesar 0 atau naik hingga 2,286, maka dapat disimpulkan bahwa penyelesaian saat ini tetap optimal jika nilai c1 berada pada interval 8 < c1 < 10,286. Nilai z tetap optimal, namun tentu saja akan besarnya berubah dengan penentuan nilai c1 yang akan dipilih. Dengan cara yang sama apabila dilakukan perobahan pada koefisien c2 yaitu dari 6,5 menjadi (6,5 + Δ), dan perubahan pada koefisien c3 yaitu dari 20 menjadi (20 + Δ), maka diperoleh nilai c2 berada pada interval -2 < c3 < 6,5 dan nilai c3 berada pada interval 15,428 < c3 < 20. 12. Kesimpulan Pendekatan yang dilakukan dalam teknik cutting plane adalah dengan membuat pembatas tambahan ang memotong ruang feasible dari program linear relaksasi sehingga dapat mengeliminasi penyelesaian yang tidak integer. Keberhasilan teknik cutting plane sangat terbatas, bergantung pada struktur persoalan yang dihadapi. Pembatasan atau pemotongan ruang penyelesaian harus berada dalam set konveks. Analisis sensitivitas yang dilakukan untuk mengetahui akibat atau pengaruh dari perubahan yang terjadi pada koefisien variable basis (BV) cj terhadap penyelesaian optimal yang telah dicapai akan tetap mempunyai penyelesaian optimal. Penentuan besarnya perubahan nilai koefesien fungsi tujuan c dari nilai cj menjadi (cj + q) dapat diperoleh 84

dalam batas-batas yang ditetapkan oleh semua variabel nonbasis. Batas atas atau bawah nilai q ditentukan dengan formula c*nbv = cBV. B-1 . αNBV cNBV untuk variable nonbasis pada penyelesaian optimal Metode Simpleks dan Metode Gomory. DAFTAR PUSTAKA Anthony V. Viacco, Introduction to Sensitivity and Stability Analysis in Nonlinear Programming, Mathematics in Science And Engineering. Volume 165, New York, 1983. Dakin, R. J., ‘A Treee Search Algorithm for Mixed Integer Programming Problems, Computer Journal, 8 (1965), pp. 250-255. Dantzig, G. B.’ Linear Programming and Extension, Princeton University Press, Princeton, N.Y., 1963. Dawande M. W. dan Hooker J.N, Inference Based Sensitivity Analysis for Mixed Integer/Linear Programming, New York, Juli Aug, 2000. Garfinkel, R.S., and G.L. Nemhauser, Integer Programming, John Wiley and Sons, New York, 1972. Gomory, R. E., An Algorith for Integer Solution to Linear Programs, in R. Graves and P. Wolfe, Recent in Mathematical Programming, McGraw-Hill Book Co, New York, 1963. Hamdy A. Taha, Operation Research n Introduction, Third Edition, Macmillan Publishing Co, Inc, New York, 1982 Kantorovich, Leningrad State University Publisher (1936), Translated as Mathematical Methods in the Organization and Planning of Produkction’ Management Science, 6 (1960), 366-422. Kim. S., and Cho, S, A Shadow Price in Integer Programming for Management Decision, European Journal of Operational Research, 37 (1988), 323-335. Koopmans, T. C., Concepts of Optimality and Their Uses, Mathematical Programming, 11 (1976), 212-228. Leunberger, D. G, Linear and Nonlinear Programming, Second Edition, Eddion Wesley Publishing Company, Staford University, California, 1984. Paul R. Thie, An Introduction to Linear Programming and Game Theory, Departement of Mathematics Boston College, 1979. Philips, D. T. A. Ravidran and J. Solberg, Operation Research : Principle and Practise, New York, 1976. Rad, S.S, Optimization, Theory and Applications, New Delhi, Wiley Eastern Limited, 1978

ANALYSIS SENSITIVITAS PADA PROGRAM INTEGER CAMPURAN

Recommend Documents