Program Linier [PDF]

Citation preview

DAFTAR ISI



DAFTAR ISI ............................................................................................................................ i BAB I ....................................................................................................................................... 1 BAB II .................................................................................................................................... 10 BAB III ... ............................................................................................................................... 20 BAB IV .................................................................................................................................. 60 BAB V .................................................................................................................................... 64 BAB VI .................................................................................................................................. 96



0



i



BAB I PROGRAM LINIER 1. Pengertian Program Linier Dalam kegiatan produksi dan perdagangan, baik pada industri skala besar maupun kecil tidak terlepas dari masalah laba yang harus diperoleh oleh perusahaan tersebut. Tujuan utamanya



adalah



untuk



memperoleh



pendapatan



yang



sebesar-besarnya



dengan



meminimumkan pengeluarannya (biaya bahan baku, biaya proses produksi, gaji karyawan, transportasi, dan lain-lain). Untuk maksud tersebut biasanya pihak manajemen perusahaan membuat beberapa kemungkinan dalam menentukan strategi yang harus ditempuh untuk mencapainya. Misalnya, dalam memproduksi dua macam barang dengan biaya dan keuntungan berbeda. Pihak perusahaan dapat menghitung keuntungan yang mungkin dapat diperoleh sebesar-besarnya dengan memperhatikan bahan yang diperlukan, keuntungan per unit, biaya transportasi, dan sebagainya. Untuk menyelesaikan masalah tersebut digunakan program linier. Program linier diartikan sebagai cara untuk menyelesaikan suatu persoalan nilai optimum (solusi optimum) dengan menggunakan metode matematik yang dirumuskan dalam bentuk persamaan-persamaan atau pertidaksamaan-pertidaksamaan linier. Program linier juga diartikan sebagai metode optimasi untuk menemukan nilai optimum dari fungsi tujuan pada kondisi pembatasan- pembatasan (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 program 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 program linier misalnya untuk keperluan: a. Realokasi sumber daya b. Produksi campuran c. Penjadualan d. Keputusan investasi



1



e. Perencanaan produksi f. Masalah transportasi, logistik dll Untuk mendapatkan solusi optimum tersebut digunakan metode grafik yang diterapkan pada program linier sederhana yang terdiri atas dua variabel dengan cara uji titik pojok atau garis selidik pada daerah himpunan solusi. Elemen program linier Ada tiga elemen penting dalam program linier yaitu: a. Variabel keputusan (decision variables):



→



adalah variabel yang nilai-



nilainya dipilih untuk dibuat keputusan. b. Fungsi tujuan (objective function):



s 1 =60−24



adalah fungsi yang akan



dioptimasi (dimaksimumkan atau diminimumkan). c. Pembatasan (constraint):



→



adalah pembatasan-pembatasan yang



harus dipenuhi. Asumsi program linier Penggunaan program linier untuk mendekati dan merepresentasikan situasi kehidupan nyata menggunakan beberapa asumsi yaitu: a. Proporsionalitas. Kontribusi masing-masing variabel keputusan terhadap fungsi tujuan dan pembatasan-pembatasan adalah proporsional langsung terhadap nilai variabel keputusan b. Aditivitas. Kontribusi terhadap fungsi tujuan dan pembatasan-pembatasan untuk beberapa variabel adalah independen dari variabel keputusan yang lain sehingga kontribusi masing-masing variabel keputusan dapat digabungkan / ditambahkan menjadi kontribusi total. c. Divisibilitas. Variabel keputusan adalah kontinu sehingga dapat diambil nilai fraksionalnya. d. Deterministik. Semua parameter (fungsi tujuan, pembatasan-pembatasan, seluruh koefisien) diketahui dengan pasti dan tetap tidak berubah selama dilakukan kajian atau analisis. Persoalan program linier Persoalan program linier adalah persoalan optimasi yang memenuhi ketentuan berikut: a. Fungsi tujuan merupakan fungsi linier dari variabel keputusan. b. Nilaivariabel keputusan harus memenuhi pembatasan-pembatasan. Setiap pembatasan harus berbentuk persamaan atau ketidaksamaan linier. 2



c. Setiap variabel keputusan harus dibatasi yaitu non negatif. Tahapan Memformulasikan Persoalan program linier Ada beberapa tahapan dalam memformulasikan persoalan program linier yaitu: a. Memahami permasalahan secara keseluruhan apakah persoalan tersebut



adalah



persoalan maksimum atau minimum. b. Mengidentifikasi variabel keputusan. c. Mendeskripsikan fungsi tujuan sebagai kombinasi linier dari variabel keputusan. d. Mendeskripsikan pembatasan-pembatasan sebagai kombinasi linier dari variabel keputusan. e. Mengidentifikasi batas bawah dan batas atas variabel keputusan. f. Mengekspresikan semua hasil identifikasi tersebut dalam formula metematika. Langkah-langkah yang ditempuh untuk mendapatkan nilai optimum adalah sebagai berikut. a. Ubahlah persoalan verbal ke dalam model matematika (dalam bentuk sistem pertidaksamaan). b. Tentukan Himpunan Solusi (daerah feasible). c. Tentukan semua titik-titik pojok pada daerah feasible tersebut d. Hitung nilai bentuk objektif untuk setiap titik pojok dalam daerah feasible. Dari hasil pada langkah d, nilai maksimum atau minimum dapat ditetapkan. Contoh: 1. Formulasikan persoalan program linier berikut. Suatu perusahaan makanan akan memproduksi dua jenis makanan akan memproduksi dua jenis makanan yaitu brownie kukus dan es krim coklat. Satu satuan brownie kukus diperlukan bahan 4 ons coklat dan 2 ons gula. Sedangkan satu satuan es krim coklat diperlukan diperlukan bahan 2 ons coklat dan 2 ons gula. Perusahaan tersebut mempunyai mempunyai dua buah bahan mentah yaitu coklat murni dan gula yaitu masing-masing 60 kg dan 48 kg. Harga satuan brownie kukus Rp 40.000 dan harga satuan es krim coklat Rp 20.000. Berapa banyak brownie kukus dan es krim coklat yang harus diproduksi supaya diperoleh hasil penjualan yang maksimum dengan memanfaatkan semua bahan mentah tersebut. Jawab: Persoalan tersebut adalah persoalan memaksimumkan dengan variabel keputusan brownie kukus dan es krim coklat. Misalkan



s1=36 : banyaknya brownie kukus



3



Z=8x1+6x2+0s1+0s2 : banyaknya es krim coklat Model matematikanya adalah: Maks



40.000 x1  20.000 x2 4 x1  2 x2  600



Kendala



2 x1  2 x2  480



s 1 =0 2. Formulasikan persoalan program linier berikut: Suatu perusahaan garmen akan memproduksi dua jenis pakaian yaitu baju dan celana. Proses produksi meliputi memotong, menjahit dan pengepakkan. Perusahaan tsb mempekerjakan 25 orang pada bagian memotong, 40 orang pada bagian menjahit dan 5 orang pada bagian pengepakkan. Semua tenaga kerja tsb bekerja 8 jam per hari selama 5 hari kerja seminggu. Tabel berikut menunjukkan waktu yang diperlukan dan keuntungan per satuan untuk pakaian tsb. pakaian Baju Celana



memotong menjahit 1 2 2 2



pengepakan profit 0.2 80 0.1 120



Jawab: Persoalan tersebut adalah persoalan memaksimumkan dengan variabel keputusan baju dan celana. Misalkan



4x1+2x2+s1=60 : baju



→



: celana



Model matematikanya adalah: Maks Kendala



4 x 1 =60



→ x 1=15 2 x 1 +4 x 2 +s2 =48



→ 3. Formulasikan persoalan program linier berikut:



4



Suatu perusahaan mobil akan memasang iklan di media cetak dan TV. Perusahaan tsb memilih cara beriklan yg paling efektif shg biayanya minimum dan sasaran iklan mencapai lebih dari 40 juta orang yg diantaranya 25 jt org berpendapatan lebih dari Rp 5 jt/ bulan. Biaya memasang iklan di media cetak sebesar RP 2M dan di TV Rp 8M. Pembaca media cetak sebanyak 4 jt org dan penonton TV sebanyak 10 jt org. Diantara pembaca media cetak terdapat 2 jt org berpendapatan lebih dari Rp 5 juta/ bln dan di antara penonton TV terdapat 1 juta org berpendapatan lebih dari Rp 5 jt/ bulan. Jawab: Persoalan tersebut adalah persoalan meminimumkan dengan variabel keputusan media cetak dan televisi. Misalkan



2x1+s2=48 : media cetak



→



: televisi



Model matematikanya adalah: Min



s 2 =48−30



→



Kendala



s 2 =18 Z=8x1+6x2 +0s1+0s2 4. Formulasikan persoalan program linier berikut: Seorang peternak memiliki 200 kambing yang mengkonsumsi 90 kg pakan khusus setiap harinya. Pakan tersebut disiapkan menggunakan campuran jagung dan bungkil kedelai dengan komposisi sbb. Bahan Jagung Bungkil kedelai



Kg per kg bahan Kalsium Protein 0.001 0.09



Serat 0.02



0.002



0.006 5500



0,6



Biaya(Rp/Kg) 2000



Kebutuhan pakan kambing setiap harinya adalah paling banyak 1% kalsium, paling sedikit 30% protein dan paling banyak 5% serat. Jawab: Persoalan tersebut adalah persoalan meminimumkan dengan variabel keputusan jagung dan bungkil kedelai. Misalkan



Z=8(15)+6(0)+ (0)+ (18)



: jagung 5



Z=120



: bungkil kedelai



Model matematikanya adalah:



x 2= 0



Min



s 2 =0



Kendala



2 x 1 +4 x 2 +s2 =48



→ 2 x 1 =48



→ 5. Formulasikan persoalan program linier berikut: Suatu pabrik perakitan radio menghasilkan dua tipe radio yaitu HiFi-1 dan Hifi-2 pada fasilitas perakitan yang sama. Lini perakitan terdiri dari 3 stasiun kerja. Waktu perakitan masing-masing tipe pada masing-masing stasiun kerja adalah sebagai berikut: Waktu perakitan per unit (menit) HiFi-1 HiFi-2 6 4 5 5 4 6



Stasiun kerja 1 2 3



Waktu kerja masing-masing stasiun kerja adalah 8 jam per hari. Masing-masing stasiun kerja membutuhkan perawatan harian selama 10%, 14% dan 12% dari total waktu kerja (8 jam) secara berturut-turut untuk stasiun kerja 1,2 dan 3. Jawab: Persoalan tersebut adalah persoalan memaksimalkan dengan variabel keputusan HiFi-1 dan HiFi-2. Misalkan



x1=24 : HiFi-1 4x1+2x2+s1=60 : HiFi-2



Waktu produktif masing-masing stasiun kerja adalah 



Stasiun 1: 480 menit-10%.480 menit = 480 menit– 48 menit = 432 menit







Stasiun 1: 480 menit-14%.480 menit = 480 menit– 67.2 menit = 412.8 menit







Stasiun 1: 480 menit-12%.480 menit = 480 menit– 57.6 menit = 422.4 menit.



Model matematikanya adalah: Min



→ 6



Kendala



4 x 1 + s 1=60



→ s 1 =60− 96



→ 6. Formulasikan persoalan program linier berikut: Empat produk diproses secara berurutanpada 2 mesin. Waktu pemrosesan dalam jam per unit produk pada kedua mesin ditunjukkan tabel di bawah ini: Waktu per unit (jam) Produk 1 Produk 2 2 3 3 2



Mesin 1 2



Produk 3 4 1



Produk 4 2 2



Biaya total untuk memproduksi setiap unit produk didasarkan secara langsung pada jam mesin. Asumsikan biaya operasional per jam mesin 1 dan 2 secara berturut-turut adalah $10 dan $5. Waktu yang disediakan untuk memproduksi keempat produk pada mesin 1 adalah 500 jam dan mesin 2 adalah 380 jam. Harga jual per unit keempat produk secara berturut-turut adalah $65, $70, $55 dan $45. Jawab: Persoalan tersebut adalah persoalan memaksimalkan dengan variabel keputusan jumlah produk 1, 2, 3 dan 4 yang dihasilkan.. Misalkan



s1=−36 : jumlah produk 1 yang dihasilkan s 1 : jumlah produk 2 yang dihasilkan s1=0 : jumlah produk 3 yang dihasilkan s2=0 : jumlah produk 4 yang dihasilkan



Keuntungan yang diperoleh dengan mengurangkan biaya dari pendapatan. 



Keuntungan per unit dari produk 1 =



4 x 1 + 2 x 2 + s1 =60







Keuntungan per unit dari produk 2 =



→







Keuntungan per unit dari produk 3 =



4 x 1 + 2 x 2 =60







Keuntungan per unit dari produk 4 =



→



Model matematikanya adalah: Maks



x 2=30 −2 x1



7



2 x 1 + 4 x 2 + s2 = 48



Kendala



→ 2 x 1 +4 x 2 =48 7. Formulasikan persoalan program linier berikut: Dua produk diproduksi menggunakan tiga mesin. Waktu masing-masing mesin yang digunakan untuk memproduksi kedua produk dibatasi hanya 10 jam per hari. Waktu produksi dan keuntungan per unit masing-masing produk ditunjukkan tabel di bawah ini: Produk 1 2



Waktu produksi (menit) Mesin 1 Mesin 2 10 6 5 20



Mesin 3 8 15



Keuntungan ($) 2 3



Jawab: Persoalan tersebut adalah persoalan memaksimumkan dengan variabel keputusan produk 1 dan produk 2. Misalkan



→



: produk 1



2x1+4(30−2x1)=48 : produk 2 Model matematikanya adalah: Maks Kendala



→ 2x 1+120−8 x 1=48



→ −6 x 1=−72



→ SOAL-SOAL LATIHAN 1. Sebuah pabrik obat ingin memproduksi suplemen dalam bentuk sirup dan tablet. Suplemen dalam bentuk sirup memberikan harga jual Rp. 27.000/buah dengan biaya bahan baku Rp. 14.000 dan biaya lain-lain Rp. 10.000. Suplemen dalam bentuk tablet memberikan harga jual Rp. 21.000/kaplet dengan biaya bahan baku Rp. 10.000 dan biaya lain-lain Rp. 9000. Pembuatan dilakukan dalam dua tahap yaitu pemrosesan dan pengemasan. Suplemen sirup memerlukan waktu 2 jam pemrosesan dan 1 jam



8



pengemasan. Suplemen sirup memerlukan waktu 1 jam pemrosesan dan 1 jam pengemasan. Ada keterbatasan jam kerja dalam setiap minggunya. Untuk pemrosesan hanya 10 jam/minggu, sedangkan untuk pengemasan 8 jam/minggu. Formulasikan masalah program linier ke dalam model matematiknya. 2. Untuk menjaga kesehatan seseorang harus memenuhi kebutuhan minimum perhari terhadap beberapa zat makanan misalnya kalsium, protein dan vitamin A. 



Kebutuhan minimum kalsium perhari 8 mg







Kebutuhan minimum protein perhari 10 mg







Kebutuhan minimum vitamin A perhari 32 mg



Ketiga zat makanan terkandung pada 2 jenis makanan yaitu: 



Jenis 1 mengandung 5 mg kalsium, 2 mg protein dan 1 mg Vitamin A







Jenis 2 mengandung 1 mg kalsium, 2 mg protein dan 5 mg Vitamin A



Adapun harga makanan setiap unitnya adalah jenis 1: Rp 500/buah, jenis 2: Rp 700/buah. Buat model matematikanya agar biaya yang dikeluarkan minimum. 3. Sebuah supplier rumah sakit memproduksi meja dan kursi untuk dokter. Setiap meja dijual Rp. 200.000 dan setiap kursi dijual Rp. 100.000, ongkos pembuatan masingmasing adalah 50% dari harga jual. Setiap meja dan kursi terdiri dari komponen besi dan kayu. Pembuatan komponen besi pada meja membutuhkan waktu 2 jam, sedangkan pada kursi 2 jam. Pembuatan komponen kayu pada meja membutuhkan waktu 6 jam, sedangkan pada kursi 6 jam. Terdapat keterbatasan waktu 240 jam/hari untuk besi dan 480 jam/hari untuk kayu. Buat model matematikanya agar keuntungannya maksimum. 4. Seorang petani memerlukan paling sedikit 30 unit zat kimia A dan 24 unit zat kimia B untuk pupuk kebun sayurnya. Kedua zat kimia itu dapat diperoleh dari pupuk cair dan pupuk kering. Jika setiap botol pupuk cair yang berharga Rp20.000,00 mengandung 5 unit zat kimia A dan 3 unit zat kimia B, sedangkan setiap kantong pupuk kering yang berharga Rp16.000,00 mengandung 3 unit zat kimia A dan 4 unit zat kimia B. Buatlah model matematikanya, sehingga petani dalam membeli dua jenis pupuk tersebut mengeluarkan biaya seminimal mungkin.



BAB II METODE PENYELESAIAN SOLUSI GRAFIK



9



A. Solusi Grafik 1. Metode Titik Pojok Salah satu metode pengoptimalan yang dapat digunakan adalah grafik. Fungsi tujuan dan kendala permasalahan digambarkan menggunakan bantuan sumbu absis (horizontal) dan ordinat (vertikal) grafik. Mengingat keterbatasan sumbu koordinat grafik, solusi grafik hanya tepat digunakan untuk dua variabel keputusan. Mengoptimalkan permasalahan dengan jumlah variabel keputusan lebih dari dua akan dihadapkan pada kesulitan penggambaran dan penskalaan. Ini merupakan salah satu kelemahan solusi grafik. Kelemahan lainnya, penskalaan harus dilakukan dengan teliti. Kesalahan penskalaan akan mengakibatkan kesalahan penentuan solusi optimal. Kelebihan solusi grafik di lain pihak adalah kemudahan penggunaannya.



Kita hanya



perlu menggambarkan garis lurus yang mewakili fungsi pembatas dan fungsi tujuan tanpa disertai



perhitungan yang rumit.



Meskipun solusi grafik tidak mungkin



digunakan dalam dunia nyata (variabel keputusan dan sumber daya yang membatasi dalam kehidupan nyata bisa ratusan atau ribuan). Solusi menggunakan solusi grafik dimulai dengan menggambarkan sumbu vertikal dan horizontal yang mewakili alternative keputusan. Jika jumlah sumbu grafik yang dibutuhkan sudah ditentukan maka langkah selanjutnya adalah menggambarkan daerah solusi. Penggambaran daerah solusi dimulai dengan menggambarkan masing-masing fungsi kendala ke dalam sumbu grafik yang sudah ditentukan. Setiap satu kendala akan diwakili satu garis. Setelah garis yang mewakili terbentuk, berikutnya adalah menggambarkan daerah solusi. Solusi grafik yang seperti tersebut di atas disebut metode titik pojok. Perhatikan kasus berikut dan tentukan solusi optimalnya: Contoh Tentukan nilai maksimum dan minimum dari Z = −6 x 1=−72 , dengan syarat:



→



,



x 1=12 , x2=30−2x1 ,



→



Jawab: Titik potong dengan sumbu X untuk pertidaksamaan



x 2=30−2(12)



adalah (0, 4) dan



→



adalah (0, 6) dan



(8,0) Titik potong dengan sumbu Y untuk pertidaksamaan (6,0) Grafiknya 10



6 4 HP 6



8



Titik potong kedua garis adalah



x2=30−24



adalah (4,2)



Titik-titik pojoknya adalah Titik



Z



=



→ (0,4) (6,0) (4,2) (0,0)



12 30 26 0



Jadi nilai maksimumnya adalah 30 dan nilai minimumnya adalah 0 2. Metode Garis Selidik Garis selidik adalah suatu garis yang digunakan untuk menyelidiki nilai optimum (maksimum atau minimum) yang diperoleh dari fungsi sasaran atau fungsi objektif. Nilai optimum (maksimum dan minimum) bentuk objektif dari himpunan solusi sistem pertidaksamaan selain dengan menggunakan metode titik pojok dapat juga dicari dengan menggunakan garis selidik. Langkah-langkah yang diperlukan untuk mencari nilai optimum dengan menggunakan metode garis selidik adalah sebagai berikut a.



Buatlah garis



x 2=6



, dimana



Z=8x1+6x2 +0s1+0s2



merupakan bentuk objektif



yang dicari nilai optimumnya. Untuk mempermudah, ambil Z=8(12)+6(6)+0(0)+0(0)



11



b.



Z =132 , yaitu dengan cara mengambil k yang



Buatlah garis-garis sejajar berbeda atau menggeser garis



x 2=6



 Jika



melalui titik



Z=132



melalui titik



ke kiri atau ke kanan.



adalah garis yang paling kiri pada daerah solusi yang



2 x 1 +x 2 ≥3



 Jika



x 1=12



, maka



Z =5 x 1 +3 x 2 merupakan nilai minimum.



adalah garis yang paling kanan pada daerah solusi yang



x 1+x 2≥2 , maka



x 1 , x 2 ≥0



merupakan nilai maksimum



bentuk objektif tersebut. Contoh Dengan menggunakan garis selidik, tentukan nilai maksimum dan minimum dari fungsi objektif x 1 ,x 2 , s1 , dan s2



pada daerah feasible



yang ditunjukkan oleh gambar di samping Jawab Untuk



fungsi objektif yang diketahui yaitu menentukan



Z=5x 1 +3 x 2+0s 1+0s 2 ,



maksimum dan minimum yang



dan



dinamai



dengan garis g.



pertama dilakukan adalah dengan membuat



persamaan



garis



dari



Geserlah garis g sehingga memotong daerah feasible di titik yang paling kiri, yaitu garis



2x1+x2−s1=3 yang merupakan garis yang sejajar



dengan garis g dan tepat melalui titik (1,2). Dengan demikian nilai minimum Z adalah



12



x 1 + x 2−s 2=2 . Sedangkan garis x1,x2, s1,s2≥0 merupakan garis yang paling kanan dan tepat



melalui



titik



(5,



4).



Dengan



demikian



nilai



maksimum



x 1=0 Aplikasi Geogebra: 1. Penyelesaian solusi grafik metode titik pojok dengan: Tentukan nilai maksimum dan minimum dari Z = −6 x 1=−72 , dengan syarat:



→



,



x 1=12 , x2=30−2x1 ,



→



Langkah-langkah 1.



2.



Buka halaman Geogebra



Tuliskan di kotak input a. b. c.



Fungsi



f ( x)  5 x  3 y



Tulis pertidaksamaan Tulis pertidaksamaan



x  2y  8 x y 6



Z



adalah



d. e.



Tulis pertidaksamaan Tulis pertidaksamaan



x0 y0



f. Berikan tanda titik sudut di setiap pojoknya dengan mengklik tanda g. Tampilkan spreadsheet dengan mengklik view-spreadsheet



h. Jika menginginkan daerah fisibelnya yang tidak diarsir maka dapat dilakukan dengan klik kanan di inequality object properties-style-inverse filling. 2. Solusi grafik dengan metode garis selidik Tentukan nilai maksimum dan minimum dari Z = −6 x 1=−72 , dengan syarat:



→



,



x 1=12 , x2=30−2x1 ,



→



Langkah-langkah: a. Buat grafik penyelesaian seperti pada metode titik pojok b. Buat garis selidik dengan semisal input k=2



Pertebal garis selidik dengan klik kanan pada garis selidik object properties c. Agar garis selidik dapat digerakkan maka harus dimunculkan slider dengan cara klik kanan aljabar pilih show object



Klik kanan pada slider dan atur nilai max dan min yang akan mengatur pergerakan garis selidik d. Memunculkan nilai Z yang akan dimaksimalkan sebagai tex.



SOAL-SOAL LATIHAN 1. Tentukan solusi optimal model matematik di bawah ini secara manual dan menggunakan geogebra Maksimumkan Subjec to



x 2= 0



2x1+x2−s1=3



→ s 1 =−3 x 1+x 2−s 2=2 2. Tentukan solusi optimal model matematik di bawah ini secara manual dan menggunakan geogebra Minimumkan Subjec to



Z  0.4 x1  0.5 x2



s 2 =−2 x 1=0 s 1 =0 2x 1+x2−s1=3



3. Seorang penjahit akan membuat pakaian jadi dengan persedian kain polos 20 meter dan kain bergaris 10 meter. Model A membutuhkan 1 meter kain polos dan 1,5 meter kain bergaris. Model B membutuhkan 2 meter kain polos dan 0,5 meter kain bergaris. Keuntungan pakaian model A sebesar Rp15.000,00 dan pakaian model B sebesar Rp10.000,00. Tentukan keuntungan optimum penjahit tersebut. 4. Seorang agen sepeda bermaksud membeli 25 buah sepeda untuk persediaan. Harga sepeda biasa Rp 600.000 per buah dan sepeda federal Rp800.000 per buah. Ia merencanakan untuk tidak membelanjakan uangnya lebih dari Rp16.000.000 dengan mengharap keuntungan Rp100.000 per buah dari sepeda biasa dan Rp120.000 per buah dari sepeda federal. Buatlah model matematikanya dan berapa keuntungan maksimalnya. 5. Sebuah pesawat terbang mempunyai kapasitas tempat duduk tidak lebih dari 48 orang. Setiap penumpang kelas utama dapat membawa bagasi seberat 60 kg dan kelas ekonomi 20 kg, sedangkan pesawat tersebut mempunyai kapasitas bagasi tidak lebih dari 1.440



kg. Apabila harga tiket untuk kelas utama dan ekonomi masing-masing adalah Rp1.000.000,00 dan Rp500.000,00 per orang, tentukan banyaknya penumpang setiap kelas agar hasil penjualan tiket maksimum. 6. Kebutuhan gizi minimum tiap pasien suatu rumah sakit per harinya adalah 150 unit kalori dan 130 unit protein. Apabila dalam tiap kilogram daging mengandung 500 unit kalori dan 200 unit protein, sedangkan setiap ikan basah mengandung 300 unit kalori dan 400 protein dengan harga masing-masing kilogramnya adalah Rp40.000,00 dan Rp20.000,00. Tentukan biaya minimum untuk kebutuhan 100 pasien tiap harinya pada rumah sakit tersebut. 7. Seorang pemborong merencanakan membangun 2 tipe rumah dengan ukuran T.50 dan T.70. Untuk itu, ia meminta uang muka masing-masing 1 juta untuk rumah T.50 dan 2 juta untuk T.70 dan ia mengharapkan uang muka yang masuk paling sedikit 250 juta rupiah dari paling sedikit 150 buah rumah yang hendak dibangunnya. Biaya pembuatan tiap rumah adalah 50 juta untuk T.50 dan 75 juta untuk T.70. Tentukan biaya minimal yang harus disediakan untuk membangun rumahrumah tersebut. 8. Suatu perusahaan mengeluarkan sejenis barang yang diperoduksi dalam tiga ukuran, yaitu ukuran besar, ukuran sedang dan ukuran kecil. Ketiga ukuran itu dihasilkan dengan menggunakan mesin I dan mesin II . Mesin I setiap hari menghasilkan 1 ton ukuran besar, 3 ton ukuran sedang dan 5 ton ukuran kecil. Mesin II setiap hari menghasilkan masing-masing ukuran sebanyak 2 ton. Perusahaan itu bermaksud memperoduksi paling sedikit 80 ton ukuran besar, 160 ton ukuran sedang dan 200 ton ukuran kecil. Bila biaya operasi mesin I adalah Rp500.000,00 tiap hari dan mesin II adalah Rp400.000,00 tiap hari. Dalam berapa hari masing-masing mesin bekerja untuk pengeluaran biaya sekecilkecilnya dan berapa biaya tersebut. 9. Sebuah pabrik ingin memproduksi suplemen dalam bentuk sirup dan tablet. Suplemen dalam bentuk sirup memberikan harga jual Rp. 27.000/ buah dengan biaya bahan baku Rp. 14.000 dan biaya lain-lain Rp.10.000. Suplemen dalam bentuk tablet memberikan harga jual Rp.21.000/kaplet dengan biaya bahan baku Rp.10.000 dan biaya lain-lain Rp.9.000. Pembuatan dilakukan dalam dua tahap yaitu pemrosesan dan pengemasan. Suplemen sirup memerlukan waktu 2 jam pemrosesan dan 1 jam pengemasan. Suplemen tablet memerlukan 1 jam pemrosesan dan 1 jam pengemasan. Ada keterbatasan jam kerja dalam setiap minggunya. Untuk pemrosesan hanya 100 jam/minggu, sedangkan untuk pengemasan hanya 80 jam/minggu. Dari pengamatan pasar terdapat informasi kebutuhan



tablet tak berhingga, sedangkan kebutuhan sirup 40 buah/minggu. Berapa buah suplemen sirup dan tablet yang harus diproduksi dalam setiap minggu agar keuntungan maksimum. 10. Perusahaan MALINDO ARSHA DANA akan  membuat  almari dan rolling door.keuntungan yang diperoleh dari satu unit almari adalah $ 15,sedangkan keuntungan yang diperoleh satu unit rolling door adalah $25.namun untuk memperoleh keuntungan tersebut perusdahaan MALINDO ARSHA DANA menghadapi kendala keterbatasan jam kerja.untuk pembuatan satu unit almari memerlukan 4 jam kerja,sedangkan untuk pembuatan rolling door memerlukan 6 jam kerja.untuk pengecatan satu unit almari memerlukan waktu 3 jam kerja,dan untuk pengecatan rolling door memerlukan waktu 5 jam kerja.jumlah jam kerja yang tersedia untuk pembuatan almari dan rolling door adalah 360 per bulan.sedangkan jumlah jam kerja untuk pengecatan  adalah 260 jam per bulan.berapa jumlah almari dan rolling door yang sebaiknya diproduksi agar keuntungan perusahaan maksimum ?



BAB III METODE SIMPLEX A. Istilah-istilah Metode grafik tidak dapat menyelesaikan persoalan linear program yang memilki variabel keputusan yang cukup besar atau lebih dari dua, maka untuk menyelesaikannya digunakan Metode Simpleks. Penentuan solusi optimal dengan simpleks dilakukan tahap demi tahap yang disebut dengan iterasi. Iterasi ke-i tergantung dari iterasi sebelumnya (i1). Ada beberapa istilah yang sangat sering digunakan dalam metode simpleks, diantaranya iterasi, variabel non basis, variabel basis, kolom pivot, baris pivot, elemen pivot, variabel masuk, variabel keluar. Masing-masing pengertian dari istilah tersebut sebagai berikut: 1.



Iterasi adalah tahapan perhitungan di mana nilai dalam perhitungan itu tergantung dari nilai tabel sebelumnya.



2.



Variabel non basis adalah variabel yang nilainya diatur menjadi nol pada sembarang iterasi. Dalam terminologi umum, jumlah variabel non basis selalu sama dengan derajat bebas dalam sistem persamaan.



3.



Variabel basis adalah variabel yang nilainya bukan nol pada sembarang iterasi. Pada solusi awal, variabel basis merupakan variabel slack (jika fungsi kendala menggunakan pertidaksamaan



→



) atau variabel buatan (jika fungsi kendala



menggunakan pertidaksamaan



x 2=3



atau =). Secara umum, jumlah variabel basis



selalu sama dengan jumlah fungsi pembatas/ kendala (tanpa kendala non negatif). 4.



Solusi atau nilai kanan adalah nilai sumber daya pembatas yang masih tersedia. Pada solusi awal, nilai kanan atau solusi sama dengan jumlah sumber daya pembatas awal yang ada, karena aktifitas belum dilaksanakan.



5.



Variabel slack adalah variabel yang ditambahkan ke model matematika yang kendala untuk mengkonversikan pertidaksamaan



x1+x2−s2=2



menjadi persamaan ( = ).



Pada solusi awal, variabel slack akan berfungsi sebagai variabel basis.



6.



Variabel surplus adalah variabel yang dikurangkan dari model matematik kendala untuk mengkonversikan pertidaksamaan → menjadi persamaan ( = ). Pada solusi awal, variabel surplus tidak bisa berfungsi sebagai variabel basis.



7.



Variabel buatan/ artificial adalah variabel yang ditambahkan yang ditambahkan ke model matematika kendala dengan bentuk



x2−s2=2



atau = untuk difungsikan sebagai



variabel basis awal. Variabel ini harus bernilai nol pada solusi optimal, karena kenyataannya variabel ini tidak ada. Variabel hanya ada di atas kertas. 8.



Kolom pivot adalah kolom yang memuat variabel masuk. Koefisien pada kolom ini akan menjadi pembagi nilai kanan untuk menentukan baris pivot.



9.



Baris pivot adalah salah satu baris antara variabel basis yang memuat variabel keluar.



10. Elemen pivot adalah elemen yang terletak pada perpotongan kolom dan baris pivot. 11. Variabel masuk adalah variabel yang terpilih untuk menjadi variabel basis pada iterasi berikutnya. 12. Variabel keluar adalah variabel yang keluar dari variabel basis pada iterasi berikutnya dan digantikan oleh variabel masuk. B. Bentuk Baku Sebelum melakukan perhitungan iteratif untuk menentukan solusi optimal terlebih dahulu model matematika dirubah menjadi bentuk baku, dengan merubah fungsi kendala ke dalam bentuk persamaan dengan menyertakan variabel basis awal. Variabel basis awal menunjukkan status sumber daya pada kondisi sebelum ada aktifitas yang dilakukan, dengan kata lain variabel keputusannya masih bernilai 0. Ada beberapa hal yang harus diperhatikan dalam membuat bentuk baku, yaitu: 1.



Fungsi kendala dengan tanda pertidaksamaan



→



dalam bentuk umum, dirubah



menjadi persamaan (=) dengan menambahkan satu variabel slack. 2.



Fungsi kendala dengan tanda pertidaksamaan



−s2=2−3



dalam bentuk umum, dirubah



menjadi persamaan (=) dengan menambahkan satu variabel surplus. 3.



Fungsi kendala dengan tanda persamaan dalam bentuk umum, ditambahkan satu variabel artificial (variabel buatan).



Perhitungan iteratif metode simpleks dilakukan dengan tabel, dengan cara bentuk baku yang sudah diperoleh harus dituangkan ke dalam bentuk tabel. C.



Langkah-langkah Solusi dengan metode simpleks



1. Periksa apakah tabel layak atau tidak. Kelayakan tabel simpleks dilihat dari solusi (nilai kanan). Jika solusi ada yang bernilai negatif maka tabel tidak layak. Tabel yang tidak layak tidak bisa diteruskan untuk dioptimalkan. 2. Tentukan kolom pivot. Penentuan kolom pivot dilihat dari koefisien fungsi tujuan dan bentuk tujuan. a. Jika tujuan berupa maksimasi, maka kolom pivot adalah kolom dengan koefisien fungsi tujuan negatif terbesar. b. Jika tujuan berupa minimasi, maka kolom pivot adalah kolom dengan koefisien fungsi tujuan positif terbesar. Variabel pada kolom pivot menjadi variabel masuk basis menggantikan variabel yang keluar basis. 3. Variabel keluar ditentukan dari rasio nilai kanan dengan elemen pada kolom pivot yang bersesuaian. Variabel keluar dipilih yang rasionya terkecil. Jika nilai negatif terbesar (untuk tujuan maksimasi) atau nilai positif terbesar (untuk tujuan minimasi) lebih dari satu maka dipilih salah satu secara sembarang. 4. Tentukan baris pivot. Baris pivot ditentukan setelah membagi nilai kanan dengan elemen kolom pivot yang bersesuaian (nilai yang terletak dalam satu baris). Baris pivot adalah baris dengan rasio pembagian terkecil. 5. Tentukan elemen pivot. Elemen pivot merupakan nilai yang terletak pada perpotongan kolom dan baris pivot. 6. Bentuk tabel simpleks baru. Tabel simpleks baru dibentuk dengan pertama kali menghitung nilai baris pivot baru, sedangkan baris pivot baru ditentukan dengan membagi baris pivot lama dengan elemen pivot. Baris baru lainnya ditentukan dengan baris lama dikurangi dengan elemen pivot pada baris yang bersangkutan dibagi dengan elemen pivot kemudian dikalikan dengan baris pivot baru. 7. Periksa apakah tabel sudah optimal. Keoptimalan tabel dilihat dari koefisien fungsi tujuan (nilai pada baris Z). a. Untuk tujuan maksimasi, tabel sudah optimal jika semua nilai pada baris Z sudah positif atau nol. b. Untuk tujuan minimasi, tabel sudah optimal jika semua nilai pada baris Z sudah negatif atau nol. Jika belum kembali ke langkah nomor 2, jika sudah optimal baca solusi optimalnya. D. Model Umum Metode Simpleks. 1.



Kasus Maksimisasi.



Fungsi Tujuan : Maksimumkan Z – C1X1-C2X2- . . . . . –CnXn-0S1-0S2-. . .-0Sn = NK Fungsi Pembatas : a11X11+a12X12+. . . .+a1nXn+ S1+0S2+. . .+0Sn = b1 a21X21+a22X22+. . . .+a2nXn+ 0S1+1S2+. . .+0Sn = b2 …….



……..



……. ….. ….. …. …..= …



am1Xm1+am2Xm2+. . . .+amnXn+ S1+0S2+. . .+1Sn = bm Var. Kegiatan



Slack Var



2. Kasus Minimisasi Fungsi Tujuan : Minimumkan Z – C1X1-C2X2- . . . . . –CnXn-0S1-0S2-. . .-0Sn = NK Fungsi Pembatas : a11X11+a12X12+. . . .+a1nXn - S1 -0S2-. . . - 0Sn = b1 a21X21+a22X22+. . . .+a2nXn - 0S1-1S2 -. . . - 0Sn = b2 …….



……..



……. ….. ….. …. …..= …



am1Xm1+am2Xm2+. . . .+amnXn- S1- 0S2 -. . . -1Sn = bm var.kegiatan



Surplus var.



Contoh: Maksimumkan



→



Kendala:



s 2 =1 Z=5x1+3x2+0s1+0s2



Z=5(0)+3(3)+0(0)+0(1) Jawab:



Bentuk baku dari persoalan maksimum tersebut, Maksimumkan



Z =9



x 1=0



Kendala



s 2 =0 x 1 +x 2−s 2=2 Iterasi ke-0



Baris pivot



B



→



x2=2



2x1+x2−s1=3



→



NK



x2−s1=3



2



1



1



0



5



NK 5   2,5 (min) a11 2



→



1



1



0



1



3



s1=x2−3



-3



-2



0



0



0



NK 3  3 a21 1



Angka pivot Paling minimum, jadi kolom pivot Kolom pivot pada tabel iterasi ke-0 adalah kolom kedua, karena pada baris Z mempunyai nilai negatif terbesar, sehingga variabel masuk adalah



→



.



Baris pivot pada tabel 1 adalah baris kedua, karena mempunyai rasio yang



s1=2−3 .



terkecil, sehingga variabel keluar adalah



Angka pivot adalah 2, karena perpotongan kolom pivot dengan baris pivot. Nilai baru pada tabel simpleks kedua sbb:



s 1 =−1



Baris 1.



→



Baris 2.



x 2=0 = = =



Baris 3.



=



s 1 =0



→



s1



2x 1+x 2 −s1 =3



→ 2 x 1 =3



=



=



x 1=1,5



→



= =



x 1 +x 2−s 2=2



x 1−s2 =2 Iterasi ke-1



B



→



x1



→



→



s2=−0,5 x1+x2−s2=2



1



x2=0



Baris pivot



s2=x1−2



0 0



x 1=2



s2=0 2x1+x2−s1=3



Paling minimum, jd baris kunci



3 2



s2=1,5−2



NK



0



s2



1



→



0



2(2)−s1=3



Angka pivot



Kolom pivot pada tabel iterasi ke-1 adalah kolom ketiga, karena pada baris Z mempunyai nilai negatif terbesar, sehingga variabel masuk adalah



→



.



Baris pivot pada tabel 1 adalah baris ketiga, karena mempunyai rasio yang terkecil,



s1=1 .



sehingga variabel keluar adalah Angka pivot adalah



Z=5x1+3x2+0s1 2 , karena perpotongan kolom pivot dengan baris pivot.



Nilai baru Tabel Simpleks 3 dengan angka pivot



Baris 1.



Z=5(2)+3(0)+0(1)+0(0)



s 1 =0 =



s 2 =0



-



2x1+x2−s1=3 →



Z=10



=



2x 1+x 2=3 x 2=3−2 x1



=



x1+x2−s2=2



Baris 2.



→



-



=



x 1 +x 2=2



→ →



x1+(3−2x1 )=2



Baris 3.



=



→



-



=



x 1=1



+



=



−x1=−1 → x 2=3−2 x1



→



Iterasi ke-2



x2=3−2(1)



B



x1



Z=5(1)+3(1)+0( )+0( ) Z=8



x2=1



→



Z = 5 x 1 + 3 x 2+ 0 s 1+ 0 s 2



H



1



0



1



-1



2



0



1



-1



2



1



0



0



1



1



8



Pada Tabel Simpleks ietrasi ke-2, pemecahan dasar sudah memberikan solusi optimum, sehingga perhitungan iterasi dihentikan. Jadi solusi optimum diperoleh dengan



x 2=1 dan



Z=8



x 1=1



.



D. Membaca tabel optimal Membaca tabel optimal merupakan bagian penting bagi pengambil keputusan. Ada beberapa hal yang bisa dibaca dari tabel optimal: 



Solusi optimal variabel keputusan







Status sumber daya







Harga bayangan (dual/ shadow prices)



Dengan menggunakan tabel optimal pada contoh di atas: B



x1



x2



s1



s2



H



x1



1



0



1



-1



2



x2



0



1



-1



2



1



Z



0



0



1



1



8



Z=3x +2x Solusi optimal: x1 = 2, 1 2 = 1, dan Z = 8, artinya untuk mendapatkan keuntungan makasimal sebesar $8, maka perusahaan sebaiknya memproduksi produk 1 sebanyak 2 unit dan produk 2 sebanyak 1 unit. Status sumber daya: Sumber daya pertama dilihat dari keberadaan variabel basis awal dari setiap fungsi kendala pada tabel optimal. Berdasarkan tabel optimal di atas



2x1+x2≤5 =



x1+x2≤3 = 0 maka dapat disimpulkan bahwa kedua sumber tersebut habis terpakai. E.



Metode Big M Dalam pembentukan model matematika sering didapati adanya fungsi kendala dengan tanda pertidaksamaan ” pertidaksamaan ”



Z=3x1+2x2+0 s1+0s2



x 1,x2≥0



” atau ”=”. Fungsi kendala dengan tanda



” mempunyai variabel surplus dan tidak ada variabel slack.



Variabel surplus tidak bisa jadi variabel basis awal, sehingga dibutuhkan satu variabel baru yang dapat berfungsi sebagai variabel basis awal. Variabel yang dapat berfungsi sebagai variabel basis awal hanya variabel slack dan variabel artificial (variabel buatan). 1. Jika semua fungsi kendala menggunakan tanda pertidaksamaan



2x1+x2+s1=5



maka semua



variabel basis awalnya adalah variabel slack. 2. Jika semua fungsi kendala menggunakan tanda pertidaksamaan



x1+x2+s2=3



dan atau



x1,x2, s1,s2≥0



maka semua variabel basis awalnya adalah variabel slack dan atau variabel buatan. Solusi solusi optimal untuk kasus seperti ini dilakukan dengan memilih antara metode Big M, Dua Fase atau Dual Simpleks. 3. Jika fungsi kendala menggunakan tanda persamaan maka variabel basis awalnya adalah variabel buatan. Solusi solusi optimal untuk kasus seperti ini hanya dapat dilakukan dengan memilih antara metode Big M atau Dua Fase.



Perbedaan metode Big M dengan primal simpleks biasa terletak pada pembentukan tabel awal simpleks. Jika fungsi kendala menggunakan tanda pertidaksamaan



x1



, perubahan



dari bentuk umum ke bentuk baku memerlukan satu variabel surplus, sedangkan variabel surplus tidak dapat dijadikan tidak dapat berfungsi sebagai variabel basis awal karena koefisiennya bertanda negatif. Sebagai variabel basis awalnya adalah variabel buatan yang ditambahkan pada bentuk bakunya. Variabel buatan pada solusi optimal harus bernilai 0 karena variabel ini memang tidak ada, keberadaanya hanya di atas kertas. Cara yang digunakan untuk membuat variabel buatan bernilai 0 pada solusi optimal adalah sebagai berikut: 



Penambahan variabel buatan pada fungsi kendala yang tidak memiliki variabel slack.







Jika fungsi tujuan adalah maksimasi maka koefisien variabel buatan pada fungsi tujuan adalah  M .







Jika fungsi tujuan adalah minimasi maka koefisien variabel buatan pada fungsi tujuan adalah  M







Karena koefisien variabel basis pada tabel simpleks harus bernilai 0, maka variabel buatan pada fungsi tujuan



Contoh: Minimumkan Dengan kendala



x2 s1 s2 x1  x2  10



Jawab: Bentuk baku: Minimumkan



s



Dengan kendala



Z



2



x1  3 x2  s2  A1  20 x1  x2  A2  10



b1 a11



b' 1=



1 = [2 2



[



1 2



1



1



1 2



5 2



0



b'2 =b 2−



[1



1



1



0



5]



]



a 21 ( b1 ) a 11



0



[2 [1



1



1



3 ]−



1 2



1 0



1



[



3 ]− 1



1 1 2



0



1 2



[



Fungsi tujuan berubah menjadi:



5 2



0



5]



]



1 2



0



-



1 2



1 2



1



]



Tabel 1 simpleks: a b'3=b3− 31 (b1) a11



B



x1



2



x2



1



s2



1



[−3 -2 0 0 0]+3



[ 2 1 1 0 5]



2



1 3 1 1 2



1 2



Z



[−3 -2 0 0 0]+ 3 3 3 0 15



1 1 15 0- 0 22 2



[]



S2



[ ]



22 2



1



0



0



0



0



-1



1



0



0



0



0



1



0



-M



0



0



NK



Rasio



16



16



s1



20 10



10 5 2



Tabel 2



s2



B



−



1 2



S2



1 2



1 2 15 - 2



15 - 2 1 2



1 2



1 2



0



1



1 2



a2 =



1



0



11 5 0 22 2



1



0



0



1 2



0



0



M 3 3



−



[ ] 1



1 2



2 1 2



Z



2M  3 3



NK



Z



11 1 0 -1 - 22 2 3  4M 3



[]



0



x2



0



a12 b'1=b1− (b2) a22



1



11 5 1 0 22 2



Rasio



s2 20 5



[ ] 10M  60 3



0



Tabel 3 B



=



1 1 2



11 1 0 -1 22 2



[ ]



1 2



[ ] 0 1 -1 2



S2



a b'3=b3− 32 (b2 ) a22



1 1 15 0- 0 22 2



[ ]



NK



−1



x1 x1



[] [0 0 1 8]



0



[0 0 1 8]



s1



0



1



0



0



1



[ ]



11 1 0 -1 22 2



0



1



0



x2



1



0



0



0



2 1 2



Z



11 1 0 -1 22 2



3  6M 6



1 1 15 0- 0 22 2



1



x1 s2



5



[ ] 3  2M 2



5 25



Karena elemen pada baris Z sudah negatif semua maka tabel sudah optimal



F.



Metode Dua Fase Metode dua fase digunakan jika variabel basis awal terdiri dari variabel buatan. Disebut sebagai metode dua fase karena proses optimasi dilakukan dalam dua tahap. Tahap pertama merupakan proses optimasi variabel buatan, sedangkan proses optimasi variabel keputusan dilakukan pada tahap kedua. Karena variabel buatan sebenarnya tidak ada (hanya ada di atas kertas), maka tahap pertama dilakukan untuk memaksa variabel buatan bernilai nol. Contoh: Minimumkan



Z  4 x1  x2



Dengan kendala



3x1  x2  3



x1 x2 s1 Bentuk baku: Minimumkan



s2 x2



Dengan kendala



Z x1 x2



Solusi dengan metode dua fase Fase 1 Minimalkan Dengan kendala



s1 s2 4 x1  3 x2  s1  A2  6 x1  2 x2  s2  4 x1 , x2 , s1 , s2  0



Dari kendala 1 diperoleh:



A1  3  3x1  x2 A2  6  4 x1  3x2  s1 A  A1  A2



=



3  3x1  x2  6  4 x1  3x2  s1



=



9  7 x1  4 x2  s1



A  7 x1  4 x2  s1  9 Tabel simpleksnya tampak sebagai berikut: Tabel 1 B



x1 3



A1



x2



s1



A1



A2



s2



NK



1



0



1



0



0



3



A2



4



3



-1



0



1



0



6



s2



1



2



0



0



0



1



4



A



7



4



-1



0



0



0



9



B



x1



x2



s1



A1



A2



s2



NK



x1



1



1 3



0



1 3



0



0



1



5 3



-1



4 -3



1



0



2



Rasio



3 1 3 6  1.5 4 4 4 1



Tabel 2



A2



0



Rasio



1 3 1 3 2 6  5 5 3 3 9  5 5 3



s2



0



5 3



0



1 -3



0



1



3



A



0



5 3



-1



7 -3



0



0



2



s2



NK



Rasio



0



3 5 6 5



Karena fase



Tabel 3 B



x1



x2



s1



A1



x1



1



0



1 5



3 5



A2 1 -5



x2



0



1



3 -5



4 -5



3 5



0



s2



0



0



1



1



-1



1



1



A



0



0



0



-1



-1



0



0



A = 0 1



3 6 x x s menghasilkan solusi basis optimal 1 = 5 , 2 = 5 dan 2 = 1. Pada tahap ini variabel buatan telah mencapai tujuan dan selanjutnya kolom variabel buatan dapat dihilangkan, dan dilanjutkan ke fase 2. Fase 2 Setelah penghapusan kolom variabel buatan, masalah asli menjadi : Minimumkan



Z  4 x1  x2



1 3 x1  s1  5 5 Kendala



3 1 x1   s1 5 5



3 6 x2  s1  5 5



6 3 x2   s1 5 5



s1  s2  1 x1 , x2 , s1 , s2  0 Dengan mensubstitusikan fungsi kendala 1 dan kendala 2 ke persamaan tujuan didapatkan:



Z  4 x1  x2 3 1  6 3   4   s1     s1  5 5  5 5 







12 4 6 3  s1   s1 5 5 5 5







18 1  s1 5 5



1 18 Z  s1   5 5



tabel simpleks di fase 2 menjadi : B



x1



x1



x2 1



s1 0



s2 1 5



0



NK 3 5



Rasio 3



x2



0



1



s2



0



0



Z



0



0



3 -5 1



1 5



0



6 5



1



1



0



18 5



-2 (diabaikan) 1



Karena soalnya minimasi maka tabel tersebut belum optimal dengan kolom kuncinya adalah kolom



s1 . Perhitungan selanjutnya ditampilkan dalam tabel berikut ini:



B



x1



x2



s1



s2 1 -5



NK



x1



1



0



0



x2



0



1



0



3 5



9 5



s1



0



0



1



1



1



Z



0



0



0



1 -5



17 5



2 5



2 9 17 x x s Tabel tersebut sudah optimal. Solusi optimalnya adalah: 1 = 5 , 2 = 5 , 1 = 1 dan Z= 5 . Metode Dual Simpleks Metode dual simpleks dilakukan jika tanda pertidaksamaan pada fungsi kendala  dan tidak ada tanda = dalam bentuk umum masalah program linier. Langkah-langkah metode dual simpleks: a.



Merubah bentuk  menjadi  dengan mengalikan (-1)



b.



Menentukan baris pivot yaitu yang nilai kanannya negatif terbesar



c.



Menentukan kolom pivot dengan membagi angka pada baris Z dengan angka pada baris pivot yang bersesuaian, kolom pivot adalah yang rasionya positif terkecil



d.



Menetukan angka pivot



Contoh: Minimumkan



Z  4 x1  x2



Dengan kendala



x1  x2  12



4 x1  3x2  6 x1 , x2  0 Semua kendala menggunakan tanda pertidaksamaan



 . Kendala dengan tanda



pertidaksamaan  dapat diubah ke pertidaksamaan  dengan mengalikan kedua ruas dengan angka -1, sehingga bentuk umum masalah program linier di atas menjadi: Minimumkan



Z  4 x1  x2



Dengan kendala



 x1  x2  12 4 x1  3 x2  6 x1 , x2  0



Semua fungsi kendala sudah dalam bentuk pertidaksamaan  , maka untuk merubahnya ke bentuk baku tinggal ditambahkan variabel slack yang berfungsi sebagai variabel basis awal. Bentuk baku sebagai berikut: Minimumkan



Z  4 x1  x2  0 s1  0s2



Dengan kendala



 x1  x2  s1  12 4 x1  3 x2  s2  6 x1 , x2 , s1 , s2  0



Tabel 1 B



x1



x2 -1



s1



s2



s1



-1



1



0



s2



-4



-3



0



1



-6



Z



-4



-1



0



0



0



R



4



1



0



NK -12



Tabel 2 B



x1



x2



s1



s2



NK



x2



1



1



-1



0



12



s2



-1



0



-3



1



30



Z



-3



0



-1



0



12



Tabel sudah mencapai optimum dan layak dengan Z = 12,



x1  0 dan x2  12



KASUS KHUSUS DALAM SIMPLEKS Ada beberapa kasus khusus dalam metode simpleks, antara lain: 1.



Jumlah solusi optimal yang lebih dari satu (alternative or multiple optimal solutions)



2.



Tidak ada solusi feasibel (infeasible LP)



3.



LP yang tidak terbatas (unbounded): ada titik di dalam daerah feasibel dengan nilai z →∞ (untuk kasus maks)



a. Solusi optimal lebih dari satu. Solusi optimal masalah PL lebih dari satu (alternative optima) ditemui jika fungsi tujuan sejajar dengan fungsi batasan. Sebagai contoh perhatikan contoh berikut: Maksimumkan



Z  2 x1  4 x2



Dengan kendala



x1  2 x2  5 x1  x2  4 x1 , x2  0



Solusi: Iterasi ke-0 B



x1



x2



s1



s2



NK



s1



1



2



1



0



5



s2



1



1



0



1



4



Z



-2



-4



0



0



0



x1 1 2



x2



s1 1 2



s2



NK 5 2



Iterasi ke-1 B



x2



1



0



s2



1 2



0



1 -2



1



3 2



Z



0



0



2



0



10



Terlihat bahwa tabel pada iterasi ke-1 sudah maksimal dengan nilai maksimal Z = 10



x x pada saat 1 = 0 dan 2 = memilih



5 2 . Akan tetapi jika iterasi tersebut dilanjutkan dengan



x1 sebagai variabel masuk, maka akan didapatkan tabel sebagai berikut:



Iterasi ke-2 B



x1



x2



s1



s2



NK



x2



0



1



1



-1



1



x1



1



0



-1



2



3



Z



0



0



2



0



10



Tampak pada tabel iterasi ke-2 nilai maksimum Z = 10 didapatkan pada saat



x1 = 3 dan



x2 = 1. Dalam praktek, pengetahuan akan solusi optimum lebih dari satu akan sangat bermanfaat karena manajemen mempunyai kesempatan untuk memilih salah satu sesuai dengan situasi yang dimiliki tanpa merusak nilai tujuan. Bentuk baku: Maksimumkan Dengan kendala



Z  2 x1  4 x2  0 s1  0 s2 x1  2 x2  s1  5 x1  x2  s2  4 x1 , x2 , s1 , s2  0



Tabel 1 B



x1



x2



s1



s2



NK



Rasio



s1



1



s2



1



Z



-2



2



1



0



5



1



0



1



4



-4



0



0



0



Pada tabel 1, kolom pivotnya adalah kolom



5 2 =2.5 4 4 1



x2 , dan baris pivotnya adalah baris s1



Tabel 2 B



x2 s2 Z



x1 1 2 1 2



x2



0



0



1 0



s1 1 2 1 -2



s2



2



0



0 1



NK 5 2 3 2 10



5 x x Pada tabel 2 didapatkan tabel sudah optimal dengan nilai optimal 1 = 0, 2 = 2 , Z = 10. Jika iterasi tersebut dilanjutkan dengan memilih



x1 sebagai variabel masuk dan s2



sebagai variabel keluar maka akan didapatkan tabel 3 berikut: Tabel 3 B



x1



x2



s1



s2



NK



x2



0



1



1



-1



1



x1



1



0



-1



2



3



Z



0



0



2



0



10



Jadi solusi optimal kedua didapatkan dengan nilai optimal



x1 = 3, x2 = 1, Z = 10.



Dalam praktek pengetahuan tentang solusi optimum yang lebih dari satu akan sangat bermanfaat karena manajemen mempunyai kesempatan untuk memilih salah satu sesuai dengan situasi yang dimiliki tanpa harus merusak nilai tujuan. b. Solusi tidak terbatas



Solusi tidak terbatas mengakibatkan nilai fungsi tujuan meningkat terus (untuk masalah maksimasi) atau menurun terus tanpa batas (untuk masalah minimasi). Solusi tanpa batas hanya mengindikasikan satu hal, yaitu model yang dibangun salah. Mendapatkan keuntungan yang tidak terbatas tentunya tidak masuk akal. Untuk mendeteksi suatu solusi tak terbatas yaitu jika semua koefisien pembatas variabel non basis bernilai (-) atau 0 pada suatu iterasi. Contoh: Maksimumkan



Z  2 x1  x2



Dengan kendala



x1  x2  10 2 x1  40 x1 , x2  0



Solusi Iterasi ke-0



x1 1



B



s1



x2



s1



s2



NK



Rasio



-1



1



0



10



10 20



s2



2



0



0



1



40



Z



-2



-1



0



0



0



Iterasi ke-1 B



x1



x2



s1



s2



NK



x1



1



-1



1



0



10



s2



0



2



-2



1



20



Z



0



-3



2



0



20



Jika iterasi ini diteruskan, tidak akan pernah berhenti. Nilai x akan meningkat terus. Dari tabel awal sebenarnya sudah dapat dideteksi bahwa nilai tujuan akan meningkat terus tanpa ada batas dengan memperhatikan koefisien dari maka



x2 dapat betambah nilainya tanpa terbatas.



x2 yang bertanda (-) dan 0,



c. Degeneracy Pada tabel simpleks, ada suatu kemungkinan saat akan menentukan variabel masuk akan ditemukan rasio pembagian terkecil lebih dari satu sehingga dalam menentukan variabel masuknya akan sembarangan. Jika hal ini terjadi satu atau lebih variabel basis akan sama dengan nol pada iterasi selanjutnya. Solusi pada iterasi di mana satu atau lebih variabel basis mempunyai nilai nol disebut sebagai degeneracy. Degeneracy ada 2 macam yaitu degenercy tetap dan degeneracy temporer. Contoh degenercy tetap Maksimumkan



Z  3x1  9 x2



Dengan kendala



x1  4 x2  8 x1  2 x2  4 x1 , x2  0



Solusi simpleks kasus tersebut adalah: Iterasi ke-0 B



x1



x2 4



s1



s2



NK



Rasio



s1



1



1



0



8



2



s2



1



2



0



1



4



2



Z



-3



-9



0



0



0



Jika diperhatikan tabel di atas, ada dua kemungkinan yang akan menjadi baris pivot sehingga ada dua kemungkinan yang akan menjadi variabel keluar yaitu Jika dipilih



s1 maka iterasi selanjutnya adalah sebagai berikut:



Iterasi ke-1 B



x2 s2



x1 1 4 1 2



x2 1 0



s1 1 4 1 -2



s2



NK



Rasio



0



2



8



1



0



0



s1 atau s2 .



Z



3 -4



Nilai kanan



0



9 4



0



18



s2 menjadi nol dan tabel belum optimal. Variabel x1 menjadi variabel



s2 menjadi variabel keluar.



masuk dan Iterasi ke-2 B



x1



x2



s1



s2 1 -2



NK



x2



0



1



0



x1



1



0



-1



2



0



Z



0



0



3 2



3 2



18



2



Dari tabel di atas dapat dilihat bahwa iterasi ke-2 tidak merubah solusi optimal dari iterasi ke-1, masing-masing itersi tersebut menghasilkan hasil yang sama yaitu nilai Z = 18 (prosedur simpleks berulang untuk iterasi yang sama) dan variabel basis



x1 = 0



yang berarti telah terjadi degeneracy. Degeneracy tersebut bersifat tetap karena solusi degenerat sudah muncul pada iterasi ke-1 dan tidak hilang sampai iterasi terakhir (solusi sudah optimum). Contoh degeneracy temporer/ tidak tetap. Maksimumkan



Z  3x1  2 x2



Dengan kendala



¿ ¿ ¿ Z=3x 1+2x 2



Solusi: Iterasi ke-0 B



2x1+x2≤5



x1+x2+s2=3



4



x1,x2,s1,s2≥0



4



x1+x2≤3



x1,x2≥0



Z=3x1+2x2+0s1+0s2



3



1



0



1



0



1



2x1+x2+s1=5 0 0



NK



Rasio



12



3



8



2



x1



4



-1



0



0



Z



-3



-2



0



0



s1



s2



s1



1



8



0



2



0



Iterasi ke-1



x2



B



s2



NK



2



Z



0



1



-1



0



4



Rasio b'1=



b1 a11 =



2 1 =[ 2 1 1 0 5 ] 2



1



[ 2 1 1 0 5]



0



11 5 1 0 22 2



[]



0



-2



0



a



21 b'2=b2− (b1) a1



0



-1



1



2



0



[ 1 1 0 1 3] −



1 2



=8 [ 1 1 0 1 3 ]− 1 1 1 0 5 22 2 =



[] 0



Z



0



11 1 0 -1 - 22 2



[]



a31 b'3=b3− (b1) a1



0



0



6



Pada tabel iterasi ke-1 di atas, yang menjadi variabel masuk adalah



[ 2 1 1 0 5]



tidak bisa menjadi variabel keluar karena koefisien dari



sehingga yang menjadi variabel keluar adalah



1 1 15 0- 0 22 2



[ ]



[−3 -2 0 0 0]+ 3 3 3 0 15



[] 22 2



[−3 -2 0 0 0]+



3 2



akan tetapi



bernilai negatif,



. Degeneracy muncul pada iterasi



ke-1 yaitu ditandai dengan adanya variabel basis yang bernilai 0. Dilanjutkan dengan iterasi ke-2 sebagai berikut:



Iterasi ke-2 B



x1



x2



1 2



0



1



s1 5 2



-



s2



1 2



NK



s2



0



2



-



1 2



0



Z



1



-2



1



4



1 2



15 2



0



a22=



1 2



1



0



1 − 2



1 2



0



0



Z



0



0



−



1 Pada iterasi ke-2 degeneracy sudah tidak ada nilai Z berubah dari 6 menjadi 2 . Degeneracy yang seperti ini disebut degeneracy temporer. d. Solusi tidak layak Solusi tidak layak terjadi jika semua fungsi pembatas tidak dapat dipenuhi secara simultan atau bersama-sama. Solusi tidak layak tidak akan pernah terjadi jika semua fungsi kendala menggunakan pertidaksamaan pertidaksamaan



a b'1=b1− 12 (b2 ) a22



(asumsikan nilai



kanan adalah positif), karena variabel slack selalu memberikan solusi layak. Dari sudut pandang praktikal solusi tidak layak dikarenakan pembentukan model yang tidak benar, dimana beberapa pembatas saling bertentangan.



METODE SIMPLEKS YANG DIREVISI Perhitungan iteratif pada simpleks yang telah dipelajari pada bab sebelumnya membutuhkan waktu yang lebih lama dan kompleks. Perhitungan itu akan semakin lama jika diselesaikan secara manual. Bentuk Masalah Program Linier dalam Matriks adalah sebagai berikut: Maksimumkan/Minimumkan [1 1



Terhadap



2 1 2



dan [0



1 2



1 1 1 - 1 2 2 2



]



1 5 0 2 2



]



[



11 5 0 22 2



Di mana [ ] adalah vektor baris 1



= adalah vektor kolom dengan:



persa



0



1 2



1 1 2



-



1 2



dan



1



1 2



]



, sedangkan



11 1 0 -1 22 2



[ ]



[ 1 0 1 -1 2 ]



dan



b'2=



b2 a22



1 dan [0 1 -1 2 2] adalah matriks



a 32 ' b3 =b 3− (b2 ) a 22



Atau bentuk bakunya: Maksimumkan/Minimumkan [ 0



-



1 1 15 0 2 2 2



[



0 -



]



−1 2



Terhadap



1 2



1 1 1 Vektor [0 2 - 2 1 2] dipartisi menjadi



1 2



1 15 0 2 2



menjadi variabel basis awal, sedangkan Vektor s 1



juga dipartisi menjadi



pada Vektor s 2 . Matriks Z



]



, di mana



x1



s2



1 1 1 0 - 1 2 2 2



[ ]



adalah elemen [0 0 0 1 8] yang



adalah elemen



x2



yang lainnya.



sesuai dengan cara membuat partisi



terdiri dari vektor kolom



P1 , P2 , , Pn .



Jadi bentuk dasar ditulis dengan: Maksimumkan Kendala



Z  CX menjadi Z  CI X I  C II X II  0



( A, I ) X  b karena X II bersesuaian dengan elemen-elemen



berkaitan dengan basis awal 2x1+x2≤5 sehingga kendala menjadi



Z=3x1+2x2



yang



x 1 + x 2≤3



x 1 , x 2 ≥0 Di setiap iterasi anggaplah berkaitannya, berarti



X B mewakili variabel basis saat ini dan B basis yang



X B mewakili m elemen dari X dengan B mewakili vektor (A, I)



X B . Anggaplah CB adalah elemen



yang berkaitan dengan



Z=8



[1 0 1 -1 0 2 ¿ ][0 1 -1 2 0 1 ¿ ] ¿ ¿



yang berkaitan dengan



. Sehingga:



x 1=2 x 2=1



Z=2x 1 +x 2 3x1+x2≥9 x1+x2≥6 x1,x2≥0 =



Z=2x1+ 2+0s1+0s2 3x1+x2−s1=9



=



x1+x2−s2=6



=



x1, x2,s1, s2≥0



s1



Ri



s2



=



Z=2x1+x2+0s1+0s2+MR1+MR2



2x1+x2+0s1+0s2+MR1+MR 2−Z=0 3x1+x2−s1+R1=9 = x1+x2−s2+R2=6 x1,x2,s1,s2,R1, R2≥0 bersesuaian dengan elemen-elemen dari



Karena



zj=CR yj−c j



yang berkaitan dengan



basis awal C R=(M M) , sehingga iterasi simpleks umum dalam bentuk matriks sebagai berikut:



yj



Basis z2=CR y2−c2=(M M)¿(1¿)¿¿ ¿



z3=C R y3−c3=( M M ) ¿ (−1¿) ¿ ¿ ¿



z8=CR y8−c8=(M M )¿(9 ¿)¿¿ ¿



z7=CR y7−c7=(M M)¿(0¿)¿¿ ¿



z1=CR y1−c1=(M M)¿(3¿)¿¿ ¿ z5=C R y5−c5=( M M ) ¿ ( 1¿ ) ¿ ¿ ¿



x1 x2 s1 s2 R1 R2 Z H [3 1 -1 0 1 0 0 9¿][1 1 0 -1 0 1 0 6¿] ¿¿ ¿ ¿



Langkah-langkah Solusi Metode Simpleks yang direvisi 1. Penentuan vektor masuk 



Hitung



[1 0 ¿



1 1 4 1 6 2 9 2



1 1 1 1 313 9 3 3 3 2 232 2



[1 − 0 0 0 3¿][0 1 − 0 ¿]¿ ¿



0 32 ¿ 0 1 12 −32 −13 32 0 92 ¿ ¿



][



]



Solusi z6=C R y6−c6=( M M ) ¿ (0 ¿ )¿ ¿ ¿ 11 1 33 3



[1 − 0 0 0 3¿][0 2 1 −3 −1 3 0 9¿]¿ ¿







Z=



Untuk setiap vektor



15 2



non basis hitung



x 1=



3 2



Untuk masalah maksimasi (minimasi) vektor



¿



x 2=



=



¿



9 2



dipilih dengan nilai



paling negative (positif) (tentukan sembarang jika lebih dari satu



yang sama). Jika semua dicapai. Dengan



2. Penentuan vektor keluar



3C+D≥40



3C+D maka solusi optimal sudah



¿ dan



2C+2D≥60



C≥0 D≥0







Nilai variabel basis saat ini:







Koefisien pembatas variabel masuk:







Vector keluar baik untuk masalah maksimasi maupun minimasi adalah



¿



¿



¿



¿



[2 1 16¿][1 2 1 ¿][1 3 15¿]¿¿ [2 1 1 30¿][1 2 3 50¿] ¿ Di mana ¿ dan ¿ adalah elemen ke- ¿30



dari



¿50



dan



j Z=(30×6)+(2×540)+(1×80)+(14×360)+(12×80)+(12×630)+(18×270)+(4×720) . Jika semua  k  0 , maka permasalahan tersebut mempunyai solusi



yangtidak layak. 3. Penentuan basis berikutnya 1 1 1 Diberikan basis saat ini adalah B , hitung B next  EB



E adalah matriks identitas nilai Z=(2×70)+12×80)+(×54 2360)+(12×450)18×270+(1×540)+(2×180)



