B. Persoalan Batasan Campuran p `
Tempat kerajinan membuat tas kantor dan tas kulit. Laba tas kantor $ 400 dan laba tas koper $ 200.
Tempat
kerajinan
tersebut
harus
menyediakan untuk pelanggan 30 tas setiap bulannya. Pabrik kulit menyuplai sedikitnya 80 yard persegi kulit perbulan. Setiap tas kantor perlu 2 yard persegi kulit, sedangkan setiap tas k koper memerlukan l k 8 yard d persegi. i Pemilik P ilik tempat t t kerajinan
mengetahui
bahwa
tidak
mungkin
memproduksi tas kantor lebih dari 20 perbulan. `
Formulasi Model Program Linear : Maksimumkan Z = 400x1 + 200x2 Batasan
x1 + x2 = 30 kebutuhan pelanggan
2x1 + 8 x2 ≥ 80 ketersediaan kulit x1 ≤ 20 tas kantor x1,, x2 ≥ 0 x1 = tas kantor, x2 = tas koper
`
Langkah pertama mengubah pertidaksamaan menjadi persamaan.
`
B t Batasan k b t h pelanggan kebutuhan l x1 + x2 = 30. Tes pada titik pangkal, yaitu x1 = 0 dan x2 = 0,, maka x1 + x2 = 30 0 + 0 = 30 perlu ditambahkan peubah artifisial sehingga persamaan menjadi x1 + x2 + A1 = 30 sehingga batasan menjadi x1 + x2 + A1 = 30. Karena fungsi tujuannya memaksimumkan dan peubah artifisial tidak memiliki arti maka peubah A1 diberi g A1 dari formulasi. koefisien –M yyangg akan otomatis mengeluarkan
`
Batasan ketersediaan kulit adalah suatu pertidaksamaan ≥, sehingga batasan ini menjadi 2x1 + 8 x2 – s1 + A2 = 80
`
Batasan tas kantor kant r adalah suatu s at pertidaksamaan ertidaksamaan ≤, ≤ sehingga sehin a menjadi x1 + s2 = 20
Formulasi program linear di atas menjadi :
`
maksimumkan Z = 400x1 + 200x2 + 0s1 + 0s2 – MA1 – MA2 batasan x1 + x2 + A1 = 30 2x1 + 8 x2 – s1 + A2 = 80 x1 + s2 = 20 x1, x2, s1, s2, A1, A2 ≥ 0 Tabel simpleks awal :
`
Variabel Dasar
cjj
Kuantitas i
400
200
0
0
-M
-M
x1
x2
s1
s2
A1
A2
-M
A1
30
1
1
0
0
1
0
-M
A2
80
2
8
-1
0
0
1
0
s1
20
1
0
0
1
0
0
zj
-110M
-3M
-9M
M
0
-M
-M
400+3M
200+9M
-M
0
0
0
cj - zj
Tabel simpleks kedua
`
Variabel Dasar
cjj
K Kuantitas tit
400
200
0
0
-M
x1
x2
s1
s2
A1
-M
A1
20
¾
0
1/8
0
1
200
X2
10
¼
1
-1/8
0
0
0
s2
20
1
0
0
1
0
zj
2000-20M
50-3M/4
200
-25-M/8
0
-M
350+3M/4
0
25+M/8
0
0
cj - zj
Tabel simpleks ketiga
`
Variabel Dasar
cj
Kuantitas
400
200
0
0
-M
x1
x2
s1
s2
A1
-M
A1
5
0
0
1/8
-3/4
1
200
x2
5
0
1
-1/8
-1/4
0
400
x1
20
1
0
0
1
0
zjj
9000 5M 9000-5M
400
200
-25-M/8 25 M/8
3/4M+350
-M M
0
0
25+M/8
-350-3M/4
0
cj - zj
Tabel simpleks optimal
`
Variabel V i b l Dasar
cj
Kuantitas
400
200
0
0
x1
x2
s1
s2
0
S1
40
0
0
1
-6
200
x2
10
0
1
0
-1
400
x1
20
1
0
0
1
zj
10.000
400
200
0
200
0
0
0
-200
cj - zj
`
Solusinya, x1( tas kantor ) = 20, x2 ( koper ) = 10, s1( kulit yang tidak terpakai ) = 40, Z ( keuntungan perbulan ) = $10.000
`
Aturan untuk merubah ketiga jenis batasan adalah : Batasan
Penyesuaian
Koefisien Fungsi Tujuan Maksimumkan
Minimumkan
≤
Tambah peubah pengurang
0
0
=
Tambah peubah artifisial
-M
M
≥
Kurang peubah penambah
0
0
dan tambah peubah artifisial
-M
M
C. Program Linear yang tidak teratur ( Ireguler l ) Persoalan-persoalan khusus yang dapat timbul pada program li linear adalah d l h solusi l i optimal ti l lebih l bih dari d i satu, t tidak tid k terdapat t d t daerah d h solusi yang feasibel, daerah solusi tidak terbatas, kolom pemutar lebih dari satu, baris pemutar lebih dari satu (degenerasi), dan nilai kuantitas yang negatif. 1.
Solusi Optimal Majemuk
`
Misalkan kasus pembuatan mangkok dan cangkir fungsi
tujuannya diubah dari Z = 4x1 + 5x2 menjadi Z = 4x1 + 3x2 `
Formulasi program linearnya :
Maksimumkan Z = 4x1 + 3x2 Batasan x1 + 2x2 ≤ 40 jam tenaga kerja 4x1 + 3x2 ≤ 120 pon tanah liat x1 x2 ≥ 0 x1, x1 = banyaknya mangkok yang diproduksi x2 = banyaknya cangkir yang diproduksi
`
Grafik untuk formulasi PL
`
Grafik menunjukan bahwa solusi maksimum ada pada garis B dan C. Tabel simpleks optimal
`
Variabel Dasar
cj
4
3
0
0
x1
x2
s1
s2
0
s1
10
0
5/4
1
-1/4
4
x1
30
1
¾
0
¼
zj
120
4
3
0
1
0
0
0
-1
cj - zj
`
Kuantitas
Tabel diatas berhubungan dengan titik C pada grafik. Menentukan solusi titik akhir alternatif maka x2 dapat p dijadikan j sebagai g kolom pemutar.
Tabel optimal alternatif
`
Variabel Dasar
cj
Kuantitas
3
0
0
x1
x2
s1
s2
3
x1
8
0
1
4/5
-1/5
4
x2
24
1
0
-3/5
2/5
zj
120
4
3
0
1
0
0
0
-1
cj - zj
`
4
Solusi optimal majemuk menjadikan pengambil keputusan mempunyai lebih banyak alternatif.
2.
Persoalan Daerah Solusi tidak Feasible
`
Contoh ppersoalan yyangg tidak feasible adalah
Maksimumkan Z = 5x1 + 3x2 Batasan 4x1 + 2x2 ≤ 8 x1 ≥ 4 x2 ≥ 6 x1, x2 ≥ 0
Grafik formulasi model PL nya
`
Titik A hanya memenuhi batasan 4x1 + 2x2 ≤ 8, sedangkan titik B hanya memenuhi x1 ≥ 4 dan x2 ≥ 6. Model ini tidak mempunyai solusi. Tabel simpleks akhirnya sbb : cj
Variabel Dasar
Kuantitas
400
200
0
0
0
-M
-M
x1
x2
s1
s2
s3
A1
A2
3
x2
4
2
1
½
0
0
0
0
-M
A1
4
1
0
0
-1
0
1
0
-M
A2
2
-2
0
-1/2
0
-1
0
1
zj
12-6M
6+M
3
3/2+M/2
M
M
-M
-M
-1-M
0
-3/2-M/2
-M
-M
0
0
cj - zj
Baris cj – zj memiliki nilai nol atau negatif, dan adanya peubah artifisial pada variabel dasar tidak berarti apa-apa.
3.
Persoalan tidak Terbatas
B b Beberapa persoalan l PL memiliki iliki batasan b t tid k tertutup. tidak t t t Dalam D l hal ini fungsi tujuan naik secara tidak terbatas. Contoh : Maksimumkan Z = 4x1 + 2x2 Batasan x1 ≥ 4 x2 ≤ 2 x1, x2 ≥ 0 Grafik dari model LP tersebut adalah :
P d grafik Pada f k fungsi f tujuan naikk tanpa ada d akhirnya. kh
Tabel simpleks kedua kasus solusi tanpa batas
`
Variabel Dasar
cj
Kuantitas
4
2
0
0
x1
X2
s1
s2
4
x1
4
1
0
-1
0
0
s2
2
0
1
0
1
zj
16
4
0
-4
0
0
2
4
0
cj - zj
Pada tabel simpleks rasio kuantitas terhadap nilai pada kolom pemutar bernilai negatif atau tak terhingga. 4. Kolom Pemutar yang Seri Kadang-kadang g g ada lebih dari satu kolom yyangg memiliki nilai positif terbesar pada baris cj-Zj atau Zj–cj. Pada saat terjadi seperti ini pilihlah kolom pemutar secara acak dari kolom-kolom calon kolom pemutar tersebut. tersebut Satu kolom pemutar memerlukan tabel simpleks lebih sedikit dibandingkan kolom pemutar lainnya.
5. Baris Pemutar yang Seri-Degenerasi Calon baris pemutar bisa memiliki rasio antara kuantitas dan elemen pada kolom bernilai sama. Dalam kasus ini pilihlah satu baris dari barisbaris calon baris pemutar terebut secara acak. Pada kasus seperti ini, p akan memiliki nilai kuantitas nol dan kasus ini baris yyangg tidak dipilih disebut degenerasi. `
Berikut adalah persoalan baris pemutar ganda.
Maksimumkan Z = 4x1 + 6x2 Batasan 6x1 + 4x2 ≤ 24 x2 ≤ 3 5x1 + 10x2 ≤ 40 x1, x2 ≥ 0 Tabel simpleks keduanya sebagai berikut cj
Variabel Dasar
Kuantitas
4
6
0
0
0
x11
X2
s1 1
s2 2
s3 3
0
s1
12
6
0
1
-4
0
6
x2
3
0
1
0
1
0
0
s3
10
5
0
0
-10
1
Zj
18
0
6
0
6
0
4
0
0
-6
0
cj - Zj
`
Baris s3 dipilih secara acak sebagai baris pemutar, kemudian menghasilkan h ilk tabel t b l simpleks i l k ketiga k ti Variabel Dasar
cj
Kuantitas
4
6
0
0
0
x1
x2
s1
s2
s3
0
s1
0
0
0
1
8
-6/5
6
x2
3
0
1
0
1
0
4
x1
2
1
0
0
-2
1/5
Zj
26
4
6
0
-2
4/5
0
0
0
2
-4/5
cj - Zj
`
Perhatikan s1 bernilai nol. Berarti s1 adalah rasio kuantitas dan elemen kolom pemutar positif yang paling kecil. Tabel optimal sebagai berikut : cj
Variabel Dasar
Kuantitas
4
6
0
0
0
x1
x2
s1
s2
s3
0
s2
0
0
0
1/8
1
-3/2
6
x2
3
0
1
-1/8
0
3/20
4
x1
2
1
0
¼
0
-1/10
Zj
26
4
6
¼
0
½
0
0
-1/4
0
-1/2
cj - Zj
`
Proses degenerasi pada kasus tersebut terlihat pada grafik.
6. Kuantitas Bernilai Negatif Seringkali kuantitas bernilai negatif. Contohnya 6x1 + 2x2 ≥ -30 oleh karena itu agar metode simpleks bekerja pertidaksamaan tersebut dikalikan dengan -1 sehingga menjadi -6x1-2x2 ≤ 30.
Kesimpulan dari tabel simpleks ireguler adalah : `
S l bersifat Solusi b f majemukk diidentifikasi d d f k oleh l h nilai l cj-Zj Z = 0 atau Zj Z – cj = 0 untuk peubah bukan dasar. Solusi alternatif diperoleh dengan memasukan peubah yang memiliki cj – Zj = 0 atau Zj – cj = 0 pada peubah dasar.
`
Solusi infeasible terdeteksi ketika cj – Zj ≤ 0 atau Zj – cj ≤ 0 dan pada variabel dasar ada peubah artifisial.
`
Persoalan tak terbatas teridentifikasi ketika rasio nilai kuantitas dan elemen kolom pemutar bernilai negatif atau tek hingga.
`
Persoalan kolom pemutar lebih dari satu diatasi dengan memilih salah satu kolom-kolom tersebut secara acak.
`
Persoalan baris pemutar lebih dari satu diatasi dengan memilih salah satu baris tersebut secara acak dan akan timbul degenerasi.
`
Persoalan nilai kuantitas negatif diatasi dengan mengalikan batasan tersebut dengan -1.
