PENDAHULUAN. Modul : KKMI3413-Teknik Riset Operasional Hal : 45

Modul : KKMI3413-Teknik Riset Operasional

Hal : 45

1 PENDAHULUAN 1.1. Sejarah Singkat Operations Research merupakan pendekatan pengambilan keputusan manajerial yang didasarkan atas metode-metode ilmiah yang menggunakan banyak analisis kuantitatif. Berbagai nama diberikan untuk bidang ilmu yang melibatkan

pendekatan-pendekatan

kuantitatif,

diantaranya

“Management

Science” (Manajemen Sains). Operations Research diterjemahkan sebagai Riset Operasi (OR), Penelitian Operasional, dan Teknik Riset Operasi (TRO). Revolusi manajemen sains pada awal 1900an yang dicetuskan Frederic W. Taylor, memberikan dasar bagai Riset Operasi.

Namun Riset Operasi modern

umumnya dianggap muncul selama periode Perang Dunia II, ketika tim OR dibentuk untuk menangani masalah-maslah strategis dan taktis yang dihadapi militer. Tim ini terdiri dari para ahli matematika, teknik, dan perilaku bersama-sama memecahkan masalah dengan menggunakan metode ilmiah.

Setelah perang usai , banyak

anggota tim ini melanjutkan penelitian dengan pendekatan kuantitatif untuk pengambilan keputusan. Pada masa Perang Dunia II, angkatan perang Inggris membentuk suatu tim yang terdiri atas para ilmuwan untuk mempelajari untuk mempelajari persoalanpersoalan strategi dan taktik sehubungan dengan serangan-serangan yang dilancarkan musuh terhadap negaranya. Tujuan mereka adalah untuk menentukan penggunaan sumber-sumber militer yang terbatas, seperti radar dan bomber dengan cara yang palin efektif. Karena tim tersebut melakukan penelitian terhadap operasi-operasi militer, maka muncullah nama “Military Operations Research”. Keberhasilan angkatan perang Inggris ini kemudian mendorong angkatan perang Amerika untuk melakukan aktifitas serupa dengan membentuk tim Operations Research. Setelah Perang Dunia II berakhir, OR yang lahir di Inggris berkembang pesat di Amerika khususnya bagi kalangan industri, konsultan, perguruan tinggi, perencanaan kota dan dunia bisinis. Perkembangan yang sangat berarti adalah penemuan George Dantzig pada tahun 1947 atas metode simpleks yang digunakan untuk memecahkan masalah pemograman linier. Kemudian pada tahun 1957, buku pertama mengenai

BRIDON SILABAN, IR, MBA

STMIK BUDIDARMA


Hal : 46

OR diterbitkan oleh Churchman, Ackoff, dan Arnoff yang berjudul “Introduction to Operation Research”. Perkembangan OR semakin pesat karena peningkatan besar dalam kemampuan

komputasi

sebagai

akibat

tersedianya

komputer.

Komputer

memungkinkan para praktisi menggunakan metodologi yang lebih cangkih untuk memecahkan berbagai masalah industri. Lahirnya bahasa pemograman seperti Visual Basic, Java, C/C++ sangat mendukung perkembangan OR, dimana persoalan yang rumit dan berskala besar, dapat diselesaikan dengan cepat, tepat dan akurat, yang berdampak positif terhadap pengambilan keputusan. 1.2.

Pemecahan Masalah dan Pengambilan Keputusan Pemecahan masalah merupakan proses pengidentifikasian perbedaan

antara kondisi aktual dan kondisi yang diinginkan serta kemudian mengambill tindakan untuk mengatasi perbedaan tersebut. Tahap-tahap pemecahan masalah. 1.

Mengidentifikasi dan mendefenisikan masalah

2.

Menentukan berbagai alternatif pemecahan

3.

Menentukan kriteria yang akan digunakan untuk mengevaluasi berbagai alternatif

4.

Mengevaluasi berbagai alternatif

5.

Memilih alternatif

6.

Menerapkan alternatih yang terpilih

7.

Mengevaluasi

hasilnya

dan

menentukan

apakah

pemecahan

telah

memuaskan. Pengambilan keputusan berhubungan dengan langkah pertama sampai dengan langkah kelima pada proses pemecahan masalah. Dalam menyelesaikan persoalan yang berkaitan dengan pengambilan keputusan ini, harus diidentifikasikan lebih dahulu dua komponen utama, yaitu tujuan (objective) dan variabel-variabel. Tujuan adalah hasil akhir yang hendak dicapai dengan cara memilih suatu tindakan yang paling tepat untuk sistem yang dipelajari.

Dalam bidang usaha,

tujuan diartikan sebagai “memaksimumkan keuntungan” atau “meminimumkan biaya”. Dalam bidang-bidang lain yang sifatnya non profit, tujuan dapat berupa “pemberian kualitas pelayanan kepada pelanggan”. Apabila tujuan telah didefenisikan, maka harus dilakukan pemilihan tindakan terbaik yang dapat mencapai tujuan tersebut. Untuk dapat menentukan tindakantindakan yang mungkin dilakukan, maka harus diidentifikasi variabel-variabel sistem yang dapat dikendalikan oleh pengambil keputusan.


STMIK BUDIDARMA


Hal : 47

1.3. Analisa Kuantitatif. Tahap

pendefenisian

masalah

dari

proses

pengambilan

keputusan

merupakan komponen paling kritis dalam menentukan keberhasilan atau kegagalan pendekatan

kuantitatif

untuk

pengambilan

keputusan.

Pada

umumnya

membutuhkan imajinasi, kerjasama dan banyak upaya untuk mengubah deskripsi masalah secara umum menjadi defenisi masalah yang baik, yang dapat menggunakan pendekatan kuantitatif. Agar berhasil dalam analisis kuantitatif untuk pengambilan keputusan, ahli OR harus bekerja sama dengan manajer atau pengguna keputusan. Apabila kedua telah sepakat, ahli OR mulai bekerja mengembangkan model yang dapat digunakan. 1.4.

Paket Programa QSB+ (Quantitative System for Business Plus) Pada saat ini telah banyak tersedia paket program yang dapat digunakan

untuk memecahkan dalam OR, diantaranya LP, LPV2, Simplex, QPTO, LPROG, QSB, QSB+. Topik OR yang disediakan dalam paket program QSB+ adalah : •

Program Linier (Liniear Programming)

•

Integer Liniear Programming

•

Masalah Transportasi (Transportation and Transshipment)

•

Masalah Penugasan (Assignment and Traveling Salesman)

•

Analisa Jaringan ( Network Analysis)

•

CPM and PERT

•

Dynamic Programming

•

Inventory Control

•

Teori Antrian

•

Simulasi Sistem ASntrian

•

Teori Keputusan dan Probabilitas

•

Teori Markov

•

Time Series Forecasting


STMIK BUDIDARMA


Hal : 48

2 PROGRAMA LINIER 2.1. Pendahuluan Programa linier yang diterjemahkan dari Liniear Programaming (LP) adalah suatu cara untuk menyelesaikan persoalan pengalokasian sumber-sumber yang terbatas di antara beberapa aktivitas yang bersaing, dengan cara yang terbaik yang mungkin dilakukan. Persoalan pengalikasian ini akan muncul apabila seseorang harus

memilih

tingkat

aktivitas-aktivitas

tertentu

yang

bersaing

dalam

hal

penggunaan sumber daya yang terbatas yang di butuhkan untuk melaksanakan aktivitas-aktivitas tersebut. Beberapa contoh situasi dari uraian di atas antara lain ialah persoalan pengalokasian fasilitas produksi, , solusi permainan (game), dan pemilihan pola pengiriman (shipping). Satu hal yang menjadi cirri situasi di atas ialah adanya keharusan untuk mengalokasikan sumber terhadap aktivitas. Programa linier ini menggunakan model matematis untuk menjelaskan persolaan yang dihadapinya. Sifat “linier” di sini memberi arti bahwa seluruh fungsi matematis dalam model ini merupakan fungsi yagn linier. Sedangkan kata “Programaa”

merupakan

sinonim

untuk

perencanaan.

Dengan

demikian,

Programaa linier (LP) adalah perencanaan aktivitas-aktivitas untuk memperoleh suatu hasil yang optimum, yaitu suatu hasil yang mencapai tujuan terbaik di antara seluruh alternative yang layak/fisibel. George B. Dantzig merupakan ahli matematika yang diakui sebagai pioneer Programa Linier. Selama perang Dunia II Danzig bekerja pada Angkatan Udara Amerika Serikat , dia bekerjasama dengan Von Neumann, Hurwicz dan Koopmans , melahirkan “Programa Saling Ketergantungan Kegiatan – Kegiata dalam Struktur linier”, kemudian disebut Linearr Programaming. Pada tahun 1947 Dantzig mempublikasikan “Metode Simplek”. Kemudian bekerjasama dengan Marshall Wood dan Alex Orden dalam pengembangan “Metode Simplek”. Pada awalnya metode simplek diterapkan pada masalah-masalah militer, seperti logistik, transportasi dan perbekalan. Sejalan dengan perkembangannya, linier Programaming sudah diaplikasikan hampir kesemua bidang

yang didukung

dengan perkembangan yang sangat pesat bidang ilmu komputer.


STMIK BUDIDARMA


Hal : 49

Sebagai ilustrasi, perhatikan contoh soal berikut : Contoh 2.1 PT. Sayang Anak memproduksi dua jenis mainan yang terbuat dari kayu, yang berupa boneka dan kereta api. Boneka dijual dengan harga Rp 27.000/lusin yang setiap lusinnya memerlukan biaya material sebesar Rp 10.000 serta biaya tenaga kerja sebesar Rp 14.000. Kereta api yang dijual seharga Rp 21.000/lusin memerlukan biaya material sebesar Rp 9.000 dan biaya tenaga kerja sebesar Rp 10.000. Untuk membuat boneka dan kereta api ini diperlukan dua kelompok tenaga kerja, yaitu tukang kayu dan tukang poles. Setiap lusin boneka memerlukan 2 jam pemolesan dan 1 jam pekerjaan kayu, sedangkan setiap lusin kereta api memerlukan 1 jam pemolesan dan 1 jam pekerjaan kayu. Meskipun pada setiap minggunya perusahaan ini dapat memenuhi seluruh material yang diperlukan, jam kerja yang tersedia hanya 100 jam utnuk pemolesan dan 80 jam untuk pekerjaan kayu. Dari pengamatan pasar selam ini dapat dikatakan bahwa kebutuhan akan keretea api tidak terbatas, tetapi untuk boneka tidak lebih dari 40 lusin yang terjual setiap minggunya. Bagaimanakah formulasi dari persoalan di atas untuk mengetahui berapa lusin jenis mainan masing-masing yang harus dibuat setiap minggu agar diperoleh keuntungan yang maksimum? Dalam membangun model dari formulasi persoalan di atas akan digunakan karakteristik-karakteristik yang biasa digunakan dalam persoalan Programaa linier, yaitu : a. Variabel keputusan Variabel keputusan adalah variable yang menguraikan secara lengkap keputusan-keputusan yang akan dibuat. Dalam persoalan ini, variable keputusan akan menentukan berapa banyak boneka dan kereta api masing-masing harus dibuat setiap minggunya. Misalkan : x1 = banyaknya boneka yang dibuat setiap minggu x2 = banyaknya kereta api yang dibuat setiap minggu. b. Fungsi tujuan Fungsi tujuan merupakan fungsi dari variable keputusan yang akan dimaksimumkan (untuk pendapatan atau keuntungan) atau diminimumkan (untuk ongkos). Pada persoalan ini akan di maksimumkan (pendapatan/minggu) – (ongkos material/minggu) – (ongkos tenaga kerja/minggu). Pendapatan dan ongkos-ongkos ini dapat

diekspresikan dengan menggunakan

variable keputusan x1 dan x2 sebagai berikut :


STMIK BUDIDARMA


Hal : 50

Pendapatan/minggu = pendapatan/minggu dari boneka + pendapatan/minggu dari KA. = 27x1 +21x2 Ongkos material/minggu = 10x1 + 9x2 Ongkos tenaga kerja/minggu = 14x1 + 10x2 Sehignga yang akan dimaksimumkan adalah : (27x1 + 21x2) – (10x1 + 9x2) – (14x1 + 10x2) = 3x1 + 2x2 Catatan : ongkos dan pendapatan dalam ribuan rupiah. Untuk menyatakan nilai fungsi tujuan ini akan digunakan variable z sehingga fugnsi tujuannya menjadi : Maksimumkan z =3x1 + 2x2 c. Pembatas Pembatas merupakan kendala yagn dihadapi sehingga kita tidak bisa menentukan harga-harga varibel keputusan secara sembarang. Pada persoalan di atas ada 3 pembatas yang kita hadapi, yaitu : Pembatas 1 : Setiap minggu tidak lebih dari 100 jam waktu pemolesan yang dapat di gunakan. Pembatas 2 : Setiap minggu tidak lebih dari 80 jam waktu pengerjaan kayu yang dapat digunakan. Pembatas 3 : Karena permintaan yang terbatas, maka tidak lebih dari 40 lusin boneka yang dapat di buat setiap minggu. Jumlah material yang dapat di gunakan diasumsikan tidak terbatas sehingga tidak ada pembatas untuk hal ini. Selanjutnya, ekspresikan pembatas- pembatas itu ke dalam x1 dan x2 sebagai berikut : Pembatas 1 : 2x1 + x2 ≤ 100 Pembatas 2 : x1 + x2 ≤ 80 Pembatas 3 : x1 ≤ 40 Koefisien dari variabel keputusan pada pembatas disebut koefisien teknologis, sedangkan bilangan yang ada di sisi kanan setiap pembatas disebut ruas kanan pembatas. d. Pembatas tanda Pembatas tanda adalah pembatas yang menjelaskan apakah variabel keputusannya diasumsikan hanya berharga nonnegative atau variabel keputusan tersebut boleh berharga positif, boleh juga negative (tidak terbatas dalam tanda). Pada contoh soal di atas kedua varibel keputusan harus berharga nonnegative sehingga harus dinyatakan bahwa


STMIK BUDIDARMA


Hal : 51

x1 ≥ 0 x2 ≥ 0 Dengan demikian, formulasi lengkap dari persoalan PT. Sayang Anak adalah : Maksimumkan

z = 3x1 + 2x2

Berdasarkan 2x1 + x2 ≤ 100 x1 + x2 ≤ 80 x1 ≤ 40 x1 ≥ 0 x2 ≥ 0 Contoh 2.2 PT. Indah Gelas adalah suatu perusahaan yang memproduksi kaca berkualitas tinggi untuk digunakan sebagai jendela dan pintu kaca. Perusahaan ini memiliki tiga buah pabrik, pabrik 1 yang membuat bingkai aluminium, pabrik 2 yang membuat bingkai kayu, dan pabrik 3 yang digunakan utnuk memproduksi kaca dan merakit produk keseluruhan. Saat ini perusahaan mendapat pesanan berupa dua macam produk baru yang potensial, yaitu kaca setinggi 8 kaki dengan bingkai aluminium (produk 1), dan jendela berukuran 4 x 6 kaki dengan bingkai kayu (produk 2). Karena perusahaan sedang mengalami penurunan pendapatan sebagai akibat resesi dunia, maka pimpinan perusahaan merasa perlu untuk memperbaiki/mengubah lintasan produksinya dengan cara menghentikan pembuatan beberapa produk yang tidak menguntungkan sehingga kapasitas produksi dapat digunakan untuk membuat salah satu atau kedua produk baru yang potensial tersebut. Kepala bagian pemasaran telah menyimpulkan bahwa perusahaan harus dapat menjual kedua produk itu sebanyak-banyaknya, yaitu sejumlah yang dapat dibuat dengan kapasitas yang ada. Akan tetapi, karena kedua produk itu akan bersaing untuk menggunakan kapasitas produksi yang sama di pabrik 3, maka persoalannya ialah : Berpa

banyakkah

masing-masing

produk

harus

dibuat

sehingga

deperoleh

keuntungan terbaik? Untuk menyelesaikan persoalan di atas, terlebih dahulu harus dicari mengenai : 1. Persentase kapasitas produksi masing-masing pabrik yang dapat digunakan untuk kedua macam produk tersebut. 2. Persentase kapasitas yang diperlukan oleh masing-masing produk untuk setiap unit yang diproduksi per menit. 3. Keuntungan per unti untuk masing-masing produk. Informasi mengenai ketiga hal di atas diberikan pada Tabel 2.1 berikut ini :


STMIK BUDIDARMA


Hal : 52

Tabel 2.1. Data untuk PT. Indah Gelas Produk

Kapasitas yang digunakan/ unit

Kapasitas yang

Ukuran produksi

Dapat digunakan

Pabrik

1

2

1

1

0

4

2

0

2

12

3

3

2

18

Keuntungan/Unit

$3

$5

Karena kapasitas yang telah digunakan oleh suatu produk di pabrik 3 menyebabkan produk lain tidak dapat menggunakannya, maka persoalan di atas dikenal sebagai persoalan Programaa linier dengan tipe “campuran produk” atau product mix. Untuk memformulasikan model metematis dari persoalan ini, kita tentukan x1 dan x2 sebagai jumlah unit dari produk 1 danproduk 2 yang diproduksi per menit, dan kita tentukan pula z sebagai keuntungan yang diperoleh per menit. Dengan demikian maka x1 dan x2 menjadi variabel-variabel keputusan dari model ini, dan tujuannya adalah memilih harga-harga x1 dan x2 sehingga diperoleh nilai maksimum dari : Z = 3x1 + 5x2 berdasarkan pembatas yang ada, yaitu kapasitas pabrik yang dapat di gunakan. Tabel 2,1 diatas memberikan implikasi bahwa setiap unit

produk 1 yang