Z = 25 . 0



Z=(2×720)+(12×720)+(2×540)+(2×360)+(12×270)+(16×180)+(10×540)+(18×450)



dengan elemen kolom



Z=25.020



diganti oleh



4. Kembali ke langkah 1 Contoh: Maksimumkan Dengan kendala



1



(1,2)⇒R1+K 2=2⇒0+K 2=2⇒K 2=2 (1,4 )⇒R1+K 4=12⇒0+K4=12⇒K 4=12 (3,4 )⇒R 3+K 4=12⇒R 3+12=12⇒R 3=0 (3,1)⇒R3+K1=2⇒0+K1=2⇒K1=2



Solusi: Bentuk bakunya adalah: Bentuk baku: Maksimumkan Terhadap



(4,4)⇒ R4 +K 4 =18⇒ R4 +12=18⇒ R 4=6 (4,3)⇒R 4 +K 3=10⇒6+K 3=10⇒K 3=4 (4,5)⇒R 4 +K 5=24⇒6+K 5=24⇒K 5=18 (2,5)⇒R2 +K 5=2⇒R2+18=2⇒R2=−16 (1,1)=−(R1+K 1 )+30=−(0+2)+30=28



Bentuk vektor dan matriks dari koefisien dan variabel adalah sebagai berikut:



(1,3)=−(R1+K3)+18=−(0+4)+18=14 (2, )=−(R2+K2)+14=−(−16+2)+14=28



(1,5)=−(R1+K 5 )+20=−(0+18)+20=2



(2,3)=−(R2+K3)+14=−(−16+4)+14=26



(4,2)=−(R4+K2)+18=−(6+2)+18=10



¿



(2,4)=−(R2+K4)+8=−(−16+12)+8=12



(3,2)=−(R3+K2)14=−(0+2)14=2



(2,1)=−(R2+K 1)+24=−(−16+2)+24=38



(3, )=−(R3+K3)+12=−(0+4)+12=8



(3,5)=−(R3+K5)16=−(0+18) 6= (4,1)=−(R4+K1)+8=−(6+2)+8=0



¿



Iterasi ke-1. a. Penentuan vektor masuk untuk variabel non basis,



¿ 3C+D



(antara



3C+D≥40



,



2C+2D≥60



)



C≥0



¿



¿



[2 1 30¿][1 2 3 50¿]¿ ¿



[2 1 16¿][1 2 1 ¿][1 3 15¿]¿¿¿



¿







¿



D≥0



=



= ¿



¿50  8



¿30







1  3    z2  c2  YP2  c2 =  0 0 0  6   9  9







