ANALISIS POSTOPTIMAL/SENSITIVITAS Dalam sub bab ini kita akan mempelajari apakah solusi optimal akan berubah jika terjadi perubahan parameter model awal. Jika solusi optimal berubah, dapatkah kita menghitung solusi optimal baru tanpa harus
menyelesaikan
permasalahan baru?
permasalahan
secara
lengkap
sebagai
Kita akan temukan dalam banyak kasus, solusi
optimal baru dapat diperoleh tanpa usaha perhitungan tambahan yang terlalu banyak. Dasar analisis optimal terletak pada penyelidikan tabel simpleks umum dalam bentuk matriks. Perubahan parameter model awal dapat mempengaruhi optimalitas maupun kelayakan. Perubahan yang terjadi dan pengaruhnya terhadap optimalitas dan kelayakan adalah sebagai berikut: 1. Perubahan yang hanya mempengaruhi optimalitas: a. Perubahan pada koefisien fungsi tujuan (CI, CII). b. Perubahan penggunaan sumber daya aktivitas non basis. c. Penambahan aktivitas baru 2. Perubahan yang hanya mempengaruhi kelayakan: a. Perubahan pada nilai kanan (solusi) b. b. Penambahan batasan baru 3. Perubahan simultan (CI, CII) dan b akan mempengaruhi baik optimalitas maupun kelayakan. Perhitungan yang dibutuhkan untuk mendapatkan solusi optimal masing-masing kategori di atas adalah: 1. Jika tabel menjadi tidak optimal, gunakan metode primal simpleks sampai diperoleh tabel optimal baru. 2. Jika tabel menjadi tidak layak, gunakan metode dual simpleks sampai solusi layak diperoleh. 3. Jika tabel menjadi tidak optimal sekaligus tidak layak, pertama gunakan primal simpleks tanpa memperdulikan
ketidaklayaknnya. Setelah solusi optimal diperoleh, gunakan metode dual simpleks untuk mendapatkan solusi optimal layak. PERUBAHAN YANG MEMPENGARUHI OPTIMALITAS Berdasarkan definisi tabel simpleks umum, perubahan (CI, CII) hanya membutuhkan perhitungan ulang baris tujuan tabel optimal. Sebagai contoh, model awal permasalahan PL adalah: Maksimumkan z = 2x1 + 3x2 Terhadap : 10x1 + 5x2 ≤ 600 6x1 + 20x2 ≤ 600 8x1 + 15x2 ≤ 600 x1, x2 ≥ 0 Solusi optimalnya adalah: VB
X1
X2
X3
X4
X5
solusi
z
0
0
0
1/3
11/45
126.67
X3
0
0
1
-5/3
-17/9
166.7
X2
0
1
0
0
-1/5
20
X1
1
0
0
1/6
2/9
100/3
Setelah beberapa lama, fungsi tujuan berubah menjadi maksimumkan 4x1 + 4x2. Perubahan ini dapat mengakibatkan ketidakoptimalan; oleh karena itu, yang harus kita lakukan adalah memeriksa syarat optimal. Dari tabel optimal di atas kita dapatkan: XB = [x3
x2
x1]
CB = [0
4
Dari formulasi matematik Plnya kita dapatkan: Y = [y1 Maka, Y = CBB-1 = [0
4
4]
4]
B-1 = y2
y3]
= [0
2/3
4/45]
Berikutnya kita menghitung koefisien baris z untuk vektor yang bukan vektor basis. Dalam hal ini adalah vektor P4 dan P5. z4 – c4 = YP4 – c4 = [0
2/3
4/45] - 0 = 2/3
z5 – c5 = YP5 – c5 = [0
2/3
4/45] - 0 = 4/45
Karena koefisien fungsi tujuan (vektor non basis) semua masih bernilai positif dan fungsi tujuan adalah maksimisasi, maka perubahan koefisien fungsi tujuan tersebut tidak merubah solusi optimal yang sudah ada, yaitu x1 = 100/3; x2 =20. Nilai yang berubah hanyalah nilai z, karena perubahan koefisien.
Nilai z (keuntungan maksimum) menjadi 4 x
100/3 + 4 x 20 = 213 .333. Perhatikan, jika koefisien fungsi tujuan itu setelah beberapa lama berubah menjadi 3x1 + 6x2. Nilai Y berbeda dengan nilai di atas, yaitu: Y = CBB-1 = [0 = [0
6 ½
3]
-8/15]
Koefisien baris z untuk vektor yang bukan vektor basis ( P4 dan P5) adalah: z4 – c4 = YP4 – c4 = [0
½
-8/15]
- 0 = 1/2
z5 – c5 = YP5 – c5 = [0
½
-8/15]
- 0 = -8/15
Berdasarkan perhitungan di atas, tabel menjadi tidak optimal dan vektor P5 menjadi vektor masuk.
Lanjutkan dengan simpleks yang direvisi
untuk mementukan solusi optimal. Karena dari perhitungan di atas kita sudah mendapatkan vektor masuk, maka selanjutnya adalah menentukan vektor keluar. ¾
XB = B-1b =
= [-6400/3 -120 700/3]T
¾
α5 = B-1P5 =
= [-17/9
2/9]T ¾
θ
= 1050
Vektor keluar dengan demikian adalah P1. ξ = [17/2
9/10
9/2]T
-1/5
E=
B-1next = EB-1 Kembali
menentukan
vektor
masuk
sekaligus
memeriksa
syarat
optimalitas. Basis pada iterasi ini adalah P3, P2 dan P5. Y = CBB-1 = [0
6
0]
Perubahan penggunaan sumber daya oleh aktivitas hanya akan mempengaruhi opimalitas, karena perubahan itu akan mempengaruhi sisi kiri pembatas dualnya.
Perubahan penggunaan sumber daya ini
kita batasi hanya untuk aktivitas non basis. sumber
daya
aktivitas
basis
akan
Perubahan penggunaan
mempengaruhi
invers
dan
mengarahkan perhitungan yang sangat kompleks. Misalkan untuk kasus di atas, setelah beberapa lama terjadi perubahan penggunaan sumber daya pertama, kedua dan ketiga oleh aktivitas 1 berubah dari 10, 6 dan 8 ke 8, 7 dan 9 secara berturut-turut. Batasan dual yang sesuai untuk perubahan itu adalah: 8y1 + 7y2 + 9y3 ≤ 2 Faktor terakhir yang akan kita pelajari yang dapat mempengaruhi optimalitas adalah penambahan aktivitas baru. Misalkan untuk kasus di atas, setelah beberapa lama perusahaan memproduksi produk 3 (x6) menggunakan fasilitas produksi yang sama. PL-nya menjadi: Maksimumkan z = 2x1 + 3x2 + x6 Terhadap : 10x1 + 5x2 + 2x6 ≤ 600
Model matematik umum
6x1 + 20x2 + x6 ≤ 600 8x1 + 15x2 + x6 ≤ 600 x1, x2, x6 ≥ 0 Penambahan aktivitas baru sama dengan mengkombinasikan analisis perubahan pada tujuan dan koefisien kendala (penggunaan sumber daya).
Kita dapat membayangkan x6 seolah-olah bagian dari
model awal dengan semua koefisien bukan nol, dengan kata lain, x6 adalah non basis.
Hal pertama yang harus kita lakukan adalah
memeriksa batasan dual yang sesuai: 2y1 + y2 + y3 ≥ 1 Karena x6 berfungsi sebagai variabel non basis pada solusi awal (tabel awal simpleks), maka nilau dual tidak berubah. Oleh karena itu koefisien x6 dalam tabel optimalnya adalah: 2(0) + 1/3 + 11/45 – 1 = -19/45 Angka ini menunjukkan bahwa solusi optimal saat ini akan lebih baik jika x6 bernilai positif. Tabel optimal saat ini dimodifikasi dengan menambahkan satu kolom x6 dengan koefisien pada baris z-nya adalah 19/45. Koefisien pembatasnya dihitung dengan cara berikut: B-1P6 = (1
-5/3
-17/9
0
0
-1/5
1
0
1/6
2/9
1
= [-14/9
(2
-1/5
7/18]T
Lanjutkan iterasi, maka akan didapatkan seperti tabel simpleks di bawah ini. VB
X1
X2
X6
X3
X4
X5
solusi
z
0
0
-19/45
0
1/3
11/45
126.67
X3
0
0
-14/9
1
-5/3
-17/9
166.7
X2
0
1
-1/5
0
0
-1/5
20
X1
1
0
7/18
0
1/6
2/9
100/3
z
38/35
0
0
0
54/105 17/35 162.854
X3
4
0
0
1
-1
-1
300.01
X2
18/35
1
0
0
3/35
-3/35
37.14
X6
18/7
0
1
0
6/14
4/7
85.7
PERUBAHAN YANG MEMPENGARUHI KELAYAKAN Dua faktor yang dapat mempengaruhi kelayakan solusi tabel simpleks, yaitu perubahan pada nilai kanan (vektor b) dan penambahan pembatas baru. Misalkan untuk kasus di atas (kasus 2.5), jam kerja mesin pertama berubah dari 600 ke 580 menit dan mesin kedua dari 600 ke 575 menit, karena kedua mesin harus mendapatkan perawatan rutin per hari selama 20 dan 25 menit secara berturut-turut. Karena perubahan nilai kanan hanya akan mempengaruhi kelayakan, maka kita akan menghitung nilai XB [x3 x2
x1]
XB = B-1b = [ -1511.6633
-120 1375/6]T
Karena nilai x3 dan x2 menjadi negatif, maka iterasi kita teruskan dengan nilai kanan variabel basis sama nilai XB di atas. VB
X1
X2
X3
X4
X5
solusi
z
0
0
0
1/3
11/45
1375/3
X3
0
0
1
-5/3
-17/9 -1511.6633
X2
0
1
0
0
-1/5
-120
X1
1
0
0
1/6
2/9
1375/6
Z
0
0
11/85
-82/51
0
262.703
X5
0
0
-9/17
15/17
1
800.2923
X2
0
1
-9/85
3/17
0
40.05846
X1
1
0
2/17
-0.22549
0
51.3239337
Tabel sudah optimal pada iterasi pertama. Perubahan yang terjadi pada kasus di atas ada pada ketersediaan sumber daya yang membatasi misalnya karena umur ekonomis mesin
sudah berkurang.
Bagaimana jika terjadi penambahan batasan baru,
misalnya permintaan terhadap produk yang dihasilkan yang tadinya tidak dibatasi menjadi terbatas (baik bataasan =/≤/≥)?
Penambahan
batasan baru ini juga akan mempengaruhi kelayakan tabel simpleks. Misalkan untuk kasus di atas, setelah beberapa lama perusahaan dapat menjalin kerja sama dengan salah satu distributor.
Distributor
sudah menyepakati untuk disuplai produk 2 maksimum 50 unit setiap hari. Karena kontrak yang ditandatangani mengatakan bahwa produk 2 hanya akan dijual ke distributor tersebut, maka permasalahan optimasi ini mendapatkan satu kendala baru, yaitu: x2 ≤ 50 Batasan baru ini tidak dipenuhi tabel simpleks optimal di atas, dimana pada tabel optimal tersebut nilai x2 (jumlah produk 2 yang diproduksi supaya optimal) adalah 20 unit. Untuk menyelesaikannya, pertama-tama batasan baru tersebut kita rubah kedalam bentuk bakunya, yaitu: x2 + x6 = 50 Nilai x2 pada persamaan di atas harus digantikan dengan nilai x2 dari tabel optimalnya, karena x2 berfungsi sebagai variabel basis pada tabel tersebut. Maka akan diperoleh: 1/5x5 + x6 = 30 Tabel simpleksnya menjadi: VB
X1
X2
X3
X4
X5
X6
solusi
z
0
0
0
1/3
11/45
0
126.67
X3
0
0
1
-5/3
-17/9
0
166.7
X2
0
1
0
0
-1/5
0
20
X1
1
0
0
1/6
2/9
0
100/3
X6
0
0
0
0
1/5
1
30
PERUBAHAN
YANG
MEMPENGARUHI
OPTIMALITAS
DAN
KELAYAKAN Perubahan optimalitas
yang
atau
terjadi
kelayakan
tidak secara
hanya
dapat
terpisah,
mempengaruhi keduanya secara bersamaan.
mempengaruhi
tetapi
dapat
juga
Perhatikan misalnya
kasus di atas, setelah beberapa lama: 1. terjadi perubahan pada koefisien fungsi tujuan menjadi 3x1 + 6x2 2. jam kerja mesin pertama berubah dari 600 menit menjadi 580 menit dan mesin kedua dari 600 menit menjadi 575 menit. Kedua perubahan itu menghasilkan tabel simpleks berikut:
