DUALITAS DAN ANALISIS SENSITIVITAS

Dualitas dan Analisis Sensitivitas

1. Pengantar
Mencari solusi optimum dari suatu masalah pada bab bab sebelumnya bukan merupakan tujuan dari LP (linier programming). Dalam table simpleks mengandung informasi ekonomi tambahan yang bahkan lebih penting dari solusi optimum masalah tersebut. Pentingnya informasi tambahan dari metode simpleks optimum telah mendorong munculnya teori ini.
Dalam bab ini akan membahas metode dual simpleks. Yang dimana kita dapat mempelajari tanpa suatu pemahaman yang baik tentang metode simpleks oleh karena itu topik topik ini mengikuti metode simpleks.
2. Teori Dualitas
Teori dualitas ini merupakan salah satu konsep yang sangat penting dan menarik dalam LP. Istilah dualitas menunjuk sebagai kenyataan dari setiap LP dalam dua bentuk, yaitu :
1. Bentuk asli (Primal)
2. Saling berhubungan (Dual) teori ini yang dimana suatu solusi terhadap LP yang asli memberikan solusi pada bentuk dualnya.
Contoh :
Pemberian jumlah mineral dan vitamin yang terdapat pada dua jenis makanan tiruan yaitu daging dan sayur per unit serta harganya.
Kandungan Makanan Tiruan Kebutuhan minimum per hari
Daging Sayur
Mineral 2 4 40
Vitamin 3 2 50
Harga per unit 3 2,5
Menentukan biaya pembelian terhadap dua kandungan hingga kebutuhan minimum per hari terpenuhi.
Rumus xj (j = 1,2)
Tentukan nilai xı dan x2?


Minumumkan Z = 3xı + 2,5x2
Dengan syarat: 2xı + 4x2 ≥ 40
3xı + 2x2 ≥ 50
xı , x2 ≥ 0
penentuan yı dan y2. (bentuk dual Y1 dan Y2/Variabel dual)
Menentukan W = 40Yı + 50 Y2
Dengan syarat: 2yı + 3Y2 ≤ 3
4Yı + 2Y2 ≤ 2,5
Yı , Y2 ≥ 0 karena nilai negatif tak benar.
Perbandingan masalah dual dengan masalah primal adalah
1. Tanda pertidaksamaan kendala dibalik
2. Bentuk dual dari dual adalah bentuk primal
3. Koofesien fungsi tujuan masalah primal menjadi konstan sisi kanan masalah dual. Sebaliknya, konstan sisi kanan primal menjadi koofesien fungsi tujuan dual.

a. Masalah Primal-Dual Simetrik
Suatu LP dikatakan Bentuk simetrik apabila semua variabel dibatasi bernilai negatif dan semua kendala berupa pertidaksamaan.
Bentuk umum masalah primal dual yang simetrik adalah :
Primal : Maksimumkan Z = cıXı + c2X2 + ...... + cnxn
Dengan syarat aııXı + aı2X2 + ……. + aınXn ≤ bı
A2ıXı + a22X2 + . . . + a2nXn ≤ b2
n variabel
m kendala
amıXı + am2X2 + …… + amnXn ≤ bm
Xı X2….,,,, Xn ≥ 0
Dual : Minimumkan W = bıYı + b2y2 + . . . + bmYm
Dengan syarat aııYı + a2ıY2 + . . . + amıYm ≥ cı
Aı2Yı + a22Y2 + . . . am2Ym ≥ c2

n variabel
m kendala
aınYı + a2nY2 + . . . + amnYm ≥ Cn
Yı, Y2,…. Ym ≥ 0
Dalam notasi matriks masalah primal-dual simetrik adalah :
Primal : Maksimumkan Z = cX
Dengan syarat : AX ≤ b
X ≥ 0
Dual : Maksimumkan W = Yb
Dengan syarat : YA ≥ c
Y ≤ 0
Yang dimana :
- A adalah suatu matriks mxn
- B adalah vektor kolom mxl
- C adalah 1xn
- X adalah vektor kolom nXı
- Y adalah vektor baris 1xm
Aturan umum penulisan bentuk dual dari suatu LP yang simetris
- Balik arah pertidaksamaan kendala
- Misalkan, sebuah variabel dual untuk setiap kendala primal
- Balik arah optimisasi, ubah minimum menjadi maksimum
- Vektor baris koofesien fungsi tujuan primal diubah menjadi vektor kolom konstan sisi kanan dual

