Linier Prog.-1 [PDF]

Citation preview

1



PENDAHULUAN



Tujuan utama suatu usaha bisnis : memaksimumkan laba atau meminimumkan biaya. - Untuk itu,pasti usaha itu memiliki berbagai kendala s.d Baik tujuan maupun kedala pada umumnya dalam kondisi deterministik. - Suhubungan dengan itu, Linier Programming (LP) memberikan solusi dalam pengambilan keputusan usaha bisnis tsb. - Linier programming adalah suatu teknik atau cara yang membantu dalam keputusan mengalokasi sumberdaya yang dimiliki perusahaan. - Sumberdaya tersebut meliputi misalnya, mesin-mesin, tenaga kerja, uang, waktu, kapasitas gudang (ruangan), material , dll., yang akan digunakan untuk memproduksi barang (sandang, pangan, papan, dll) atau jasa (rencana pengiriman dan produksi, keputusan investasi, kebijakan advertensi, dll) 2



Persyaratan Yang Diperlukan Dalam L P : 1. Perusahaan mempunyai tujuan,yaitu memaksimumkan laba atau miminimumkan biaya 2. Perusahaan mempunyai kerterbatasan atau kendala sumberdaya dalam mencapai tujuan. 3. Perusahaan mempunyai keputusan atau kegiatan alternatif, salah satu diantaranya dipakai atau dipilih untuk mencapai tujuan. 4. Tujuan dan kendala dinyatakan dalam hubungan persamaan ( = ) dan pertidaksamaan ( < / > ) matematik yang linier. 3



Beberapa Asumsi Yang Berlaku Dalam LP : 1.Kondisi-kondisi bisnis dalam perusahaan dalam kepastian dimana nilai-nilai, jumlah-jumlah dalam fungsi tujuan dan kendala diketahui dengan pasti (deterministik), tidak berubah selama periode analisis. 2.Hubungan dalam fungsi tujuan dan kendala adalah proporsional dalam bentuk matematik yang linier, contoh : L = 10 X  jika X = 2, maka L = 20 jika X = 4, maka L = 40 M < 60X  jika X = 2, maka M < 120 jika X = 5, maka M < 300 3.Bentuk fungsi tujuan dan kendala besifat aditivity, artinya jumlah total nilai kegiatan = penjumlahan dari nilai-nilai kegiatan individu : L = $3 X1 + $5 X2  Jika X1 = 10 dan X2 = 20, maka L = $3(10) + $5(20) = $ 130. 4.Barang dan jasa yang dihasilkan (variabel keputusan) harus positif bukan negatif (non negatively) paling tidak nol (tidak menghasilkan) X ,X > 0



4



Sejarah Linier Program



- LP telah dikembangkan sebelum perang dunia II oleh matematikawan Rusia, A.N. Kolmogorov dan Leonid Kantorovic penerima nobel “Optimasi Perencanaan” - Dalam aplikasi berikutnya LP dikembangkan oleh Stigler (1945) dalam persoalan Diit (kesehatan). - Perkembangan berikutnya (1947),George D.Dantzig me-ngembang kan solusinya dengan metode simplex. Jasa Dantzig ini luar biasa sehingga kita kenal sampai sekarang dengan istilah “Linier Programming”. Dia seorang matematikawan di Angkatan Udara Inggris menjabat sebagai kepala Pengendali Analisis Perang Angkatan Udara. Saat itu militer memerlukan sekali program perencanaan latihan militer, pemasokan peralatan dan amunisi, penempatan unit-2 tempur. Dantzig memformulasikan sistem pertidaksamaan linier - Setelah perang dunia II aplikasi dalam dunia bisnis luar biasa, misalnya dalam usaha pengolahan, jasa, pertanian, dll. - Tahun 1984 N.Karmarkar mengembangkan model yang lebih superior dari metode simplex utk berbagai aplikasi yg lebih luas. 5



Model Formulasi Model LP berisikan beberapa komponen dan karakteristik ttt. Komponen adalah Fungsi Tujuan dan Fungsi Kendala, didalamnya terdapat Variabel Keputusan dan Parametrer. Variabel Keputusan adalah simbul matematik dari kegiatan yang dilakukan /dibuat/diproduksi oleh perusahaan, misalnya : X1 = jml. Meja, X2 = jml.Kursi dan X3 = jml tempat tidur yang diproduksi Parameter adalah nilai-nilai di depan variabel keputusan yang pada dasarnya sudah diketahui. Fungsi Tujuan merupakan hubungan matematika linier yang menggambarkan tujuan perusahaan baik memaksimumkan laba atau meminimumkan biaya untuk membuat var. keputusan. Fungsi Kendala juga merupakan hubungan linier antar variabel kepu tusan yg menggambarkan keterbatasan sumberdaya. Misalnya, keterbatasan dlm. jumlah Tenaga Kerja utk memproduksi Meja sebesar 40 jam/hari. 6 Nilai-nilai Konstanta dalam fungsi tujuan atau kendala juga



METODE GRAFIK Persoalan maksimasi . contoh : perusahaan xyz Sebuah industri XYZ berkecimpung dalam proses produksi dua macam produk, yaitu produk A dan B. Kedua produk tesebut dapat dijual masing-masing dengan harga Rp 3000,per unit. Dalam proses produksinya diperlukan tiga macam departemen, yaitu Departemen P yang memiliki 3 unit mesin tipe P, Departemen Q memiliki 6 unit mesin tipe Q dan Dep. R memiliki 9 unit mesin tipe R. Lama waktu pemakaian mesin mesin tersebut berbeda untuk setiap produk. Produk A memerlukan waktu 2 jam untuk proses produksinya pada mesin tipe P, kemudian 2 jam pada mesin tipe Q dan 4 jam pada mesin tipe R. Sedangkan untuk produk B memerlukan waktu 1 jam pada mesin tipe P, kemudian 3 jam pada mesin tipe Q dan 3 jam pada mesin tipe R. 7



Lamanya waktu mesin-mesin tersebut beroperasipun sangat terbatas, yaitu mesin tipe P beroperasi selama 10 jam per hari per mesin, mesin tipe Q dapat beroperaasi 10 jam per hari per mesin dan mesin tipe R beroperaasi selama 8 jam per hari per mesin. - Rumuskan persoalan tsb. dalam model program linier (formula matematika) ! - Gambarlah persoalan LP tersebut dan Hitunglah berapa produk A dan B harus dijual sehingga penerimaannya maksimal



8



Dari contoh persoalan LP di atas, dapat diringkas pada tabel berikut : Sd P Q R Harga



A 2 2 4 3000



B 1 3 3 3000



Kap. < 30 < 60 < 72



Kemudian dengan lebih mudah dapat disusun formulasi matematisnya : Max. TR = 3000A + 3000B Stc. P : 2A + B < 30 Q : 2A + 3B < 60 R : 4A + 3B < 72 A,B > 0 9



GAMBAR FUNGSI KENDALA



•



P : 2A + B < 30 Jika A = 0 , maka B = 30 Jika B = 0 , maka A = 15



Max. TR = 3000A + 3000B Stc. P : 2A + B < Q : 2A + 3B < R : 4A + 3B < A,B >



•



10



30 60 72 0



Metode Grafik / Maksimasi



FISIBLE AREA dan ISO REVENUE TR = 3000A + 3000B  B =



TR



/3000 - A



0 = 3000(0) + 3000(0) 45000 = 3000(15) + 3000(0)



B



•



60000 63000 66000 > 66000



P



= = = =



3000(0) + 3000(20) 3000(9) + 3000(12) 3000(6) + 3000(16) IMPOSIBLE Solusi : Produk A = 6 unit Produk B = 16 unit TR = $ 66000



• • Q



Evaluasi Sumberdaya : P : 2(6) + 1(16) = 28 jam  sisa 2 jam Q : 2(6) + 3(16) = 60 jam  persis R : 4(6) + 3(16) = 72 jam  persis



R



•



• A 11



KEPUTUSAN BERALTERNATIF



•



1) Antara titik A dan B 2) Antara titik B dan C 3) Antara titik C dan D



A B



•



C



•



D



•



12



Variabel Slack



- Ingat bahwa solusi terjadi pada titik ekstrim, di mana garis pertidaksamaan kendala berpotongan satu sama yang lain atau berpotongan dengan sumbu pada grafk. Jadi dalam hal ini, kendala-kendala tersebut lebih dipertimbangkan sbg. persamaan daripada pertidaksamaan. - Prosedur baku untuk merubah pertidaksamaan kendala menjadi persamaan, adalah dengan menambah sebuah variabel baru ke dalam masing-masing kendala, yang disebut sebagai variabel slack. - Untuk contoh perusahaan XYZ di muka, model kendala adalah : P : 2A + B < 30 Q : 2A + 3B < 60 R : 4A + 3B < 72 13



- Penambahan sebuah variabel slack,S1 pada kendala P, S2 pada kendala Q dan S3 pada kendala R hasilnya dapat dilihat sbb. : C - Variabel slack S1, S2 dan S3 merupakan nilai yang diperlukan untuk membuat sisi sebelah kiri persamaan menjadi sama dengan sisi sebelah kanan. Misalnya secara hipotetis, A = 9 dan B = 10. Masukkan kedua nilai itu kedalam persamaan : P : 2(9) + 10 + S1 = 30 S1 = 2 Q : 2(9) + 3(10) + S2 = 60 S2 = 12 R : 4(9) + 3(10) + S3 = 72 S3 = 6



14



- Dalam contoh di atas, menghasilkan solusi yang tidak menghabiskan jumlah sumberdaya. Pada kendala P hanya menggunakan 28 jam, berarti sisa 2 jam yang tidak digunakan. - Jadi S1 merupakan jumlah waktu yang tidak digunakan pada sumberdaya P atau disebut slack P. Demikian juga pada kendala Q dan R masing-masing mempunyai slack Q dan slack R sebagai sisa 12 jam dan 6 jam yang tidak digunakan. - Jika perusahaan belum melakukan kegiatan produksi, maka seluruh kapasitas sumberdaya masih utuh, slacknya masing-masing sebesar 30, 60 dan 72 jam 15



Pengaruh Variabel Slack Terhadap Fungsi Tujuan Fungsi tujuan dari contoh adalah : TR = 3000 A + 3000 B. Koefisien 3.000 dan 3.000, masing-masing merupakan kontribusi TR setiap produk A dan produk B. Lalu, apa wujud kontribusi variabel slack S1 dan S2 ?. Variabel slack tidak mempunyai kontribusi apapun terhadap TR sebab variabel slack merupakan sumberdaya yg tidak digunakan. TR dicapai hanya setelah sumberdaya digunakan dalam proses produksi. Dengan demikian variabel slack dalam fungsi tujuan dapat ditululis parameter 0 , sbb : TR = 3000A + 3000 B + 0S1 + 0S2 + 0S3 16



Seperti halnya pada variabel keputusan (A dan B), variabel slack bernilai non-negative, sebab tidak mungkin sumberdaya itu negatif. Oleh karenanya, model formulasinya : A, B , S1, S2 dan S3 > 0 Dengan adanya varibel slack, model LP baku secara lengkap dapat ditulis sbb.: Maksimumkan : TR =3000 A + 3000 B+ 0S1+ 0S2 +0S3



Kendala



2A + B + S1 = 30 2A + 3B + S2 = 60 4A + 3B + S3 = 72 A, B , S1, S2 dan S3 > 0



17



A = 0 B = 20 TR = 60000 S1 = 10 S2 = 0 S3 = 12



•B



Max. TR = 3000 A + 3000B Kendala : 2A + B + S1 2A + 3B + S2 4A + 3B + S3 9 A, B , S1, S2 dan S3



A = 6 B = 16 TR = 66000 A = S1 = 2 B = 12 S2 = 0 TR = 63000 S3 = 0 S1 = 0 S2 = 6 C S3 = 0



< < < >



30 60 72 0



•



• D



A = 15 B = 0 TR = 45000 S1 = 0 S2 = 30 E S3 = 12



•



18



Contoh lain :



Persoalan Perusahaan BW



Perusahaan ini memproduksi dua macam produk, yaitu Meja dan Kursi, dimana dalam proses produksinya harus melalui dep. Assembling dan Finishing.Departemen assembling tersedia waktu 60 jam, sedangkan departemen finishing dapat menangani hingga sampai 48 jam kerja. packing . Untuk membuat sebuah kursi diperlukan waktu 2 jam pada assembling dan 4 jam pada fininshing.untuk memebuat sebuah meja diperlukan waktu 4 jam di ddepartemen assamabling dan 2 jam didepartemen finishing Jika Laba setiap satu meja sebesar $ 8 dan setiap satu kursi $ 6, persoalan yang dihadapi perusahaan BW adalah menentukan banyaknya produksi meja dan kursi yang terbaik, dan menjualnya sedemikian rupa sehingga memperoleh laba maksimum. 19



Informasi tentang persoalan perusahaan BW seperti dikemukakan di atas, dapat disajikan dalam tabel berikut ini : Sumberdaya Assembling Finishing Laba per unit X1 = meja X2= Kursi



Jam yg diperlukan per unit Meja /Kursi



X



1



X2



Jml jam yg tersedia



4 2



2 4



60 48



$8



$6



Maksimumkan : L = 8 X1 + 6 X2 Kendala : 4 X1 + 2 X2 < 60 2M+4K < 48 20



Sumberdaya Assembling Finishing Laba per unit



Jam yg diperlukan per unit Meja /Kursi



X



1



X2



Jml jam yg tersedia



4 2



2 4



60 48



$8



$6



X1 = meja X2= Kursi



21



Solusi B M=0 K = 12 L = 72 SA = 36 SF = 12



Solusi A M=0 K=0 L =0 SA = 60 SF = 48



K



(12, 6)



C



•



Solusi D M = 15 K= 0 L = 120 SA = 0 SF = 18



Keputusan: Jml Meja yang diproduksi sebanyak : 12 unit Jml kursi yang diproduksi sebanyak : 6 unit Laba = $8(12) + $6(6) = $ 132 Penggunaan Sumberdaya : Assembling : (4x12)+(2x6) = 60 unit (persis) Finishing : (2x12)+ (4x6) = 48 unit (persis)



•B A



Solusi C M = 12 K=6 L = 132 SA = 0 SF = 0



•



D



• M



22



Untuk Titik C : 4M + 2K = 60 →x1 = 4M + 2K = 60 2M + 4K = 48 →x2 = 4M + 8K = 96 ― ― 6K = ―36 K=6 M = 12 Atau 4M + 2K ― 60 = 2M +4K ― 48 2M ― 2K = 12 M= 6+K 4M + 2K = 60 4(6 + K) + 2K = 60 K=6 M = 12 23



Latihan : Sebuah perusahaan membuat dua macam produk (A dan B) dari dua sumberdaya SD1 dan SD 2. Jika perusahaan berhasil membuat produk tersebut, perusahaan akan memperoleh laba sebesar $ 8 (prodk A)dan $ 4 (produk B). Untuk membuat kedua produk tersebut setiap satu produk A yang diproses di SD 1 diperlukan waktu sebanyak 4 jam ,sedang untuk setiap satu produk B dibutuhkan waktu 5 jam, sedangkan SD 1 hanya tersedia waktu 20 jam. Pada SD 2,setiap satu produk A yang diproses diperlukan waktu sebanyak 2 jam,sedang untuk setiap satu produk B dibutuhkan waktu 6 jam, sementara SD 2 terbatas waktu sebanyak 18 jam saja. Saudara sebagai manajer RO, diminta untuk menyusun persoalan ini dalam bentuk LP untuk menentukan jumlah kedua produk yang akan dibuat . Selesaikan persoalan ini dengan metode grafik. 24



Metode Grafik / Minimasi



Contoh Soal Sebuah perusahan membuat bahan pelarut A dan B, yang menggunakan bahan Minyak tanah (MT), Damar (D) dan Spiritus (S). Biaya bahan pelarut A sebesar Rp 80,- dan bahan pelarut B sebesar Rp 100,-. Masing-masing bahan campurannya (MT,D dan S) minimal dibutuhkan sebanyak 24 liter Minyak Tanah, 20 Kg Damar, dan 24 liter spiritus. Untuk setiap bahan A dibutuhkan Minyak Tanah sebanyak 8 liter , 10 kg Damar dan 6 liter Spiritus. Untuk setiap bahan B dibutuhkan Minyak Tanah 6 liter, Damar 4 Kg, dan 12 liter Spiritus. Saudara diminta bantuan untuk menyelesaikan berapa bahan A dan B dibuat shingga biaya minimum ?. Selesaikan dengan metode grafik. 25



Metode Grafik / Minimasi GAMBAR FUNGSI KENDALA



B



Min. TC = 80A + 100B Stc. MT : 8A + 6B > 24 D : 10A + 4B > 20 S : 6A + 12B > 24 A,B > 0



MT : 8A + 6B > 24 B > 4 – 4/3 A



A



B



D : 10A + 4B > 20 B > 5 - 2,5 A



A



B



S : 6A + 12B > 24 B > 2 - 0,5 A



A



26



FISIBLE AREA dan ISO COST Solusi Optimal : B.Pelarut A = 2,4 unit B.Pelarut B = 0,8 unit TC min = 80 (2,4) + 100(0,8) = Rp 272 Penggunaan Sumberdaya : MT = 8(2,4) + 6(0,8) = 24 Lt.  persis D = 10(2,4) + 4(0,8) = 27,2 Kg.  > 20 S = 6(2,4) + 12(0,8) = 24 Lt.  persis



•( 2, 4 ; 0,8 ) 27



METODE SIMPLEK PENDAHULUAN Kenyataan yang sering dihadapi oleh para manajer dalam pengambilan keputusan adalah kompleks. Keputusan yang harus diambil tidak hanya untuk 2 variabel saja, bisa saja lebih, sementara metode grafik terbatas hanya 2 demensi atau paling banyak mencakup 3 variabel. Untuk mengatasi persoalan linier programming yang kompleks jelas menjadi tidak sederhana. Satu cara sederhana (simple) dan efisien yang dapat menyelesaikan persoalan adalah dengan Metode Simplex, di mana metode ini menggunakan tabel yang unik yang sering disebut “Tabel Simplek” 28



Metode simplek untuk linier programming dikembangkan pertama kali oleh George Dantzing pada tahun 1947, kemudian digunakan juga pada penugasan di Angkatan Udara Amerika Serikat. Dia mendemonstrasikan bagaimana menggunakan fungsi tujuan (iso-profit) dalam upaya menemukan solosi diantara beberapa kemungkinan solosi sebuah persoalan linier programming. Proses penyelesaiaanya dalam metode simplek, dilakukan secara berulang-ulang (iterative) sedemikian rupa dengan menggunakan pola tertentu (standart) sehingga solusi optimal tercapai. Ciri lain dari metode simplek adalah bahwa setiap solosi yang baru akan menghasilkan sebuah nilai fungsi tujuan yang lebih besar daripada solosi sebelumnya. 29



MENYUSUN SOLUSI AWAL Untuk memperoleh pengertian yg lebih mudah dan cepat, dalam pembahasan ini kita gunakan persoalan yang meliputi 2 variabel riil saja (sekedar untuk cross cek), kita gunakan kasus Persh,”XYZ” contoh pertama. Dengan menggunakan contoh kasus “XYZ”di muka, penyelesaian dapat dilakukan dengan beberapa langkah :



Langkah 1. Menyususun Persoalan Dalam Matematik Maksimumkan : TR = $ 3000A + 3000B Kendala : P : 2A + B < 30 Q : 2A + 3B < 60 R : 4A + 3B < 72 A,B > 0 30



Langkah 2. Mengubah Pertidaksamaan menjadi Persamaan Mengandung pengertian : tidak selalu kapasitas S.D digunakan seluruhnya, diantaranya masih ada yang tersisa  ada kelonggaran (slack) untuk menambah sebuah variabel sehingga menjadi persamaan. Variable baru ini disebut Variabel Slack = sejumlah unit kapasitas yang tidak dipakai dalam suatu Departemen (SD). Variabel Slack Misal : S1 = waktu yang tidak dipakai dlm.Dep.P  P :2A + B 60 pon P dan C > 0