1  2   z1  c1  YP1  CI =  0 0 0 7   4  4



Karena masalah maksimasi maka yang menjai vector masuk adalah yang paling negative yaitu vector



P2 .



b. Penentuan vector keluar,



Pr (di antara P4 , P5 , P6 ), dengan diketahui P2 masuk



basis.











1 0 0  0 1 0    1   0 0 1 XB  B b  



y1 y2 y3 y4 y5 y6 y7 y8 =



[3 1 -1 0 1 0 0 9¿][1 1 0 -1 0 1 0 6¿] ¿



5 H 2 = =5 a11 1 2 1 H 2 = =1 (min) a21 1 2



c1 c2 c3 c4 c5 c6 c7 c8



H 5 = =2,5(min) a11 2 H 3 = =3 a 1 21



5 H 2 = =5 a11 1 2 1 H 2 = =1 (min) a21 1 2



B1−13 B2



1 B 31



3B2−B1 B3−(4 M−2)B2



B3−(−2M+1) B2







= 1  ( B b) k    j   min   k   min







Perhitungan untuk langkah a. dan b. dapat diringkaskan sebagai berikut B x4



x1



x2



1 B 2 2



2 3 8  , ,  1 1 3 6



x3



x4



x5



x6



NK



Rasio



2



2



x5



