Universitas Terbuka
1
Ir. Tito Adi Dewanto
LINEAR PROGRAMMING, METODE GRAFIK
LINEAR PROGRAMMING : 1. Pembuatan program atau rencana yang mendasarkan asumsiasumsi linear (berpangkat satu). 2. Cara alokasi sumber daya yg terbatas secara optimal.
Optimal bermakna sebaik-baiknya buat kita yaitu memaksimumkan keuntungan atau meminimumkan biaya.
Metode Grafik : Pemecahan masalah menggunakan bantuan grafik.
Terdiri dari 2 macam persamaan/pertidaksamaan 1. Batasan/kendala : Batasan fungsional dan batasan non-negatif .a11X1 + a12X2 b1 .a21X1 + a22X2 b2 X1 0 , X2 0 2. Fungsi Tujuan Z = c1X1 + c2X2
Contoh Soal dan Pembahasan 1:
PT Maju Mundur menghasilkan 2 macam barang. Setiap unit barang I memerlukan bahan baku A = 2 kg dan bahan baku B = 2 kg. Setiap unit II memerlukan bahan baku A= 1 kg dan B= 3 kg. Jumlah bahan baku A yang disediakan perusahaan 6000 kg dan bahan baku B = 9000 kg. Sumbangan terhadap laba untuk produk I adalah Rp 3000,dan setiap unit produk II adalah Rp 4000,-. Tentukan Keuntungan Maksimum ? Jawab : Produk Bahan Baku A B Laba
Kebutuhan Bahan Baku Produk I Produk II 2 1 2 3 3000 4000
2X1 + X2 6000 2X1 + 3X2 9000 X1 0 , X2 0 Z = 3000 X1 + 4000 X2
Kapasitas Maksimum 6000 9000
Universitas Terbuka
2
Ir. Tito Adi Dewanto
X
6000 2X1 + 3000 C
X2 6000 2X1 + 3X2 9000
B A
0
4500
3000
X1
Koordinat titik pojok A(3000,0), B( 2250,1500 ), C(0,3000) Titik B : 2X1 + X2 = 6000 2X1 + 3X2= 9000 – -2X2=-3000 X2 = 1500 2X1 + 1500= 6000 2X1 = 6000 – 1500 = 4500 X1 = 2250 Titik Pojok Z = 3000 X1 + 4000 X2 A(3000,0) 9.000.000 B(2250,1500) 6.750.000+6.000.000=12.750.000 C(0,3000) 12.000.000 Produk pertama dihasilkan 2250 unit Produk kedua dihasilkan 1500 unit Dan Keuntungan maksimum adalah Rp 12.750.000,Contoh Soal dan Pembahasan 2:
S
eorang pembuat kue mempunyai 4 kg gula dan 9 kg tepung. Untuk membuat sebuah kue jenis A dibutuhkan 20 gram gula dan 60 gram tepung, sedangkan untuk membuat sebuah kue jenis B dibutuhkan 20 gram gula dan 40 gram tepung. Jika kue A dijual dengan harga Rp 4000/buah dan kue B dijual dengan harga Rp 3000/buah, maka pendapatan maksimum pembuat kue adalah ….. A. Rp 600.000 C. Rp 650.000 B. Rp 700.000 D. Rp 750.000 E. Rp 800.000 Jawab : 1) Buat Tabel KUE A KUE B MAXIMUM JENIS X Y BAHAN GULA
20
20
4000
TEPUNG
60
40
9000
4000
3000
PENDAPATAN
Universitas Terbuka
3
Ir. Tito Adi Dewanto
2) Buat Model Matematika 20X + 20Y ≤ 4000 X + Y ≤ 200 60X + 40Y ≤ 9000 3X + 2Y ≤450 X≥0 Y≥0 Fungsi Tujuan: Z = 4000 X + 3000Y Batasan:
3) Buat Himpunan Penyelesaian
Y
225 200
(50,150)
0
150
200
X
Titik Potong Kedua garis X + Y = 200 2X + 2Y = 400 3X + 2Y = 450 3X + 2Y = 450 -X = -50 X = 50 dan Y = 150 4) Cari Nilai Optimum Titik pojok
Z = 4000 X + 3000Y
Hasil
(150,0)
600.000
600.000
(50,150)
200.000+450.000
650.000 (Max)
(0,200)
600.000
600.000
5) Penafsiran Pendapatan maksimum tukang kue tersebut adalah Rp 650.000,- yaitu dengan membuat 50 kue A dan 150 kue B.
Universitas Terbuka
4
Ir. Tito Adi Dewanto
PENYIMPANGAN-PENYIMPANGAN BENTUK STANDAR 1. 2. 3. 4.
Fungsi Batasan bertanda Lebih besar atau sama dengan ( ) Fungsi Batasan bertanda sama dengan (=) Meminimumkan Fungsi Tujuan Perubahan dalam Batasan Non Negatif
BEBERAPA ISTILAH DALAM LINEAR PROGRAMMING 1. Daerah Feasible Daerah yang tidak melanggar batasan-batasan yang ada. Biasa disebut juga daerah Himpunan Penyelesaian (HP). 2. Titik sudut yang Feasible Titik-titik sudut yang bisa dicapai 3. Masalah yang memiliki titik feasible Terjadi kalau letak dan sifat batasan-batasannya sedemikian rupa sehingga tidak memungkinkan terdapatnya daerah atau alternative pemecahan yang feasible. 4. Pemecahan/Hasil Optimal (Optimal Solution) Hasil pemecahan yang mempunyai nilai tujuan (Z) terbaik bisa memaksimumkan atau meminimumkan. 5. Masalah yang Memiliki Pemecahan Optimal Lebih dari satu titik (Multiple Optimal Solution) Terjadi apabila gambar fungsi tujuan sejajar dengan batasan bila kita geser 6. Masalah yang tidak memiliki Pemecahan Optimal Ada 2 penyebab : i) Masalah yang tidak memiliki daerah feasible ii) Salah satu aktifitas tidak terpengaruh oleh batasan yang ada 7. Hubungan antara titik-titik sudut feasible Garis yang terkanan memiliki nilai Z Terbesar 8. Analisis Sensitivitas Bertujuan untuk menghitung akibat-akibat perubahan kendala dan fungsi tujuan pada nilai tujuan (hasil).
1. 2. 3. 4. 5.
Motivation Tips Jangan menunggu bahagia baru tersenyum tapi tersenyumlah, kian bahagia. Jangan menunggu kaya baru bersedekah tapi bersedekalah, semakin kaya. Jangan menunggu termotivasi baru bergerak tapi bergeraklah, motivasimu akan meningkat. Jangan menunggu proyek baru mau bekerja tapi bekerjalah proyek kan berdatangan kepadamu. Jangan menunggu sukses baru bersyukur tapi bersyukurlah, bertambah kesuksesanmu.
maka maka maka maka maka
Universitas Terbuka
5
Ir. Tito Adi Dewanto
Tes Formatif
Perusahaan tas ANTOMIA membuat 2 tas, model X1 dan model X2 dari kulit. Untuk membuat kedua macam tas tersebut perusahaan memiliki 3 macam mesin. Mesin I membuat tas parasit, mesin II membuat tas kulit dan mesin III melakukan penyelesaian akhir kedua macam tas tersebut. model
X1
X2
5 0 8 6
0 6 5 8
mesin 1 2 3 Sumbangan terhadap laba (Rp 1.000.000)
Kapasitas Maksimum 20 18 40
Fungsi Tujuannya adalah Z = 6x1 + 8x2, maka....
1. Fungsi Batasan mesin I adalah ... A. 5x1 20 B. 6x2 18 C. 8x1 + 5x2 40 D. 6x1 + 8x2 0 2. Fungsi Batasan mesin II adalah ... A. 5x1 20 B. 6x2 18 C. 8x1 + 5x2 40 D. 6x1 + 8x2 0 3. Fungsi Batasan mesin III adalah ... A. 5x1 20 B. 6x2 18 C. 8x1 + 5x2 40 D. 6x1 + 8x2 0 4. Apabila berdasarkan data x diatas diperoleh grafik sebagai berikut x2
A
B
F C
O D G x1 Maka daerah feasible grafik tersebut adalah ..... A. OABCD B. ABE C. CDG D. BCF
Universitas Terbuka
6
Ir. Tito Adi Dewanto
5. Agar memperoleh laba maksimum, maka perusahaan sepatu ANTOMIA perlu memperoduksi sepatu model x1 dan x2 sebesar ..... A. 0 dan 3 B. 4 dan 0 C. 4 dan 8/5 D. 3 1/8 dan 3 Exercise 1. Suatu perusahaan cat menyediakan campuran A dan B untuk dibuat satu jenis cat. Campuran A mengandung 400 gr bahan I dan 600 gram bahan II. Campuran B mengandung 800 gr bahan I dan 200 gr bahan II. Cat tersebut berkualitas baik bila mengandung minimal 4 kg bahan I dan 2 kg bahan II. Jika harga tiap kg campuran A Rp. 20.000,- dan B Rp. 10.000,- maka berapa banyaknya campuran A dan B agar biaya yang dikeluarkan minimum …. a. 4 kg campuran A dan 2 kg B b. 4 kg campuran A dan 12 kg B c. 2 kg campuran A dan 4 kg B d. 2 kg campuran A dan 2 kg B 2. Seorang tukang roti mempunyai bahan A, B, dan C masing-masing sebanyak 160 kg, 110 kg, dan 150 kg. Roti I memerlukan 2 kg bahan A, 1 kg bahan B, dan 1 kg bahan C. Roti II memerlukan 1 kg bahan A, 2 kg bahan B, dan 3 kg bahan C. Sebuah roti I dijual dengan harga Rp 30.000,00 dan sebuah roti II dijual dengan harga Rp 50.000,00. Pendapatan maksimum yang dapat diperoleh tukang roti tersebut adalah a. Rp 8.000.000,00 c. Rp 3.100.000,00 b. Rp 4.500.000,00 d. Rp 2.900.000,00
Insanity: doing the same thing over and over again and expecting different results. Science without religion is lame. Religion without science is blind (Albert Einstein)