44



SOLUSI AWAL



Metode Simplek / Minimasi



Merubah persamaan dan pertidaksamaan pada kendala - Untuk tanda Persamaan ( = ) harus ditambah dengan variabel Artifisial (A) - Untuk Pertidaksamaan”lebih besar sama dengan” ( > ) harus dikurangi variabel surplus (S) dan ditambah variabel Artifisial (A) - Untuk Pertidaksamaan kurang sama dengan ( < ) harus ditambah variabel slack (S) Utk Kendala : P + C = 200  P + C + A1 = 200 P < 80  P + S1 = 80 C > 60  C  S2 + A2 = 60 45



Metode Simplek / Minimasi



SOLUSI AWAL Koefisien teknologi (para meter) masing-masing variabel , secara ekplisit harus ditulis, dengan ketentuan yang tidak ada pengaruhnya ditulis nol Nilai biaya untuk variabel Artifisial diberi nilai yang sangat besar (M), dan untuk variabel Slack/Surplus = 0 Secara lengkap : Minimize: Cost = 3P + 8C + 0S1 + 0S2 + MA1 + MA2 P + C + A1 = 200 P + S1 = 80 C  S2 + A2 = 60 P, C, S1, S2, A1, A2 > 0 46



Metode Simplek / Minimasi



SOLUSI TABEL SIMPLEK Cj $M $0 $M



$M $0 $8



$M $3 $8



$0 $3 $8



BV A1 S1 A2 Zj Cj –Zj A1 S1 C Zj Cj –Zj A1 P C Zj Cj –Zj



$3 $8 Quantity P C 200 1 1 80 1 0 60 0 1 $260M $M $2M $3  $M $8  $2M 140 1 0 80 1 0 60 0 1 $140M+$480 $M $8 $3 - $M $0 60 0 0 80 1 0 60 0 1 $60M+ $720 $3 $8 $0 $0



$M A1 1 0 0 $M $0 1 0 0 $M $0 1 0 0 $M $0



$0 S1 0 1 0 $0 $0 0 1 0 $0 $0 1 1 0 $3  $M $M  $3 1 1 1  $5



S2 P C



60 80 120



0 1 0



0 0 1



1 0 1



Zj Cj –Zj



$1200



$3 $0



$8 $0



$8



$0 S2 0 0 1 $M $M 1 0 -1 $M-$8 $8-$M 1 0 -1



$M A2 0 0 1 $M $0 -1 0 1 $8-$M $2M-$8 -1 0 1



$M  $8 $8  $M 1 0 0



$8  $M $2M$8 -1 0 1



$0 $0



$8 $M - $8



Ri 200 60



140 80 -



60 60



47



Metode Simplek / Minimasi



SOLUSI TABEL SIMPLEK Cj $M $0 $M



$M $0 $8



$M $3 $8



$0 $3 $8



BV A1 S1 A2 Zj Cj –Zj A1 S1 C Zj Cj –Zj A1 P C Zj Cj –Zj



$3 $8 Quantity P C 200 1 1 80 1 0 60 0 1 $260M $M $2M $3  $M $8  $2M 140 1 0 80 1 0 60 0 1 $140M+$480 $M $8 $3 - $M $0 60 0 0 80 1 0 60 0 1 $60M+ $720 $3 $8 $0 $0



$M A1 1 0 0 $M $0 1 0 0 $M $0 1 0 0 $M $0



$0 S1 0 1 0 $0 $0 0 1 0 $0 $0 1 1 0 $3  $M $M  $3 1 1 1  $5 $5



S2 P C



60 80 120



0 1 0



0 0 1



1 0 1



Zj Cj –Zj



$1200



$3 $0



$8 $0



$8 $M  $8



$0 S2 0 0 1 $M $M 1 0 -1 $M-$8 $8-$M 1 0 -1



$M A2 0 0 1 $M $0 -1 0 1 $8-$M $2M-$8 -1 0 1



$M  $8 $8  $M 1 0 0



$8  $M $2M$8 -1 0 1



$0 $0



$8 $M - $8



Ri 200 60



140 80 -



- 60 60



48



Metode Simplek / Minimasi



SOLUSI TABEL SIMPLEK Cj $M $0 $M



$M $0 $8



$M $3 $8



$0 $3 $8



BV A1 S1 A2 Zj Cj –Zj A1 S1 C Zj Cj –Zj A1 P C Zj Cj –Zj



$3 $8 Quantity P C 200 1 1 80 1 0 60 0 1 $260M $M $2M $3  $M $8  $2M 140 1 0 80 1 0 60 0 1 $140M+$480 $M $8 $3 - $M $0 60 0 0 80 1 0 60 0 1 $60M+ $720 $3 $8 $0 $0



$M A1 1 0 0 $M $0 1 0 0 $M $0 1 0 0 $M $0



$0 S1 0 1 0 $0 $0 0 1 0 $0 $0 1 1 0 $3  $M $M  $3 1 1 1  $5 $5



S2 P C



60 80 120



