Riset Operasi Nina A [PDF]

Citation preview

RISET OPERASI RINGKASAN BUKU RISET OPERASI HAMDY A. TAHA



DISUSUN OLEH:



NINA AGUSTINA



1834021362



PROGRAM STUDI MANAJEMEN FAKULTAS EKONOMI UNIVERSITAS KRISNA DWIPAYANA



DAFTAR ISI contents DAFTAR ISI .................................................................................................................. i KATA PENGANTAR .................................................................................................. v BAB II ........................................................................................................................... 1 PEMBAHASAN ........................................................................................................... 1 I.



PENGAMBILAN KEPUTUSAN DALAM RISET OPERASI ........................ 1 JENIS JENIS MODEL OR ............................................................................ 1 UNSUR-UNSUR DARI SEBUAH MODEL KEPUTUSAN ........................ 2 SENI PERMODELAN ................................................................................... 2 JENIS-JENIS MODEL OR ............................................................................ 3 PENGARUH KETERSEDIAAN DATA TERHADAP PEMODELAN ....... 3 PERHITUNGAN DALAM OR ..................................................................... 5 TAHAP-TAHAP STUDI OR ......................................................................... 7



II. PEMROGRAMAN MATEMATIS ................................................................. 11 MODEL DUA VARIABLE DAN PEMECAHAN GRAFIKNYA ............. 12 PEMECAHAN GRAFIK DARI MODEL LP .............................................. 16 ANALISIS SENSITIVITAS ........................................................................ 16 FORMULASI LP ......................................................................................... 17 III. PEMROGRAMAN LINIER: METODE SIMPLEKS ..................................... 18 . GAGASAN KESELURUHAN TENTANG METODE SIMPLEKS ........ 18 PENGEMBANGAN METODE SIMPLEKS .............................................. 19 . BENTUK LP STANDAR .......................................................................... 20 METODE SIMPELKS PRIMAL ................................................................. 22



i



METODE SIMPELKS DUAL ..................................................................... 28 KASUS KHUSUS DALAM APLIKASI METODE SIMPLEKS ............... 33 DEGENERASI ............................................................................................. 34 INTERPRETASI TABEL SIMPLEKS: ANALISIS SENSITIVITAS ........ 35 IV. PEMROGRAMAN LINIER: METODE SIMPLEKS YANG DIREVISI ...... 39 DASAR MATEMATIS ................................................................................ 39 MODEL LP STANDAR DALAM BENTUK MATRIKS .......................... 40 PEMECAHAN DASAR DAN BASIS ......................................................... 42 METODE SIMPLEKS (PRIMAL) YANG DIREVISI ................................ 43 BENTUK HASIL PERKALIAN DARI INVERSI ...................................... 43 V. PEMROGRAMAN LINIER: DUALITAS DEFINISI MASALAH DUAL ... 44 HUBUNGAN ANTARA NILAI TUJUAN PRIMAL DAN DUAL ........... 45 INTERPRETASI EKONOMI DARI MASALAH DUAL .......................... 46 HARGA DUAL ............................................................................................ 47 NILAI SLACK KOMPLEMENTER ........................................................... 49 ANALISIS PASCA-OPTIMAL ATAU ANALISIS SENSITIVITAS ........ 49 PEMROGRAMAN LINIER PARAMETRIK ............................................. 51 VI. PEMROGRAMAN LINIER: MODEL TRANSPORTASI ............................. 53 DEFINISI DAN APLIKASI MODEL TRANSPORTASIA........................ 53 PEMECAHAN MASALAH TRANSPORTASI .......................................... 55 PEMECAHAN AWAL DIPERBAIKI......................................................... 60 MODEL TRANSSHIPMENT ...................................................................... 62 VII. PEMROGRAMAN LINIER ............................................................................ 63 METODE SIMPLEKS PRIMAL VARIABEL YANG DIBATASI ........... 63



ii



ALGORITMA DEKOMPOSISI .................................................................. 64 ALGORITMA TITIK INTERIOR KARMARKAR .................................... 65 ALGORITMA TITIK INTERIOR ............................................................... 66 VIII. .......................................................................................... MODEL JARINGAN 67 DEFINISI JARINGAN ................................................................................ 67 MASALAH POHON PERENTANGAN MINIMAL .................................. 68 MASALAH RUTE TERDEKAT ................................................................. 69 MASALAH ARUS MAKSIMAL ................................................................ 76 IX. PEMROGRAMAN LINIER INTEGER .......................................................... 80 APLIKASI ILUSTRATIF PEMROGRAMAN ........................................... 81 METODE PEMECAHAN PEMROGRAMAN INTEGER ......................... 84 ALGORITMA BIDANG PEMOTONG ...................................................... 86 PERHITUNGAN METODE PEMOTONGAN ........................................... 89 MASALAH INTEGER NOL-SATU ........................................................... 90 ALGORITMA ADITIF ................................................................................ 91 X. PEMROGRAMAN DINAMIS ........................................................................ 94 UNSUR-UNSUR MODEL DP: CONTOH PENGANGGARAN MODAL 95 LEBIH LANJUT TENTANG DEFINISI KEADAAN ................................ 97 CONTOH-CONTOH MODEL DAN PENGHITUNGAN DP .................... 98 MASALAH DIMENSIONALITAS DALAM ............................................. 98 DAFTAR PUSTAKA ............................................................................................... 100



iii



iv



KATA PENGANTAR



Puji syukur kehadirat Tuhan Yang Maha Esa atas segala rahmatNYA sehingga makalah ini dapat tersusun hingga selesai . Tidak lupa kami juga mengucapkan banyak terimakasih atas bantuan dari pihak yang telah berkontribusi dengan memberikan sumbangan baik materi maupun pikirannya. Dan harapan kami semoga makalah ini dapat menambah pengetahuan dan pengalaman bagi para pembaca, Untuk ke depannya dapat memperbaiki bentuk maupun menambah isi makalah agar menjadi lebih baik lagi. Karena keterbatasan pengetahuan maupun pengalaman kami, Kami yakin masih banyak kekurangan dalam makalah ini, Oleh karena itu kami sangat mengharapkan saran dan kritik yang membangun dari pembaca demi kesempurnaan makalah ini.



v



BAB II PEMBAHASAN



I.



PENGAMBILAN KEPUTUSAN DALAM RISET OPERASI



JENIS JENIS MODEL OR Tahap pengembangan model adalah tahap pertama, dengan diikuti oleh pemecahan model untuk memperoleh pemecahan yang diinginkan. Metode pemecahan biasanya dirancang untuk mertanfaatkain struktur khusus dan model yang dihasilkan Dengan demikian, berbagai model yang berkaitan dengan sistem nyata yang ada menimbulkan berbagai teknik pemecahan dalam junlah yang sama. Inilah asal dari berbagai nama yang sudah loita kenal seperti pemrograman linier, integer, dinamis, dan online yang mewakili berbagai algoritma untuk mencerahkan kelompok kelompok model OR tertentu. Dalam kebanyakan aplikasi OR, diasumsikan bahwa tujuan dan bisan sebuah modem dapat diekspresikan secara kuantitatif atau secara matematis sebagai fungsi dari variabel keputusan. Dalam kasus demikian, kita mengatakan bahwa kita memang model matematis. Sayangnya, walaupun terdapat kemajuan yang mengesankan dalam pemodelan matematis sejumlah situasi nyata masih berada jauh di luar kemampuan teknik-teknik matematis yang sekarang tersedia. Karena satu hal, sistem nyata kemungkinan terlalu rumit untuk memungkinkan representasi matematis yang memadai." Kemungkinan lain, sekalipun sebuah model matematis dapat diformulasikan, model itu kemungkinan terbukti terlalu kompleks untuk dipecahkan dengan metode-metode pemecahan yang ada. Sebuah pendekatan yang berbeda untuk pemodelan sistem (yang kompleks) adalah penggunaan simulasi. Model-model simulasi berbeda dengan model matematis dalam hal bahwa hubungan antara masukan dan keluaran tidak dinyatakan secara eksplisit. Melainkan, sebuah model simulasi memecahkan sistem yang dimodel tersebut ke dalam modul-modul dasar atau elementer yang lalu dikaitkan satu sama lain dengan hubungan-hubungan logis yang didefinisikan dengan baik dalam bentuk JIKA/MAKA). Jadi dengan dimulai dari modul masukan, perhitungan akan bergerak dari satu modul ke modul lainnya sampai sebuah hasil keluaran direalisasikan.



1



Model simulasi, ketika dibandingkan dengan model matematis, memang menawarkan keluwesan yang lebih besar dalam mewakili sistem yang kompleks. Alasan utama untuk keluwesan ini adalah bahwa simulasi memandang sistem dari tingkat elementer yang mendasar. Pemodelan matematis, sebaliknya, cenderung mempertimbangkan sistem dari tingkat representasi yang kurang terinci. Keluwesan simulasi bukannya tidak memiliki kekurangan. Pengembangan sebuah model simulasi biasanya cukup mahal baik dalam hal waktu maupun sumber daya. Selain itu, pelaksanaan sebuah model simulasi, sekalipun dengan komputer yang tercepat, dapat menimbulkan sejumlah biaya yang cukup besar. Sebaliknya, modelmodel matematis yang berhasil biasanya dapat dikelola dalam hal perhitungannya.



Riset Operasi sebagai sebuah teknik pemecahan masalah, OR dirancang sebagai ilmu dan seni. Aspek ilmu terletak dalam penyediaan teknik-teknik matematis dan logaritma untuk memecahkan masalah keputusan yang tepat. Riset Operasi adalah sebuah seni karena keberhasilan dalam semua tahap yang mendahului dan melanjuti pemecahan dari sebuah model matematis sebagian besar bergantung pada kreativitas dan kemampuan pribadi dari mereka yang menganalisis pengambilan keputusan tersebut. UNSUR-UNSUR DARI SEBUAH MODEL KEPUTUSAN Sebuah keputusan dicapai dengan memilih alternatif yang dinilai “terbaik “ diantara semua pilihan tersedia. Keputusan yang di dasari oleh kedua alternative pertama hanya akan menghasikan apa yang disebut sebagai pemecahan suboptimal. Hal ini menujukan pentingnya kemampuan mengenali semua alternative yang layak dari sebuah masalah keputusan yang bersangkutan. Pada intinya,”kualitas” dari pemecahan yang optimal adalah fungsi sekelompok alternative layak yang kita definiskan untuk permasalahan tersebut. SENI PERMODELAN Sistem dunia nyata



Sistem dunia nyata yang diasumsikan



Model bdh



2



Model didefiniskan sebagai sebuah fungsi tujuan dengan



batasan-batasan yang



diekspresikan dalam bentuk variable keputusan (alternative) dari permasalahan tersebut. Sistem dunia nyata yang di asumsikan adalah sistem yang di abstraksi dari situasi nyata dengan memusatkan perhatian identfikasi factor-faktor yang dominan (variable, batasan, dan parameter) yang mengendalikan perilaku sistem nyata tersebut . Model yang merupakan sebuah abstraksi dari sistem nyata yang diasumsikan, lalau mengidentifikasi hubungan sesuai



dengan sistem tersebut dalam bentuk tujuan



sekelompok batasan. Jenis-jenis Model OR Dalam kebanyakan aplikasi OR, diasumsikan bahwa tujuan dan batasan sebuah model dapat di ekspresikan secara kuantitatif atau matematis sebagai fungsi dari variable keputusan. Sayangnya, walaupun terdapat kemajuan yang mengesankan dalam permodelan matematis, sejumlah situasi nyata diluar kemampuan tenik-teknik sistematis yang tersedia sekalipun sebuah model matematis dapat diformulasikan, model itu kemungkinan terbukti terlalu kompleks untuk dipecahkan dengan metodemetode pemecahan yang ada. Permodel sistem (yang kompleks) adalah penggunaan simulasi. Model simulasi ketika dibandingkan dengan model sistematis, memang menawarkan keluwesan yang lebih besar dalam mewakili sistem yang kompleks. PENGARUH KETERSEDIAAN DATA TERHADAP PEMODELAN Model berjenis apapun, tanpa bergantung pada kecanggihan dan akurasinya, dapat terbukti hanya memiliki sedikit nilai praktis jika tidak didukung oleh data yang andal.



3



Walaupun sebuah model didefinisikan dengan baik, mutu pemecahan model tersebut jelas bergantung pada seberapa baik kita dapat mengestimasi data. Jika estimasi tersebut terdistorsi, pemecahan yang diperoleh, walaupun optimum dalam arti matematis, pada kenyataannya dapat bermutu rendah dari sudut pandang sistem nyata. Dalam beberapa situasi, data tidak dapat diketahui dengan pasti. Sebaliknya, data diestimasi berdasarkan distribusi probabilitas. Dalam situasi seperti ini, struktur model kemungkinan perlu diubah untuk mengakomodasi sifat probabilistik dari permintaan. Hal ini menimbulkan model pro babilistik atau stokastik, sebagaimana dipertentangkan dengan model deterministik. Kadang-kadang sebuah model dikembangkan dengan asumsi bahwa data tertentu dapat diperoleh, tetapi pencarian kemudian membuktikan bahwa informasi seperti itu sulit diperoleh. Dalam kasus ini, model tersebut perlu disusun ulang untuk mencerminkan kurangnya data. Jadi derajat ketersediaan data dapat pula mempengaruhi akurasi model. Sebagai ilustrasi, pertimbangkan sebuah model sediaan di mana tingkat sediaan untuk satu barang tertentu ditentukan sedemikian rupa sehingga biaya total untuk penyimpanan sediaan yang berlebih dan tidak memenuhi semua permintaan diminimumkan. Model ini memerlukan estimasi tentang biaya penyimpanan per unit barang yang berlebih dalam sediaan dan biaya kehabisan sediaan barang per unit permintaan yang tidak terpenuhi. Biaya penyimpanan, yang bergantung pada biaya penyimpanan dan biaya modal, relatif sederhana untuk diestimasi. Tetapi jika biaya kehabisan sediaan tersebut memperhitungkan kerugian akibat berkurangnya kepercayaan pelanggan, faktor yang tidak berwujud seperti itu akan sulit dikuantifikasi. Dalam kondisi seperti ini, model tersebut kemungkinan harus diubah sehingga biaya kehabisan sediaan tidak dinyatakan secara eksplisit. Misalnya, kita dapat menyatakan batas atas jumlah kekurangan yang dapat diterima setiap waktu. Pada intinya, batas atas yang dinyatakan itu menyiratkan estimasi tertentu dari biaya kehabisan sediaan. Tetapi menentukan batas seperti itu jauh lebih sederhana daripada mengestimasi biaya kehabisan sediaan.



