16 BAB 2 LANDASAN TEORI
Pada bab ini akan dibahas beberapa konsep-konsep dasar yang berhubungan dan mendukung penentuan solusi optimal masalah program linier parametrik. Dengan demikian, akan mempermudah dalam hal pembahasan pada bab berikutnya.
2.1
Program Linier
Program linier merupakan suatu metode optimisasi yang dapat dipakai untuk penyelesaian masalah yang muncul dengan fungsi tujuan dan kendala masalah dalam bentuk fungsi linier dari variabel-variabel keputusannya.
Kendala masalah program linier mungkin dalam bentuk kesamaan atau ketidaksamaan. Bentuk umum masalah program linier dapat dinyatakan dalam bentuk standar berikut.
1. Dalam bentuk Skalar Minimum z = c1 x1 + c2 x2 + . . . + cn xn Dengan kendala a11 x1 + a12 x2 + . . . + a1n xn = b1 a21 x1 + a22 x2 + . . . + a2 n xn = b2 am1 x1 + am 2 x2 + . . . + amn xn = bm atau dalam bentuk n
Minimum z = ∑ c j x j j =1
Dengan kendala n
∑a x j =1
ij
j
= bi , i = 1, 2 , . . . , m
dan x j ≥ 0
j = 1, 2 , . . . , n
17 2. Dalam bentuk matrik Minimum z = cT x Dengan kendala Ax = b x≥0
c1 b1 x1 c b x 2 2 2 . . . x= ,b= ,c= . . . . . . cn bm xn
di mana a11 a12 a 21 a22 . . A= . . . . am1 am 2
. .
. .
. .
.
.
.
a1n a2 n . . . amn
Karakteristik masalah program linier dapat dibedakan dalam bentuk standar yaitu :
1. Fungsi tujuan adalah jenis meminimumkan. 2. Semua kendala berbentuk persamaan. 3. Semua variabel keputusan nonnegatif. 4. Semua nilai kuantitas batasan nonnegatif.
Setiap masalah program linier dapat diletakkan ke dalam bentuk standar dengan menggunakan transformasi berikut :
1. Pemaksimuman suatu fungsi z adalah ekivalen dengan peminimuman dari negatif fungsi yang sama dan sebaliknya. Contoh : Fungsi tujuan Minimum z = c1 x1 + c2 x2 + . . . + cn xn Ekivalen kepada maksimum z ' = − z = − c1 x1 − c2 x2 − . . . − cn xn
18 2. Jika suatu kendala muncul dalam bentuk ketidaksamaan “ lebih kecil atau sama dengan “ (≤ ) seperti a k1 x1 + a k 2 x 2 + a kn x n ≤ bk maka itu dapat diubah ke dalam bentuk kesamaan dengan menambahkan satu variabel pengurang tidak negatif sebagai berikut : a k1 x1 + a k 2 x 2 + . . . + a kn x n + x n +1 = bk Sama halnya jika kendala muncul dalam bentuk ketidaksamaan “ lebih besar atau sama dengan “ (≥ ) seperti a k1 x1 + a k 2 x 2 + a kn x n ≥ bk maka itu dapat diubah ke dalam bentuk kesamaan dengan mengurangkan suatu variabel seperti ak1 x1 + ak 2 x2 + . . . + a kn xn − xn +1 = bk dimana xn+1 adalah variabel nonnegatif yang dikenal sebagai variabel penambah. Sisi kanan suatu persamaan dapat selalu dibuat tidak negatif dengan mengalikan kedua sisi dengan –1 dan arah pertidaksamaan dibalik jika kedua sisi dikalikan –1.
3. Variabel Sebagian atau semua variabel dikatakan unrestricted jika mereka dapat memiliki nilai negatif atau positif. Variabel unrestricted dapat diekspresikan dalam dua variabel tidak negatif dengan menggunakan subsitusi
x j = x ' j − x '' Di mana x j = Variabel unrestricted dan x ' j , x" ≥ 0
Beberapa terminologi yang digunakan dalam program linier dan beberapa teorema penting yang berhubungan dengan masalah ini adalah sebagai berikut :
1. Himpunan Konvex, merupakan suatu koleksi dari titik-titik sedemikian hingga jika x1 dan x2 merupakan setiap dua titik dalam koleksi, maka gabungan segmen garis kedua titik-titik tersebut juga berada dalam koleksi.
19 Jika S menyatakan himpunan konvex, maka S dapat didefinisikan secara matematika sebagai berikut : Jika x1 , x 2 ∈ S , maka x ∈ S di mana x = αx1 + (1 − α )x 2 ,
0 ≤α ≤1
2. Vertek ( titik ekstrim ), merupakan suatu titik pada himpunan konvex yang tidak terletak pada gabungan segmen garis kedua titik lain pada himpunan.
3. Solusi layak, merupakan setiap solusi dalam masalah program linier yang memiliki kendala-kendala Ax = b dan x ≥ 0 . 4. Solusi basis, merupakan suatu solusi di mana ( n-m ) variabel himpunan sama dengan nol. Solusi basis dapat diperoleh dengan membuat ( n-m ) variabel sama dengan nol dan menyelesaikan persamaan dengan simultan.
5. Basis, merupakan koleksi dari variabel-variabel himpunan yang tidak sama dengan nol untuk memperoleh solusi basis.
6. Solusi layak basis, adalah solusi basis yang memenuhi kondisi nonnegatif dari persamaan xj ≥ 0,
7. Solusi layak basis nondegenerasi, adalah suatu solusi layak basis yang secara tepat mempunyai m nilai xi yang positif.
8. Solusi optimal, adalah suatu solusi layak yang mengoptimalkan fungsi tujuan.
9. Solusi basis optimal, merupakan suatu solusi layak basis yang mana fungsi tujuannya adalah optimal ( terbaik ).
20 Teorema 2.1.1 Daerah layak S dari suatu masalah program linier adalah konvex. Bukti :Daerah layak S dari suatu masalah program linier standar didefinisikan sebagai S = {x Ax = b, x ≥ 0}. Misalkan titik x1 dan x2 termasuk himpunan layak S sedemikian hingga
Ax1 = b , x1 ≥ 0
(1)
Ax2 = b , x 2 ≥ 0
(2)
Atau dengan mengalikan persamaan (1) dengan λ dan persamaan (2) dengan (1- λ ) dan menjumlahkan mereka ,maka diperoleh A [λx1 + (1 − λ ) x 2 ]= λb +(1- λ ) b = b
Axλ = b Di mana
xλ = λ x1 + (1- λ ) x2 . Jadi titik xλ memenuhi kendala dan jika
0 ≤ λ ≤ 1,
xλ ≥ 0 . Oleh karena itu teorema terbukti.
Teorema 2.1.2 Suatu titik
x
{x : Ax = b, x ≥ 0} jika dan hanya jika
adalah suatu titik ekstrim dari himpunan
x adalah solusi layak basis.
Bukti : ⇐ Akan diperlihatkan jika x adalah solusi layak basis maka x juga merupakan titik ekstrim. Pertama-tama, diasumsikan n − m variabel akhir dari x
x x adalah nonbasis sehingga x = B = B . x N 0 Misalkan B menjadi basis invertibel sesuai untuk x B . Dengan kontradiksi akan dibuktikan : Jika x bukan suatu titik ekstrim maka terdapat 2 (dua) titik layak yang berbeda, y dan z memenuhi x = λy + (1 − λ )z dengan 0 ≤ λ ≤ 1 . Pada basis yang
y z sama y dan z dapat ditulis y = B dan z = B . Baik y dan z adalah layak, y z N N sehingga y N ≥ 0 dan z N ≥ 0 . Karena 0 = x N = λy N + (1 − λ )z N dan 0 ≤ λ ≤ 1 , semua bagian pada sisi kanan adalah nonnegatif, dan karena itu dapat disimpulkan
21 y N = z N = 0 . Juga karena x, y, z adalah layak, mereka memenuhi kendala persamaan masalah sehingga Bx B = By B = Bz B = b . Karena B adalah invertibel, x B = y B = z B , kontradiksi dengan asumsi bahwa y dan z adalah titik yang berbeda dari x . Oleh karena itu, x adalah titik ekstrim. ⇒ Akan diperlihatkan jika x adalah titik ekstrim maka x adalah solusi layak basis. Ini juga akan dibuktikan dengan kontradiksi. Suatu titik ekstrim x harus menjadi layak sedemikian hingga Ax = b dan x ≥ 0 . Dengan mengurutkan variabel sehingga
x variabel nol terakhir dapat ditulis sebagai x = B di mana x N = 0 dan x B ≥ 0 . x N Dapat ditulis A = (B, N ) di mana B dan N adalah koefisien yang sesuai untuk x B dan x N , secara berturut-turut. ( B dapat diasumsikan sebagai matriks bujur sangkar ). Jika kolom B bebas linier maka x adalah solusi layak basis dan tidak perlu dibuktikan. Jadi, dianggap kolom B adalah bergantung linier dan dikonstruksikan titik layak y dan z memenuhi x = 1 y + 1 z , dengan memperlihatkan itu, x tidak 2 2 dapat menjadi titik ekstrim. Misalkan Bi menjadi kolom ke i dari B . Jika kolom B bergantung linier maka terdapat bilangan rill p1 ,..., p k yang tidak semuanya nol, sedemikian hingga
p = ( p1 ,..., p k )
T
B1 p1 + B2 p 2 + ... + Bk p k = 0 . Jika
p
didefinisikan sebagai
maka persamaan di atas dapat ditulis sebagai B p = 0 . Catatan,
B (xB ± λ p ) = BxB ± λB p = BxB = b untuk semua nilai λ . Karena x B > 0 untuk setiap nilai positif terkecil ε
akan dimiliki x B + εp > 0 dan x B − εp > 0 . Misalkan
x B + εp x − εp dan z = B . Kemudian diperoleh x = 1 y + 1 z yang mana y = x x 2 2 N N mengekspresikan x sebagai kombinasi dari dua titik berbeda dalam himpunan konvex, ini tidak dapat terjadi atau kontradiksi dengan asumsi di atas karena x adalah suatu titik ekstrim. Jadi B adalah bebas linier dan oleh karena itu x adalah suatu solusi layak basis.
22 2.2 Solusi Sistem Persamaan Linier Melalui Operasi Pivot
Suatu sistem persamaan linier merupakan himpunan terbatas persamaan linier di mana tiap-tiap persamaan memiliki variabel yang sama. Suatu solusi sistem persamaan linier adalah suatu vektor yang secara simultan adalah solusi untuk tiap-tiap persamaan dalam sistem. Himpunan solusi sistem persamaan linier adalah himpunan dari semua solusi sistem.
Misalkan ada n buah sistem persamaan berikut : a11 x1 + a12 x 2 + ... + a1n = b1
(E1)
a 21 x1 + a 22 x 2 + ... + a 2 n = b2
(E2)
(3)
a n1 x1 + a n 2 x 2 + ... + a1n = bn
(En)
Andaikan himpunan persamaan ini memiliki solusi khusus, satu cara penyelesaian sistem persamaan linier melalui pereduksian persamaan ke suatu bentuk yang diketahui seperti bentuk standar. Dari aljabar linier dasar dapat diketahui bahwa solusi dari persamaan (3) tidak akan berubah menurut operasi berikut :
1. Setiap persamaan Er digantikan oleh persamaan kEr di mana k merupakan suatu konstanta bukan nol, dan 2. Setiap persamaan Er digantikan oleh persamaan Er + kEs di mana Es merupakan persamaan lain dari sistem.
Dengan penggunaan operasi dasar ini, sistem persamaan (3) dapat direduksi ke suatu bentuk ekivalen yang sesuai seperti berikut. Pertama beberapa variabel xi dipilih dan dicoba dieliminasi dari semua persamaan kecuali persamaan ke j ( di mana a ji tidak nol ). Ini dapat diselesaikan dengan membagi persamaan ke j dengan a ji dan mengurangi
hasil
kelipatan
k = 1,2,..., k − 1, k + 1,..., n.
aki
dari
tiap-tiap
persamaan
lain,
23 Hasil sistem persamaan dapat ditulis sebagai berikut :
a11' x1 + a12' x 2 + ... + a1' ,i −1 xi −1 + 0.xi + a1' ,i +1 xi +1 + ... + a1' n x n = b1' ' ' a 21 x1 + a 22 x 2 + ... + a 2' ,i −1 xi −1 + 0.xi + a 2' ,i +1 xi +1 + ... + a 2' n x n = b2'
a 'j −1,1 x1 + a 'j −1, 2 x 2 + ... + a 'j −1,i −1 xi −1 + 0.xi + a 'j −1,i +1 xi +1 + ... + a 'j −1,n x n = b 'j −1
(4)
a 'j1 x1 + a 'j 2 x 2 + ... + a 'j ,i −1 xi −1 + 1.xi + a 'j ,i +1 xi +1 + ... + a 'jn x n = b 'j
a 'j +1,1 x1 + a 'j +1, 2 x 2 + ... + a 'j +1,i −1 xi −1 + 0.xi + a 'j +1,i +1 xi +1 + ... + a 'j +1,n x n = b 'j +1 ' a n' 1 x1 + a n' 2 x 2 + ... + a n' ,i −1 xi −1 + 0.xi + a n' ,i +1 xi +1 + ... + a nn x n = bn'
Di mana dari keterangan menunjukkan bahwa aij' dan b 'j diubah dari sistem asli. Operasi pengeliminasian suatu variabel khusus ini dari semua persamaan, kecuali dari satu persamaan disebut operasi pivot. Sistem persamaan (4) dihasilkan oleh operasi pivot yang secara tepat memiliki solusi yang sama seperti himpunan asli dari persamaan (3), yaitu x yang memenuhi persamaan (3) juga memenuhi persamaan (4) dan sebaliknya.
Selanjutnya, jika persamaan (4) diambil dan dilakukan suatu operasi pivot yang baru dengan pengeliminasian x s , s ≠ i , pada seluruh persamaan kecuali persamaan ke t , t ≠ j , nol atau 1 pada kolom ke i tidak akan diganggu. Operasi pivot ini dapat diulang tiap kali dengan penggunaan suatu variabel dari persamaan yang berbeda hingga sistem persamaan (4) tereduksi ke bentuk :
1.x1 + 0.x 2 + 0.x3 + ... + 0.x n = b1" 0.x1 + 1.x 2 + 0.x3 + ... + 0.x n = b2"
0.x1 + 0.x 2 + 1.x3 + ... + 0.x n = b3"
0.x1 + 0.x 2 + 0.x3 + ... + 1.x n = bn"
(5)
24 Sistem dari persamaan (5) ini dikatakan berada dalam bentuk standar dan telah diperoleh setelah mengadakan n operasi pivot. Dari bentuk standar, vektor solusi dapat diperoleh sebagai xi = bi"
, i = 1,2,..., n
(6)
karena himpunan persamaan (5) telah diperoleh dari persamaan (4) hanya melalui operasi dasar. Sistem persamaan (5) ekivalen dengan sistem persamaan (3). Jadi sistem yang diberikan pada persamaan (6) merupakan solusi yang diinginkan untuk persamaan (3).
Sebelumnya, sistem persamaan dalam bentuk sistem kuadrat, yang terdiri dari n buah variabel dan persamaan. Sistem tersebut memiliki vektor solusi sebagai xi = bi" , i = 1,2,..., n . Sekarang sistem terdiri dari m persamaan dan n variabel dengan n ≥ m . Untuk memperoleh solusinya, maka diandaikan sistem persamaan ini
konsisten sehingga sedikitnya memiliki satu solusi. a11 x1 + a12 x 2 + ... + a1n = b1 a 21 x1 + a 22 x 2 + ... + a 2 n = b2
(7)
a m1 x1 + a m 2 x 2 + ... + a mn = bm Jika operasi pivot berkenaan dengan setiap variabel m
dilakukan, katakan
x1 , x 2 ,..., x m diubah, himpunan hasil persamaan dapat ditulis sebagai berikut :
Sistem Kanonik dengan Variabel Khusus x1 , x 2 ,..., x m
1.x1 + 0.x 2 + ... + 0.x m + a1",m +1 x m +1 + ... + a1"n x n = b1" 0.x1 + 1.x 2 + ... + 0.x m + a 2" ,m +1 x m +1 + ... + a 2" n x n = b2"
(8)
" 0.x1 + 0.x 2 + ... + 1.x m + a m" ,m +1 x m +1 + ... + a mn x n = bm"
variabel pivot
variabel bukan pivot
konstanta
25 Satu solusi khusus yang dapat selalu diambil dari persamaan (8) adalah xi = bi"
, i = 1,2,..., m
xi = 0
, i = m + 1, m + 2,..., n
(9)
Solusi ini disebut suatu solusi basis karena vektor solusi berada tidak lebih dari m buah faktor tidak nol. Variabel pivot xi , i = 1,2,..., m disebut variabel basis
dan
variabel xi lainnya, i = m + 1, m + 2,..., n disebut variabel nonbasis. Tentu ini bukan hanya solusi, tapi itu adalah salah satu solusi termudah yang dapat diambil dari persamaan (8), itu memenuhi x j ≥ 0, j = 1,2,..., n n
∑a j =1
ij
dan memenuhi persamaan
x j = bi , i = 1,2,..., m . Oleh karena itu, solusi dapat disebut suatu solusi layak
basis.
Ada kemungkinan untuk memperoleh solusi basis lainnya dari sistem standar persamaan (8). Suatu operasi pivot tambahan dapat dilakukan pada sistem setelah sistem dalam bentuk standar, menggunakan a "pq ( bukan nol ) sebagai faktor pivot, q > m , dan menggunakan setiap baris p ( di antara 1,2,..., m ). Sistem baru akan
masih berada dalam bentuk standar, tapi dengan x sebagai variabel pivot pengganti q x p . Variabal x p yang merupakan variabel basis pada bentuk standar asli, tidak akan
lama menjadi variabel basis pada bentuk standar baru. Sistem standar baru ini mempunyai suatu solusi basis baru ( yang mana dapat menjadi layak atau tidak layak ) sama halnya pada persamaan (9). Nilai dari semua variabel basis dapat berubah, secara umum, ketika satu solusi basis bergerak ke solusi basis lainnya hanya satu variabel nol ( yang mana nonbasis pada bentuk standar asli ) menjadi bukan nol ( yang menjadi basis dalam sistem standar baru ) dan sebaliknya.
Dari keterangan di atas dapat dilihat bagaimana solusi basis berpindah ke solusi basis terdekat dengan operasi pivot. Jadi, satu cara untuk menemukan solusi optimal dari masalah program linier yang diberikan adalah dengan membangkitkan semua solusi dan memilih satu yang layak dan sesuai untuk nilai optimal fungsi tujuan. Hal inilah yang nantinya menjadi dasar penyelesaian masalah program linier dengan menggunakan metode simplex.
26 2.3 Metode Simplex
Metode simplex pertama kali dikembangkan oleh George B. Dantzig pada tahun 1947. Metode ini telah terbukti efisien untuk memecahkan persoalan program linier dalam skala besar. Metode simplex adalah suatu prosedur aljabar di mana setiap iterasi melibatkan pemecahan suatu sistem persamaan untuk mendapatkan pemecahan baru dan untuk pengujian keoptimalan. Hal ini didasari dari penyelesaian sistem persamaan linier secara umum. Metode simplex sesungguhnya merupakan suatu algoritma, di mana algoritma simplex menguji secara berurutan himpunan penyelesaian layak basis hingga diperoleh penyelesaian optimal.
Titik awal algoritma simplex selalu dimulai dengan suatu himpunan persamaan yang mencakup fungsi tujuan bersama-sama kendala masalah dalam bentuk standar. Jadi, tujuan algoritma simplex adalah menemukan vektor x ≥ 0 yang meminimumkan fungsi z dan memenuhi persamaan-persamaan :
1.x1 + 0.x 2 + ... + 0.x m + a1",m +1 x m +1 + ... + a1"n x n = b1"
0.x1 + 1.x 2 + ... + 0.x m + a 2" ,m +1 x m +1 + ... + a 2" n x n = b2"
(10)
" x n = bm" 0.x1 + 0.x 2 + ... + 1.x m + a m" ,m +1 x m +1 + ... + a mn " 0.x1 + 0.x 2 + ... + 0.x m − z + c m" +1 x m +1 + ... + c mn x n = − z 0"
di mana aij , c j , bi dan z 0 adalah konstanta, − z dinyatakan sebagai suatu variabel dasar dalam bentuk standar dari persamaan (10), solusi dasar yang dengan mudah ditarik dari persamaan (10) adalah
xi = bi"
, i = 1,2,..., m
z = z 0"
xi = 0
(11) , i = m + 1, m + 2,..., n
27 Jika solusi basis ini layak, nilai xi , i = 1,2,..., n adalah nonnegatif dan karena bi" ≥ 0, i = 1,2,..., m
(12)
Setelah ditemukan suatu solusi layak basis, maka akan diuji apakah solusi layak tersebut merupakan solusi optimal. Dengan melihat c "j , j = 1,2,..., n , solusi layak basis dapat dinyatakan optimal atau tidak. Teorema berikut menyediakan suatu pengertian dari pengidentifikasian titik optimal.
Teorema 2.4.1 Suatu solusi basis yang layak adalah suatu solusi optimal dengan suatu nilai fungsi tujuan minimum z 0" jika semua harga koefisien c "j , j = m + 1, m + 2,..., n pada persamaan (10) nonnegatif.
Bukti : Dari baris akhir persamaan (10), dapat ditulis
z 0" +
n
∑c x
i = m +1
" i i
=z
(13)
Satu-satunya cara setiap variabel x m +1 , x m + 2 ,..., n dapat diubah menjadi positif adalah dengan membuat nilai mereka sama dengan nol dan dibatasi menjadi nonnegatif. Tapi jika ci" > 0
untuk i = m + 1, m + 2,..., n , maka kenaikkan setiap xi tidak dapat
menurunkn nilai dari fungsi tujuan z . Karena tidak berubah pada variabel nonbasis, untuk dapat menyebabkan z menurun, maka solusi yang dihadirkan harus menjadi optimal dengan nilai optimal z sama dengan z 0" .
Jadi, sebagai suatu kesimpulan, suatu solusi layak basis dapat disebut sebagai solusi layak optimal khusus jika
c "j > 0
untuk semua variabel nonbasis
x j , j = m + 1, m + 2,..., n .
Jika setelah pengujian keoptimalan, arus solusi layak ditemukan tidak optimal, suatu perbaikan solusi basis diperoleh dari penyajian bentuk standar sebagai berikut.
28 Dari baris akhir persamaan (10), fungsi tujuan dapat ditulis sebagai berikut :
m
z = z + ∑c x + " 0
i =1
" i i
n
∑c
j = m +1
" j
xj
(14)
= z 0" untuk solusi yang diberikan oleh persamaan (11)
Jika sedikitnya satu c "j negatif, nilai dari z dapat direduksi dengan pembuatan x j > 0 yang sesuai. Dengan kata lain, variabel nonbasis x j yang mana harga koefisien c "j negatif, dibuat menjadi suatu variabel basis untuk mereduksi nilai fungsi tujuan. Pada operasi pivot, satu dari variabel basis akan menjadi variabel nonbasis, dan karena itu nilai dari variabel basis yang baru diatur untuk menghasilkan nilai z yang lebih kecil dari z 0" . Jika di sana terdapat lebih dari satu c "j < 0 , indeks s dari variabel nonbasis x s yang mana dibuat basis dipilih sedemikian hingga c s" = minimum c "j < 0
(15)
Jika terdapat lebih dari satu c "j yang mempunyai nilai minimum sama, maka salah satu dari mereka dipilih sebagai c s" secara sembarang.
Setelah diputuskan variabel x s menjadi variabel basis, nilainya dari nilai nol sekarang ini dinaikkan dan diperiksa pengaruhnya pada arus variabel baru. Oleh persamaan (10), ini dihubungkan sebagai
x1 = b1" − a1"s x s , b1" ≥ 0 x 2 = b2" − a 2" s x s , b2" ≥ 0 s " x m = bm − a m x s , bm ≥ 0
(16)
z = z 0" + c s" x s , c s" < 0
(17)
Karena c s" < 0 , persamaan (17) menganjurkan bahwa nilai x s seharusnya menjadi lebih besar kemungkinannya untuk mereduksi nilai z sebanyak mungkin. Akan tetapi, pada proses kenaikan nilai x s , beberapa variabel xi (i = 1,2,..., m ) pada
29 persamaan
(16)
dapat
menjadi negatif.
Itu terjadi jika semua
koefisien
ais" ≤ 0, i = 1,2,..., m , maka xs dapat dibuat terbatas besarnya tanpa pembuatan setiap
xi < 0, i = 1,2,..., m . Dalam sebuah contoh kasus, nilai minimum z adalah minus tak terbatas dan masalah program linier dikatakan memiliki solusi tidak terbatas.
Di sisi lain, jika sedikitnya satu ais" positif, nilai maksimum x s dapat diambil tanpa pembuatan xi negatif. Jika di sana ada lebih dari satu ais" > 0 , nilai terbesar x s*
b" yaitu x s dapat diambil dari pemberian nilai minimum perbandingan i" a is ais" > 0 . Jadi, x s" =
bi" br" " imum min = = a ais" >.0 a rs" is
.
yang mana (18)
Kemudian r dipilih secara sembarang dalam kasus seri, asumsikan semua bi" > 0 . Jika setiap bi" yang mana ais" > 0 adalah nol pada persamaan (16) maka x s tidak dapat dinaikkan oleh jumlah berapapun, seperti suatu solusi disebut suatu solusi degenerasi. Pada kasus solusi basis yang layak nondegenerasi, suatu solusi layak basis baru dapat dikonstruksikan dengan suatu nilai yang lebih rendah dari fungsi tujuan sebagai berikut.
Dengan pensubstitusian nilai x s* yang diberikan oleh persamaan (16) dan (17) diperoleh :
xi = bi" − ais" x s* ≥ 0 , i = 1,2, , m dan i ≠ r . xr = 0 x j = 0, j = m + 1, m + 2, , n dan j ≠ s
(19)
z = z 0" + c s" x s* ≤ z 0"
(20)
x s = x s*
yang mana dengan cepat dapat dilihat untuk menjadi suatu solusi layak yang berbeda dari sebelumnya. Karena ais" > 0 pada persamaan (18), suatu operasi pivot tunggal pada elemen ais" dalam sistem persamaan (10) akan memimpin ke suatu bentuk
30 standar baru yang mana solusi basis dari (19) dapat dengan mudah diperoleh. Juga persamaan (20) menunjukkan bahwa solusi layak basis ini sesuai untuk nilai fungsi tujuan yang lebih rendah dibandingkan persamaan (11). Solusi layak basis ini dapat lagi diperiksa keoptimalannya dengan melihat apakah semua ci" > 0 pada bentuk standar baru. Jika solusi tidak optimal, maka prosedur keseluruhan harus diulangi, prosedur bergerak ke solusi basis lainnya dari satu solusi layak basis sekarang ini. Pada algoritma simplex, prosedur ini diulangi dalam suatu cara iteratif hingga algoritma menemukan salah satu hal berikut : 1. Suatu kelas dari solusi layak optimal yang mana z → −∞ atau 2. Suatu solusi layak basis optimal dengan semua ci" ≥ 0 , i = 1,2, , n
Karena hanya ada beberapa cara yang terbatas untuk memilih suatu himpunan m variabel basis yang keluar dari n variabel, proses iteratif algoritma simplex akan berakhir pada beberapa putaran yang terbatas.
Langkah-langkah metode simplex juga dapat diturunkan dalam bentuk matriks, tepatnya dengan menggunakan invers matriks. Suatu formula umum untuk langkah- langkah metode simplex dalam bentuk vektor matriks. Anggap bahwa masalah mempunyai n variabel dan m persamaan kendala yang bebas linier. Minimum z = c T x Dengan kendala :
Ax = b x≥0
x Misalkan x menjadi suatu solusi layak basis dengan variabel terurut x = B x N Di mana x B adalah vektor variabel basis dan x N adalah vektor variabel nonbasis (sekarang ini bernilai nol). Fungsi tujuan dapat ditulis sebagai : z = c BT x B + c TN x N Di mana koefisien untuk variabel basis yaitu c B dan koefisien untuk variabel nonbasis yaitu c N . Sama halnya kendala ditulis dengan B x B + N x N = b . Kendala dapat dituliskan kembali sebagai x B = B −1b − B −1 N x N . Oleh perubahan nilai variabel
31 ^
^
^
xB ← xB − As x s
^
^
^
dan z ← z + c s x s dapat digunakan untuk nonbasis, semua solusi A x = b dapat diperoleh. Jika formula ini disubstitusikan ke
yang mungkin untuk
dalam formula untuk z maka hasil yang diperoleh adalah : z = c BT B −1b + ( c TN − c BT B −1 N ) x N . Jika y = ( c BT B −1 ) T = B −T c B maka z dapat dituliskan
sebagai z = y T b + ( c TN − y T N ) x N . Vektor y merupakan vektor pengali simplex. Arus nilai variabel dan tujuan diperoleh dengan pembuatan x N = 0 . Ini dinyatakan oleh ^
^
x B = b = B −1 b
dan z = c BT B −1 b . ^T
Misalkan c ^j menjadi elemen pada vektor c N = ( c TN − c BT B −1 N ) sesuai untuk x j . ^
^
^t
Koefisien c j disebut harga reduksi dari x j . Maka z = z + c N x N .
Untuk menguji keoptimalan, apa yang akan terjadi pada fungsi tujuan akan diperiksa jika tiap-tiap variabel nonbasis dinaikkan dari nol. Jika c ^j > 0 , fungsi tujuan akan naik, jika c ^j = 0 , tujuan tidak akan berubah dan jika c ^j < 0 , tujuan akan menurun. Oleh karena itu jika c ^j < 0 untuk beberapa j maka fungsi tujuan dapat diperbaiki jika x j dinaikan dari nol. Jika basis sekarang tidak optimal maka suatu variabel x s dengan c s^ < 0 dapat dipilih untuk masuk basis.
Sekali variabel masuk x s telah dipilih, kemudian nilai x s harus ditentukan besar kenaikannya sebelum kendala kenegatifan dilanggar. Ini menentukan variabel mana ( jika ada ) yang akan meninggalkan basis. Variabel basis didefinisikan oleh x B = B −1b − B −1 N x N . Dan dengan pengecualian ( x s ), semua komponen x N adalah ^
^
^
nol. Jadi x B = b − A x s di mana A s merupakan vektor B −1 As dan A s adalah kolom ke ^
^
s dari A . Komponen persamaan ini diperiksa dengan cara ( x B ) i = b i − a i , s x s Jika a ik^ < 0 maka ( x B ) i akan menurun ketika variabel masuk x s menaik dan ( x B ) i ^
^
akan sama dengan nol ketika x s = b i / a ik . Jika ais^ < 0 maka ( x B ) i akan menaik dan
32 ais^ = 0 maka ( x B ) i akan tetap tidak berubah. Variabel x s dapat dinaikkan
jika
sepanjang semua variabel tetap nonnegatif yaitu hingga ia menjangkau nilai, ^ ^ x s = min imum b i 1 ≤ i ≤ m a^ is
^ ; ai , s > 0
Perbandingan minimum dari tes perbandingan mengidentifikasikan variabel nonbasis baru, dan karena itu menentukan solusi layak basis baru dengan x s sebagai variabel basis baru. Formula : menentukan nilai baru fungsi tujuan dan variabel basis pada basis sekarang. Variabel ^
x s diberikan nilai xs ; sisa variabel nonbasis tetap nol.
Jika ais^ ≤ 0 untuk semua nilai i , maka tidak ada satupun basis akan menurun nilainya ketika x s dinaikan dari nol, sehingga x s dapat dibuat lebih besar secara sembarang. Pada kasus ini fungsi tujuan akan menurun tanpa batas ketika xs → ∞ ,
mengidentifikasikan bahwa program linier tidak mempunyai minimum
terbatas. Seperti suatu masalah dikatakan “ tidak terbatas “.
Dengan demikian metode simplex dapat diperlihatkan sebagai berikut. Metode diawali dengan suatu matriks basis B sesuai untuk solusi layak basis, ^
x B = b = B −1b ≥ 0 . Langkah-langkah algoritma diberikan sebagai berikut : 1. Tes keoptimalan. Hitung vektor y T = c BT B −1 . Hitung koefisien c TN = c TN − y T N . ^T
Jika c N ≥ 0 maka
basis sekarang optimal, prosedur iteratif dihentikan.
Sebaliknya, pilih suatu variabel x s yang memenuhi c s^ < 0 sebagai variabel masuk.
^
2. Langkah. Hitung A s = B −1 As , koefisien kendala sesuai untuk variabel masuk. Temukan suatu indeks i yang memenuhi
33 ^
br ^
a r ,s
^ bi = min imum ^ 1≤i ≤ m a is
^
; a i,s
>0
Tes perbandingan ini menentukan variabel yang keluar dan “ elemen pivot “ ^
^
a r ,s . Jika a is ≤ 0 untuk semua i , maka masalah tidak terbatas.
3. Pivot – Perbaharui matriks basis dan vektor variabel basis x B . Kembali ke langkah pertama.
Perhitungan pada metode simplex dapat disajikan dalam bentuk tabel di mana tabel menggunakan invers matrix basis. Langkah-langkah yang digunakan pada tabel sesuai dengan langkah-langkah algoritma simplex di atas. Pada bagian dasar dari tabel berisi koefisien kendala program linier dalam bentuk standar. Bagian atas baris tabel terdiri dari koefisien fungsi tujuan.Untuk memberi tekanan, nilai tujuan dikalikan -1, baris atas tabel diberikan label − z . Kolom pertama tabel berisi variabel basis dan label kolom sisi kanan mencatat nilai − z dan variabel basis. Karena matrix basis dasar adalah B = I , entri pada bagian dasar kolom “ sisi kanan “ adalah ^
^
x B = b = B −1b dan entri pada baris dasar adalah harga reduksi c sekarang. Pada setiap iterasi entri dalam tabel akan disajikan pada bagian basis sekarang sehingga ^
^
kolom “ sisi kanan “ akan mencakup b dan baris atas akan mencakup c . Suatu formula umum akan diberikan untuk tabel. Suatu program linier dalam bentuk standar dengan n variabel dan m kendala persamaan. Pada iterasi ini, vektor dari variabel basis dan nonbasis secara tepat diasumsikan sebagai x B = (x1 , x 2 ,..., x n )T
dan
T x N = (x m +1 , x m + 2 ,..., x n ) . Tabel yang sesuai untuk program linier asli dan
perubahannya ditunjukkan oleh tabel 2.1
.
34 Tabel 2.1 Perubahan Nilai pada Tabel Simplex Iterasi
0
n
Variabel Persamaan Basis
z 1
Koefisien Dari Variabel Variabel Asli Slack cTN cBT
Sisi Kanan
-z
(0)
xB
( 1,2,…,m )
0
B
N
b
…
…
…
…
…
…
…
…
…
…
…
…
-z
(0)
1
0
xB
( 1,2,…,m )
0
I
c
T N
-
c B −1 N T B
B −1 N
0
-
c BT B −1b B −1b
2.4 Teori Dualitas dan Metode Dual Simplex
Setiap model program linier memiliki dua bentuk yaitu primal dan dual. Bentuk asli dari suatu model program linier disebut bentuk primal, sedangkan bentuk alternatif yang dikembangkan dari bentuk primal disebut dual.
Kegunaan bentuk dual bagi para pengambil keputusan adalah bahwa dengan mereka dapat melihat alternatif permasalahan dari sisi yang berbeda. Bentuk primal akan menghasilkan solusi dalam bentuk jumlah laba yang diperoleh dari memproduksi barang, sedangkan bentuk dual memberikan informasi mengenai nilai (harga) dari sumber-sumber yang membatasi tercapainya laba tersebut.
Suatu masalah minimum dalam bentuk standar jika semua kendala bertipe “ ≥ “ dan semua variabel nonnegatif. Minimum z = c T x Dengan kendala Ax = b
x≥0 Memiliki bentuk dual Maksimum w = b T y Dengan kendala AT y ≤ c y≥0
35 Jika masalah primal memiliki n variabel dan m kendala maka masalah dual akan mempunyai m variabel ( satu variabel dual untuk satu kendala primal ) dan n kendala ( satu kendala dual untuk satu variabel primal ). Koefisien pada tujuan primal merupakan koefisien pada sisi sebelah kanan dual, dan sebaliknya. Matrix kendala pada dual adalah transpos dari matrix pada primal. Masalah dual adalah masalah memaksimumkan, di mana semua kendala bertipe “ ≤ ” dan semua kendala nonnegatif. Ini mengarah kepada bentuk standar untuk masalah maksimum. Kedua bentuk permasalahan di atas disebut pasangan primal dual dan itu dapat dilihat dari relasi berikut, bahwa dual dari dual adalah primal.
Teorema 2.5.1 Dual dari program linier dual adalah program linier primal.
Bukti : Masalah minimum dalam bentuk standar T Minimum z = c x
Dengan kendala Ax ≥ b
x≥0 Program dualnya yaitu : Maksimum w = b T y Dengan kendala AT y ≤ c y≥0
Ini ekivalen dengan masalah minimum berikut dalam bentuk standar : Minimum w ' = −b T y Dengan kendala − AT y ≥ −c y≥0
Dual masalah ini adalah Maksimum z ' = −c T x Dengan kendala − Ax ≤ −b
x≥0
36 Program linier ini ekivalen dengan program Minimum z = c T x Dengan kendala Ax ≥ b
x≥0 yang adalah program linier primal.
Beberapa teorema berikut mendukung sifat-sifat dasar yang berhubungan dengan masalah program linier dual.
Teorema 2.5.2 Misalkan x menjadi suatu titik layak untuk masalah primal dalam bentuk standar dan misalkan y menjadi suatu titik layak untuk masalah dual, maka z = cT x ≥ bT y = w
Bukti : Kendala untuk masalah dual menunjukkan bahwa c T ≥ y T A . Karena x ≥ 0, z = c T x ≥ y T Ax = y T b = b T y = w .
Teorema 2.5.3 Pada pasangan masalah primal dan dual, jika satu masalah mempunyai solusi optimal maka masalah yang lain juga mempunyai salusi optimal dan nilai optimal keduanya adalah sama.
Bukti : Untuk mempermudah, perlu asumsi bahwa 1. Masalah primal mempunyai solusi optimal ( karena peran primal dan dual dapat berganti ) 2. Masalah primal dalam bentuk standar. 3. x* , solusi untuk primal adalah solusi layak basis optimal.
Dengan mengurutkan variabel dan menulis x* dalam bagian variabel basis dan
x nonbasis : x* = B dan menulis A = (B x N
c N ) dan c = B maka X B = B −1b . Jika cN
x* adalah harga reduksi optimal memenuhi c TN − c BT B −1 N ≥ 0 atau c BT B −1 N ≤ c TN .
37 Misalkan y*
menjadi vektor pengali simplex sesuai untuk solusi layak basis ini;
y* = B −1c B atau y*T = c BT B −1 . Akan ditunjukkan bahwa y* adalah layak untuk dual dan b T y* = c T x* . Maka dari teorema 2.5.1 menunjukkan bahwa y* adalah solusi untuk dual. Pemeriksaan kelayakan : y*T A = c BT B −1 (B N )
(
) (
= c BT c BT B −1 N ≤ c BT c TN ) = c T ,
oleh karena itu AT y* ≤ c dan y memenuhi kendala dual. Nilai tujuan untuk primal dan dual adalah
z = c T x = c BT x B = c BT B −1b w = b T y = y T b = c BT B −1b = z w = y T b = c BT B −1b = c BT x B = z
sehingga y* adalah layak untuk dual dan mempunyai nilai dual yang sama dengan nilai optimal primal. Oleh karena itu, dari teorema 2.5.1, y* adalah optimal untuk dual atau oleh karena z adalah batas atas untuk w, y* = B −T c B menyelesaikan dual dan oleh karena itu teorema terbukti.
Metode simplex primal memulai penyelesaian masalah program linier primal dengan solusi layak basis dan mengiterasikannya hingga kondisi optimal terpenuhi. Masalah dual juga dapat memakai metode simplex, dimulai dengan suatu solusi layak untuk program dual dan diiterasikan hingga kondisi optimal dual terpenuhi.
Kondisi optimal untuk primal sesuai dengan kondisi optimal untuk dual. Hasil ini diturunkan sebagai bagian dari pembuktian teorema 2.5.1 di mana itu ditunjukkan bahwa kondisi optimal primal c TN − c BT B −1 N ≥ 0 adalah sama untuk kondisi optimal dual AT y ≤ c . Di mana y = B −1c B merupakan vektor pengali simplex sesuai pada basis. Jadi, metode simplex primal bergerak melalui barisan layak primal tapi basis
38 tidak layak dual. Tiap iterasi mereduksi ketidaklayakan dual hingga keoptimalan primal terpenuhi.
Metode dual simplex bekerja pada cara “ dual”. Bergerak melalui suatu barisan layak dual tapi basis tidak layak primal, mereduksi ketidaklayakan primal hingga kondisi primal terpenuhi. Walaupun metode dual simplex dapat dilihat sebagai penggunaan metode simplex untuk masalah dual, namun metode dual simplex dapat juga diimplementasikan secara langsung dalam hubungan masalah primal, jika suatu solusi layak tersedia. Misalkan masalah diselesaikan secara mendasar pada bentuk standar dengan beberapa b < 0 , harga koefisien relatif untuk variabel basis c B = 0 dan semua lainnya c N ≥ 0 . Karena beberapa b negatif, solusi primal akan tidak layak dan kerena semua c ≥ 0 , solusi dual yang sesuai akan menjadi layak. Oleh karena itu metode dual simplex berakhir ketika
basis sekarang
adalah layak primal dan
sebaliknya, iterasi metode dual simplex dimulai dengan pemeriksaan nilai x B ≥ 0 . Jika tidak demikian, beberapa entri ( x B )s < 0 digunakan untuk menjadi baris pivot. Dengan menggunakan argumen yang sama, iterasi metode dual simplex diturunkan seperti pada metode simplex primal. Andaikan bahwa suatu variabel (x B )r ^
tidak layak hingga elemen sebelah kanannya b < 0 seperti keterangan di atas. Sementara kendala ke s pada basis sekarang mempunyai bentuk :
(x B )r + ∑ a s , j x j
^
= br < 0
j∈N
^ di mana N merupakan himpunan indeks variabel nonbasis dan a s , j merupakan
^
entri pada baris s dari B −1 A . Jika beberapa entri a r , j < 0 dan variabel nonbasis x j ^
digantikan (x B )s pada basis, maka nilai baru x j akan menjadi
bs ^
> 0 , yang mana
a s, j variabel basis baru akan menjadi layak. Tidak semua variabel nonbasis dapat masuk basis karena kondisi layak dual ( keoptimalan primal ) harus tetap terpenuhi. Jika x j adalah variabel masuk, maka harga reduksi baru akan memenuhi
39 −
^
a s ,l untuk cl = cl − c j ^ l = 1,2,..., n a s, j ^
^
^
^
( jika l = j maka c l = 0 ). Karena tiap c l harus menjadi nonnegatif, rasio terkecil
^ cj ^ a s , j
dengan ^ a s , j < 0 menentukan mana harga reduksi menjadi nol pertama kali. ^
Tes perbandingan memerlukan perhitungan
cj ^
untuk setiap variabel nonbasis j
a r, j ^
yang mana a s , j < 0 . Jadi itu penting untuk mengetahui elemen pada baris pivot. Sebaliknya, baris pivot harus dihitung. Elemen nonbasis pada baris yang masuk ditunjukkan oleh esT B −1 A j di mana es adalah kolom ke s dari matriks identitas
m × m . Elemen ini dapat dihitung oleh σ T = esT B −1 yaitu penghitungan baris r dari B −1 kemudian
pembentukan σ T A j untuk semua variabel nonbasis j . Harga ^ pada c j
perhitungan akhir ini hampir sama ketika langkah penetapan harga metode simplex primal.
Pivot yang ditunjukkan seperti pada metode simplex primal. Sebaliknya kolom ^
pivot dihitung menggunakan At = B −1 At dan harga reduksi sekarang ini menggunakan ^ ^
^
cj ←cj−
ct ^
^
a s , j . Akhirnya x B dan B −1 terbaharui.
a s ,t
Selanjutnya metode simplex dapat disimpulkan sebagai berikut. Pada basis ^
asli, harga reduksi harus memenuhi c j ≥ 0 . Ada 3 (tiga) langkah utama; tes kelayakan, langkah, dan pivot : ^
1. Tes kelayakan. Jika x B = b = B −1b ≥ 0 , maka basis sekarang adalah suatu solusi. Sebaliknya, (x B )r dipilih sebagai variabel keluar, di mana b s < 0. ^
40 ^
2. Langkah. Pada baris pivot ( baris dengan elemen a r , j = c sT B −1 A j , di mana c s merupakan kolom ke s dari matriks identitas ) temukan suatu indeks t yang memenuhi ^
ct ^
a s ,t
^ cj = min imum ^ 1≤ j ≤ n as, j
^ ; a s , j < 0 , x j nonbasis. ^
Ini menentukan variabel masuk xt dan elemen pivot a s ,t . Jika tidak terdapat indeks t , maka masalah primal tidak layak dan masalah tidak terbatas. 3. Pivot. Hal ini menggambarkan program linier pada hubungan basis baru.
Metode dual simplex juga memberikan langkah-langkah yang mudah pada penyelesaian masalah dual dalam bentuk tabel.
1. Baris r dipilih sebagai baris pivot sedemikian hingga −
−
b r = minimum b i < 0
2. Kolom s sebagai kolom pivot sehingga _
cs ^
− a r ,s
− cj = min imum − − arj < 0 − a rj
−
Jika semua a rj ≥ 0 , primal tidak akan mempunyai satupun solusi layak (optimal).
−
3. Adakan suatu operasi pivot pada a rs −
4. Uji keoptimalan. Jika semua b i ≥ 0 maka solusi sekarang adalah optimal dan karena itu prosedur iteratif dihentikan. Selain itu, kembali ke langkah (1)
41 2.6 Analisis Sensitivitas
Analisis sensitivitas adalah analisis yang dilakukan untuk mengetahui pengaruh perubahan yang terjadi pada parameter-parameter persoalan program linier terhadap solusi optimal yang telah dicapai. Analisis ini juga sering disebut dengan analisis pasca optimal, yaitu suatu analisis yang dilakukan setelah solusi optimal diperoleh.
Tujuan umum dari analisis sensitivitas adalah untuk menentukan parameterparameter sensitif ( yaitu parameter yang tidak dapat diubah tanpa mengubah penyelesaian optimal ), melakukan estimasi parameter-parameter dengan lebih tepat, serta memilih penyelesaian yang tetap lebih baik untuk sejumlah nilai-nilai yang layak dimiliki oleh parameter-parameter yang sensitif. Tujuan yang lain adalah untuk mengurangi perhitungan-perhitungan dan menghindari perhitungan ulang, bila terjadi perubahan pada satu atau beberapa koefisien model program linier pada saat penyelesaian optimal telah dicapai.
Teknik analisis sensitivitas bergantung pada kondisi layak dan optimal untuk suatu program linier.Basis sekarang adalah layak jika B −1b ≥ 0 dan itu optimal jika c TN − c BT B −1 N ≥ 0 . Dari sudut pandang ilmu pasti, semua analisis sensitivitas dapat
diingat sebagai konsekuensi formula ini. Pendekatan umum analisis sensitivitas adalah
1. Apakah perubahan parameter mempengaruhi kondisi optimal dan seberapa besar data dapat berubah sebelum kondisi optimal dilanggar ? Jika basis sekarang tidak optimal, maka metode simplex primal digunakan untuk memperbaiki keoptimalan.
2. Apakah perubahan parameter mempengaruhi kondisi layak dan seberapa besar parameter dapat berubah sebelum kondisi layak dilanggar. Jika basis sekarang tidak layak, maka metode dual simplex digunakan untuk memperbaiki ketidaklayakan.
Secara umum, ketika suatu parameter berubah, salah satu akibat yang mungkin terjadi adalah :
42 1. Solusi optimal tidak berubah, begitu juga variabel basis dan nilainya juga tidak berubah. 2. Variabel basis tetap sama tetapi nilainya berubah. 3. Variabel basis dan nilainya sama-sama berubah.
Ada 5 ( lima ) tipe dasar perubahan parameter yang mempengaruhi solusi optimal. Kelima tipe itu adalah :
1. Perubahan koefisien fungsi tujuan ( c j ) 2. Perubahan konstan sisi kanan ( bi ) 3. Perubahan kendala atau koefisien matrix A 4. Penambahan variabel baru 5. Penambahan kendala baru
Tetapi dalam masalah ini, perubahan parameter yang berhubungan dengan program linier parametrik hanyalah pada tipe 1 (satu) dan 2 (dua). Beberapa aturan umum dapat diuraikan untuk penyelesaian analisis sensitivitas dengan harga reduksi ^T
c N = c TN − c BT B −1 N adalah sebagai berikut. 1. Perubahan pada koefisien fungsi tujuan (c j ) Perubahan ini terdiri dari dua bagian, yaitu : 1. Perubahan koefisien fungsi tujuan variabel basis (c B ) . −
Jika c B = c B + ∆c B maka untuk menentukan agar basis tetap optimal ^T
dengan memeriksa bahwa c B ≥ −(∆c B )T x B terpenuhi. Jika basis tidak −
−
berubah maka y = y + B −T ∆c B dan z = z + (∆c B )T x B . Jika basis berubah, metode simplex primal digunakan untuk memperbaiki keoptimalan pada masalah pengganggu.
43 2. Perubahan koefisien fungsi tujuan variabel nonbasis (c N ) . −
Jika c N = c N + ∆c N maka untuk menentukan agar basis tetap optimal ^T
dengan memeriksa bahwa c N ≥ −(∆c N )T terpenuhi. Jika basis tidak berubah maka metode simplex primal digunakan untuk memperbaiki keoptimalan pada masalah pengganggu.
2. Perubahan konstan sisi kanan ( bi ) −
Jika b = b + ∆b maka untuk menentukan agar basis tetap layak dengan memeriksa
^
b ≥ − B −1 ∆b
−
terpenuhi.
Jika
basis
tidak
berubah
maka
−
x B = x B + B −1 ∆b dan z = z + y T ∆b . ( Vektor y merupakan vektor dari variabel dual ). Jika b < 0 , metode dual simplex digunakan untuk memperbaiki kelayakan pada masalah pengganggu.
2.7 Program Linier Parametrik
Analisis sensitivitas membicarakan tentang pengaruh perubahan parameter terhadap solusi optimal yang telah dicapai, di mana perubahan parameter yang terjadi secara tertentu. Sementara program linier parametrik juga membicarakan tentang pengaruh perubahan parameter terhadap solusi optimal yang telah dicapai, bedanya, perubahan parameter dapat terjadi secara kontinu. Oleh karena itu program linier parametrik dapat diartikan sebagai analisis yang berkaitan dengan perubahan kontinu parameter untuk menentukan urutan solusi dasar yang menjadi optimum jika perubahan dilakukan lebih jauh. Dalam pengertian yang lain, program linier parametrik merupakan suatu bentuk analisis sensitivitas sistematis, di mana nilai interval tujuan dan sisi kanan ( nilai kuantitas kendala ) dianalisis. Besarnya nilai perubahan parameter yang terjadi berada dalam interval tertentu. Perubahan parameter-parameter ( koefisien tujuan atau nilai kuantitas kendala ) dapat diperkenankan terjadi secara bersamaan ataupun terpisah.
44
Program linier parametrik dibagi dalam 2 ( dua ) bagian : 1. Perubahan parameter koefisien fungsi tujuan (c j ) Pada saat parameter c j diubah, fungsi objektif asli n
Minimum z = ∑ c j x j j =1
Berubah menjadi Minimum z (θ ) = ∑ (c j + α jθ )x j n
j =1
Dengan kendala yang tetap seperti kendala asli dan x j ≥ 0, j = 1,2,..., n Di mana :
z (θ )
: Suatu modifikasi fungsi model program linier asli menjadi fungsi θ
θ
: Besarnya tingkat perubahan parameter yang diinginkan terjadi (θ ∈ R )
αj
: Angka relatif perubahan parameter, ( α j ∈ Z )
cj
: Keuntungan setiap satuan variabel keputusan j terhadap nilai z
xj
: Variabel keputusan ke j
j
: Jenis aktivitas yang menggunakan sumber atau fasilitas yang tersedia
( j = 1,2,..., n ) 2. Perubahan parameter pada nilai kuantitas batasan (bi ) Pada saat nilai kuantitas kendala diubah, nilai kuantitas kendala asli n
∑a j =1
ij
x j = bi
Berubah menjadi n
∑a j =1
ij
x j = bi + α iθ , i = 1,2,..., m
Dengan fungsi tujuan tetap seperti pada masalah asli. Di mana : aij
: Banyaknya sumber ke i yang diperlukan untuk menghasilkan setiap unit aktivitas j .
45 xj
: Variabel keputusan ke j
bi
: Banyaknya sumber atau fasilitas ke i yang tersedia untuk dialokasikan pada setiap jenis aktivitas.
αi
: Angka relatif perubahan parameter kuantitas kendala, (α i ∈ Z )
θ
: Besarnya tingkat perubahan parameter yang diinginkan terjadi.
i
: Jenis sumber atau fasilitas yang tersedia (i = 1,2,..., m )
Perubahan kenaikan ataupun penurunan θ sisi sebelah kanan pada himpunan persamaan awal, kemudian akan menyebabkan perubahan sisi kanan pada himpunan persamaan akhir yang nantinya akan menyebabkan perubahan daerah solusi optimal. Prosedur penyelesaian masalah program linier parametrik mirip dengan prosedur untuk perubahan sistematis parameter c j . Prosedur yang digunakan adalah prosedur analisis sensitivitas pada perubahan parameter nilai kuantitas batasan, di mana juga melibatkan penggunaan metode dual simplex untuk kasus khusus (bi < 0 ) sehingga solusi optimal untuk masalah baru ini dapat diperoleh.