0 1 0



0 0 1



1 0 1



Zj Cj –Zj



$1200



$3 $0



$8 $0



$8 $M  $8



$0 S2 0 0 1 $M $M 1 0 -1 $M-$8 $8-$M 1 0 -1



$M A2 0 0 1 $M $0 -1 0 1 $8-$M $2M-$8 -1 0 1



$M  $8 $8  $M 1 0 0



$8  $M $2M$8 -1 0 1



$0 $0



$8 $M - $8



Ri 200 60



140 80 -



- 60 60



49



DUALITAS ANTARA MAKSIMASI dan MINIMASI



Untuk setiap permasalahan optimasi yang mempunyai kendala/pembatas, akan terdapat “permasalahan dual”, yaitu dengan memaksimasi atau meminimasi fungsi kendala dan fungsi tujuan sebelumnya menjadi kendalanya. Hubungan ini disebut sebagai dualitas (duality) Permasalahan yang pertama disebut dengan “primal” dan permasalahan kedua disebut dengan “dual”. Jadi misalnya, jika permasalahan primalnya adalah maksimasi tujuan dengan kendala tertentu, maka sekarang menjadi dual, yaitu minimasi kendala dengan kendalanya adalah fungsi tujuannya. Demikian sebaliknya, jika permasalahan primalnya adalah menimasi tujuan dengan kendala tertentu, maka sekarang menjadi maksimasi kendala dengan fungsi tujuan sebagai 50 kendalanya.



Dengan demikian dalam sebuah pemodelan Pemrograman Linear, terdapat dua konsep yang saling berlawanan. Konsep yang pertama kita sebut Primal dan yang kedua Dual.Bentuk Dual adalah kebalikan dari bentuk Primal. Hubungan Primal dan Dual sebagai berikut: Masalah Primal (atau Dual) Masalah Dual (atau Primal) Koefisien fungsi tujuan …………… Nilai kanan fungsi batasan Maksimumkan Z (atau Y) ………… Minimumkan Y (atau Z) Batasan i …………………………… Variabel yi (atau xi) Bentuk < …………………………. yi > 0 Bentuk = …………………………… yi > dihilangkan Variabel Xj ………………………. . Batasan j Xj > 0 ………………………………. Bentuk < Xj > 0 dihilangkan ………………… Bentuk = 51



Contoh 1: Primal Minimumkan



Z = 5X1 + 2X2 + X3



Fungsi batasan: 1) 2X1 + 3X2 + X3 > 20 2) 6X1 + 8X2 + 5X3 > 30 3) 7X1 + X2 + 3X3 > 40 X1 , X2 , X3 > 0 Dual Maksimumkan Z ’ = 20Y1 + 30Y2 + 40Y3



Fungsi batasan:



1)



2Y1 + 6Y2 + 7Y3 < 5



2)



3Y1 + 8Y2 + Y3 < 2



3)



Y1 + 5Y2 + 3Y3 < 1



52



Langkah-langkah membentuk Dual



• Jika betuk primal adalah maksimasi, maka bentuk dual adalah minimasi, dan begitu sebaliknya. • Nilai sisi kanan dari kendala akan menjadi koefisien fungsi tujuan dalam bentuk Dual • Koefisien fungsi tujuan primal menjadi nilai sisi kanan dari kendala bentuk Dual. • Transpose koefisien fungsi kendala primal menjadi koefisien fungsi kendala Dual 53



CONTOH : ( Ek. Mikro) PRIMAL Maksimumkan : Q = L . C Kendala : 1200 = 30L + 40C L dan C optimum = ?



DUAL Minimumkan : B = 30L + 40C Kendala : 300 = L . C L dan C optimum = ?



Jawab Slope Isoquant = Slope Budget Line



Jawab Slope Isoquant = Slope Budget Line



1200 = 30L + 40 (3 / 4 L ) 1200 = 60L Jadi : L = 20 dan C = 15 Q max. = 20 x 15 = 300



L2 = 400 Jadi : L = (400)1/2 = 20 dan C = 15 Bmin. = 30(20) + 40 (15 ) = 1200



 MPL / MPC =  PL/ PC  C / L =  30/ 40 C = 3/ 4 L



dC



/ d L =  PL/ PC  300 / L2 =  30/ 40



54



CONTOH : USAHA KATERING (RANGSUM)



Kasus Primal sebuah usaha kesehatan dalam rangka membuat susunan rangsum dari berbagai bahan makanan dengan biaya murah adalah sbb. : Minimumkan : Z =150X1+100X2 +350X3 + 250X4 +320X5 Kendala : Protein : 8,3 X1 +246 X2 +17,2 X3+ 5,2 X4+ 2,01 X5 > 70 Karbohidrat : 5 X1 +26 X2 +595 X3 + 3,1 X4+ 4 X5 > 3000 Lemak : 0,4 X1 +793 X2 +4,8 X3 + 0,6 X4 +0,16 X5 > 800 Vitamin : 6 X1 +93 X2 +61,6 X3+ 6,8 X4 +2,05 X5 > 40 Zat Besi : 24,9X1 +243X2 +810 X3 +16,4X4 0,57 X5 > 12 Dimana : X1 = Nasi X4 = Buah X2 = Sayur X5 = Susu X3 = Lauk pauk 55 Buatlah model Dual persoalan di atas, dan selesaikan !