4



Pengumpulan data pada kenyataannya dapat merupakan bagian paling sulit dari pembuatan sebuah model. Sayangnya, tidak ada peraturan yang dapat disarankan untuk prosedur ini. Sementara pengalaman pemodelan dalam sebuah organisasi bertambah, mereka yang melakukan analisis OR juga dapat mengembangkan alat-alat untuk pengumpulan dan dokumentasi data dengan cara yang berguna untuk proyek-proyek saat ini dan di masa mendatang. PERHITUNGAN DALAM OR



Dalam OR terdapat dua jenis perhitungan yang berbeda: yang melibatkan simulasi dan yang berkaitan dengan model matematis. Dalam model simulasi, perhitungan umumnya sangat banyak dan kebanyakan sangat memakan waktu. Tetapi, dalam simulasi kita dapat selalu yakin bahwa hasil yang diinginkan akan diperoleh dengan pasti. Masalahnya semata-mata adalah menyediakan waktu komputer yang cukup!



Perhitungan dalam model-model OR matematis, sebaliknya, umumnya bersifat iteratif. Yang kami maksudkan dengan istilah ini adalah bahwa pemecahan yang optimal dari sebuah model matematis biasanya tidak tersedia dalam bentuk tertutup. Melainkan, jawaban akhir dicapai dalam langkah-langkah atau iterasi, dengan setiap iterasi baru membawa pemecahan tersebut lebih dekat dengan pemecahan optimal. Dalam hal ini, kita mengatakan bahwa pemecahan menyatu secara iteratif ke pemecahan optimal.



5



Sayangnya, tidak semua model OR matematis memiliki algoritma (metode) pemecahan yang selalu menyatu ke pemecahan optimal. Terdapat dua alasan untuk kesulitan ini: Algoritma pemecahan dapat terbukti menyatu ke pemecahan optimal, tetapi hanya dalam arti teoritis. Konvergensi teoritis menyatakan bahwa terdapat sejumlah batas atas tertentu dalam jumlah iterasi, tetapi tidak mengatakan berapa tinggi batas atas tersebut. Jadi kita dapat menghabiskan waktu komputer berjam-jam tanpa mencapai iterasi terakhir. Yang lebih buruk lagi, jika iterasi tersebut dihentikan sebelum mencapai pemecahan optimal, kita biasanya tidak dapat mengukur kualitas Pemecahan yang diperoleh secara relatif terhadap pemecahan optimal yang sebenarnya. (Perhatikan perbedaan antara situasi ini dengan simulasi. Dalam simulasi, kita memiliki pengendalian atas waktu perhitungan semata-mata dengan mengurangi periode observasi dari model tersebut. Dalam model model matematis, jumlah iterasi adalah fungsi dari efisiensi algoritma pemecahan dan struktur spesifik dari model yang bersangkutan, yang keduanya kemungkinan tidak dapat dikendalikan oleh pengguna.) Kompleksitas model mate natis dapat membuat perancangan algoritma pemecahan tidak mungkin dilakukan. Dalam kasus ini, model tersebut tetap tidak dapat dipecahkan secara perhitungan. Kesulitan yang jelas dalam perhitungan model matematis telah memaksa para praktisi untuk mencari metode-metode perhitungan alternatif. Metode-metode ini juga bersifat iteratif, tetapi tidak menjamin optimalisasi. Sebaliknya, mereka semata-mata mencari pemecahan yang baik untuk sebuah masalah. Metode-metode ini biasanya dikenal sebagai heuristik, karena logika metode ini didasari oleh peraturan-peraturan umum yang mendukung pemerolehan pemecahan yang baik. Keuntungan dari heuristik adalah bahwa metode ini umumnya melibatkan lebih sedikit perhitungan ketika dibandingkan dengan algoritma yang pasti. Juga, karena didasari oleh peraturanperaturan umum, metode-metode ini lebih mudah diterangken kepada para pengguna yang tidak berorientasi pada matematika. Dalam OR, heuristik dipergunakan untuk dua maksud yang berbeda: Heuristik dapat dipergunakan dalam konteks algoritma optimisasi yang pasti untuk mempercepat proses untuk mencapai pemecahan optimal. Kebutuhan untuk memperbaiki algoritma optimasasi tersebut menjadi lebih jelas dalam model-model berskala besar.



6



1. Heuristik semata-mata dipergunakan untuk menemukan satu pemecahan yang baik untuk sebuah masalah. Pemecahan yang dihasilkan tidak dijamin sebagai pemecahan optimal, dan pada kenyataanya akan sulit diukur. Tahap-tahap studi OR Sebuah studi OR tidak dapat dilakukan dan dikendalikan oleh seorang analis OR saja. Walaupun ia adalah seorang ahli pemodelan dan teknik-teknik pemecahan model, analis tersebut tidak mungkin merupakan ahli dalam semua bidang di mana masalah OR timbul. Konsekuensinya, sebuah kelompok OR harus mencakup para anggota organisasi yang secara langsung bertanggung jawab atas fungsi-fungsi di mana masalah tersebut berada serta atas pelaksanaan dan implementasi pemecahan yang direkomendasikan. Dengan kata lain, seorang analis OR melakukan sebuah kesalahan besar dengan tidak mengusahakan kerja sama dari mereka yang akan melaksanakan pemecahan yang direkomendasikan.Tahap-tahap utama yang harus dilalui oleh sebuah kelompok OR untuk melakukan sebuah studi OR mencakup 1. Definisi masalah, sebagai sudut pandang riset operasi dan aspek utama 2. Pengembangan model, yang bergantung pada definisi maslah 3. Pemecahan model, yaitu teknik-teknik optimisasi untuk menghasilkan pemecahan optimal 4. Pengujian keabsahan model, sebagai metode umum menguji keabsahan model 5. Implementasi hasil akhir, yaitu hasil model yang telah diuji Walaupun sama sekali bukan merupakan standar, urutan ini umumnya dapat diterima. Kecuali untuk tahap pemecahan model," yang umumnya didasari oleh teknik yang telah dikembangkan dengan baik, tahap-tahap lainnya tampaknya tidak mengikuti peraturan-peraturan yang tetap. Hal ini berakar dari fakta bahwa prosedur untuk tahap-



7



tahap ini bergantung pada jenis masalah yang sedang diteliti dan lingkungan operasi di mana masalah itu terdapat. Dalam hal ini, sebuah kelompok riset operasi terutama akan dituntun dalam studi tersebut oleh pengalaman professional para anggotanya, daripada oleh beberapa peraturan yang pasti. Walaupun terdapat kesulitan yang jelas dalam menetapkan peraturan yang tetap untuk pelaksanaan tahap-tahap ini, tampaknya penetapan beberapa petunjuk umum merupakan hal yang diinginkan. Sisa bagian ini ditujukan untuk memberikan orientasi tentang butir-butir utama yang terlibat dalam sebuah studi riset operasi. Tahap pertama dari studi ini berkaitan dengan definisi masalah. Dari sudut pandang riset operasi, hal ini menunjukkan tiga aspek utama: (1) deskripsi tentang sasaran atau tujuan dari studi tersebut, (2) identifikasi alternatif keputusan dari sistem tersebut, dan (3) pengenalan tentang keterbatasan, batasan, dan persyaratan sistem tersebut. Tahap kedua dari studi ini berkaitan dengan pengembangan model. Bergantung pada definisi masalah, kelompok riset operasi tersebut harus memutuskan model yang paling sesuai untuk mewakili sistem yang bersangkutan. Model seperti ini harus menyatakan ekspresi kuantitatif dari tujuan dan batasan masalah dalam bentuk variabel keputusan. Jika model yang dihasilkan termasuk dalam model matematis vang umum (misalnya, pemrograman linier), pemecahan yang dalam salah satu vang umum pemrogra memudahkan dapat diperoleh dengan menggunakan teknik-teknik matematis, Jika hubungan matematis dalam model tersebut terlalu kompleks untuk memungkinkan pemevahan analisis model simulasi kemungkinan lebih sesuai. Beberapa kasus memerlukan penggunaan kombinasi antara model matematis, simulasi dan heuristik. Hal ini tentu saja sebagian besar bergantung pada sifat dan kompleksitas sistem yang sedang ditentu. Tahap ketiga dari studi ini berkaitan dengan pemecahan model. Dalam modelmodel matematis hal ini dicapai dengan menggunakan teknik-teknik optimisasi yang didefinisikan dengan baik dan model tersebut dikatakan menghasilkan sebuah



8



pemecahan optimal. Jika simulasi atau model heuristik dipergunakan, konsep optimalitas tidak didefinisikan dengan begitu baik, dan pemecahan dalam kasus ini dipergunakan untuk memperoleh evaluasi terhadap tindakan dalam sistem tersebut. Di samping pemecahan (optimal) dari model tersebut, kita harus juga memperoleh, ketika mungkin, informasi tambahan yang berkaitan dengan perilaku pemecahan tersebut yang disebabkan oleh perubahan dalam parameter sistem tersebut. Hal ini biasanya disebut sebagai analisis sensitivitas. Secara khusus, analisis seperti ini diperlukan ketika parameter dari sebuah sistem tidak dapat diestimasi secara akurat. Dalam kasus ini, adalah penting untuk mempelajari perilaku pemecahan yang optimal di sekitar estimasi ini. Tahap keempat menuntut pemerkosaan terhadap keabsahan model. Sebuah model adalah absah jika, walaupun tidak secara pasti mewakili sistem tersebut, dapat memberikan prediksi yang wajar dari kinerja sistem tersebut. Satu metode yang umum untuk menguji keabsahan sebuah model adalah membandingkan kinerjanya dengan data masa lalu yang tersedia untuk sistem actual tersebut. Model tersebut akan absah jika dalam kondisi masukan yang serupa, model tersebut dapat menghasilkan ulang kinerja masa lalu dari sistem tersebut. Masalahnya di sini adalah bahwa tidak ada jaminan bahwa kinerja masa mendatang akan terus serupa dengan perilaku masa lalu. Juga, karena model tersebut didasari oleh penelitian yang hati-hati terhadap data masa lalu, perbandingan itu akan selalu menunjukkan hasil yang menguntungkan. Dalam beberapa situasi, masalah ini dapat diatasi dengan menggunakan data dari penggunaan percobaan dari sistem tersebut. Harus dicatat bahwa metode pengujian keabsahan seperti ini tidak sesuai untuk sistem yang belum ada, karena data tidak tersedia untuk perbandingan. Dalam beberapa kasus, jika sistem semula diinvestigasi oleh sebuah model matematis, adalah layak untuk mengembangkan sebuah model simulasi yang darinya data dapat diperoleh untuk melakukan perbandingan



9



Tahap akhir dari studi ini berkaitan dengan implementasi hasil model yang telah diuji tersebut. Beban pelaksanaan hasil ini terutama berada di pundak para peneliti operasi. Implementasi melibatkan penerjemahan hal ini menjadi petunjuk operasi yang terinci dan disebarkan dalam bentuk yang mudah dipahami kepada para individu yang akan mengatur dan mengoperasikan sistem yang direkomendasikan tersebut. Interaksi antara kelompok riset operasi dan para tenaga operasi akan mencapai puncaknya dalam tahap ini. Komunikasi di antara kedua kelompok dapat diperbaiki dengan mengusahakan partisipasi para tenaga operasi dalam pengembangan rencana implementasi. Pada kenyataannya, partisipasi ini harus diusahakan di keseluruhan tahap-tahap dalam studi ini. Dengan cara ini, tidak satu pun pertimbagan praktis yang akan mengarah pada kegagalan sistem tersebut terabaikan. Sementara itu, modifikasi atau penyesuaian yang mungkin terhadap sistem tersebut dapat diuji untuk melihat kelayakannya oleh para tenaga operasi. Dengan kata lain, merupakan sebuah ke atasan bahwa tahap implementasi tersebut dilakukan melalui kerja sama antara kelompok riset operasi tersebut dengan mereka yang bertanggung jawab untuk mengelola dan mengoperasikan sistem yang bersangkutan. Pada intinya, topik-topik dalam buku ini dikelompokkan sesuai dengan modelmodel matematis yang sudah dikenal luas dalam OR (misalnya, pemrograman linier, pemrograman integer, sediaan, dan teori antrian). Terdapat dua alasan untuk hal ini. Pertama, seperti yang dapat diperkirakan, tidak terdapat peraturan pasti yang dapat disarankan untuk aspek seni dari OR. Keragaman situasi di mana OR dapat diterapkan membuat usaha ke arah ini hampir sia-sia. Kedua, kami percaya bahwa adalah sangat penting bagi seorang praktisi OR untuk memiliki pemahaman yang memadai tentang kemampuan dan batasan teknik-teknik OR matematis. Pandangan bahwa seorang pengguna OR tidak perlu mempelajari aspek matematis dari OR karena komputer dapat "menangani" pemecahan masalah tersebut merupakan pandangan yang berbahaya. Kita harus mengingat bahwa komputer memecahkan model sebagaimana diajukan oleh pengguna. Jika pengguna tersebut tidak menyadari keterbatasan model yang dipergunakan, kualitas pemecahan akan mencerminkan kekuruangan ini.