diproduksi per menit akan menggunakan 1 persen dari kapasitas pabri k1, padahal kapasitas yang dapat digunakan hanya 4 persen. Pembatas ini dinyatakan secara matematis dengan ketidaksamaan x1 ≤ 4. Dengan cara yang sama, pabrik 2 memiliki pembatas 2x2 ≤ 12. Persentase kapasitas pabrik 3 digunakan dengan cara memilih x1 dan x2 sebagai produk-produk baru tersebut sehingga ukuran produksinya adalah 3x1 + 2x2. Karena itu, secara matematis pembatas dari pabrik 3 ini adalah 3x1 + 2x2 ≤ 18. Karena ukuran produksi ini tidak mungkin berharga negative, maka variabelvariabel keputusan ini dibatasi sehingga berharga nonnegative dengan x1 ≥ 0 dan x2 ≥ 0. Sebagai kesimpulan, persoalan di atas dapat dinyatakan secara matematis sebagai berikut : Maksimumkan

z = 3x1 + 5x2

berdasarkan x1

≤

4

2x2

≤

12

3x1 + 2x2

≤

18

dan


STMIK BUDIDARMA


Hal : 53

x1 ≥ 0, x2 ≥ Dari ilustrasi di atas dpat ditarik kesimpulan mengenai pengertian persoalan Programaa linier sebagai berikut : Persoalan Programaa linier (LP) adalah suatu persoalan optimasi di mana kita melakukan hal-hal berikut ini : 1.

Kita berusaha memaksimumkan atau meminimumkan suatu fungsi linier dari variabel-variabel keputusan yang disebut fungsi tujuan.

2.

Harga/besaran dari variabel-variabel keputusan itu harus memenuhi suatu set pembatas.

Setiap

pembatas

harus

merupakan

persamaan

linier

atau

ketidaksamaan linier. 3.

Suatu pembatas tanda dikaitkan dengan setiap variabel. Untuk setiap variabel xi harus nonnegative (x1 ≥ 0) atau xi tidak terbatas dalam tanda.

Definisi : Suatu fungsi f (x1, x2,…,xn) dari x1, x2,…,xn adalah fungsi linier jika dan hanya untuk sejumlah set kontanta c1, c2,…, cn berlaku f (x1, x2,…, xn) = c1x1 + c2x2 +… + cnxn Sebagai contoh, f (x1, x2) = 2 x1 + x2 adalah fungsi linier dari x1 dan x2, tetapi 2 x12 + x2 vukan fungsi linier dari x1 dan x2. Untuk setiap fungsi linier f (x1, x2, …, xn) dan setiap bilangan b, ketidaksamaan f (x1, x2, …, xn) ≤ b dan f (x1, x2, …, xn) ≥ b adalah ketidaksamaan linier. Sebagai contoh, 2x1 + 3x2 ≤ 3 dan 2x1 + x2 ≥ 3 adalah ketidaksamaan linier, sedangkan 2 x12 + x2 ≥ 3 bukanlah ketidaksamaan linier. 2.2. Model Programa Linier Tabel 2.2. Data Model Programa Linier Aktivitas

Penggunaan Sumber/Unit 1

2

……….

Banyaknya N

Sumber

yang

digunakan

Sumber 1

a11

a12

………..

a1n

b1

2

a21

a22

………..

a2n

b2

.

.

.

.

.

.

.

.

.

m

am1

am2

………..

amn

δ Z/Unit

C1

C2

……….

Cn

Tingkat

X1

X2

……….

Xn

bm

Berdasarkan table diatas dapat dibuat formulasi model matematis Programa Linier.


STMIK BUDIDARMA


Hal : 54

Fungsi Tujuan : Maksimumkan Z = C1X1 + C2X2 + C3X3 + . . . . . . + CnXn Batasan/Kendala : a11X1 + a12X2 + a13X3 + ……………………..+ a1nXn ≤ b1 a21X1 + a22X2 + a23X3 + ……………………..+ a2nXn ≤ b2 a31X1 + a32X2 + a33X3 + ……………………..+ a3nXn ≤ b3 . am1X1 + am2X2 + am3X3 + …………………..+ amnXn ≤ bm dan ,

X1 ≥ 0 , X2 ≥ 0, X3≥0,………………

Xn ≥ 0

Catatan : Yang harus dicari adalah X1, X2, …………Xn Bentuk model diatas disebut Bentuk Standar Persoalan Programa Linier

2.3. Asumsi Model Programa Linier Sebenarnya asumsi-asumsi dasar Programa Linier telah tersirat pada model matematis yang telah dibahas. Tetapi ada baiknya membahas asumsi-asumsi tersebut agar terperinci. Asumsi-asumsi Programa linier menuntut agar hubungan fungsional

dalam

masalah

bersifat

linier/proporsional,

aditif,

divisibility,

dan

deterministic. a. Linierity/Proportionality (Linier/proporsional ) Persyaratan uatama pada Programa Linier adalah bahwa fungsi tujuan (Z) dan semua kendala harus linier. Jika suatu kendala dengan 2 variabel keputusan dalam diagram dimensi 2, maka akan berbentuk garis lurus. Demikian juga apabila 3 variabel, maka akan menghasilkan bidang datar. Linier berarti bahwa hubungannya proporsional artinya tingkat perubahan atau hubungan fungsional adalah konstan.

Perubahan nilai variabel akan

mengakibatkan perubahan relative nilai fungsi tujuan dalam jumlah yang sama. Contoh: Z = C1X1 + C2X2 + C3X3 + ………… + CnXn Setiap pertambahan 1 unit X1 akan menaikkan Z dengan C1 Setiap pertambahan 1 unit X2 akan menaikkan Z dengan C2 Dan seterusnya. a11X1 + a12X2 + a13X3 + ……………………..+ a1nXn ≤ b1 Setiap pertambahan 1 unit

X1 akan menaikkan penggunaan sumber

daya/fasilitas 1 dengan a11. Setiap pertambahan 1 unit

X2 akan menaikkan penggunaan sumber

daya/fasilitas 1 dengan a12.


STMIK BUDIDARMA


Hal : 55

b. Additivity Asumsi ini berarti bahwa nilai tujuan tiap kegiatan tidak saling mempengaruhi, dianggap bahwa kenaikan dari nilai tujuan (Z) yang diakibatkan oleh kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi bagian nilai Z yang diperoleh dari kegiatan lain. Contoh: Z = 3X1 + 5X2 Dimana , X1 = 10 ; X2 = 2. Maka,

Z = 3(10) + 5(2) = 40

Jika X1 bertambah 1 unit, maka sesuai dengan asumsi pertama , maka nilai Z menjadi 40 + 3 = 43 Nilai 3 merupakan kenaikan X1 yang dapat langsung ditambahkan pada nilai Z mula-mula tanpa mengurangi bagian Z yang diperoleh dari kegiatan 2(X2). Dengan kata lain tidak korelasi antara X1 dan X2 c. Divisibility. Divisibility berarti bahwa output yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan, demikian juga dengan nilai Z yang dihasilkan. d. Deterministic. Semua parameter model (cj,aij, dan bj) diasumsikan diketahui dengan kepastian.

Dalam kenyataannya, parameter model jarang bersifat deterministic,

karena mencerminkan kondisi masa depan maupun sekarang, dan keadaan masa depa jarang diketahui dengan pasti. Analisis sensitivitas merupakan suatu teknik yang dikembangkan untuk menguji nilai solusi, bagaimana kepekaannya terhadap perubahan-perubahan parameter.


STMIK BUDIDARMA


Hal : 56

3 TEKNIK PEMECAHAN PROGRAMA LINIER Ada dua cara yang digunakan untuk menyelesaikan persoalan Programa linier, yaitu Metode Grafis dan Metode Simplek. Metode Grafis dipergunakan apabila persoalan Programa linier itu hanya mempunyai dua variabel. Namun demikian metode ini telah memberikan petunjuk penting bahwa dalam pemecahanPrograma linier , kita hanya perlu memperhatikan titik ekstrim (titik terjauh) pada ruang solusi atau daerah fisibel.

Petunjuk inilah

sebagai kunci dalam mengembangkan “Metode Simplek”. 3.1.

Metode Grafis.

Untuk menjelaskan metode grafis, akan kita berikan contoh Programa linier dengan persoalan maksimasi dan minimasi. 3.1.1. Persoalan Maksimasi. Sebuah perusahaan sepatu “Maryland” yang bermarkas di Mareland memproduksi 2 jenis sepatu, yaitu sepatu dengan sol karet dan sepatu dengan sol kulit. Untuk membuat sepatu tersebut, dibutuhkan 3 jenis mesin yaitu, mesin I khusus membuat sol dari karet, mesin II khusus membuat sol dari kulit dan mesin III khusus menggabungkan bagian atas sepatu dengan sol sepatu. Untuk membuat sepatu dari sol karet per lusin dibutuhkan waktu pengerjaan 2 jam pada mesin I, dan 6 jam pada mesin III. Sedangkan untuk membuat sepatu dengan sol dari kulit per lusin dibutuhkan 3 jam pada mesin II dan 8 jam pada mesin III. Dalam satu minggu, mesin I hanya dapat bekerja 5 jam, mesin II 15 jam dan mesin III 30 jam. Sedangkan keuntungan yang diperoleh dari setiap lusin sepatu sol karet sebesar Rp. Rp. 30.000,- dan sepatu sol kulit Rp. 50.000,-. Dalam kasus ini , masalah yang dihadapi adalah menentukan jumlah masingmasing sepatu yang harus diproduksi agar memperoleh keuntungan maksimum.


STMIK BUDIDARMA


Hal : 57

Penyelesaian: 1. Buat Data Tabel Perusahaan Marylan. Tabel 3.1. Data Perusahaan Sepatu “Maryland” I2 Kapasitas Maks I1 Merek Sepatu Mesin I II III Keuntungan(10.000) Jumlah Produksi

2 0 6 3 X1

5 5 X2

0 3

8 15 30

X1 = jumlah produksi sepatu sol karet (I1) X2 = jumlah sepatu sol kulit ( I2) 2. Buat model matematis fungsi tujuan dan fungsi pembatas. Fungsi Tujuan. Maksimumkan Z = 3 X1 + 5 X2 Batasan/Kendala 2X1 + 0X2 ≤ 8 atau 2X1 ≤ 8 ………….. 0X1 + 3X2 ≤ 15 3X2 ≤ 15 ………….. (2) 6X1 + 5X2 ≤ 30 ………………………………………. (3) X1 >= 0 ; X2 >= 0

(1)

3. Gambarkan grafik fungsi pembatas, dengan membuat grafik berdimensi dua, dimana X1 (sepatu sol karet) dan X2 (sepatu sol kulit) sebagai sumbusumbunya. Setelah seluruh fungsi pembatas digambarkan, maka akan diperoleh daerah yang berlaku untuk ketiga fungsi tersebut.(lihat gambar 3.1.) 4.

Gambarkan fungsi Tujuan. Gambarkan fungsi tujuan dengan cara menentukan nilai Z terlebih dahulu (dalam hal ini ambiil nilai Z1 = 20). Kemudian geser nilai Z sejajar dengan Z1 sehingga bersinggungan dengan daerah fisibel. Dalam hal ini kita mencoba dan mencoba lagi sehingga ditemukan titik singgungnya.

Untuk menentukan titik singgung : 3X2 = 15 x5 x3 6X1 + 5X2 = 30 ---------------------------------- (-)

15 X2 = 75 18X1 + 15X2 = 90 ------------------------------------ (-) - 18 X1= -15

X1

=

0,833

X2

=

5

Jadi fungsi tujuan bersinggungan dengan daerah fisibel pada titik X1 = 0,833 dan X2 = 5 dengan nilai Z = 27,5. (Keuntungan)

Grafik fungsi pembatas dan fungsi tujuan

dapat dilihat pada gambar 3.1 di bawah ini.


STMIK BUDIDARMA


Hal : 58

Gambar 3.1. Grafik fungsi pembatas dan fungsi tujuan Kasus Maksimasi X2 6

A

Daerag A B C D merupakan Daerah fisible (layak)

B

5 4 3 2 1 0

Daerah Fisibel 1

2

C 3

4

D

5

6

7

X1

Z1 = 3X1+ 5X2 =21 3.1.2. Persoalan Minimasi. PT. Putri Srikandi memproduksi dua jenis mobil, yaitu jenis sedan dan truk. Dalam rangka menaikkan penjualan pihak perusahaan memutuskan melakukan promosi melalui acara televise (TV). Ada dua acara yang tersedia, yaitu pada acara hiburan dan olahraga. Berdasarkan hasil survey, acara hiburan ditonton 7 juta pemirsa wanita dan 2 juta pemirsa pria. Sedangkan acara olahraga ditonton 2 juta wanita dan 12 juta pria.

Biaya promosi pada acara hiburan Rp. 5.000.000,- per menit,

sedangkan pada acara olahraga

Rp 10.000.000,- per menit. Pihak perusahaan

menginginkan promosi disaksikan oleh 28 juta pemirsa wanita dan 24 juta pemirsa pria, apa strategi promosi perusahaan tersebut.


STMIK BUDIDARMA


Hal : 59

Penyelesaian. Variabel Keputusan. X1

= lamanya promosi dalam acara hiburan

X2

= lamanya promosi dalam acara olahraga Data Perusahaan PT. Putri Srikandi Hiburan Jenis Acara

Olahraga

Kapasitas Maks

Pemirsa Wanita (W) Pria (P)

Biaya/menit Juta)

