20140311_modul2--lpsimpleks
Post on 23-Nov-2015
83 Views
Preview:
DESCRIPTION
TRANSCRIPT
-
Linier Programming Simplex MethodRiski Aditya
Operation Research
-
Pre-Test (Dalam 10 Menit)
Sebuah lembaga penelitian di DI.Yogyakarta hendak
menyebarkan 10000 kuesioner (harus habis) ke dua
pulau, yaitu P. Sumatra dan P. Bali.Ongkos kirim P.
Sumatra Rp 1.200,- per kuesioner dan Bali Rp 1.000,-
per kuesioner. Jumlah kuesioner yang dikirim ke Bali
paling sedikit 3000 kuesioner dan untuk Sumatra paling
sedikit 1500 kuesioner. Berapa komposisi kuesioner yang
harus dikirim ke masing-masing pulau? Berapa total
biaya pengirimannya?
-
Pengantar Simplex
Mahasiswa akan membeli laptop untuk
keperluan kuliah dan kerjanya. Ia diberikan
kesempatan memilih 4 jenis laptop
(hp/lenovo/vaio/samsung). Masing-masing
laptop memili spesifikasi dan harga yang
berbeda. Bagaimana mahasiswa itu akan
memilih laptop yang sesuai dengan
kebutuhan dan kantongnya ?
-
Syarat Awal Metode Simplek
Semua kendala harus berbentuk persamaan matematikabiasa (dengan tanda =). Apabila kendala berbentuk
persamaan linier, maka harus diubah kebentuk
persamaan matematika dengan penambahan variabel
slack secukupnya.
Fungsi kendala dengan tanda diubah ke bentuk dengan cara mengalikan dengan 1, lalu diubah ke bentukpersamaan matematika biasa dengan ditambahkan
variabel slack. Kemudian karena RHS-nya negatif,
dikalikan lagi dengan 1 dan ditambah artificial variabel(M).
Semua ruas kanan variabel keputusan (Z) harus bernilai= 0
-
Rubah menjadi bentuk simplek
Minimum/maksimum
kendala
-
Contoh Kasus
Perusahaan sepatu membuat 2 macam sepatu. Yang pertama
merek I1, dgn sol karet, dan merek I2 dgn sol kulit. Diperlukan
3 macam mesin. Mesin 1 membuat sol karet, mesin 2
membuat sol kulit, dan mesin 3 membuat bagian atas sepatu
dan melakukan assembling bagian atas dengan sol. Setiap
lusin sepatu merek I1 mula-mula dikerjakan di mesin 1 selama
2 jam, kemudian tanpa melalui mesin 2 terus dikerjakan di
mesin 3 selama 6 jam. Sedang untuk sepatu merek I2 tidak
diproses di mesin 1, tetapi pertama kali dikerjakan di mesin 2
selama 3 jam kemudian di mesin 3 selama 5 jam. Jam kerja
maksimum setiap hari mesin 1 adalah 8 jam, mesin 2 adalah
15 jam, dan mesin 3 adalah 30 jam. Sumbangan terhadap
laba setiap lusin sepatu merek I1 = Rp 30.000,00 sedang
merek I2 = Rp 50.000,00. Masalahnya adalah menentukan
berapa lusin sebaiknya sepatu merek I1 dan merek I2 yang
dibuat agar bisa memaksimumkan laba.
-
Penyelesaian (Bentuk Matematika)
Maksimumkan Z = 3X1 + 5X2 Batasan (constrain)
(1) 2X1 8
(2) 3X2 15
(3) 6X1 + 5X2 30
-
Langkah-langkah metode simpleks
Langkah 1:
Mengubah fungsi tujuan dan batasan-batasan
Fungsi tujuan
Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 = 0.
Fungsi batasan (diubah menjadi kesamaan & di + slack variabel)
(1) 2X1 8 menjadi 2X1+ X3 = 8
(2) 3X2 15 menjadi 3X2+ X4= 15
(3) 6X1 + 5X2 30 menjadi 6X1 +5X2+X5= 30
-
Beberapa Istilah dlm Metode Simplek
NK adalah nilai kanan persamaan, yaitu nilai di belakang
tanda sama dengan ( = ). Untuk batasan 1 sebesar 8,
batasan 2 sebesar 15, dan batasan 3 sebesar 30.
Variabel dasar adalah variabel yang nilainya sama
dengan sisi kanan dari persamaan. Pada persamaan
2X1 + X3 = 8, kalau belum ada kegiatan apa-apa, berarti
nilai X1 = 0, dan semua kapasitas masih menganggur,
maka pengangguran ada 8 satuan, atau nilai X3 = 8. Pada
tabel tersebut nilai variabel dasar (X3, X4, X5) pada fungsi
tujuan pada tabel permulaan ini harus 0, dan nilainya pada
batasan-batasan bertanda positif
-
Hasil Pengubahan
Z = 3X1 + 5X2 menjadi Z - 3X1 - 5X2 = 0.
(1) 2 X1 8 menjadi 2X1+ X3= 8
(2) 3 X2 15 menjadi 3X2+ X4 = 15
(3) 6 X1 + 5 X2 30 menjadi 6X1 +5X2+ X5= 30
-
Tabel Simplek Awal
Variabel
DasarZ X1 X2 X3 X4 X5 NK
Z 1 -3 -5 0 0 0 0
X3 0 2 0 1 0 0 8
X4 0 0 3 0 1 0 15
X5 0 6 5 0 0 1 30
-
Langkah 2 : Pemilihan Kolom Kunci
Kolom kunci adalah kolom yang merupakan dasar untuk
mengubah tabel simplek. Pilihlah kolom yang mempunyai
nilai pada garis fungsi tujuan yang bernilai negatif
dengan angka terbesar.
-
Pemilihan Kolom Kunci
Jika suatu tabel sudah tidak memiliki nilai negatif pada barisfungsi tujuan, berarti tabel itu tidak bisa dioptimalkan lagi(sudah optimal).
Variabel
DasarZ X1 X2 X3 X4 X5 NK
Keterang
an
(Indeks)
Z 1 -3 -5 0 0 0 0
X3 0 2 0 1 0 0 8
X4 0 0 3 0 1 0 15
X5 0 6 5 0 0 1 30
-
Langkah 3 : Pemilihan Baris Kunci
Baris kunci adalah baris yang merupakan dasar untuk mengubah
tabel simplek, dengan cara mencari indeks tiap-tiap baris dengan
membagi nilai-nilai pada kolom NK dengan nilai yang sebaris pada
kolom kunci.
Indeks = (Nilai Kolom NK) / (Nilai kolom kunci)
Untuk baris batasan 1 besarnya indeks = 8/0 = , baris batasan 2 =
15/3 = 5, dan baris batasan 3 = 30/5 = 6. Pilih baris yang mempunyai
indeks positif dengan angka terkecil. Dalam hal ini batasan ke-2
yang terpilih sebagai baris kunci. Beri tanda segi empat pada baris
kunci. Nilai yang masuk dalam kolom kunci dan juga masuk dalam
baris kunci disebut angka kunci
-
Mengubah Nilai Baris Kunci
Nilai baris kunci diubah dengan cara membaginya dengan angka
kunci, seperti tabel 3. bagian bawah (0/3 = 0; 3/3 = 1; 0/3 = 0; 1/3
= 1/3; 0/3 = 0; 15/3 = 5). Gantilah variabel dasar pada baris itu
dengan variabel yang terdapat di bagian atas kolom kunci (X2).
-
Tabel Perubahan Baris Kunci
-
Langkah 4 : Penentuan Baris Baru
-
[ 6 5 0 0 1, 30 ]
(5) [ 0 1 0 1/3 0, 5 ] ( - )
Nilai baru = [ 6 0 0 -5/3 1, 5 ]
Variabel
DasarZ X1 X2 X3 X4 X5 NK
Z 1 -3 -5 0 0 0 0
X3 0 2 0 1 0 0 8
X4 0 0 3 0 1 0 15
X5 0 6 5 0 0 1 30
Z 1 -3 0 0 5/3 0 25
X3 0 2 0 1 0 0 8
X2 0 0 1 0 1/3 0 5
X5 0 6 0 0 -5/3 1 5
Tabel pertama nilai lama dan tabel kedua nilai baru
-
Ulangilah langkah-langkah perbaikan
mulai langkah 2 sampai langkah ke-4
untuk memperbaiki tabel-tabel yang telah
diubah/diperbaiki nilainya. Perubahan
baru berhenti setelah pada baris pertama
(fungsi tujuan) tidak ada yang bernilai
negatif
Langkah 5 : Lanjut Perbaikan
-
[-3 0 0 5/3 0, 25 ]
(-3) [ 1 0 0 -5/18 1/6, 5/6] ( - )
Nilai baru = [ 0 0 0 5/6 , 271/2]
[ 2 0 1 0 0, 8 ]
(2) [ 1 0 0 -5/18 1/6, 5/6] ( - )
Nilai baru = 0 0 1 5/9 -1/3, 61/3]
[ 0 1 0 1/3 0, 5 ]
(0) [ 1 0 0 -5/18 1/6, 5/6] ( - )
Nilai baru = 0 1 0 1/3 0, 5]
Baris ke-1
Baris ke-2 (batasan 1)
Baris ke-3 tidak berubah karena nilai pada kolom kunci = 0
-
Baris pertama (Z) tidak ada lagi yang bernilainegatif. Sehingga tabel tidak dapat dioptimalkanlagi dan tabel tersebut merupakan hasil optimal
X1 = 5/6
X2 = 5
Zmaksimum = 271/2
Tabel Hasil Akhir
Variabel
DasarZ X1 X2 X3 X4 X5 NK
Z 1 0 0 0 5/6 271/2
X3 0 0 0 1 5/9 -1/3 61/3
X2 0 0 1 0 1/3 0 5
X1 0 1 0 0 -5/18 1/6 5/6
-
Perusahaan Riski corp memproduksi 3 buah model almari (A, B,dan C). Waktu pembuatan (jam kerja) dan harga pembelianbahan baku (ratusan ribu rupiah) tiap almari dapat dilihat padatabel.
Kerena keterbatasan modal, biaya pembelian bahan bakuterbatas sebesar 20.000.000 dan waktu pembuatan jugaterbatas selama 150 jam. Hasil penjualan lemari A, B, Cmasing-masing memberikan keuntungan 400.000, 200.000,300.000. berapakan banyaknya lemari yang harus dibuat agarbisa mendapatkan keuntungan maksimal ?
Latihan 1
A B C
Waktu pembuatan (jam) 7 3 6
Harga bahan baku 400000 400000 500000
-
Perusahaan mempunyai anggaran produksi
sebesar $2000 dan jam kerja maksimum
665 jam per hari. Maksimum permintaan
tiap hari 200 unit untuk jam dinding, 300 unit
radio, 150 unit toaster. Keuntungan
maksimum tiap produk adalah $15 untuk
jam dinding, $20 untuk radio, dan $12 untuk
toaster. Tentukan produksi optimal agar
keuntungan maksimum !
Latihan 2
-
Tugas 1
Silahkan buat tim (1 tim terdiri 2-3 Orang).
Lakukan observasi lapangan langsung
(tempat penelitian bebas). Analisa kebutuhan
untuk linier programming dan buatkan
kesimpulan dari hasil analisanya.
Cat.
Object yang diteliti harus menghasilkan
minimal 3 variabel
-
TERIMA KASIH
Operation Research
top related