Beberapa teori dualitas yang memberikan hubungan antara solusi primal dan dual
1. Teori 1
Misalkan suatu bentuk primal dan simetrik
Maks. Z = cX dan Min. W = Yb
Dengan syarat : AX ≤ b Dengan syarat : YA ≥ c
X ≥ 0 Y > 0
Nilai fungsi tujuan masalah minimisasi untuk setiap solusi yang layak selalu lebih besar atau sama dengan masalah maksimisasinya.
2. Teori 2
Jika terdapat solusi layak X ᴼ dan Yᴼ pada bentuk primal dual simetrik demikian hingga nilai nilai fungsi tujuan yang berhubungan adalah sama, maka solusi layak ini adalah solusi optimum terhadap masalah yang bdi hadapi.
3. Teori 3
Jika baik masalah primal maupun dual adalah layak, maka keduanya memiliki solusi demikian hingga nilai optimum fungsi tujuan adalah sama.
4. Teori 4
Kondisi ini merupakan complementary slackness yang pernyataannya ialah :
- Jika suatu variabel primalnya Xᴼj bernilai positif.
- Jika suatu kendala primal berupa pertidaksamaan pada keadaan optimum
- Jika suatu variabel dual Yᴼi bernilai positif
- Jika suatu kendala dual berupa pertidaksamaan murni

b. Masalah Primal Dual Asimetrik
Karena tidak semua program linier berbentuk linier dalam hal ini akan di bicarakan hubungan primal-dual bagi masalah LP yang tak simetris.
Bentuk masalah primal yang tak simetris :
Maks. Z = 4Xı + 5x2
Dengan syarat : 3Xı + 2X2 ≤ 20
4Xı – 3X2 ≥ 10
Xı + X2 = 5
Xı ≥ 0, X2 tak terbatas.
Bentuk masalah primal yang simetris :
Maks. Z = 4Xı + 5X3 – 5X4
Dengan syarat : 3Xı + 2x3 – 2x4 ≤ 20
-4x1 +3x3 + 3x4 ≤ -10
X1 + x3 – x4 ≤ 5
-x1 – x3 + x4 ≤ -5
x1, x3, x4 ≥ 0
Bentuk dual simetriknya :
Minimumkan W = 20Uı – 10U2 + 5U3 – 5U4
3U1 – 4U2 + U3 – U4 ≥ 4
2U1 + 3U2 + U3 – U4 ≥ 5
-2U1 + 3U2 – U3 + U4 ≥ -5
U1, U2, U3 U4 ≥ 0

Yı = U1, Y2 = -U2, Y3 = U3 – U4
Minimumkan W = 20Yı + 10Y2 + 5Y3
Dengan syarat : 3Yı + 4Y2 + Y3 ≥ 4
2Yı – 3Y2 + Y3 = 5
Y1 > 0, Y2 < 0, Y3 tak terbatas