(Rp.

Lama Promosi

7 2

2 12

5

10

X1

X2

28 24

Tujuan dari permaslalahan ini adalah untuk menekan biaya atau meminimkan biaya, maka persolannya adala Minimasi. Fungsi Tujuan Minimumkan Z = 5 X1 + 10 X2 Fungsi Pembatas 7X1 + 2X2 ≥ 28 2X1 + 12X2 ≥ 24 X1 ≥ 0 ; X2 ≥ 0


STMIK BUDIDARMA


Hal : 60

Grafik fungsi pembatas dan fungsi tujuannya dapat dilihat pada gambar 3.2. dibawah ini. X2 15 14

A

13

Daerah A B C merupakan daerah fisibel (layak)

7X1 + 2X2 28

12 11 10 9 8 7 6

Daerah fisibel

5 4 3 2

B

1 0

C 1

2

3

4

5

6

7

8

9

10

11

12

13

X1

Z1 = 30 = 5X1 + 10X2 Gambar 3.2 Grafik fungsi pembatas dan fungsi tujuan Kasus Minimasi 3.1.3. Kasus Khusus Pada masalah perusahaan Maryland an PT. Putri Srikandi yang telah dibahas dengan metode grafik, kita memperoleh hanya satu solusi optimal. Akan tetapi ada kasus dimana solusinya tidak demikian, yang kita sebut kasus khusus, seperti : 1. Memiliki solusi optimal yang tidak terbatas yang

disebut

juga

mempunyai

solusi

alternative atau bersolusi optimal banyak. Contoh : Maksimumkan

Z = 3X1 + 2X2

Fungsi Pembatas (1/40) X1 + (1/60) X2 ≤ 1 (1/50) X1

+ (1/50) X2 ≤ 1

X1 ≥ 0 ; X2 ≥ 0 2. Tidak mempunyai solusi fisibel


STMIK BUDIDARMA


Hal : 61

Contoh : Z = 3X1 + 2X2

Maksimumkan Fungsi Pembatas

(1/40) X1 + (1/60) X2 ≤ 1 (1/50) X1

+ (1/50) X2 ≤ 1 X1 ≥ 30 X2 ≥ 20 3. Mempunyai ruang solusi yang tidak terbatas, kasus dimana nilai Z yang sangat besar (tidak terbatas).

Contoh : Maksimumkan

Z = 2X1 - X2

Fungsi Pembatas X1 - X2

≤ 1

2X1 + X2 ≥ 6 X1 ≥ 0 ; X2 ≥ 0 3.2. Metode Simplek. 3.2.1. Bentuk Umum

Maksimumkan atau Minimumkan

Z =

n

∑ Cjxj j =i

Dengan syarat : Xj

aijxj (≤, = , ≥) bi, untuk semua I (i=1,2,3,……m) semua xj>=0

: banyaknya kegiatan j, dimana j = 1,2,3,…………n ( berarti terdapat n variable keputusan)

Z

: nilai fungsi tujuan (maksimum atau minimum)

Cj

: sumbangan per unit kegiatan Untuk maksimasi cj menunjukkan penerimaan/keuntungan per unit. Untuk minimasi cj menunjukkan biaya per unit

bi

: jumlah sumber daya i (i = 1,2,3,……………..m)

aij

: banyaknya sumber daya i yang dikonsumsi sumber daya j.

Simbol-simbol tersebut diatas selanjutnya disusun ke dalam bentuk table standar Programa Linier, seperti Tabel 1. Dan model matematisnya sbb. Fungsi Tujuan : Maksimumkan Z = C1X1 + C2X2 + C3X3 + . . . . . . + CnXn Batasan/Kendala : a11X1 + a12X2 + a13X3 + ……………………..+ a1nXn ≤ b1 a21X1 + a22X2 + a23X3 + ……………………..+ a2nXn ≤ b 2


STMIK BUDIDARMA


Hal : 62

a31X1 + a32X2 + a33X3 + ……………………..+ a3nXn ≤ b3 . am1X1 + am2X2 + am3X3 + ……………………..+ amnXn ≤ bm dan ,

X1 ≥ 0 , X2 ≥ 0, X3 ≥0,…………………… Xn ≥ 0

3.2.2. Langkah- Langkah Metode Simplek.

3.2.2.1 Kasus Maksimum. 1. Mengubah Fungsi Tujuan dan Batasan – Batasan Fungsi tujuan diubah menjadi fungsi implisilit. Artinya semua CjXij geser ke kiri Contoh. Fungsi Tujuan. Z = 3X1 + 5X2,

menjadi

Z - 3X1 - 5X2

= 0,

Fungsi Pembatas Semua batasan bertanda ≤ dirubah menjadi tanda = dengan menambah “slack varable”. (S1, S2, ………,Sm) Slack variable adalah variable yang mewakili tingkat pengangguran . 2X1

≤ 8

menjadi

2X1

+

S1

= 8

3X2

≤ 15 menjadi

3X2

+

S2

= 15

6X1 + 5X2 +

S3

= 30

6X1 + 5X2 ≤ 30 menjadi

(S3, S4,S5 adalah Slack Variable). 2. Menyusun Tabel Simplek. Variabel Dasar Z S1 S2 .Sm

Z 1 0 0 . .0

X1 -C1 a11 a21 a31 . am1

X2 ……Xn S 1, -C2 … -Cn 0 a12 . . . . . a1n 1 a22 . . . . . a2n 0 a32 . . . . . a3n 0 . . am2 . . . . . amn 0

S2, ………,Sm 0 ……….. 0 0

……………

1

……………. 0

0

0

…………….. 0

. 0

……………… 1

NK 0 b1 b2 b3 bm

NK adalah Nilai Kanan persamaan. Kasus perusahaan sepatu “Maryland” dapat dibuat menjadi table berikut. Tabel Simplek Perusahaan Sepatu Maryland Variabel Dasar Z X1 X2 S1 S2 S3 NK 0 -3 -5 0 0 0 1 Z 8 2 0 1 0 0 0 S1 15 0 3 0 1 0 0 S2 30 6 5 0 0 1 0 S3 3. Pilih Kolom Kunci Pilih kolom yang mempunyai nilai pada garis fungsi tujuan yang bernilai negative dengan angka terbesar.


STMIK BUDIDARMA


Hal : 63

Variabel Dasar

Z

X1

X2

S1

S2

S3

NK

Z

1

-3

-5

0

0

0

0

S1

0

2

0

1

0

0

8

S2

0

0

3

0

1

0

15

S3

0

6

5

0

0

1

30

Keterangan

4. Pilih Baris Kunci Hitung Indeks yang merupakan Nilai Kolom NK dibagi dengan Nilai Kolom Kunci. Cari nilai terkecil Variabel Z Dasar

X1

X2

S1

S2

S3

NK

Keterangan

Z

1

-3

-5

0

0

0

0

S1

0

2

0

1

0

0

8

Tak terhingga

S2

0

0

3

0

1

0

15

5

S3

0

6

5

0

0

1

30

6

5. Mengubah Nilai-Nilai Baris Kunci Nilai-nilai pada baris kunci bagikan terhadap nilai kunci, dalam hal ini nilai yang terdapat pada perpotongan kolom kunci dengan baris kunci. angka 3. Kemudian X4 pada kolom variable dasar diganti menjadi kolom kunci (X2) Variabel Dasar

Z

X1

X2

S1

S2

S3

NK

Z

1

-3

-5

0

0

0

0

S1

0

2

0

1

0

0

8

S2

0

0

3

0

1

0

15

S3

0

6

5

0

0

1

30

0

0

1

0

1/3

0

5

Z S1 X2 S3 Catatan : Ganti S4 pada variabel Dasar menjadi X2. 6. Mengubah nilai-nilai pada baris selain baris kunci. Nilai Baru = Baris Lama - (Koefisien pada kolom kunci) x nilai baru baris kunci. Baris 1 (Z) -5

Baris Baru Baris 2 (X3) 0


-3

-5

0

0

0

0

0

1

0

1/3

0

5

-3

-5

0

0

0

0

0 -3 2

-5 0 0

0 0 1

5/3 5/3 0

0 0 0

-25 25 8

(-)

0

1

0

1/3

0

5

(-)

(-)

STMIK BUDIDARMA


Baris Baru Baris 4 (X5) 5

Baris Baru

Iterasi

Hal : 64

2

0

1

0

0

8

0 2

0 0

0 1

0 0

0 0

0 8

6

5

0

0

1

30

0 6

1 5

0 0

1/3 0

0 1

5 30

(-)

0 6

5 0

0 0

5/3 -5/3

0 1

25 5

(-)

(-)

Variabel Dasar

Z

X1

X2

S3

S4

S5

NK

Z

1

-3

-5

0

0

0

0

X3

0

2

0

1

0

0

8

0

1

X4

0

0

3

0

1

0

15

X5

0

6

5

0

0

1

30

Z

1

-3

0

0

5/3

0

25

S3

0

2

0

1

0

0

8

X2

0

0

1

0

1/3

0

5

S5

0

6

0

0

5/3

1

5

7. Kembali ke Langkah 3 s/d langkah 6 , hingga diperoleh niali pada Baris Z tidak ada lagi bertanda negative. Hasilnya sbb. Iterasi

1

2

Variabel Dasar

Z

X1

X2

S

S2

S3

NK

Z

1

-3

0

0

5/3

0

25

S1

0

2

0

1

0

0

8

X2

0

0

1

0

1/3

0

5

S3

0

6

0

0

-5/3

1

5

Z

1

0

0

0

0,83325

0,5

27,5

S1

0

0

0

1

0,5555

-0,3333

6,33333

X2

0

0

1

0

0,33333

0

5

X1

0

0,16667

0,83333

1 0 0 -0,2778 Catatan : Ganti S5 pada Variabel dasar menjai X1. Z = 27,5 X1 = 0,8333 X2 = 5 S1 = 6,3333

3.2.2.2. Kasus Minimum. 1. Apabila kita menyelesaikan masalah minimasi, maka fungsi tujuan harus dirubah menjadi maksimasi, agar sesuai dengan bentuk standar Programa Linier, dengan cara mengganti tanda positif dan negative pada fungsi tujuan.


STMIK BUDIDARMA


Hal : 65

Z = ∑ Cjxj n

Minimumkan

j =i

Menjadi

(- Z ) = ( ∑ − Cjxj ) n

Maksimumkan

j=i

Contoh: Minimumkan

Z = 3X1 + 5X2

diubah menjadi Maksimumkan (- Z) = -3X1 - 5X2 2. Fungsi Pembatas bertanda ≥ Bila suatu fungsi pembatas bertanda ≥, maka harus diubah menjadi ≤, kemudian menjadi tanda = agar dapat diselesaikan dengan metode simplek. Contoh : 6X1 + 5X2 ≥ 30,

dikalikan (-1) menjadi

- 6X1 - 5X2 ≤ - 30, ditambah variable S1 - 6X1 - 5X2 + S1 = - 30 3. Bagian Kanan Persamaan Bertanda Negatif. Contoh : - 6X1 - 5X2 + S1 = - 30, kalikan dengan (-1), menjadi 6X1 + 5X2 - S1 =

30

Perhatikan slack variable masih bertanda negative (yaitu – S1), hal ini tidak memungkinkan menggunakan metode simplek. Maka harus ditambahkan lagi variable buatan (artificial variable) R1. Persamaan menjadi : 6X1 + 5X2 - S1 + R1 =

30

Catatan : S1 disebut juga surplus variable, karena mengurangi kelebihan dari bagian kiri persamaan. Contoh Soal. Fungsi Tujuan. Minimumkan

Z = 3X1 + 5X2

Batasan. 2X1

= 8


STMIK BUDIDARMA

Modul : KKMI3413-Teknik Riset Operasional 3X2 6X1 + 5X2

Hal : 66

≤ 15 ≥ 30

Hitunglah, X1, X2 dan Z. Penyelesaian. Fungsi tujuan dirubah dari minimum menjadi maksimum. Z = 3X1 + 5X2

Minimumkan

menjadi - Z = -3X1 - 5X2

Batasan 1. 2X1 + R1

= 8

; R1 adalah variable buatan

Sehingga fungsi tujuan menjadi, Maksimumkan (-Z) = -3X1 – 5X2 – R1 Batasan 2. 3X2 3X2

≤ 15, menjadi + S1 = 15

Batasan 3. 6X1 + 5X2 - 6X1 - 5X2

≥ 30, menjadi ≤ - 30, ditambah variable S2,

menjadi

- 6X1 - 5X2 + S2 = - 30, diaklikan dengan (-), menjadi 6X1 + 5X2 - S2 = 30, karena variable S2 bertanda (-), maka Harus ditambah variable buatan R2, shg

6X1

+ 5X2 - S2 + R2 = 30 Sehingga fungsi tujuan menjadi Maksimumkan (-Z) = -3X1 – 5X2 – R1 – R2. Jika dirubah menjadi fungsi implicit menjadi: (-Z) – ( -3X1 – 5X2 – R1 – R2) = 0 atau -Z + 3X1 + 5X2 + R1 + R2 = 0 Ada dua teknik penyelesaian untuk kasus dengan variable artificial, yaitu •

Teknik M (Metode Penalty)

•

Teknik Dua Fase.

3.3. Teknik M (Metode Penalty) Perhatikan fungsi pembatas 2X1 + R1

= 8

2X1 = 8 , menjadi R1 = 8 – 2X1

R1 adalah variable buatan Sehingga fungsi tujuan menjadi, Maksimumkan (-Z) = -3X1 – 5X2 – R1 Perhatikan fungsi pembatas 3X2

3X2

≤ 15, menjadi

+ S1 = 15


STMIK BUDIDARMA

Modul : KKMI3413-Teknik Riset Operasional Perhatikan fungsi pembatas 6X1 + 5X2 - 6X1 - 5X2

Hal : 67

≥ 30, menjadi

≤ - 30, ditambah variable S2, menjadi

- 6X1 - 5X2 + S2 = - 30, diaklikan dengan (-), menjadi 6X1 + 5X2 - S2 = 30, karena variable S2 bertanda (-), maka Harus

ditambah

variable

buatan

R2,

shg

6X1 + 5X2 - S2 + R2 = 30 atau R2 = 30 – (6X1 + 5X2 - S2) Sehingga fungsi tujuan menjadi Maksimumkan (-Z) = -3X1 – 5X2 – R1 – R2. Jika dirubah menjadi fungsi implicit menjadi: (-Z) – ( -3X1 – 5X2 – R1 – R2) = 0 atau -Z + 3X1 + 5X2 + R1 + R2 = 0 Kalikan M (merupakan bilangan positif yang sangat besar) dengan Artificial Variable atau variabel buatan (dalam hal ini R1 dan R2) pada fungsi tujuan, sehingga : -Z + 3X1 + 5X2 + MR1 + MR2 = 0 Substitusi R1 dan R2 pada fungsi tujuan, sehingga diperoleh : -Z + (-8M + 3)X1 + (-5M+5)X2 – MS2 = -38 M. Buatlah Tabel Simplek. Variabel

Z

X1

X2

S1

S2

R1

R2

NK

Z

1

-8M + 3

-5M+5

0

-M

0

0

-38 M

S1

0

2

0

0

0

1

0

8

4

R1

0

0

3

1

0

0

0

15

∼

R2

0

6

5

0

-1

0

1

30

6

Dasar

Ket.

Lanjutkan sesuai dengan langkah-langkah menyelesaikan Metode Simplek, mulai langkah ketiga.

3.4. Teknik Dua Fase. Dengan penggunaan konstanta M yang nilainya sangat besar, dapat mengakibatkan

kesalahan

perhitungan,

terutama

bila

perhitungan

dengan

menggunakan komputer. Hal ini dapat terjadi karena koefisien fungsi tujuan relatif sangat kecil dibandingkan dengan harga M, sehingga komputer menganggap bernilai nol. Perhatikan fungsi tujuan : -Z + (-8M + 3)X1 + (-5M+5)X2 – MS2 = -38 M Misalkan M = 100 000, maka (-8M + 3) = (-800 000 + 3) (-5M+5) = (-500000 + 5)


STMIK BUDIDARMA


Hal : 68

Kesulitan ini dapat dikurangi dengan menggunakan teknik dua fase. Konstanta M dihilangkan dengan cara menyelesaikan persoalan dalam dua fase (tingkatan) sebagai berikut : Fase Pertama. Fase ini digunakan untuk menguji apakah persoalan yang kita hadapi memiliki solusi fisibel atau tidak. Padafase ini fungsi tujuan diganti dengan meminimumkam jumlah artificial variable.

Jika nilai minimum fungsi tujuan baru ini berharga nol (artinya

seluruh variabel artifisialberharga nol) berarti persoalan memiliki solusi fisibel, kemudian lanjutkan ke fase kedua. Tetapi, apabila nilai minimum fungsi tujuan baru ini berharga positif, maka persoalan tidak memiliki solusi fisibel. Fase Kedua. Gunakan solusi optimum dari fase pertama sebagai solusi awal bagi persoalan semula. Ubahlah bentuk fungsi tujuan fase pertama dengan mengembalikannya pada fungsi tujuan persoalan semula. Contoh Soal. Maksimumkan

Z = 3 X1 + 5 X2

Batasan : 2X1

≤ 2X2

3X1 + 2X2

8

≤ 12 = 18

X1 >= 0 ; X2 >= 0 Penyelesaian. 2X1

+

S1

=

2X2

+

S2

= 12

3X1 + 2X2

8

+ R1 = 18

atau R1 = 18 -3X1 - 2X2

Z = 3 X1 + 5 X2 - MR3 - Z – 3X1 - 5X2 + MR3 = 0 Fase Pertama. Minimumkan r = R3 atau -r = -18 + 3X1 + 2X2 atau -r - 3X1 - 2X2 = -18


STMIK BUDIDARMA


Iterasi

Hal : 69

Variabel

NK/Kolom

Dasar

Z

X1

X2

S1

S2

R1

NK

r

-1

-3

-2

0

0

0

-18

S1

0

1

0

1

0

0

4

4

S2

0

0

2

0

1

0

12

∼

R3

0

3

2

0

0

1

18

6

0

-2

3

0

0

-6

0

r 1

2

Kunci

X1

1

1

0

1

0

0

4

∼

S2

0

0

2

0

1

0

12

6

R3

0

0

2

-3

0

1

6

3

r

0

0

0

0

1

0

X1

1

0

1

0

0

4

S2

0

0

3

1

-1

6

X2

0

1

-1,5

0

0,5

3

Persoalan diatas memiliki solusi fisibel, kemudian R tidak diikut sertakan. Dari tabel diatas pada fase 1 dapat dituliskan persamaan sebagai berikut : X1 + S1 = 4

atau

X1 = 4 – S1

3 S1 + S2 = 4 X2 - 1,5 S1

= 3

atau

X2 = 3 + 1,5 S1

Z = 3 X1 + 2 X2 Z = 3 ( 4 – S1) + 5 ( 3 + 1,5 S1) Z = 12 – 3 S1 + 15 + 7,5 S1 Z = 27 – 4,5 S1

Iterasi

0

1

Variabel Dasar

Z

X1

X2

S1

S2

NK

Z

1

0

0

-4,5

0

27

X1

0

1

0

1

0

4

S2

0

0

0

3

1

6

X2

0

0

1

-1,5

0

3

Z

1

0

0

0

1,5

36

X1

0

1

0

0

-0,333

2

S1

0

0

0

1

0,3333

2

X2

0

0

1

0

0,5

6

Jadi : Z = 36 , X1 = 2 : X2 = 6 ; S1 = 2


STMIK BUDIDARMA


Hal : 70

SOAL –SOAL. BAGIAN SATU 1. Sebuah perusahaan elektronik memproduksi tape recorder dan amplifier yang prosesnya dilakukan di dua stasiun kerja, yaitu perakitan dan pengetesan. Setiap unit tape recorder memerlukan 2 jam perakitan dan 2 jam pengetesan, sedangkan setiap unit amplifier memerlukan 4 jam perakitan dan 3 jam pengetesan. Waktu yang tersedia di departemen perakitan adalah 72 jam/minggu sedangkan di departemen pengetesan adalah 48 jam/minggu. Kontribusi profit dari tape recorder adalah Rp 25.000, dan dari setiap unit amplifier adalah Rp 50.000. Bagaimanakah formulasi persoalan di atas agar dapat ditentukan strategi produksi terbaik yang memberikan konntribusi profit maksimum ? 2. Sebuah perusahaan membuat 2 jenis produk, A dan B. Harga jual produk A adalah Rp 20.000/unit sedangkan produk B dijual dengan harga Rp 30.000/unit. Untuk membuat 1 unit produk A dibutuhkan waktu 2 jam-orang ( man-hour ), sedangkan untuk 1 unit produk B diperlukan 6 jam-orang. Jumlah pekerja adalah 2 orang, masing-masing bekerja 8 jam/hari termasuk istirahat selama 30 menit. Untuk 1 unit A dibutuhkan 6 kg bahan baku, sedangkan setiap unit B membutuhkan 3 kg bahan baku. Harga per kg bahan baku adalah Rp 1.500. Upah pekerja per jam-orang adalah Rp 2.000.jika bahan baku yang tersedia per hari adalah 40 kg, bagaimanakah formulasi persoalan ini agar diperoleh kontribusi profit maksimum ? 3. Seorang petani yang memiliki 7 ha tanah sedang memikirkan berapa ha tanah yang harus ditanami jagung dan berapa ha yang harus ditanami gandum. Dia mengetahui bahwa jika ditanami jagung, setiap ha tanah akan menghasilkan 10 ton jagung. Untuk ini diperlukan 4 jam-orang setiap minggunya. Jika ditanami gandum, hasilnya adalah 25 ton/ha dan diperlukan 10 jam-orang/minggu.Setiap kg jagung dapat dijual seharga Rp 30, sedangkan harga jual gandum adalah Rp 40/kg.Saat ini petani tsb. hanya memiliki 40 jam-orang setiap minggunya. Karna ada peraturan pemerintah yang mengharuskan setiap petani untuk menghasilkan gandum paling sedikit 30 ton setiap kali panen, bagaimanakah formulasi persoalan ini agar petani tsb. dapat menggarap tanahnya secara optimal? 4. Seorang pedagang buah-buahan membeli buah duku dari 3 orang petani. Kualitas buah ini biasa dinyatakan dengan besarnya, dan diklasifikasi dalam 3 kategori, yaitu besar, sedang, dankecil. Berikut ini adalah data harga dan persentase ukuran buah yang dimiliki oleh masing-masing petani :


STMIK BUDIDARMA


Hal : 71

Persentase Untuk Ukuran Penghasil

Harga/Kg

Buah

(Rp)

(%) Besar

Sedang

Kecil

Petani 1

5.000

40

40

20

Petani 2

4.000

30

35

35

Petani 3

3.000

20

20

60

Kebutuhan minimum pedagang tsb. akan masing-masing kualitas buah setiap bulannya adalah ukuran besar 500kg, ukuran sedang 300kg, dan ukuran kecil 300kg. Modal perusahaan itu saat ini hanya mampu untuk membeli maksimum 500kg dari masing-masing petani. Formulasikanlah persoalan ini untuk meminimumkan ongkos. 5. Seseorang yang sedang dalam pengawasan seorang ahli gizi mendapat petunjuk bahwa kebutuhan minimal orang tersebut setiap hari adalah 500 kalori, 6 ons cokelat, 10 ons gula, dan 8 ons lemak. saat ini orang tsb. sedang berada di suatu tempat yang hanya menyediakan kue kering, es krim, coca cola,

dan

roti

keju.

Harga

dan

kandungan

bahan

masing-masing

makanan/minuman tsb dapat dilihat pada tabel dibawah ini. Bagaimanakah formulasi untuk memenuhi kebutuhan akan bahan makanan dengan biaya minimum ?

Jenis Barang

Harga

Kue Kering/bungkus Es krim/mangkok Coca cola/botol Roti keju/potong

(Rp)

Kalori

Cokelat

Gula

Lemak

(Ons)

(Ons)

(Ons)

500

400

3

2

2

200

200

2

2

4

300

150

0

4

1

800

500

0

4

5

Bagaimanakah formulasi untuk memenuhi kebutuhan akan bahan makanan dengan biaya minimum ? 6. Indah motor adalah sebuah perusahaan yang memproduksi dua jenis truk. Setiap jenis truk yang dibuatnya harus melalui unit kerja perakitan dan pengcetan. Apabila unit kerja pengecetan hanya digunakan untuk mengerjakan truk jenis I, maka akan dapat dihasilkan 800 unit truk jenis I per hari, tetapi jika hanya digunakan untuk mengerjakantruk jenis II, hasilnya


STMIK BUDIDARMA


Hal : 72

adalah 700 unit truk jenis II. Apabila unit kerja perakitan hanya digunakan untuk mengerjakan truk jenis I, akan dihasilkan 1,500 unit truk jenis I per hari, sedangkan jika hanya digunakan untuk mengerjakan truk jenis II akan dihasilkan 1.200 unit truk jenis II per hari. Keuntungan dari truk jenis I adalah Rp 300.000/unit,sedangkan dari jenis II akan diperoleh keuntungan sebesar Rp 500.000/unit. Bagaimanakah formulasi ini agar di peroleh keuntungan yang maksimum ? 7. Seorang pengusaha yang memiliki 3 buah pabrik sedang menghadapi masalah yang berkaitan dengan pembuangan limbah dari pabriknya. Selama ini ia membuang limbah tsb. kesungai, sehingga menimbulkan dua macam polutan. Setelah berkonsultasi dengan pihak berwenang, diperoleh informasi bahwa ongkos untuk memproses zat buangan dari pabrik I adalah Rp 15.000/ton dengan kemampuan dapat mengurangi polutan 1 sebanyak 0,1 ton dan polutan 2 sebanyak 0,45 ton dari setiap 1 ton zat buangan. Ongkos untuk memproses zat buangan dari pabrik II adalah Rp 10.000/ton dengan kemampuan mengurangi 0,2 ton polutan 1 dan 0,25 ton polutan 2. Untuk memproses 1 ton zat buangan dari pabrik III diperlukan biaya Rp 20.000 yang akan mengurangi 0,4 ton polutan 1 dan 0,3 ton polutan 2. Peraturan pemerintah mengharuskan ini untuk dapat mengurangi polutan 1 paling sedikit 30 ton dan polutan 2 paling sedikit 40 ton. Formulasikan persoalan ini agar diperoleh ongkos total minimum. BAGIAN KEDUA 1.

P.T.Unilever bermaksud membuat 2 jenis sabun, yakni sabun bubuk dan sabun batang. Untuk itu dibutuhkan 2 macam zat kimia, yakni A dan B.Jumlah zat kimia yang tersedia adalah A = 200 kg dan B = 360 = kg. Untuk membuat 1kg sabun bubuk diperlukan 2kg A dan 3kg B. Bila keuntungan yang akan diperolehsetiap membuat 1kg sabun bubuk = $ 3 sedangkan setiap 1kg sabun batang = $ 2, berapa kg jumlaah sabun bubuk dan sabun batang yang sebaiknya dibuat ?

2.

Sebuah perusahaan film sedang membuat rencana kegiatan untuk tahun yang akan datang. Ada 2 jenis film yang akan dibuat, yakni film untuk TV dan film untuk di gedung. Biaya pembutan film TV adalah sebesar Rp 750.000,00 sedangkan biaya pembuatan film gedung adalah Rp 2.000.000,00 sebuah. Film TV dapat dijual dengan harga Rp 1.250.000,00 sedangkan film gedung dapat di jual dengan harga : Rp 3.000.000,00 sebuah. Waktu ekuivalen yang di butuhkan untuk membuat sebuah film TV = 12 minggu, sedangkan untuk film gedung = 30 minggu. Waktu ekuivalen yang


STMIK BUDIDARMA


Hal : 73

tersedia selama tahun yang akan datang adalah sebanyak 600 minggu ( 1 tahun = 50 minggu, terdapat 12 alat, jadi waktu ekuivalen = 50 x 12 = 600 minggu). Bila dana yang tersedia adalah sebesar Rp 25.000.000,00, berapa jumlah masing-masing jenis film yang harus dibuat ? 3.

Sebuah perusahaan mebel bermaksud membuat 2 jenis produk, yakni lemari pakaian dan tempat tidur.Keuntungan setiap lemari pakaian adalah sebesar Rp 6.000,00, sedangkan bila membuat tempat tidur keuntungannya adalah sebesar Rp 5.000,00 sebuah. pembuatan kedua produk tersebut harus melalui 2 unit kerja, yakni unit kerja 1 dan unit kerja 2. Jam kerja tersedia pada unit kerja 1 adalah 40 jam/minggu, sedangkan pada unit kerja 2 adalah 50 jam/minggu. Setiap lemari pakaian membutuhkan waktu 2 jam pada unit kerja 1 dan 1 jam pada unit kerja 22, sedangkan setiap tempat tidur memerlukan waktu 1,25 jam pada unit kerja 1dan 1 jam pada unit kerja 2. Berapa jumlah lemari pakaian dan tempat tidur yang sebaiknya dibuat setiap minggu ?

4.

PT Sayang Anak memproduksi dua jenis mainan A dan B yang keduanya terbuat dari campuran pasir dan lilin. produk A dapat dibuat melalui proses 1 atau proses 2, sedangkan produk B dapat dibuat melalui

proses 3 atau

proses 4. Untuk mendapat 1 unit produk A dan B pada masing-masing proses diperlukan masukan ( input ) sebagai berikut : INPUT

1 Unit produk A

1 Unit produk B

Satuan

Proses 1

Proses 2

Proses 3

Proses4

Tenaga kerja

1

1

1

1

Jam orang

Pasir

7

5

3

2

m3

Lilin

3

5

10

15

dus

Tenaga kerja yang tersedia tidak lebih dari 15 jam-orang, sedangkan persediaan pasir dan lilin adalah 120 m3 dan 100 dus. Keuntungan proses 1,2,3, dan 4 masing-masing Rp4,00/unit, Rp 5,00/unit, Rp 9,00/unit, dan Rp 11,00/unit. Formulasikan persoalan di atas sebagai persoalan Programaa linier, dan buatlah tabel iterasi awalnya. 5.

Suatu perusahaan membuat 5 tipe truk. Adapun jumlah truk yang diproduksi dibatasi oleh kapasitas tiap bagian yang membuat masing-masing tipe truk, yaitu a.

Bagian metal stamping tidak menangani lebih dari jumlah ekuevalen 10.000 truk tipe I. perbandingan jumlah truk yang dibuat pada bagian metal stammping adalah tipe I : tipe II : tipe III : tipe IV : tipe V = 1: 1,4 : 2 :0,8 : 2,2.


STMIK BUDIDARMA

Modul : KKMI3413-Teknik Riset Operasional b.

Hal : 74

Bagian asembling mesin tidak dapat menangani lebih dari jumlah ekuivalen 15.000 truk tipe I. Perbandingan jumlah truk yang dibuat pada bagian asembling mesin adalah tipe I : tipe : II : tipe III : tipe IV : tipe V = 1: 1,6 : 3 : 1 : 2,6.

c.

Jumlah truk maksimum yaang dapat ditangani oleh bagian asembling akhir adalah sebagai berikut : Tipe I Tipe II

...................................................7.500 buah ................................................... 5.000 buah

Tipe III ................................................... 1.000 buah Tipe IV .................................................. 9.000 buah Tipe V

.................................................. 3.000 buah

Keuntungan yang diperoleh dari tipe I s.d. V masing-masing adalah Rp 350.000, Rp 450.000, Rp 500.000, Rp 300.000, dan Rp 400.000 per buah. Tentukanlah model matematis Programaa liniernya 6.

“ Fine Wall Paper Company “ adalah sebuah perusahaan yang memproduksi linier board. Produk ini mempunyai lebar standar 68 inci. Untuk tahun depan perusahaan ini mendapat pesanan produk dengan lebar yang berbeda-beda, yaitu : 110 unit yang lebarnya 22 inci, 120 unit yang lebarnya 20 inci, dan 80 unit yang lebarnya 12 inci. Bayangkanlah bahwa saudara adalah seorang konsultan kepercayaan perusahaan tersebut. Bagaimanakah usul saudara untuk dapat memenuhi pesanan tersebut, tetapi dengan syarat, jumlah linier board yang terbuang sekecil mungkin ?

7.

PT Philips Ralin memproduksi 3 jenis/model radio, yaitu model A,B, dan C yang masing-masing memberikan keuntungan sebagai berikut : Model A : $ 16 per set Model B : $ 30 per set Model C : $ 50 per set Menurut informasi dari bagian penjualan, keperluan minimum per minggu dari masing-masing model adalah : Model A = 20 set Model B = 120 set Model C = 60 set Proses pembuatan radio ini meliputi proses-proses pembuatan komponen, perakitan, dan pengepakan yang untuk masing-masing model, waktunya adalah sebagai berikut : Model A : pembuatan komponen : 3 jam/set


STMIK BUDIDARMA

Modul : KKMI3413-Teknik Riset Operasional perakitan

Hal : 75

: 3,5 jam/set

pengepakan

: 5 jam/set

Model B : pembuatan komponen : 4 jam/set perakitan

: 5 jam/set

pengepakan

: 8 jam/set

Model C : pembuatan komponen : 1 jam/set perakitan

: 1,5 jam/set

pengepakan

: 3 jam/set

Untuk minggu yang akan datang, perusahaan mempunyai waktu sebanyak : - untuk pembuatan komponen - untuk perakitan

: 1440 jam : 1920 jam

- untuk pengepakan

: 576 jam

Pertanyaan : a. Formulasikan persoalan di atas sebagai persoalan Programa linier. b. Buatlah tabel simpleks untuk iterasi awalnya saja ! 8.

Sebuah perusahaan elektronik membuat 2 jenis pesawat telepon, yakni jenis push button ( PB ) dan dial (D ), masing-masing dalam 3 warna ( abu-abu, merah, hijau ). Proses pengerjaannya melalui 4 mesin,yaitu P, Q, R, dan S. Dari hasil penelitian diperoleh data-data sebagai berikut : Push button

Pengerjaan

Dial

Jam mesin

pada mesin

A

M

H

A

M

H

tersedia

P

0,02

0,02

0,02

0,06

0,06

0,06

1,700

Q

0,40

-

-

0,10

-

-

1,400

R

-

0,40

-

-

0,10

-

200

S

-

-

0,06

-

-

0,15

1,800

Keuntungan

0,80

0,58

0,64

1,44

1,28

1,20

per unit Bila saudara diminta bantuannya, bagaimanakah rencana produksi yang paling optinum, dan berapa keuntungan yang akan diperoleh ? 9.

Suatu perusahaan konfeksi pakaian memproduksi 3 jenis pakaian, yaitu pakaian anak-anak, pakaian pria, pakaian wanita. Untuk satu lusin pakaian anak-anak diperlukan dua rol kain berbagai corak dan warna serta empat orang tenaga kerja. Untuk satu lusin pakaianpria dan satu lusin pakaian wanita diperlukan masing-masing sebanyak empat dan dua rol kain berbagai corak dan warna dengan jumlah tenaga kerja masing-masing dua dan enam orang. Kain yang digunakan setiap harinya tersedia, sebanyak dua puluh rol. Tenaga kerja yang ada mempunyai keahlian yang sama, dan jumlahnya


STMIK BUDIDARMA


Hal : 76

enam belas orang. Policy perusahaan mengharuskan seluruh tenaga kerja digunakan, artinya tidak boleh ada tenaga kerja yang menganggur. Ongkos membuat masing-masing jenis pakaian itu didasarkan atas model, aksesori, dan jam kerja yang diperlukan. Tetapi, sebagai patokan dapat digunakan biaya ratarata yang besarnya $ 15/lusin pakaian anak-anak, $ 30/lusin pakaian pria, dan $ 45/lusin pakaian wanita. Jika masing-masing jenis pakaian itu laku terjual dengan harga $ 25/ lusin pakaian anak-anak, $ 54/lusin pakaian pria, dan $ 53/lusin pakaian wanita, bagaimanakah model Programaa linier persoalan di atas ? 10. Direktur Pertamina mengatakan bahwa ada dua macam proses pengolahan minyak, yaitu : Proses 1: dengan menggunakan bahan 1barrel minyak mentah A dan 3 barrel minyak mentah B sehingga dihasilkan : 50 galon gasolin x dan 20 galon gasolin y Proses 2 : dengan menggunakan bahan 4 barrel minyak mentah A dan 2 barrel minyak mentah B sehingga dihasilkan : 30 galon gasolin x dan 80 galon gasolin y Diketahui bahwa persediaan maksimum minyak mentahA adalah 120 barrel dan minyak mentah B sebanyak 180 barrel. Bagian penjualan melaporkan bahwa untuk tahun depan diperlukan sekurang-kurangnya 2800 galon gasolin x dan 2200 galon gasolin y. Keuntungan masing-masing proses adalah : US $ 5/unit proses 1 dan US $ 8/unit proses 2. Tentikanlah berapa barrel masing-masing minyak mentah yang harus dipakai pada proses 1 dan 2 agar diperoleh keuntungan yang maksimum.

11. PT. ZULEHA PERSADA memproduksi 3 jenis model radio yaitu model A, B dan C yang masing- masing memberikan keuntungan $ 16, $ 30 dan $ 50 per set. Proses pembuatan radio meliputi pembuatan komponen, perakitan, dan pengepakan yang yntuk masing-masing model waktunya adalah sbb: Model A

Pembuatan Komponen

3 jam/set

Perakitan

3,5 jam/set


STMIK BUDIDARMA

Modul : KKMI3413-Teknik Riset Operasional Model B

Model C

Hal : 77

Pengepakan

5 jam/set

Pembuatan Komponen

4 jam/set

Perakitan

5 jam/set

Pengepakan

8 jam/set

Pembuatan Komponen

1 jam/set

Perakitan

1,5 jam/set

Pengrepakan

3 jam/set

Untuk minggu yang akan datang, perusahaan mempunyai waktu sebanyak: Pembuatan Komponen

1120 jam/set

Perakitan

506 jam/set

Pengepakan

1240 jam/set

Bila anda diminta bantuannya, bagaimana rencana produksi optimum dan berapa keuntungan yang diperoleh.


STMIK BUDIDARMA


Hal : 78

4 TEORI DUALITAS 4.1. Dualitas Teori dualitas merupakan salah satu konsep programa linier yang penting dan menarik ditinjau dari segi teori dan praktisnya.Ide dasar yang melataarbelakangi teori ini adalah bahwa setiap persoalan programa linier mempunyai suatu programa linier lain yang saling berkaitan yang disebut ”dual”, sedemikian sehingga solusi pada persoalan semula (yang disebut ”primal”) juga memberi solusi pada dualny. Pendefenisian dual ini akan bergantung pada jenis pembatas, tanda-tanda variabel, dan bentuk optimasi dari persoalan primalnya. Akan tetapi, karna setiap persoalan programa linier harus dibuat dalam bentuk standar lebih dahulu sebelum modelnya dipecahkan, maka pendefinisian di bawah ini akan secara otomatis meliputi ketiga hal diatas. Bentuk umum masalah primal-dual adalah sebagai berikut : Primal : Fungsi Tujuan : Maksimumkan Z = C1X1 + C2X2 + C3X3 + . . . . . . + CnXn Batasan/Kendala : a11X1 + a12X2 + a13X3 + ……………………..+ a1nXn ≤ b1 a21X1 + a22X2 + a23X3 + ……………………..+ a2nXn ≤ b2 a31X1 + a32X2 + a33X3 + ……………………..+ a3nXn ≤ b3 . am1X1 + am2X2 + am3X3 + …………………..+ amnXn ≤ bm dan ,

X1 ≥ 0 , X2 ≥ 0, X3≥0,………………

Xn ≥ 0

Dual : Fungsi Tujuan : Minimumkan W = b1Y1 + b2Y2 + b3Y3 + . . . . . . + bmYm Batasan/Kendala : a11Y1 + a21Y2 + a31Y3 + ……………………..+ am1Ym ≤ c1 a12Y1 + a22Y2 + a32Y3 + ……………………..+ am2Ym ≤ c2 a13Y1 + a23Y2 + a33Y3 + ……………………..+ am3Ym ≤ c3 . a1nY1 + a2nY2 + a3nY3 + …………………..+ amnYm ≤ cn dan ,

Y1 ≥ 0 , Y2 ≥ 0, Y3≥0,………………


Ym ≥ 0

STMIK BUDIDARMA


Hal : 79

Kalau kita bandingkan kedua persoalan diatas, ternyata terdapat korespondensi antara primal dengan dual sebagai berikut : 1. Koefisien fungsi tujuan primal menjadi konstanta ruas kanan bagi dual, sedangkan konstanta ruas kanan primal menjadi koefisien fungsi tujuan bagi dual. 2. Untuk setiap pembatas primal ada satu variabel dual, dan untuk setiap variabel primal ada satu pembatas dual. 3. Tanda ketidaksamaan pada pembatas akan bergantung pada fungsi tujuan. 4. Fungsi tujuan berubah bentuk (maksimasi menjadi minimasi dan sebaliknya). 5. Setiap kolom pada primal berkorespondensi dengan baris (pembatas) pada dual. 6. Setiap baris (pembatas) pada primal berkorespondensi dengan kolom pada dual. 7. Dual dari dual adalah primal. Definisi : Suatu persoalan LP dikatakan persoalan maksimal normal jika persoalan itu mempunyai fungsi tujuan maksimasi dengan seluruh variabel berharga nonnegatif dan seluruh pembatas bertanda . Begitu pula, suatu persoalan LP disebut sebagai persoalan minimasi normal jika fungsi tujuan dari persoalan itu adalah minimasi dengan seluruh variabel berharga nonnegatif dan seluruh pembatas bertanda

. Jika pembatasnya mempunyai tanda yang

lain, seperti = dan (untuk persoalan maksimasi) atau = dan (untuk persoalan minimasi) maka persoalan LP yang bersangkutan di sebut persoalan LP yang tidak normal. 4.1.1. Menentukan dual dari persoalan LP normal Contoh 1 : Primal Maksimumkan : z = 60 x1 + 30 x2 + 20 x3 berdasarkan : 8 x1 + 6 x2 + x3 ≤ 48 4 x1 + 2 x2 + 1,5 x3 ≤ 20 2 x1 + 1,5 x2 + 0,5 x3 ≤ 8 x1, x2, x3 ≥ 0 Dual Minimumkan : w = 48 y1 + 20 y2 = 8 y3 berdasarkan : 8 y1 + 4 y2 + 2 y3 ≥ 60 6 y1 + 2 y2 + 1,5 y3 ≥ 30 y1 + 1,5 y2 + 0,5 y3 ≥ 20 y1, y2, y3 ≥ 0 Contoh 2 : Primal Minimumkan : w = 50 y1 + 20 y2 + 80 y3


STMIK BUDIDARMA

Modul : KKMI3413-Teknik Riset Operasional berdasarkan :

Dual

Hal : 80

100 y1 + 200 y2 + 150 y3 + 500 y4 ≥ 500 3 y1 + 2 y2 + ≥ 6 2 y1 + 2 y2 + 4 y3 + 4 y4 ≥ 10 2 y1 + 4 y2 + y3 5 y4 ≥ 8 y1, y2, y3, y4 ≥ 0

Maksimumkan : z = 500 x1 + 6 x2 + 10 x3 + 8 x4 berdasarkan : 400 x1 + 3 x2 + 2 x3 + 2 x4 ≤ 50 200 x1 + 2 x2 + 2 x3 + 4 x4 ≤ 20 150 x1 + 4 x3 + x4 ≤ 30 500 x1 + 4 x3 + 5 x4 ≤ 80 x1, x2, x3, x4 ≥ 0

4.1.2. Menentukan dual persoalan LP yang tidak normal Apabila kita membangun dual dari suatu persoalan LP yang tidak normal, maka akan berlaku hal-hal sebagai berikut : a. Untuk persoalan maksimasi, jika pembatas primal ke-i bertanda , maka variabel dual yang berkorespondensi dengan pembatas tersebut memenuhi yi 0. Sebaliknya, untuk persoalan minimasi, jika pembatas primal ke-i bertanda , maka variabel dual yang berkorespondensi dengan pembatas tersebut akan memenuhi xi 0 b. Jika pembatas primal ke-i bertanda =, maka variabel dual yang berkorespondensi dengan pembatas tersebut akan tidak terbatas dalam tanda c. Jika variabel primal ke-i tidak terbatas dalam tanda, maka pembatas dual ke-i akan bertanda =.

Contoh 1 : Primal Maksimumkan :z = x1 + 2x2 -3x3 = 4x4 berdasarkan pembatas : x1 + 2 x2 + 2 x3 – 3 x4 ≤ 25 2 x1 + x2 – 3 x3 + 2 x4 = 15 x1, x2, x3, x4 ≥ 0 Dual Minimumkan : w = 25 y1 + 15 y2 berdasarkan pembatas : y1 + 2 y2 ≥ 1 2 y1 + y2 ≥ 2 2 y1 – 3 y2 ≥ -3 -3 y1 + 2 y2 ≥ 4 y1 ≥ 0 y2 tidak terbatas dalam tanda. Contoh 2 : Primal Minimumkan : z = 5x1 – 2x2 berdasarkan pembatas :


STMIK BUDIDARMA


Dual

Hal : 81

- x1 + x2 ≥ -3 2 x1 + 3 x2 ≤ 5 x1, x2 ≥ 0 Maksimumkan : w = 3y1 + 5y2 berdasarkan pembatas : y1 + 2 y2 ≤ 5 -y1 + 3 y2 ≤ -2 y1, y2 ≤ 0

Contoh 3 : Primal Maksimumkan : z = 5x1 + 6x2 berdasarkan pembatas : x1 + 2 x2 = 5 -x1 + 5 x2 ≥ 3 4 x1 + 7 x2 ≤ 8 x1 tidak terbatas dalam tanda x2 ≥ 0 Dual Minimumkan : w = 5y1 + 3y2 + 8v3 berdasarkan pembatas : y1 – y2 + y3 ≥ 5 -y1 + y2 – 4y3 ≥ -5 2y1 + 5y2 + 7y3 ≥ 6 - y2 ≥ 0 atau y2 ≤ 0 y3 ≥ 0 y1 tidak terbatas dalam tanda 4.2. Hubungan primal-dual Untuk menjelaskan hubungan antara primal dengan dual, perhatikan ilustrasi berikut ini : Primal Maksimumkan : z = 5x1 + 12x2 + 4x3 berdasarkan pembatas : x1 + 2x2 + x3 ≤ 10 2x1 – x2 + 3x3 = 8 x1, x2, x3 ≥ 0 Bentuk standar : Maksimumkan : z = 5 x1 + 12x2 + 4x3 + OS1 – MR2 berdasarkan pembatas : x1 +2x2 + x3 + S1 = 10 + R2 = 8 2x1 – x2 + 3x3 x1, x2, x3, S1, R2 ≥ 0 Dual dari persoalan di atas adalah : Minimumkan : w = 10y1 + 8(y2’ – y2”) berdasarkan pembatas : y1 + 2(y2’ – y2”) ≥ 5 2y1 – (y2’ – y2”) ≥ 12 y1 + 3(y2’ – y2”) ≥ 4 y1 ≥ 0, y2 tidak terbatas dalam tanda Bentuk standar: Minimumkan : W = 10y1 + 8(y2’ – y2”) – 0(S1 + S2 + S3) M(R1 + R2 + R3)


STMIK BUDIDARMA


Hal : 82

berdasarkan pembatas : y1 + 2(y2’ – y2” ) – S1 + R1 2y1 – (y2’ – y2”) - S2 + R2 y1 + 3(y2’ – y2”) - S3

=5 =12 + R3 =4

Solusi persoalan di atas masing-masing adalah : Primal Tabel.4.1. Tabel Simplek Persoalan Primal Iterasi

0

1

2

3

Basis

X1

X2

X3

S1

R2

Solusi

Z

-(2M+5)

(M-12)

-(3M+4)

0

0

-8M

S1

1

2

1

1

0

10

R2

2

-1

3

0

1

8

Z

-7/3

-40/3

0

0

(4/3 + M)

32/3

S1

1/3

7/3

0

1

-1/3

22/3

X3

2/3

-1/3

1

0

1/3

8/3

Z

-3/7

0

0

40/7

-(4/7 + M)

368/7

X2

1/7

1

0

3/7

-1/7

22/7

X3

5/7

0

1

1/7

2/7

26/7

Z

0

0

3/5

29/5

(2/5 + M)

544/5

X2

0

1

-1/5

2/5

-1/5

12/5

X1

1

0

7/5

1/5

2/5

26/5

Pada iterasi 4, kita dapat membaca nilai Y2 pada Tabel. 4.2. Y2 = (Y2’ – Y2”) = (0 – 2/5) atau Y2 = -2/5 Dari Tabel 4.1. dan 4.2. dapat disimpulkan bahwa hubungan primal dengan dual adalah sebagai berikut : 1. Solusi visibel persoalan minimasi adalah batas atas dari solusi visibel persoalan maksimasi (lihat iterasi 0, 1, dan 2 pada tabel 4.1. serta iterasi 0, 1,2, dan 3 pada tabel 4.2.) 2. Jika kedua persoalan sudah mencapai solusi optimum, maka maksimum Z = Minimum W (lihat iterasi 3 pada tabel 4.1. dan iterasi 4 pada tabel 4.2.). 3. Nilai optimum variabel – variabel solusi awal pada primal = nilai optimum variabel – variabel dual yang berkorespondensi dengan persamaan pembatas pada primal. Dengan kata lain : a. Jika variabel dual berkorespondensi dengan variabel slack awal pada persoalan primal, maka nilai optimum variabel tersebut = koefisien variabel slack pada persamaan Z yang optimum.


STMIK BUDIDARMA


Hal : 83

Bukti : Y1 berkoresp[ondensi dengan S1 pada primal, maka nilai optimum Y1 (= 29/5, lihat iterasi 4 pada tabel 4.2.) sama dengan koefisien S1 pada persamaan Z optimum (= 29/5, lihat iterasi 3 pada tabel 4.1.) b. Jika varibel dual berkorespondensi dengan variabel buatan awal pada primal, maka nilai optimum variabel tersebut variabel

buatan

pada

persamaan

Z

yang

= koefisien

optimum

setelah

menghilangkan konstanta M. Bukti : Y2 berkorespondensi dengan R2 pada primal, maka nilai optimum Y2 (-2/5, lihat iterasi 4 pada tabel 4.2.)


STMIK BUDIDARMA


Hal : 84

Dual Tabel 4.2. Tabel Simplek Persoalan Dual Iterasi

Basis

y1

y2'

y2"

S1

S2

S3

R1

R2

R3

Solusi

w

(4M-10)

(4M+8)

(-4M+8)

-M

-M

-M

0

0

0

21M

R1

1

-2

-2

-1

0

0

1

0

0

5

R2

2

1

1

0

-1

0

0

1

0

12

R3

1

-3

-3

0

0

-1

0

0

1

4

w

(8/3M 22/3)

0

0

-M

-M

(1/3M - 8/3)

0

0

(-4/3M + 8/3)

47/3M 32/3

R1

1/3

0

0

-1

0

2/3

1

0

-2/3

7/3

R2

7/3

0

0

0

-1

-1/3

0

1

1/3

40/3

y2'

1/3

1

-1

0

0

-1/3

0

0

1/3

4/3

w

0

(-8M + 22)

(8M - 22)

-M

-M

(3M - 10)

0

0

('-4M + 10)

(5M + 40)

R1

0

-1

1

-1

0

1

1

0

-1

1

R2

0

-7

7

0

-1

2

0

1

-2

4

y1

1

3

-3

0

0

-1

0

0

1

4

w

0

0

0

-M

(1/7M - 22/7)

(5/7M - 26/7)

0

(-8/7M + 22/7)

(12/7M + 26/7)

3/7M 368/7

R1

0

0

0

-1

1/7

5/7

1

1/7

-5/7

3/7

y2"

0

-1

1

0

-1/7

2/7

0

1/7

-2/7

4/7

y1

0

0

0

0

-3/7

-1/7

0

3/7

1/7

40/7

w

0

0

0

-26/5

-12/5

0

26/5 - M

12/5 - M

-M

54 4/5

S3

0

0

0

-7/5

1/5

1

7/5

-1/5

-1

3/5

y2"

0

-1

1

2/5

-1/5

0

2/5

1/5

0

2/5

y1

0

0

0

-1/5

-2/5

0

1/5

2/5

1

29/5

0

1

-

+

2

3

4


STMIK BUDIDARMA

+


Hal : 85

dengan koefisien R2 pada persamaan Z optimum (= -2/5 + M – M = -2/5, lihat iterasi 3 pada tabel 4.1.) 4.3 Sifat - Sifat Primal Dual Yang Penting. Sifat –sifat primal dual ini penting untuk dipahami, terutama pada saat kita membicarakan masalah analisis kepekaan. Dengan menggunakan sifat-sifat ini kita dapat menentukan nilai variabel-variabel tertentu dengan cara yang sangat efisien. Ada 4 sifat yang perlu diketahui, yaitu : Sifat 1. Menentukan koefisien fungsi tujuan variabel-variabel basis awal. Pada setiap iterasi solusi simplek, baik primal maupun dual, koefien fungsi tujuan variabel-variabel basisnya awal dapat dicari dengan cara : a. Mengalika funsi tujuan yang original dan variabel-variabel basis pada iterasi yang bersangkutan dengan matriks di bawah

variabel basis awal pada iterasi yang

bersangkutan. Koefisien ini biasa disebut sebagai simplex multipliers. koefisien fungsi

matriks di bawah

tujuan yang ori-

variabel

basis

ginal dari vari-

awal pada iterasi

abel basis pada

yang bersangkuta-

iterasi yang

=

simplex multipliers

an

bersangkutan

b. Kurangi nilai-nilai simplex multipliers ini dengan fungsi tujuan yang original dari variabelvariabel basis awal. Sebagai contoh, kita lihat Tabel 4.1. Dalam tabel itu variabel basis awalnya adalah S1 dan R2 denhan joefisien tujuan original 0 dan –M Untuk iterasi 1 : Yang menjadi variabel basis pada iterasi 1 adalah S1 dan x3, di mana koefisien fungsi tujuan originalnya adalah 0 dan 4. Matriks di bawah variabel basis awal (S1 dan R2) pada iterasi 1 adalah : 1

-1/3

0

1/3


STMIK BUDIDARMA


Hal : 86

Dengan demikian simplex multipliers-nya adalah :

0

4

1

-1/3

0

1/3

0

4/3

Koefisien fungsi tujuan variabel-variabel basis awal (S1 dan R2 pada iterasi 1 adalah: S1 = 0 – 0 = 0 R2 = 4/3 – (-M) = 4/3 + M Untuk iterasi 2 : dengan cara yang sama diperoleh : ( 12

5)

3/7

-1/7

= [ 40/7

-4/7 ]

= [ 29/5

-2/5 ]

1/7 2/7 S1 = 40/7 – 0 = 40/7 R2 = -4/7 – (-M) = -4/7 + M Untuk iterasi 3 : ( 12

5)

2/5

-1/5

1/5 2/5 S1 = 29/5 – 0 = 29/5 R2 = -2/5 – (-M) = -2/5 + M Untuk dual kita lihat Tabel 4.2. Misalnya untuk iterasi 4 diperoleh : 7/5 ( 12

5)

-2/5 1/5 2/5

-1/5 1/5

-1 0

= [ 29/5

-2/5 0 ]

0

R1 = 26/5 – (M) = 26/5 – M R2 = 12/5 – (M) = 12/5 – M R3 = 0

- (M) = -M

Sifat 2 : Menetukan koefisien fungsi tujuan variabel-variabel nonbasis awal Pada setiap iterasi dari persoalan primal, koefisien fungsi tujuannya dapat ditentukan dengan menyubstitusikan simplex multipliers pada variabel-variabel pembatas dari dual, kemudian mencari selisih antara ruas kiri dan ruas kanan dari pembatas dual tersebut.


STMIK BUDIDARMA


Hal : 87

Contoh : Dari formulasi persoalan diketahui bahwa : x1 berkorespondensi dengan pembatas y1 + 2y2 ≥ 5 x2 berkorespondensi dengan pembatas 2y1 – y2 ≥ 12 x3 berkorespondensi dengan pembatas y1 + 3y2 ≥ 4 Substitusikan simplex multipliers pada pesamaan-persamaan pembatas di atas Untuk iterasi 1 : SM = (0

4/3)

x1 : y1 + 2y2 ≥ 5

x1 = -7/3

0 + 2(4/3) – 5 = -7/3 x2 : 2y1 – y2 ≥ 12 0

x2 = -40/3

- 4/3 – 12 = -40/3

x3 : y1 + 3y2 ≥ 4

x3 = 0

0 + 3(4/3) – 4 = 0

Untuk iterasi 2 : SM = (40/7

-4/7)

x1 : y1 + 2y2 ≥ 5

x1 = -3/7

40/7 + 2(-4/7) – 5 = -3/7 x2: 2y1 – y2 ≥ 12

x2 = 0

2(40/7 – (-4/7) – 12 = 0 x3 : y1 + 3y2 ≥ 4

x3 = 0

40/7 + 3(-4/7) – 4 = 0 Untuk iterasi 3 : SM (29/5

-2/5)

x1 : y1 + 2y2 ≥ 5

x1 = 0

29/5 + 2(-2/5) – 5 = 0 x2 : 2y1 – y2 ≥ 12

x2 = 0

2(29/5) – (-2/5) – 12 = 0 x3 : y1 + 3y2 ≥ 4

x3 = 3/5

29/5 + 3(-2/5) – 4 = 3/5 Untuk dual, hal yang sama berlaku juga kecuali bahwa substitusi simplex multipliers dilakukan terhadap variabel-variabel pembatas primal.


STMIK BUDIDARMA


Hal : 88

Contoh : Untuk iterasi 4 (lihat Tabel 4.2). SM (26/5

12/5

y1 : x1 + 2x2 + x3 ≤ 10

0)

y1 = 0

26/5 + 2(12/5) + 0 - 10 y2 : 2x1 – x2 + 3x3 = 8

y2 = 0

2(26/5) – 12/5 + 0 – 8 = 10 S1 : -x1≤ 0

S1 = -26/5

-26/5 – 0 = -26/5 S2 : -x2 ≤ 0

S2 = -12/5

-12/5 – 0 = - 12/5 S3 : -x3 ≤ 0

S3 = 0

0–0=0 Sifat 3 : Menentukan nilai ruas kanan (solusi) dari variabel-variabel basis Pada setiap iterasi, baik primal maupun dual, nilai ruas kanan (kolom solusi) variabel-variabel basis pada iterasi yang bersangkutan dapat ditentukan dengan cara sebagai berikut : matriks di bawah variabel basis awal

matriks kolom

pada iterasi yang

ruas kanan

bersangkutan

original

matriks kolom =

ruas kanan variabel basis

Lihat iterasi ke-2 dari Tabel 4.1 (primal) Variabel basis pada iterasi ini adalah x2 dan x3, sedangkan matriks kolom ruas kanan yang original adalah 10

, maka ruas kanan variabel basis

x2

8

x3

adalah : 3/7 -1/7 1/7

10

2/7

=

8

22/7 26/7

Lihat iterasi ke-4 dari Tabel 4.2 (dual) Variabel basis pada iterasi ini adalah S3, y2”, dan y1, sedangkan matriks kolom ruas kanan yang original adalah 5 12

S3 Maka ruas kanan variabel basis

4


y2”

adalah

y1

STMIK BUDIDARMA

Modul : KKMI3413-Teknik Riset Operasional 7/5

-1/5

-1

5

-2/5

1/5

0

12

1/5

2/5

0

4

Hal : 89

3/5 =

2/5 29/5

Sifat 4 : Menentukan koefisien pembatas. Pada setiap iterasi, baik primal maupun dual, koefisien pambatas dari setiap variabel dapat ditentukan dengan cara sebagai berikut : matriks di bawah

matriks kolom

variabel basis awal

dari kolom

pada iterasi yang

koefisien pembatas

bersangkutan

yang original

matriks kolom =

dari kolom koefisien pembatas pada iterasi yang bersangkutan

Contoh : a. Lihat iterasi 3 dari Tabel 4.1 (primal) Untuk variabel x1, koefisien pembatas pada iterasi ini adalah 2/5

-1/5

1

=

0

1/5

2/5

2

2/5

-1/5

2

1/5

2/5

-1

2/5

-1/5

1

= -1/5

1/5

2/5

3

7/5

1

Untuk x2 : =

1 0

Untuk x3 :

b. Lihat iterasi 4 Tabel 4.2 (dual) Untuk variabel y1, koefisien pembatas dari iterasi ini adalah 7/5

-1/5

-1

1

-2/5

2/5

0

2

1/5

2/5

0

7/5

-1/5

-1

2

-2/5

2/5

0

-1

1/5

2/5

0

0 =

0

1

1

Untuk y2’ : 0 = 3


-1 0

STMIK BUDIDARMA


Hal : 90

Untuk y2” : 7/5

-1/5

-1

-2

-2/5

2/5

0

1

1/5

2/5

-3

7/5

-1/5

-1

-1

-2/5

1/5

0

0

1/5

2/5

0

7/5

-1/5

-1

0

-2/5

1/5

0

-1

1/5

2/5

0

7/5

-1/5

-1

0

-2/5

1/5

0

0

1/5

2/5

0

0 =

1

-3

0

Untuk S1 : 7/5 =

2/5

0

-1/5

Untuk S2 : 1/5 =

-1/5

0

-2/5

Untuk S3 : 1 =

0

-1

0

Supaya penggunaan sifat-sifat primal-dual ini dapat lebih teras pentingnya, berikut ini diberikan satu contoh persoalan sebagai berikut : Maksimumkan : z = 4x1 + 6x2 + 2x3 berdasarkan pembatas : 4x1 – 4x2

≤5

-x1 + 6x2

≤5

-x1 + x2 + x3

≤5

x1, x2, x3 ≥ 0 Salah satu iterasi dari persoalan di atas adalah sebagai berikut : Basis

x1

x2

x3

S1

S2

S3

Solusi

z

d

e

f

a

b

c

t

x1

j

m

q

6/20

4/20

0

g

x2

k

n

r

1/20

4/20

0

h

S3

l

p

s

5/20

0

1

i


STMIK BUDIDARMA


Hal : 91

Tentukanlah harga-harga a, b, c, d, e, f, g, h, i, j, k, l, m, n, p, q, r, s, dan t dengan menggunakan sifat-sifat primal-dual. Jawaban : 1. Sifat 1 : (4

6

0)

6/20

4/20

0

1/20

4/20

0

5/20

0

1

= [ 3/2 2

0]

a = 3/2 – 0 = 3/2 b= 2 -0= 2 c= 0 -0=0 2. Sifat 2 : SM = (3/2

2

x1 : 4y1 – y2 – y3 ≥ 4

0) d=0

4(3/2) – 2 – 0 – 4 = 0 x2 : -4y1 + 6y2 + y3 ≥ 6

c=0

-4(3/2) + 6(2) + 0 – 6 = 0 x3 : y3 ≥ 2

f = -2

0 – 2 = -2 3. Sifat 3 : 6/20

4/20

0

5

1/20

4/20

0

5

5/20

0

1

5

6/20

4/20

0

4

1/20

4/20

0

-1

5/20

0

1

-1

5/2 =

5/4 25/4

g = 5/2 h = 5/4 i = 25/4 4. Sifat 4 :


1 =

0 0

STMIK BUDIDARMA


Hal : 92

j=1 k=0 l=0 6/20

4/20

0

-4

0

1/20

4/20

0

6

5/20

0

1

1

0

6/20

4/20

0

0

0

1/20

4/20

0

0

5/20

0

1

1

=

1

m=0 n=1 p=0 =

0 1

q=0 r=0 s=0 Dengan demikian, t dapat dicari dengan memasukkan harga-harga g, h, dan i ke dalam persamaan z, sehingga diperoleh : t = 4(5/2) + 6(5/4) + 0(25/4) t = 70/4 t = 17 ½


STMIK BUDIDARMA


Hal : 93

5 METODE TRANSPORTASI 5.1. PENDAHULUAN Metode transportasi merupakan suatu metode yang digunakan untuk mengatur distribusi dari

sumber-sumber

yang

menyediakan

produk

yang

sama,

ketempat-tempat

yang

membutuhkan secara optimal. Alikasi produk ini harus sedemikian rupa, karena terdapat perbedaan biaya-biaya alokasi dari saru sumber ke tempat-tempat tujuan berdeda-beda, dan dari beberapa sumber ke suatu tempat tujuan juga berbeda-beda. Di samping itu, metode transportasi juga dapat digunakan untuk memecahkan masalah-masalah dunia usaha (bisnis) lainnya, seperti masalah-masalah yang meliputi pengiklanan, pembelanjaan modal (capital financing) dan alokasi dana untuk investasi, analisis lokasi, keseimbangan lini perakitan dan perencanaan serta scheduling produksi. Ada beberapa macam metode transportasi, yang semuanya terarah pada penyelesaian optimal dari masalah-masalah transportasi yang terjadi. F.L. Hitlchcock (1941), T.C. Koopmans (1949), dan G.B. Dantziq (1951) adalah orang-orang yang pertama sebagai kontributor yang mengembangkan teknik-teknik transportasi. Bab ini pertama-tama akan membicarakan metode-metode transportasi dimulai dengan membahas metode stepping stone yang ditemukan oleh W.W. Cooper dan A.Charnes, dilanjutkan dengan metode MODI dan Vogel’s Approximation (VAM). 5.2. Metode Stepping-Stone Untuk mempermudah penjelasan metode Stepping-Stone, berikut ini akan dipergunakan contoh suatu perusahaan yang mempunyai 3 pabrik di W, H, dan P. Perusahaan mengahadapi masalah alokasi hasil produksinya di pabrik-pabrik tersebut ke gudang-gudang penjualan di A, B, dan C. Kapasitas pabrik, kebutuhan gudang dan biaya pengangkutan dari tiap pabrik ke tiap gudang dapat dilihat pada Tabel 5.1, 5.2, dan 5.3.


STMIK BUDIDARMA


Hal : 94

Tabel 5.1. Kapasitas pabrik W Pabrik Kapasitas produksi tiap bulan W 90 ton H 60 ton P 50 ton Jumlah 200 ton Tabel 5.2. Kebutuhan gudang A, B, dan C Gudang A B C Jumlah

Kebutuhan tiap bulan 50 ton 110 ton 40 ton 200 ton

Tabel 5.3. Biaya pengankutan setiap ton dari pabrik W, H, P ke gudang A, B, C Dari Pabrik W Pabrik H Pabrik P

Biaya tiap ton (dalan ribuan Rp) Ke Gudang A Ke Gudang B Ke Gudang C 20 5 8 15 20 10 25 10 19

5.2.1. Penyusunan Tabel Alokasi Untuk bisa memahami dengan lebih mudah dan memcahkan masalah, maka data di atas harus disusun ke dalam suatu table yang menunjukkan hubungan antar kapasitas pabrik, kebutuhan gudang, dan biaya pengankutan seperti terlihat pada Tabel 5.4. Pada table tersebut jumlah kebutuhan tiap-tiap gudang diletakkan pada baris terakhir dan kapasitas pabrik pada kolom terkhir. Sedang biaya pengangkutan diletakkan pada segi empat kecil pada table itu. Misalnya biaya angkut 1 ton barang dari W ke A adalah 20, diletakkan di segi empat kecil di dalam segi empat AW, dan seterusnya. Adapun Xij adalah banyaknya alokasi dari sumber i ke tujuan j, misalnya dari W ke A (sumber 1 ke tujuan pertama) = X11. Nilai Xij inilah yang nanti akan kita cari. Tabel 5.4. Tabel transportasi Ke Dari

Gudang

Gudang

Gudang

Kapasitas

A

B

C

Pabrik

Pabrik W

20 X11

Pabrik H

X21

Kebutuhan Gudang

20 X22

25 X31 50


8 X13

X12 15

Pabrik P

5

10 X23

10 X32 110

19 X33 40

90 60 50 200

STMIK BUDIDARMA

Modul : KKMI3413-Teknik Riset Operasional 5.2.2.

Hal : 95

Prosedur Alokasi Setelah data tersusun dalam bentuk table, maka langkah selanjutnya adalah

mengalokasikan produk dari pabrik-pabrik ke gudang-gudang. Pedoman yang merupakan prosedur alokasi sistematis pertama adalah pedoman sudut barat laut (northwest corner rule). Mulai dari sudut kiri atas dari Tabel 5.4 (Xij) dialokasikan sejumlah maksimum produk dengan melihat kapasitas pabrik dan kebutuhan gudang. Kemudian setelah itu, bila Xij merupakan kotak terakhir yang dipilih, dilanjutkan dengan mengalokasikan pada X1,

j+1

bila i mempunyai kapasitas

yang tersisa. Bila tidak, alokasikan ke X1+1,j, dan seterusnya sehingga semua kebutuhan telah terpenuhi. Dari contoh diatas, alokasi pertama adalah X11 = 50, yang tepat memenuhi kebutuhan gudang A dalam kolom 1 (dan hilangkan kolom ini dari pertimbangan alokasi berikutnya). Dalam hal ini ada kelebihan kapasitas pabrik W sebesar 40 dalam baris 1, sehingga alokasi berikutnya X1, 1+1

= X12. Bila kapasitas pabrik tidak lebih besar dari kebutuhan gudang B dalam kolom 2, maka

pada X12 dialokasikan sebesar 4, dan hilangkan baris 1 dari pertimbangan berikutnya. Untuk selanjutnya alokasi yang dipilih X1+1, 2 = X22. Dari table terlihat bahwa kebutuhan gudang B masih lebih besar dari kapasitas pabrik H, sehingga pada X22 dialokasikan sebesar 60, dan hilangkan baris, dan seterusnya sampai semua kapasitas yagn tersedia telah dialokasikan ke gudanggudang yagn membutuhkan seperti terlihat pada Tabel 5.5. Segi empat yagn tersisi alokasi biasanya disebut segi empat batu, dan yang kosong disebut segi empat air. Biaya pengangkutan untuk alokasi tahap pertama ini = 50(20 + 40(50) + 60(20) + 10(10) + 40(19) = 3260. Tabel 5.5. Alokasi tahap pertama dengan pedoman sudut barat laut. Ke

Gudang

Gudang

Gudang

Kapasitas

A

B

C

Pabrik

Dari Pabrik W

20 50

15

H

20

10

10

19

60

Pabrik

25

P Gudang

8

40

Pabrik

Kebutuhan

5

40

10

50


110

40

90 60 50 200

STMIK BUDIDARMA

Modul : KKMI3413-Teknik Riset Operasional 5.2.3.

Hal : 96

Mengubah Alokasi Secara Trial and Error Untuk mengurai biaya pengangkutan, alokasi pada Tabel 5.5 diubah secara trial and

error. Misalnya, terlihat pada kolom “Gudang A”. Segi empat HA belum terisi, maka dicoba bila diisi 1 satuan (ton) tentu saja perlu pemindahan dari segi empat yagn lain, misalnya dari segi empat WA agar jumlah kebutuhan gudang tetap 50; di samping itu juga akan mempengaruhi segi empat WB dan segi empat HB, seperti terlihat pada Tabel 5.6. Perubahan biaya yang diakibatkan adalah sebagai berikut : Tambahan biaya :

dari H ke A

=

dari W ke B

15 =

5 20

Pengurangan biaya

:

dari W ke A

=

20

dari M ke B

=

20 40

Tambahan biaya 20 sedang pengurangan biaya 40, berarti ada penghematan 20 (=Rp 20.000,00) untuk setiap perpindahan alokasi 1 unit (1 ton) barang ke segi empat HA dan WB dan HB. Berdasarkan kenyataan ini, bila jumlah alokasi yang dilaksanakan lebih banyak (tidak hanya 1 unit saja), maka penghematannya akan lebih banyak. Jumlah yang bisa diubah maksimum sebesar isi terkecil dari 2 segi empat yang terdekat dengan isi segi empat HB = 60. Jadi diisikan pada segi emapat HA 50 unit dan ditambahkan pula isi segi empat WB (yang bertolah belakang dengan HA) sebesar 50 unit. Perubahan alokasi ini seperti terlihat pada Tabel 5.7, dengan menghasilkan biaya pengangkutan yang lebih murah, yaitu 90(5) + 50(15) +10(20) + 10(10) + 40(19) = 2260 lebih murah dari laokasi pertama (Tabel 5.5). Tabel 5.6. Perbaikan pertama dengan trial and error Ke

Gudang

Gudang

Gudang

Kapasitas

A

B

C

Pabrik

Dari Pabrik W

20 50

(-)

20

10

60

(+)

Pabrik P

50


90

(+)

15

H

Gudang

8

40

Pabrik

Kebutuhan

5

25

(-)

10

19

10

40

110

40

60 50 200

STMIK BUDIDARMA


Hal : 97

Tabel 5.7. Perbaikan kedua dengan trial and error Ke Dari

Gudang

Gudang

Gudang

Kapasitas

A

B

C

Pabrik

Pabrik W

50

40

(-)

Pabrik (+)

25

(-)

P

20

10

10

19

90

60

Pabrik

8

90

(+)

15

H

5

40

10

Kebutuhan

50

Gudang

110

40

90 60 50 200

Perubahan alokasi ini dapat juga dilakukan dengan mengubah alokasi pada segi empat yang tidak berdekatan. Misalnya, akan diisi segi empat WC, maka segi empat lain yang ikut berubah dapat berupa segi empat WB, PB, dan PC, seperti terlihat pada Tabel 5.8, dengan biaya pengangkutan = 50(5) + 40(8) +50(15) + 10(20) + 50(10) = 2020. Demikian seterusnya diadakan perubahan bila dengan perubahan itu dapat mengurangi biaya, sampai akhirnya diperoleh biaya pengangkutan yang terendah (optimal). Tabel 5.8. Perbaikan dengan masalah alokasi segi empat yang tidak berdekatan. Ke Dari

Gudang

Gudang

Gudang

Kapasitas

A

B

C

Pabrik

Pabrik

5 90

W Pabrik H

50

25

40

10

10 10

P Gudang

20

10

Pabrik Kebutuhan

(+)

(-) 50

15

8

(-)

(+) 50

50

19

110

90 60 50

40

40

200

5.3. Metode MODI Metode MODI ( Modified Distribution) merupakan perkembangan dari metode steppingstone, karena penentuan segi empat kosong yang bisa menghemat biaya dilakukan dengan prosedur yagn lebih pasti dan tepat serta metode ini dapat mencapai hasil optimal lebih cepat. Cara utnuk memilihnya digunakan persamaan Ri + Kj = Cij. Ri adalah nilai baris i, Kj nilai kolom j, dan Cij adalah biaya pengangkutan 1 satuan barang dari sumber i ke tujuan j. Adapun langkahlangkah menghitungnya sebagai berikut : a. Isilah table pertama dari sudut kiri ke atas ke kanan bawah,


STMIK BUDIDARMA


Hal : 98

b. Menentukan nilai baris dan kolom Nilai baris dan kolom ditentukan berdasarkan persamaan di atas (Ri + Kj = Cij). Baris pertama selalu diberi nilai 0, dan nilai baris-baris yang lain dan nilai semua kolom ditentukan berdasarkan hasil-hasil hitungan yagn telah diperoleh. Bila nilai suatu baris sudah diperoleh, maka nilai kolom yang dihubungkan dengan segi empat batu dapat dicari dengan rumus Ri + Kj = Cij. Nilai baris W = Rw = 0 Mencari nilai kolom A : RW + KA = CWA 0 + KA = 20, nilai klom A = KA = 20 Mencari nilai kolom dan baris yang lain : RW + KB = CWB

; 0 + KB = 5

; KB = 5

RH + KB = CHB

; RH + 5 = 20

; RH = 15

RP + KB = CPB

; RH + 5 = 10

; RP = 5

RP + KC = CPC

; 5 + KC = 19

; KC = 14

Nilai-nilai ini kemudian diletakkan pada baris/kolom yagn bersangkutan, seperti terlihat pada Tabel 5.9. Tabel 5.9. Tabel pertama. Ke Dari

Gudang

Gudang

Gudang

Kapasitas

A

B

C

Pabrik

Pabrik W

90

60

(+) (-)

5

8

20

10

10

19

50

Pabrik H

40

(-)

15

50

(+)

Pabrik P Kebutuhan Gudang

10

25

40

10

50

110

40

90 60 50 200

c. Menghitung indeks perbaikan Indeks perbaikan adalah nilai dari segi empat akhir (segi empat yang kosong). Mencarinya dengan rumus : Cij – Ri – Kj = Indeks perbaikan Tabel 5.10. menghitung indeks perbaikan Segi empat HA PA WC HC


Cij – Ri – Kj 15 – 15 – 20 25 - 5 – 20 8 - 0 – 14 10 – 15 - 14

Indeks perbaikan -20 0 -6 -19

STMIK BUDIDARMA


Hal : 99

d. Memilih titik tolah perubahan Segi empat yang mempunyai indeks perbaikan negative berarti bila diberi alokasi (diisi) akan dapat mengurangi jumlah biaya pengangkutan. Bila nilainya positif berarti pengisian akan menyebabkan kenaikan biaya pengangkutan. Segi empat yagn merupakan titik tolak perubahan adalah segi empat yang indeksnya “bertanda negative”, dan “angkanya terbesar”. Dalam Tabel 5.10, ternyata yang memenuhi syarat adalah segi empat HA. Olwh karena itu segi empat ini dipilih sebagai segi empat yagn akan diisi. e. Memperbaiki alokasi Berilah tanda positif pada segi empat yang terpilih (HA). Pilihlah 1 segi empat terdekat yang isi dan sebaris (HB), 1 segi empat yang isi terdekat dan sekolom (WA); berilah tanda negative pada 2 segi empat ini. Kemudian pilihlah satu segi empat yang bertanda negative tadi (WB), dan berilah segi empat ini tanda positif. Selanjutnya pindahkanlah alokasi dari segi empat yang bertanda negative ke yagn bertanda positif sebanyak isi terkecil dari segi empat yang bertanda positif (50). Jadi segi empat HA kemudian berisi 50, segi empat HB berisi 60 – 50 = 10, segi empat WB berisi 40 + 50 = 90, dan segi empat WA menjadi tidak berisi. Lihat Tabel 5.9 f.

Ulangilah langkah-langkah tersebut di atas, mulai langkah nomor b sampai diperoleh

biaya terendah. Bila masih ada indeks perbaikan yang bernilai negative berarti alokasi tersebut masih dapat diubah utnuk mengurangi biaya pengangkutan. Bila sudah tidak ada indeks yagn negative berarti sudah optimal. Sebagai contoh perubahan pertama sampai mencapai table optimal dapat dilihat pada Tabel 5.11, a, b, c, d, dan e, Tabel 5.11. Perubahan alokasi untuk memperoleh alokasi optimal dengan Metode MODI (a) Ke Dari

Gudang

Gudang

Gudang

Kapasitas

A

B

C

Pabrik

Pabrik W

50

(-)

Pabrik H

5

8

20

10

10

19

90

(+)

15

40 10

50

(+)

Pabrik

(-)

25

60

P Kebutuhan Gudang

10

50

90 60 50

40

110

40

200

Biaya transportasi = 90 (5) + 50(15) + 10(20) +10(10) + 40(19) = 2260


STMIK BUDIDARMA


Hal : 100

(b) Ke Dari

Gudang

Gudang

Gudang

Kapasitas

A

B

C

Pabrik

Pabrik

5

8

20

10

90

W Pabrik

15 10

H

50

(+)

(-)

Pabrik

25

10 (+)

50

Gudang

19

40

50

(-) 10

Kebutuhan

60

10

40

P

90

30

110

40

200

Biaya transportasi = 90(5) + 50(15) + 10(10) + 20(10) + 30(19) = 2070 (c) Ke Dari

Gudang

Gudang

Gudang

Kapasit

A

B

C

as Pabrik

Pabrik

5

8

20

10

90

W Pabrik

15 10

H

50

(+)

(-)

Pabrik

25

10 (+)

Kebutuhan Gudang

19

40

50

(-) 10

50

60

10

40

P

90

30

110

40

200

Biaya transportasi = 60(5) + 30(8) + 50(15) + 10(10) + 50(10) = 1890 (d) Ke Dari

Gudang

Gudang

Gudang

Kapasitas

A = 13

B=5

C=8

Pabrik

Pabrik

5 60

W Pabrik H

15 50


8 30

20

10

90 60

10

STMIK BUDIDARMA

Modul : KKMI3413-Teknik Riset Operasional Pabrik

25

Hal : 101 10

P

19

50

Kebutuhan

50

Gudang

110

40

50 200

Tabel (d) tidak bisa dioptimalkan lagi, karena indeks perbaikan pada setiap segi empat akhir sudah tidak ada yang negative, seperti terlihat pada Tabel 5.12. Tabel 5.12. Indeks perbaikan dari Tabel 5.11e Segi empat WA HB PA PC

Cij – Ri – Kj 20 – 0 – 5 20 - 2 – 5 25 - 5 – 13 19 – 5 - 8

Indeks perbaikan 15 13 7 6

5.4. Metode Vogel’s Approximation Metode vogel atau Vogel’s Approximation Method (VAM) merupakan metode yang lebih cepat untuk dapat mengatur alokasi dari beberapa sumber ke beberapa daerah pemasaran. Adapun langkah-langkah untuk mengerjakannya adalah sebagai berikut : 1. Susunlah kebutuhan, kapasitas masing-masing sumber, dan biaya pengangkutan ke dalam matriks seperti pada Tabel 5.4. 2. Carilah perbedaan dari dua biaya terkevil (dalam nilai absolute), yaitu biaya terkecil dan terkecil kedua untuk tiap baris dan kolom pada matriks (Cij). Misalnya pada baris W biaya angkut terkecil = Rp 5,00 dan nomor dua dari yang terkecil – Rp 8,00. Jadi nilai baris W = 8 – 5 = 3. Demikian seterusnya nilai-nilai yang lain sebagai berikut : Baris H =

15 – 10 = 5

Baris P

=

19 – 10 = 9

Kolom A

=

20 – 15 = 5

Kolom B

=

10 – 5 = 5

Kolom C

=

10 – 8 =2

3. Pilihlah 1 nilai perbedaan-perbedaan yang terbesar di antara semua niilai perbedaan pada kolom dan baris. Dalam hal ini baris P mempunyai nilai perbedaan terbesar, yaitu 9. 4. Isilah pada salah satu segi empat yang termasuk dalam kolom atasu baris terpilih, yaitu pada segi empat yang biayanya terendah di antar segi empat lain pada kolom/baris itu. Isiannya sebanya mungkin yagn biasa dilakukan. Misalnya pada baris P, biaya angkut untuk segi empat PA = 25, segi empat PB = 10, dan segi empat PC = 19. Yang terkecil adalah biaya pada segi empat PB. Maka kita isi segi empat PB dengan 50 satuan (lebih dari 50 satuan tidak mungkin karena kapasitas pabrik P = 50)


STMIK BUDIDARMA


Hal : 102

Tabel 5.13. Feasible solution mula-mula dari metode Voge’s approximation

Pabrik

W H P

Kebutuhan Perbedaan kolom

A 20 15 25 50 5

Gudang B 5 20 10 110 5

C 8 10 19 40 2

Perbedaan Kapasitas baris 90 3 60 5 50 9 Pilihan XPB = 50 Hilangkan baris P

5. Hilangkan baris P karena baris tersebut sudah diisi sepenuhnya (kapasitas penuh) sehingga tidak mungkin diisi lagi. Kemudian perhatikan kolom dan baris yagn belum terisi/teralokasi (baris W, H, dan kolom A, B, C). 6. Tentukan kembali perbedaan (selisih) biaya pada langkah ke 2 untuk kolom dan baris yang belum terisi. Ulangi langkah 3 sampai dengan langkah 5, sampai semua baris dan kolom sepenuhnya teralokasi lihat Tabel 5.14. Tabel 5.14. Feasible solution dari metode VAM lanjutan

W Pabrik H Kebutuhan Perbedaan kolom

A 20 15 50 5

W Pabrik H Kebutuhan Perbedaan kolom

A 20 15 50 5

Pabrik Kebutuhan

A 15 50

H

Gudang B 5 20 60 15

Gudang

Gudang

C 8 10 40 2

Perbedaan Kapasitas baris 90 3 60 5 Pilihan XWB = 60 Hilangkan baris B

C 8 10 40 2

Perbedaan Kapasitas baris 30 12 60 5 Pilihan XWC = 30 Hilangkan baris W

C 10 40

Perbedaan Kapasitas 60 Pilihan XHA = 50 XHC = 10

Jadi, matriks alokasi sengan metode Vogel’s Approximation di atas adalah sebagai berikut :


STMIK BUDIDARMA


Hal : 103

Tabel 5.15. Matriks hasil alokasi dengan metode VAM Ke Dari

Gudang

Gudang

Gudang

Kapasitas

A

B

C

Pabrik

Pabrik

5 60

W Pabrik

90

30

15

H

8

20

50

10

60

10

Pabrik

25

10

P

19

50

50

Kebutuhan

50

Gudang

110

40

200

7. Setelah terisi semua, maka biaya transportasinya yang harus dibayar adalah 60 (Rp 5,00) + 30 (Rp 8,00) + 50( 15,00) + 10(Rp 10,00) + 50(Rp 10,00) = Rp 1.890,00 8. Bila nilai perbedaan aa 2 yang besarnya sama, missal yang satu terletak pada kolom maka: Lihatlah segi empat yang masuk ke dalam kolom maupun baris yang mempunyai nilai terbesar. Bila segi empat ini mempunyai biaya terendah di antara segi empat pada baris atau klomnya, maka isian alokasi maksimum pada segi empat ini. Bila biayanya tidak terendah, maka pilihlah segi empat yagn akan diisi berdasar salah satu, baris terpilih atau kolom terpilih, seperti pada langkah 4 dan 5 Kebaikan dari metode Vogel ini adalah mudah menghitungnya. Tetapi hasil pemecahan dari metode ini kadang-kadang masih dapat dioptimalkan dengan metode lain, misalnya metode Simples yang akan dibicarakan kemudian. 5.5. Kapasitas Tidak Sama dengan Kebutuhan Bila

kebutuhan

tidak

sama

dengan

kapasitas

yagn

tersegia,

maka

untuk

menyelesaikannya harus dibuat kolom semu (dummy column) atau baris semu (dummy row), sehingga jumlah isian kolom jumlah isian baris semua. Contoh untuk kebutahan lebih kecil dari kapasitas yagn tersedia seperti terlihat pada Tabel 5.16, sedang untuk kebutuhan yagn lebih banyak dari kapasitas yagn tersedia seperti terlihat pada Tabel 5.17. Setelah diadakan penambahan baris atau kolom “dummy” ini dengan biaya nol (0) dapat diselesaikan dengan metode stepping stone, MODI atau VAM.


STMIK BUDIDARMA


Hal : 104

Tabel 5.16. Kebutuhan lebih kecil dari sumber (kapasitas) yang tersedia. Ke

Gudang

Gudang

Gudang

Dummy

Jlh

A

B

C

D

Kapasita

Dari

s Pabrik

20

5

8

0

W

90

Pabrik

15

20

10

0

H

60

Pabrik

25

10

19

0

P

100

Jumlah

50

Kebutuhan

110

40

50

250

Tabel 5.17. Kebutuhan lebih besar dari sumber yang tersedia Ke Dari

Gudang

Gudang

Gudang

Jumlah

A

B

C

Kapasita s

5

Pabrik

8 90

W 15

Pabrik

20

10 60

H 25

Pabrik

10

20 50

P 0

Dummy

0

0 50

Q Jumlah Kebutuhan

100

110

40

250

5.6 Masalah Degeneracy Di dalam mengisi table awal berdasar sudut kiri atas kadang-kadang terjadi degeneracy, yaitu apabila banyaknya segi empat yang terisi kurang dari m + n – 1 (m banyaknya baris dan n banyaknya kolom). Misalnya seperti yang terdapat pada Tabel 5.18, segi emapt XB merupakan segi empat yagn tidak terisi. Dalam mencari nilai baris dan kolom :


STMIK BUDIDARMA


Hal : 105

RW = 0 RW + KA = CWA; 0 + KA = 20; KA = 20 RW + KB = CWB; 0 + KB = 5; KB = 5 Sampai disini tidak bias kita lanjutkan untuk mencari nilai baris H, karena segi HB kosong. Untuk mengatasi hal ini bias kita isi segi empat HB dengan nilai isian 0. Dengan demikian jumlah segi empat yang terisi ada 6, tepat sama dengan m + n – 1 (3 + 4 – 1), seperti terlihat pada Tabel 5.19. Tabel 5.18. Terdapat 5 segi empat yang terisi kurang dari 6 (=3 + 4 – 1) Ke Dari

Gudang

Gudang

Gudang

Gudang

Kapasitas

A = 20

B=5

C

D

Pabrik

Pabrik

5

8

11

W

90

Pabrik

15

20

10

H

15

40

Pabrik

25

10

20

60

20

20

P

50

Kebutuhan

50

Gudang

40

40

50

70

200

Tabel 5.19. Segi empat HB diisi 0, sehingga banyaknya segi empat yang terisi ada 6 tepat sama dengan 3 + 4 – 1 Ke Dari

Gudang

Gudang

Gudang

Gudang

Kapasitas

A = 20

B=5

C = -5

D=0

Pabrik

Pabrik W

5 50

Pabrik H

90 20

0 25

10 40

10

Gudang

15 20

20

P Kebutuhan

11

40 15

Pabrik

8

20 50

50

40

40

60

70

50 200

Dengan sendirinya nilai dari semua kolom dan baris dari Tabel 5.19 ini dapat dicari, karena segi empat HB sudah terisi. RH + KB = CHB; RH +5 = 20; RH = 20 – 5 = 15


STMIK BUDIDARMA


Hal : 106

RH + KC = CHX; 15 + KC = 10; KC = 10 – 15 = -5 RH + KD = CHD; 15 + KD = 15; KD = 15 – 15 = 0 RP + KD = CHD; RP + 0 = 20; RP = 2 Berdasarkan nilai-nilai tersebut di atas nilai indeks perbaikan dapat dicari dan perbaikan dapat dilakukan sampai table optimal, caranya sama dengan yang telah dibicarakan di depan. 5.7. Penggunaan Programa Linier Masalah transportasi ini dapat juga dipecahkan dengan metode programa linier. Sudah dibicarakan di depan bahwa kebutuhan tidak selalu sama dengan kapasitas yang tersedia. Mungkin kebutuhan lebih besar dari kapasitas, atau sebaliknya. Berikut ini akan disajikan perumusan masalah kalau kebutuhan sama, lebih besar atau lebih kecil dari kapasitas yang tersedia. Setelah masalah dirumuskan, maka dapat di selesaikan dengan langkah-langkah dalam metode linear programming. a. Perumusan masalah kalau kebutuhan sama dengan kapasitas : Fungsi tujuan : minimumkan Z =

m

n

i =1

j =1

∑ ∑

CijXij

CijXij n

Batasan-batasan : (1)

∑

Xij = ai (i=1, 2, ….., m)

j =1

m

(2)

∑

Xij = bi (j=1, 2, ….., n)

i =1

(3) Xij ≥ 0. Pada rumusan di atas semua kebutuhan dapat dipenuhi, semua kapasitas sumber dialokasikan, dan nilai alokasi harus positif. b. Bila kebutuhan lebih kecil dari kapasitas. Fungsi tujuan : minimumkan Z =

m

n

i =1

j =1

∑ ∑

CijXij

n


∑

Xij ≤ ai (i=1, 2, ……, m)

j =1

m

(2)

∑

Xij = bi (j=1, 2, ….., n)

i =1

(3) Xij ≥ 0. Pada rumusan ini semua kebutuhan dapat dipenuhi, tetapi kapasitas sumber tidak bias dimanfaatkan sepenuhnya.


STMIK BUDIDARMA


Hal : 107

c. Bila kebutuhan lebih besar dari kapasitas. Fungsi tujuan : minimumkan Z =

m

n

i =1

j =1

∑ ∑

CijXij

n


∑

Xij = ai (i=1, 2, ….., m)

j =1

m

(2)

∑

Xij ≤ bi (j=1, 2, ….., n)

i =1

(3) Xij ≥ 0. Pada rumusan ini tidak semua kebutuhan bias dipenuhi meskipun kapasitas sumber telah digunakan sepenuhnya. Simbol i menunjukkan nomor sumber, dari sumber 1, 2, …… sampai dengan yang ke-m, j menunjukkan nomor tempat tujuan pengiriman, mulai yang ke-1, 2, …….. sampai tempat yang ke-n; Xij menunjukkan banyak barang yang dikirimkan dari sumber i ke tempat tujuan j, sedang Cij ongkos angkut setiap satuan barang dari ke j. Arti batasan pada ketiga macam perumusan masalah ini ialah: Batasan (1) merupakan batasan kapasitas tersedianya barang di setiap sumber, batasan (2) merupakan batasan kebutuhan di tempat-tempat tujuan, dan batasan ke-(3) merupakan batasan tidak negatig (nonnegative

constraint).

Fungsi

tujuan

berusaha

untuk

meminimumkan

jumlah

biaya

pengangkutan seluruhnya. Sebagai contoh lihat perumusan masalah di depan, yang kalau diformulasikan sebagai berikut : Minimumkan Z = 20XWA + 15XHA + 25XPA + 5KWB + 20KHB + 10XPB + 8XWC + 10XHC + 19XPC Batasan-batasan :

XWA + XWB + XWC = 90 XHA + XHB + XHC = 60 XPA + XPB + XPC

= 50

XWA + XHA + XPA = 50 XWB + XHB + XPB = 110 XWC + XHC + XPC = 40 XWA, XWB…………XPC ≥ 0 Bila diselesaikan, maka nilai X dan Z yang optimal adalah sebagai berikut :


STMIK BUDIDARMA

Modul : KKMI3413-Teknik Riset Operasional XWB = 60

Hal : 108

XPB = 50

XWC = 30 XHA = 10

Z = 1890

XHC = 10 SOAL-SOAL 1.

Saat ini Pertamina memiliki tiga daerah penambangan minyak di pulau jawa, yaitu di Cepu, Cilacap, dan Cirebon dengan kapasitas produksi masing- masing sebesar 600.000galon, 500.000 galon, dan 800.000 galon setiap harinya. Dari tempat- tempat tersebut, minyak kemudian diangkut ke daerah- daerah pemasaran yang terspusat di semarang, Jakarta, Bandungn, dengan daya tampung masing- masing sebbanyak 400.000 galon, 800.000 galon, dan 700.000 galon perhari. Ongkos pengangkutan per 100.000 galon adalah: Dari Cepu ke semarang dan Jakarta masing- masing sebesar: Rp

120.000 dan Rp

180.000. Dari Cilacap ke Semarang, Jakarta dan Bandung masing- masing Rp 300.000, Rp 100.000 dan 80.000. Dari Cirebon ke semarang, Jakarta dan bandung masing- masing : Rp 200.000, Rp 250.000, dan Rp 120.000. Bagaimana ususl saudara untuk mendistribusikan minyak tersebut sebaik- baiknya? 2.

Direktur PN GIA menerangkan bahwa untuk melayani penerbangan di jawa barat harus dibuka 4 bandar udara, yaitu di Jakarta, bandung, Cirebon, dan Cilacap[, sehingga pesawat dapat mengisi bahan baker pada keempat lapangan terbang tersebut. Kebutuhan akan bahan baker ini akn disuplai oleh tiga agen pertamina, yaitu pertamina I, II,dan II yanga masing-masing dapat menyediakan sebanyak 275.000 galon, 550.000 galon dan 660.000. adapun masing- masing lapangan terbang di perkirakan akan membutuhkan bahan baker sebanyak: •

Jakarta

•

Bandung : 330.000 galon

•

Cirebon

: 220.000 galon

•

Cilacap

:110.000 galaon


: 440.000 galon

STMIK BUDIDARMA


Hal : 109

Harga bahan bakar per galon yang dijual pada masing-masing Bandar udara oleh agen I, II, dan III adalah seperti pada table berikut: Agen

I

II

III

1

11

13

9

2

9

12

4

3

10

11

14

4

10

7

8

Bandara

Formulasikan persoalan di atas sebagai persoalan transaportasi, dan dapatkan jawaban optimumnya. 3.

Seorang pedagang beras mempunyai 3 gudang di Cianjur, Cikampek, dan Sumedang, yang masing- masing menyimpan beras sebanyak 60,80,dan 100 ton. Pedagang tersebut mempunyai daerah pemasaran di Bandung, Bogor, Jakarta, dan Cirebon yang masingmasing membutuhkan beras sebanyak 40, 60, 80, dan 50 ton. Cianjur Ke Bandung

= Rp 11.000,00

Ke Bogor

= Rp 12.000,00

Ke Jakarta

= Rp 13.000,00

Ke Cirebon

= Rp 14.000,00

Cikampek Ke Bandung = Rp 14.000,00 Ke Bogor

= Rp13.000,00

KeJakarta

= Rp12.000,00

Ke Cirebon

= Rp10.000,00

Sumedang ke Bandung = Rp 10.000,00 Ke Bogor

= Rp12.000,00

Ke Jakarta

= Rp 12.000,00

Ke Cirebon

= Rp 11.000,00

Bila saudara diminta, bagaimanakah pengalokasian /pendistribusian beras yang optimum dan berapa ongkosnya.


STMIK BUDIDARMA


Hal : 110

6 MASALAH PENUGASAN

6.1. PERUMUSAN MASALAH Seperti masalah transportasi, masalah penugasan (assignment problem) merupakan suatu kasus khusus bagi masalah linear programming pada umumnya. Dalam dunia usaha (bisnis) dan industri, manajemen sering menghadapi masalah-masalah yang berhubungan dengan penugasan optimal dari bermacam-macam sumber yang produktif atau personalia yang mempunyai tingkat efisiensi yang berbeda-beda untuk tugas-tugas yang berbeda-beda. Metode Hungarian (Hungarian method) adalah salah satu dari beberapa teknik-teknik pemecahan yang tersedia untuk masalah-masalah penugasan. Metode ini mula-mula dikembangkan oleh seorang ahli matematika berkebangsaan Hungaria yang bernama D. Konig dalam tanuh 1916 Untuk dapat menerapkan metode Hungarian, jumlah sumber-sumber yang ditugaskan harus sama persis dengan jumlah tugas yang akan diselesaikan. Selain itu, setiap sumber harus ditugaskan hanya untuk satu tugas. Jadi masalah penugasan akan mencakup sejumlah n sumber yang mempunyai n tugas. Ada n! (n factorial) penugasan yang mungkin dalam satu masalah karena perpasangan satu-satu. Masalah ini dapat dijelaskan dengan mudah oleh bentuk matriks segi empat, di mana baris-barisnya menunjukkan sumber-sumber dan kolomkolomnya menunjukkan tugas-tugas. Masalah penugasan dapat dinyatakan secara matematis dalam suatu bentuk linear programming sebagai berikut : Minimumkan (maksimumkan): Z=

m

n

i =1

j =1

∑ ∑

CijXij

Dengan batasan: m

∑ i =1

n

Xij =

∑

Xij = 1

j =1

Dan Xij ≥ 0 (Xij = Xij 2 Dimana Cij adalah tetapan yang telah diketahui.


STMIK BUDIDARMA


Hal : 111

6.2. Masalah Minimasi Suatu perusahaan kecil mempunyai 4 (empat) pekerjaan yang berbeda untuk diselesaikan oleh 4 (empat) karyawan. Biaya penugasan seorang karyawan untuk pekerjaan yang berbeda adalah berbeda karena sifat pekerjaan berbeda-beda. Setiap karyawan mempunyai tingkat keterampilan, pengalaman kerja dan latar belakang pendidikan serta latihan yang berbeda pula. Sehingga biaya penyelesaian pekerjaan yang sama oleh para karyawan-karyawan yang berlainan juga berbeda. Matriks pada Tabel 6.1 menunjukkan biaya penugasan karyawan untuk bermacam-macam pekerjaan. Sebagai contoh A dapat menyelesaikan pekerjaan I pada biaya Rp 15,00, pekerjaan II pada biaya Rp 20,00, dan seterusnya. Tabel 6.1. Matriks biaya(Rp) Pekerjaan

I II III Karyawan A 15,00 20,00 18,00 B 14,00 16,00 21,00 20,00 23,00 C 25,00 18,00 18,00 D 17,00 Karena metode penugasan Hungarian mensyaratkan perpasangan

IV 22,00 17,00 20,00 16,00 satu-satu, maka ada

4! (4, 3, 2, 1 = 24) kemungkinan penugasan. Langkah-langkah penyelesaiannya adalah sebagai berikut : 1. Langkah pertama adalah mengubah matriks biaya menjadi matriks opportunity cost. Ini dicapai dengan memilih elemen terkecil dari setiap baris dari matriks biaya mula-mula untuk mengurangi seluruh elemen (bilangan) dalam setiap baris. Sebagai contoh, seluruh elemen terkecil baris A (=15) digunakan untuk mengurangi seluruh elemen pada baris A. Sehingga paling sedikit akan diperoleh satu elemen yang bernilai nol sebagai hasilnya. Prosedur yang sama diulang untuk setiap baris pada Tabel 6.1 untuk mendapatkan matriks biaya yang telah dikurangi (reduced-cost matrix) seperti yang ditunjukkan Tabel 6.2 Tabel 6.2. Reduced-cost matrix Pekerjaan Karyawan A B C D

I

II

III

IV

0 0 5 1

5 2 0 2

3 7 3 2

7 3 0 0

2. Reduced cost-matrix di atas terus dikurangi untuk mendapatkan total-opportunity-cost matric. Hal ini dapat dicapai dengan memilih elemen terkecil dari setiap kolom pada


STMIK BUDIDARMA


Hal : 112

reduced-cost matrix untuk mengurangi seluruh elemen dalam kolom-kolom tersebut. Pada contoh di atas hanya dilakukan pada kolom III karena semua kolom lainnya telah mempunyai elemen yang bernilai nol. Bila langkah pertama telah menghasilkan paling sedikit satu nilai nol pada setiap kolom, langkah kedua ini dapat dihilangkannya. Matriks total-opportunity-cost ditunjukkan dalam Tabel 6.3 Tabel 6.3. Total-opportunity-cost matrix Pekerjaan Karyawan A B C D

I

II

III

IV

0 0 5 1

5 2 0 2

1 5 1 0

7 3 0 0

Dalam contoh total-opportunity-cost matrix pada Tabel 6.3, terdapat paling sedikit satu nilai nol, dalam setiap baris dan setiap kolom. 3. Langkah berikutnya adalah mencari skedul penugasan dengan suatu total-opportunitycost nol. Untuk mencapai penugasan ini dibutuhkan 4 (empat) “independent zeros” dalam matriks. Ini berarti setiap karyawan harus ditugaskan hanya untuk satu pekerjaan dengan opportunity-cost nol; atau setiap pekerjaan harus diselesaikan hanya oleh satu karyawan. Prosedur praktis untuk melakukan test optimalisasi adalah dengan menarik sejumlah minimum garis horizontal dan/atau vertical untuk sejumlah elemen bernilai nol dalam total-opportunity-cost matrix (lihat Tabel 6.4). Bila jumlah garis sama dengan jumlah baris atau kolom penugasan optimal adalah feasible. Bila tidak sama maka matriks harus direvisi. Tabel 6.4. Test for optimality

Pekerjaan I

II

III

IV

0 0 5 1

5 2 0 2

1 5 1 0

7 3 0 0

Karyawan A B C D

Dalam Tabel 6.4 ada tiga baris yang meliputi seluruh nilai nol disbanding empat beris atau kolom, sehingga langkah berikutnya diperlukan untuk merevisi matriks. 4. Untuk merevisi total-opportunity-cost matrix, pilih elemen terkecil yang belum terliput garisgaris (yaitu opportunity-cost terendah, atau pada contoh di atas = 1) untuk mengurangi seluruh elemen yang belum terliput. Kemudian tambahkan dengan jumlah yang sama


STMIK BUDIDARMA


Hal : 113

(nilai elemen terkecil) pada seluruh elemen-elemen yang mempunyai dua garis yang saling bersilangan ( 5 pada baris C dan 1 pada baris D), atau sama dengan 6 dan 2. Masukkan hasil-hasil ini pada matriks, dan menyelesaikan matriks dengan seluruh elemenelemen yang telah terlipu tampa perubahan, ulangi langkah 3. Matriks yang telah direvisikan pada Tabel 6.5 berikut ini didapatkan dengan mengikuti prosedur di atas. Tabel 6.5. Revised matrix dan test for optimality

Pekerjaan I

II

III

IV

0 0 6 2

4 1 0 2

0 4 1 0

6 2 0 0

Karyawan A B C D

5. Dalam Tabel 6.5 dibutuhkan empat garis untuk meliputi seluruh nilai nol atau sama dengan jumlah baris atau kolom, sehingga matriks penugasan optimal telah tercapai. Karyawan B ditugaskan untuk pekerjaan I karena baris B hanya mempunyai satu nilai nol pada kolom I. Kolom II berisi satu nol pada baris C, jadi karyawan C ditugaskan untuk pekerjaan II. Kemudian karyawan A ditugaskan untuk pekerjaan III, karena pekerjaan I telah ditugaskan karyawan B. Karyawan D ditugaskan untuk pekerjaan terakhir IV. Skedul penugasan optimal dengan biaya minimum adalah sebagai berikut : Skedul penugasan A – III B–I C – II D – IV

Rp 18,00 14,00 20,00 10,00 Rp 68,00

6.3. Jumlah Pekerjaan Tidak Sama dengan Jumlah Karyawan Untuk memnuhi persyaratan suatu matriks segi empat bujur sangkar, agar metode Hungarian dapat diterapkan, bila terdapat jumlah pekerjaan lebih besar dari jumlah karyawan, maka harus ditambahkan suatu karyawan semu (dummy worker). Biaya semu adalah sama dengan nol, karena tidak akan terjadi biaya bila suatu pekerjaan ditugaskan ke karyawan semu. Sebalikanya bila jumlah karyawan lebih besar dari jumlah pekerjaan, maka harus ditambahkan suatu pekerjaan semu (dummy job). Sebagai contoh, bila jumlah pekerjaan lebih besar dari jumlah karyawan, dapat dilihat pada Tabel 6.6


STMIK BUDIDARMA


Hal : 114

Tabel 6.6. Jumlah pekerjaan lebih besar dari jumlah karyawan

Pekerjaan I

II

III

IV

Karyawan Rp 21,00 Rp 18,00 Rp 20,00 A Rp 15,00 15,00 21,00 16,00 B 14,00 17,00 23,00 20,00 C 25,00 18,00 18,00 18,00 D 17,00 0,00 0,00 0,00 0,00 Dummy E Prosedur penyelesaian selanjutnya sama dengan langkah-langkah di atas. 6.4. Masalah Maksimasi Metode penugasan Hungarian untuk minimasi juga dapat diterapkan untuk masalah penugasan yang menyangkut maksimasi. Dalam masalah maksimasi, matriks elemen-elemen menunjukkan tingkat keuntungan (atau indeks produktivitas). Efektivitas pelaksanaan tugas oleh karyawan-karyawan individual diukur dengan jumlah kontribusi keuntungan. Matriks 6.7 menunjukkan bahwa karyawan A mempunyai keterampilan yang dibutuhkan menangani 5 (lima) pekerjaan-pekerjaan yang berlainan. Tabel 6.7. Matriks keuntungan

Pekerjaan I

II

III

Rp 12,00 10,00 8,00 15,00 13,00

Rp 10,00 9,00 7,00 8,00 14,00

IV

Karyawan A B C D E

Rp 10,00 14,00 9,00 13,00 10,00

Rp 15,00 13,00 12,00 11,00 17,00

Langkah pertama dalam masalah maksimasi adalah mengubah matriks keuntungan menjadi suatu matriks opportunity-loss. Dalam masalah ini, A mempunyai keuntungan tertinggi Rp !5,00 bila dia ditugaskan pada pekerjaan V. Oleh karena itu, bila A ditugaskan pada pekerjaan I (yang kontribusi keuntungannya = Rp 10,00), ada sebesar Rp 5,00 sebagai opportunity-loss yang terjadi dengan penugasan ini, dan seterusnya. Seluruh elemen dalam setiap baris dikurangi dengan nilai maksimum opportunity-loss yang ditunjukkan dalam Tabel 6.8. Matriks ini sebenarnya bernilai negative. Tabel 6.8. Matriks opportunity-loss

Pekerjaan I

II

III

IV

5 1 3

3 5 4

7 0 4

0 2 0

Karyawan A B C


STMIK BUDIDARMA

Modul : KKMI3413-Teknik Riset Operasional D E

3 7

Hal : 115

1 4

0 0

5 0

Seperti sebelumnya, setiap baris akan berisi nilai nol. Langkah berikutnya dengan meminimumkan opportunity-loss akan memaksimumkan kontribusi keuntungan total. Matriks total-opportunity-loss yang ditunjukkan dalam Tabel 6.9 didapatkan melalui pengurangan seluruh elemen dalam setiap kolom dengan elemen terkecil dari kolom tersebut. Tabel 6.9. Matriks total-opportunity-loss Pekerjaan

I II Karyawan A 4 2 B 0 4 C 2 3 D 2 0 E 6 3 Dalam Tabel 6.9 seluruh elemen bernilai nol

III

IV

2 3 2 5 0 dapat diliput

7 0 0 2 4 0 0 5 6 0 hanya dengan empat garis.

V

Jadi, matriks harus dikurangi menurut langkah ke-4 seperti yang telah dijelaskan di muka. Matriks baru ditunjukkan oleh Tabel 6.10, dimana penugasan optimal dapat ditentukan. Tabel 6.10. Tabel oprimal

Pekerjaan I

II

III

IV

V

2 0 0 2 6

0 4 1 0 3

0 3 0 5 0

5 0 2 0 6

0 4 0 7 2

Karyawan A B C D E

Skedul penugasan optimal dan keuntungan total untuk dua alternative penyelesaian adalah : Skedul Penugasan I A – II B–1 C–V D – IV E – III

Keuntungan Rp 12,00 14,00 12,00 16,00 14,00 Rp 68,00


Skedul Penugasan 2 A–V B – IV C– D – II E – III

Keuntungan Rp 15,00 15,00 9,00 15,00 14,00 Rp 68,00

STMIK BUDIDARMA


Hal : 116

6.5. Masalah-masalah Penugasan Tambahan Dalam masalah-masalah penugasan di muka, seluruh elemen matriks diketahui konstan. Bagaimana juga, kadang-kadang beberapa elemen matriks tidak diketahui. Ada sejumlah alas an mengapa terdapat elemen-elemen yang tidak diketahui. Dalam masalah penugasan personalia, sebagai contoh, seorang karyawan tertentu tidak dapat ditugaskan untuk melaksanakan pekerjaan tertentu karena tidak memenuhi persyaratan keterampilan yang diperlukan, defisiensi dalam pengetahuan teknis, latihan yang tidak tepat, ketidakmampuan fisik, dan sebagainya. Penugasan untuk keadaan tersebut bias tidak mungkin dilakukan, atau tidak menguntungkan bila dilakukan. Untuk pemecahan suatu masalah penugasan yang tidak mungkin dilakukan, kita hanya menandai setiap elemen penugasan yang tidak mungkin dengan suatu nilai sangat besar yang tidak diketahui, M yaitu, M untuk masalah minimasi dan –M untuk masalah maksimisasi). Langkah pemecahan selanjutnya persis sama dengan prosedur metode Hungarian yang telah dibahas di muka, hanya perlu diperhatikan bahwa penugasan seorang karyawan untuk melaksanakan pekerjaan tertentu yang elemennya diberi tanda M harus dihindari.


STMIK BUDIDARMA

PENDAHULUAN. Modul : KKMI3413-Teknik Riset Operasional Hal : 45

Recommend Documents