lp linear program

KASUS KHUSUS PROGRAM LINEAR

(1). SOLUSI OPTIMUM GANDA Jika fungsi tujuan sejajar dengan fungsi kendala, maka akan terjadi nilai optimum yang sama pada lebih dari satu titik solusi. Keadaan ini dinamakan “Optimum Ganda” atau “Optimum Alternatif”. Contoh: 1. Fungsi Tujuan : Maksimumkan : Z = 2 X1 + 4 X2

2. Fungsi Kendala :2.1. 2 X1 + 4 X2 52.2. X1 + X2 4 X1 , X2 0

Penyelesaian :1. Metode Grafik X2

X1 + 2 X2 5

A

X1 + X2 4 B

O C X1

ZC ZA dan ZB

a). Titik O(0,0) : ZA = 0b). Titik A(0,5/2): ZA = 2(0) + 4(5/2) = 10c). Titik B(3,1) : ZB = 2(3) + 4(1) = 10d). Titik C(5,0) : ZC = 2(5) + 4(0) = 10

2. Metode Simpleks : ---------------------------------------------------------------------------------------------------------------- Variabel X1 X2 S1 S2 NK

Indeks Dasar -----------------------------------------------------------------------------------------------------------------

Z -2 -4 0 0 0

S1 1 2 1 0 5 5/2 S2 1 1 0 1 4

3/2

-----------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------- Variabel X1 X2 S1 S2 NK

Indeks Dasar -----------------------------------------------------------------------------------------------------------------

Z 0 0 2 0 10

X2 1/2 1 1/2 0 5/2 5 S2 1/2 0 -1/2 1 3/2 3

-----------------------------------------------------------------------------------------------------------------

Z 0 0 2 0 10

X2 0 1 1 0 1 X1 1 0 -1 2 3

-----------------------------------------------------------------------------------------------------------------

Alternatif Optimal : 1). X1 = 0; X2 = 5/2; Zmaks.= 10. 2). X1 = 3; X2 = 1; Zmaks.= 10

(2). SOLUSI TAK TERBATAS Pada beberapa model PL, nilai variabel mungkin

bertambah tak terbatas tanpa menyimpang dari kendala, berarti bahwa ruang solusi menjadi tak terbatas sekurang-kurangnya pada satu arah. Akibatnya, nilai fungsi tujuan dapat bertambah tanpa pernah mencapai batas fungsi kendala. Dalam keada- an ini dikatakan bahwa baik ruang solusi maupun nilai tujuan optimum adalah tak terbatas. Contoh : 1. Fungsi Tujuan : Maksimumkan : Z = 2X1 + X2

2. Fungsi Kendala : 2.1. X1 - X2 10

2.2. 2X1 40 X1 , X2 0

Penyelesaian :1. Metode Grafik : X2 Ruang Solusi Tak Terbatas

X1-X2 10

X1 40

X1

(2). Metode Simpleks : _______________________________________________________________________

Variabel X1 X2 S1 S2 NK Indeks Dasar -----------------------------------------------------------------------------------------------------------------

Z -2 -1 0 0 0

S2 1 -1 1 0 10 10 S2 2 0 0 1 40 20

-----------------------------------------------------------------------------------------------------------------

Z 0 0 2 0 20

X1 0 -1 1 0 10 - S1 1 1 -1 1 30 30

----------------------------------------------------------------------------------------------------------------- Z 3 0 1 3 110

X1 0 0 0 1 30 - X2 1 1 -1 1 30 -

-----------------------------------------------------------------------------------------------------------------

(3). DEGENERASI Dalam penerapan feasibility condition, jika terdapat rasio minimum kembar, maka pemilihan leaving variabel dilaku- kan secara sembarang. Jika ini terjadi, satu atau lebih variabel dasar akan sama dengan nol pada iterasi berikutnya Dalam kasus ini, solusi mengalami “DEGENERASI”. Berdasarkan pengalaman, degenerasi muncul jika model memiliki sekurang-kurangnya sebuah kendala yang berlebih- an. Celakanya, tidak ada teknik untuk mengalokasikan secara langsung dari fungsi kendala mana yang berlebih.

Contoh 1 :1. Fungsi Tujuan :

Maksimumkan : Z = 3 X1 + 9 X2