10



Kami harus menyatakan bahwa buku ini tidak mengabaikan aspek seni dari OR. Banyak contoh yang disajikan di sepanjang buku ini akan memberikan gagasan tentang seni pemodelan OR. Kami juga menekankan topik-topik yang paling berguna dalam analisis masalah-masalah praktis. Satu contoh adalah topik analisis sensitivitas, yang memainkan peran penting dalam studi masalah-masalah GR. Kami percaya bahwa kuliah pertama dalam OR harus memberikan dasar yang baik kepada para mahasiswa tentang aspek matematika dari OR, dengan dilipatgandakan dengan contoh-contoh aplikasi dan kasus kecil yang bermakna. Skema seperti ini akan memberikan jenis keyakinan diri kepada para pengguna OR yang umumnya tidak terdapat jika mereka mengarahkan pendidikan utama mereka ke arah aspek filosofi dan artistik dari pengambilan keputusan. Setelah pengetahuan mendasar tentang dasar-dasar matematis dari OR diperoleh, para mahasiswa dapat mneningkatkan



kemampuan



mereka



sebagai



pengambil



keputusan



dengan



mempelajari studi kasus yang dilaporkan dan benar-benar mengerjakan masalahmasalah dunia nyata.



II.



PEMROGRAMAN MATEMATIS



Keberhasilan sebuah teknik OR pada akhirnya diukur berdasarkan penyebaran penggunaannya sebagai sebuah alat pengambilan keputusan. Sejak diperkenalkan di akhir dasawarsa 1940-an, pemrograman linier (linear programming/LP) telah terbukti merupakan salah satu alat riset operasi yang paling efektif. Keberhasilannya berakar dari keluwesannya dalam menjabarkan berbagai situasi kehidupan nyata di bidangbidang berikut ini: militer, industri, pertanian, transportasi, ekonomi, kesehatan, dan bahkan ilmu sosial dan perilaku. Di samping itu, tersedianya program komputer yang sangat efisien untuk memecahkan masalah-masalah LP yang sangat luas merupakan faktor penting dalam tersebarnya penggunaan teknik ini.



11



Kegunaan LP adalah lebih luas daripada aplikasinya semata-mata. Pada kenyataannya, LP harus dipandang sebagai dasar penting untuk pengembangan teknikteknik OR lainnya, termasuk pemrograman integer, stokastik, arus jaringan, dan kuadratik. Dalam hal ini, pemahaman akan LP adalah penting untuk implementasi teknik-teknik tambahan ini. Keberhasilan sebuah teknik OR pada akhirnya diukur berdasarkan penyebaran penggunaannya sebagai sebuah alat pengambilan keputusan. Sejak diperkenalkan di akhir dasawarsa 1940-an, pemrograman linier (linear programming/LP) telah terbukti merupakan salah satu alat riset operasi yang paling efektif. Keberhasilannya berakar dari keluwesannya dalam menjabarkan berbagai situasi kehidupan nyata di bidangbidang berikut ini: militer, industri, pertanian, transportasi, ekonomi, kesehatan, dan bahkan ilmu sosial dan perilaku. Di samping itu, tersedianya program komputer yang sangat efisien untuk memecahkan masalah-masalah LP yang sangat luas merupa kan faktor penting dalam tersebarnya penggunaan teknik ini. Kegunaan LP adalah lebih luas daripada aplikasinya semata-mata. Pada kenyataannya, LP harus dipandang sebagai dasar penting untuk pengembangan teknik-teknik OR lainnya, termasuk pemrograman integer, stokastik, arus jaringan, dan kuadratik. Dalam hal ini, pemahaman akan LP adalah penting untuk implementasi teknik-teknik tambahan ini.



Model Dua Variable dan Pemecahan Grafiknya Prosedur menawarkan peluang yang luar biasa untuk memahmi bagaimana proses opmisasi LP bekerja.



Pemecahan ini juga memungkin kami untuk



memperkenalkan konsep analisis sensitivitas dengan cara yang logis dan mudah dipahami. Contoh:



12



Reddy Mikks Company memiliki sebuah pabrik kecil yang menghasilkan cat, baik untuk interior maupun eksterior untuk didistribusikan kepada para grosir. Dengan dua bahan mentah A dan B, dipergunkan untuk membuat cat tersebut. Ketersediaan A maksimum adalah 6 ton sehari dan B 8 ton satu hari. Kebutuhan harian akan bahan mentah per ton cat interior diringkas dalam tabel berikut.



Ton Bahan Mentah perton cat Eksterior



Interior



Ketersediaan maksimum (ton)



Bahan Mentah A



1



2



6



Bahan Mentah B



2



1



8



Dengan permintaan harian cat interior tidak lebih tinggi dibandingkan permintaan akan cat eksterior dan permintaan maksimum cat interior terbatas 2 ton per hari. Harga grosir per ton adalah $3000 untuk cat eksterior dan $2000 untuk cat interior, berapa banyak cat interior dan eksterior yang harus dihasilkan perusahaan tersebut setiap harinya unutk memaksimumkan pendapatan kotor? Variable-variable dari model ini dapat didefiniskan sebagai XE = jumlah ton cat eksterior yang diperoduksi setiap hari XI = jumlah ton cat interior yang diperoduksi setiap hari



13



Pendapatan kotor dari penjualan xE ton adalah 3Xe ribu dollar Pendapatan kotor dari penjualan xI ton adalah 2XI ribu dollar Z mewakili pendapatan kotor total (dalam ribuan dollar). Dengan fungsi tujuan ditulis sebagai z=3xe + 2Xi. (



penggunaan bahan mentah oleh ketersediaan bahan )≤( ) mentah maksimum kedua cat



Ini mengarah pada batasan berikut Xe + 2Xi ≤ 6 (bahan mentah A) 2Xe + Xi ≤ 6 ( bahan mentah B) Batasan permintaan diekspresikan secara verbal sebagai



(



jumlah kelebihan cat interior ) ≤ 1 ton per hari dibandingkan cat eksterior



(permintaan akan cat interior) ≤ 2 ton per hari



