3 LINEAR PROGRAMMING, METODE SIMPLEKS.pptx

linear programming

1. LINEAR PROGRAMMING METODE SIMPLEKS

2. LANGKAH-LANGKAH METODE SIMPLEKS : Misalkan contoh kita PT. KEMBANG ARUM Fungsi tujuan : Max : Z = 3X 1 + 4X 2 Batasan – batasan : 1. 2X 1 + X 2 ≤ 6.000 2. 2X 1 + 3X 2 ≤ 9.000 3. X1 ≥ 0 ; X2 ≥ 0

3. LANGKAH 1 : MERUBAH BENTUK FUNGSI TUJUAN Fungsi tujuan dirubah sedemikian rupa , sehingga semua variabel yang belum diketahui nilainya berada di sebelah kiri tanda = . Misalnya dalam contoh diatas , fungsi tujuan : Maksimum : Z = 3X 1 + 4X 2 diubah menjadi Maksimum : Z – 3X 1 – 4X 2 = 0

4. LANGKAH 2 : MERUBAH BENTUK BATASAN-BATASAN Semua batasan yang mula-mula bertanda lebih kecil atau sama dengan ( ≤ ) dirubah menjadi tanda persamaan ( = ), dengan menggunakan suatu tambahan variabel yang sering disebut sebagai “ Variabel Slack ”, yang biasanya diberi simbol “ S “. Perubahan tersebut menjadi : 2X 1 + X 2 ≤ 6.000 dirubah menjadi 2X 1 + X 2 + S 1 = 6.000 2X 1 + 3X 2 ≤ 9.000 dirubah menjadi 2X 1 + 3X 2 + S 2 = 9.000

5. LANGKAH 3 : MENYUSUN PERSAMAAN KE DALAM TABEL LANGKAH 4 : MEMILIH KOLOM KUNCI Pilih kolom yang pada garis Z mempunyai nilai negatif terkecil ( pailng negatif ). LANGKAH 5 : MEMILIH BARIS KUNCI baris kunci adalah baris yang merupakan dasar untuk mengubah / mengadakan perbaikan . Untuk menentukannya terlebih dahulu harus kita cari indeks tiap-tiap baris dengan cara sebagai berikut : VD Z X 1 X 2 S 1 S 2 NK Z 1 -3 -4 S 1 2 1 1 6.000 S 2 2 3 1 9.000 Kolom kunci Baris kunci Angka kunci

6. LANGKAH 5 : MEMILIH BARIS KUNCI : Indeks : 6.000 / 1 = 6.000 9.000 / 3 = 3.000 Kemudian kita pilih baris kunci , yaitu baris yang mempunyai indeks positif terkecil , yaitu baris batasan kedua ( indeks batasan pertama 6.000 dan batasan kedua hanya 3.000). Kemudian baris kunci ini kita beri tanda ( dilingkari ) agar lebih mudah mengingatnya . Kita lihat ada angka yang masuk dalam kolom kunci dan juga masuk dalam baris kunci disebut angka kunci sebesar 3.

7. LANGKAH 6 : MERUBAH NILAI-NILAI BARIS KUNCI Mula-mula kita ubah dulu nilai-nilai baris kunci dengan membagi semua angkanya dengan angka kunci . Jadi semua angka pada baris kunci itu kita bagi 3, disamping itu variabel dasarnya kita ganti dengan variabel yang kolomnya terpilih sebagai kolom kunci , dalam contoh kita variabel X 2 . VD Z X 1 X 2 S 1 S 2 NK Z 1 -3 -4 S 1 2 1 1 6.000 S 2 2 3 1 9.000 Dibagi 3 VD Z X 1 X 2 S 1 S 2 NK Z S 1 S 2 2/3 1 1/3 3.000

8. LANGKAH 7 : MENGUBAH NILAI DILUAR BARIS KUNCI Nilai baru dari baris-baris yang bukan merupakan baris kunci dapat dihitung dengan rumus sebagai berikut : Untuk baris Z pada tabel dapat dihitung sebagai berikut : Nilai Baris Baru = Nilai Baris Lama Koefisien Pada Kolom Kunci Nilai Baru Baris Kunci X _ -3 -4 - ( -4 ) 2/3 1 1/3 3.000 -1/3 1 4/3 12.000 Nilai baru baris kunci Koefisien angka pada kolom kunci Nilai baris lama Nilai baris baru

9. Untuk baris batasan pertama sebagai berikut : 2 1 1 6.000 - ( 1 ) 2/3 1 1/3 3.000 4/3 1 -1/3 3.000 Tabel I nilai lama dan tabel II nilai baru ( setelah diperbaiki sekali ) : VD Z X 1 X 2 S 1 S 2 NK Z 1 -3 -4 S 1 2 1 1 6.000 S 2 2 3 1 9.000 VD Z X 1 X 2 S 1 S 2 NK Z 1 -1/3 4/3 12.000 S 1 4/3 1 -1/3 3.000 X 2 2/3 1 1/3 3.000 I II