1 3



3



x6



6



8



1 4 3



Z 



¿



-8



-9



Jadi vector keluar adalah



-4



P5



0



0



0



0



c. Penentuan basis berikutnya  12   2   2   1   2   2   2    32      2  =



B 1next  EB 1



 1  3    1   3     6   3 



 1  3    1  3     2    sehingga E  1   1  3 0    0 1 0    1 0 0  3   0 1 0  0  2 1      0 0 1   =  =



1   1  3 0   0 1 0    3   0 2 1    1   1  3 0    0 1 0    3   0 2 1   



Basis baru ini berkaitan dengan vektor dasar  x4  X B   x2  ;  x6 



CB  CII   0 9 0  ;



CNB  CI   8 4 0



1   1  3 0    0 1 0    3   0 2 1  1   B next B  E   Iterasi ke-2 P P, P , P e. Penentuan vector masuk, j (antara 1 3 5 ) 1   1  3 0    0 1 0    3   0 2 1   1 0 9 0     0 3 0  Y  CB B =  1   2    7   8  8 0 3 0 z  c  YP  c   1 1 1 1=  2 4    2   4  8 0 3 0 z  c  YP  c   3 3 3 3= 







0  1    z5  c5  YP5  c5 =  0 3 0  0   0  3



Karena masalah maksimasi maka yang menjai vector masuk adalah yang paling negative yaitu vector b.



5x+3y



Penentuan vector keluar,



.



x+2y≤8



(di antara



x+ y≤6



x≥0



), dengan diketahui



masuk



basis.







y≥0



x+2y≤8 x+y≤6



x+2y=8¿}¿¿¿



5 x +3 y







1   1  3 0    0 1 0    1  3    0 2 1   2   1  7    1 = B P1 = 







  min







Perhitungan untuk langkah a. dan b. dapat diringkaskan sebagai berikut B



ax+by ax + by = k ax + by = k 1 



5x+3 y



y≥0



x+2 y≤8



x+2y≤8



x+y≤6



k=ab ax+by=k 3



Jadi vector keluar adalah



k1=ax1+by1



1  3    2 3   3   



x+y≤6



x + 2 y = 8 ¿ }¿ ¿



5x+3y



=



x≥0



ax + by = k



NK



Rasio



1



3



1



3



2



( x1 , y1)



c. Penentuan basis berikutnya a. Penentuan basis berikutnya



ax+by=k2



x( 2, y2) k2=ax2+by2 z=2x+3y g1 g2 k2=2(5)+3(4)=2 Z=8x1+6x2 sehingga 2x+3y=6=k



=



k 1=2(1)+3(2)=8 =



=



Basis baru ini berkaitan dengan vektor dasar



4x1+2x2≤60 x1 ,x 2 ,s1 , dan s2



2 x 1 + 4 x 2 ≤48



Z=8x1+6x2+0s1+0s2



4x1+2x2+s1=60



 Iterasi ke-3 a. Penentuan vector masuk non basis,



x 2= 0







x 1=0 =







2x 1+4 x 2+s2 =48 =



x 1 , x 2 ≥0



2x1+4x2+s2=48 (antara x1 ,x2 ,s1 ,s2≥0 )



4x1+2x2+s1=60



→ s2=48



⇒



→



Z=8x1+6x2+0s1+0s2



s 1 =60 x 1=0











s 1 =0



=



2x 1+4 x 2+s2 =48 =



4x1+2x2+s1=60



→



2x2=60



→



x2=30



→



s2=48−120



→



→ 4x2+s2=48



Solusi optimal sudah diperoleh, karena nilai vector non basis sudah positif semua. Nilai optimal untuk masing-masing vector basis adalah sebagai berikut:



s 2=−72 Nilai Z dihitung dengan rumus:



x1=0



s2



=



2x1+4x2+s2=48



→



=



Jadi solusi optimalnya Z =



s2=0



4x2=48



→



, dengan



x2=12



,



4x1+2x2+s1=60



dan



→



.



Solusi simpleks dengan Solver Excel. Solver merupakan salah satu fasiltas tambahan (Add-ins) yang terdapat pada program Microsoft Excel. Fasilitas ini terdapat pada MS Excel versi 2007 maupun versi sebelumnya. Solver disediakan oleh MS Excel berfungsi sebagai alat untuk mencari nilai optimal pada suatu formula pada sel lembar kerja Excel ( atau disebut sel target ). Nilai yang diharapkan dapat berupa nilai paling maksimum, nilai paling minimum atau nilai tertentu yang diharapkan.



Microsoft Excel Solver



mengkombinasikan fungsi dari suatu Graphical User Interface (GUI), suatu algebraic modeling language seperti GAMS (Brooke, Kendrick, dan Meeraus 1992) atau AMPL (Fourer, Gay, and Kernighan 1993), dan optimizers untuk linier, nonlinear, dan integer program. Masing-masing fungsi ini terintegrasi ke dalam spreadsheet program. Fitur Solver ini diinstal secara tersendiri karena fasilitas tambahan / optional. Cara mengaktifkannya tidaklah sulit. Langkah-langkah mengaktifkan Solver Add-ins sebagai berikut: 1. Buka worksheet Microsoft Excel 2007 2. Klik Costumize Quick Access Toolbaar pada bagian kiri atas 3. Pilih More Command > Add-ins 4. Pilih Solver Add-in > Go 5. Kemudian klik OK dan ikuti istruksi selanjutnya. 6. Apabila pada menu Data > Analysis, terdapat menu Solver maka proses pengaktifan Solver Add-in telah berhasil Yang perlu diingat, pada saat penambahan fasilitas ini memerlukan master MS Office itu sendiri untuk proses penginstalan baik itu berupa CD master ataupun suatu folder tersendiri yang menyediakan master yang dibutuhkan. Solver merupakan suatu bagian dari serangkaian perintah (command) yang saling berhubungan baik secara langsung maupun tidak langsung dalam suatu group terhadap satu formula dalam suatu sel target. Perintah ini biasa disebut What-if Analysis Tools. Pada dasarnya Solver terdiri dari 3 (tiga) bagian, yakni: 1. Sel Target (Target Cell) Merupakan



bagian



solver



sebagai



tempat



dimana



hasil



akhir



pemrosesan/eksekusi suatu formula ditempatkan. Dalam excel, fungsi tujuan berada dalam satu cell saja. Dimana di dalam cell ini terdapat formula excel dari cell lainnnya. Selain itu, kita harus menentukan tujuan kita itu apa. Apa mau mencari fungsi minimum (meminimumkan Target Cell), fungsi maksimum (memaksimumkan Target Cell), atau membuat fungsi sama dengan nilai tertentu (Value of). 2. Sel Pengatur ( Adjusted Cell )



Solver mengatur perubahan nilai pada sel yang spesifik, untuk memproduksi hasil perlu spesifikasi dari formula pada sel target. Sel pengatur ini harus mempunyai kaitan dengan sel target dalam suatu lembar kerja excel. 3. Sel Pembatas (Constrained Cell) Constraint digunakan untuk membatasi nilai solver yang dapat digunakan pada suatu model tertentu dan constraint mengacu pada sel lain yang memperngaruhi formula pada sel target. Menu solver dapat dilihat dibawah ini: ( Data> Analysis > Solver )



Solver parameter 



Set Target Cell : merupakan sel yang dijadikan target (dalam bentuk formula/rumus)







Equal To : tujuan yang hendak dituju Maximal/Minimal/Nilai tertentu (Value Of)







By Changing Cells : yakni sel asal perhitungan sel target yang dapat dimanipulasi nilainya.







Subject to the Constraints: Batasan-batasan yang diatur dalam perhitungan formula misalnya: nilai yang ditentukan harus positif (x >= 0) dll.



Pada menu Box Dialog Options, set satu atau lebih pilihan yang disediakan:



a. Solusi waktu dan iterasi Pada Max Time box, tuliskan nomor dari waktu (dalam detik/second) yang diizinan untuk solusi waktu. Pada box Iterations, masukkan nomor maksimal dari iterasi yang diizinkan. b. Degree of Precision Pada Precision box, ketikkan derajat ketepatan (Degree of Precision) yang diinginkan, semakin kecil angka itu semakin tinggi ketapatan yang dihasilkan. c. Integer Tolerance Pada box Tolerance, ketik persentase error yang diizinkan pada saat mengeksekusi solusi. d. Degree of Convergence. Pada Convergence box, ketik jumlah perubahan relatif yang diizinkan pada lima iterasi terakhir sebelum solver berhenti dengan solusinya. Semakin kecil angka semakin sedikit perubahan relatif yang diizinkan. Contoh: Suatu perusahaan garmen akan memproduksi dua jenis pakaian yaitu baju dan celana dan rok. Proses produksi meliputi memotong, menjahit dan pengepakkan. Perusahaan tsb mempekerjakan 25 orang pada bagian memotong, 40 orang pada