Secara matematis kedua batasan tersebut diekspresikan secara berturut- turut sebagai Xi – Xe ≤ 1 (kelebihan cat dibandingkan eksterior) xi ≤ 2 (permintaan maksimum akan cat interior Batasan implisit adalah bahwa jumlah yang diproduksi untuk setiap cat tidak dapat negative (kurang dari nol). Untuk menghindari memperoleh pemecahan seperti itu, kita mengenakan batasan non negativitas, yang ditulis sebagai xI ≥ 0



14



xe ≥ 0 Model sistematis yang lengkap untuk masalah Reddy Mikks dapat diringkas sebagai berikut: Tentukan jumlah ton cat interior dan eksterior, xi dan xe, yang harus diproduksi untuk maksimumkan z = 3xe + 2xi



(fungsi tujuan)



Dengan batasan Xe + 2xi ≤ 6 2xe + xi ≤ 8 -xe + xi ≤ 1 Xi ≤ 2 xe≤ 0, xi ≤ 0 Yang menjadikan model ini sebagai program linier karena fungsinya (batasan dan tujuan) adalah linier, linieritas menyiratkan bahwa baik sifat proporsionalitas maupun aditivitas dipenuhi. 1. Proporsionalitas mengharuskan bahwa kontribusi setiap variable (yaitu xe dan xi) dalm fungsi tujuan atau penggunaan sumber daya harus proposional secara langsung dengan tingkat (nilai) variable tersebut. Misalnya jika Reddy Mikks Company memberikan pemotongan harga dengan menjual satu ton cat eksterior dengan harga $2500 ketika penjualan melebihi 2 ton, setiap ton tidak lai menghasilkam pendapatan $3000. Melainkan, setiap ton akan menghasilkan $3000 per ton untuk xe ≤ 2 dan $2500 per ton untuk xe ≥ 2 ton. Situasi ini tidak memenuhi kondisi proporsionalits langsung dengan xe. 2. Aditivitas mengharuskan bahwa fungsi tujuan adalah jumlah langsung dai kontribusi individual dari variable-variabel yang berbeda. Dengan cara



15



yang sama, sisi kiri dari setiap batasan harus merupakan jumlah penggunaan individual setiap variable dari sumber daya yang bersesuaian. Misalnya, dalam kasus dua produk yang bersaing, di mana kenaikan dalam tingkat penjualan satu produk memiliki pengaruh yang merugikan terhadap penjualan produk lainnya, kedua produk tersebut tidak memenuhi sifat aditivitas.



Pemecahan Grafik dari Model LP Untuk model-model dengan dua Variable dapat dipecahkan dengan secara grafik, sedangkan tiga grafik atau lebih dipecahkan dengan grafik tidak praktis, yang akan dipelajari juga di Bab 3 bahwa metode grafik akan berfungsi sebagai dasar untuk pengembanga meode pemecahan umum. Analisis sensitivitas Analisis sensitivitas dirancang untuk mempelajari pengaruh perubahan dalam parameter model LP terhadap pemecahan optimum yang dipandang sebagai bagian integral dari pemecahan (yang diperluas) dari setiap masalah LP.Tujuan akhir



16



analisis ini adalah untuk memperoleh informasi tentang pemecahan optimum yang baru dan yang memungkinkan dengan perhitungan tambahan yang minimal yang terutama sangat sesuai untuk mempelajari pengaruh variasi dalam koefisisen biaya/laba dan jumlah sumber daya. Formulasi LP Dalam hal ini disajikan dua model LP yang akan memudahkan dalam mendeifiniskannya. Dalam bagian berikutnya, disajikan formulasi lain dimana identifikasi dan penggunaan variable keputusan adalah lebih rumit. Formulasi LP secara grafik dipergunakan untuk menarik kesimpulan umum tentang msalah LP, metode pemecahannya, dan sensitivitas nilai pemecahan optimum terhadap perubahan. Pemecahan grafik mengungkapkan observasi penting bahwa pemecahan LP yang optimum akan selalu berkaitan dengan titik sudut dari ruang pemecahan. Hasil ini meruoakan gagasan kunci untuk pengembangan prosedur umum, yang disebut metode simpleks, untuk memecahkan program linear secara aljabar. Malah LP dapat dipandang dalam satu kerangka sebagai sebuah mdel alokasi sumber daya di mana sumber daya yang terbatas dialokasikan untuk kegiatan ekonimi. Dengan asumsi masalah LP maksimisasi, orofitabilitas dari sebuah kegiatan ekonomi diukur dalam bentuk penggunaan sumber daya dan kontribusinya pada fungsi tujuan. Pengaruh bersih dari kedua factor ini diukur berdasarkan pengurangan biaya daro kegiatan ekonomi. Harga jual, sebaliknya memberikan ukuran dampak perubahan dalam ketersediaan sumber daya terhadap nilai tujuan optimum.  Representasi Matematis Kita berusaha menentukan kombinasi susunan pisau (variabel) yang akan memenuhi pesanan yang diperlukan (batasan dengan bidang kerugian pemotongan yang terkecil (tujuan). Definisi variabel sebagaimana diberikan di sini harus diterjemahkan dengan cara yang dapat dipergunakan oleh para operator di pabrik tersebut. Dengan mempelajari cara kita mengembangkan kedua kombinasi tersebut, kita mencatat bahwa



17



variabel itu harus didefinisikan sebagai jumlah gulungan standar yang harus dipotong sesuai dengan satu susunan pisau tertentu. Definisi ini jelas mengharuskan identifikasi semua susunan pisau yang mungkin sebagaimana diringkaskan dalam tabel berikut ini. Susunan 1, 2, dan 3 diberikan dalam Gambar 2-14. Anda sebaiknya meyakinkan diri anda sendiri tentang keabsahan susunan lainnya dan bahwa tidak ada susunan lain yang menjanjikan" yang terlupakan. Ingat bahwa sebuah susunan yang menjanjikan tidak dapat menghasilkan kerugian pemotongan dengan lebar 5 kaki atau lebih.



III.



PEMROGRAMAN LINIER: METODE SIMPLEKS



. Gagasan Keseluruhan Tentang Metode Simpleks Metode grafik yang disajikan dalam Bab 2 memperlihatkan bahwa LP yang optimum selalu berkaitan dengan titik ekstrim atau titik sudut dari ruang pemecahan. Gagasan ini dengan tepat mengatur pengembangan metode simpleks. Pada intinya, apa yang dilakukan metode simpleks adalah menerjemahkan definisi geometris dari titik ekstrim menjadi definisi aljabar. Sebagai langkah pertama, metode simpleks mengharuskan agar setiap batasan ditempatkan dalam bentuk standar yang khusus di mana semua batasan diekspresikan sebagai persamaan dengan menambahkan variabel slack dan surplus sebagaimana diperlukan. Jenis konversi ini umumnya menghasilkan sekelompok persamaan di mana jumlah variabel adalah lebih besar daripada jumlah persamaan, yang umumnya berarti bahwa persamaan-persamaan tersebut menghasilkan sejumlah titik pemecahan yang tidak terbatas (bandingkan dengan ruang pemecahan secara grafik). Titik ekstrim dari ruang ini dapat diidentifikasi secara aljabar sebagai pemecahan dasar (basic solutions) dari sistem persamaan simultan tersebut. Dari teori aljabar linier, sebuah pemecahan dasar diperoleh dengan menetapkan beberapa variabel yang sebanyak selisih antara jumlah total variabel dengan jumlah total persamaan memiliki nilai sama dengan nol dan lalu memecahkan variabel sisanya, dengan ketentuan bahwa kondisi tersebut



18



menghasilkan satu pemecahan yang unik. Pada intinya, transisi dari prosedur grafik ke prosedur aljabar sepenuhnya bergantung pada keabsahan hubungan penting berikut ini: titik ekstrim pemecahan dasar Dengan tidak adanya ruang pemecahan grafik untuk menuntun kita ke arah titik optimum, kita memerlukan sebuah prosedur yang mengidentifikasi pemecahanpemecahan dasar yang menjanjikan secara cerdas. Apa yang dilakukan oleh metode simpleks adalah mengidentifikasi satu pemecahan dasar awal dan lalu bergerak secara sistematis ke pemecahan dasar lainnya yang memiliki potensi untuk memperbaiki nilai fungsi tujuan. Pada akhirnya, pemecahan dasar yang bersesuaian dengan nilai optimum akan diidentifikasi dan proses perhitungan berakhir. Pada gilirannya, metode simpleks merupakan prosedur perhitungan yang berulang (iteratif) di mana setiap pengulangan (iterasi) berkaitan dengan satu pemecahan dasar. Penentuan pemecahan dasar dalam metode simpleks umumnya melibatkan perincian perhi-tungan yang menjemukan. Perincian seperti ini sebaiknya tidak mengalihkan perhatian anda darı gagasan dasar metode ini: menghasilkan beberapa pemecahan dasar secara berurutan dengan cara yang akan mengarahkan anda pada titik ekstrim òptimum. Semua perincian perhitungan adalah sekunder dibandingkan gagasan dasar ini dan anda harus terus memandangnya demikian. Pengembangan Metode Simpleks Pembahasan ini dimulai dengan pengembangan bentuk standar yang diperlukan untuk mewakili ruang pemecahan LP dengan sebuah sistem persamaan simultan. Pembahasan selebihnya memperlihatkan bagaimana pemecahan dasar yang berturutturut ditentukan secara selektif dengan maksud untuk mencapai titik pemecahan optimum dalam sejumlah terbatas iterasi. Ada dua variasi dari metode simpleks: algoritma simpleks primal dan simpleks dual. Pada permukaannya, kedua metode ini tampaknya berbeda. Sebenarnya tidak demikian halnya, dan pada kenyataannya inti dari kedua algoritma ini tetap didasari



19



oleh gagasan bahwa titik ekstrim dari ruang pemecahan adalah sepenuhnya diidentifikasi oleh pemecahan dasar dari model LP. Pada dasarnya, kedua algoritma tersebut tampaknya berbeda hanya karena keduanya dirancang untuk memanfaatkan rancangan awal khusus dari model LP yang bersangkutan. . Bentuk LP Standar Model LP dapat mencakup batasan dengan segala jenis (S, 2, =). Lebih jauh lagi, variabel dapat nonnegarif atau tidak dibatasi dalam tandanya. Untukmengembangkan sebuah metode pemecahan yang umum, masalah LP harus ditempatkan dalam format yang sama, yang akan kita sebut sebagai forma: standar. Sifat dari bentuk ini adalah sebagai berikut: 1. Semua batasan adalah persamaan (dengan sisi kanan yang non negatif jika modei tersebut dipecahkan dengan metode simpleks prmal) 2. Semua variabel adalah nonnegatif. 3. Fungsi tujuan dapat berupa maksimisasi atau minimisasi. Sebagaimana akan diterangkan lebih lanjut, sifat kedua yang mensyaratkan bahwa semua variabel harus nonnegatif ad?lah sangat penting dalam pengembangan metode simpleks (primal dan dual).  Batasan 1. Sebuah variabel yang berjenis ≥ (≤) dapat dikonversikan menjadi sebuah persamaan dengan menambahkan variabel slack ke (mengurangkan variabel surplus dari) sisi kiri batasan tersebut. Misalnya, dalam batasan X1 + 2x2 ≤ 6 kita menambahkan slack sį 2 0 ke sisi kiri untuk memperoleh persamaan Xi + 2x2 + SĮ = 6, s1 2 ≥ 0 Kemudian, pertimbangkan batasan 3x1+2x2 – 3x3 ≥ 5



20



Karena sisi kiri sekarang tidak lebih kecil daripada sisi kanan, kita mengurangkan variabei s u r p l u s s 2 ≥ 0 dari sisi kiri untuk memperoleh persamaan 3xi + 2xi – 3x3 –s2 = 5, s2 ≥ 0 2. Sisi kanan dari. sebuah persamaan dapat selalu dibuat nonnegatif dengan mengalikan kedua sisi dengan -1. Misalnya, 2xi + 3x2 — 7x3 = -5 secara matematis adalah setara dengan -2xi — 3x2 + 7x3 = +5. 3. Arah petidaksamaan dibalik ketika kedua sisi dikalikan dengan -1. Misalnya, sementara 2 ≥ 4, -2 ≥ -4. Jadi pertidaksamaan 2x 1 - x2, < -5 dapat digantikan dengan -2x1 + x2 ≥ 5  Fungsi Tujuan Walaupun model LP standar dapat berjenis maksimisasi atau minimisasi, konversi dari satu bentuk ke bentuk lainnya kadang-kadang berguna. Maksimisasi sebuah fungsi adalah setara dengan minimisasi negatif dari fungsi yang sama, dan demikian pula sebaliknya. Misalnya,



maksimumkan z = 5x1 + 2x2 + 3x3



secara matematis adalah setara dengan



minimumkan (-z) = -5x1 - 2x2 - 3x3



Kesetaraan berarti bahwa untuk sekelompok balasan yang sama, nilai optimum dari x1, x2, dan x3 adalah sama dalam kedua kasus tersebut. Perbedaan satu-satunya adalah bahwa nilai fungsi tujuan walaupun sama secara numerik, akan terlihat dengan tanda yang berbeda.



21



Metode Simpelks Primal Metode simpleks primal dimulai dari satu pemecahan dasar yang layak (titik ekstrim) dan berlanjut untuk berulang melalui pemecahan dasar yang layak berikutnya sampai titik optimum dicapai. Proses dimulai di ekstrim titik asal (titik A) dan bergerak di sepanjang tepi AB dari ruang layak ke titik ekstrim B yang bersebelahan iterasi 1). Dari B, proses tersebut bergerak di sepanjang tepi BC ketitik ekstrim C yang bersebelahan iterasi 2), yang adalah optimum. Perhatikan bahwa prosedur ini tidak mampu melintasi ruang pemecahan (misalnya, dari A ke C), tetapi harus bergerak disepanjang tepi di antara titik-titik ekstrim yang bersebelahan. Semua yang perlu kita lakukan adalah memperlihatkan bagaimana titik ekstrim seperti A, B, dan C diidentifikasi tanpa keuntungan dari sebuah ruang pemecahan grafik. Pertimbangkan model Reddy Mikks dalam bentuk standar yang diberikan di bawah ini: maksimumkan z = 3xE + 2xi + 0s1 + 0s2 + 0s3+ 0s4 Sifat pertama menjamin bahwa jumlah variabel slack adalah sama dengan jumlah persamaan. Jadi semua variabel sisanya dapat dipergunakan sebagai variabel nondasar (nol). Karena berdasarkan sifat 2 semua sisi kanan dari persamaan adalah nonnegatif, pemecahan dasar yang dihasilkan secara otomatis adalah layak, sebagaimana dipersyaratkan oleh metode simpleks primal. Titik logis berikutnya yang mengikuti identifikasi pemecahan awal adalah meneliti pergerakan ke sebuah pemecahan dasar yang baru. Dari sudut pandang optimisasi, kita tertarik dengan pergerakan ke pemecahan dasar lainnya hanya jika kita dapat mewujudkan perbaikan dalam nilai fungsi tujuan. Pertama-tama ingat bahwa sebuah pemecahan dasar yang baru hanya diperoleh dengan membuat setidaknya satu dari variabel nondasar (nol) saat ini menjadi variabel dasar. Dalam metode simpleks,



22



kita melakukan perubahan ini dengan memasukkan satu variabel non- dasar setiap kali. Secara intuitif, sebuah variabel nondasar seperti itu hanya dapat dimasukkan ke dalam pemecahan jika hal tersebut memperbaiki nilai fungsi tujuan. Untuk merancang peraturan perhitungan yang jelas, metode simpleks menggunakan sebuah heuristik; yaitu, dalam kasus maksimisasi, variable nondasar yang dipilih adalah variabel yang memiliki koefisien yang paling negatif dalam persamaan tujuan z. Dengan menggunakan heuristik seperti ini, diharapkan (tetapi tidak dijamin) bahwa metode simpleks tersebut akan menghasilkan “lompatan" terbesar dalam nilai tujuan sementara ia bergerak dari satu iterai ke iterasi berikutnya, sehingga menjangkau optimum dalam sedikit mungkin iterasi. Pemecahan dasar yang baru dan diperoleh dengan memasukkan variabel masuk haruş mencakup tepat m variabel dasar. Ini berarti bahwa salah satu dari variabel dasar saat ini harus dikeluarkan dari pemecahan. Dalam contoh Reddy Mikks, variabel keluar (leaving variable) haruslah salan satu dari variabel s1, $2, S3, atau s4. Dengan memperhatikan Gambar 3-2, kita melihat bahwa nilai variabel masuk dalam pernikahan yang baru itu bersesuaian dengan titik B. Setiap kenaikan yang melewati titik ini akan membawa kita keluar ruang layak. Dari definisi batasan, ini berarti bahwa s2 (yang berkaitan dengan batasan 2) akan sama dengan nol, yang berarti bahwa s2 merupakan variabel keluar. Kita dapat memilih variabel keluar secara langsung dari persamaan batasan sematamata dengan menghitung titik potong non negatif dari semua batasan dengan sumbu XE. Titik potong terkecil akan mengidentifikasi variabel keluar. Dalam model Reddy Mikks, hanya batasan 1 dan 2 berpotongan dengan sumbu x dalam arah positif, dengan titik potong masing-masing sama dengan 6/1 = 6 dan 8/2 = 4. Karena titik potong yang lebih kecil (= 4) berkaitan dengan batasan kedua, variabel dasar s2 harus meninggalkan pemecahan.



23



Bagaimana kita dapat mengotomatisasi proses pemilihan variabel keluar tanpa memanfaatkan ruang pemecahan grafik? Semua yang perlu kita lakukan adalah menghitung semua titik potong batasan dengan sumbu x sebagai rasio antara sisi kanan dengan koefisien batasan XE yang bersesuaian; yaitu, titik potong batasan 1 = 6/1 = 6 titik potong batasan 2 = 8/2 = 4 titik potong batasan 3 = 1/-1 = -1 titik potong batasan 4 = 2/0 = tak hingga



Tiga titik potong pertama digambarkan dalam Gambar 3-2. Titik potong keempat tidak dapat diperlihatkan karena batasan 4 sejajar dengan sumbu X. Kita tidak perlu memperhatikan titik potong ketiga, karena nilainya negatif, yang berarti bahwa batasan ketiga tersebut tidak membatasi XE dalam arah positif. Kita juga tidak perlu memperhatikan batasan 4, karena tidak berpotongan dengan XE sama sekali. Ini hanya meninggalkan titik potong 1 dan 2, dengan kesimpulan bahwa s2 haruslah merupakan variabel keluar. Dalam arti mekanis, kita dapat mengotomatisasi proses di atas dengan hanya memperhatikan batasan yang koefisien batasannya positif secara ketat untuk variabel masuk yang bersangkutan. Prosedur yang diberikan di atas untuk memilih variabel masuk dan variabel keluar disebut sebagai kondisi optimalitas dan kondisi kelayakan. Kita mencatat bahwa kondisi kelayakan (titik potong minimum) dapat diterapkan baik untuk masalah maksimisasi maupun minimisasi. Sebaliknya, kondisi optimalitas untuk masalah minimisasi adalah berbeda dalam hal bahwa variable masuk berkaitan dengan koefisien



24



non dasar yang paling positif (sebagaimana dibandingkan dengan yang paling negatif dalam kasus maksimisasi). Berikut ini adalah ringkasan formal dari dua kondisi simpleks tersebut: Kondisi Optimalitas: Variabel masuk dalam maksimisasi (minimisasi) adalah variabel non dasar dengan koefisien yang paling negatif (positif) dalam persamaan z tujuan. Koefisien dengan nilai yang sama dapat dipilih secara sembarang. Nilai optimum dicapai ketika semua koefisien nondasar dalam persamaan z adalah non negatif (dan positif).



25



