mkpk 7 lp simpl 2012
Post on 09-Aug-2015
46 Views
Preview:
DESCRIPTION
TRANSCRIPT
LINEAR PROGRAMMING METODA SIMPLEX
Pangestu Subagyo2012
Tujuan instruksional:
Setelah mempelajari topik/ materi kuliah ini, maka pembaca atau mahasiswa akan mampu:1. Membuat persamaan-persamaan
kendala dlm LP, dengan memasukkan slack variable, surplus variable dan artificial variable.
2. Memecahkan masalah LP dengan menggunakan Simplex tableaus.
3. Memahami arti setiap angka yang ada pada setiap tabel4. Memahami masalah-masalah khusus dlm
linear programming yang ada, misalnya infeasibility, unboundedness, dan degeneracy.
5. Melakukan analisis sensitivitas dengan menggunakan tabel-tabel simplex yang dihasilkan
6. Menyelesaikan dual problem berdasar primal problem yg dimiliki
Dalam metoda LP Simplex:
• Dlm metoda Simplex dikerjakan
dengan tabel, sehingga memungkinkan
masalah dengan variabel yg lebih banyak• diantara tabel-tabel yg feasible, dipilih tabel
yang terbaik (optimum) • Dengan prosedur tertentu
Untuk memudahkan pembahasannya:
• Mula-mula dipecahkan dengan masalah yang memiliki standard form
• Fungsi tujuan maximumkan, kemudian minimumkan
• Penyimpangan-penyimpangan dari bentuk standar
• Dual
Contoh: (data pada contoh metida grafik)
Suatu perusahaan menghasilkan mebel, yang mengasilkan meja, untuk selanjutnya T, dan kursi untuk selanjutnya disebut dengam C. Sumbangan terhadap lana setiap meja (T) = $ 70 dan setiap kursi $ 50. Untuk selanjutnya dapat dirumuskan dalam persamaan-persamaan sebagai berikut:
Fungsi tujuan: Max profit = $70T + $50C
Subyect to constraints:
2T + 1C < 100
4T + 3C < 240
T, C > 0
Merubah persamaanpersamaan kendala: • Fungsi kendala bertanda
pertidaksamaan (memakai tanda < ), yang berarti: “maksimum sumberdaya yang tersedia atau dapat digunakan”.
• Fungsi ini harus dirubah menjadi persamaan (memakai tanda = ).
• Dengan menambah slack variable, untuk menampung nilai ruas kanan dengan ruas kiri persamaan.
Kendala pertama:
• Mula-mula: 2T + 1C < 100• Dirubah menjadi: 2T + 1C + S1 = 100• S1 menampung beda nilai ruas kanan (2T +
1C) dengan ruas kanan (100). Kalau nilai ruas kiri lebih besar daripada ruas kanan, maka bedabya ditampung di S1.
• Lalau nilai ruas kanan sama dengan ruas nilai kiri mmaka nilai S1 = 0.
• Kendala kedua menjadi: 4T + 3C + S2 = 240
Disajikan dlm persamaan-persamaan yg lebih jelas:
• Fungsi tujuan:
Maximize profit:
Z = $70T +$50C + $0S1 +$0S2
• Kendala-kendala :
2T + 1C + 1S1 = 100
4T + 3C + 1S2 = 240
T, C, S1, S2 > 0
T = table, meja
C = chair = kursi
Atau:
• Fungsi tujuan:
Maximize profit:
Z = $70T + $0C + $0S1 + $0S2
• Kendala-kendala :
2T + 1C + 1S1 + 0S2 = 100
4T + 3C + 0S1 + 1S2 = 240
T, C, S1, S2 > 0
Profit Product Real Slack Constant per mix variable variable variableunit
1
2
3
4
Tabel 1. Tabel awal.
Cj SolutionMix
$70T
$50C
$0S1
$0S2
Quantity
$0$0
S1
S2
24
13
10
01
100 240
Zj
Cj - Zj
$0$70
$0$50
$0$0
$0$0
$0$0
Keterangan tabel:
1. Profit per unit row2. Constraint equation row3. Gross profit row4. Net profit row
Arti dari Tabel 1:
• Pada Tabel produk meja (T) = 0, dan kursi (C) juga 0,belum dihasilkan.
• T maupun C tidak ada dalam kolom production mix, berarti tidak/ belum dihasilkan.
• Kendala 1 dan kemdala 2 belum dipakai sama sekali, masih utuh, sehingga nilai S1 dan S2 masih seperti yang tersedia. S1 = 100 dan S2 = 240
• Nilai tujuan, Zj = profit/ unit
Kalau tabel awal disajikan dlm vector/
matrix: T 0 C 0
S1 = 100
S2 240 Berarti:
nilai T = 0, C = 0, S1 = 100 dan S2 = 240
Kalau misalnya diperoleh jawaban optimal:
T = 30 dan C = 40, Maka semua kendala sudah dipakai, berarti:
S1 = 0 dan
S2 = 0.
Andaikata dihasilkan meja (T) 30 buah dan kursi (C) 40 buah, maka:
• Sumberdaya cukup, dan habis semua• Sumberdaya 1 dipakai 2(30) + 1(40) = 100• Sumberdaya 2 dipakai 30(4) + 3(40) = 240
T 30 C 40
S1 = 0
S2 0
Substitution rate:
• Yang ada pada body dari tabel
• Kolom-kolom sbb:
T : 2 C: 1 S1: 1 S: 2
4 3 0 1
Objective function:
• Tambahka baris objective function, Cj , pada baris diatas body tabel.
• Profit per unit, ada pada baris Cj, disebut sebagai contribution rates.
• Profit per unit tidak hanya ada pada baris objective function, tetapi juga ada pada kolm. Tetapi yang ada pada kolom Cj hanyalah profit per unit dari variabel yg muncul di solution mix.
Tanda < dirubah menjadi =, dgn menambah slack variable.
S1 = slack kendala 1, jam kerja mesin
pengecatan yang tidak dipakai.
7T + 1C < 100
menjadi:
7T + 1C + S1 = 100
S2 = slack kendala 2, jam kerja
pertukangan yang tidak dipakai.
4T + 3C < 240
menjadi:
4T + 3C + S2 = 240
Tabel lengkap, dgn obyective function:
Cj Solution
Mix
$70 $50 $0 $0Quan-
tityT C S1 S2
$0$0
S1
S2
24
13
10
01
100240
Zj
Cj - Zj
$0$70
$0$50
$0$0
$0$0
$0$0
Tahap-tahap dlm metoda simplex:
1) Tentukan kolom kunci (KK) = pivot collumn, yaitu kolom yang nilai Cj
– Zj -nya positif terbesar.
Yaitu kolom T, sebab nilai Cj – Zj = $70, sedang kolom yg lain lebih rendah:
Cj – Zj positif terbesar
Cj Solution
Mix
$70 $50 $0 $0Quan-
tityT C S1 S2
$0$0
S1
S2
24
13
10
01
100240
Zj
Cj - Zj
$0$70
$0$50
$0$0
$0$0
$0$0
2) Tentukan baris kunci (pivot row),
dengan cara: - hitung indeks baris = nilai di kolom quantity , (nilai di
kolom kanan) dibagi nilai KK (kolom kunci) - pilih yg indeksnya positif terkecil. Berarti baris S1
Indeks baris positif terkecil:
Cj Solution
Mix
$70 $50 $0 $0Quan-
tityT C S1 S2
$0$0
S1
S2
24
13
10
01
100240
Zj
Cj - Zj
$0$70
$0$50
$0$0
$0$0
$0$0
100/2 = 50 240/40 = 60
3) Kita peroleh pivot number = angka
kunci = angka yg masuk dlm kolom kunci dan baris kunci. Dalam contoh kita = 2, dalam baris S1 dan kolom T.
Dalam contoh kita = 24) Hitung nilai baru dari baris kunci
(NBBK), dgn:
ALBK (angka lama di baris kunci) AK (angka kunci)
Niai baru baris kunci = NBBKdalam contoh kolom T
Pivot number = 2
T C S1 S2 Quantity
NBL 2 1 1 0 100
NBL/AK 2/2 1/2 1/2 0/2 100/2
NBB 1 1/2 1/2 0 50
5) Nilai baru baris non kunci:
NBB = [NBL] – [NLKK] x [NBBK]
Dalam contoh kita hanya baris S2:
Nil Brs Lama(NBL)
4 3 0 1 240
Nil Lm Kl Kunc(NLKK) pada baris ybs.
4 4 4 4 4
Nil Br Br Knc(NBBK)
1 ½ ½ 0 50
Nil. Baris Baru
0 1 -2 1 40
Kolom kunci dan baris kunci:
unci
Sol.Mix
$70 $50 $0 $0
Quantity
T C S1 S2
$0$0
S1
S2
24
13
10
01
100240
Zj
Cj - Zj
$0$70
$0$50
$0$0
$0$0
$0$0
Angka kunci:
Cj Sol.Mix
$70 $50 $0 $0Quantit
yT C S1 S2
$0$0
S1
S2
24
13
10
01
100240
Zj
Cj - Zj
$0$70
$0$50
$0$0
$0$0
$0$0
Perubahan pada Solution Mix:
• Pada kolom Cj , nilai di baris kunci diganti dengan nilai Cj - Zj . Dalam contoh kita = $70
• Kolom kunci diganti dengan variable di kolom kici, yaitu T
Angka kunci:
Cj Sol.Mix
$70 $50 $0 $0Quantit
yT C S1 S2
$0$0
S1
S2
24
13
10
01
100240
Zj
Cj - Zj
$0$70
$0$50
$0$0
$0$0
$0$0
Nilai T dan S2:
Cj Solution
MixT C S1 S2
Quantity
$ 70$ 0
TS2
10
0.51
0.5-2
01
5040
Nilai Z baru:
Zj , kolom T ($70)(1) + ($0)(0) $70
Zj , kolom C ($70)(0.5) + ($0)(1)
$35
Zj , kolom S1
($70)(0.5) + ($0)(-2)
$35
Zj , kolom S2
($70)(0) + ($0)(1) $0
Zj , kolom Z ($70)(50) + ($0)(40)
$3,500
Net profit:
KolomT C S1 S2
Cj
Zj
$70$70
$50$35
$0$35
$0$0
Cj - Zj $0 $15 -$35 $0
Tabel kedua:
Cj Sol.Mix
$70 $50 $0 $0
Quan-tity
T C S1 S2
$70$0
TS2
10
0.51
0.5-2
01
5040
Zj
Cj - Zj
$70$0
$35$15
$35-$35
$0$0
$3500
Tabel kedua:
Cj Sol.Mix
$70 $50 $0 $0
Quan-tity
T C S1 S2
$70$0
TS2
10
0.51
0.5-2
01
5040
Zj
Cj - Zj
$70$0
$35$15
$35-$35
$0$0
$3500
Nilai pada baris (Cj - Zj ) :
• Bila 0 atau negatif berarti optimal
• Kalau ada yang positif berarti masih belum optimal, masih dapat diperbaiki
• Pada kolom C nilainya $15, berarti belum optimal.
Diulang/ diteruskan lagi sampai optimal.
Tabel ketiga:
Cj Sol.Mix
$70 $50 $0 $0Quan-
tityT C S1 S2
$70$50
TC
10
01
1.5-2
-0.51
3040
Zj
Cj - Zj
$70$0
$50$0
$5-$5
$15-$15
$4100
Optimal, sebab di baris (Cj - Zj) tidak
ada yang positif, yang hanya 0 atau negatif.
Penyimpangan dari bentuk baku (standard form):
Penyimpangan dari bentuk baku (standard form):• Kendala fungsional bertanda >• Kendala fungsional bertanda =• Fungsi tujuan meminimumkanegat• Kendala non negatif tidak betanda
> 0
Surplus Variable
• Pada pembahas sebelumnya, kita –masalah bahas masalah yang kendala fungsionalnya bertanda <.
• Dalam kenyataan, banyak masalah yg kendala fungsionalnya bertanda >.
• Menyimpang dari bentuk baku, harus ada penyesuaian.
Mis. suatu masalah dgn formls. sbb:
Fungsi tujuan: Max. Z = $5X1 + $9X2 + $7X3’l + $0S1 +
(1)5X1 + 10X2 + 8X3 > 210
(2) 25X1 + 30X2 = 900
(3) X1 , X2 ,X3 > 0
- Diluar bentuk standar- Harus dilakus dilakukan penyesuaian.
Kendala pertama (1):5X1 + 10X2 + 8X3 > 210
- Ditambah surplus variable, - mirip slack variable tetapi negatif - simbolnya juga Sj, tetapi negatif.
5X1 + 10X2 + 8X3 - S1 = 210
Asumsi: stiap variabel hrs brtanda > 0tidak dipenuhi, tdk dpt dikrjkn dgn LP.
Berarti S1 bertanda negarif.
- Bila semua var. brnil 0 (X1, X2, X3 = 0),
- maka nilai S1 = -210
- tidak dapat dikerjakan- Harus ditambah artificial variable- Persamaannya menjadi: 5X1 + 10X2 + 8X3 - S1 + A1 = 210
- Lalu dikerjakan dgn LP
• Nilainya (nilai variabel A1) = 0
• Setiap digunakan A1, pada fungsi tujuan harus ditam M.
• Nilai M itu besar sekali, ttp tidak takterhingga (bukan ∞)
• Kendala kedua: 25X1 + 30X2 = 900
• Sudah berbentuk persamaan (bertanda =)
• Tetapi belum memiliki slack variable
• Harus ditambah artificial variable• Hasilnya: 25X1 + 30X2 + A2 = 900
• Contoh ini akan diselesaikan kalau datan lengkap.
• Sebab kalau fungsi tujuannya memaksimumkan, hasilnya (X1, X2, X3 ) = 0.
• Bila fungsi tujuan:Minimumkan Z = $5X1 + $9X2 + $7X1
Persamaan semuanya:
Fungsi tujuan: Max. Z = $5X1 + $9X2 + $7X1 + $0S1 + $MA1 + $MA2
Fungsi kendala: 5X1 + 10X2 + 8X3 - 1S1 + 1A1 + 0A2 = 210
25X1 + 30X2 + 0X3 + 0S1 + 0A1 + 1A2 = 900
X1 , X2 , X3 , A1 , A2 > 0
Untuk sementara hasilnya tidak dijawab, semam minimiwsasi belum dibahas.
TUJUANNYA MEMINIMUMKAN
Langkah-langkahnya:• Pilih variabel (dlm kolom) yang nilai
di baris Cj – Zj paling negatif, sebagai kolom kunci (pivot collumn)
• Tentukan baris kunci (pivot row) yg nilai indeksnya positif terkecil.
• Hitunglah nilai baru baris kunci
• Menghitung nilai Zj dan Cj – Zj pada tabel terbaru di tahap ini.
Tabel awal minimumkan :
Cj Sol.Mix
$5 $6 $0 $0 $M $M Quan-tityX1 X2 S1 S2 A1 A2
$M$0$M
A1
S1
A2
110
101
010
00-1
100
001
1000300150
Zj
Cj - Zj
$M-
$M+5
$2M-
$M+6
$0$0
-$M$M
$$0
$M$0
$1150M
Tabel awal dgn pivot collumn, pivot raw, pivot number:Cj Sol.
Mix$5 $6 $0 $0 $M $M Quan-
tityX1 X2 S1 S2 A1 A2
$M$0$M
A1
S1
A2
110
101
010
00-1
100
001
1000300150
Zj
Cj - Zj
$M-
$M+5
$2M-
$M+6
$0$0
-$M$M
$$0
$M$0
$1150M
Pivot collumn Pivot number Pivot row
Tabel kedua:
Cj Sol.Mix
$5 $6 $0 $0 $M $M Quan-tityX1 X2 S1 S2 A1 A2
$M$0$6
A1
S1
X2
110
001
010
10-1
100
-101
850300150
Zj
Cj - Zj
$M-
$M+5
$2M-
$M+6
$0$0
-$M$M
$$0
$M$0
$1150M
Tabel kedua, kolom kunci, baris cunci dan angka kunci:
Cj Sol.Mix
$5 $6 $0 $0 $M $M Quan-tity
X1 X2 S1 S2 A1 A2
$M$0$6
A1
S1
X2
110
001
010
10-1
100
-101
850300150
Zj
Cj - Zj
$M-$M+5
$6$0
$0$0
$M-6-
$M+6
$M$0
-$M+6$2M-6
$850M+$900
Tabel ketiga:
Cj Sol.Mix
$5 $6 $0 $0 $M $M Quan-tity
X1 X2 S1 S2 A1 A2
$M$5$6
A1
X1
X2
010
001
-110
10-1
100
-101
550300150
Zj
Cj - Zj
$5$0
$6$0
-$M+5$M-5
$M-6-
$M+6
$M$0
-$M+6$2M-6
$550M+$2400
Tabel keempat:
Cj Sol.Mix
$5 $6 $0 $0 $M $M Quan-tity
X1 X2 S1 S2 A1 A2
$0$5$6
S2
X1
X2
010
001
-11-1
100
101
-100
550300700
Zj
Cj - Zj
$5$0
$6$0
-$1$1
$0$0
$6$M-6
$0$M
$5700
Penggunaan QM for Windows:
Fungsi tujuan: Max profit = $70 X1 + $50 X2
Subyect to constraints:
2 X1 + 1 X2 < 100
4 X1 + 3 X2 < 240
X1, X2 > 0
Soal-soal:1. Kerjakanlah soal nomer 1 metoda grafik, gunakan metoda Simplex.
2. Kerjakanlah soal nomer 2 metoda grafik, gunakan metoda Simplex.
3. Perusahaan makanan ternak Prabujaya menghasilkan makanan ternak, yaitu type I, type II dan type III. Untuk membuat satu kantong makanan ternak type I diperlukan bahan baku A sebanyak 9 kg, bahan baku B sebanyak 12 kg dan bahan baku C sebanyak 18 kg.
Untuk membuat satu kantong makanan ternak
type II diperlukan bahan baku A sebanyak 3 kg, bahan baku B sebanyak 8 kg dan bahan baku C sebanyak 6 kg. Dan untuk membuat satu kantong makanan ternak type III diperlukan bahan baku A sebanyak 12 kg, bahan B baku sebanyak 5 kg dan bahan baku C sebanyak 15 kg. Sumbangan terhadap laba, setiap kontong makanan ternak type Rp 6 000,-, makanan ternak type II Rp 9 000 dan makanan ternak type III Rp 3 000,-. Jumlah bahan bakuA yang tersedia sebanyak 54 ton, bahan baku B sebanyak 64 tn dan bahan baku C sebanyak 63 ton. Buatlah rumusan masalah perencanaan jumlah produksi ini, buatlah fungsi tujuan dan fungsi-fungsi kendalanya.
Rumuskan masalah ini kedalam
persamaan-persamaan, tidak usah dicari rencana produksinya.
4. Suatu masalah dapat dirumuskan didalam persamaan-persamaan berikut:
Fungsi tujuan: Maks. Z = 30X1 + 10X2
Kendala-kendala: (1) 3X1 + 6X2 < 18 (2) 5X1 + 2X2 < 10 (3) X1, X2 > 0 Carilah jawaban optimalnya, gunakan linear programming metoda Simplex!
5. Perusahaan roti Arumi menghasilkan dua
macam roti, yaitu roti dengan merk Sukaku dan merk Sukamu. Faktor yang membatasi pembuatan roti ini adalah gandum, gula pasir dan keju. Untuk membuat satu kaleng roti merk Sukaku diperlukan gandum 0,5 kg, gula 0,20 kg dan keju 0,25 kg. Sedang untuk membuat satu kaleng roti merk Sukamu diperlukan gandum 0,40 kg, gula pasir 0,40 kg dan keju 0,30 kg
Untuk bulan depan banyaknya gandum yang tersedia sebanyak 1 250 kg, gula pasir 600 kg dan keju 720 kg. Sumbangan terhadap laba untuk setiap kaleng roti merk Sukaku Rp 2 500,- sedang setiap kaleng merk Sukamu Rp 3 000,-. Kit akan merencanakan jumlah produksi setiap merk roti untuk bulan depan.
a) Buatlah formulasi masalah ini kedalam persamaan-persamaan linier agar dapat dikerjakan dengan liner programming!
b) Carilah keputusan optimalnya dengan pendekatan grafik!
c) Carilah keputusan optimalnya dengan pendekatan Simplex
top related