bagian menjahit dan 5 orang pada bagian pengepakkan. Semua tenaga kerja tsb bekerja 8 jam per hari selama 5 hari kerja seminggu. Untuk produksi baju minimal harus 500 buah baju sesuai dengan pesanan. Tabel berikut menunjukkan waktu yang diperlukan dan keuntungan per satuan untuk pakaian tsb. (dalam jam) pakaian Baju celana rok



memotong 1 2 0.7



menjahit 2 2 1.5



pengepakan 0.2 0.1 0.1



profit 80 120 75



Model dari masalah perusahaan garmen tersebut adalah Maksimumkan keuntungan Dengan kendala



2 x 2 + s 1= 60



→ s 1 =60−24



→ s 1 =36 Z=8x1+6x2 +0s1+0s2 Dengan



Z=8(0)+6(12)+0(36)+0( )



: banyaknya baju yang akan diproduksi



Z=72



: banyaknya celana yang akan diproduksi



x2=0 : banyaknya rok yang akan diproduksi Solusi masalah program linier di atas dapat menggunakan program solver dalam excel dengan langkah-langkah sebagai berikut: a. Masukkan informasi berikut ke dalam spreadsheet Microsoft Excel:



Keterangan: 1.



Nilai keputusan awal ditentukan sembarang, dalam hal ini di pilih



s 1 =0



, nilai-nilai optimum akan dicari oleh computer.



2.



Sel G3 adalah formula dari: G3=SUMPRODUCT(C3:E3,C2:E2)



3.



Sel F6 sampai F9 juga merupakan formula. F6=SUMPRODUCT(C6:E6,C2:E2) F7=SUMPRODUCT(C7:E7,C2:E2) F8=SUMPRODUCT(C8:E8,C2:E2) F9=SUMPRODUCT(C9:E9,C2:E2)



4.



Pilih menu “data” kemudian “solver”.



5.



Isi parameter sebagai berikut:



Set Target Sell: $G$3 (karena G3 mengandung formula target keuntungan) Equal to: Max By Changing Sell: $C$2:$E$2 (karena sel C2 sampai E2 adalah adalah sel yang berisi nilai-nilai optimum dari variabel keputusan yang akan diganti oleh komputer) Subject to the Constraints: Diisi dengan jalan memilih Add, sebagai berikut: Add Constraint Cell Reference: $F$6:$F$8 = $C$2:$E$2 >= 6.



Constraint: $H$6:$H$8 $H$ 0



(Add) (Add) OK



Pilih “Solve”



Selanjutnya komputer akan memunculkan Solver Results.



Hasil solusi masalah linear programming di atas oleh Solver Microsoft Excel ditunjukkan sebagai berikut:



Keterangan: a. Final Value dari profit adalah Rp.74125 berarti perusahaan garmen itu akan mencapai keuntungan yang maksimal senilai Rp.74125 jika melaksanakan keputusan membuat baju sebanyak 500 buah, celana 206 buah dan rok 125. b. Nilai slack dapat diinterpretasikan sebagai berikut: misalkan untuk waktu potong dan jahit nilai slack nya nol artinya jika perusahaan melaksanakan keputusan maka semua sumber daya untuk departemen tersebut habis terpakai atau tidak bersisa. Sedangkan untuk departemen pengepakkan waktu yang digunakan hanya sekitar 133 jam dan waktu yang sisa ada 67 jam. Berdasarkan hasil tersebut maka



untuk tenaga pengepakkan dapat dikurangi 1 orang sehingga akan mengurangi ongkos produksi, karena dengan 4 orang saja sudah cukup bisa mencapai keuntungan maksimal. Solusi program linier dengan LINGO Penyelesaian masalah optimasi dapat dilakukan dengan bantuan software LINGO. Contoh: Maksimumkan Z  5 x  3 y Dengan Kendala x  2 y  8 x y 6



x0 y0 Solusi dengan LINGO



Untuk mengeksekusinya dengan mengklik



. hasilnya adalah:



LATIHAN 1. Max



Z  3x1  2 x2



Kendala



x1  x2  15 2 x1  x2  28 7 x1  2 x2  20 x1 , x2  0



2. Max



Z  8 x1  9 x2  4 x3



Kendala



x1  x2  2 x3  2 2 x1  3x2  4 x3  3 7 x1  6 x2  2 x3  8 x1 , x2 , x3  0



3. Selesaikan soal berikut dengan metode simplek Big M dan simpleks 2 fase



a. Min



Z  2 x1  3x2



Kendala



2 x1  x2  16 x1  3 x2  20 x1  x2  10 x1 , x2  0



b. Min



Z  4 x1  x2



Kendala



x1  x2  3 x1  3x2  20 2 x1  x2  16 x1 , x2  0



4. Selesaikan soal berikut dengan metode simplek Big M, metode simplek 2 fase dan metode dual simpleks dan bandingkan a. Min



Z  2 x1  x2



Kendala



3 x1  x2  9 x1  x2  6 x1 , x2  0



b. Min



Z  40 x1  25 x2



Kendala



x1  2 x2  28 9 x1  3x2  400 2 x1  x2  20 x1 , x2  0



BAB IV PRIMAL DAN DUAL Setiap persoalan program linier selalu mempunyai dua macam analisis, yaitu : analisis primal dan analisis dual yang biasanya disebut analisis primal-dual. Untuk menjelaskan hubungan antara Primal dengan Dual akan ditunjukan dengan contoh kasus di bawah ini: PT. Maju Jaya adalah sebuah perusahaan yang menghasilkan dua macam produk yaitu A dan B. Setiap Produk A menghasilkan laba Rp. 40,- dan Produk B Rp. 60,-. Kedua macam produk tersebut harus diproduksi melalui dua tahap proses yaitu proses I dan proses II. Kapasitas dan waktu proses bagi kedua macam produk tersebut adalah sebagai berikut : Waktu proses A 3 1



Proses I II



Kapasitas per bulan B 2 2



(jam) 2000 1000



Model matematika Kasus diatas adalah : Fungsi Tujuan : Memaksimumkan : Z = 40A + 60B, Fungsi Kendala : 1. 3A +2B



4x1+2x2+s1=60



2000



2. A + 2B → 1000, 3. A,B



4x1=60



0,



Model matematika diatas disebut model Primal. Dual pada dasarnya adalah masalah penentuan harga, yaitu : Harga dari sumber-sumber yang dipergunakan untuk berproduksi secara optimal, dimana harga tersebut merupakan nilai minimum sehingga dapat dipergunakan sebagai bahan pertimbangan untuk menambah atau mengurangi sumber-



sumber tersebut secara tepat. Misalkan C dan D sebagai biaya sewa per jam yang harus dibebankan kepada proses I dan II. Karena jumlah kapasitas yang tersedia untuk proses I adalah 2000 jam dan proses II 1000 jam, maka biaya sewa total untuk kedua macam proses tersebut adalah : F = 2000C + 1000D. Selagi F merupakan jumlah biaya sewa kedua macam proses tersebut maka manajeman PT. Maju Jaya tersebut berusaha untuk meminimumkannya. Pandang jika model Primal sebagai pihak penjual yang ingin memaksimumkan laba, di sisi lain model Dual sebagai pihak pembeli yang menginginkan harga pembelian yang minimum. Setiap unit produk A memerlukan waktu 3 jam pada proses I dan 1 jam pada prose II, sehingga biaya untuk menghasilkan setiap unit produk A adalah



→



.



Dipandang dari pihak pembeli tentu saja harga tesebut tidak boleh lebih rendah dari sumbangan laba yang akan diberikan oleh produk A terhadap penjualan yaitu sebesar Rp. 40,- (bila penjual mendapat laba Rp. 40,- untuk setiap penjualan produk A, maka tentu saja pembeli menginginkan agar harga yang ia bayar untuk biaya pemrosesan produk tersebut paling sedikit harus sama dengan laba yang diperoleh penjual yaitu sebesar Rp. 40,-). Sehingga biaya untuk memroses setiap unit produk A adalah



x 1=15



.



Dengan cara yang sama biaya untuk memroses setiap unit produk B adalah 2 x 1 +4 x 2 +s2 =48



dan selanjutnya karena harga tidak mungkin negatif maka



→



dan



2x1+s2=48 .



Asumsi Dasar : Untuk dapat menyusun suatu persoalan primal Program Linier ke dalam bentuk dual, maka selalu harus dirumuskan terlebih dahulu ke dalam bentuk kanonik.







Untuk persoalan maksimasi, maka semua rumusan fungsi kendala mempunyai tanda lebih kecil dari pada atau sama dengan ( → ).







Untuk persoalan minimasi maka tanda fungsi syarat ikatannya harus lebih besar dari pada atau sama dengan (



s2=48−30



) . ( Ingat bahwa tidak perlu semua konstanta atau nilai



sebelah kanan (nsk) fungsi kendala yang bersangkutan harus selalu non-negatif dalam suatu rumusan yang berbentuk kanonik).







Jika suatu persoalan dalam rumusan Program Linier mempunyai fungsi kendala kesamaan (nilai nsk-nya bertanda sama dengan), maka fungsi kendalanya tersebut dapat ditukar atau diganti dengan dua fungsi lainnya, yang pertama, bertanda “lebih kecil dari pada atau sama dengan ( → )”dan yang kedua, bertanda “lebih besar



dari-pada atau sama dengan (



s2=18



)”. Salah satu diantara kedua fungsi kendala lain



tersebut (dipilih salah satu), kemudian diambil, dan kalikan dengan (-1) untuk mendapatkan fungsi kendala yang sesuai dengan aturan yang diminta oleh bentuk kanonik tersebut.



Contoh: Sebuah perusahaan pakaian memiliki data sebagai berikut: Baju 1 2 1 1 30



Katun Sutera Tetron Harga



Baju 1 2 3 50



Tersedia 16 11 15



Berapa banyak baju 1 dan baju harus dibuat agar penghasilan maksimum? Kita lakukan analisis terhadap masalah yang harus dibahas ini. Jika masalah ini kita anggap sebagai masalah Primal maka tentukan matriks koefisiennya. 1.



Matriks koefisien dari masalah primal adalah:



Z=8x1+6x2+0s1+0s2 2.



Dual memiliki fungsi objektif sebagai berikut: F = 16 u + 11v + 15w



3.



Masalah dual memiliki matriks koefisien sebagai berikut:



Z=8(15)+6(0)+0(0)+0(18) 3.



Masalah dual minimum dapat ditulis sebagai berikut: Minimumkan: Kendala:



f = 16u + 11v + 15w 2u + v + w Z=120 u + 2v + 3w x 2=0



Latihan: Tentukan dual dari masalah primal berikut, dan tentukan solusinya: Min



Z  x1  20 x2  2 x3  10 x4



Kendala



2 x1  x2  x3  40 x1  4 x2  x4  80 x1  x2  4 x4  100 x1  x2  x4  60 x1 , x2 , x3 , x4  0



BAB V MODEL TRANSPORTASI Model Transportasi adalah pengalokasian pengiriman sejumlah barang (satu macam barang) yang berasal dari sejumlah sumber pengiriman menuju sejumlah tujuan pengiriman yang memberikan biaya pengiriman total terendah. Barang yang akan dikirim dari setiap sumber pengiriman dan jumlah permintaan yang diminta oleh setiap tujuan pengiriman, serta biaya pengiriman dari setiap sumber menuju setiap tujuan adalah berbeda. Penggunaan model Transportasi antara lain untuk : 



Persoalan pengiriman barang







Persoalan perancangan produksi







Penugasan mesin-orang







Penugasan mesin-pekerjaan Formulasi Matematik Karena tujuan optimasi adalah penentuan total biaya minimum, maka tujuan dalam model matematiknya adalah minimasi. Alternatif keputusan dalam hal ini adalah penentuan jumlah yang akan diangkut dari daerah sumber



s2=0



menuju tujuan 2x1+4x2+s2=48 .



Koefisien fungsi tujuan adalah biaya angkut per unit dari sumber



→



menuju tujuan



2x1=48 . Kendala atau sumber daya yang membatasi penentuan total biaya transportasi



optimum adalah jumlah suplai pada masing-masing sumber dan jumlah permintaan pada masing-masing daerah tujuan. Banyaknya yang harus diangkut dari sumber



→



menuju tujuan



4x1+2x2+s1=60 , biaya transportasi per unit komoditas dari sumber dilambangkan



s1=−36



→



. Sedangkan



→



x1=24



dilambangkan



menuju tujuan



4x1+s1=60



s1=60−96 adalah banyaknya suplai pada sumber → , dan



sebagai banyaknya permintaan pada tujuan



transportasi adalah: Minimumkan



s 1 =0



Terhadap



s 2 =0



s 1 , maka bentuk PL kasus



4x1+2x2+s1=60



→



4x1+2x2=60 Jika total suplai



→



sama dengan total permintaan



x2=30−2x1



, maka formulasi



yang dihasilkan disebut sebagai model tansportasi seimbang. Penentuan Solusi Awal Langkah pertama dalam metode transportasi terdiri atas penentuan solusi awal program transportasi. Tersedia berbagai metode untuk menentukan program awal tersebut. Akan dibicarakan tiga metode dalam penanganan langkah pertama dalam persoalan transportasi. Solusi awal layak dilihat dari jumlah sel yang teralokasi. Solusi layak jika jumlah sel yang terisi sebanyak m + n – 1 (m menunjukkan banyaknya sumber dan n adalah banyaknya tujuan). 1.



Aturan NWC (North West Corner) Sesuai nama aturan ini, maka penempatan pertama dilakukan di sel paling kiri dan paling atas (northwest) matriks. Banyaknya yang dialokasikan pada sel kosong tersebut ( tidak boleh melebihi jumlah suplai pada sumber



2x1+4x2+s2=48 )



→ dan banyaknya permintaan pada



tujuan 2x1+4x2=48 . Contoh: PT. X yang memproduksi minuman ringan yang dibotolkan memiliki 4 pabrik yang letaknya di tempat yang berbeda, yaitu A, B, C, D. Produk dari pabrik tersebut akan didistribusikan ke 5 gudang di 5 kota yang berbeda, yaitu P, Q, R, S dan T. Setiap hari masing-masing pabrik memproduksi (dalam ribu krat) 900, 540, 810, dan 990. Sementara itu masing-masing agen berturut-turut memesan (dalam ribu krat) 360, 720, 540, 900 dan 720 unit. Adapun biaya pengangkutan per krat minuman (puluhan rupiah), tampak pada tabel. Pabrik menghendaki semua barang terkirim dan semua permintaan gudang terpenuhi dengan biaya sekecil mungkin. Tabel 1. Biaya distribusi per unit dan kapasitas sumber dan tujuan Asal/Tujuan A B C D Permintaan



P 30 24 2 8 360



Q 2 14 14 18 720



R 18 14 12 10 540



S 12 8 12 18 900



T 20 2 16 24 720



Kapasitas 900 540 810 990 3240



Solusi dengan metode NWC: Dimulai sel pojok kiri atas diisi maksimum, kemudian diikuti sel-sel lainnya. Asal/Tujuan A



P 30



Q 2



R 18



S 12



T 20



Kapasitas 900



B



360 24



540 14



14



8



2



540



2



180 14



360 12



12



16



810



630 18



24



990



270 900



720 720



3240



C D



8



18



180 10



Permintaan



360



720



540