2. Fungsi Kendala : 2.1. X1 + 4X2 8 2.2. X1 + 2X2 4

X1 ,X2 0 X1 3 X1 + 9 X2

Penyelesaian :(1). Metode Grafik

X1 + 4X2 8

X1 + 2X2 4

X2

(2). Metode Simpleks : ____________________________________________________________________

Variabel X1 X2 S1 S2 NK Indeks Dasar ------------------------------------------------------------------------------------------------- Z -3 -9 0 0 0 S1 1 4 1 0 8 4 S2 1 2 0 1 4 4 -------------------------------------------------------------------------------------------------- Z -3/4 0 9/4 0 18 X2 1/4 1 1/4 0 2 8 S2 1/2 0 -1/2 1 0 0

-------------------------------------------------------------------------------------------------- Z 0 0 3/2 3/2 18 X2 0 1 1/2 -1/2 2 X2 1 0 -1 2 0

---------------------------------------------------------------------------------------------------

Degenerasi memiliki dua pengaruh :(1). Peristiwa cycling, yaitu tidak terjadi perbaikan

nilai solusi meskipun iterasi terus terjadi.(2). Dalam iterasi 1 dan 2, meskipun klasifikasi var.

dasar dan non dasar berbeda, akan menghasilkan nilai fungsi tujuan yang sama.

Berdasarkan gagasan ini timbul kemungkinan untukmenghentikan perhitungan pada iterasi 1 (ketika

gene-rasi pertama muncul), bahkan meskipun pada iterasiitu belum optimum. Kita akan membantah gagasan

inidengan melihat contoh berikut ini.

Contoh 2 :(1). Fungsi Tujuan : Maksimumkan : Z = 3 X1 + 2 X2

(2). Fungsi Kendala : 2.1. 4 X1 + 3 X2 12

2.2. 4 X1 + X2 8 2.3. 4 X1 - X2 8

X1 , X2 0

Penyelesaian : (1). Metode Grafik X2

4X1- X2 8

4X1+X2 8

4X1+3X2 12

Z=3X1+2X2 X1

(2). Metode Simpleks :---------------------------------------------------------------------------------------------------------Var Dasar X1 X2 S1 S2 S3 NK Indeks-------------------------------------------------------------------------------------------------------- Z -3 -2 0 0 0 0 S1 4 3 1 0 0 12 3 S2 4 1 0 1 0 8 2 S3 4 -1 0 0 1 8 2--------------------------------------------------------------------------------------------------------- Z 0 -5/4 0 3/4 0 6 S1 0 2 1 -1 0 4 2 X2 1 1/4 0 1/4 0 2 8 S3 0 -2 0 -1 1 0 ---------------------------------------------------------------------------------------------------------- Z 0 0 5/8 1/8 0 17/2 X2 0 1 1/2 -1/2 0 2 X2 1 0 -1/8 3/8 0 3/2 S3 0 -2 0 -1 1 0 ----------------------------------------------------------------------------------------------------------

Pada contoh 2 ini, degenerasi muncul pada iterasi 1.Perhatikan bahwa pada iterasi kedua, degenerasi tidakterlihat dan nilai fungsi tujuan berubah dari 6 menjadi17/2. Kesimpulan dari kedua contoh ini adalah bhwiterasi simpleks harus diteruskan sampai iterasi

terakhiryang memenuhi optimality condition.Disamping NK minimum kembar, dapat pula terjadikoefisien pada persamaan Z yang kembar dalam apli-kasi optimality condition. Dlm hal ini entering var.dipilih secara sembarang di antara nilai kembar itu.Tidak ada pilihan yg salah, meskipun pemilihan adalah satu var dapat mengakibatkan iterasi yg lebih banyak.

PENAFSIRAN TABEL SIMPLEKSBanyak masalah-maslah dlm praktek yg dirumuskansebagai PL menggunakan ratusan kendala dan ribuanvariabel keputusan. Menjadi tidak perlu

menyelesaikanmasalah PL itu dengan perhitungan tangan, sebagaigantinya digunakan komputer. Dalam penyelesaianmodel PL, akan terasa bahwa banyak waktu yg diper-lukan utk pembentukan model, pengumpulan data danmenyiapkan input utk dicocokan dengan kode kompu-ter. Jika ini telah dilakukan, komputer akan mengambilalih dan memberikan solusi optimal.