Kondisi Kelayakan: Baik untuk masalah maksimisasi maupun minimisasi, variabel keluar adalah variabel dasar saat ini yang memiliki titik potong terkecil (rasio minimum dengan penyebut yang positif secara ketat) dalam arah variabel masuk. Nilai yang sama dapat dipilih secara sembarang Kita sekarang siap untuk menyajikan langkah-langkah iterasi formal dari metode simpleks primal: Langkah 0: Dengan menggunakan bentuk standar (dengan sisi kanan semua nonnegatif). tentukan pemecahan dasar awal yang layak. Langkah 1. Pilih variabel masuk dan di antara variabel nondasar dengan menggunakan kondisi optimalitas. Langkah 2: Pilih variabel keluar dari variabel dasar saat ini dengan menggunakan kondisi kelayakan Langkah 3. Tentukan nilai variabel dasar yang baru dengan membuat variabel masuk tersebut sebagai variabel dasar dan variabel keluar sebagai variabel nondasar. Kembali ke langkah 1. Dengan pemikiran tertentu, anda akan menyadari bahwa metode simpleks primal didasari oleh argumen yang masuk akal. Secara spesifik, di titik pemecahan dasar (titik ekstrim) tertentu, kita mencari satu pemecahan dasar yang baru hanya jika kenaikan dalam nilai salah satu variable nondasar saat ini dapat memperbaiki nilai tujuan (kondisi optimalitas). Jika kita menemukan variabel nondasar seperti itu, salah satu variabel dasar saat ini harus meninggalkan pemecahan untuk memenuhi persyaratan bahwa jumlah variabel dasar harus tepat sama dengan m. Pemilihan variabel keluar dicapai dengan menggunakan kondisi kelayakan. Proses penukaran variable dasar



26



dengan variabel nondasar ini tepat setara dengan pergerakan di antara titik-titik ekstrim yang bersebelahan di sepanjang tepi ruang pemecahan (bandingkan dengan Gambar 31). Sebenarnya ti dan metode simpleks primal. Tetapi, anda perlu mengingat saran berikut ini. Ketika kita mulai menjelaskan bagaimana metode yang disebut metode Gauss Jordan dipergunakan untuk melakukan "penukaran" variabel masuk dan variabel keluar, anda akan menemukan perincian perhitungan yang monoton dan membosankan. Pengalaman kami yang panjang dalam pengajaran menunjukkan bahwa sebagian besar mereka yang baru mempelajari topik ini "termakan" oleh perincian ini, sehingga kehilangan jejak tentang apa yang sebenarnya dicapai oleh metode simpleks. Untuk menghindari jebakan ini, ingat bahwa sasaran utama dari prosedur perhitungan Gauss-Jor dan adalah mentransformasikan persamaan-persamaan dengan cara yang memampukan kita untuk memperoleh pemecahan dasar yang baru dengan memberikan nilai nol pada variabel nondasar saat ini. Selain itu, prosedur Gauss-Jordan tidak memiliki makna khusus apapun sepanjang berkaitan dengan teori metode simpleks. Terlebih lagi, ingatlah bahwa anda hanya perlu beberapa kali melakukan perhitungan yang menjemukan ini, dan sesudahnya anda dapat menggunakan TORA (atau perangkat lunak lainnya) untuk menangani tugas ini. Di sepanjarg bab ini, perhatian anda sebaiknya dipusatkan pada interpretasi pemecahan yang diperoleh dengan perhitungan Gauss-Jor dan. Ini adalah inti dari pembahasan kami. Dengan pemikiran tertentu, anda akan menyadari bahwa metode simpleks primal didasari oleh argumen yang masuk akal. Secara spesifik, di titik pemecahan dasar (titik ekstrim) tertentu, kita mencari satu pemecahan dasar yang baru hanya jika kenaikan dalam nilai salah satu variable nondasar saat ini dapat memperbaiki nilai tujuan (kondisi optimalitas). Jika kita menemukan variabel nondasar seperti itu, salah satu variabel dasar saat ini harus meninggalkan pemecahan untuk memenuhi persyaratan bahwa jumlah variabel dasar harus tepat sama dengan m. Pemilihan



27



variabel keluar dicapai dengan menggunakan kondisi kelayakan. Proses penukaran variabel  Pemecahan Awal Buatan Untuk Metode Simpleks Primal Dalam model Reddy Mikks, semua batasan adalah berjenis S. Sifat ini, bersamaan dengan fakta bahwa sisi kanan dari semua batasan adalah nonnegatif, memberikan kita pemecahan dasar awal yang layak yang terdiri dari semua variabel slack. Kondisi seperti ini tidak dipenuhi oleh semua model LP, sehinga menimbulkan kebutuhan untuk merancang sebuah prosedur perhitungan otomatis untuk memulai iterasi simpleks. Kita melakukan ini dengan menambahkan variabel buatan (artificial variable) atau variabel tambahan di mana diperlukan untuk memainkan peran variable slack. Tetapi, karena variabel buatan seperti itu tidak memiliki makna fisik dalam model semula (sehingga diberi nama buatan"), ketentuan harus dibuat untuk membuatnya menjadi nol di iterasi optimum. Dengan kata lain, kita menggunakan variabel buatan untuk memulai pemecahan, dan lalu meninggalkan mereka setelah misi mereka terpenuhi. Kita mencapai hal ini dengan menggunakan umpan balik informasi, yang akan membuat variabel ini tidak menarik dari sudut pandang optimisasi. Satu cara yang logis untuk mencapai tujuan ini adalah dengan mengenakan penalti pada variabel buatan dalam fungsi tujuan. Dua metode (yang berkaitan erat) yang didasari oleh penggunaan penalti tersedia untuk maksud ini: (1) metode M atau metode penalti dan (2) metode dua tahap. Perincian tentang kedua prosedur ini diberikan di bawah ini. Metode Simpelks Dual Kami menggunakan variabel buatan untuk memecahkan masalah LP yang tidak memiliki pemecahan dasar awal yang layak dan semuanya adalah variabel slack. Terdapat sekelompok masalah LP yang tidak memiliki pemecahan dasar awal yang layak dan semuanya adalah variabel slack, tetapi dapat dipecahkan tanpa menggunakan



28



variabel buatan. Prosedur untuk memecahkan kelompok masalah ini disebut metode simpleks dual. Dalam metode ini, pemecahan dimulai tidak layak dan optimal (sebagaimana diperbandingkan dengan metode sim simpleks primal yang memulai layak tetapi non optimal). Kami akan pertama-tama memperlihatkan gagasan metode simpleks dual ini secara grafik dan lalu menyajikan langkah-langkah aljabarnya. Pertimbangkan masalah LP berikut ini: minimumkan z = 3x1 + 2x2 dengan batasan 3x1 + x2 ≥ 3 4x1 + 3x2 ≥ 6 X1 + x2 ≤ 3 X1, x2 ≥ 0 Jika kita mengkonversikan batasan menjadi bentuk persamaan dengan menambahkan variable surplus atau slack, maslah tersebut dapat di tulis sebagai Minimumkan z = 3x1 +2x2 Dengan batasan -3 – x2 + x3 = -3 -4 -3x2



+ x4 =-6



29



X1 + x2



+x5 = 3



X1,x1,x3,x4,x5 ≥ 0 Bentuk diatas dianggap sbegai bentuk standar metode simpleks dual. x3= -1



x4= -6



x5 = 3



Gagasan umum dari prosedur simpleks dual adalah bahwa sementara iterasi pertama dimulai tidak layak dan lebih baik daripada) optimal, iterasi berikutnya bergerak ke arah ruang layak tanpa kehilangan sifat optimalitas (ingat bahwa simpleks biasa mempertahankan kelayakan sementara bergerak ke arah optimalitas). Pada iterasi di mana pemecahan menjadi layak untuk pertama kalinya, proses tersebut berakhir. Gambar 3-3 mengilustrasikan gagasan ini secara grafik. Permecahan dimulai di titik A (X) = x2 0 dan x3 = -3,44 = -6,15 = 3) dengan z=0, yang akan tidak layak dalam kaitannya dengan ruang pemecahan. Iterasi berikutnya diperoleh dengan bergerak ke titik B (x) = 0, x2 = 2) dengan z= 4, yang masih tidak layak. Yang terakhir, kita mencapai titik C (x = 3/5,x2 = 6/5), di mana z = 21/5. Untuk pertama kalinya kita menemukan pemecahan yang layak, sehingga menunjukkan akhir dari proses iterasi ini. Perhatikan bahwa iterasi tersebut dapat pula berlanjut dalam urutan A D → C, daripada A B C, dengan kesimpulan yang sama. Kami akan memperlihatkan di bawah ini bagaimana metode simpleks dual memilih jalur tertentu. Perhatikan juga bahwa nilai z yang berkaitan dengan A, B, dan C adalah 0, 4, dan 4Vs. secara berurutan, yang menerangkan mengapa pemecahan yang dimulai di A adalah lebih baik daripada optimal. Tabel awal untuk iterasi simpleks dual untuk contoh tersebut adalah sebagai berikut



30



Variabel masuk



Dasar



x1



x2



x3



x4



x5



Pemecahan



z



-3



-2



0



0



0



0



x3



-3



-1



1



0



0



-3



x4



-4



-3



1



0



0



-6



x5



2



1



0



0



1



3



Variabel keluar Tabel ini bersesuaian dengan titik A dalam Gambar 3-3. Perhatikan bahwa baris tujuan memenuhi kondisi optimalitas (minimisasi). Pemecahan ini juga tidak layak karena x3 dan X4 memiliki nilai negatif. Ini adalah kondisi (optimal dan tidak layak) yang diperlukan untuk iterasi awal dalam metode simpleks dual. Karena sasaran kami adalah menyingkirkan ketidaklayakan ini, kita melakukannya dengan berusaha memaksa variabel dasar negatif ini untuk keluar dari pemecahan. Walaupun baik x3 (= -3) atau x4 (= -6) akan memahami maksud ini, sebuah peraturan umum menuntut penyingkiran variabel yang paling tidak layak (paling negatif) di antara semua kandidat dengan harapan bahwa hal itu akan mengarahkan kita pada pemecahan yang layak dengan cara yang paling cepat. Jadi, dalam contoh kita ini, kita memilih x4 sebagai variabel keluar. Variabel masuk sekarang harus dipilih dari di antara variabel non dasar saat ini dengan ketentuan bahwa optimalitas tetap terjaga. Hal ini dicapai dengan mengambil rasio koefisien sisi kiri dari persamaan z dengan koefisien yang bersesuaian dalam persamaan variabel keluar. Untuk memper tahankan optimalitas, rasio dengan



31



penyebut positif atau nol disir.gkirkan. Variabel masuk adalah variabel yang berkaitan dengan rasio yang memiliki nilai terkecil. Dalam tabel awal kita ini, rasio dihitung sebagai berikut:



Variabel



x1



x2



x3



x4



x5



Persamaan z



-3



-2



0



0



0



Persamaan x4



-4



-3



1



0



1



rasio



3/4



2/3



-



-



-



Jadi, tabel berikut ini diperoleh dengan menggunakan operasi baris yang biasa, sehingga mengarah pada tabel berikut:



Dasar



x1



x2



x3



x4



x5



Pemecahan



z



-1/3



0



0



-2/3



0



4



x3



-5/3



0



1



-1/3



0



-1



x2



4/3



1



0



-1/3



0



2



x5



-1/3



0



0



1/3



1



1



rasio



1/5



-



-



2



-



Kemudian, x3 meninggalkan pemecahan dasar dan x1 masuk, yang menghasilkan tabel berikut:



Dasar



x1



x2



x3



x4



x5



Pemecahan



z



0



0



-1/5



-3/5



0



21/5



x3



1



0



-3/5



1/5



0



3/5



32



x2



0



1



4/5



-3/5



0



6/5



x5



0



0



-1/5



2/5



1



6/5



=Tabel ini sekarang layak dan optimal. Pemecahan yang bersesuaian adalah x1 = 315, 6/5, dan z = 21/5 Metode simpleks dual diterapkan dengan cara yang serupa untuk masalah maksimisasi dengan ketentuan bahwa pemecahan awal sekali lagi optimal tetapi tidak layak. Perbedaan satu-satunya adalah, seperti yang anda perkirakan, terjadi dalam kondisi untuk memilih variabel masuk, seperti diterangkan di bawah ini. Kondisi Kelayakan: Variabel keluar adalah variabel dasar yang memiliki nilai paling negative (jika sama, tentukan secara sembarang). Jika semua variabel dasar adalah nonnegatif, proses berakhir. Kondisi Optimalitas: Variabel masuk adalah variabel nondasar yang berkaitan dengan rasio terkecil jika meminimumkan atau nilai absolut terkecil dari rasio jika memaksimumkan (jika sama, tentukan secara sembarang). Rasio ditentukan dengan membagi koefisien sisi kiri dari per samaan z dengan koefisien negatif vang bersesuaian dalam persamaan dengan koefisien negative yang bersangkutan dengan variabel keluar. Jika semua penyebut adalah nol atau positif, tidak terdapat pemecahan yang layak. Metode simpleks dual, di samping penggunaannya untuk sekelompok masalah LP khusus, adalah berguna untuk melakukan analisis pasca-optimisasi dalam bentuk analisis sensitivitas dan pemrograman parametrik. KASUS KHUSUS DALAM APLIKASI METODE SIMPLEKS Dalam bagian ini, kita akan mempertimbangkan kasus khusus yang dapat timbul dalam aplikasi metode simpleks, yang mencakup



33



1. Degenerasi. 2. Optimum alternatif. 3. Pemecahan yang tidak dibatasi. 4. Pemecahan tidak ada (atau tidak layak). Minat kita untuk mempelajari kasus-kasus khusus ini adalah berlipat dua: (1) untuk menyajikan penjelasan teoritis tentang alasan-alasan mengapa situasi ini timbul dan (2) memberikan interpretasi praktis tentang apa arti hasil-hasil khusus ini dalam masalah kehidupan nyata.