CONTOH : USAHA KATERING (RANGSUM)



Kasus Primal sebuah usaha kesehatan dalam rangka membuat susunan rangsum dari berbagai bahan makanan dengan biaya murah adalah sbb. : Minimumkan : Z =150X1+100X2 +350X3 + 250X4 +320X5 Kendala : Protein : 8,3 X1 +246 X2 +17,2 X3+ 5,2 X4+ 2,01 X5 > 70 Karbohidrat : 5 X1 +26 X2 +595 X3 + 3,1 X4+ 4 X5 > 3000 Lemak : 0,4 X1 +793 X2 +4,8 X3 + 0,6 X4 +0,16 X5 > 800 Vitamin : 6 X1 +93 X2 +61,6 X3+ 6,8 X4 +2,05 X5 > 40 Zat Besi : 24,9X1 +243X2 +810 X3 +16,4X4 0,57 X5 > 12 Dimana : X1 = Nasi X4 = Buah X2 = Sayur X5 = Susu X3 = Lauk pauk 56 Buatlah model Dual persoalan di atas, dan selesaikan !



JAWAB :



Maksimumkan : Z’ = 70Y1+3000Y2+800Y3+40Y4+12Y5



Kendala : X1 : 8,3 Y1+ 5,0 Y2 + 0,4 Y3 + 6,0 Y4 + 24,9 Y5 0 57



SOLUSI Cj Langka 1 0 0 0 0 0



Basic Quantity Variable



70 Y1



3000 Y2



800 Y3



40 Y4



12 Y5



0 0 0 0 0 slack 1 slack 2 slack 3 slack 4 slack 5



slack 1 slack 2 slack 3 slack 4 slack 5 zj cj-zj



150 100 350 250 320 0



8.3 246 17.2 5.2 2.01 0 70



5 26 595 3.1 4 0 3,000



0.4 793 14.8 0.6 0.16 0 800



6 93 61.6 6.8 2.05 0 40



24.9 243 810 16.4 0.57 0 12



1 0 0 0 0 0 0



0 1 0 0 0 0 0



0 0 1 0 0 0 0



0 0 0 1 0 0 0



0 0 0 0 1 0 0



slack 1 slack 2 Y2 slack 4 slack 5 zj cj-zj



147.0588 84.7059 0.5882 248.1765 317.6471 1,764.71



8.1555 0 0.2756 245.2484 0 792.3533 0.0289 1 0.0249 5.1104 0 0.5229 1.8944 0 0.0605 86.7227 3,000 74.6218 -16.7227 0 725.3782



5.4824 90.3082 0.1035 6.4791 1.6359 310.5882 -270.588



18.0933 207.605 1.3613 12.1798 -4.8754 4,084.03 -4,072.03



1 0 0 0 0 0 0



0 1 0 0 0 0 0



-0.0084 -0.0437 0.0017 -0.0052 -0.0067 5.042 -5.042



0 0 0 1 0 0 0



0 0 0 0 1 0 0



slack 1 Y3 Y2 slack 4 slack 5 zj cj-zj



147.0294 0.1069 0.5856 248.1206 317.6406 1,842.25



8.0701 0 0.3095 0 0.0212 1 4.9485 0 1.8756 0 311.241 3,000 -241.241 0



5.4509 0.114 0.1007 6.4195 1.629 393.263 -353.263



18.0211 0.262 1.3548 12.0428 -4.8912 4,274.09 -4,262.09



1 0 0 0 0 0 0



-0.0003 0.0013 0 -0.0007 -0.0001 0.9155 -0.9155



-0.0084 -0.0001 0.0017 -0.0052 -0.0067 5.002 -5.002



0 0 0 1 0 0 0



0 0 0 0 1 0 0



Langkah 2



0 0 3,000 0 0



Langkah3



0 800 3,000 0 0



0 1 0 0 0 800 0



58



59



Soal N0. 8 Perusahaan mebel Jati Indah memproduksi meja dan kursi dari sumberdaya tenaga kerja dan kayu. Perusahaan memiliki kapasitas terbatas untuk tenaga kerja 80 jam perhari dan 36 Kg kayu perhari. Permintaan atau penjualan kursi terbatas 6 kursi per hari. Untuk memproduksi satu unit kursi memerlukan 8 jam tenaga kerja dan 2 Kg kayu, sedang setiap satu meja memerlukan 10 jam tenaga kerja dan 6 Kg kayu. Laba yang diperoleh untuk setiap meja sebesar Rp 40.000 dan untuk setiap kursi sebesar Rp 50.000. Perusahaan ingin menetapkan jumlah meja dan kursi yang harus dijual agar memperoleh laba maksimum. a. Formulasikan model LP untuk persoalan ini. b. Selesaikan persoalan ini dengan analisis grafik. 60



SOAL N0. 8



M Maximize



K



Kap



40000 50000



Labor



10



8



= >= >=



RHS



Dual



6 4 12 $230.000,



