You're Reading a Free Preview
Pages 7 to 8 are not shown in this preview.
You're Reading a Free Preview
Pages 13 to 26 are not shown in this preview.
REFERENSI MATERI PEMROGRAMAN LINEAR KELAS REGULER & NON SEMESTER 4 - Marchasan Lexbin PROGRAM STUDI PENDIDIKAN MATEMATIKA FMS IKIP SILIWANGI CIMAHI MANDIRI APRIL
KATA PENGANTAR Tak mudah melakukan sesuatu dengan harus tetap memperhatikan capaian tujuannya dalam konteks menjaga mutu. Hal seperti itulah yang terjadi sejalan upaya melahirkan referensi materi pemrograman linear di - ini. Kondisi pandemi yang belum juga berakhir ditambah karakteritik mahasiswa yang dihadapi kelas reguler dan kelas non reguler yang tentunya berkarakteristik tak sama juga dikeduanya ada yang berlatarbelakang menengah kejuruan tataboga kesehatan dll juga menjadi pertimbangan. Penulis praktis tak menulis buku ini, tetapi kembali menuliskan materi dari bab bab tertentu dari literatur yang ada dengan sedikit penyederhanaan dan penambahan diawali program linear materi SMA yang dilakukan sesuai dengan silabus yang disepakati mahasiswa paska pertemuan pertama. Buku buku dimaksud tertulis diantara daftar rujukan. Terkait hal di atas, trimakasih disampaikan kepada penuls buku sumber terkhusus ke DR Ruminta. Sekalipun belum berkesempatan sy bersilaturahmi dan memohon ijin. Mudahan esensi pra kata ini bermakna sama disertai harapan upaya ini menjadi barokah bagi anak anak yang hebat dan sedang terus berjuang tuk menjadi lebih hebat bagi dirinya keluarganya n NKRI tercinta melalui bidang bidang masing masing di depan hari di saat kondisi tak kondusif saat ini. Setelah daftar rujukan tersaji pokok pokok materi perkuliahan merujuk RPS yang dikembangkan Ibu Indah Puspita dan Bu Aflich Yusnitha Prodi Math FMS IKIP Siliwangi walau mungkin tak sampai dualitas dan dengan penyedehanaan Semangat smua dan salam sehat. 7 April. Marchasan Lexbin i
DAFTAR ISI Kata Pengantar Daftar Isi.. i ii Bab I. Sistem Pertidaksamaan Linear. Bab II. Pemrograman Linear. Bab III. Simpleks. 4 Daftar Rujukan. 76 Lampiran. 77 ii
BAB I SISTEM PERTIDAKSAMAAN LINEAR Contoh nomor : Seorang ibu hendak membuat macam kue untuk keperluan pesta. Kue A memerlukan kg tepung terigu dan 4 butir telur untuk membuat loyang kue. Untuk membuat loyang kue B, diperlukan g tepung terigu dan butir telur. bahan yang tersedia dirumah adalah kg tepung terigu dan 4 butir telur. Berapa jumlah maksimal kue A dan B yang dapat dibuat tanpa harus membeli bahan lagi? Model matematika pada contoh nomor di subbab sebelumnya dapat dituliskan kembali sebagai berikut. Memaksimumkan z = x + y dengan kendala,5x +,y 4x + y 4 X, y Keempat pertidaksamaan pada contoh kendala ini yaitu,5x +,y.. () 4x + y 4 () x () y. (4) membentuk suatu sistem pertidaksamaan linear. Penyelesaian dari sistem ini harus memenuhi keempat pertidaksamaan di atas. Jika model matematikanya hanya mempunyai dua peubah control, maka untuk mencari penyelesaian sistem ini dapat digunakan bantuan grafik fungsi. Langkah yang harus dilakukan adalah sebagai berikut.. Ubah masing-masing pertidaksamaan menjadi persamaan untuk fungsi kendala. Kemudian gambarkan grafik persamaan tersebut dalam bidang Cartesius. Untuk contoh nomor subbab sebelumnya, pertidaksamaan () menjadi
,5x +,y = Atau 5x + y =. Tentukam daerah yang memenuhi pertidaksamaan. Daerah ini disebut daerah penyelesaiannya. Untuk,5x +,y atau 5x + y, daerah yang memenuhi adalah daerah yang diarsir pada gambar. berikut ini. y 4 x Gambar. Cara yang mudah untuk menentukan daerah penyelesaiannya adalah dengan menentukan salah satu titik kemudian disubstitusikan ke pertidaksamaan. Contohnya, kita pilih titik (,) kemudian substitusi titik (,) ke dalam pertidaksamaan, menjadi,5() +,() = ( memenuhi). Jadi, daerah penyelesian pertidaksamaan,5x +,y adalah daerah di mana titik (,) berada.. Ulangi langkah dan untuk semua pertidaksamaan dalam sistem dan tentukan daerah yang memenuhinya. 4x + y 4
y 8 6 6 x Gambar. X y x
Gambar. y y X Gambar.4 4. gambarkan semua daerah yang memenuhi pertidaksamaan pada fungsi kendala ke dalam satu bidang cartesius. y 8 A Gambar.5 B(,5) D 4 6 x 4
Titik potong garis 5x + y = dan 4x + y = 4 adalah titik B(,5). Himpunan penyelesaian dari sistem pada contoh di atas adalah daerah yang di arsir. titik-titik dari daerah atau himpunan penyelesian disebut titik-titik verteks. Untuk gambar.5 diperoleh 4 titik verteks, yaitu A(,8), B(,5), C(4,), dan D(,). Latihan Gambar daerah penyelesaian dari sistem pertidaksamaan linear di bawah ini.. x + y 4 x + 7y 4 x y. x y 6 x + 7y X Y. x + 9y 8 X + y X Y 4. 6x + y 8 x 4y 8 X Y 5. y x 6 5x y X Y 6. Sebuah perusahaan membuat kotak besi jenis A dan B dengan menggunakan mesin, yakni M dan M. Proses pembuatan kotak A di mesin M berlangsung selama menit dan di mesin M selama 4 menit. Untuk pembuatan kotak B, proses di mesin M berlangsung selama 8 menit dan di mesin M selama 4 menit. Keuntungan untuk membuat kotak A adalah Rp 8., perbuah dan untuk kotak B adalah Rp 5
5., perbuah. Tentukan rencana produksi untuk memaksimalkan keuntungan setiap jam produksi. 7. Seorang pasien di rumah sakit memerlukan paling sedikit 84 unit obat A dan unit obat B setiap hari. Dengan anggapan bahwa kelebihan dosis dari salah satu obat tidak mengakibatkan hal yang fatal. Setiap gram substansi M mengandung unit obat A dan 8 unit obat B. setiap gram substansi N memuat unit obat A dan 4 unit obat B. berapa jumlah subtansi M dan N yang dapat dicampurkan agar memenuhi kebutuhan minimum setiap hari? Model Matematika Sistem pertidaksamaan linear yang telah dijelaskan sebelumnya dapat diterapkan pada permasalahan sehari-hari dengan memodelkan permasalahan tersebut ke dalam model matematika. Sebagai ilustrasi perhatikan contoh berikut. PT. Samba Lababan memproduksi ban motor dan ban sepeda. Proses pembuatan ban motor melalui tiga mesin, yaitu menit pada mesin I, 8 menit pada mesin II, dan menit pada mesin III. Adapun ban sepeda diprosesnya melalui dua mesin, yaitu 5 menit pada mesin I dan 4 menit pada mesin II. Tiap mesin ini dapat dioperasikan 8 menit per hari. Untuk memperoleh keuntungan maksimum, rencananya perusahaan ini akan mengambil keuntungan Rp 4., dari setiap penjualan ban motor dan Rp., dari setiap penjualan ban sepeda. Berdasarkan keuntungan yang ingin dicapai ini, maka pihak perusahaan merencanakan banyak ban motor dan banyak ban sepeda yang akan di produksinya dengan merumuskan berbagai kendala sebagai berikut. Perusahaan tersebut memisalkan banyak ban motor yang diproduksi sebagai x dan banyak ban sepeda yang diproduksi sebagai y, dengan x dan y bilangan asli. Dengan menggunakan variable x dan y tersebut, perusahaan itu membuat rumusan kendala-kendala sebagai berikut. Pada mesin I : x + 5y 8 Persamaan Pada mesin II : 8x + 4y 8 Persamaan 6
Pada mesin III : x 8 Persamaan x, y bilangan asli : x, y Persamaan 4 Fungsi tujuan (objektif) yang digunakan untuk memaksimumkan keuntungan adalah f(x,y) = 4.x +.y. dalam merumuskan masalah tersebut, PT. Samba Lababan telah membuat model matematikan dari suatu masalah program linear. Nilai Optimum Suatu Fungsi Objektif Dalam pemodelan matematika masalah produksi ban PT. Samba Lababan, kalian akan mencari nilai x dan y sedemikian sehingga f(x,y) = 4.x +.y maksimum. Bentuk umum dari fungsi tersebut adalah f (x,y) = ax + by. Suatu fungsi yang dioptimumkan (maksimum atau minimum). Fungsi ini disebut fungsi objektif. Untuk menentukan nilai optimum fungsi objektif ini, kalian dapat menggunakan dua metode, yaitu metode uji titik pojok dan metode garis selidik. Metode Uji Titik Pojok Untuk menentukan nilai optimum fungsi objektif dengann menggunakan metode uji titik pojok, lakukalah langkah-langkah berikut. a. Gambarlah daerah penyelesaian dari kendala-kendala dalam masalah program linear tersebut. b. Tentukan titik-titik pojok dari daerah penyelesaian itu. c. Substitusikan koordinat setiap titik pojok itu ke dalam fungsi objektif. d. Bandingkan nilai-nilai fungsi objektif tersebut. Nilai terbesar berarti menunjukan nilai maksimum dari fungsi f(x,y), sedangkan nilai terkecil berarti menunjukan nilai minimum dari fungsi f (x,y). Sebagai contoh, kalian akan memaksimumkan keuntungan PT.Samba Lababan dari produksi ban dengan model matematika f(x,y) = 4.x +.y. 7
y D C 6 HP x Daerah kanan x 8 x+5y 8 4 B O Gambar.6 Daerah penyelesaian yang memenuhi x + 5y 8; 8x +4y 8; x, y A 8 8x+4y 8 4 Perhatikan daerah penyelesaian dari grafik pada gambar di atas. a. Titik-titik pojoknya adalah titik O, A, B, C, dan D. titik O adalah titik pusat koordinat. Jadi, titik O(,). Titik A adalah titik potong antara garis x = 8 dan sumbu x. Jadi, titik A(8, ). Titik B adalah titik potong antara garis x = 8 dan garis 8x + 4y = 8. Substitusi x = 8 ke persamaan 8x + 4y = 8 8. 8 + 4y = 8 y = 4, jadi titik B (8,4) Titik C adalah titik potong antara garis 8x + 4y = 8 dan x + 5y = 8. Dari 8x + 4y = 8 didapat y = x. Substitusi nilai y ke persamaan x + 5y = 8 x + 5( x) = 8 x + x = 8-8x = - X = 5 8
Substitusi x = 5 ke persamaan y = x y =. 5 y = 5, jadi titik C ( 5,5). Titik D adalah titik potong antara garis x + 5y = 8 dan sumbu y. Substitusi x = ke persamaan x + 5y = 8. + 5y = 8 5y = 8 y = 6, jadi titik D (,6). b. Uji titik-titik pojok ke fungsi objektif f(x,y) = 4.x +.y, sehingga fungsi objektif ini maksimum. Titik pojok ( x,y ) f(x,y) = 4.x +.y A (8,).. B (8,4) 4.4. C (5,5) 5.5. D (,6) 4.8. Dari table tersebut dapat diperoleh nilai maksimum fungsi objektif f(x,y) = 4.x +.y adalah f(5,5) = 5.5.. Jadi PT.Samba Lababan harus memproduksi 5 ban motor dan 5 ban sepeda untuk memperoleh keuntungan maksimum. 9
C. Metode garis selidik Untuk menentukan nilai optimum fungsi objektif dengan menggunakan metode garis selidik, lakukanlah langkah-langkah berikut. a. Tentukan garis selidik, yaitu garis-garis yang sejajar dengan garis ax + by = k, a >, b >, dan k Ԑ R. b. Gambar garis selidik-garis selidik tersebut pada koordinat Cartesius! c. Untuk menentukan nilai maksimum fungsi tujuan maka carilah garis selidik yang jaraknya terbesar terhadap titik pusat O(,) dan berada dalam daerah penyelesaian. Sedangkan untuk menentukan nilai minimum fungsi tujuan maka carilah garis selidik yang jaraknya terkecil terhadap titik pusat O(,) dan y berada pada daerah penyelesaian. Sebagai contoh, grafik berikut ini adalah produksi ban PT. Samba Lababan. x + y 5 5 C 5 B 5 x Daerah kanan HP y A Daerah atas x + y x Gambar.7 Daerah penyelesaian yang memenuhi x + y ; x + y 5; x ; y Garis selidik dari fungsi objektif f(x,y) = 4.x +.y adalah 4x + y = k. Ambil k =, didapat garis selidik 4x + y = Ambil k = 4, didapat garis selidik 4x + y = 4 Ambil k = 55, didapat garis selidik 4x + y = 55
Gambarkan garis-garis selidik ini sehingga kamu dapat menentukan nilai maksimum fungsi objektif f(x,y) = 4.x +.y. y x = 8 6 4x + y = 4 8 x + 5y = 8 4x + y = 4 8x + 4y = 8 4x + y = 55 x O 6 Gambar.8 Garis-garis selidik yang memenuhi x + 5y = 8; 4x +y = 55; 8x + 4y = 8; 4x + y = 4; 4x +y = 4 Perhatikan bahwa garis selidik yang menyebabkan fungsi objektif maksimum adalah 4x + y = 55 Dengan menglikan kedua ruas persamaan garis selidik dengan., kamu mendapatkam nilai maksimum fungsi objektif sebagai berikut..(4x + y) =.(55) 4.x +.y = 5.5. Jadi nilai maksimum fungsi objektif f(x,y) = 4.x +.y adalah 5.5.. Dari gambar di atas tampak bahwa garis selidik 4x + y = 55 melalui titik C ( 5,5). Ini berarti, fungsi objektif f(x,y) = 4.x +.y mencapai maksimum pada titik C(5,5). Jadi, PT. Samba Lababan harus memproduksi 5 ban motor dan 5 ban sepeda untuk memperoleh keuntungan maksimum Rp 5.5..
. Definisi Pemrograman Linier BAB II PEMROGRAMAN LINIER Pemrograman linier (PL) adalah metode optimasi untuk menentukan nilai optimum dari fungsi tujuan linier pada kondisi pembatasanpembatasan (constraints) tertentu. Pembatasan-pembatasan tersebut biasanya keterbatasan yang berkaitan dengan sumber daya seperti : a. Bahan mentah b. Uang c. Waktu d. Tenaga kerja dll. Persoalan pemrograman linier dapat ditemukan pada berbagai bidang dan dapat digunakan untuk membantu membuat keputusan untuk memilih suatu alternatif yang paling tepat dan pemecahan yang paling baik (the best solution). Aplikasi pemrograman linier misalnya untuk keperluan : a. Realokasi sumber daya b. Produksi campuran, c. Penjadwalan, d. Keputusan investasi, e. Perencanaan produksi, f. Masalah transportasi, logistic, dll... Elemen Pemrograman Linier Ada tiga elemen penting dalam pemrograman linier yaitu : a. Variabel keputusan (decision variables) : x, x,, xn adalah variable yang nilai-nilainya dipilih untuk dibuat keputusan. b. Fungsi tujuan (objective function): Z= f(x, x,, xn) adalah fungsi yang akan dioptimasi (dimaksimumkan atau diminimumkan). c. Pembatasan (constraints): gi ( x, x,..., xn) b adalah pembatasan-pembatasan yang harus dipenuhi.
.. Pola Umum Pemrograman Linier Menentukan variabel keputusan (decision variables) yaitu : x, x,, xn sedemikian rupa untuk mengoptimalkan fungsi tujuan (objective function) f(x, x,, xn) yang memenuhi pembatasan-pembatasan (constraints) gi ( x, x,..., xn) b (i=,,, m). Variabel keputusan x, x,, xn merupakan nilai non-negatif atau x untuk semua j=,,.., n. a. Nilai variabel keputusan x, x,, xn yang memenuhi semua pembatasan-pembatasan model disebut solusi layak (feasible). b. Nilai variabel keputusan x, x,, xn yang memberikan nilai fungsi tujuan optimum ( maksimum atau minimum ) dan memenuhi pembatasan-pembatasan disebut solusi optimum... Asumsi Pemrograman Linier Penggunan pemrograman linier untuk mendekati dan merepresentasikan situasi kehidupan nyata menggunakan beberapa asumsi yaitu :. Proporsionalitas. Kontribusi masing-masing variabel keputusan terhadap fungsi tujuan dan pembatasan-pembatasan adalah proporsional langsung terhadap nilai variabel keputusan.. Aditivitas. Kontribusi terhadap fungsi tujuan dan pembatasanpembatasan untuk beberapa variabel adalah independen (bebas) dari variabel keputusan yang lain sehingga kontribusi masing-masing variabel keputusan dapat digabungkan/ditambahkan menjadi kontribusi total.. Divisibilitas. Variabel keputusan adalah kontinu sehingga dapat diambil nilai fraksionalnya. 4. Deterministik. Semua parameter (fungsi tujuan, pembatasanpembatasan, seluruh koefisien) diketahui dengan pasti dan tetap tidak berubah selama dilakukan kajian atau analisis.. Model Pemrograman Linier Ada dua model pemrograman linier yaitu model pemrograman linier persoalan maksimum (maksimasi) dan model pemrograman linier persoalan minimum (minimasi).
.. Model Pemrograman Linier Maksimum Mencari variabel keputusan nonnegative (xi) yang memenuhi fungsi tujuan maksimum. a. Tentukan variabel keputusan: x, x,, xn b. Sedemikian rupa sehingga (S.r.s) : Z = c x + cx + + cnxn : Fungsi tujuan maksimum c. Dengan pembatasan-pembatasan (D.p) : a x + a x + + an xn b a x + a x + + an xn b am x + am x + + amn xn bm Di mana x, x,, xn.. Model Pemrograman Linier Minimum Mencari variabel keputusan nonnegative (xi) yang memenuhi fungsi tujuan minimum. a. Tentukan variabel keputusan : x, x,, xn b. Sedemikian rupa sehingga (S.r.s): Z = c x + cx + + cnxn : Fungsi tujuan minimum c. Dengan pembatasan-pembatasan (D.p) : a x + a x + + an xn b a x + a x + + an xn b am x + am x + + amn xn bm Di mana x, x,, xn. Persoalan Pemrograman Linier Persoalan pemrograman linier adalah persoalan optimasi yang memenuhi ketentuan berikut :. Fungsi tujuan merupakan fungsi linier dari variabel keputusan. 4
. Nilai variabel keputusan harus memenuhi pembatasanpembatasan. Setiap pembatasan harus berbentuk persamaan atau ketidaksamaan linier.. Setiap variabel keputusan harus dibatasi yaitu nonnegatif. Syarat dari Persoalan Pemrograman Linier Ada beberapa persyaratan penting dalam merumuskan persoalan pemrograman linier yaitu :. Ada beberapa kuantitas yang memungkinkan dioptimasi untuk digunakan sebagai tujuan.. Ada variabel-variabel yang dapat dibuat variabel keputusan.. Ada pembatasan kemampuan dalam mencapai tujuan. 4. Ada langkah-langkah alternatif pemecahan yang dapat dipilih. 5. Tujuan dan pembatasan-pembatasan harus dapat diekspresikan dalam persamaan atau ketidaksamaan linier. Tahapan Memformulasikan Persoalan Pemrograman Linier Ada beberapa tahapan dalam memformulasikan persoalan pemrograman linier yaitu :. Memahami persoalan secara keseluruhan apakah persoalan tersebut adalah persoalan maksimum atau minimum.. Mengidentifikasi variabel keputusan.. Mendeskripsikan fungsi tujuan sebagai kombinasi linier dari variabel keputusan. 4. Mendeskripsikan pembatasan-pembatasan sebagai kombinasi linier dari varibel keputusan. 5. Mengidentifikasi batas bawah atau batas atas variabel keputusan. 6. Mengekspresikan semua hasil identifikasi tersebut dalam formula matematika. 5
Contoh :. Formulasikan persoalan pemrograman linier berikut. Suatu perusahaan makanan akan memproduksi dua jenis makanan yaitu brownie kukus dan eskrim cokelat. Satu satuan brownie kukus diperlukan bahan 4 ons coklat dan ons gula. Sedangkan satu satuan eskrim coklat diperlukan bahan ons coklat dan ons gula. Perusahaan tersebut mempunyai dua buah bahan mentah yaitu coklat murni dan gula yaitu masing-masing 6 kg dan 48 kg. harga satuan brownie kukus Rp 4 ribu dan eskrim coklat Rp ribu. Berapa banyak brownie kukus dan eskrim coklat yang harus diproduksi supaya hasil penjualan yang maksimum dengan memanfaatkan semua bahan mentah tersebut. Solusi :. Persoalan pemrograman tersebut adalah persoalan maksimum.. Variabel keputusan : x = brownie kukus x = eskrim coklat. Fungsi tujuan sebagai kombinasi linier variabel keputusan : Z = 4x + x (maksimum) 4. Pembatasan sebagai kombinasi linier variabel keputusan : 4x + x 6 (coklat) x + x 48 (gula) 5. Batas bawah dan atas variabel keputusan : x dan x 6. Formulasi matematika persoalan pemrograman tersebut : Cari x dan x S.r.s : z = 4x + x (maksimum) D.p : 4x + x 6 x + x 48 x, x 6
. Formulasikan persoalan pemrograman linier berikut. Suatu perusahaan garmen akan memproduksi dua jenis pakaian yaitu baju dan celana panjang. Proses produksi meliputi memotong, menjahit, dan packaging. Perusahaan tersebut mempekerjakan 5 orang pada bagian memotong, 4 orang pada bagian menjahit, dan 5 orang pada bagian packaging. Semua tenaga kerja tersebut bekerja 8 jam per hari selama 5 hari kerja dalam seminggu. Tabel berikut menunjukkan waktu yang diperlukan dan keuntungan (profit) per satuan untuk pakaian tersebut. Table.. Waktu yang diperlukan dan keuntungan per satuan pakaian Pakaian Memotong Menjahit Packaging Profit (Rp) Baju. 8 Celana. Panjang Berapa produksi pakaian optimum mingguan pada perusahaan tersebut. Solusi :. Persoalan pemrograman tersebut adalah persoalan maksimum.. Variabel keputusan : x = baju x = celana panjang. Fungsi tujuan sebagai kombinasi linier variabel keputusan : Z = 8x + x (maksimum) 4. Pembatasan sebagai kombinasi linier variabel keputusan : X + x 5x8x5 (memotong) x + x 4x8x5 (menjahit).x +.x 5x8x5 (packaging) 7
5. Batas bawah dan atas variabel keputusan : x dan x 6. Formulasi matematika persoalan pemrograman tersebut adalah : Cari x dan x S.r.s : z = 8x + x (maksimum) D.p : x + x x + x 6.x +.x x, x. Formulasikan persoalan pemrograman linier berikut. Suatu perusahaan mobil akan memasang iklan di media cetak dan televise. Perusahaan tersebut bertujuan memilih cara beriklan yang paling efektif sehingga biayanya minimum dan sasaran iklan mencapai lebih dari 4 juta orang yang di antaranya 5 juta orang berpendapatan lebih dari Rp 5 juta/bulan. Biaya memasang iklan di media cetak sebesar Rp M dan di televise sebesar Rp 8 M. Pembaca media cetak sebanyak 4 juta orang dan penonton televisi sebanyak juta orang. Di antara pembaca media cetak terdapat juta orang berpendapatan lebih dari Rp 5 juta/bulan dan di antara penonton televisi terdapat juta orang berpendapatan lebih dari Rp 5 juta/bulan. Solusi :. Persoalan pemrograman tersebut adalah persoalan minimum. Variabel keputusan : X = media cetak X = televis. Fungsi tujuan sebagai kombinasi linier variabel keputusan : Z = x + 8x (minimum) 8
4. Pembatasan sebagai kombinasi linier variabel keputusan : 4x + x 4 (pembaca media cetak dan penonton televisi) x + x 5 ( pendapatan lebih dari Rp 5 juta/bulan ) 5. Batas bawah dan atas variabel keputusan : x dan x 6. Formulasi matematika persoalan pemrograman tersebut : Cari x dan x S.r.s : z = x + 8x (minimum) D.p. : 4x + x 4 x + x 5 X, x.4 Solusi Persoalan Pemrograman Linier Solusi persoalan pemrograman linier didasarkan pada identifikasi variabel keputusan (decision variables) yaitu x, x,..., xn, tujuan (objective function) yaitu z(x, x,..., xn), dan pembatasanpembatasan (constraints) yaitu gi(x, x,..., xn) bi (i =,,, m). Variabel keputusan x, x,..., xn merupakan nilai non negatif atau xj untuk semua j =,,, n. Nilai variabel keputusan x, x,..., xn yang memenuhu semua pembatasan-pembatasan model disebut solusi layak (feasible). Nilai variabel keputusan x, x,..., xn yang memberikan nilai fungsi tujuan optimum (maksimum atau minimum) dan memenuhi pembatasan-pembatasan disebut solusi optimum. Setelah persoalan pemrograman linier (PL) dapat diidentifikasi variabel keputusan, fungsi tujuan, dan pembatasannya yang diformulasikan ke dalam bentuk matematik, maka persoalan pemrograman linier tersebut dapat dipecahkan menggunakan beberapa metode seperti metode grafik, metode subtitusi, dan metode simplex..5 Metode Grafik Metode grafik dipergunakan untuk menyelesaikan pemrograman linier yang mempunyai dua (atau kadang-kadang ) variabel keputusan. 9
Pemecahan pemrograman linier menggunakan metode grafik terdiri dari dua fase yaitu :. Menentukan ruang/ daerah penyelesaian (solusi) yang feasible yaitu menemukan nilai variabel keputusan di mana semua pembatasan bertemu.. Menemukan solusi optimal dari semua titik di ruang/daerah feasible. A. Tahapan Menentukan Ruang/Daerah Feasible. Gambarlah sumbu vertical dan sumbu horizontal (sumbu dimensi) yang mewakili nilai variabel keputusan.. Semua variabel keputusan adalah non-negatif menunjukan bahwa daerah feasible hanya berada pada kuadran pertama.. Gambarlah semua pembatasan sebagai garis (setiap ketidaksamaan pembatasan diubah menjadi persamaan). Untuk menggambar garis tersebut gunakan (x, o) dan (o, x). 4. Pada setiap ketidaksamaan pembatasan, tentukan daerah feasible-nya. 5. Tentukan interseksi dari semua daerah feasible yang didefinisikan semua pembatasan. Langkah ini akan menghasilkan daerah feasible.
5 Pembatasan Pembatasan 5 Pembatasan 5 Daerah feasible 5 5 5 Gambar. Daerah feasible dan garis pembatasan B. Tahapan menentukan Solusi Optimum Ada metode untuk mengidentifkasi solusi optimum pada ruang/daerah feasible yaitu metode kesamaan garis (isoline) dan metode titik ekstrim. a. Metode Isoline. Tentukan kemiringan garis fungsi tujuan (merupakan himpunan infinitive dari isoline). o Pilihlah dua titik tertentu di daerah feasible. o Gambarlah garis fungsi tujuan yang mengenai titik-titik tertentu.. Tentukan arah peningkatan (penurunan) dari fungsi tujuan persoalan maksimum (minimum). pilliihlah dua garis (isoline) fungsi tujuan di daerah feasible dan evaluasi nilai fungsi tujuan pada kedua garis isoline tersebut.
. Ikuti arah peningkatan atau penurunan sampai mencapai titik batas (sudut) d mana peningkatan atau penurunan dari fungsi tujuan keluar dari daerah feasible. 4. Solusi optimum diperoleh dari titik batas di mana peningkatan atau penurunan dari fungsi tujuan (Z) akan meninggalkan feasible. X 5 Z Z 5 Z (solusi optimum) Z 5 Daerah feasible ba X 5 5 5 Gambar. daerah feasible, garis fungsi tujuan dan solusi optimum
b. Metode titik Ekstrim. Tentukan interseksi dari semua daerah feasible yang didefinisikan semua pembatasan sehingga diperoleh daerah feasible.. Tentukan titik ekstrim (sudut) dari daerah feasible. Setiap titik ekstrim merupakan titik interseksi dari dua pembatasan linier.. Tentukan nilai fungsi tujuan (Z) pada setiap titik ekstrim daerah feasible. Solusi optimum terletak pada salah satu titik ekstrim daerah feasible. X 5 Z Z 5 5 Z 4 Z 5 5 Daerah feasible ba Z 5 5 5 Gambar. Garis pembatasan dan titik ekstrim daerah feasible
Contoh :. Tentukan solusi dari persoalan pemrograman linier berikut. Cari x dan x S.r.s : Z = 5 x + x ( maksimum) D.p : x + x 9 x + 6 x 566 x + 6 x 88, x Solusi : Gambarlah semua garis pembatasan pada bidang datar (sumbu vertikal dan horizontal) untuk menentukan daerah feasible. X + x x + x = 9 x + 6 x 566 9 x + 6 x = 566 x + 6 x 88 x + 6 x = 88 Gambarlah garis pembatasan persoalan pemrograman linier : 5 X Gambar.4 garis pembatasan Pembatasan 5 X + x 5 X 5 5 4
X 5 Pembatasan 9X + 6x 566 5 5 5 5 5 Gambar.5 garis pembatasan 5
X 5 Pembatasan X + 6x 88 5 5 Daerah feasible ba 5 5 5 Gambar.6 garis pembatasan dan daerah feasible Setelah daerah feasible diketahui selanjutnya menentukan solusi optimum melalui metode Isoline atau metode titik ekstrim. Solusi optimum dengan Metode Isoline Membuat beberapa garis yang sejajar dengan garis fungsi tujuan (isoline) pada daerah feasible hingga batas terluar dari daerah feasible, seperti ditunjukan pada Gambar 9.7 s.d. gambar 9.8. 6
Solusi optimum dengan Metode Titik Ekstrim Menentukan nilai fungsi tujuan (Z) secara langsung dari titik-titik ekstrim pada daerah feasible kemudian mencari nilai Z yang paling optimum (Z = 5x + x : maksimum) seperti ditunjukkan pada gambar 9. X 5 Z -> 5x + x = 5 5 5 Daerah feasible ba 5 5 5 Gambar.7 garis isoline Z 7
X 5 Z -> 5x + x =55 5 5 Daerah feasible ba 5 5 5 Gambar.8 garis isoline Z 8
X 5 Z -> 5x + x =66 Solusi optimum di (,78) 5 5 Daerah feasible ba 5 5 5 Gambar.9 garis isoline Z dan solusi optimum 9
X (,8) Z = 54 5 (8,) Z 5 = 64 (,78) Z 4 = 66 (optimum) 5 (74,) Z = 69 Daerah feasible 5 ba (,) Z = 5 5 5 Gambar. Titik daerah feasible dan solusi optimum Jadi solusi optimum diperolej x = dan x = 78 dengan nilai Z = 66.. Tentukan solusi dari persoalan pemograman linier berikut. Cari x dan x S.r.s : Z= x + x (maksimum) D.p : x + x 6 x + x 8 -x + x x x, x
solusi : gambarlah semua garis pembatasan pada bidang datar ( sumbu vertical dan horizontal) untuk menentukan daerah feasible. x + x 6 x + x = 6 x + x 8 x + x = 8 -x + x -x + x = x x = 9 Pembatasan Pembatasan 8 x + x 8 -x + x 7 6 5 Pembatasan 4 x 6 4 Pembatasan x + x 6 4 5 6 7 8 Gambar. Garis pembatasan dan daerah feasible
Z =.66 Z = 9 Z = 6 9 8 7 6 5 4 a. Solusi optimum metode isoline (Z = x + x : Maksimum).,. Z =.66 (solusi optimum) 4 5 6 7 8 Gambar. Garis isoline Z dan solusi optimum
b. solusi optimum metode titik ekstrim 9 Gambar. titik ekstrim daerah feasible dan solusi optimum 8 7 6 5 (,) Z 5 = 7 (,) Z 5 = 4 (.,.) Z 4 =.66 (solusi optimum) (4,) Z = 6 4 5 6 7 8 9 (,) Z = (,) Z = Jadi berdasarkan metode isoline ataupun metode titik ekstrim daerah feasible diperoleh solusi optimum yaitu x =. dan x =. dengan nilai Z =.66. 4, Tentukan solusi dari persoalan pemrograman linier berikut. Cari x dan x S.r.s : Z = x + x (maksimum) D.p. : x + x 6 x + 5x 6 x, x
solusi : gambarlah semua garis pembatasan pada bidang datar (sumbu vertical dan horizontal) untuk menentukan daerah feasible. x + x 6 x + x = 6 x + 5x 6 x + 5x = 6 Penentuan daerah feasible : X 6 Pembatasan x + x 6 Daerah feasible Pembatasan x + 5x 6 X 5 Gambar.4 Garis pembatasan dan daerah feasible 4
Menentukan solusi optimum : a. Metode isoline ( Z = x + x : Minimum) X Z = 7 7 6 Daerah Feasible Z = 4 4 (,) Z = 4 optimum X 4 5 6 7 Gambar.5 Garis isoline (Z=x + x : minimum) dan solusi optimum 5
b. Metode titik Ekstrim (,6) Z = 6 6 Daerah feasible 5 4 (,6) Z = 4 (solusi optimum) (5,) Z = 5 4 5 6 Gambar.6 Titik ekstrim daerah feasible dan solusi optimum Jadi solusi optimum diperoleh x = dan x = dengan nilai Z = 4. 6
.6 Metode Substitusi Penyelesaian pemrogramam linier dapat dilakukan dengan metode subtitusi. Penyelesian pemrograman linier dengan metode subtitusi mempunyai beberapa tahapan yaitu : a. Mengubah ketidaksamaan pembatasan menjadi persamaan pembatasan dengan cara menambahkan variabel slack (surplus) untuk persoalan maksimum. Varibel slack (surplus) adalah variabel yang ditambahkan (dikurangkan) di sebelah kiri tanda ketidaksamaan pembatasan, agar ketidaksamaan pembatasan berubah menjadi kesamaan pembatasan. Persoalan pemrograman linier, di mana ketidaksamaan pembatasan sudah berubah menjadi kesamaan kesamaan pembatasan disebut persoalan pemrograman linier standar. b. Tentukan seluruh pemecahan dasar dari persamaan pembatasan dan tentukan pemecahan yang memenuhi semua syarat pembatasan (solusi feasible). c. Tentukan salah satu dari solusi feasible tersebut yang memenuhi syarat fungsi tujuan atau solusi optimum. Model Persoalan Pemrograman Linier Asli Persoalan pemrograman linier asli adalah persoalan pemrograman linier di mana pembatasannya masih dalam bentuk ketidaksamaan ( atau ). Tentukan: x, x,, x n S.r.s : Z = c x + c x + + c nx n (optimum) D.p : a x + a x + + a nx n ( ) b a x + a x + + a nx n ( ) b. a mx + a mx + + a mnx n ( ) b x, x,, x n Persoalan Pemrograman Linier Standar Persoalan pemrograman linier standar adalah persoalan pemrograman linier di mana pembatasannya sudah dalam bentuk kesamaan (=). Tentukan : x, x,, x n, s, s,, s n S.r.s : Z = c x + c x + + c nx n + os + os + + os n (optimum) D.p : a x + a x + + a nx n ± s = b 7
a x + a x + + a nx n ± s = b a mx + a mx + + a mnx n ± s n = b m x, x,, x n, s, s,, s n s variabel tambahan pada persoalan pemrograman linier standar : a. Pada persoalan maksimum, varibel s (slack) selalu ditambahkan ke sisi sebelah kiri pada pembatasan. b. Pada persoalan minimum, variabel s (surplus) selalu dikurangkan ke sisi sebelah kiri pada pembatasan. Contoh :. Tentukan solusi dari persoalan pemrograman linier berikut. Cari x dan x S.r.s : Z = 8x + 6x (maksimum) D.p : 4 x + x 6 x + 4 x 48 X, x Solusi ; Tranformasi persoalan pemrograman linier ke dalam bentuk standar. Cari x, x, s dan s S.r.s : Z = 8x + 6x + o s + o s ( maksimum) D.p : 4 x + x + s = 6 x + 4 x + s = 48 X, x, s, s Mencari solusi feasible. a). x = dan x = o 4x + x + s = 6 s = 6 x + 4x + s = 48 Z = 8x + 6x + s + s = b). x = dan s =, 4x + x + s = 6 x = 6 x = x + 4x + s = 48 4x + s = 48 s = -7 c). x = dan s = 4x + x + s = 6 x + x = 6 s = 6 x + 4x + s = 48 4x = 48 Z = 8x + 6x + s + s = Z = 8 () + 6() + (6) + () = 7 8
d). x = dan s = 4x + x + s = 6 4x = 6 x = 5 x + 4x + s = 48 x + s = 48 s = 8 Z = 8x + 6x + s + s = Z = 8(5) + 6() + () + (8) = e). x = dan s =, 4x + x + s = 6 4x + s = 6 s = -6 x + 4x + s = 48 x = 48 x = 4 Karena s negatif tidak feasible sehingga Z tidak dihitung. f). s = dan s =, 4x + x + s = 6 4x + x = 6 x = x x + 4x + s = 48 x + 4x = 48 x + 4( -x ) = 48 x + 8x = 48-6x = -7 x = x + 4x = 48 () + 4x = 48 x = 6 Z = 8x + 6x + s + s = Z = 8() + 6(6) + () + () = Jadi solusi optimum terjadi pada x = dan x = 6 dengan Z =.. Tentukan solusi dari pemrograman linier berikut. Cari x dan x S.r.s : Z =.5 x + x (maksimum) D.p : x + x 8 x + x 9 x, x solusi : transformasi persoalan pemrograman linier ke dalam bentuk standar. cari x, x, s, dan s S.r.s : Z =.5 x + x + s + s (maksimum) D.p : x + x + s = 8 x + x + s = 9 X, x, s, s Mencari solusi feasible, a). x = dan x =, x + x + s = 8 s = 8 x + x + s = 9 s = 9 Z =.5 x + x + s + s Z =.5() + () + (8) + (9) = 9
b). x = dan s =, x + x + s = 8 x = 8 x = 4 x + x + s = 9 x + s = 9 s = Z =.5 x + x + s + s Z =.5() + (4) + () + () = 8 c). x = dan s =, x + x + s = 8 x + s = 8 x + x + s = 9 x = 9 x = 45 s = - Karena s negatif tidak feasible sehingga Z tidak dihitung. d). x = dan s =, x + x + s = 8 x = 8 x + x + s = 9 x + s = 9 s = 9 (8) = -7 Karena s negatif tidak feasible sehingga Z tidak dihitung. e). x = dan s =, x + x + s = 8 x + s = 8 s = 5 x + x + s = 9 x = 9 x = Z =.5 x + x + s + s Z =.5() + () + (5) + () = 75 f). s = dan s =, x + x + s = 8 x + x = 8 x = 8 x x + x + s = 9 x + x = 9 x + (8 x ) = 9 x + 8 x = 9 x = x = 5 x + x = 9 (5) + x = 9 x = 75 x = 75 Z =.5 x + x + s + s Z =.5(5) + (75) + () + () = 875 Jadi solusi optimum terjadi pada x = 5 dan x = 75 dengan Z = 875. Tentukan solusi dari persoalan pemrograman linier ke dalam bentuk standar. Cari x, x, s, dan s S.r.s : Z = x + x + s + s (minimum) D.p. : x + x s = 6 x + x s = 9 X, x, s, s 4
Mencari solusi feasible. a). x = dan x =, x + x s = 6 s = -6 (tidak feasible) x + x s = 9 s = -9 (tidak feasible) Karena s dan s negatif tidak feasible sehingga Z tidak dihitung. b). x = dan s =, x + x s = 6 x = -6 x = x + x s = 9 x + s = 9 s = 9 (8) = -7 Karena s negatif tidak feasible sehingga Z tidak dihitung. c). x = dan s =, x + x s = 6 x s = 6 s = x 6 s = (9) 6 = x + x s = 9 x = 9 x = 9 Z = x + x + s + s = Z = () + (9) + () + () = d). x = dan s =, x + x s = 6 x = 6 x + x s = 9 x s = 9 s = x 9 = (6) 9 = Z = x + x + s + s = Z = (6) + () + () + () = e). x = dan s =, x + x s = 6 x s = 6 s = x 6 = 9/ 6 = -/ x + x s = 9 x = 9 x = 9/ Karena s negatif tidak feasible sehingga Z tidak dihitung. f). s = dan s =, x + x s = 6 x + x = 6 x = 6 x x + x s = 9 x + x = 9 (6 x ) + x = 9 4x + x = 9 -x = - x = x + x = 9 x + () = 9 x = 8 x = 4 Z = x + x + s + s = Z = (4) + () + () + () = Jadi solusi optimum terjadi pada x = 4 dan x = dengan Z = 4
Soal untuk Latihan. sebuah toko computer berancana untuk menjual dua model computer yaitu A dan B dengan harga masing-masing sebesar Rp. juta dan Rp. 4 juta. Komputer model A menghasilkan keuntungan sebesar Rp. 5 ribu dan computer model B menghasilkan keuntungan sebesar Rp. 5 ribu. Toko tersebut memperkirakan bahwa permintaan total bulanan tidak akan melebihi 5 unit. Cari jumlah unit masing-masing model computer tersebut yang harus di sediakan took untuk memaksimalkan keuntungan. Toko computer tersebut hanya berinvestasi dalam penyediaan computer maksimum Rp. 8 juta per bulan.. tentukan solusi persoalan pemrograman linier minimum berikut ini. Cari : x dan x S.r.s : Z = x + x : maksimum D.p : x + x 6 X + x 8 X + 4x 48 X ; x 4
BAB III SIMPLEX. Metode Simplex Metode simplex adalah salah satu teknik penyelesaian pemrograman linier secara iterasi. Metode simplex mencari suatu penyelesaian dasar yang feasible ke penyelesaian dasar feasible yang lainnya dilakukan secara berulang-ulang sehingga akhirnya tercapai suatu penyelesaian optimum. Setiap tahap penyelesaian menghasilkan nilai fungsi tujuan yang selalu lebih optimum atau sama dari tahap-tahap penyelesaian sebelumnya. Metode simplex sangat efisien dan sistematik yang dilengkapi tes kriteria yang dapat memberitahukan kapan perhitungan harus dilanjutkan atau dihentikan sampai diperoleh solusi optimum. Pada metode simplex persoalan pemrograman linier selalu diubah menjadi persoalan pemrograman linier standar, dimana setiap ketidaksamaan pembatasan diekspresikan dalam bentuk persamaan pembatasan dengan menambahkan variabel slack atau surplus... Transfromasi Persoalan Pemrograman Standar Transfromasi persoalan pemrograman linier asli menjadi persoalan pemrograman linier standar adalah mengubah bentuk ketidaksamaan pembatasan menjadi bentuk persamaan pembatasan dengan menambahkan variabel slack atau surplus. A. Persoalan Pemrograman Linier Maksimum. Persoalan Pemrograman Linier Asli Variabel keputusan : x, x,, xj + + xn Fungsi tujuan : Z = cx + cx + + cjxj + + cnxn Z = CX Pembatasan : ax + ax + + aj xj + + an xn h ax + ax + + ajxj + + anxn h.. aix + aix + + aijxj + + ainxn hi 4
atau, AX H amx + amx + + amjxj + + amnxn hm. Persoalan Pemrograman Linier Standar Variabel Keputusan : x,x + + xj + + xn + s,s + + sj + + sn Fungsi tujuan : Z = cx + cx + + cjxj + + cnxn + s + s + + sj + + sm Z = CX Pembatasan : ax + ax + + ajxj + + anxn + s = h ax + ax + + ajxj + + anxn + s = h... aix + aix + + aijxj + + ainxn + si = hi amx + amx + + amjxj + + amnxn + sm = hm atau AX = H B. Persoalan Pemrograman Linier Minimum. Persoalan Pemrograman Linier Asal Varibel keputusan : x, x +, xj + + xn Fungsi tujuan : Z = cx + cx + + cjxj + + cnxn Z = CX Pembatasan : ax + ax + + aj xj + + an xn h atau, ax + ax + + ajxj + + anxn h.. aix + aix + + aijxj + + ainxn hi amx + amx + + amjxj + + amnxn h AX H 44
. Persoalan Pemrograman Linier Standar Variabel keputusan : x,x + + xj + + xn + s,s + + sj + + sn fungsi tujuan : cx + cx + + cjxj + + cnxn + s + s + + sj + + sm Z = CX Pembatasan : ax + ax + + ajxj + + anxn - s = h ax + ax + + ajxj + + anxn - s = h... aix + aix + + aijxj + + ainxn - si = hi amx + amx + + amjxj + + amnxn - sm = hm atau, AX = H Pada persoalan maksimum atau minimum standar: a. Jika pembatasannya maka variabel s (slack) diberi tanda positif b. Jika pembatasannya maka variabel s (surplus) diberi tanda negative.. Bentuk Matriks Pembatasan Pembatasan persoalan pemrograman linier standar dapat dinyatakan dalam bentuk persamaan matriks seperti berikut. AX = H Atau, a a a a a i [ a m a a m a j a n a j a n a ij a mj a in a mn] [ x x x i x n ] = h h h i [ h m ] (mn)(n) = (m) 45
jika, a a a j a a a j A = a, A = i a,,, A j = a ij [ a m ] [ a m ] [ a mj] a n a n, A = a in [ a mn ] Maka, x h x h [A A A j A n ] x = i h i [ x n ] [ h m ] (A x + A x + A j x i + A n x n ) = H n Atau, j= A j x i = H Dimana : m = banyaknya pembatasan n = banyaknya variabel keputusan Jika dari matriks A (koefisien pembatasan) diambil m kolom dan katakanlah matriks B (B, B,, Bm), maka akan diperoleh persamaan Bx = H yang juga memenuhi persamaan pembatasan itu. Vektor pada matriks B yaitu B, B,, Bm disebut vector basis. 46
Jika kita mempunyai solusi feasible dasar dengan B sebagai basis, maka AX = H dapat ditulis sebagai, BxB + NxN = H Jika pada persamaan tersebut ke dua sisinya dikalikan dengan B -, maka diperoleh : BB - xb + B - NxN = B - H xb + B - NxN = B - H dimana, h = B - H xb = B - H - B - NxN xb = B - H B - R j (A j ) xb = h B - R (A j ) di mana Aj adalah kolom matriks pembatasan untuk variabel keputusan xj dan R jumlah variabel nonbasis... Bentuk Matriks Fungsi Tujuan Fungsi tujuan persoalan pemrograman linier standar dapat dinyatakan dalam bentuk persamaan matriks berikut. Z = CX Jika kita mempunyai solusi feasible dasar dengan B sebagai basis, maka Z = CX dapat ditulis sebagai, Z = CX = cbxb + cnxn = cb (B - H B - R R j A j xj ) + j c j x j = cb B - H B - R R cb j A j xj + j c j x j R = z - j (z j c j ) xj Atau, Z = z + Q(zj cj) Dimana, j R Q = - j x j Z = cb B - H Zj = cbb - A Nilai zj cj disebut nilai pengurangan variabel xj akibat vector B sebagai basis. xj xj 47
Pada metode simplex setiap pemecahan persamaan dasar feasible, memberikan nilai fungsi tujuan (z) yang berbeda dan nilainya selalu bertambah (pada persoalan maksimum) atau selalu berkurang (pada persoalan minimum) dari nilai z sebelumnya. Nilai fungsi tujuan (Zj) untuk pemecahan persamaan dasar yang feasible pada tahap awal sebagai berikut, R Z = CX Z = j x B c B Nilai fungsi tujuan (Zj) untuk pemecahan persamaan dasar yang feasible pada tahap berikutnya sebagai berikut, Z = Z + Q(zj cj) Q = - x j Karena Q o, ada dua kemungkinan yang terjadi yaitu : a. Untuk nilai zj cj < o, maka Z Z, terdapat pada persoalan pemrograman linier maksimum. b. Untuk nilai zj cj > o, maka Z Z, terdapat pada persoalan pemrograman linier minimum...4 Prosedur Metode Simplex Prosedur penyelesaian persoalan pemrograman linier maksimum maupun minimum dapat dilakukan melalui beberapa tahapan berikut. A. Persoalan Pemrograman Linier Maksimum. Selidiki semua nilai zj cj a. Jika semua nilai zj cj, maka pemecahan dasar feasible yang bersangkutan sudah memberikan pemecahan yang optimum. Hal ini berari pemecahan dasar sudah selesai. b. Jika salah satu atau lebih zj cj < o, dan semua aik o, maka pemecahan dasar tidak ada batasnya (unbounded solution). c. Jika salah satu atau lebih zj cj < o, dan semua aik o, maka pemecahan dasar belum selesai dan perlu dilanjutkan. Tentukan salah satu vector A yang akan dimasukan ke dalam basis B yang memenuhi syarat berikut, h r (zk ck) = min ( h r (z a rk a j c j )), untuk zj cj < rk R j 48
Atau, Zk ck = min (zj cj), untuk zj cj <. Jika hasilnya kategori c, tentukan salah satu vector yang akan dikeluarkan dari basis B dengan menggunakan syarat berikut, h r = min ( h i, a a rk h ik >, i m) ik Kolom ke r dari basis B dikeluarkan diganti dengan Ak.. Tentuka nilai-nilai baru dari fungsi tujuan (Z) dan semua pembatasan. a) hi = hi hr a ij a rj, untuk i r dan hi h r a rj, untuk i = r b) aij = aij arj a ik a rj, untuk i r dan aij a rj a rk, untuk i = r c) Z = Z - b r a rj (zj cj) d) (zj cj) = (zj cj) - a rj a rk (zk ck) 4. Lakukan lagi tahap hingga, demikian seterusnya, sehingga diperolah suatu pemecahan dasar feasible dengan nilai fungsi tujuan yang optimum. B. Persoalan Pemrograman Linier Minimum. Selidiki semua nilai zj cj a. Jika semua nilai zj cj, maka pemecahan dasar feasible yang bersangkutan sudah memberikan pemecahan yang optimum. Hal ini berarti pemecahan dasar sudah selesai. b. Jika salah satu atau lebih zj cj >, dan semua aik, maka pemecahan dasar tidak ada batasnya (unbounded solution). c. Jika salah satu atau lebih zj cj >, dan semua aik, maka salah satu vektor A yang akan dimasukan ke dalam basis B yang memenuhi syarat berikut, h r a rk (zk ck) = maks ( h r a rk (zk ck), untuk zj cj > Atau zk - ck = maks(zj cj), untuk zj cj > 49
. Jika hasilnya kategori c, tentukan salah satu vektor yang akan dikeluarkan dari basis B dengan menggunakan syarat berikut, h r = min ( h i, a a rk a ik >, i m) ik kolom ke r dari basis B dikeluarkan diganti dengan Ak.. Tentukan nilai-nilai baru dari fungsi tujuan dan semua pembatasan. a) hi = hi hr a ij a rj, untuk i r dan hi h r a rj, untuk i = r b) aij = aij arj a ik a rj, untuk i r dan aij a rj a rk, untuk i = r c) Z = Z - b r a rj (zj cj) d) (zj cj) = (zj cj) - a rj a rk (zk ck) 4. Lakukan lagi tahap hingga, demikian seterusnya, sehingga diperoleh suatu pemecahan dasar feasible dengan nilai fungsi tujuan yang optimum.. Tabel Metode Simplex Setiap literasi pemecahan persamaan dasar feasible dengan metode Simplex biasanya menggunakan tabel simplex seperti berikut. Pada tabel tersebut terdapat sejumlah m + baris (m = jumlah pembatasan) dan sejumlah n+m kolom. Dimana pada baris terakhir pada tabel tersebut merupakan fungsi tujuan dan pada kolom terakhir adalah sisi kanan dari pembatasan (h). 5
Variabel keputusan (Basis) Variabel slack/surplus (NonBasis) Solusi Optimum Basis x x xn s s sm H b b s s s m a a am a a am an an amn Z z c z c zn cn h h hm B m b m+ y y n+ y y n y n+ y n+m y n+m+ Koefisien matriks pembatasan(a) Koefisien matriks slack/surplus Vektor dalam Basis.. Cara Menggunakan Tabel Metode Simplex Tabel simplex dapat dipergunakan untuk menyelesaikan persoalan pemrograman linier maksimum maupun minimum. A. Persoalan Pemrograman Linier Maksimum. Selidiki baris terakhir pada tabel simplex, jika zj cj (tidak ada nilai negatif) pemecahan dasar sudah mencapai optimal. Proses pemecahan dasar sudah selesai. 5
. Jika masih ada zj cj < ( masih ada nilai negatif), pilih kolom yang mempunyai zj cj terkecil. Katakanlah kolom ke k, maka Ak dimasukan ke dalam basis. Sebagai akibatnya ada vector yang dikeluarkan dari dalam basis dan dipilih berdasarkan : h r = min ( h i, a a rk a ik >, i m) ik Kolom ke r dari basis B dikeluarkan diganti dengan Ak.. Selanjutnya buat tabel simplex baru dan tentukan nilai-nilai baru dari fungsi tujuan dan semua pembatasannya. 4. Lakukan lagi tahap hingga, sehingga diperoleh suatu pemecahan dasar dengan nilai fungsi tujuan yang optimum. B. Persoalan Pemrograman Linier Minimum. Selidiki baris terakhir pada tabel simplex, jika zj cj (tidak ada nilai posotif) pemecahan dasar sudah mencapai optimal. Proses pemeecahan dasar sudah selesai.. Jika masih ada zj cj > ( masih ada nilai positif), pilih kolom yang mempunyai zj cj terbesar. Katakanlah kolom ke k, maka Ak dimasukan ke dalam basis. Sebagai akibatnya ada vector yang dikeluarkan dari dalam basis dan dipilih berdasarkan : h r = min ( h i, a a rk a ik >, i m) ik Kolom ke r dari basis B dikeluarkan diganti dengan Ak.. Selanjutnya buat tabel simplex baru dan tentukan nilai-nilai baru dari fungsi tujuan dan semua pembatasannya. 4. Lakukan lagi tahap hingga, sehingga diperoleh suatu pemecahan dasar dengan nilai fungsi tujuan yang optimum.. Teknik Perhitungan Nilai Tabel Simplex Ada dua teknik perhitungan nilai baru pada setiap Tabel Simplex yaitu berbasis vektor baris (metode Ring Around the Rossy ) dan berbasis vektor kolom (Metode Transformasi). 5
.. Perhitungan Nilai Pada Tabel Simplex Menggunakan Basis Vektor Baris (Metode Ring Around Rossy ) Nilai-nilai baru dihitung untuk setiap baris (b) pada Tabel Simplex dan dihitung dengan rumus berikut. untuk i r a ij = a ij a rj a ik a rk, a ij = a rj, untuk i = r a rk Dimana, i = indeks baris r = indeks kolom Elemen ark disebut elemen vipot yang terletak pada perpotongan baris r dan kolom k pada Tabel Simplex. Di mana k adalah kolom yang vektornya harus masuk ke dalam basis B dan r adalah baris yang vektornya harus ke luar dari dalam basis B yang diganti oleh vector Ak. Contoh :. Tentukan solusi dari persoalan pemrograman linier berikut. Cari : x dan x S.r.s : Z = x + x (maksimum) D.p. : x + x 5 x + x x,x Solusi : Persoalan pemrograman linier standar dari persoalan maksimum tersebut, Cari : x, x, s dan s S.r.s : Z = x + x + s + s : maksimum D.p : x + x + s = 5 X + x + s = X; x; s; s 5
Tabel.. Nilai Baru Tabel Simplex Keluar basis B x x s s H sj s Z - - 5 h a = = paling minimum, masuk basis h a = 5 =.5(min) Nilai baru pada Tabel Simplex point. menggunakan elemen vipot = a= : Baris. b = b = [ 5] = [.5.5.5] a Baris. b = b - a a (b ) = b (b) = [ ] [ 5] = [.5.5.5 ] Baris. B = b - a a (b ) = b (b) = [ ] + [ 5] = [.5.5 7.5 ] Keluar basis Tabel.. Nilai Baru Tabel Simplex B x x s s H x s.5.5.5 -.5.5.5 Z -.5.5 7.5 h a = 5 = 5 h a =.5.5 = (min) 54
minimum, masuk basis Nilai baru pada Tabel Simplex point. menggunakan elemen vipot = a=.5 : Baris.. b = b - a a (b ) = b.5.5 (b) = [.5.5.5] [.5.5.5] = [ ] Baris. b = b = [.5.5.5] = [ ] a.5 Baris. b = b - a a (b ) = b.5.5 (b) = -.5.5 7.5 +.5 -.5.5 = 8 B x x s s H x s - - Z 8 Solusi optimum Tabel. Nilai baru tabel simplex Pada Tabel Simplex point. semua nilai zj cj, pemecahan persamaan dasar sudah memberikan solusi optimum. Jadi solusi optimum diperoleh Z= 8 dengann x= dan x=.. Tentukan solusi dari persoalan pemrograman linier berikut. Cari : x dan x S.r.s : Z = 8x + 9x : maksimum 55
D.p : x + x 5 x + 6x 8 x + x 7, X ; x Solusi : Persoalan pemrograman linier standar dari persoalan maksimum tersebut. Cari : x, x, s, s, dan s S.r.s : Z = 8x + 9x + s + s + s : maksimum D.p : x + x + s = 5 x + 6x + s = 8 x + x + s = 7; x; x; s; s; s Keluar basis B x x s s s H s s s Tabel.4. Nilai baru Tabel Simplex h 6 5 8 7 Z -8-9 = 5 a h = 8 (min) a 6 h = 7 a Masuk basis Nilai-nilai baru pada Tabel Simplex menggunakan elemen vipot = a = 6; Baris. b = b a a (b ) = [ 5] [ 6 8] 6 = [ ] 56
Baris. b = b = [ 6 8] a 6 = [ 6 4 ] Baris. b = b a (b a ) = [ 7] [ 6 8] 6 = [ ] Baris 4. b 4 = b 4 a 4 (b a ) = [ 8 9 ] 9 [ 6 8] = [ 5 ] 6 Keluar basis B x x s s s H s x s / -/ /6 -/ 4/ Z -5 / h = (min) a h = 4/ a / h = a Masuk basis Tabel.5. Nilai baru Tabel Simplex Nilai-nilai baru pada Tabel Simplex menggunakan elemen vipot = a = ; Baris. b = b = [ / ] a = [ ] Baris. b = b a a (b ) = [ 6 4 = [ ] ] [ ] Baris. b = b a a (b ) 57
Keluar basis = [ ] [ ] = [ ] Baris 4. b 4 = b 4 a 4 a (b ) = [ 5 ] 5 [ ] = [ 5 7] B x x s s s H x x s -/ - -/ / / Z 5-7 Nilai-nilai baru pada Tabel Simplex menggunakan elemen vipot = a4 = /; Baris. b = b a 4 a 4 (b ) = [ ] / [ ] / = [ ] Baris. b = b a 4 a 4 (b ) Masuk basis h = a 4 h = a 4 / Tabel.6. Nilai baru Tabel Simplex = [ / ] / [ ] / = [ / /] (non) h = (min) a 4 / Baris. b = b = [ / ] a / = [ 4 ] Baris 4. b 4 = b 4 a 44 (b a ) 4 58
= [ 5 7] [ ] / B x x s s s H x x s Z 9 [ 9] - -4 -/ / = Tabel.7. Nilai baru Tabel Simplex 4 Pada Tabel simplex.7 semua nilai zj cj, pemecahan persamaan dasar sudah memberikan solusi optimum. Jadi solusi optimum. Jadi solusi optimum diperoleh Z =9 dengan x = dan x = /.. Tentukan solusi dari persoalan pemrograman linier berikut. Cari x, x, dan x S.r.s : Z= x + x 4x : minimum D.p : x + x + x + s 9 x + x - x - x + x + x 4 X; x; x Solusi : Cari : x, x, x, s, s, dan s S.r.s : Z= x + x 4x + s + s + s : minimum D.p. : x + x + x + s = 9 x + x - x + s = 59
- x + x + x + s = 4 x; x; x; s; s; s Keluar basis B x x x s s s H s s s Tabel.8. Nilai Baru Tabel Simplex - - Z - - 4 9 4 h a = 9 h a = (non) h a = 4 (min) Masuk basis Nilai-nilai baru pada Tabel Simplex menggunakan elemen vipot = a = : Baris. b = b - a a (b ) = 9 - - 4 = - - Baris. b = b - a a (b ) = - - - 4 = 6 Baris. b = b a = - 4 6
= - 4 Baris 4. b4 = b4 - a 4 a (b) = - - 4-4 - 4 = -5-4 -6 Keluar basis B x x x s s s H s s s - - Tabel.9. Nilai Baru Tabel Simplex Z -5-4 -6-6 4 h a = (min) h a = 6 h a = 4 (non) Masuk basis Nilai-nilai baru pada tabel simplex menggunakan elemen vipot = a = : Baris. b = b = [ ] a = [ Baris. b = b a a (b) ] = [ 6] [ ] = [ 6] Baris. b = b a a (b) = [ 4] [ ] 6
= [ ] Baris 4. b4 = b4 a 4 a (b) = [ 5 4 6] [ ] = [ 4 7] B x x x s s s H s s s Tabel.. Nilai Baru Tabel Simplex -/ / / / -/ / / 6 / Z -4 - - -7 Pada tabel Simplex. semua nilai zj cj, pemecahan persamaan dasar sudah memberikan solusi optimum. Jadi solusi optimum diperoleh Z= -7 dengan x= /, x=, dan x = /... Perhitungan Nilai Pada Tabel Simplex Menggunakan Basis Vektor Kolom (Metode Transformasi) Nilai-nilai baru diperoleh untuk setiap kolom (k) pada Tabel Simplex dan dihitung dengan rumus berikut. aij = aij + arjt dimana, i = indeks baris j = indeks kolom 6
a ik /a rk a ij a a (r )k /a rk ij aij = [ ] dan T = a rk a a (r+k)k /a rk mj [ a mk /a rk ] Elemen ark disebut elemen vipot yang terletak pada perpotongan basis r dan kolom k pada tabel simplex. Dimana k adalah kolom yang vektornya harus masuk kedalam basis B dan r adalah baris yang vektornya harus ke luar dari dalam basis B yang diganti oleh vector Ak. Contoh :. Tentuka solusi dari persoalan pemrograman linier berikut. Cari : x, x, x, s, s, dan s S.r.s : Z= x + x 4x + s + s + s : minimum D.p. : x + x + x + s = 9 x + x - x + s = - x + x + x + s = 4 solusi : x; x; x; s; s; s Persoalam pemrograman linier standar dari persoalan tersebut, Cari : x, x, s dan s S.r.s : Z = x + x + s + s : maksimum D.p. : x + x + s = 5 x + x + s = x; x; s; s 6
Keluar basis Tabel.. Nilai Baru Simplex B x x s s H s 5 s Z - - h a = 5 =,5(min); h a = = Paling minimum, masuk basis Nilai-nilai baru pada tabel simplex menggunakan elemen vipot = a = : /a T = [ a /a ] = [ ] = [ ] a /a ( ) Kolom. y = y + at = [ ] + [ ] = [ ] Kolom. y = y + a T = [ ] + [ ] = [ ] Kolom. y = y + a T = [ ] + [ ] = [ ] Kolom 4. y 4 = y 4 + a 4 T = [ ] + [ ] = [ ] 5 5 Kolom 5. y 5 = y 5 + a 5 T = [ ] + 5 [ ] = [ ] 5 64