DEGENERASI Dalam Bagian 3.3 kami menunjukkan bahwa dalam penerapan kondisi kelayakan metode simpleks primal, dua rasio minimum yang sama dapat dipilih secara sembarang untuk maksud menentukan variabel keluar. Tetapi, ketika hal ini terjadi, satu variabel dasar atau lebih pasti akan sama dengan nol dalam iterasi berikutnya. Dalam kasus ini, kita mengatakan bahwa pemecahan baru itu adalah degenerasi. (Dalam semua contoh LP yang telah kita pecahkan sejauh ini, variabel dasar selalu memiliki nilai positif secara ketat.) Tidak terdapat satu pun hal yang mengejutkan dalam menangani pemecahan degenerasi, dengan kekecualian satu ketidaknyamanan teoritis kecil, yang akan segera kita bahas. Dari sudut pandang praktis, kondisi ini menunjukkan bahwa model tersebut memiliki setidaknya satu batasan yang berlebihan. Untuk mampu memberikan pemahaman yang lebih mendalam tentang dampak praktis dan teoritis dari degenerasi, kita akan mempertimbangkan satu contoh numerik. Ilustrasi grafik akan meningkatkan pemahaman kita tentang gagasan di balik situasi khusus ini.



34



INTERPRETASI TABEL SIMPLEKS: ANALISIS SENSITIVITAS Dalam bagian yang lalu, kami telah memperkenalkan perincian dasar tentang metode simpleks. Kita sekarang akan mengalihkan perhatian pada interpretasi hasil keluaran dari perhitungan metode simpleks. Daftar berikut ini meringkaskan informasi yang dapat diperoleh dari tabel simpleks: 1. Pemecahan optimum. 2. Status sumber daya. 3. Harga dual (nilai unit sumber daya) dan pengurangan biaya. 4. Sensitivitas pemecahan optimum terhadap perubahan dalam ketersediaan sumber daya, laba/biaya marginal (koefisien fungsi tujuan), dan penggunaan sumber daya oleh kegiatan-kegiatan dalam model



Semua butir yang didaftarkan di atas telah dibahas dan diterangkan dalam Bab 2, sebagian besar melalui penggunaan perangkat lunak TORA. Sasaran kami dalam bagian ini adalah memberikan pandangan tentang bagaimana hasil yang diberikan dalam Bab 2 ini diperoleh dari perhitungan metode simpleks.  STATUS SUMBER DAYA Sebuah batasan diklasifikasi sebagai batasan yang langka atau melimpah bergantung, secara berturut-turut, pada apakah pemecahan optimum tersebut "menghabiskan" keseluruhan jumlah yang tersedia untuk sumber daya yang bersangkutan. Tujuan kita adalah memperoleh informasi ini dari tabel optimum. Dalam model Reddy Mikks ini, kita memiliki empat batasan yang berjenis < Dua batasan pertama (yang mewakili penggunaan bahan mentah) merupakan batasan sumber daya yang "otentik." Batasan ketiga dan keempat berkaitan dengan batasan. permintaan yang dikenakan oleh kondisi pasar. Kita dapat memandang batasan ini sebagai “sumber daya" yang terbatas, karena 35



batasan permintaan yang meningkat adalah setara dengan peningkatan pangsa pasar perusahaan. Secara moneter, hal ini memiliki pengaruh yang sama seperti peningkatan ketersediaan sumberdaya fisik (seperti bahan mentah) melalui alokasi dana tambahan. Status sumber daya (melimpah atau langka) dalam setiap model LP dapat diperoleh secara langsung dari tabel optimum dengan mengamati nilai variabel slack. Nilai variabel slack yang positif berarti bahwa sumber daya tersebut tidak dipergunakan sepenuhnya, sehingga melimpah, sementara nilai variabel slack yang sama dengan nol menunjukkan bahwa keseluruhan sumber daya tersebut dihabiskan oleh kegiatankegiatan dalam model yang bersangkutan. Jadi, dalam model Reddy Mikks, kita memiliki ringkasan berikut ini:



Sumber Daya



Variabel Slack



Status Sumber Daya



Bahan mentah a



s1=0



Langka



Bahan mentah b



s2=0



Langka



Batasan atas kelebihan cat interior



s3=3



Melimpah



s4=2/3



Melimpah



Batasan atas permintaan untuk cat eksterior



Sumber daya yang dapat dinaikkan untuk maksud memperbaiki pemecahan (meningkatkan laba) adalah bahan mentah A dan B, karena tabel optimum memperlihatkan bahwa kedua sumber daya ini langka. Sebuah pertanyaan logis secara alamiah timbul: Sumber daya langka yang mana yang harus diprioritaskan dalam alokasi dana tambahan untuk meningkatkan laba secara paling menguntungkan? Kita menjawab pertanyaan ini ketika kita mempertimbangkan harga dual dari sumber daya yang berbeda.



36



 PERUBAHAN MAKSIMUM DALAM KETERSEDIAAN SUMBER DAYA Dalam bagian ini, kita berusaha menentukan kisaran variasi dalam ketersediaan sumber daya dimana harga dual tetap konstan. Untuk mencapai hal ini, kita perlu melakukan perhitungan tambahan. Kami pertama-tama memperlihatkan bagaimana prosedur ini bekerja dan lalu memperlihatkan bagaimana informasi yang sama ini dapat diperoleh dari tabel optimum. Misalkan bahwa kita mempertimbangkan perubahan sumber daya pertama dalam model Reddy Mikks dengan jumlah Di. yang berarti bahwa bahan mentah A yang tersedia adalah 6 + Di ton. Jika Di adalah positif, jumlah sumber daya ini meningkat; jika angka ini negatif, jumlah sumber daya ini menurun. Bagaimana tabel simpleks berubah ketika perubahan D dilakukan? Cara yang paling sederhana untuk menjawab pertanyaan ini adalah dengan menambahkan D, ke sisi kanan dari batasan pertama dalam tabel awal dan lalu melakukan operasi aritmatika yang sama seperti yang dipergunakan untuk mengembangkan iterasi yang berturutturut tersebut. Jika kita mengingat bahwa konstanta sisi kanan tidak pernah dipergunakan sebagai elemen pivot, terlihat jelas bahwa perubahan D hanya akan mempengaruhi sisi kanan dari setiap iterasi. Anda sebaiknya memeriksa bahwa iterasi yang berurutan dari model ini berubah seperti yang diperlihatkan dalam Tabel 3-5. Sebenarnya, perubahan di sisi kanan yang dihasilkan dari Di dapat diperoleh secara langsung dari tabel yang berturut-turut tersebut. Pertama-tama, perhatikan bahwa, dalam setiap iterasi, elemen sisi kanan yang baru terdiri dari sebuah konstanta dan bagian linier dalam D. Komponen konstanta adalah tepat sama dengan sisi kanan dalam iterasi sebelum D ditambahkan. Koefisien bagian linier dalam Di pada intinya adalah koefisien di bawah s dalam iterasi yang sama. Misalnya, dalam iterasi optimum, konstanta (12,4/3, 10/3, 3, 2/3) mewakili sisi kanan dari tabel optimum sebelum Di ditambahkan, dan (1/3, 2/3, -1/3, -1, -2/3) adalah



37



koefisien-koefisien di bahwa si dalam tabel yang sama. Mengapa si? Karena variabel ini secara unik berkaitan dengan variabel pertama. Dengan kata lain, untuk perubahan sisi kanan dalam batasan kedua, ketiga, dan keempat, kita akan secara berturut-turut menggunakan koefisien di bawah s2. S3. dan s4.  PERUBAHAN MAKSIMUM DALAM LABA/BIAYA MARGINAL