Layak tidaknya solusi awal dipenuhi jika banyaknya sel basis (sel yang terisi sama dengan 5 + 4 – 1 = 8. Jumlah sel basis pada solusi awal dengan metode NWC di atas adalah 8, dengan demikian solusi awal yang diperoleh sudah layak. Alokasi barang dilihat dari solusi awal dengan metode NWC di atas adalah: 



Banyaknya krat yang diangkut dari pabrik A ke gudang P adalah 360.000 krat per hari.







Banyaknya krat yang diangkut dari pabrik A ke gudang Q adalah 540.000 krat per hari







Banyaknya krat yang diangkut dari pabrik B ke gudang Q adalah 180.000 krat per hari







Banyaknya krat yang diangkut dari pabrik B ke gudang R adalah 360.000 krat per hari







Banyaknya krat yang diangkut dari pabrik C ke gudang R adalah 180.000 krat per hari







Banyaknya krat yang diangkut dari pabrik C ke gudang S adalah 630.000 krat per hari







Banyaknya krat yang diangkut dari pabrik D ke gudang S adalah 270.000 krat per hari







Banyaknya krat yang diangkut dari pabrik D ke gudang T adalah 720.000 krat per hari







Total biaya pengangkutan minuman ringan per hari adalah:



→ Z = 5.130.000.000 2. Metode Inspeksi/ Biaya terkecil Dalam solusi persoalan transportasi tanpa ragu-ragu diperlukan inspeksi dan pertimbangan. Alokasi pertama dibuat terhadap sel yang berkaitan dengan biaya pengangkutan terendah. Sel dengan ongkos terendah ini diisi sebanyak mungkin dengan mengingat persyaratan kapasitas awal maupun permintaan tempat tujuan. Kemudian beralih ke sel termurah berikutnya dan mengadakan alokasi dengan memperhatikan kapasitas yang tersisa dan permintaan baris dan kolom. Tabel 1. Asal/Tujua



P



Q



R



S



T



Kapasitas



n A B C D Permintaan



30 24 2 8 360



2 14 14 18 720



18 14 12 10 540



12 8 12 18 900



20 2 16 24 720



900 540 810 990 3240



Tabel 2. Asal/Tujua n A B C D Permintaan



P



Q



R



S



T



Kapasitas



30 24 2



2 14



18 14



12 8



20 2



14



12



12



16



900 540 810



18 720



10 540



18 900



24 720



360 8 360



450 990 3240



Tabel 3. Asal/Tujua



Q



R



S



T



Kapasitas



n A



2



900



18



12



20



14 12 10 540



8 12 18 900



2 16 24 720



180 540 450 990 3240



R



S



T



Kapasitas



18



12



180



B



14



8



20 2



C D



12 10



12 18



Permintaan



540



900



R



S



T



Kapasitas



18



12



20



180



12 10



12



16



18



24



450 990



900



180



450 3240



S



T



Kapasitas



20



180



B C D Permintaan



720 14 14 18 720



Tabel 4. Asal/Tujua n A



540 16 24 720 180



540 450 990 3240



Tabel 5. Asal/Tujua n A C D Permintaan



540 540



Tabel 6. Asal/Tujua n A



12 180



C D Permintaan



12 18 900 720



16 24



450 450



180



3240



T



Kapasitas



16



450



24



450



180



3240



T



Kapasitas



Tabel 7. Asal/Tujua n



C D Permintaan



S



12 450 18 720 270



Tabel 8. Asal/Tujua n



D Permintaan



S



18 270 270



24



450 180



180



Tabel 9. Asal/Tujua n



D Permintaan Tabel 10.



T



Kapasitas



24 180



180



Asal/Tujua n



P



Q



A



R



S



2



12



720



180



T



Kapasitas 900



2



B



540



540



C



2



12



360 10



450 18



24



540 540



270 900



180 720



D Permintaan



360



720



810 990 3240



2 x 1 + 4 ( 30 −2 x1 )= 48



→



3.



Metode VAM Langkah-langkah pada metode VAM: a. Mengurangkan biaya yang terkecil pada setiap baris dengan biaya yang lebih besar satu tingkat pada baris yang sama b. Demikian juga untuk kolom c. Pilih hasil selisih terbesar pada baris dan kolom d. Alokasikan dengan memilih sel yang biayanya terkecil pada baris dan kolom yang dipilih. e. Ulangi langkah 1 tapi baris dan kolom yang sudah dialokasikan jangan digunakan lagi f. Hitung total biaya



terkecil



Tabel 1 Asal/Tujua



P



Q



R



S



T



Kapasitas



Selisih



30



2



18



12



900



10



B



24



14



14



8



20 2



C D



2 8



14 18



12 10



Permintaan



360



720



540



12 18 900



Selisih



6



12



2



n A



4



540 16 24 720 180 14*



540 810 990



6 10 2



3240



Selisih terbesar



Baris B hilang



Elemen terkecil pada kolom T adalah sel (B, T) = 2. Min{540, 720} = 540. Jadi sel (B, T) = (2; 540) Tabel 2 Asal/Tujua



P



n A



30



C D Permintaan Selisih



2 8 360 6



Q 2 720 14 18 720 12*



R



S



T



18



12



20



12 10 540 2



12 18 900 6



16 24 180 4



Kapasitas 900 180



Selisih 10



810 990 3240



10 2



Kolom Q hilang Elemen terkecil pada kolom Q adalah sel (A,Q) = 2. Min {720, 900} = 720. Jadi sel (A, Q) = (2; 720) Tabel 3 Asal/Tujua n A



P



R



S



T



Kapasitas



Selisih



30



18



12



20



180



6



12



12



16



810



10*



10 540 2



18 900 6



24 180 4



450 990 3240



2



2



C D Permintaan Selisih



360 8 360 6



terbesar



Kolom P hilang Elemen terkecil pada baris C adalah sel (C,P) = 2. Min {360, 900} = 810. Jadi sel (C,P) = (2; 360) 2x1+120−8x1=48 Tabel 4



Asal/Tujuan A



R 18



S 12



T 20



Kapasitas Selisih 180 6



C D



12 10



12 18



16 24



450 990



4 8*



terbesar



Permintaan Selisih



540 540 2



900 6



180 4



450 3240



Elemen terkecil pada baris D adalah sel (D,R) = 10. Min {540, 990} = 540. Jadi sel (D,R) = (10; 540) Tabel 5 Asal/Tujuan A C D Permintaan Selisih



S 12 180 12 18 900 720 6



T 20



Kapasitas Selisih 8* 180



16 24



450 450



180



3240



4 6



4



Elemen terkecil pada baris A adalah sel (A,S) = 12. Min {180, 900} = 180. Jadi sel (A,S) = (12; 180) Tabel 6 Asal/Tujuan



S



C



12



D Permintaan Selisih



18 720 6



T



Kapasitas Selisih



16



450



180 24 180 8*



270 450 3240



4 6



Terbesar Kolom T hilang Elemen terkecil pada kolom T adalah sel (C,T) = 16. Min {180, 450} = 180. Jadi sel (C,T) = (16; 180) Tabel 7 Asal/Tujuan



S



Kapasitas



C



12



270



Beda Kolom 12



Baris A hilang



18



D



450 720



Permintaan



3240



270 6



Beda Baris



18*



450



Elemen terkecil pada kolom T adalah sel (D,S) = 18. Min {450, 720} = 450. Jadi sel (D,S) = (18; 450)



Tabel 7 Asal/Tujua



S



Kapasitas



C



12



270



Permintaan



270



n



Elemen terkecil pada kolom T adalah sel (D,S) = 18. Min {450, 720} = 450. Jadi sel (D,S) = (18; 450) Tabel Lengkap Asal/Tujua n



P



A



Q



R



S



2



12



720



180



2



12



360 10



270 18



540



450



540



900



D Permintaan



360



720



Kapasitas 900



2



B C



T



540 16 180



540 810 990



720



3240



Terbesar Baris D hilang



Banyaknya sel basis yang diperoleh sama dengan 7, dengan demikian solusi awal yang diperoleh sudah layak.



→ −6 x 1=−72



Metode Penentuan Solusi Optimal Setelah menyusun tabel/ program awal dengan salah satu metode, langkah selanjutnya adalah menguji apakah program awal sudah memberikan solusi optimal. Ada dua metode yang bisa digunakan untuk menentukan solusi optimal, yaitu metode Steppingstone dan Modified Distribution (MoDi). Kedua metode digunakan untuk menentukan sel masuk. 1.



Metode MoDi Masih menggunakan program awal dengan metode inspeksi, uji keoptimalan dengan mencari nilai dari sel isi, dengan diawali niali R



→



selalu nol.



Contoh: Perhatikan hasil solusi awal pada metode inspeksi di atas. Perhatikan kembali tabel transportasi dengan m sumber dan n tujuan. S U M B E R



TUJUAN 1



2



−6x1=−72



1



→



x2=30−2x1



→



2



x1=12 x2=6



2x1+x2≥3



m



kapasitas



Z=8(12)+6( )+0( )+0( )



x2=30−2(12)



x 1=12



Z=8x1+6x2+0s1+0s2



Z=132



x1+x2≥2



x1,x2≥0



x1,x2 ,s1 , dan s2



x1+x2−s2=2



x1=0



2x1+x2−s1=3



x1,x2, s1,s2≥0



x2=0 s2=−2



→



n



Suplai



→



→



x2=30−24 x2=6



Z=5x1+3x2



Z=132 Z=5x1+3x2+0s1+0s2



→ s1=−3 x1=0



2x1+x2−s1=3



x1+x2−s2=2



s



Minimumkan Terhadap



1



=0



2 x 1 + x 2 −s1 =3 x 1 + x 2− s 2=2



x2−s2=2



→



−s2=2−3



→



x2=3



→



→



s 2 =1



Z=5x1+3x2+0s1+0s2



Z=5(0)+3( )+0( )+0(1)



Z =9



x 1=0



s2=0



→



x2=2



x 1 + x 2− s 2=2 2x1+x2−s1=3



x2−s1=3



→



→



s1=x2−3



→



Solusi optimal tercapai jika untuk: 



Maksimasi,



s 1 =2−3







Minimasi,



→



Langkah-langkah penyelesaian: 1. Penentuan sel masuk a. Untuk setiap sel basis/ sel isi, hitung baris ke-i dan



s 1 =−1 .



s 1 menunjukkan



x2=0 menunjukkan kolom ke-j, sedangkan s1=0 adalah biaya



pada sel ij; Karena banyaknya variabel yang tidak diketahui (



2x 1+x 2−s1=3 )



lebih banyak dibandingkan banyaknya persamaan yang dibentuk, maka salah satu variabel diasumsikan bernilai 0. b. Untuk setiap sel non basis, hitung



→



c. Untuk maksimasi, sel masuk adalah sel dengan



2x1=3



paling negatif,



sedangkan untuk minimasi sel masuk adalah sel dengan



→



paling



positif. 2. Penentuan sel keluar. Penentuan sel keluar dilakukan dengan loop tertutup. Awal dan akhir loop adalah sel masuk. Garis-garis horizontal dan vertikal yang membentuk loop harus berakhir pada sel basis.



3. Pemeriksaan keoptimalan dilakukan dengan melihat maksimasi optimal jika



→ Asal/Tujuan A(1)



C(3) D(4) Permintaan



x1+x2−s2=2 semua, dan untuk minimasi optimal jika



semua.



P(1) 30



Q(2) 2 720 14



R(3) 18



2 360 8



14



12



18



360



720



10 540 540



24



B(2)



x1=1,5 . Untuk



14



S(4) 12 180 8



T(5) 20 2 540 16



12 450 18 270 900



24 180 720



Kapasitas 900 540 810 990 3240



Sel basis: AQ (12), AS (14), BT (25), CP (31), CS (34), DR (43), DS (44), DT (45) Sel Non Basis: AP (11), AR (13), AT (15), BP (21), BQ (22), BR (23), BS (24), CQ (32), CR (33), CT (35), DP (41), DQ (42) Penentuan Sel Masuk Untuk setiap sel basis/ sel isi, misalkan 12 →



s2=x1−2 = 2



14 →



s2=−0,5 = 12



→



x1+x2−s2=2 = 2



s2



25



s2 =0



31



2x1+x2−s1=3



34



s 1=1



Z=5x1+3x2+0s1+0s2 = 12



Z=5(2)+3(0)+0(1)+0(0)



43



s 1=0



s 2 =0 = 10



2x1+x2−s1=3



44



2x1+x2=3



45 →



→



→



→



=2



2(2)−s1=3



= 18



x1+x 2=2 = 24



s2=1,5−2 x 2=0 x 1=2



→ Z =10 →



x2=3−2x1



x 1 + x 2− s 2=2



→



x 1 +( 3−2 x 1 )=2



Untuk setiap sel non basis/ sel kosong



→



−x 1=−1 = 0 + 2 – 30 = -18



→



x 1=1 = 0 + 4 – 18 = -14



x2=3−2x1



→



x1−s2=2



= 0 + 18 – 20 = -2



x2=3−2(1)



→



x2=1



= - 16 + 2 – 24 = - 34



Z=5x1+3x2+0s1+0s2 = - 16 + 12 – 14 = - 18



Z=5(1)+3(1)+0( )+0( )



Z =8



= -16 + 4 – 14 = - 26



x1=1



x 2=1



= -16 + 12 – 8 = - 12



Z=8



 u2  v5  c25 = -16 + 18 – 14 = - 20



c33  u3  v3  c33 = 0 + 4 – 12 = - 8 c35  u3  v5  c35 = 0 + 18 – 16 = 2 c41  u4  v1  c41 = 6 + 2 – 8 = 0



Z=3x1+2x2



2 x 1 +x 2 ≤5 = 6 + 12 – 18 = 0



Karena ini masalah minimasi maka sel non basis harus negatif semua, karena masih ada yang positif maka tabel belum optimal. Sel masuk adalah sel positif terbesar yaitu sel 35, artinya dengan mengisi sel 35 maka biaya transport bisa berkurang. Penentuan sel keluar Sel keluar ditentukan dengan menggunakan sel tertutup. Loop harus berawal dan berakhir sel masuk yaitu sel 35. Bentuk loop nya adalah 35 – 34 – 44 – 45, sehingga tabelnya menjadi seperti berikut: Asal/Tujua n A(1) B(2) C(3) D(4) Permintaan



P(1)



Q(2)



R(3)



S(4)



T(5)



30



2



18



12



20



24



720 14



14



180 8



2



12



12



540 16



10



270 18



180 24



540



450



540



900



2 360 8



360



14 18



720



720



Kapasitas 900 540 810 990 3240



Setelah dioptimalkan dengan metode MoDi maka Nilai Z = 25020, sebelumnya dengan metode inspeksi adalah Z = 25200. 2. Metode Stepping Stone



Metode stepping stone digunakan untuk menentukan solusi optimal dengan memeriksa kemungkinan pengurangan biaya untuk kasus minimasi (penambahan keuntungan untuk kasus maksimasi) jika sel non basis tertentu berubah menjadi sel basis. Metode stepping stone mencoba (dengan trial and error) mengisi sel yang masih kosong dengan memindahkan alokasi sebagian atau keseluruhan dari sel yang sudah terisi. Jika pemindahan itu mengakibatkan pengurangan baiya total, maka dibentuk loop untuk menentukan sel yang akan dikosongkan/kurangi dan sel yang akan bertambah.



Contoh: Solusi awal dengan metode inspeksi/biaya terkecil sbb: Asal/Tujua n A(1) B(2) C(3) D(4)



P(1)



Q(2)



R(3)



S(4)



T(5)



30



2



18



12



20



24



720 14



14



180 8



2



12



12



540 16



18



10



450 18



24



720



540 540



270 900



180 720



2 360 8



Permintaan 360 Untuk sel kosong:



14



Sel 11: 30 – 12 + 12 – 2 = 28 Sel 13: 18 – 12 + 18 – 10 = 14 Sel 15: 20 – 24 + 18 – 12 = 2 Sel 21: 24 – 2 + 24 – 18 + 12 – 2 = 38 Sel 22: 14 – 2 + 12 – 18 + 24 – 2 = 28 Sel 23: 14 – 2 + 24 – 10 = 26 Sel 24: 8 – 2 + 24 – 18 = 12 Sel 32: 14 – 12 + 12 – 2 = 12



Kapasitas 900 540 810 990 3240



Sel 33: 12 – 12 + 18 – 10 = 8 Sel 35: 16 – 24 + 18 – 12 = - 2 Sel 41: 8 – 18 + 12 – 2 = 20 Sel 42: 18 – 18 + 12 – 2 = 10 Interpretasi dari nilai sel kosong di atas adalah: Untuk sel 11 jika akan diisi dengan memindahkan sejumlah unit dari sel 14, 34, dan 31 maka akan menambah biaya per unit sebesar 28. Dengan demikian maka pengalokasian ke sel 11 sebaiknya jangan diakukan. Beradasarkan nilai data di atas maka pemindahan sejumlah unit tersebut akan mengurangi biaya sebesar 2 jika mengisi sel 35 dengan loop sel 35, 45, 44 dan 34. Setelah dilakukan pemindahan tersebut maka tabelnya menjadi seperti berikut:



Asal/Tujua n A(1) B(2) C(3) D(4) Permintaan



P(1)



Q(2)



R(3)



S(4)



T(5)



30



2



18



12



20



24



720 14



14



180 8



2



12



12



540 16



18



10



270 18



180 24



720



540 540



450 900



720



2 360 8 360



14



Kapasitas 900 540 810 990 3240



Setelah dioptimalkan dengan metode stepping stone maka Nilai Z = 25020, sebelumnya dengan metode inspeksi adalah Z = 25200. Metode M Besar dan Dummy Misalkan alokasi dari suatu daerah sumber menuju daerah tujuan tidak dimungkinkan karena berbagai alasan, diantaranya tidak adanya jalur transportasi, biaya yang sangat mahal, waktu lama melebihi umur ekonomis dan lain-lain. Kasus di atas dapat diatasi dengan memberikan biaya yang sangat besar (M besar) pada sel yang bersesuaian jika tujuannya adalah minimasi, atau keuntungan yang sangat kecil (-M besar) jika tujuan



adalah maksimasi. Teknik ini menghasilkan tidak adanya pengalokasian pada sel yang bersangkutan. Contoh: Asal/Tujua n 1 2 3 4 Permintaan



1



2



3



4



Kapasitas



15 6 10 11 300



5 10 15 5 400



M 20 10 16 200



13 3 8 9 300



200 300 350 350 1200



4



Kapasitas



Solusi dengan metode VAM Tabel.1 Asal/Tujua



1



2



3



15



5



M



2 3 4



6 10 11



20 10 16



Permintaan



300



200 10 15 5 400



n 1



Selisih



200



8*



3 8 9



300 350 350



3 2 4



200



300



1200



6



5



13



4



200 0



1



2



3



4



Kapasitas



1 2



6 10



20 10



3



3



10 15



300 350



3 2



4 Permintaan selisih



11 300 4



5 200 5



200 16 200 6*



150 350 1200



4



selisih Tabel.2 Asal/Tujua n



Tabel.3



8 9 300 5



Selisih



Asal/Tujua n



1



2



6



3



Selisih



4



Kapasitas



10



3



300



3



10 11 300 4



15 5 200 5



300 8 9 300 5*



150 350 1200



2 4



1



2



4



Kapasitas



10 11



15 5



150 350



300 1



200 200 10*



150 1200



1



2



1 2 3 4 Permintaan selisih



Tabel.4 Asal/Tujua n 1 2 3 4 Permintaan selisih



3



Selisih



5 4



Tabel.5 Asal/Tujua n



3



4



Kapasitas



Selisih



1 2 3 4 Permintaan selisih



10



150



10



150 11



150



11



150 300 1



1200



Ringkasan pekerjaan di atas Asal/Tujua n 1 2



1



2



3



15



5



M



6



200 10



20



4



Kapasitas



13



200



3



300



0 10



3



300 15



150 11



4



10



8



200



350



5



16 9 350 150 200 Permintaan 300 400 200 300 1200 Jumlah sel basis (sel isi) seharusnya 4 + 4 – 1 = 7, akan tetapi tabel di atas hanya terisi 6 saja, artinya terjadi kemerosotan, sehingga untuk membantu dalam menentukan solusi optimal maka perlu mengalokasikan sebanyak 0 pada sel kosong yang biayanya terkecil. Permintaan dan Persediaan Tidak Seimbang Penggunaan metode penyelesaian masalah transportasi bisa digunakan jika banyaknya



x 1 +x 2≤3



permintaan = besarnya kapasitas/ suplai (



). Jika syarat ini tidak dipenuhi



maka diperlukan penambahan daerah asal atau daerah tujuan. Dummy ini hanya bersifat sementara, hanya ada dalam perhitungan. Contoh: Penyelesaian dengan NWC Asal/Tujua n W



X Y Permintaan



Dummy



A



B



C



4



8



8



0



72 16



4 24



16



0



8



82 16



24



0



72



16 102



41 41



20 20



Penyelesaian optimasi dengan metode MoDi Sel Basis/ Isi: 11, 12, 22, 32, 33, 34 11



x1 ,x2≥0



Z=3x1+2x2+0s1+0s2 = 4 2x 1+x 2+s1=5



12



x1+x2+s2=3



x1 ,x2 ,s1 ,s2≥0 = 8



22



s1



s2



32 Z 33



1 =[2 1 1 0 5] 2



34 [2 1 1 0 5]



[



1



x1



= 24



s1



x 1 = 16



s1



1 1 5 0 2 2 2



]



[ 1 1 0 1 3] − 1 1 1 0 5



[ ] 22 2



a b'2=b 2− 21 (b1 ) a 11



= 24 =0 [



0



1 1 1 - 1 2 2 2



]



x2 s2 b'1 =



b1 a11



[ 1 1 0 1 3 ]− 1 2



b'3 =b 3−



a 31 ( b1 ) a11



Sel non basis/ sel kosong: 13, 14, 21, 23, 24, 31



Kapasitas 76 82 77 215\ 235



[ 2 1 1 0 5]



3 2



13



[−3 -2 0 0 0]+



14



[−3 -2 0 0 0 ]+ 3 0



21



x1



x2



= 16 + 4 – 16 = 4



23



s1



s2



= 16 + 16 – 16 = 16



24



1 2



1 2



31



s2



1 2



[



3 3 15 22 2



[ ]



0 -



1 2



Asal/Tujua n W



X Y Permintaan



1 15 0 2 2



= 0 + 16 – 8 = 8



]



= 0 + (-8) – 0 = - 8



positif terbesar



5 2



= =



−



1 2



Dummy



A



B



C



4



8



8



0



72 16



4 24



16



0



8



41 16



41 24



0



72



57 102



41



20 20



Sel Basis/ Isi: 11, 12, 22, 23, 32, 34 11



1 2



Z



12



1 2



15 2



22



1 2



1 2



−



=4



s2



x2



=8



a22= = 24



b'1 =b1 −



1 2



1



23 [



1



1 1 5 0 2 2 2



2



]



= 16 [



1 2



32 [



0



1 1 1 - 1 2 2 2



]



[ 1 0 1 -1 2]



34 [



0



1 1 1 - 1 2 2 2



]



[



0 1 -1 2



1 2



]



= 16 =0



0



1 1 1 - 1 2 2 2



b'2 =



[



]



1 2



1



=



b2 a22



a b'3=b 3− 32 (b2 ) a 22



[



0 -



1 2



a12 ( b2 ) a22



1 2



5 2



0



]



1 1 2



1 2



0



15 2



]



Sel non basis/ sel kosong: 13, 14, 21, 24, 31, 33 13 14 [



−1 2 1 2



0-



1 1 15 0 2 2 2



]



21 [0 0 0 1 8]



[



0



1 1 1 1 2 2 2



[



0



1 1 1 1 2 2 2



] ]



=0+0–8=-8 = 0 + (-8) – 0 = - 8



x1



= 16 + 4 – 16 = 4



24



x2



s1



=



31



x2



Z



= 8 48  4



s2



Kapasitas 76 82 77 215\ 235



33 



u3  v3  c33 =



Asal/Tujua n W



X Y Permintaan



x1



B



C



4



8



8



0



72 16



4 24



16



0



8



21 16



41 24



20 0



72



77 102



41



20



Sel Basis/ Isi: 11, 12, 22, 23, 24, 32 11



x2



s1 = 4



s2



12



x2



Z



=8



x1



22



s1



s2



u  24  8  16 = 24  2



x2



u v v  16  16  0 23  2 3 = 16  3 u v v  0  16  16 24  2 4 = 0  4 32 



Dummy



A



u3  v2 = 16  u3  16  8  8



Sel non basis/ sel kosong: 13, 14, 21, 31, 33, 34 13 



u1  v3  c13 = 0 + 0 – 8 = - 8



14 



u1  v4  c14 = 0 + (-16) – 0 = - 16



21 



u2  v1  c21 = 16 + 4 – 16 = 4



31 



u3  v1  c31 = 8  4  8  4



33 



u3  v3  c33 = 8  0  24  16



34 



u3  v4  c34 = 8  ( 16)  0  8



Kapasitas 76 82 77 215\ 235



Asal/Tujua



Dummy



A



B



C



W



4



8



8



0



X



51 16



25 24



16



0



21 8



16



41 24



20 0



72



77 102



41



20



n



Y Permintaan



Sel Basis/ Isi: 11, 12, 21, 23, 24, 32 11 



u1  v1 = 4  v1  4



12 



u1  v2 = 8  v2  8



21 



u2  v1 = 16  u2  16  4  12



u v v  16  12  4 23  2 3 = 16  3 u v v  0  12  12 24  2 4 = 0  4 32 



u3  v2 = 16  u3  16  8  8



Sel non basis/ sel kosong: 13, 14, 22, 31, 33, 34 13 



u1  v3  c13 = 0 + 4 – 8 = - 4



14 



u1  v4  c14 = 0 + (-12) – 0 = - 12



22 



u2  v2  c22 = 12 + 8 – 24 = - 4



31 



u3  v1  c31 = 8  4  8  4



33 



u3  v3  c33 = 8  4  24  12



34 



u3  v4  c34 = 8  ( 12)  0  4



Kapasitas 76 82 77 215\ 235



Asal/Tujua



Dummy



A



B



C



4



8



8



0



X



16



76 24



16



0



Y



21 8



16



41 24



20 0



Permintaan



51 72



26 102



41



20



n W



Sel Basis/ Isi: 12, 21, 23, 24, 31, 32 12 



u1  v2 = 8  v2  8



21 



u2  v1 = 16  u2  16  0  16



u v v  16  16  0 23  2 3 = 16  3 u v v  0  16  16 24  2 4 = 0  4 31 



u3  v1 = 8  v1  8  8  0



32 



u3  v2 = 16  u3  16  8  8



Sel non basis/ sel kosong: 11, 13, 14, 22, 33, 34 11 



u1  v1  c11 = 0 + 0 – 4= - 4



13 



u1  v3  c13 = 0 + 0 – 8 = - 8



14 



u1  v4  c14 = 0 + (-16) – 0 = - 16



22 



u2  v2  c22 = 16 + 8 – 24 = 0



33 



u3  v3  c33 = 8  0  24  16



Kapasitas 76 82 77 215\ 235



34 



u3  v4  c34 = 8  ( 16)  0  8



Karena sel basis/ sel kosong sudah negatif semua atau sama dengan 0 maka tabel sudah optimal. Z = 2424 Solusi masalah transportasi dengan solver excel Seperti hal nya pada metode simpleks yang bisa diselesaikan dengan solver excel maka masalah transportasi juga bisa diselesaikan dengan solver excel. Contoh: Seorang pedagang beras mempunyai dua gudang di Kudus dan Semarang, yang masingmasing menyiapkan beras sebanyak 120, 140 ton. Pedagang tersebut mempunyai daerah pemasaran di Jepara, Pati, Purwodadi, Blora dan Kendal



yang masing-masing



membutuhkan beras sebanyak 40, 60, 80, 40 dan 25 ton. Ongkos angkut tiap ton beras dari Kudus ke Jepara, Pati, Purwodadi, Blora dan Kendal masing-masing Rp 50.000, Rp 45.000, Rp 65.000 , Rp 75.000 dan Rp 60.000, ongkos angkut dari Semarang ke Jepara, Pati, Purwodadi, Blora dan Kendal masing-masing Rp 60.000, Rp 55.000, Rp 70.000, Rp 85.000 dan Rp 45.000. Bagaimana pedagang tersebut mendistribusikan beras dagangannya untuk memenuhi permintaan masing-masing daerah dengan batasan kapasitas gudang, agar biaya minimum pengiriman tercapai ? Dalam linear programming, masalah



tersebut dapat diformulasikan dalam model



matematik yang meliputi tiga tahap : 1. Variabel keputusan, yaitu variable yang menguraikan secara lengkap keputusan yang akan di buat. Variabel keputusan dalam masalah ini adalah banyaknya barang yang akan dikirimkan dari masing-masing gudang ke masing-masing daerah. Variabel keputusan masalah tersebut dapat dilambangkan sebagai berikut :



x1A = jumlah barang yang dikirimkan dari pabrik Kudus ke daerah Jepara x1B = jumlah barang yang dikirimkan dari pabrik Kudus ke daerah Pati x1C = jumlah barang yang dikirimkan dari pabrik Kudus ke daerah Purwodadi x1D = jumlah barang yang dikirimkan dari pabrik Kudus ke daerah Blora



x1E = jumlah barang yang dikirimkan dari pabrik Kudus ke daerah Kendal x2 A = jumlah barang yang dikirimkan dari pabrik Semarang ke daerah Jepara x2 B = jumlah barang yang dikirimkan dari pabrik Semarang ke daerah Pati x2C = jumlah barang yang dikirimkan dari pabrik Semarang ke daerah Purwodadi x2D = jumlah barang yang dikirimkan dari pabrik Semarang ke daerah Blora x2E = jumlah barang yang dikirimkan dari pabrik Semarang ke daerah Kendal



2.



Fungsi tujuan: yaitu fungsi dari variable keputusan yang akan dioptimumkan.



Tujuan dari masalah tersebut di atas adalah meminimumkan biaya trasportasi total. Biaya transport adalah sejumlah biaya dari masing-masing gudang ke masing-masing daerah. Misalkan biaya dari Kudus ke daerah Jepara adalah perkalian antara banyaknya beras yang dikirim dari Kudus ke Jepara dengan biaya tranport per ton dalam hal ini (Rp.50.000). Dengan cara serupa juga dapat dihitung untuk pabrik dan daerah lainnya. Sehingga total biaya transport ( Z ) dapat ditulis : Z  50.000 x1 A  45.000 x1B  65.000 x1C  75.000 x1D  60.000 x1E  60.000 x2 A  55.000 x2 B  70.000 x2C  85.000 x2 D  45.000 x2 E 3.



Kendala adalah pembatasan-pembatasan yang harus dipenuhi yang mencerminkan



keterbatasan sumberdaya masalah itu Dalam masalah ini ada dua kendala yaitu kendala permintaan dan kendala kapasitas gudang. Total barang yang diterima di masing-masing daerah harus lebih besar atau sama dengan permintaan daerah tersebut, serta total barang yang dikirimkan dari masingmasing pabrik harus lebih kecil atau sama dengan kapasitas produksi gudang tersebut. Kendala permintaan: Daerah A:



x1 A  x2 A  40



Daerah B:



x1B  x2 B  60



Daerah C:



x1C  x2C  80



Daerah D:



x1D  x2 D  40



Daerah E:



x1E  x2 E  25



Kendala kapasitas produksi: Gudang 1:



x1 A  x1B  x1C  x1D  x1E  120



Gudang 2:



x2 A  x2 B  x2C  x2 D  x2 E  140



Kendala non negative



x1 A , x1B , x1C , x1D , x1E , x2 A , x2 B , x2C , x2 D , x2 E  0 Setelah merumuskan model linear programming tersebut, langkah selanjutnya adalah masuk ke aplikasinya dalam Solver Excel untuk mencari nilai optimalnya.



Keterangan: 7. Nilai keputusan awal pada sel B12:F13 ditentukan sembarang, dalam hal ini di pilih



x1 A  x1B  x1C  x1D  x1E  x2 A  x2 B  x2C  x2 D  x2 E  1 , nilai-nilai optimum akan dicari oleh komputer. 8. Kendala permintaan: (sel B14:F14) Sel B14 adalah formula dari: SUM(B12:B13), dengan cara yang sama sampai sel F14 9. Kendala kapasitas produksi (sel G12) G12=SUM(B12:F12), dengan cara yang sama untuk sel F13 10. Sel D18 adalah formula dari D18=SUMPRODUCT(B12:F13,B4:F5) 11. Pilih menu “data” kemudian “solver”.



Set Target Sel: $D$18 (karena D18 mengandung formula target keuntungan) Equal to: Min By Changing Sell: $B$12:$F$13 (karena sel B12 sampai F13 adalah adalah sel yang berisi nilai-nilai optimum dari variabel keputusan yang akan diganti oleh komputer) Subject to the Constraints: Diisi dengan jalan memilih Add, sebagai berikut: Add Constraint Cell Reference:



Constraint:



$B$14:$F$14



>= $B$16:F16



(Add)



$G$12:$G$13