-15000 -35000 0



Soal N0.12



63



Soal N0.12 Variable Status BAHAN 1 Basic BAHAN 2 Basic surplus 1 NONBasic surplus 2 NONBasic surplus 3 Basic Optimal Value (Z)



Value 1 3 0 0 8 230000



64



Soal N0.12 Cj Iterati 1



Basic Variables



0 artfcl 1 0 artfcl 2 0 artfcl 3 Zj cj-zj Iteratn 2 0 artfcl 1 0 artfcl 2 50.000 BHN 2 Zj cj-zj Iterati 3 80.000 BHN 1 0 artfcl 2 50.000 BHN 2 Zj cj-zj Iterati 4 80.000 BHN 1 0 surplus 1 50.000 BHN 2 Zj cj-zj Iterati 5 80.000 BHN 1 0 surplus 1 50.000 BHN 2 Zj cj-zj Iterati 6 80.000 BHN 1 0 surplus 3 50.000 BHN 2



80000 BHN 1



50000 BHN 2



0 artfcl 1



0 surplus 1



0 artfcl 2



0 surplus 2



0 artfcl 3



6 4 12 22



3 1 2 79.994 6



1 1 6 49.992 8



1 0 0 0 0



-1 0 0 1 -1



0 1 0 0 0



0 -1 0 1 -1



0 0 1 0 0



0 surplu 3 $ 0 0 -1 1 -1



4 2 2 6



2,6667 0,6667 0,3333 79.996,66 3,3333



0 0 1 50.000 0



1 0 0 0 0



-1 0 0 1 -1



0 1 0 0 0



0 -1 0 1 -1



-0,1667 -0,1667 0,1667 1,3333 -1,3333



0,1667 0,1667 -0,1667 -0,3333 0,3333



1,5 1 1,5 1



1 0 0 80.000 0



0 0 1 50.000 0



0,375 -0,25 -0,125 1,25 -1,25



-0,375 0,25 0,125 -0,25 0,25



0 1 0 0 0



0 -1 0 1 -1



-0,0625 -0,125 0,1875 1,125 -1,125



0,0625 0,125 -0,1875 -0,125 0,125



3 4 1 0



1 0 0 80.000 0



0 0 1 50.000 0



0 -1 0 1 -1



0 1 0 0 0



1,5 4 -0,5 1 -1



-1,5 -4 0,5 0 0



-0,25 -0,5 0,25 1 -1



0,25 0,5 -0,25 0 0



3 4 1



1 0 0



0 0 1



0 -1 0



0 1 0



1,5 4 -0,5



-1,5 -4 0,5



-0,25 -0,5 0,25



0,25 0,5 -0,25



289.999,99



80.000



50.000



0



0



-95.000



95.000



7.500,00



-7.500,00



0



0



0



0



95.000,00



-95.000,00



-7.500,00



7.500,00



1 0 0



0 0 1



0,5 -2 -0,5



-0,5 2 0,5



-0,5 8 1,5



0,5 -8 -1,5



0 -1 0



Quantity



1 8 3



0 1 0 65



KASUS UCP SD



X1



X2



Kap.



Sur.



Klaim



16



12



> 450



30



Rusak



0,5



1,4



> 25



31



Kompt



1



1



< 40



0



C



Solusi



64000 42000



0



40



TC = 168000



66



KASUS Giman Piza



SD



PI



PS



Kap



Slack



DM



1



1



< 150



17,5



TM



4



8



< 800



0



Sales PI



1



< 75



0



< 125



62,5



Sales PI



1



Laba



500



750



Solusi



75



62,5



84375



67



KASUS Toko Perhiasan



Sd



K



G



Kap



Emas



30



20



18



Platina



20



40



20



1



40



DG



Slack



Laba 300000 400000 Solusi



0,4



0,3



L=24000068



KASUS Obat Sd



B1



B2



Kap



Sur



A1



3



1



>6



0



A2



1



1



>4



0



A3



2



6



> 12



8



TC Solusi



80000 50000 1



3



TC=230000



69



KASUS Usaha Ternak



Min. TC = 60A + 100K Stc. Pr : 20 A + 40 K Lm : 2 A + 0,5 K Prod. : 1 A + 1 K A, K



> 30 > 1 < 1 ,> 0



78,571 43



Sd



A



K



kap



Slack



Pr



20



40



> 30



0



Lm



2



0,5



>1



0



Prod



1



1



0



Sd



C



T



kap



Slack



K



8



6



< 120



0



Tom



3



6



< 90



0



B



3



2



< 45



3



Prod



1



1



< 24



6



Solusi



6



12



Laba



12



24



36



71



KASUS Untitled



Mak. L = 3 X + 2 Y Stc. A : 3 X + 2 Y < 120 F : 1 X + 2 Y < 80 Pro X : 1 X + 0 Y > 10 Pro Y : 0 X + 1 Y > 10 X, Y > 0 Sd



X



Y



kap



S



A



3



2



< 120



0



F



1



2



< 80



26,67



Pro X



1



-



> 10



13,33



Pro Y



-



1



> 10



0



120



72



Solusi 33,33



10



Laba



20



100



73