Seperti yang dilakukan dalam mempelajari kisaran yang diijinkan untuk perubahan dalam sumber daya, kita juga berminat untuk mempelajari kisaran yang diijinkan untuk perubahan dalam laba biaya marginal. Kami telah memperlihatkan secara grafik dalam Bagian 2.1.2 (Masalah Sensitivitas 1) bahwa koefisien fungsi tujuan dapat berubah dalam batasan-batasan tanpa mempengaruhi nilai optimal dari variabel (walaupun nilai optimum z akan berubah ini, kami memperlihatkan bagaimana informasi ini dapat diperoleh dari tabel optimum. dalam situasi ini, seperti dalam kasus perubahan sumber daya, persamaan tujuan tidak pernah dipergunakan sebagai persamaan pivot. Jadi setiap perubahan dalam koefisien fungsi tujuan hanya akan mempengaruhi persamaan tujuan dalam tabel optimum. Ini berarti bahwa perubahan seperti ini memiliki pengaruh berupa membuat pecahan menjadi tidak optimal. Sasaran kita adalah menentukan kisaran variasi untuk koefisien tujuan (satu per satu) di mana di dalamnya pemecahan optimum saat ini tetap tidak berubah Dua kasus yang berbeda timbul bergantung pada apakah variabel tersebut dasar atau nondasar dalam tabel optimal. Kasus 1: Variabel Dasar. Sifat operasi baris dalam tabel simpleks mengungkapkan bahwa setiap perubahan dalam koefisien semula dari variabel dasar optimal akan mempengaruhi semua koefisien nondasar dalam baris tujuan dari tabel optimum. Jadi, perubahan seperti ini mempengaruhi optimum saat ini, karena satu variabel nondasar atau lebih kemungkinan menjadi dapat dimasukkan ke dalam pemecahan dasar.



38



Kepentingan kita adalah menemukan kisaran variasi untuk koefisien tujuan semula yang akan menjaga optimum saat ini tetap tidak berubah. Kita mengilustrasikan perhitungan yang bersangkutan dengan mengubah laba marginal dari xe dalam model Reddy Mikks dari 3 menjadi 3 + di, di mana di dapat positif atau negatif. jadi, fungsi tujuan tersebut terbaca Z= (3 + di) + 2x1



Jika kita menggunakan fungsi ini dalam tabel awal dan melakukan urutan perhitungan yang sama seperti yang dipergunakan untuk menghasilkan tabel optimum semula, kita akan memperoleh tabel berikut ini (periksalah!):



IV.



PEMROGRAMAN LINIER: Metode Simpleks yang Direvisi



DASAR MATEMATIS Dalam bagian ini, kami mendefinisikan masalah LP dalam bentuk matriks. Berdasarkan definisi ini kami memperlihatkan bagaimana pemecahan dasar ditentukan. Kita lalu menggunakan informasi ini untuk mengembangkan tabel simpleks umum dalam bentuk matriks. Pengembangan ini membentuk dasar untuk pembahasan perincian metode simpleks yang direvisi. 39



MODEL LP STANDAR DALAM BENTUK MATRIKS Masalah pemrograman linier dalam bentuk standar dapat diekspresikan dalam bentuk matriks sebagai berikut: maksimumkan atau minimumkan z = CX dengan batasan (A,I) X = b X≥0



di mana I adalah matriks identitas m dan



Sisi kanan diharapkan bersifat non negatif dalam kasus metode simpleks primal. Matriks identitas I dapat selalu dibuat untuk tampil sebagaimana diperlihatkan dalam persamaan batasan dengan menambahkan atau mengatur susunan variabel slack, surplus, dan/atau buatan sebagaimana diperlukan. Ini berarti bahwa n elemen dari vektor X mencakup setiap variabel slack, surplus, dan variabel buatan yang ditambahkan, dengan m elemen paling kanan mewakili variabel pemecahan awal. Untuk memperjelas definisi di atas, contoh numerik berikut ini diberikan. Contoh: 40



maksimumkan z=2x1 + 3x2 + 4x3



dengan batasan x1 + x2 + x3 ≥ 5 x1 + x2



=7



5x1 - 2x2 + 3x3 ≥ 9 X1,x2,x3 ≥ 0



Diekspresikan dalam bentuk matriks standar sebagai



𝑥1 𝑥2 𝑥3 Maksimumkan z= (2, 3, 4, 0, -M, -M, 0) 𝑥4 𝑥5 𝑥6 [𝑥7] Dengan batasan 𝑥1 𝑥2 1 1 1 −1 1 0 0 𝑥3 5 [1 2 0 0 0 1 0] 𝑥4 = [7] 5 −2 3 0 0 0 1 𝑥5 9 𝑥6 [𝑥7] Xj ≥ 0



j = 1,2,…., 7



41



Perhatikan bahwa x4 adlah variable surplus sementara x7 adalah variable slack. Variable x5 dan x6 adalah variable buatan Dalam bentuk definisi matriks kita memiliki X= (x1, x2, ….., x7) C = ( 2, 3, 4, 0, -M, -M, 0) B = (5, 7, 9) 1 1 1 −1 A= [1 2 0 0 ] 5 −2 3 0



1 0 0 I = [0 1 0 ] 0 0 1



PEMECAHAN DASAR DAN BASIS Metode simpleks primal dan dual adalah bahwa pemecahan optimum, ketika berjumlah terbatas, harus berkaitan dengan titik ekstrim atau titik sudut dari ruang pemecahan. Secara aljabar, sebuah titik ekstrim berkaitan dengan pemecahan dasar dari persamaan batasan (A, I)X = b. Dengan diketahui bahwa (A, I)X = b memiliki m persamaan dan n variabel yang tidak diketahui [X = (x1, x2, .., Xn)], sebuah pemecahan dasar diperoleh dengan menetapkan n - m variabel sama dengan nol dan lalu memecahkan m persamaan dengan m variabel yang tidak diketahui, yang tersisa, dengan ketentuan bahwa sebuah pemecahan yang unik terdapat. Secara sistematis (A, I) X = ∑𝑛𝑗=𝑙 𝑃𝑗𝑋𝑗 P adalah vektor kolom ke-j dari (A, I). Setiap m yang merupakan vektor yang independant secara linier di antara P1, P2, Pn akan bersesuaian dengan pemecahan dasar (A, I)X = b dan karena itu bersesuaian dengan satu titik ekstrim dari ruang pemecahan. Dalam kasus ini, vektor m yang dipilih membentuk sebuah basis yang untuknya matriks bujur sangkar yang berkaitan haruslah bersifat "non singular."



42



METODE SIMPLEKS (PRIMAL) YANG DIREVISI Metode simpleks primal maupun dual; yaitu, setelahvariabel dasar diidentifikasi, basis B secara otomatis diketahui dan keseluruhan tabel dihasilkan dari data semula dalam bentuk standar dan inversi Peraturan spesifik dari metode simpleks primal dan lalu dapat diterapkan informasi Pada metode simpleks primal dan bentuk pemilihan vektor masuk dan vektor keluar. Selain dari itu, semua sama. Untuk kita hanya akan membahas metode simpleks primal yang Dalam metode simpleks (primal dual) yang direvisi, fakta iterasi hanya dalam definisi basis B menunjukkan keuntungan yang potensial dalam perhitungan: 1. Dalam masalah LP yang besar, penggunaan operasi pada kesalahan pembulatan mesin kumulatif yang tidak dapat dikendalikan dengan yang terhadap hasil akhir. Dalam yang direvisi, kita semula dari masalah. Dengan demikian kita mengendalikan akurasi perhitungan dengan mengendalikan kesalahan pembulatan dalam perhitungan 2. Sifat manipulasi matriks menunjukkan bahwa kita tidak perlu menghitung entri dari simpleks, yang untuk ukuran masalah LP tertentu kemungkinan memerlukan lebih sedikit perhitungan. BENTUK HASIL PERKALIAN DARI INVERSI Metode bentuk hasil perkalian adalah sebuah prosedur aljabar matriks yang menghitung inversi dari sebuah basis yang baru dari inversi basis lainnya, dengan ketentuan bahwa kedua basis tersebut berbeda tepat dalam satu vektor kolom. Prosedur ini sangat sesuai untuk perhitungan metode simpleks, karena basis yang berturut-turut berbeda tepat dalam satu (vektor) kolom sebagai hasil dari pertukaran vektor masuk dan keluar. Dengan kata lain, dengan diketahui basis saat ini B, basis berikutnya, Bnext dalam iterasi yang berikutnya, akan berbeda dengan B hanya dalam satu kolom. Prosedur bentuk hasil perkalian lalu menghitung inversi berikutnya B next dengan mengalikan terlebih dahulu inversi saat ini B-l dengan sebuah matriks E yang dibentuk



43



secara khusus. Definisi matriks identitas IM sebagai Im = (e1,e2,….,em) Dimana e adalah satu vector kolom dengan satu elemen di tempat I dan nol di tempat lainnya. Anggaplah bahwa B dan B-1 sudah diketahui dan asumsikan bahwa vector Pr dalam B digantikan dengan vector baru Pj. Untuk penyederhanaan didefiniskan ai = B-1 Pj



V.



PEMROGRAMAN LINIER: DUALITAS DEFINISI MASALAH DUAL



Masalah dual adalah sebuah masalah LP yang diturunkan secara matematis dari satu model LP primal. Masalah dual dan primal sangat berkaitan erat sedemikian rupa sehingga pemecahan simpleks optimal dari salah satu masalah akan secara otomatis menghasilkan pemecahan optimum untuk masalah lainnya. Dalam kebanyakan pembahasan LP, masalah dual didefinisikan untuk berbagai bentuk masalah primal, bergantung pada jenis batasan, tanda dari variabel, dan arti dari optimisasi. Dengan mendefinisikan masalah dual dari bentuk standar, hasilnya akan konsisten dengan informasi yang termuat dalam tabel simpleks. Tetapi, ingatlah bahwa definisi tunggal yang kami berikan di sini adalah umum dalam arti bahwa definisi ini secara otomatis menerangkan semua bentuk yang diberikan dalam pembahasanpembahasan LP lainnya. Bentuk standar yang umum dari maslah primal didefinisikan sebagai Z = ∑𝑛𝑗=1 𝐶𝑗𝑋𝑗



44



Dengan batasan ∑𝑛𝑗=1 𝐴𝑖𝑗𝑋𝑗 = 𝑏𝑖 I = 1, 2, ….. m Xj ≥ 0,



j = 1, 2,…….n



1. Untuk setiap batasan primal terdapat sebuah variabel dual. 2. Untuk setiap variabel primal terdapat sebuah batasan dual. 3. Koefisien batasan dari sebuah variabel primal membentuk koefisien sisi kiri dari batasan dual yang bersesuaian; dan koefisien tujuan dari variabel yang sama menjadi sisi kanan dari batasan dual. Peraturan-peraturan ini menunjukkan bahwa masalah dual akan memiliki m variabel (y1, y2, .., ym) dan n batasan (yang bersesuaian dengan x1, x2, ..., Xn). Kita sekarang mengalihkan perhatian kita untuk menentukan elemen sisanya dari masalah dual: arti optimisasi, jenis batasan, dan tanda dari variabel dual. Informasi ini diringkaskan dalam Tabel 5-2 untuk jenis maksimisasi dan minimisasi dari bentuk standar. Ingat sekali lagi bahwa bentuk primal standar mengharuskan semua batasan untuk berbentuk persamaan (dengan sisi kanan nonnegatif jika metode simpleks primal dipergunakan untuk memecahkan masalah primal) dan semua variabel nonnegatif.



HUBUNGAN ANTARA NILAI TUJUAN PRIMAL DAN DUAL Nilai tujuan dalam satu pasangan masalah primal dan dual harus memenuhi hubungan berikut 1. Untuk setiap pasangan primal dan dual yang layak 𝑛𝑖𝑙𝑎𝑖 𝑡𝑢𝑗𝑢𝑎𝑛 𝑛𝑖𝑙𝑎𝑖 𝑡𝑢𝑗𝑢𝑎𝑛 ( )≤( ) 𝑑𝑎𝑙𝑎𝑚 𝑚𝑎𝑠𝑙𝑎𝑎ℎ 𝑚𝑎𝑘𝑠𝑖𝑚𝑎𝑠𝑖 𝑑𝑎𝑙𝑎𝑚 𝑚𝑎𝑠𝑎𝑙𝑎ℎ 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑎𝑠𝑖



45



2. Di pemecahan optimum untuk kedua 𝑛𝑖𝑙𝑎𝑖 𝑡𝑢𝑗𝑢𝑎𝑛 𝑛𝑖𝑙𝑎𝑖 𝑡𝑢𝑗𝑢𝑎𝑛 ( )=( ) 𝑑𝑎𝑙𝑎𝑚 𝑚𝑎𝑠𝑙𝑎𝑎ℎ 𝑚𝑎𝑘𝑠𝑖𝑚𝑎𝑠𝑖 𝑑𝑎𝑙𝑎𝑚 𝑚𝑎𝑠𝑎𝑙𝑎ℎ 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑎𝑠𝑖



Amati dengan hati-hati bahwa kedua hasil ini tidak mengatakan apapun tentang mana masalah primal dan mana masalah dual. Yang penting dalam kasus ini adalah arti optimisasi (maksimisasi dan minimisasi). Untuk membuktikan keabsahan kedua hasil ini, anggaplah (X1, XII) dan Y merupakan pemecahan primal dan dual yang layak, yang bersesuaian dengan definisi primal-dual yang diberikan dalam bentuk matriks di akhir Bagian 5.1. Lalu, dengan mengalikan sebelumnya batasan-batasan dengan Y, kita memperoleh



TAXI + XII = Yb = w



INTERPRETASI EKONOMI DARI MASALAH DUAL Dapat didefiniskan dua indikator ekonomi: harga dual (dual price) dan pengurangan biaya (reduced costs). Secara spesifik, kita me nyatakan bahwa harga dual mewakili nilai per unit dari sumber daya LP. Sebaliknya, pengurangan biaya mewakili kenaikan dalam pengembalian marginal atau penurunan dalam biaya per unit sumber daya yang diperlukan untuk membuat sebuah kegiatan LP (variabel) sekedar menguntungkan. Bagian ini menggunakan masalah primal-dual untuk menerangkan makna ekonomi yang pasti dari harga jual dan pengurangan biaya. Interpretasi ini akan terbukti berguna dalam dua aspek: 1. Memberikan pemahaman mendasar akan model LP sebagai sistem masukan keluaran ekonomi.



46



2. Memungkinkan implementasi analisis sensitivitas atau analisis pascaoptimal secara efisien. Aspek pertama dibahas dalam bab ini. Analisis sensitivitas akan diliput dalam bagian berikutnya. Untuk maksud penyediaan interpretasi ekonomi dari masalah dual, kita menggunakan definisi (non matriks) berikut ini untuk masalah primal dan dual.



HARGA DUAL



Dalam Bagian 5.2. 1 kami memperlihatkan bahwa di pemecahan optimal dari baik masalah primal maupun dual, kita memiliki Z=w Atau 𝑛



𝑚



∑ 𝐶𝑗𝑋𝑗 = ∑ 𝑏𝑖𝑦𝑖 𝑗=1



𝑖=1



Kita dapat memperoleh interpretasi ekonomi dari variabel dual y, dengan menggunakan analisis dimensional berikut ini. Karena sisi kiri dari persamaan tersebut mewakili nilai uang (pengembalian) dan b, mewakili unit (jumlah) sumber i, maka yi, berdasarkan persamaan di atas, pastilah mewakili nilai uang per unit sumber daya i seperti diperlihatkan analisis dimensional berikut ini:



47



(pengembalian) ∑𝑚 𝑖=1



=



(unit sumber daya 1)/$(unit sumber daya )



Jadi variabel dual y, mewakili nilai per unit sumber daya i. Dalam literatur, y, biasanya disebut sebagai harga dual (kadang-kadang istilah harga bayangan juga dipergunakan). Analisis dimensional di atas mengarahkan kita pada sebuah observasi menarik. Kami telah menerangkan dalam Bagian 5.2.1 bahwa untuk pemecahan primal dan dual yang layak dan tidak optimal, kita memiliki isi



Berdasarkan interpretasi ekonomi yang diberikan untuk nilai dual di atas, pertidaksamaan ini menunjukkan bahwa atau (laba) 0, maka x; pastilah nondasar dan karena itu berada di tingkat nol. 2. Jika di pemecahan optimum sebuah variabel dual yi memiliki nilai positif, batasan primal pastilah dipenuhi dalam bentuk persamaan karena nilai slack yang berkaitan dengan nya pastilah nol. ANALISIS PASCA-OPTIMAL ATAU ANALISIS SENSITIVITAS Inti dari analisis pasca-optimal berada dalam penelitian terhadap tabel simpleks umum yang diberikan dalam bentuk matriks. Dengan diketahui masalah LP berikut ini dalam bentuk standar: maksimumkan z = C1X1 + CnXII dengan batasan AXI + IXn = b Asumsikan bahwa B adalah basis saat ini dan anggaplah CB dan XB adalah elemenelemen berkaitan dengannya sebagaimana didefinisikan di sepanjang bab ini. Dengan diketahui dual Y = CBB-1, iterasi simpleks umum yang bersesuaian adalah Dasar z Xb



XI YA - CI B-1A



XII Y - CII B-1



Pemecahan CBB-1b B-1b



Amati dengan seksama bahwa setelah B, CB, dan XB diketahui, keseluruhan tabel dapat dihitung dengan menggunakan B-dan data semula dari masalah tersebut. Analisis pasca-optimal didasari persis oleh observasi ini.



49



Umumnya, dalam analisis pasca-optimal kita berminat untuk mempelajari pengaruh perubahan koefisien fungsi tujuan Cr dan CH dan/atau jumlah sumber daya yang tersedia b. Lihatlah tabel di atas dan perhatikan bahwa perubahan dalam Ci, Cli, dan b tidak memiliki pengaruh apapun terhadap B atau B-. Alasannya adalah bahwa B terdiri dari kolom (A, I) dan selama (A, I tetap tidak berubah, B tetap tidak dipengaruhi. Jadi hal pertama yang ingin kita lakukan dalam analisis pasca-optimal adalah menguji apakah sebuah perubahan tertentu dari (C1, Cn) ke (D1, DII) dan/ atau perubahan dari b ke d akan membuat basis saat ini B optimal dan layak. Jadi, dengan asumsi bahwa tidak ada perubahan dalam B, semua yang perlu kita lakukan adalah mengganti CB dengan DB yang baru dan b dengan d dan lalu menghitung ulang baris tujuan (dengan menggunakan Y = DBB-1) dan sisi kanannya (= B-d). Jika tidak satu pun dari koefisien baris tujuan yang baru tersebut melanggar optimalitas dan tidak satu pun dari koefisien sisi kanan yang baru menjadi negatif, maka B tetap optimal dan layak di nilai yang baru B-d. Jika tidak, bergantung pada apakah optimalitas atau kelayakan (atau keduanya) yang dilanggar, perhitungan tambahan akan diperlukan untuk memperoleh pemecahan baru. Untuk meringkaskan pembahasan di atas, analisis pasca-optimal dapat dimasukkan ke dalam salah satu dari ketiga kategori ini. 1. Perubahan dalam koefisien tujuan (C1, Cli) hanya dapat mempengaruhi optimalitas. 2. Perubahan dalam sisi kanan b hanya dapat mempengaruhi kelayakan. 3. Perubahan simultan dalam (Cı, Cm) dan b dapat mempergaruhi baik optimalitas maupun kelayakan Perhitungan tambahan diperlukan untuk memperoleh pemecahan baru yang bersesuaian yang dapat dimasukkan ke dalam salah satu dari ketiga prosedur ini. 1. Jika tabel menjadi non optimal, terapkan metode simpleks primal terhadap tabel yang baru sampai optimalitas dicapai (atau terdapat bukti bahwa pemecahan baru tersebut tidak dibatasi).



50



2. Jika tabel tersebut menjadi tidak layak, terapkan metode simpleks dual terhadap tabel yang baru sampai kelayakan diperoleh kembali (atau terdapat bukti bahwa pemecahan baru itu tetap tidak layak). 3. Jika tabel tersebut menjadi non optimal dan tidak layak, pertama-tama terapkan simpleks primal terhadap tabel baru tersebut tanpa memperhitungkan ketidaklayakan. Setelah optimalitas dicapai, terapkan metode simpleks dual untuk



memperoleh



kembali



kelayakan.



Prosedur



ini



pada



initinya



menggabungkan prosedur 1 dan 2 secara berurutan. Anda kemungkinkan memikirkan apakah analisis pasca-optimal dapat diperluas untuk mencakup perubahan dalam koefisien batasan (teknologis) A dari model LP tersebut. Ingatlah bahwa B terdiri dari vektor kolom dalam (ASI). Jika perubahan dalam A tidak mempengaruhi B, yaitu, perubahan tersebut hanya terjadi dalam vektor kolom nondasar, B tetap tidak dipengaruhi, dan dari tabel simpleks umum yang diberikan di atas, perubahan dalam A dalam kasus ini hanya akan mempengaruhi baris tujuan can karena itu hanya mempengaruhi optimalitas. Sebaliknya, jika perubahan dalam A mempengaruhi vektor kolom B, berhati-hatilah! Inversi saat ini B-1 tidak lagi absah dan inti dari tabel simpleks tersebut "benar-benar digoyahkan." Tentu saja, kita dapat melanjutkan dan berusaha menghitung ulang B- yang baru dari B yang baru itu. Tetapi, tidak ada dapat diketahui, menghitung ulang B- dapat merupakan tugas yang menjemukan, sehingga mengalahkan maksud pelaksanaan analisis pasca-optimal. Sebagai ringkasan, perubahan dalam matriks teknologis A tidak sesuai dengan analisis pasca-optimal. Jadi, kecuali dalam kasus di mana perubahan dilakukan dalam vektor kolom nondasar A, disarankan untuk memecahkan masalah tersebut dari awal.



PEMROGRAMAN LINIER PARAMETRIK Pemrograman linier parametrik adalah perluasan alamiah dari prosedur analisis pascaoptimal. Pemrograman ini meneliti perubahan dalam pemecahan LP optimum yang disebabkan oleh variasi



51



kontinyu yang ditentukan sebelumnya dalam parameter model yang bersangkutan, seperti ketersediaan sumber daya atau perubahan dalam laba atau biaya marginal. Dalam industri minyak misalnya, di mana LP diterapkan secara sangat berhasil, adalah normal untuk meneliti perubahan dalam pemecahan LP optimal yang dihasilkan dari perubahan dalam ketersediaan dan kualitas minyak mentah. Fungsi yang ditentukan sebelumnya yang mewakili perubahan dalam koefisien model tidak perlu linier, karena fungsi ini tidak memiliki kaitan apapun dengan pemrograman linier. Memperlihatkan fungsi yang umumnya dapat mewakili perubahan dalam ketersediaan sumber daya. Satu-satunya keuntungan dalam memanfaatkan fungsi linier adalah bahwa perhitungan menjadi tidak terlalu rumit. Karena alasan ini, dan agar perhatian kita tidak teralihkan oleh perincian perhitungan, sisa bagian ini hanya berkonsentrasi pada penggunaan fungsi linier. Seperti dalam analisis sensitivitas, kita mempertimbangkan jenis-jenis variasi berikut ini: 1. Variasi dalam koefisien tujuan C. 2. Variasi dalam ketersediaan sumber daya b. 3. Variasi dalam koefisien batasan pj. 4. Perubahan simultan dalam C, b, dan Pj.



52



VI.



PEMROGRAMAN LINIER: MODEL TRANSPORTASI



DEFINISI DAN APLIKASI MODEL TRANSPORTASIA Dalam arti sederhana, model transportasi berusaha menentukan sebuah rencana transportasi sebuah barang dari sejumlah sumber ke sejumlah tujuan. Data dalam model ini mencakup: 1. Tingkat penawaran di setiap sumber dan jumlah permintaan di setiap tujuan. 2. Biaya transportasi per unit barang dari setiap sumber ke setiap tujuan. Karena hanya terdapat satu barang, sebuah tujuan dapat menerima permintaannya dari satu sumber atau lebih. Tujuan dari model ini adalah menentukan jumlah yang harus dikirimkan dari setiap sumber ke setiap tujuan sedemikian rupa sehingga biaya transportasi total diminimumkan. Asumsi dasar dari model ini adalah bahwa biaya transportasi di sebuah rute tertentu adalah proporsional secara langsung dengan jumlah unit yang dikirimkan. Definisi "unit transportasi" akan bervariasi tergantung pada jenis "barang" yang dikirimkan. Misalnya, kita dapat membicarakan unit transportasi sebagai setiap balok baja yang diperlukan untuk membangun jembatan. Atau kita dapat menggunakan beban truk dari sebuah barang sebagai unit transportasi. Bagaimanapun juga, unit penawaran dan permintaan harus konsisten dengan definisi kita tentang "unit yang dikirimkan", Sebuah sumber atau tujuan diwakili dengan sebuah node, Busur yang menghubungkan sebuah sumber dan sebuah tujuan mewakili rute pengiriman barang tersebut. Jumlah penawaran di sumber i adalah a, dan permintaan di tujuan j adalah b. Biaya unit transportasi antara sumber dan tujuan j adalah Cij



53



Anggaplah x mewakili jumlah barang yang dikirimkan dari sumber i ke tujuan j; maka model LP yang mewakili masalah transportasi ini diketahui secara umum sebagai



𝑛 minimumkan z = ∑𝑚 𝑖=1 ∑𝑗=1 𝐶𝑖𝑗𝑋𝑖𝑗



dengan batasan ∑𝑛𝑗=1 𝑋𝑖𝑗 ≤ 𝑎𝑖,



I = 1, 2,……., m



∑𝑛𝑗=1 𝑋𝑖𝑗 ≤ 𝑏𝑗,



j = 1, 2,……., m



Xij ≥ 0



untuk semua I dan j



Kelompok batasan pertama menetapkan bahwa jumlah pengiriman dari sebuah sumber tidak dapat melebihi penawarannya; demikian pula, kelompok batasan kedua mengharuskan bahwa jumlah pengiriman ke sebuah tujuan harus memenuhi permintaannya. Model yang baru digambarkan di atas menyiratkan bahwa penawaran total 1 a; harus setidaknya sama dengan permintaan total = 1 bj. Ketika penawaran total sama dengan permintaan total ( 2 1 a; = = b;), formulasi yang dihasilkan disebut model transportasi berimbang



54



(balanced transportation model). Model ini berbeda dengan model di atas hanya dalam fakta bahwa semua batasan adalah persamaan; yaitu, ∑𝑛𝑗=1 𝑋𝑖𝑗 ≤ 𝑎𝑖,



I = 1, 2,……., m



∑𝑛𝑗=1 𝑋𝑖𝑗 ≤ 𝑏𝑗,



j = 1, 2,……., m



Dalam kehidupan nyata, tidak selalu dapat dipastikan bahwa penawaran sama dengan permintaan atau melebihinya. Tetapi, sebuah model transportasi dapat selalu berimbang. PEMECAHAN MASALAH TRANSPORTASI Dalam bagian ini kami memperkenalkan perincian untuk pemecahan model transportasi. Metode ini menggunakan langkah-langkah metode simpleks secara langsung dan hanya berbeda dalam perincian penerapan kondisi optimalitas dan kelayakan.  Teknik Informasi Langkah 1: Tentukan pemecahan awal yang layak. Langkah 2: Tentukan variabel masuk dari di antara variabel nondasar. Jika semua variabel masuk memenuhi kondisi optimalitas (dari metode simpleks), berhenti; jika tidak, lanjutkan ke langkah 3. Langkah 3: Tentukan variabel keluar (dengan menggunakan kondisi kelayakan) dari di antara variabel-variabel dalam pemecahan dasar saat ini; lalu temukan pemecahan dasar baru. Kembali ke langkah 2.



55



a. Penentuan Pemecahan Awal Definisi umum dari model transportasi dalam Bagian 6.1 mengharuskan bahwa di = j=1 bj. Persyaratan ini menghasilkan satu persamaan independen, yang berarti bahwa model tersebut hanya memiliki M+n- 1 persamaan independen. Jadi, seperti dalam metode simpleks, pemecahan dasar yang layak harus mencakup m +n-1 variabel dasar. Biasanya, jika model transportasi dirumuskan sebagai sebuah tabel simpleks, kita perlu me manfaatkan variabel buatan untuk memperoleh pemecahan dasar awal. Tetapi, ketika tabel trans portasi dipergunakan, pemecahan dasar awal yang layak dapat diperoleh secara mudah dan langsung. Kami menyajikan prosedur yang disebut peraturan sudut barat laut (northwest-corner rule) untuk maksud ini. Dua prosedur lainnya, yang disebut metode biaya terendah (least-cost) dan pendekatan Vogel. Prosedur ini biasanya memberikan pemecahan awal yang lebih baik dalam arti bahwa nilai fungsi tujuan yang bersangkutan adalah lebih kecil. Metode sudut barat laut memulai dengan mengalokasikan jumlah maksimum yang dapat diijinkan oleh penawaran dan permintaan ke variabel X (variabel yang berada di sudut barat laut dari tabel). Kolom (baris) yang sudah dipenuhi lalu disilang, yang menunjukkan bahwa variabel Sisanya dalam kolom (baris) yang disilang tersebut adalah sama dengan nol. Jika sebuah kolom dan sebuah baris dipenuhi secara bersamaan, hanya satu (salah satunya) yang disilang. Kondisi ini menjamin penentuan variabel dasar nol, jika ada, secara otomatis.



56



 Penentuan Variabel Masuk Variabel masuk ditentukan dengan menggunakan kondisi optimalitas dari metode simpleks. seperti diterangkan lebih lanjut dalam bagian ini, perhitungan koefisien persamaan tujuan didasarioleh hubungan primal-dual yang disajikan dalam Bagian 5.2. Kami pertama-tama akan menyajikan mekanika metode ini dan lalu menyediakan penjelasan yang terinci tentang prosedur yang didasari oleh teori dualitas. Metode lainnya, yang disebut prosedur batu loncatan (stepping-stone procedure), juga tersedia untuk menentukan variabel masuk. Walaupun perhitungan dalam kedua metode ini tepat setara, metode batu loncatan memberikan kesan bahwa prosedur ini sepenuhnya tidak berkaitan dengan metode simpleks. b.



Penentuan Variabel Keluar (Konstruksi Loop)



Langkah ini setara dengan penerapan kondisi kelayakan dalam metode simpleks. Tetapi, karena semua koefisien batasan dalam model transportasi semula adalah nol atau 1, rasio (positif) dari kondisi kelayakan akan selalu memiliki penyebut yang sama dengan 1. Jadi nilai variabel dasar akan secara langsung memberikan rasio yang bersangkutan. Untuk maksud penentuan rasio minimum, kita mengembangkan loop tertutup untuk variabel masuk saat ini (x31 dalam iterasi saat ini). Loop berawal dan berakhir di variabel nondasar yang ditunjukkan. Loop ini terdiri dari segmen horizontal dan vertikal (yang tersambung) yang ujung ujungnya haruslah variabel dasar, kecuali untuk titik-titik akhir yang berkaitan dengan variabel masuk. Ini berarti bahwa setiap elemen sudut dari loop ini haruslah sebuah sel yang memuat sebuah variabel dasar. Tidak menjadi masalah apakah loop tersebut ditelusuri searah atau berlawanan arah dengan jarum jam. Amati bahwa untuk satu pemecahan dasar tertentu, hanya satu loop yang unik yang dapat dikembangkan untuk setiap variabel nondasar



57



disesuaikan sebagai berikut. Turunkan x dengan satu unit, naikkan x12 dengan satu unit, fununkan 92 dengan satu unit, naikkan X24 dengan satu unit, dan akhirnya turunkan xu dengan satu unit. Proses ini diringkaskan dengan tanda plus dan minus e di sudut-sudut yang sesuai dalam Tabel 6-10. Perubahan ini akan mempertahankan batasan penawaran dan permintaan tetap dipenuhi. Variabel keluar dipilih dari di antara variabel-variabel sudut dari loop ini yang akan menurun ketika variabel masuk x meningkat melewati tingkat nol. Ini ditunjukkan dalam Tabel 6-10 dengan variabel dalam kotak-kotak yang diberi label dengan tanda minus O. Dari Tabel 6-10, 11, X22. dan X34 adalah variabel dasar yang akan menurun ketika x meningkat. Variabel yang memiliki nilai terkecil lalu dipilih sebagai variabel keluar, karena variabel itu akan menjadi variabel pertama yang mencapai nilai nol dan setiap penurunan lebih lanjut akan menyebabkan nilainya menjadi negatif (bandingkan kondisi kelayakan dari metode simpleks di mana variabel keluar dikaitkan dengan rasio minimum). Dalam contoh ini tiga variabel 0,x, x22, dan x34 memiliki nilai yang sama (