Tabel simplek optimum bukan sekedar suatu daftarvariabel dan nilai optimumnya, tetapi ia dipenuhi

dgninformasi-informasi, termasuk nilai optimum

variabel-variabel. Informasi yang dapat diperoleh dari Tabelsimpleks baik secara langsung maupun dgn

tambahanperhitungan sederhana adalah :(1). Solusi Optimum.(2). Keadaan Sumberdaya.(3). Sumbangan per unit Sumberdaya.(4). Kepekaan solusi optimum terhadap perubahan

tersedianya sumberdaya, koefisien fungsi tujuan, dan konsumsi sumberdaya oleh setiap kegiatan.

(1). SOLUSI OPTIMUM 1. Fungsi Tujuan :

Maksimumkan Profit : Z = 3X1 + 2X2

2. Fungsi Kendala : 2.1. Tenaga Kerja : X1 + X2 15

2.2. Kayu : 2X1 + X2 28 2.3. Paku : X1 + 2X2 20 X1 , X2 0

dimana : X1 , X2 adalah jumlah produksi kursi

dan meja.

Tabel Simpleks Optimum :-------------------------------------------------------------------------------------------------------

--Var Dasar X1 X2 S1 S2 S3 NK-------------------------------------------------------------------------------------------------------

-- Z 0 0 1 1 0 43

X2 0 1 2 -1 0 2 X1 1 0 -1 1 0 13 S3 0 0 -3 1 1 3-------------------------------------------------------------------------------------------------------

- Var. Keputusan Nilai Optimum Keputusan

X1 13 Kursi = 13X2 2 Meja = 2Z 43 Profit = 43

(2). Keadaan Sumberdaya : Kendala digolongkan dua, yaitu langka dan ber- lebihan, tergantung solusi optimal mengkonsumsi seluruh ketersediaan (kapasitas) sumberdaya yang bersangkutan. Berbicara sumberdaya secara tidak langsung menyatakan bahwa ada suatu pembatas maksimum ketersediaannya yang berarti bahwa kendala harus berjenis, sehingga kendala jenis bukan menunjukkan suatu pembatas sumberdaya, tetapi mereka lebih menyatakan bahwa solusi hrs memenuhi kebutuhan tertentu, seperti kepuasan minimum dan permintaan minimum.

Keadaan sumberdaya (langka atau berlebihan) padasetiap model PL dapat ditentukan secara langsung dariTabel Optimum dengan mengamati nilai variabel slack,sebagai berikut :Sumberdaya Slack Var. Keadaan SumberdayaTenaga Kerja S1= 0 LangkaKayu S2= 0 LangkaPaku S3= 1 BerlebihSuatu slack var positif berarti sumberdaya tdk diguna-kan seluruhnya (berlebih), sedangan slack var = 0 me-nunjukkan seluruh jlh sumberdaya dikonsumsi olehkegiatan-kegiatan dalam model.

Dari hasil solusi optimum menunjukkan sumberdayaketiga (S3), yaitu paku berlebih, artinya penambahanpaku hanya membuat paku makin berlebihan tanpamemperbaiki solusi optimum. Peningkatan jumlahtenaga kerja dan kayu akan memperbaiki solusi opti-mum karena masih langka.(3). Sumbangan per Unit SumberdayaSumbangan sumberdaya per unit adalah tingkat per-baikan dalam nilai optimum sebagai akibat kenaikanjumlah ketersediaan sumberdaya tersebut. Hal ini dptdilihat dari koefisien persamaan Z dibawah var dasarawal (S1, S2, dan S3) seperti berikut ini.

--------------------------------------------------------------------------------------------------------Var Dasar X1 X2 S1 S2 S3 NK--------------------------------------------------------------------------------------------------------

Z 0 0 1 1 0 43--------------------------------------------------------------------------------------------------------

Koefisien sebesar 1, artinya jika sumberdaya ditambah1 unit maka nilai fungsi tujuan bertambah 1. Koefisiensebesar 0, artinya jika sumberdaya ditambah maka nilai fungsi tujuan tidak akan berubah (karena sumber-daya yang digunakan berlebih). Nilai-nilai tersebut di-sebut dengan “Shadow Price”. Shadow Price adalahsumbangan dari perubahan satu unit sumberdaya ter-hadap fungsi tujuan.