c. Mencari solusi optimum bentuk dual
Karena setiap LP dapat dipecahkan dengan metode simpleks, maka metode itu dapat di terapkan baik pada masalah primal maupun dual. Main duality theorem menyatakan bahwa suatu solusi optimum terdapat bentuk dual dapat di peroleh melalui solusi primal dan sebaliknya.
d. Penafsiran solusi dual
Solusi optimum bentuk dual dapat di tafsirkan sebagai sumbangan per unit kendala sumberdaya. Berdasarkan main duality theorem nilai optimum fungsi tujuan primal dan dual adalah sama. Jika xº dan yº adalah solusi optimumnya, maka Z = cXº = Yº b = W.
Optimum program linier adalah Z = Yıºbı + Y2ºb2 + . . . + Ymºbm,
e. Keuntungan perhitungan bentuk dual
Setiap masalah LP dapat dipecahkan dengan merumuskan baik dalam bentuk primal maupun dual. Karena solusi satu masalah adalah selalu dapat diperoleh dari solusi bentuk dualnya, maka tidak perlu kedua bentuk.
Satu jenis masalah adalah lebih mudah untuk diselesaikan dibanding yang lain tanpa meneliti struktur massalahnya. Atas kesepakatan bahwa sejumlah besar kendala membuat masalah perhitungan yang lebih gawat daripada sejumlah besar variabel. Yang di karenakan jumlah kendala menentukan banyak vektor basis dalam solusi yang pada gilirannya menentukan ukuran matriks basis inverse.
3. METODE DUAL SIMPLEKS
Prosedur pehitungan yang dibicarakan sejauh ini bergerak dari solusi dasar yang belum optimum ke solusi layak yaang lain. Kemampuan untuk mendapatkan suatu solusi dasar awal layak sangat tergantung pada proses akhir. Jika formulasi LP mengandung sejumlah besar artificial variabel, maka banyak memperhitungkan perolehan solusi awal layak.
Karena itu, akan dijelaskan suatu prosedur perhitungan yang memberikan suatu solusi layak optimum, meski solusi awalnya tak layak. Prosedur itu biasa juga disebut dual simpleks algoritm yang dikemukakan oleh lemke. Algoritm berpengaruh penting dalam post optimality analisis.
4. ANALISIS SENSITIVITAS
Suatu analisisnya jarang dapat menentukan paramenentukan parameter model LP karena nilai parameter ini adalah fungsi beberapa uncontrolable variable. Analisis perubahan parameter dan pengaruhnya rerhadap solusi LP dinamakan Post optimality analysis. Isttilah Post optimality menunjukan bahwa analisis ini terjadi setelah diperoleh solusi optimum, dengan mengasumsikan seperangkat nilai parameter yang di gunakan dalam model.
Perubahan dalam suatu masalah LP yang biasanya dipelajari melalui post optimality analysis dapat dipisahkan kedelam kelompok umum.
- Analisis yang berkaitan dengan perubahan diskrit parameter untuk melihat berapa besar perubahan dapat ditolerir sebelum solusi optimum mulai kehilangan optimalisasinya, ini dinamakan analisis sensitivitas.
- Analisis yang berkaitan dengan perubahan struktural.
- Analisis yang berkaitan dengan perubahan kontinu parameter untuk menentukan urutan solusi dasar yang menjadi optimum jika perubahan ditambah lebih jauh, ini dinamakan parametric – programming.
Melalui analisis sensitivitas dapat dievaluasi pengaruh perubahan perubahan parameter dengan sedikit tambahan perhitungan berdsarkan tabel simmpleks optimum. Namun jika perubahan terlalu banyak, perhitungan post optimum dapat meletihkan sehingga lebih efisien jika menyelesaikan kembali masalah LP dengan metode simpleks.
Perubahan perubahan parameter dalam analisis sensitivitas dikelompokan menjadi :
a. perubahan koofesien fungsi tujuan
b. perubahan konstan sisi kanan
c. perubahan kendala
d. penambahan variabel baru
e. penambahan kendala baru.
Prinsip prinsip dasar dalam menjalankan analisis sensitivitas akan dijelaskan secukupnya sehingga pembaca tidak akan mendapat kesulitan memperluas ke masalah masalah lain.
a. perubahan koefisien fungsi tujuan
hal ini biasa terjadi untuk variabel basis atau variabel non basis. Interval sensitivitas masing masing ditentukan secara berlainan, sehingga dual hal yang berbeda akan di pelajari secara terpisah.
1. perubahan koefisien fungsi tujuan dari variabel non basis
Dalam kombinasi barang optimum, barang C tidak diproduksi karena keuntungan per unitnya rendah, yaitu 1. menjadi menarik untuk mencari interval suatu nilai demikian hingga solusi optimum yang ada tidak merubah.
Jika nilai C3 turun, ia tak berpengaruh terhadap solusi optimum yang ada. Namun, jika ia bertambah melebihi suatu nilai tertentu, barang C mungkin menjadi menguntungkan untuk diproduksi.
Jika nilai C3 berubah, nilai koefisien persamaan Z dari variabel non basis X3 pada tabel optimum turut berubah.
2. perubahan koeffisien fungsi tujuan variabel basis
pengaruh perubahan keuntungan per unit suatu barang. Jika barang pertama turun di bawah satu tingkat yang tertentu dapat menjadi tidak menguntungkan untuk memproduksi barang lainnya pula. Begitu juga sebaliknya. Sehingga terdapat suatu batas atas dan batas bawah dari pengaruh suatu barang yang dimana solusi optimum diberikan pada proses produksi sebelumnya.
3. perubahan koefisien fungsi tujan pada variabel basis dan non basis
Suatu kasus koefisien persamaan yang sederhana dapat mudah diselesaikan.
b. perubahan konstan sisi kanan.
Suatu tambahan satu unit buruh dapat terjadi, dan perusahaan ingin menentukan bagaimana pengaruh terhadap kombinasi produk optimum. Tambahan satu unit buruh mengubah vektor konstan sisi kanan pada tabel simpleks awal.
c. Solusi komputer
Masalah LP dengan software AB : QM. Menu linier programming pada software ini dapat juga mengerjakan analisis sensitivitas koefisien fungsi tujuan, Cj, dan konstan sisi kanan, bi
d. Perubahan matriks kendala (A)
Matriks kendala atau koefisien matriks A dapat berubah karena :
1. penambahan variabel variabel atau kegiatan kegiatan baru
bagian penelitian dan pengembangan perusahaan menganjurkan suatu produk baru barang yang membutuhkan 1 unit buruh dan 1 unit bahan mentah. Produk baru memiliki pasar yang cukup dan dapat dijual dengan keuntungan perunit sebesar 3. Yang dimana pihak perusahaan ingin mengetahui produksi menguntungkan atau tidak.
2. perubahan kebutuhan sumberdaya dari kegiatan kegiatan yang ada.
Pemenuhan atas kebutuhan bahan mentah atau buruh dari kegiatan nonbasis berubah, pengaruh pada solusi optimum dapat dipelajari dengan mengikuti langkah langkah yang sama. Disisi lain koefisien kendala dari suatu kegiatan basis berubah, maka matriks basis dengan sendirinya terpengaruh, yang pada gilirannya dapat mempengaruhi semua angka angka.
3. penambahan kendala baru.
Penambahan suatu kendala jasa administrasi terhadap masalah dimana barang a, b, dan c. Masing masing membutuhkan 1, 2, dan 1 jam jasa administrasi, sementara tersedia 10 jam administrasi. Jumlah ini akan menambah suatu kendala baru dalam bentuk :
X1 + 2x2 + x3 ≤ 10
Terhadap perumusan masalah asli. Untuk mempelajari pengaruh terhadap solusi optimum yang ada, cukup membuktikan apakah kombinasi barang optimum yang ada memenuhi kendala baru.