10. LANGKAH 8 : MELANJUTKAN PERBAIKAN Selama masih ada nilai negatif pada baris Z ulangilah langkah perbaikan mulai dari langkah ke-3 sampai dengan langkah ke-7 sampai diperoleh pemecahan optimal. Kalau sudah tidak ada nilai pada baris Z yang negatif berarti alokasi itu sudah optimal. Nilai baru dari baris Z menjadi : -1/3 4/3 12.000 - ( -1/3 ) 1 3/4 -1/4 2.250 ¼ 5/4 12.750 2/3 1 1/3 3.000 - ( 2/3 ) 1 3/4 -1/4 2.250 1 -1/2 1/2 1.500 Nilai baru baris batasan pertama :

11. VD Z X 1 X 2 S 1 S 2 NK Z 1 -3 -4 S 1 2 1 1 6.000 S 2 2 3 1 9.000 VD Z X 1 X 2 S 1 S 2 NK Z 1 -1/3 4/3 12.000 S 1 4/3 1 -1/3 3.000 X 2 2/3 1 1/3 3.000 VD Z X 1 X 2 S 1 S 2 NK Z 1 1/4 5/4 12.750 X 1 1 3/4 -1/4 2.250 X 2 1 -1/2 1/2 1.500 I II III

12. Pada bagian III dari tabel di atas ternyata dalam bari Z sudah tidak memiliki negatif lagi , berarti tabel ini sudah optimal. Arti dari hasil pemecahan optimal ini sebagai berikut : Produk pertama dihasilkan 2.250 unit (X 1 = 2.250) Produk kedua dihasilkan 1.500 unit (X 2 = 1.500) Sumbangan terhadap laba sebesar Rp . 12.750,- (Z = 12.750)

13. LATIHAN 1: Suatu pabrik automotive menghasilkan dua macam kendaraan dengan kualitas berbeda , yaitu type BEBAS EMISI dan type HEMAT BAHAN BAKAR. Untuk menghasilkan kedua macam kendaraan tersebut digunakan tiga macam spare part yang sama yaitu spare part A, B dan C. kebutuhan spare part untuk menghasilkan tiap satuan produk sebagai berikut : Type Kebutuhan Spare part A Spare part B Spare part C BEBAS EMISI 3 2 2 HEMAT BB 2 4 4 Maks tersedia 30 42 80 Permintaan dianggap cukup bisa menyerap semua produk yang dihasilkan . Sumbangan terhadap laba tiap satuan kendaraan type BEBAS EMISI $ 5.000 sedangkan type HEMAT BAHAN BAKAR $ 10.000. perusahaan akan menentukan jumlah tiap type yang dihasilkan agar bisa memaksimalkan laba . Selesaikanlah persoalan diatas dengan metode simpleks !

14. LATIHAN 2 : Suatu perusahaan menghasilkan 2 macam produk , yaitu produk A dan produk B. kedua produk itu dibuat melalui dua mesin ( mesin I dan mesin II). Untuk menghasilkan 100 unit produk A harus dikerjakan di mesin I selama 3 jam dan di mesin II selama 4 jam; sedang untuk menghasilkan 100 unit produk B harus dikerjakan di mesin I selama 2 jam dan di mesin II selama 5 jam. Kapasitas kerja maksimum untuk mesin I 12 jam dan mesin II juga 12 jam. Sumbangan terhadap laba untuk setiap 100 buah produk A sebesar Rp . 3.000 dan untuk produk B sebesar Rp . 3.500. berapakah jumlah produk A dan produk B yang seharusnya dihasilkan agar memperoleh laba maksimum ?

15. LATIHAN 3 : Suatu perusahaan menghasilkan dua macam produk , dengan menggunakan bakan baku J , K dan L. kebutuhan akan bahan baku setiap unit produk sebagai berikut : Bahan baku Kebutuhan bahan baku / unit Maks . Tersedia Produk I Produk II J 3 kg 2 kg 42 kg K 2 kg 4 kg 30 kg L 2 kg 4 kg 48 kg Sumbangan thd laba Rp . 12,- Rp . 8,- Hitunglah kombinasi jumlah produk yang bisa memaksimumkan laba perusahaan !

16. LATIHAN 4 : 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, dan 150 unit toater . Keuntungan maksimum tiap unit produk adalah $ 15 untuk jam dinding , $ 20 untuk radio, dan $ 12 untuk toaster. Tentukan produksi optimal agar keuntungan maksimum ! Produk Kebutuhan sumber daya Biaya /unit Jam/unit Jam dinding 8 2 Radio 10 3 Toaster 5 2

17. LATIHAN 5 : Sebuah industri kerajinan kulit membuat tas yang terdiri dari jenis A dan B. keuntungan masing-masing jenis tas adalah $ 400 dan $ 200 dolar per unit. Industri mendapat pesanan dari sebuah toko sebesar 30 (A dan B) buah per bulan . Suplai bahan kulit paling sedikit 80 lembar per bulan , dan industri kerajinan ini harus memesan paling tidak 80 lembar per bulan . Setiap barang A memerlukan 2 lembar kulit sedangkan barang B membutuhkan 8 lembar . Dari pengalaman sebelumnya industri ini tidak bisa membuat barang jenis A lebih dari 20 buah per bulan . Mereka ingin mengetahui berapa jumlah masing-masing jenis A dan B yang harus dibuat supaya keuntungan yang didapat maksimum . Tentukan model program liniernya dan selesaikan persoalan dengan metode simpleks .!