1

BAHAN KULIAH

RISET OPERASI (OPERATIONAL RESEARCH)

Disusun Oleh:

SUWAJI, SE. MM

SEKOLAH TINGGI ILMU EKONOMI INDRAGIRI (STIE-I)RENGAT TAHUN AKADEMIK 2015/2016

DAFTAR ISI

1. RISET OPERASI .......................................

2. LINEAR PROGRAMING .......................................

3. METODE SIMPLEKS .......................................

4. MASALAH DUAL DAN PRIMAL .......................................

5. MASALAH PENUGASAN .......................................

6. MASALAH TRANSPORTASI .......................................

-Metode Modi- VAM- Net Work (Jaringan)

7. MANAJEMEN PROYEK .......................................

2

RISET OPERASI (OPERATIONAL RESEARCH)

1. PERKEMBANGAN RISET OPERASIIstilah riset operasi pertama kali dikenalkan dan digunakan di kota kecil Bowdsey, Inggris tahun 1940 oleh Me Closky dan Trefthen. Pada masa itu, pemimpin militer Inggris memanggil sekelompok ahli dari kalangan sipil dari berbagai disiplin ilmu kemudian mengkoor dinasikan mereka dalam suatu kelompok yang diserahi tugas mencari cara yang paling efisien untuk menggunakan alat yang baru ditemukan.

2. ARTI DARI RISET OPERASIKata operations dapat didefinisikan sebagai tindakan-tindakan yang diterapkan pada beberapa masalah atau hipotesis. Sementara Research adalah suatu proses yang terorganisasi dalam mencari kebenaran akan masalah atau hipotesis yang dibuat.

Definisi1RO adalah penerapan metode -metode ilmiah terhadap masalah-masalah rumit yang muncul dalam pengarahan dan pengelolaan dari suatu system besar manusia, mesin, bahan dan uang dalam industri, bisnis, pemerintahan dan pertahanan. (Operational Research Society of Great Britain).

Definisi 2Riset operasi berkaitan dengan menentukan pilihan secara ilmiah bagaimana merancang dan menjalankan system manusia-mesin secara terbaik, biasanya membutuhkan alokasi sumber daya yang langka. (Operation Research Society of America).

Definisi 3Riset operasi adalah seni memberikan jawaban buruk terhadap masalah-masalah, yang jika tidak, memiliki jawaban yang lebih buruk. (T.L. Saaty).

Definisi 4Riset operasi adalah pendekatan dalam pengambilan keputusan yang ditandai dengan penggunaan pengetahuan ilmiah melalui usaha kelompok antar disiplin yang bertujuan menentukan penggunaan terbaik sumber daya yang terbatas. (Hamdi A. Taha).

Definisi 5Riset operasi dalam arti luas dapat diartikan sebagai penerapan metode-metode, teknik-teknik, dan alat-alat terhadap masalah-masalah yang menyangkut operasi-operasi dari sistem-sistem, sedemikian rupa sehingga memberikan penyelesaian optimal. (Churchman, Ackoff, dan Arnoff).

3

3. CIRI-CIRI RISET OPERASICiri yang menonjol dalam riset operasi adalah sbb:a. Riset Operasi merupakan pendekatan kelompok antar disiplin untuk mencari hasil

yang optimum.b. Riset Operasi merupakan teknik penelitian ilmiah untuk mendapatkan solusi yang

optimum.c. Riset Operasi hanya akan memberikan jawaban yang jelek terhadap persoalan jika

tersedia jawaban yang lebih jelek, sehingga Riset Operasi hanya memperbaiki kualitas dari solusi.

Keilmiahan dan Seni Riset Operasi

Aspek keilmiahan dari OR terletak pada penyediaan teknik dan algoritma matematika untuk menyelesaikan masalah. OR merupakan seni karena keberhasilan semua tahap sebelum maupun sesudah solusi model sepenuhnya tergantung pada kreativitas dan kemampuan personal pengambil keputusan. Harus ditekankan, suatu tim OR yang berhasil diharapkan menunjukkan kemampuan yang memadai dalam segi ilmu pengetahuan dan seni.

4. MODEL DALAM RISET OPERASIModel adalah abstraksi atau penyerderhanaan realitas dari system yang kompleks dimana hanya komponen-komponen yang relevan atau factor-faktor yang dominan dari masalah yang dianalisis dan diikutsertakan. Ia menunjukan hubungan-hubungan (langsung dan tidak langsung) dari aksi dan reaksi dalam pengertian sebab dan akibat . Jenis dasar dari model meliputi: Iconic (physical), analogue (diagrammatic) dan symbolic (mathematical).

a. Iconic (Physical) ModelIconic model adalahsuatu penyajian fisik yang tampak seperti aslinya dari suatu sistem nyata dengan skala yang berbeda. Contoh model ini adalah mainan anak-anak, potret, histogram, maket dan lain-lain.

b. Analogue ModelModel analogue lebih abstrak disbanding model iconic, karena tak kelihatan sama antara model dengan system nyata. Contohnya jaringan pipa tempat air mengalir dapat digunakan dengan pengertian yang sama sebagai distribusi aliran listrik. Contoh lain adalah petadengan bermacam-macamwarna merupakan model analog dimana perbedaan warna menunjukan perbedaan cirri, misalnya biru menunjukan air, kuning menunjukan pegunungan, hijau sebagai dataran rendah, dan lain-lain.

c. Mathematic (Symbolic) ModelModel matematik sifatnya paling abstrak. Model ini menggunakan seperangkat simbol matematik untuk menunjukan komponen-komponen (dan hubungan antar mereka) dari sistem nyata. Namun, system nyata tidak selalu dapat diekspresikan dalam rumusan matematik. Model ini dapat dibedakan menjadi deterministic dan probabilistic. Model deterministic dibentukdalam situasi kepastian (certainty). Model ini memerlukan

4

penyederhanaan – penyederhanaan dari realitas karena kepastian jarang terjadi. Model probabilistic meliputikasus-kasus dimana diasumsikan ketidakpastian (uncertainty).

4. TAHAP-TAHAP DALAM RISET OPERASIPola dasar penerapan OR terhadap suatu masalah dapat dipisahkan menjadi beberapa tahapan:a. Merumuskan masalah

Dalam OR, ada tiga pertanyaan penting yang harus dijawab:1) Variabel Keputusan : Yaitu unsur-unsur dalam persoalan yang dapat dikendalikan

oleh pengambil keputusan. Ia sering disebut sebagai instrument.2) Tujuan (obyective): Penetapan Tujuan membantu pengambilan keputusan untuk

memusatkan perhatian pada persoalan dan pengaruhnya terhadap organisasi. Tujuan ini diekspresikan dalam variable keputusan

3) Kendala (constraints): Merupakan pembatas-pembatas terhadap alternative tindakan yang tersedia.

b. Pembentukan ModelModel merupakan ekspresi kuantitatif dari tujuan-tujuan dan kendala-kendala persoalan dalam variable keputusan. Pengambil keputusan menentukan model yang paling cocok untuk mewakili system.

c. Mencari Penyelesaian MasalahDisini bermacam-macam teknik dan metode solusi kuantitatif merupakan bagian utama dari Riset Operasi, diharapkan penyelesaian masalah yang didapat merupakan aplikasi satu atau lebih dari teknik-teknik model.

d. Validasi ModelAsumsi-asumsi yang digunakan dalam membentuk model harus abash. Model harus diperiksa apakah ia mencerminkan berjalanya system yang diwakili. Suatu metode untuk menguji validitas model adalah dengan nmembandingkan kinerja model dengan data dimasa lalu yang tersedia.

e. Penerapan Hasil AkhirTahap terakhir adalah menerapkan hasil model yang telah diuji.

5. METODE-METODE UMUM MENCARI SOLUSIPada umumnya, terdapat tiga metode umum untuk mencari solusi terhadap model OR yaitu: metode analitis yang bersifat deduktif, metode numeric bersifat induktif dan metode monte carlo.

- Metode Analitik merupakan metode yang memerlukan perwujudan model dengan solusi grafik atau dengan perhitungan matematik. Jenis matematika yang digunakan tergantung sifat-sifat model.

5

- Metode Numerik merupakan pendekatan yang berhubungan dengan perulangan atau ncoba-coba prosedur-prosedur, melalui penggunaan perhitungan numeric pada tiap tahapanya.

- Motode Monte Carlo merupakan pendekatan dengan teknik simulasi dimana fungsi distribusi statistic dibuat melalui seperangkat bilangan random.

6. MASALAH-MASALAH DALAM RISET OPERASIMasalah-Masalah Riset Operasi yang didefinisikan dengan baik dan diterima umum adalah sebagai berikut:1) Masalah Alokasi2) Masalah Pertarungan3) Masalah Antri4) Masalah Jaringan5) Masalah Persediaan

7. KELEMAHAN RISET OPERASITeknik-teknik OR memiliki kelemahan sebagai berikut:- Perumusan masalah dalam suatu program Riset Operasi adalah suatu tugas yang

sulit.- Jika suatu organisasi memiliki beberapa tujuan yang bertentangan, maka akan

terjadi suboptimum yaitu suatu kondisi yang tak dapat menolong seluruh organisasi mencapai hasil yang terbaik secara serantak.

- Suatu hubunganh nonlinier yang diubah menjadi linier untuk disesuaikan dengan program linier dapat mengganggu solusi yang disarankan.

6

BAB ILINEAR PROGRAMING

1. LINEAR PROGRAMING

Linear Programing (LP) : Merupakan model matematika pengalokasian sumber daya yang langka dalam rangka mencapai tujuan tunggal untuk memaksimumkan laba atau meminimumkan biaya dan bergantung pada jumlah variable input. Program Linier merupakan salah satu teknik OR yang digunakan paling luas dan diketahui dengan baik.

Pioner dari Program Linier adalah George B. Dantzig dkk. Merupakan peneliti matematika untukmemecahkan masalah logistic militer Angkatan Udara Amerika pada Perng Dunia II. Nama asli teknik ini adalah Program Saling Ketergantungan Kegiatan-kegiatan dalam Suatu Struktur Linier yang kemudian disingkat menjadi Linear Programing. Paper pertama yang berisi metode solusi sekarang dikenal dengan Metode Simpleks,dipublikasikan Dantzig dkk tahun1947.

2. BENTUK UMUM MODEL LINEAR PROGRAMING (LP)Secara umum suatu masalah LP akan ditentukan Variabel Keputusan, Fungsi Tujuan dan Fungsi Kendala yang bersama sama membentuk suatu model matematika :

nMaksimum (Minimum) Z = ∑CuXj

J=iDengan syarat: aijxj (≤, =, ≥) bi, dan untuk semua I (1= 1,2,….n) semua Xj≥ 0Keterangan :Z= Nilai Fungsi Tujuanaij = Banyaknya Sumber daya I yang dikonsumsi sumber daya j

xij = Banyaknya kegiatan j, dimana j = 1,2,…n, n merupakan banyaknya variable keputusan

bi = Banyaknya sumber daya I (I = 1,2,3….m) berarti bayaknya m jenis sumber daya

cj = Sumbangan per unit kegiatan j, untuk masalah maksimisasi C j menunjukan keuntungan atau penerimaan perunit, untuk maslah minimisasi Cj menunjukan biaya perunit.

3. FORMULASI MODELMasalah yang sering dihadapi oleh pengambil keputusan adalah alokasi optimum dari sumber daya yang langka. Sumber daya dapat berupa:

- Uang- Tenaga Kerja- Bahan Mentah- Kapasitas Mesin- Waktu- Kapasitas Ruangan- Teknologi

Setelah masalah diidentifikasi, tujuan ditetapkan dan selanjutnya adalah formulasi model matematika yang meliputi tiga langkah:a. Tentukan Variabel (variable keputusan) dan nyatakan dalam symbol matematikab. Membentuk fungsi tujuan yang ditunjukan sebagai suatu hubungan linier (bukan perkalian)

dari variable keputusan

7

c. Menentukan kendala dari masalah tersebut dan mengekspresikan dalam persamaan dan pertidaksamaan yang juga merupakan hubungan linier dari variable keputusan yang mencerminkan keterbatasan sumber daya masalah tersebut.

Contoh Formulasi Model 1:Masalah Kombinasi Produk:Sebuah Perusahaan Karpet menghasilkan tiga produk yaitu: Karpet A, Karpet B, dan Karpet C. Untuk memproduksi ketiga jenis karpet tsb, Jumlah waktu yang tersedia adalah 240 jam dan bahan mentah yang tersedia adalah 400 kg, harga dari masing masing produk seperti data dibawah ini:

Tabel 1.1

Jenis Produk Kebutuhan Sumber Daya Harga (Rp/unit)Buruh (Jam/unit) Bahan (Kg/unit)

Produk 1 (Karpet A)Produk 2 (Karpet B)Produk 3 (Karpet C)

648

8106

574

Masalah yang dihadapi perusahaan adalah menentukan jumlah masing masing produk yang harus dihasilkan agar keuntungan maksimum, selanjutnya masalah tersebut dirumuskan dalam model

a. Menentukan Variabel (variabel keputusan)Dalam masalah ini variable ada tiga yaitu, Variabel 1 adalahJumlahProduk 1 dilambangkan dengan X1

Variabel 2 adalahJumlah Produk 2 dilambangkan dengan X2

Variabel 3 adalah Jumlah Produk3 dilambangkan dengan X3

b. Fungsi TujuanTujuan dari dari masalah kombinasi produk tersebut adalah untuk memaksimumkan penerimaan total. - Penerimaan total produk 1 (X1) adalah perkalian antara jumlah produk 1 dengan harga

per unit produk 1 (Rp 5)- Penerimaan total produk 2 (X2) adalah perkalian antara jumlah produk 2 dengan harga

per unit produk 1 (Rp 7)- Penerimaan total produk 3 (X3)adalah perkalian antara jumlah produk 1 dengan harga per

unit produk 3 (Rp 4)

Penerimaan Total (Z) dapat dituliskan Zmax = 5X1 + 7X2 + 4X3 .

c. Sistem KendalaDalam hal ini kendala yang dihadapi adalah jumlah buruh dan bahan mentah yang terbatas.1) Kendala Buruh dengan jam kerja yang tersedia adalah 240 jam

- Produk 1 (X1) Jam kerja buruh untuk tiap unit adalah 6 jam ditulis 6X1 jam.- Produk 1 (X2) Jam kerja buruh untuk tiap unit adalah 4 jam ditulis 4X2 jam.- Produk 1 (X3) Jam kerja buruh untuk tiap unit adalah 8 jam ditulis 8X3jam.

Fungsi kendala (1)untuk Jumlah Buruh adalah :6X1 + 4X2 + 8X3 ≤ 240

8

2) Kendala Bahan Mentah- Produk 1 (X1) bahan mentah untuk tiap unit adalah 8 kg ditulis 8X1 kg.- Produk 1 (X2) bahan mentah untuk tiap unit adalah 10 kg ditulis 10X2 kg.- Produk 1 (X3) bahan mentah untuk tiap unit adalah 6 jam ditulis 6X3 kg.

Fungsi kendala (2) untuk Jumlah Buruh adalah :8X1 + 10X2 + 6X3 ≤ 400

Ada batasan bahwa masing-masing variable hanya pada nilai positif karena tentunya tidak masuk akal jika menghasilkan produk dengan jumlah negative. Kendala-kendala ini dinamai dengan non-negativity constraints, secara matematika ditulis dengan :X1 ≥ 0, X2 ≥ 0, X3 ≥ 0

Masalah Linear Programing diatas secara lengkap secara matematis dapat dirumuskan sebagai berikut:

Maksimum, Z = 5X1 + 7X2 + 4X3 .Kendala 6X1 + 4X2 + 8X3 ≤ 240

8X1 + 10X2 + 6X3 ≤ 400X1 , X2 , X3 ≥ 0

Contoh Formulasi Model 2:Masalah Transportasi

Bulog ingin mengangkut beras dari dua daerah surplus ke tiga daerah yang kekurangan pangan. Pasokan dari daerah surplus dan permintaan dari daerah kekurangan serta ongkos angkut per unit pada masing-masing jalur transportasi disajikan melalui data berikut:

Daerah Tujuan PasokanDKI Kaltim NTT

JatimDaerah asal Sulsel

8

15

5

10

6

12

120

80

Permintaan100 70 60 200

230

Permasalahan yang dihadapi bulog adalah menentukan pola pengiriman (distribusi) sedemikian rupa sehingga biaya transportasi total dapat diminimumkan. Agar masalah ini dapat dirumuskan dalam model LP diperlukan dua asumsi:

1) Hanya ada satu jenis beras sehingga kekurangan dapat diambil dari mana saja dan kelebihan dapat diirim kemana saja.

2) Onkos angkut perunit adalah tetap atau tidak dipengaruhi oleh jumlah yang diangkut.

a. Variabel KeputusanYang harus dirumuskan disini adalah volume beras yang diangkut dari setiap daerah surplus ke daerah kekurangan, Misalnya :

XijadalahVolume beras dari sumber i ketujuan jDimana :i = 1 adalah Jatimdan i= 2 adalah Sulsel

9

j = 1 adalah DKI, j = 2 Kaltim, j = 3NTT ,Berarti terdapat 6 variabel.

b. Fungsi TujuanTujuan Bulog adalah menekan biaya transportasi total, maka fungsi tujuan dapat dituliskan

Z = 8X11 + 5X12 + 6X13 + 15X21 + 10X22 + 12X23

C. Fungsi KendalaKendalanya adalah jumlah permintaan lebih besar dari pasokan, berarti seluruh pasokan akan habis, sehingga kendala pasokan bertanda =, tidak semua pasokan akan terpenuhi sehingga kendala permintaan bertanda ≤ , maka model LP maslah tersebut menjadi:

Minimumkan Z = 8X11 + 5X12 + 6X13 + 15X21 + 10X22 + 12X23

Dengan syarat X11 + X12 +X13 = 120X21 + X22 + X23 = 80X12+ X21 ≤ 100X11 + X22 ≤ 70X11 + X12 ≤ 60

Ciri khas masalah transportasi adalah pada kendala yang mangatakan bahwa semua koefisien nilainya sama dengan satu.

10

Menyelasaiakan Permasalahan Maksimisasi dan minimisasi

A. Masalah Maksimisasi Masalah maksimisasi biasanya akan berupa upaya untuk memaksimalkan keuntungan atau hasil.Contoh Soal Maksimisasi:Sebuah prabrik akan memproduksi dua jenis produk yaitu kain sutera dan wol. Untuk berproduksi dibutuhkan bahan baku benang sutera, bahan baku wol juga tenaga kerja. Maksimum penyediaan benang sutera adalah 60 kg per hari, wol 30 kg per hari, dan tenaga kerja 40 jam per hari, seperti tabel dibawah ini

Bahan Baku dan Tenaga kerja

Kg bahan baku dan Jam Tenaga Kerja Maksimum PenyediaanKain Suteran (X1) Kain Wol (X2)

Benang Sutera 2 3 60 kgBenang Wol - 2 30 kgTenaga Kerja 2 1 40 Jam

Kedua jenis produk akan memberikan keuntungan sebesar Rp 40 juta untuk kain sutera dan Rp 30 Juta untuk kain wol.Masalahnya: Dengan ketersediaan bahan baku dan tenaga kerja yang ada, Bagaimana

menentukan jumlah unit setiap jenis produk yang akan diproduksi setiap hari agar keuntunganya maksimal (maksimisasi).

Langkah-langkah penyelesaian:1) Variabel Keputusan ; X1 = Kain Sutera

X2 = Kian Wol

2) Fungsi Tujuan : ZMax = 40X1 + 30X2

3) Fungsi Kendala/batasan : 1. 2X1 + 3X2 ≤ 60 (Benang Sutera)1. 2X2 ≤ 30 (Benang Wol)2. 2X1 + X2 ≤ 40 (Tenaga Kerja)

4) Membuat Grafik:a. 2X1 + 3X2 = 60 -> X1 = 0 , X2 = 60/3 = 20 X2 = 0 , X1 = 60/2 = 30

b. 2X2 = 30 -> X2 = 30/2 = 15 c. 2X1 + X2 = 40 -> X1 = 0 , X2 = 40 X2 = 0 , X1 = 40/2 = 20

11

X2

40

(1) 2X1 + 3X2 ≤ 60

20

15 E D C 2

(3) 2X1 + X2 ≤ 40 A B

0 20 30 X1

Daerah Penyelesian

Cara mendapatkan solusioptimal:Titik A : X1 = 0 , X2 = 0, Maka Z = 40 (0) + 30 (0) = 0Titik B : X1 = 20, X2 = 0 , Maka Z = 40 (20) + 30 (0) = 800Titik C : Mencari titik potong garis 1 dan 3; 2X1 + 3X2 = 60

2X1 + X2 = 40 2X2 = 20 -> X2 = 10

Masukkan X2 Kedalam kendala 1:2X1 + 3X2 = 602X1 + 3 (10) = 60 -> 2X1 = 30 -> X1 = 15

Masukan nilai X1 dan X2 ke Fungsi Tujuan (Z):ZMax = 40X1 + 30X2 = 40 (15) + 30 (10) = 600 + 300 = 900 (Optimal).

Titik D : 2X2 = 30 -> X2 = 15, - > 2X1 + 3X2 = 60 ,- > 2X1 + 3(15) = 60 2X1 + 45 = 60, -> 2X1 = 15

ZMax = 40X1 + 30X2 = 40 (7,5) + 30 (15) = 300 + 450 = 750

Kesimpulan:Solusi optimal akan tercapai pada persilangan garis kendala (1) dan (3) yaitu pada titi C. Jadi untuk memperoleh keuntungan maksimal, maka jumlah X1 = 15, dan jumlah X2 = 10, dengan keuntungan sebesar Rp 900 juta.

B. Masalah Minimisasi Permasalahan minimsiasi dapat berupa meminimumkan biaya produksi. Solusi optimal akan dicapai pada saat garis fungsi tujuan menyinggung daerah yang terdekat dengan titik origin (daerah fisible)

Contoh Soal Minimisasi:Sebuah Perusahaan Home Industri memproduksi Jaket, Perusahaan tersebut memproduksi dua jenis Jaket yaitu jaket A dan jaket B, Kedua jenis jaket tersebut berbahan Kulit dan Bahan Sintetis.

12

Jaket A paling sedikit diproduksi 2 unit perhari dan jakt B 1 unit. Ketersediaan bahan kulit minimum perhari 16 unit dan Bahan sintetis 24 unit Tabel berikut menunjukan kebutuhan Minimum per unit akan bahan dan biaya per unit dari produknya:

Jenis Jaket Bahan Kulit Bahan Sintetis Biaya per uniy (Rp,000)Jaket A 4 4 200Jaket B 2 6 160Kebutuhan Minimum 16 24

Bagaimana menentukan kombinasi jenis jaket agar meminimumkan biaya produksi.

Langkah-langkah penyelesaian:1. Tentukan Variabel Keputusan:

X1 = Jaket model AX2 = Jaket model B

2. Fungsi Tujuan:Zmin = 200X1 + 160X2

3. Fungsi Kendala:1) 4X1 + 2X2 ≥ 16 (Bahan kulit)2) 4X1 + 6X2 ≥ 24 (bahan sintetis)3) X1 ≥ 44) X2 ≥ 2

4. Membuat grafik1. 4X1 + 2X2 = 16 X1 = 0 , X2 = 8 X2 = 0 , X1 = 4

2. 4X1 + 6X2 = 24 X1 = 0 , X2 = 4 X2 = 0 , X1 = 6

3. X1 = 24. X2 = 1

Mencari Persilangan garis kendala (1) dan (2)4X1 + 2X2 = 16 4X1 + 6X2 = 24 -4X2 = -8 X2 = 2

Masukkan X2 ke dalam kendala (1)4X1 + 2X2 = 16 4X1 + 2 (2) = 16 4X1 = 12 X1 = 3

Masukan nilai X1 dan X2 ke dalam Fungsi tujuan

Zmin = 200X1 + 160X2 = 200(3) + 160 (2) = 600 + 320 = 920

Solusi optimal diperoleh pada titik B (titik yang terdeket dengan titik origin), yaitu persilangan garis (1) 4X1 + 2X2 ≥ 16 dengan garis (2) 4X1 + 6X2 ≥ 24

13

X2

(1) (3) 8

4 (2) C Daerah Penyelesaian

B (3,2)

1 A (4)

2 4 6 X1

Kesimpulan: Untuk memnimumkan biaya produksi, Maka Jaket A (X1) harus diproduksi 3 Unit perhari dan Jaket B (X2) harus diproduksi 2 unit. Dengan total biaya produksi Rp 920 ribu.

14

BAB II

METODE SIMPLEKS

Karena kesulitan menggambar grafik yang berdimensi banyak, maka penyelesaian masalah LP yang melibatkan lebih dari dua variabel menjadi tidak praktis.Dalam keadaan ini kebutuhan metode solusi yang lebih umum menjadi nyata. Metode umum ini dikenal dengan nama Algoritma Simpleks yang dirancang untuk menyelesaikan masalah LP. Metode ini menyelesaikan masalah LP melalui perhitungan ulang (iteration), dimana langkah perhitungan yang sama diulang berkali-kali sampai solusi optimum tercapai.

Salah satu teknik penentuan solusi optimal yang digunakan dalam pemrograman linier adalah metode simpleks. Penentuan solusi optimal menggunakan metode simpleks didasarkan pada teknik eleminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim satu per satu dengan cara perhitungan iteratif. Sehingga penentuan solusi optimal dengan simpleks dilakukan tahap demi tahap yang disebut dengan iterasi. Iterasi ke-i hanya tergantung dari iterasi sebelumnya.

Ada beberapa istilah yang sangat sering digunakan dalam metode simpleks, diantaranya :

1. Iterasi adalah tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai tabel sebelumnya.

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

3. Variabel basis merupakan variabel yang nilainya bukan nol pada sembarang iterasi. Pada solusi awal, variabel basis merupakan variabel slack (jika fungsi kendala merupakan pertidaksamaan ≤ ) atau variabel buatan (jika fungsi kendala menggunakan pertidaksamaan ≥ atau =). Secara umum, jumlah variabel basis selalu sama dengan jumlah fungsi pembatas (tanpa fungsi non negatif).

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

5. Variabel slack adalah variabel yang ditambahkan ke model matematik kendala untuk mengkonversikan pertidaksamaan ≤ menjadi persamaan (=). Penambahan variabel ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel slack akan berfungsi sebagai variabel basis.

6. Variabel surplus adalah variabel yang dikurangkan dari model matematik kendala untuk mengkonversikan pertidaksamaan ≥ menjadi persamaan (=). Penambahan ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel surplus tidak dapat berfungsi sebagai variabel basis.

7. Variabel buatan adalah variabel yang ditambahkan ke model matematik kendala dengan bentuk ≥ atau = untuk difungsikan sebagai variabel basis awal. Penambahan variabel ini terjadi pada tahap inisialisasi. Variabel ini harus bernilai 0 pada solusi optimal, karena kenyataannya variabel ini tidak ada. Variabel hanya ada di atas kertas.

8. Kolom pivot (kolom kerja) adalah kolom yang memuat variabel masuk. Koefisien pada kolom ini akn menjadi pembagi nilai kanan untuk menentukan baris pivot (baris kerja).

9. Baris pivot (baris kerja) adalah salah satu baris dari antara variabel basis yang memuat variabel keluar.

10. Elemen pivot (elemen kerja) adalah elemen yang terletak pada perpotongan kolom dan baris pivot. Elemen pivot akan menjadi dasar perhitungan untuk tabel simpleks berikutnya.

15

11. Variabel masuk adalah variabel yang terpilih untuk menjadi variabel basis pada iterasi berikutnya. Variabel masuk dipilih satu dari antara variabel non basis pada setiap iterasi. Variabel ini pada iterasi berikutnya akan bernilai positif.

12. Variabel keluar adalah variabel yang keluar dari variabel basis pada iterasi berikutnya dan digantikan oleh variabel masuk. Variabel keluar dipilih satu dari antara variabel basis pada setiap iiterasi. Variabel ini pada iterasi berikutnya akan bernilai nol.

BENTUK BAKU

Sebelum melakukan perhitungan iteratif untuk menentukan solusi optimal, pertama sekali bentuk umum pemrograman linier dirubah ke dalam bentuk baku terlebih dahulu. Bentuk baku dalam metode simpleks tidak hanya mengubah persamaan kendala ke dalam bentuk sama dengan, tetapi setiap fungsi kendala harus diwakili oleh satu variabel basis awal. Variabel basis awal menunjukkan status sumber daya pada kondisi sebelum ada aktivitas yang dilakukan. Dengan kata lain, variabel keputusan semuanya masih bernilai nol. Dengan demikian, meskipun fungsi kendala pada bentuk umum pemrograman linier sudah dalam bentuk persamaan, fungsi kendala tersebut masih harus tetap berubah.

Ada beberapa hal yang harus diperhatikan dalam membuat bentuk baku, yaitu :

1. Fungsi kendala dengan pertidaksamaan ≤ dalam bentuk umum, dirubah menjadi persamaan (=) dengan menambahkan satu variabel slack.

2. Fungsi kendala dengan pertidaksamaan ≥ dalam bentuk umum, dirubah menjadi persamaan (=) dengan mengurangkan satu variabel surplus.

3. Fungsi kendala dengan persamaan dalam benttuk umum,ditambahkan satu artificial variabel (variabel buatan).

1. MODEL DAN TABEL SIMPLEKSMetode simpleks didasarkan atas gagasan dan langkah-langkah sbb:a. Dimulai dari suatu titik asal yang biasanya disebut solusi awalb. Bergerak dari satu titik asal ketitik lainya yang berdekatan, pergerakan ini akan menghasilkan

fungsi tujuan yang lebih baik (meningkat untuk masalah maksimisasi dan menurun untuk minimisasi). Jika solusi yang lebih baik sudah diperoleh, , prosedur simplek dengan sendirinya akan menghilangkan solusi-solusi lain yang kurang baik.

c. Proses ini diulang-ulang sampai suatu solusi yang lebih baik tak dapat ditemukan, Proses simpleks ini kemudian berhenti dan solusi telah diperoleh.

Contoh 2.1: Penyelesaian Masalah dengan Prosedur Metode Simpleks

Toko Mainan Anak menjual 2 (dua) macam jenis mainan, yaitu mainan A dan mainan B. Kedua produk berbahan baku yang sama, namun dalam jumlah yang berbeda. Bahan baku dan jumlah yang dibutuhkan adalah Sbb:

Jenis Mainan Bahan Baku Plastik (ons/unit) Bahan Perekat (pack/unit)A 5 2B 4 1

Jumlah yang Tersedia 100 30

16

Setiap menjual 1 buah A produk PMA bisa mendapatkan keuntungan sebesar $3. Keuntungan untuk 1 produk B sebesar $2. Berapa banyak produk yang harus dijual Pabrik PMA agar memperoleh keuntungan maksimal (Maksimisasi)?

Diketahui:a. Variabek Keputusan X1 = Produk A

X2 = Produk B

b. Fungsi Tujuan Zmax = 3X1 + 2X2

c. Fungsi Kendala Plastik : 5X1 + 4X2 ≤ 100Perekat : 2X1 + X2 ≤ 30

X1 dan X2 ≥ 0Penyelesaian: A. Fungsi tujuan:

Zmax = 3X1 + 2X2

Menambahkan fungsi kendala dengan Variabel Slack Fungsi Kendala 5X1 + 4X2 ≤ 100 => 5X1 + 4X2 + X3 = 100 (2)

2X1 + X2 ≤ 30 => 2X1 + X2 + X4 = 30 (3)B. Menyusun Persamaan – persamaan kedalam tabel

Untuk metode simpleks fungsi kendala dari masalah tersebut menjadi:Plastik : 5X1 + 4X2 + 1X3 + 0X4 = 100Perekat : 2X1 + X2 + 0X3 + 1X4 = 30

Cj V. Dasar X1 X2 X3 X4 Q R- - 3 2 0 0 - -0 X3 5 4 1 0 100 -0 X4 2 1 0 1 30 -- Zj

- Cj - Zj

Keterangan:Cj =Zj = Cj - Zj =Q =R =

Menentukan Zj : X1 = (0 x 5) + (0 x 2) = 0X = (0 x 4) + (0 x 1) = 0X3 = (0 x 1) + (0 x 0) = 0X4 = (0 x 0) + (0 x 1) = 0Q = (0 x 100) + (0 x 30) = 0

Menentukan Cj – Zj : X1 = 3 – 0 = 3X2 = 2 – 0 = 2X3 = 0 – 0 = 0X4 = 0 – 0 = 0

17

Tabel 2 :

Cj Basis X1 X2 X3 X4 Q R- - 3 2 0 0 - -0 X3 5 4 1 0 100 -0 X4 2 1 0 1 30 -- Zj 0 0 0 0 0 -- Cj - Zj 3 2 0 0 - -

Kolom Kunci

Pada fungsi tujuan maksimisasi, jika nilai (Cj - Zj) masih ada yang bernilai positif (+) maka hasilnya belum optimum. Jadi masih ada langkah/prosedur berikutnya. Namun sebelum mengerjakan prosedur berikutnya, harus ditentukan dulu “ Angka Kunci “ .

Angka Kunci adalah angka yang terletak pada pertemuan baris dan kolom. Kolom Kunci adalah dengan memilih kolom dengan nilai (Cj - Zj) paling besar, lalu beri kolom tersebut penanda (diarsir).

Selanjutnya hitunglah nilai R (Rasio) dengan membagi nilai Q (Jumlah) dengan nilai di kolom Kunci (X1), Yaitu : Nilai R pada baris X3 = 100/ 5 = 20

Nilai R pada baris X4 = 30/ 2 = 15

Tabel 3:Cj Basis X1 X2 X3 X4 Q R- - 3 2 0 0 - -0 X3 5 4 1 0 100 200 X4 2 1 0 1 30 15- Zj 0 0 0 0 0 -- Cj - Zj 3 2 0 0 - -

C. Menentukan baris X4 BARU- Pilihlah baris dengan niali R terkecil dan positif, yaitu baris X4. . - Tentukan Angka Kunci, yang merupakan perpotongan antara kolon A dan baris X4 Yaitu

angka 2. - Tentukan baris X4 baru dengan membagi angka dibaris X4 dengan Angka Kunci (2).

Baris Lama : 2/2 ½ 0/2 1/2 30/2Baris baru : 1 0,5 0 0,5 15

- Beri tanda X4 yang baru menjadi X4’- Menentukan angka dalam baris X3 yang baru : X1 = 5 – (5 x 1) = 0

X2 = 4 – (5 x 0,5) = 1,5X3 = 1 - (5 x 0 ) = 1X4 = 0 - (5 x 0,5) = -2,5Q = 100 – (5 x 15) = 25

18

- Beri tanda X3 yang baru menjadi X3’- Menentukan Zj baru : X1 = (0 x 0) + (3 x 1) = 3

X2 = (0 x 1,5) + (3 x 0,5) = 1,5 X3 = (0 x 1) + (3 x 0) = 0 X4 = (0 x -2,5) + (3 x 0,5) = 1,5 Q = (0 x 25 ) + (3 x 15) = 45

- Menentukan Cj - Zj = X1 = 3 – 3 = 0 X2 = 2 – 1,5 = 0,5 X3 = 0 – 0 = 0 X4 = 0 – 1,5 = -1,5

Tabel 4:

Cj Basis X1 X2 X3 X4 Q R- - 3 2 0 0 - -0 X3’ 0 1,5 1 -2,5 25 -3 X4’ 1 0,5 0 0,5 15 -- Zj 3 1,5 0 1,5 45 -- Cj - Zj 0 0,5 0 -1,5 - -

Pada tabel diatas nilai (Cj - Zj) masih ada yang positif maka tujuan maksimisasi hasilnya belum optimum. Jadi masih ada prosedur berikutnya.

D. Langkah 3:- Tentukan Angka Paksi dengan memilih kolom yang memiliki nilai (C j - Zj) yang paling besar

dan positif, yaitu kolom X2 dengan Angka Paksi sebesar 0,5, dan beri arsir kolom X2 .- Hitung nilai R dengan membagi antara Q dengan nilai kolom X2, Yaitu :

Nilai R pada baris X3’ = 25/1,5 = 50/3Nilai R pada baris X4’ = 15/0,5 = 30

- Pilih baris dengan nilai R terkecil dan positif, yaitu baris X3’ (50/30)

Tabel 5:

Cj Basis X1 X2 X3 X3 Q R- - 3 2 0 0 - -0 X3’ 0 1,5 1 -2,5 25 50/33 X4’ 1 0,5 0 0,5 15 30- Zj 3 1,5 0 1,5 45 -- Cj - Zj 0 0,5 0 -1,5 - -

- Tentukan Angka Kunci yang merupakan perpotongan kolom X2 dengan X3’, Yaitu angka 1,5.- Tentukan Baris X3’ baru dengan membagi angka dai baris X3’ dengan Angka Kunci (1,5).

Baris lama : 0/1,5 1,5/1,5 1/1,5 -2,5/1,5 25/1,5Baris Baru : 0 1 0,6667 -1,6667 16,6667

- Beri tanda X3’ mnejadi X3” X3”

19

- Menentukan angka dalam kolom X4” (baru):X1 = 1 – (0,5 X 0) = 1X2 = 0,5 – (O,5 X 1) = 0X3 = 0 – (0,5 X 0,6667) = -0,3333 X4”X4 = 0,5 – (0,5 X -1,6667) = 1,3333Q = 15 – (0,5 X 16,6667) = 6,6667

Tabel 6 :

Cj Basis X1 X2 X3 X4 Q R- - 3 2 0 0 - -2 X3” 0 1 0,6667 -1,6667 16,6667 -3 X4” 1 0 -0,3333 1,3333 6,6667 -- Zj 3 2 0,3333 0,6667 53,3333 -- Cj - Zj 0 0 - 0,3333 -0,6667 - -

- Menentukan Zj :X1 = (2 X 0) + (3 X 1) = 3X2 = (2 X 1) + (3 X 0) = 2X3 = (2 X 0,6667) + (3 X ( -0,3333)) = 0,3333X4 = (2 X (-1,6667)) + (3 X 1,3333) = 0,6667Q = (2 X 16,6667) + (3 X 6,6667) = 53,3333

- Menentukan Cj - Zj :X1 = 3 -3 = 0X2 = 2 – 2 = 0X3 = 0 – 0,3333 = - 0,3333X4 = 0 – 0,6667 = - 0, 6667

Hasil Cj - Zj sudah tidak ada yang positif maka solusi sudah optimum (angka nol dianggap negatif). Jadi solusinya adalah agar perusahaan mampu menjual produk A sebanyak 6,6667 buah dan Produk B sebanyak 16,6667 buah untuk mendapatkan keuntungan maksimun sebesar $ 53,3333.

20

Contoh 2.2 :Bu Ani membuat usaha kue, Setelah membuat perencanaan Bu Ani akan memproduksi tiga jenis kue Tar yaitu keu A, Kue B, Kue C. Bu Ani turun langsung dalam pembuatan kue dan dibantu oleh 1 (satu) orang tenaga kerja. Jam kerja yang dibutuhkan dalam sehari ditargetkan selama 9 jam. Untuk membuat kue tar dibutuhkan bahan sbb:

Kue A : 300 gram tepung terigu dan 200 gram gula untuk 1 kue AKue B : 500 gram tepung terigu 400 gram gula untuk 1 kue BKue C : 400 gram tepung terigu 500 gram gula untuk 1 kue C

Jam kerja yang dibutuhkan adalah 60 untuk kue A dan 120 menit untuk kue B dan C. Dalam satu hari Bu Ani hanya akan menggunakan 6 kg tepung terigu dan 4 kg gula untuk memproduksi kue-kuenya. Harga jual yang direncanakan untuk masing masing kuadalah: Kue A = Rp 15.000, Kue B = Rp 30.000 dan Kue C = Rp 20.000 dari penjualan tersebut Bu Ani menargetkan laba 40% dari harga jual.

Bagaimana sebaiknya Bu Ani mengatur jenis kue yang harus diproduksi agar setiap hari mendapatkan keuntungan yang maksimum? Dan berapa keuntungan maksimum yang bisa diperoleh dalam 1 hari?

Jenis Kue Sumber daya per unitTepung (gram) Gula (gram) Tenaga kerja (menit)

ABC

300500400

200400500

60120120

Catatan: - Tenaga kerja duan orang yakni Bu Ani dan iarang karyawan jam kerja 9 jam, maka:

2 x 9 jam = 18 jam, 18 jam x 60 menit = 1080 menitDiketahui :

a. Variabel Keputusan : X1 = Kue Tar jenis AX2 = Keu Tar jenis B

X3 = Kue Tar jenis C

b. Fungsi Tujuan : Profit kue tar A = 40% X Rp 15.000 = Rp 6.000Profit kue tar B = 40% X Rp 30.000 = Rp 12.000Profit kue tar C = 40% X Rp 20.000 = Rp 8.000

Z = 6000X1 + 12000X2 + 8000X3 (dalam Rp)

c. Fungsi Kendala :Tepung (gram) -> 300X1 + 500BX2+ 400X3 < 6000Gula (gram) -> 200X1 + 400X2 + 500X3 < 4000Tenaga Kerja (menit) -> 60X1 + 120X2 + 120X3 < 1080

Dalam Metode Simpleks Fungsi Kendala Diubah Menjadi:Tepung (gram) -> 300X1 + 500X2 + 400X3 + X4 = 6000Gula (gram) -> 200X1 + 400X2 + 500X3 + X5 = 4000Tenaga Kerja (menit) -> 60X1 + 120X2 + 120X3 + X6 = 1080

21

Tabel 1.

Cj

-

- 6000 1200 8000 -- X1 X2 X3 X4 X5 X6 Q R

0 X4 300 500 400 1 0 0 60000 X5 200 400 500 0 1 0 40000 X6 60 120 120 0 0 1 1080- Zj

- Cj - Zj

- Nilai R dicari dengan membagi nilai Q dengan nilai pada kolom Kunci - Kolom kunci dari masalah diatas adalah Kolom X2, dan Angka Kunci adalah 120.- Menentukan nilai Zj :

X1 = (0 X 300) + (0 X 200) + (0 X 60) = 0X2 = (0 X 500) + (0 X 400) + (0 X 120) = 0X3 = (0 X 400) + (0 X 500) + (0 X 120) = 0X4=(0 X 1) + (0 X 0) + (0 X 0) = 0X5=(0 X 0) + (0 X 1) + (0 X 0) = 0X6=(0 X 0) + (0 X 0) + (0 X 1) = 0Q =(0 X 6000) + (0 X 4000) + (0 X 1080) = 0

Tabel 2:

Cj

-

- 6000 1200 8000 -- X1 X2 X3 X4 X5 X6 Q R

0 X4 300 500 400 1 0 0 6000 120 X5 200 400 500 0 1 0 4000 100 X6 60 120 120 0 0 1 1080 9- Zj 0 0 0 0 0 0 0 -- Cj - Zj 6000 12000 8000 - - -

- Dari tabel diatas ketahui Angka KUNCI adalah 120, Maka angka pada X6’ adalah:Baris Lama : 60/120 120/120 120/120 0/120 0/120 1/120 1080Baris Baru (X6’) : 1/2 1 1 0 0 1/120 9

- Menentukan angka pada baris X4’ ( baru) :X1 = 300 – (1/2 X 500) = 50X2 = 500 – (1 X 500) = 0X3 = 400 – (1 X 500) = -100X4 = 1 – (0 X 500) = 1X5 = 0 – (0 X 500) = 0X6 = 0 – (1/120 X 500) = -25/6Q = 6000 – (9 X 500) = 1500

- Menentukan angka dalam baris X5’ (baru) :X1 = 200 – (1/2 X 400) = 0X2 = 400 – (1 X 400) = 0X3 = 500 – (1 X 400) = 100X4 = 0 – (0 X 400) = 0X5 = 1 – (0 X 400) = 1X6 = 0 – (1/120 X 400) = -10/3

22

Q = 4000 – (9 X 400) = 400

Tabel 3:

Cj

-

- 6000 12000 8000 -- X1 X2 X3 X4 X5 X6 Q R

0 X4’ 50 0 -100 1 0 -25/6 1500 -0 X5’ 0 0 100 0 1 -10/3 400 -

12000

X6’ 1/2 1 1 0 0 1/120 9 -

- Zj’ 6000 12000 12000 0 0 100 108000- Cj - Zj’ 0 0 -400 0 0 -100

- Menentukan nila Zj’ : X1 = (0 X 50) + (0 X 0) + (12000 X ½) = 6000X2 = (0 X 0) + (0 X 0) + (12000 X 1) = 1200X3 = (0 X 0) + (0 X 0) + (12000 X 1) = 1200X4 = (0 X 0) + (0 X 0) + (0 X 0) = 0X5 = (0 X 0) + (0 X 0) + (0 X 0) = 0X6 = (0 X 0) + (0 X 0) + (12000 X 1/120) = 100B = (0 X 1500) + (0 X 400) + (12000 X 9) = 108000

- Menentukan Cj - Zj’ :X1 = 6000 – 6000 = 0X2 = 12000 – 12000 = 0X3 = 8000 – 12000 = -4000X4 = 0X5 = 0X6 = 0- 100 = -100

- Keputusan Akhir:1. Jika ingin mendapatkan keuntungan yang maksimum, Bu Ani harus memproduksi 9

buah kue tar jenis B dan tidak perlu memproduksi kue tar jenis A dan C.2. Keuntungan nmaksimum yang bisa Bu Ani PEROLEH dengan hanya menjual kue tar

jenis B adalah sebesar Rp 108.000

23

BAB IIIMASALAH PRIMAL DAN DUAL

1. TEORI DUALITASDari sudut pandang teiri maupun praktik, teory duaitas merupakan suatu konsep yang sangat penting dan menarik dalam Program Linier. Istilah dualitas menunjukan bahwa kenyataan pada setiap LP terdiri atas dua bentuk :

- Bentuk pertama atau bentuk asli dinamakan “Primal”, sementara bentukkedua yang berhubungan dinamakan ‘Dual” hingga suatu solusi terhadap LP yang asli juga memberikan solusi pada bentuk dualnya.

- Jadi, jika suatu LP diselesaikan dengan metode simpleks, sesungguhnya diperoleh penyelesaian untuk dua masalah LP.

Contoh:Tabel 3.1 dibawah ini menampilkan masalah penyediaan makanan untuk vegetarian oleh sebuah restoran, dimana jumlah mineral dan vitamin pada dua jenis makanan tiruan, yaitu daging dan sayur tiruan per unit, serta harganya.

Jenis Makanan Kebutuhan Minimum per HariDaging

(satuan per unit)Sayur

(satuan per unit)Mineral 2 4 40Vitamin 3 2 50 Harga per Unit 3 2,5

Masalahnya adalah menentukan biaya pembelian sejumlah daging dan sayuran hingga kebutuhan minimum per hari akan vitamin dan mineral terpenuhi (primal).

- Rumuskan masalah secara matematika misalnya Xj( j = 1,2...) adalah jumlah daging dan sayuran yang dibeli, dan masalahnya menentukan jumlah X1 dan X2 yang tepat

- Sehingga:Minimumkan; Z = 3X1 + 2,5 X2 Dengan Syarat: 2X1 + 4X2 ≥ 40 3X1 + 2X2 ≥ 50 X1 , X2 ≥ 0

Selanjutnya pikirkan masalah yang berbeda (dual), yang berhubugan dengan masalah yang pertama (primal).

- Misalkan ada sebuah toko A menjual vitamin dan mineral. Pemilik restoran mengetahui benar bahwa daging dan meneral yang dijual memIliki nilai karena kandungan vitamin dan mineralnya. Pemilik restoran membeli vitamin dan mineral dari toko A untuk membuat daging dan sayuran tiruan.

- Masalah selanjutnya dari Toko A adalah menetapkan harga jual per unit dari VITAMIN dan MINERAL agar harga daging dan sayur yang dijual restoran tidak melebihi harga pasar.

- Misalkan Toko A menetapkankan menjual harga daging per unit sebesar Y 1 dan harga sayuran Y2, maka masalah dialer dapat dirumuskan secara matematika menjadi:

24

Jenis Makanan Kebutuhan Minimum per HariDaging

(satuan per unit)Sayur

(satuan per unit)Mineral 2 4 40Vitamin 3 2 50 Harga per Unit 3 2,5

Minimumkan: W = 40 Y1 + 50 Y2

2Y1 + 3Y2 ≤ 3 4Y1 + 2Y2 ≤ 2,5

Y1 , Y2 ≥ 0

Bentuk LP yang terakhir ini disebut dengan masalah Dual, dan Y1 , Y2 dinamakan variabel dual.

Biala maslah primal dibandingkan dengan masalah dual dapat di bedakan sebagai berikut:- Koefisien fungsi tujuan dalam masalah primal menjadi konstanta sisi kanan masalah dual,

dan sebaliknya konstan sisi kanan primal menjadi koefisian fungsi tujuan dual.- Tanda pertidaksamaan kendala dibalik.- Tujuan diubah dari minimisasi (maksimisasi) dalam primal diubah menjadi maksimisasi

(minimisasi) dalam dual.- Setiap kolom pada primal berhubungan dengan suatu baris (kendala) dalam dual.

Sehingga banyaknya kendala dual sama banyaknya dengan variabel primal.- Setiap baris kendalapada primal berhubungan dengan suatu kolom dalam dual. Sehingga

ada satu variabel dual untuk setiap kendala primal.- Bentuk dual dari dual dalah primal.

Latihan Primal dan Dual:

PrimalMinimumkan: Z = 2X1 + X2

Fungsi batasan : X1 + 5X2 ≤ 10 X1 + 3X2 ≤ 6 2X1 + 2X2 ≤ 8 X1 , X2 ≥ 0

Ubahlah permasalahan matematika diatas menjadi bentuk Dual

PrimalMaksimumkan: Z = X1 + 3X2 - 2X2

Fungsi batasan: 4X1 + 8X2 + 6X3 = 25 7X1 + 5X2 + 9X3 = 30 X1 , X2 , X3 ≥ 0

Ubahlah permasalahan matematika diatas menjadi bentuk Dual

25

BAB IV

MODEL TRANSPORTASI

Pada umumnya, masalah transportasi berhubungan dengan distribusi suatu produk tunggal dari beberapa sumber, dengan penawaran terbatas, menuju beberapa tujuan, dengan permintaan tertent, dan pada biaya transportasi minimum. Kalu hanya satu barang, suatu ntempat tujuan bisa terpenuhi permintaanya dari satu atau lebih sumber.

Asumsi dasar dari model transportasi adalah bahwa biaya transport pada suatu rute tertentu akan proporsional dengan banyaknya unit yang dikirimkan. Definisi unit yang dikirimkan akan tergantung pada jenis produk yang diangkut dan yang penting “ satuan penawaran dan permintaan produk harus konsisten”.

Sebuah model transportasi akan berupa suatu jaringan yang dapat digambarkan seperti contoh berikut. Misalnya suatu produk yang dihasilkan oleh tiga pabrik (sumber) harus di distribusikan ke tiga sumber (gudang). Setiap pabrik memiliki kapasitas produksi tertentu, dan setiap gudang memiliki jumlah permintaan tertentu terhadap produk tersebut.

Dengan diketahuinya biaya transportasi per unit dari masing-masing sumber ke gudang tujuan akan muncul permasalahan yang mendasar yaitu, menentukan jumlah barang yang harus dikirim dari masing-masing pabrik ke masing- masing gudang dengan meminimumkan biaya transportasi.

Kendala dalam masalah ini adalah bahwa permintaan pada setiap gudang harus dipenuhi tanpa melebihi kapasitas produksi pada tiap pabrik, Maslah in I diilustrasikan dalam suatu model jaringan transportasi produk ppupukgambar 3.1 dibawah ini:

Gambar 4.1 :

Sumber (Pabrik) Tujuan (Gudang)

Cirebon 1. Semarang

Bandung 2. Jakarta

Cilacap 3. Purwokerto

Pabrik Pasar (Gudang) Penawaran

26

(sumber) (unit)Semarang Jakarta PurwokertoCirebonBandungCilacap

8153

5109

61210

1208080

Permintaan 150 70 60 280Masalah transportasi ini dapat diilustrasikan sebagai suatu model jaringan seperti gambar berikut 4.2

Sumber (Pabrik) Volume yang diangkut Tujuan (Gudang)Supply Demand S1 = 120 D1 = 150

S2 = 80 D2 = 70

S3 = 80 D 3 = 60

Bisa dirumuskan sbb:

- Misalnya Xij : Banyaknya unit barang yang dikirim ke pabrik, ) dimana i = 1,2,3 ke pasar j dimana j = 1,2,3, maka:Minimumkan Z = 8X11 + 5X12 + 6X13 + 15X21 + 10X22 + 12X23 + 3X31 + 9X32 + 10X33

Dengan syarat : X11 + X12 + X13 = 120 (supply pabrik 1) X21 + X22 + X23 = 80 (supply pabrik 2)

X31 + X32 + X33 = 80 (supply pabrik 3) X11 + X12 + X13 = 150 (demand pabrik 1)

X21 + X22 + X23 = 70 (demand pabrik 2) X31 + X32 + X33 = 60 (demand pabrik 3)

Dan Semua X ij ≥ 0Kendala model menunjukan jumlah yang bisa ditawarkan oleh masing-masing sumber dan jumlah yang diminta masing-masing pasar. Asumsi persamaan diatas bahwa semua permintaan akan dipenuhi. Fungsi tujuan adalah biaya total dalambangkan dengan C ij

sebagai biaya transport dari pabrik i ke gudang j, sehingga rumus umum biaya transportasi termurah berupa m = daerah asal dan n = daerah tujuan:

m nMinimumkan Biaya Transport Total = ∑ ∑ Cij Xij

I = 1 I = 1 m

Dengan Syarat = ∑ Xij = Si (penawaran i = 1,2,3,...m) I = 1

n

27

Dengan Syarat = ∑ Xij = Dj (peermintaan j = 1,2,3,..n) m = 1

Semua X > 0

m m m n Kondisi keseimbangan : ∑ S1 = ∑ Xij = ∑ Xij = ∑ Dij

i =1 i = 1 i = 1 i = 1

Jika diperhatikan, semua koefisien matriks kendala pada model ini adalah sama dengan 1. Sifat-sifat model ini mengakibatkan penggunaan metode solusi khusus (Tabel Transportasi) perhitunganya lebih efisien dibanding dengan metode simpleks.

Metode Tabel Transportasi:

1. Metode NWC2. Metode Least Cost3. Metode VAM

Contoh 4.1

Penyelesaian masalah transportasi dengan model Tabel Transportasi.

Soal:

PT. MAJU memiliki 4 pabrik yaitu; Pabrik A, B,C Dan D yang memproduksi cendramata unik. Masing masing pabrik memiliki kapasitas Sbb: Pabrik A = 3.000 unit, Pabrik B = 2.000 Unit, Pabrik C = 2.500 Unit, dan Pabrik D = 1.500 Unit.

PT MAJU menyalurkan produknya ke 4 distributor di 4 wilyahberbeda, yaitu : Bekasi, Bogor, Bandung, dan Karawang.Total permintaan keempat distributor tersebut adalah 9.000 unit dengan rincian; Bekasi = 3.000 unit , Bogor = 1.500 unit, Bandung = 2.500, dan Karawang = 2.000. Data lengkapnya adalah sbb:

Tabel berikut adalah biaya transportasi (dalam Rp) perunit yang dikeluarkan PT MAJU.

Pabrik TujuanBekasi Bogor Bandung Karawang

A 5.000 4.000 8.000 6.000B 2.500 2.000 4.000 5.000C 1.500 1.000 2.000 4.000D 7.000 6.000 5.000 8.000

Pabrik Tujuan Supply(unit)Bekasi Bogor Bandung Karawang

A ? ? ? ? 3000B ? ? ? ? 2000C ? ? ? ? 2500D ? ? ? ? 1500

Demand (unit) 3000 1.500 2.500 2.000

28

Jika perusahaan ingin meminimalkan biaya transportasi, maka tentukanlah alokasi jumlah unit yang tepat harus dikirim dari masing-masing pabrik ke kemasing-masing tujuan dengan menggunakan metode NWC, Least Cost, dan Metode VAM.

1. Penyelesaian dengan Metode NWC:

PT. MAJU memiliki 4 pabrik yaitu; Pabrik A, B,C Dan D yang memproduksi cendramata unik. Masing masing pabrik memiliki kapasitas Sbb: Pabrik A = 3.000 unit, Pabrik B = 2.000 Unit, Pabrik C = 2.500 Unit, dan Pabrik D = 1.500 Unit.PT MAJU menyalurkan produknya ke 4 distributor di 4 wilyahberbeda, yaitu : Bekasi, Bogor, Bandung, dan Karawang.Total permintaan keempat distributor tersebut adalah 9.000 unit dengan rincian; Bekasi = 3.000 unit , Bogor = 1.500 unit, Bandung = 2.500, dan Karawang = 2.000. Data lengkapnya adalah sbb:

Tabel berikut adalah biaya transportasi (dalam Rp) perunit yang dikeluarkan PT MAJU.

Pabrik TujuanBekasi Bogor Bandung Karawang

A 5.000 4.000 8.000 6.000B 2.500 2.000 4.000 5.000C 1.500 1.000 2.000 4.000D 7.000 6.000 5.000 8.000

Pabrik Tujuan Supply(unit)Bekasi Bogor Bandung Karawang

A ? ? ? ? 3000B ? ? ? ? 2000C ? ? ? ? 2500D ? ? ? ? 1500

Demand (unit) 3000 1.500 2.500 2.000

Masalahnya : Tentukanlah alokasi jumlah unit yang tepat harus dikirim dari masing-masing pabrik ke kemasing-masing tujuan dengan menggunakan metode NWC.

Prosedur penyelesaian dengan Metode NWC

- Isi (alokasikan) mulai dari kotak yang berada dipojok kiri sesuai dengan permintaan dan penawaran yang tersedia. Contoh; Bekasi memerlukan 3.000 unit dan suplai yang tersedia dipabrik A 3.000 unit. Maka pabrik A bisa langsung memenuhi seluruh kebutuhan Bekasi.

- Alokasikan sebanyaknya ke sel fisibel berikutnya yang berdekatan, yaitu kotak yang berada disebelah kanan kotak A-> Bogor. Namun karena Pabrik A sudah tidak bisa lagi mensuplai lagi. Langsung aja pindahkan perhatian ke kotak dibawah A -> Bekasi ke kotak yang berada dibawahnya yang dimulai dari kotak palinh kiri yaitu Kotak B -> Bekasi. Bekasi tidak membutuhkan suplay dari pabrik B maka kita langsung saja pindah kekotak sebelah kananya yaitu B -> Bogor dst prosedur akan diulang-ulang.

29

Pabrik Tujuan Supply(unit)Bekasi Bogor Bandung Karawang

A (5.000)3.000

(4.000) (8.000) (6.000) 3.000

B (2.500) (2.000)1.500

(4.000)500

(5.000) 2.000

C (1.500) (1.000) (2.000)2000

(4.000)500

2.500

D (7.000) (6.000) (5.000) (8.000)1.500

1.500

Demand (unit) 3.000 1.500 2.500 2.000 9.000

Hasil Perhitungan dengan metode NWC:

Pabrik Tujuan Unit Biaya (Rp) Total Biaya (Rp)A Bekasi 3.000 5.000 15.000.000B Bogor 1.500 2.000 3.000.000B Bandung 500 4.000 2.000.000C Bandung 2.000 2.000 4.000.000C Kerawang 500 4.000 2.000.000D Kerawang 1.500 8.000 12.000.000

Total 38.000.000

2. Penyelesaian Dengan Metode Least Cost (Minimum Cost)Prosedur dengan metode Least Cost:

- Alokasikan sebanyak mungkin ke sel fisibel dengan biaya tarnsportasi paling minimum, dan sesuaikan dengan kebutuhan permintaan dan suplai. Contoh; C – Bogor merupakan sel fisibel dengan biaya transportasi paling minimum sebesar Rp 1.000.

- Ulangi prosedur seperti diatas sampai kebutuhan permintaan dan suplai terpenuhi.

Pabrik Tujuan Supply(unit)Bekasi Bogor Bandung Karawang

A (5.000) (4.000) (8.000)1.000

(6.000)2.000

3.000

30

B (2.500)2.000

(2.000) (4.000) (5.000) 2.000

C (1.500)1.000

(1.000)1.500

(2.000) (4.000) 2.500

D (7.000) (6.000) (5.000)1.500

(8.000) 1.500

Demand (unit) 3.000 1.500 2.500 2.000 9.000

Hasil Perhitungan dengan metode Least Cost:

Pabrik Tujuan Unit Biaya (Rp) Total Biaya (Rp)A Bandung 1.000 8.000 8.000.000A Kerawang 2.000 6.000 12.000.000B Bekasi 2.000 2.500 5.000.000C Bekasi 1.000 1.500 1.500.000C Bogor 1.500 1.000 1.500.000D Bandung 1.500 5.000 7.500.000

Total 35.500.000

3. Perhitungan dengan Metode VAMProsedur Penyelesaian dengan Metode VAM:

- Tentukan Slack (S) dengan cara mengurangkan biaya terkebil kedua dengan biaya yang paling kecil pada semua baris dan kolom.

- Setelah S terhitung, selanjutnya pilihlah baris atau kolom dengan nilai S terbesar.- Alokasikan semaksimal mungkin ke sel dengan biaya terkecil pada baris/kolom yang di

pilih tadi.Catatan:

- Apabila ada baris atau kolom yang memiliki S dalam jumlah yang sama dan S tersebut termasuk S dengan nilai yang terbesar, maka pilihlah diantara baris dan kolom tersebut, manakah yang memiliki nilai niaya terkecil.

- Jika ada dua nilai terkecil yang sama, alokasikan ke kolom yang permintaanya lebih besar terlebih dahulu, dengan syarat bahwa permintaan tersebut di imbangi oleh suplai.

- Ulangi prosedur tersebut sampai semua permintaan dan suplai teralokasikan.

Tahap 1.

Pabrik Tujuan Supply(unit)Bekasi Bogor Bandung Karawang

A (5.000) (4.000) (8.000) (6.000) 3.000S = 1.000

B (2.500) (2.000) (4.000) (5.000) 2.000

31

S = 500C (1.500) (1.000) (2.000) (4.000) 2.500

S = 500D (7.000) (6.000) (5.000) (8.000) 1.500

S = 1.000

Demand (unit) 3.000S = 1.000

1.500S = 1.000

2.500S = 2.000

2.000S = 1.000

9.000

Tahap 2.

Pabrik Tujuan Supply(unit)

Bekasi Bogor KarawangA (5.000) (4.000) (6.000) 3.000

S = 1.000B (2.500)

2.000(2.000) (5.000) 2.000

S = 500D (7.000) (6.000) (8.000) 1.500

S = 1.000

Demand (unit) 3.000S = 1.000

1.500S = 1.000

2.000S = 1.000

6.500

Tahap 3.

Pabrik Tujuan Supply(unit)

Bekasi Bogor KarawangA (5.000) (4.000)

1.500(6.000) 3.000

S = 1.000D (7.000) (6.000) (8.000) 1.500

S = 1.000

Demand (unit) 3.000S = 1.000

1.500S = 1.000

2.000S = 1.000

4.500

Tahap 4.

Pabrik Tujuan Supply(unit)

Bekasi KarawangA (5.000)

1000(6.000) 1.500

S = 1.000

32

D (7.000) (8.000) 1.500S = 1.000

Demand (unit) 3.000S = 1.000

2.000S = 1.000

3000

Tahap 5.

Pabrik Tujuan Supply(unit)

KarawangA (6.000)

500500

S = 1.000D (8.000)

15001.500

S = 1.000

Demand (unit) 2.000S = 1.000

2000

Hasil Perhitungan dengan metode VAM:

Pabrik Tujuan Supply(unit)Bekasi Bogor Bandung Karawang

A (5.000)1000

(4.000)1500

(8.000) (6.000)500

3.000

B (2.500)2000

(2.000) (4.000) (5.000) 2.000

C (1.500) (1.000) (2.000)2500

(4.000) 2.500

D (7.000) (6.000) (5.000) (8.000)1500

1.500

Demand (unit) 3.000 1.500 2.500 2.000 9.000

Hasil Perhitungan dengan metode VAM:

Pabrik Tujuan Unit Biaya (Rp) Total Biaya (Rp)A Bekasi 1.000 5.000 5.000.000A Bogor 1.500 2.000 6.000.000A Karawang 500 6000 3.000.000B Bekasi 2.000 2.500 5.000.000C Bandung 2.500 2.000 5.000.000D Kerawang 1.500 8.000 12.000.000

Total 36.000.000

4. METODE MODIDengan metode MODI akan dilakukan pengujian apakah masih ada perhitungan biaya lain yang lebih rendah dibanding dengan metode Least Cost (Minimum Cost) dan ternyata masih ada biaya yang lebih rendah. Untuk itu perhitungan dengan metode Modi dalam rangka menperoleh biaya terendah dapat dilihat sbb:

- Misalkan tabel awal yang digunakan adalah tabel Least Cost

33

- Buat variabel Ri dan Kj untuk masing-masing baris dan kolom- Hitunglah sel yang berisi nilai tiap tabel dan tiap kolom dengan rumus

Ri + Kj = C Dimana Ri = Baris Kj = Kolom

C = Biaya

Pabrik Tujuan Supply(unit)Bekasi Bogor Bandung Karawang

A (5.000)0

(4.000) (8.000)1.000

(6.000)2.000

3.000

B (2.500)2.000

(2.000) (4.000) (5.000) 2.000

C (1.500)1.000

(1.000)1.500

(2.000) (4.000) 2.500

D (7.000) (6.000) (5.000)1.500

(8.000) 1.500

Demand (unit) 3.000 1.500 2.500 2.000 9.000Jumlah kotak yang terpakai adalah (6) < 4 + 4 - 1 (7), merupakan penjumlahan dari “Jumlah kolom + jumlah baris – 1” , maka kasus diatas dinamakan degenerasi dan perlu dibentuk artificially occuppied cell, dipilih C11:C11 = R1 + K1 - > 5000 = 0 + K1 -> K1= 5000C13 = R1 + K3 –> 8000 = 0 + K3 -> K3 = 8000C14 = R1 + K4 -> 6000 = 0 + K4 -> K4 = 6000C21 = R2 + K1 –> 2500 = R2 + 5000 -> R2 = -2500C31 = R3 + K1 -> 1500 = R3 + 5000 -> R3 = -3500C32 = R3 + K2 -> 1000 = -3500 + K2 -> K2 = 4500C43 = R4 + K3 -> 5000 = R4 + 8000 -> R4 = -3000

IMPROVEMENT INDEKSKotak Cij - Ri - Kj12 4000 - 0 - 4500 = -50022 2000 - (-2500) - 4500 = 023 4000 - (-2500) - 8000 = -150024 5000 - (-2500) - 6000 = 150033 2000 - (-3500) - 8000 = -250034 4000 - (-3500) - 6000 = 150041 7000 - (-3000) - 5000 = 500042 6000 - (-3000) - 4500 = 4500

Pabrik TujuanBekasi Bogor Bandung

A + 01000

-10000

B 2000

C -10000

1.500 +1.000

Kotak yang bertanda (+) akan ditambah 1.000 dan yang bertanda (-) akan dikurangi 1.000 unit.

34

Pabrik Tujuan Supply(unit)Bekasi Bogor Bandung Karawang

A (5.000)1000

(4.000) (8.000) (6.000)2.000

3.000

B (2.500)2.000

(2.000) (4.000) (5.000) 2.000

C (1.500) (1.000)1.500

(2.000)1000

(4.000) 2.500

D (7.000) (6.000) (5.000)1.500

(8.000) 1.500

Demand (unit) 3.000 1.500 2.500 2.000 9.000

Jumlah kotak yang terpakai (6) < 4 + 4 – 1 (7) maka kasus diatas kembali mengalami degenerasi:

C11 = R1 + K1 - > 5000 = 0 + K1 -> K1= 5000C12 = R1 + K2 –> 4000 = 0 + K2 -> K3 = 4000C14 = R1 + K4 -> 6000 = 0 + K4 -> K4 = 6000C21 = R2 + K1 –> 2500 = R2 + 5000 -> R2 = -2500C32 = R3 + K2-> 1500 = R3 + 5000 -> R3 = -3500C32 = R3 + K3 -> 1000 = -3000 + K3 -> K3 = 5000C43 = R4 + K3 -> 5000 = R4 + 5000 -> R4 = 0

IMPROVEMENT INDEKSKotak Cij - Ri - Kj13 8000 - 0 - 5000 = 300022 2000 - (-2500) - 4000 = 023 4000 - (-2500) - 5000 = 150024 5000 - (-2500) - 6000 = 150031 1500 - (-3500) - 5000 = -50034 4000 - (-3000) - 6000 = 100041 7000 - 0 - 5000 = 200042 6000 - 0 - 4000 = 200044 8000 - 0 - 6000 = 2000

Pabrik TujuanBekasi Bogor

A - 10000

+ 01000

B 2000

C +1000

-1.500500

Kotak yang bertanda (+) akan ditambah 1.000 dan yang bertanda (-) akan dikurangi 1.000 unit.

Pabrik Tujuan Supply(unit)Bekasi Bogor Bandung Karawang

35

A (5.000) (4.000)1000

(8.000) (6.000)2.000

3.000

B (2.500)2.000

(2.000) (4.000) (5.000) 2.000

C (1.500)1000

(1.000)500

(2.000)1000

(4.000) 2.500

D (7.000) (6.000) (5.000)1.500

(8.000) 1.500

Demand (unit) 3.000 1.500 2.500 2.000 9.000

C12 = R1 + K2 - > 4000 = 0 + K2 -> K2 = 4000C14 = R1 + K4 –> 6000 = 0 + K4 -> K4 = 6000C21 = R2 + K1 -> 2500 = R2 + 4500 -> R2 = 2000C31 = R3 + K1 –> 1500 = -3000 + K1 -> K1 = 4500C32 = R3 + K2 -> 1000 = R3 + 4000 -> R3 = -3000C33 = R3 + K3 -> 2000 = -3000 + K3 -> K3 = 5000C43 = R4 + K3 -> 5000 = R4 + 5000 -> R4 = 0

IMPROVEMENT INDEKSKotak Cij - Ri - Kj11 5000 - 0 - 4500 = 50013 8000 - 0 - 5000 = 300022 2000 - (-2000) - 4000 = 023 4000 - (-2000) - 5000 = 100024 5000 - (-2000) - 6000 = 100034 4000 - (-3000) - 6000 = 100041 7000 - 0 - 4500 = 250042 6000 - 0 - 4000 = 200044 8000 - 0 - 6000 = 2000

Pabrik TujuanBekasi Bogor

A - 20001500

+ 500

C + 10001500

-5000

Kotak yang bertanda (+) akan ditambah 500 dan yang bertanda (-) akan dikurangi 500 unit.Pabrik Tujuan Supply

(unit)Bekasi Bogor Bandung KarawangA (5.000) (4.000)

1000(8.000) (6.000)

2.0003.000

B (2.500)1500

(2.000)500

(4.000) (5.000) 2.000

C (1.500)1500

(1.000) (2.000)1000

(4.000) 2.500

D (7.000) (6.000) (5.000)1.500

(8.000) 1.500

Demand (unit) 3.000 1.500 2.500 2.000 9.000

36

Oleh karena nilai improvement indeks seluruhnya sudah tidak ada yang negatif, maka solusi sudah optimal, dengan rincian biaya sbb:

Pabrik Tujuan Unit Biaya (Rp) Total Biaya (Rp)A Bogor 1.000 4.000 4.000.000A Kerawang 2.000 6.000 12.000.000B Bekasi 1.500 2.500 3.750.000B Bogor 500 2.000 1.000.000C Bekasi 1.500 1.500 2.250.000C Bandung 1.000 2.000 2.000.000D Bandung 1.500 5.000 7.500.000

Total 32.500.000

BAB VMASALAH PENUGASAN (ASSIGMENT PROBLEM)

1. PENUGASANMasalah penugasan menyangkut penempatan para pekerja pada bidang yang tersedia agar biaya yang ditanggung dapat diminimumkan. Metode yang digunakan untuk perhitungan penugasan adalah metode Hungarian. Jika pekerja dianggap sumber, dan pekerjaan dianggap tujuan, maka model ini mirip dengan model transportasi. Bedanya pada penugasan jumlah pasokan pada setiap “ sumber” dan jumlah permintaan pada setiap “tujuan” adalah 1 (satu). Ini menjelaskan bahwa setiap pekerja hanya menangini satu pekerjaan, dan sebaliknya setiap pekerjaan hanya ditangini oleh satu pekerja “ Jumlah n sumber mencaku n tugas, sehingga ada n! (n faktoril)”.

Masalah penugasan dapat dijelaskan dengan menggunakan matriks segi empat, dimana baris-barisnya menunjukkan sumber dan kolom-kolomnya menunjukkan tugas-tugas.

A. Masalah Minimisasi

Contoh 5.1: Perusahaan Kecil memiliki 4 pekerjaan yang harus diselesaikan oleh 4 karyawan. Setiap karyawan memiliki penugasan yang berbeda dengan biaya yang berbeda, sehingga biaya penyelesaian setiap unit pekerjaan oleh masing maing karyawan juga beda. Tabel biaya Sbb:

Tabel 1:Pekerjaan

KaryawanI II III IV

Rony Rp 150 Rp 200 Rp 180 Rp 220Hadi Rp 140 Rp 160 Rp 210 Rp 170

37

Herman Rp 250 Rp 200 Rp 230 Rp 200Doni Rp 170 Rp 180 Rp 180 Rp 160

Masalahnya: Bagaimana menugaskan keempat karyawan untuk menyelesaikan keempat pekerjaan agar total biaya minimum.

Prosedur yang harus dilalui adalah:1) Menyusun tabel biaya seperti tabel diatas2) Melakukan pengurangan baris dengan cara:

- Memilih biaya terkecil setiap baris- Kurangkan semua biaya dengan biaya terkecil setiap baris, sehingga

menghasilkan Reduced Cost Matrix (Matrik biaya yang telah dikurangi) sbb:

Tabel 2:Pekerjaan

KaryawanI II III IV

Rony 0 50 30 70Hadi 0 20 70 30Herman 50 0 30 0Doni 10 20 20 0

3) Memilih biaya terkecil- Berdasarkan tabel 2, Pilihlah biaya terkecil tiap kolom untuk mengurangi seluruh

biaya dalam kolom kolom tsb. Pada tabel diatas dilakukan pada kolom 3 karena kolom lainya sudah ada elemen bernilai nol. Tetapi bila pada langkah tersebut sudah menghasilkan paling sedikit satu nilai nol pada setiap kolom, maka langkah ketiga dapat dihilangkan.

Tabel 3:Pekerjaan

KaryawanI II III IV

Rony 0 50 (30-20) = 10 70Hadi 0 20 (70-20) = 50 30Herman 50 0 (30-20) = 10 0Doni 10 20 (20-20) = 0 0

4) Membentuk penugasan optimum- Menarik garis vertikal dan horizontal untuk meliputi seluruh elemen bernilai nol.

Jika jumlah garis sama dengan jumlah baris/kolom, maka penugasan sudah optimal. Jika tidak maka penugasan harus direvisi.

Tabel 4:

38

PekerjaanKaryawan

I II III IV

Rony 0 50 10 70

Hadi 0 20 50 30Herman 50 0 10 0Doni 10 20 (0 0

5) Melakukan Revisi Tabel:- Pilih angka terkecil yang tidak terliput oleh garis (angka 10)- Kurangi angka yang tidak terliput oleh garis dengan angka terkecil (angka 10)- Tambahkan angka yang terdapat pada persilangan garis (angka 50, 10) dengan

angka terkecil (10).- Kembali ke langkah 4.

Tabel 5:Pekerjaan

KaryawanI II III IV

Rony 0 40 0 60

Hadi 0 10 40 20Herman 60 0 10 0Doni 20 20 0 0

Tabel Solusi Penugasan:

B. Masalah MaksimisasiAlokasi karyawan juga bisa bertujuan untuk memaksimumkan keuntungan, yaitu bila yang dijadikan ukuran untuk menentukan efisiensi itu berupa besarnya keuntungan atau manfaat yang bisa diambil.

Contoh:

39

Penugasan BiayaRony -> III Rp 180Hadi -> I Rp 140Herman -> II Rp 200Doni -> IV Rp 160

Rp 680

Sebuah perusahaan memiliki 4 orang karyawan yang memiliki 4 tugas yang berbeda, dimana setiap karyawan harus memeberikan keuntungan sesuai dengan jenis pekerjaanya.

Tabel 1: Matrik Keuntungan pekerjaan karyawan (Rp, 000)Pekerjaan

KaryawanI II III IV

Rony 40 48 40 32Hadi 56 40 36 60Herman 32 36 28 32Doni 52 60 32 64

Langkah-langkah pengerjaanya:1) Membuat Opportunity Lost Matrix

Tabel 2:Pekerjaan

KaryawanI II III IV

Rony 8 0 8 16Hadi 4 20 24 0Herman 4 0 8 4Doni 12 4 32 0

2) Membuat Total Opportunity Lost MatrixDengan cara merubah nilai pada kolom yang belum memiliki nilai angka 0, dengan mengurangi angka pada kolom dengan nilai terkecil, Misalnya kolom I (8-4 = 4, 4 – 4 = 0, 4 – 4 = 0, 12 – 4 = 8)

3) Membuat garis minimum

1

2 3 44) Membuat Matrik Keuntungan

40

PekerjaanKaryawan

I II III IV

Rony 4 0 0 16

Hadi 0 20 16 0Herman 0 0 0 4Doni 8 4 24 0

Penugasan BiayaRony -> II Rp 48Hadi -> I Rp 56Herman -> III Rp 28Doni -> IV Rp 64

Rp 196

C. Masalah Pekerjaan Tidak Sama Dengan Jumlah Karyawan

Bila jumlah pekerjaan lebih besar dari jumlah karyawan, maka harus ditambahkan karyawan semu (Dummy worker). Biaya semu sama dengan nol karena tidak akan ada biaya jika pekerjaan ditugaskan ke karyawan semu. Bila Jumlah karyawan lebih banyak dari pekerjaan ditambahkan pekerjaan semu (dummy jobs).

Contoh 5.2: Jumlah pekerjaan lebih besar dari karyawanSebuah Toko Fashion memperkerjakan 4 karyawan dengan pekerjaan yang berbeda. Perusahaan merencanakan meambah karyawan baru untuk mengisi salah kekurangan tenaga kerja paada pekerjaan yang masih kosong. Berikut adalah data biaya harian dari pegawai pada masing-masing pos (Rp.,000) :

Tabel 1:Pekerjaan

KaryawanA B C D E

Ani 16 18 20 15 14Budi 9 25 17 20 11Candra 14 20 15 42 10Dedi 10 15 18 32 9

Masalah:- Pekerjaan apa yang memmerlukan tambahan karyawan baru- Bagaimana alokasi masing-masing Karyawan beserta biayanya.

Langkah-langkah mencari solusi:1) Buat Matrik seperti diatas2) Tambahkan Dummy Worker pada dengan jenis pekerjaan yang tersedia 3) Kurangi nilai terendah setiap baris

Tabel 2:Pekerjaan

KaryawanA B C D E

41

Ani 16 18 20 15 14

Budi 9 25 17 20 11Candra 14 20 15 21 10Dedi 10 15 18 16 9Dummy 0 0 0 0 0

2

1 3

- Garis meliputi angka O

Tabel 3:Pekerjaan

KaryawanA B C D E

Ani 16 18 20 15 14

Budi 9 25 17 20 11Candra 14 20 15 21 10Dedi 10 15 18 16 9Dummy 0 0 0 0 0

42

2

1 4 5 3

Tabel 4:Pekerjaan

KaryawanA B C D E

Ani DBudi ACandra CDedi EDummy X

Kesimpulan:- Pekerjaan yang belum ada pekerjanya adalah pekerjaan B- Alokasi masing-masing Karyawan beserta biayanya

43

Karyawan Pekerjaan BiayaAni D Rp 15Budi A Rp 9Candra C Rp 15Dedi E Rp 9

Rp 48

Latihan 5.1: Perusahaa Nasional memiliki 3 tenaga ahli yang berdomisili di tiga daerah. Mereka akan dikirim ke tiga daerah lain yang lebih membutuhkan. Berikut ditunjukkan biaya perjalanan dari 3 ahli ke setiap daerah (Rp,0.000).

Domisili Ahli TujuanPontianak Yogya Denpasar

Jakarta 25 31 35Surabaya 15 20 24Makasar 22 19 17

Masalahnya: Bagaimana menugaskan keempat karyawan Ahli untuk menyelesaikan keempat pekerjaan agar total biaya minimum.

Solusi:- Solusi optimum tercapai apabila setiap ahli dapat ditugasi ke setiap daerah dan

setiap daerah hanya diisi satu ahli.- Lahkah pertama adalah menyusun total opprtunity cost table, caranya dengan

mengurangi angka pada setiap baris dengan angka terkecil pada baris itu. (25 – 25, 31-25, 35-25 dst) pengurangan akan menghasilkan:

44

Pengurangan Baris: Pengurangan Kolom:0 6 10 0 4 100 5 9 0 3 95 2 0 5 0 0

- Prosedur Penemuan opportunity cost table dapat dibalik dari pengurangan baris ke pengurangan kolom dan sebaliknya.

- Penugasan dapat ditempatkan pada sel yang nilainya 0, misalnya ahli dijakarta ditugaskan ke pontianak. Pada tabel diatas solusi optimum belum tercapai.

- Tutup semua angka nol dengan menarik garis datar dan tegak dengan jumlah garis paling efisien. Jika jumlah baris itu lebih kecil dari dari jumlah baris dan kolom pada tabel, penugasan optimum belum ditemukan.

- Kurangi semua angka yang tidak tertutup garis dengan angka terkecil yang tidak tertutup (angka 3). Tambahkan angka terkecil yang tidak tertutup pada angka yang menempati posisi silang (angka 5). Biarkan angka lain tetap, maka opportunity cost yang baru adalah:

0 1 70 0 68 0 0

- Tak peduli bagaimana cara menutup angka-angka nol, jumlahh garis minimum yang diperlukan adalah 3, sehingga penugasan adalah:

- Ahli dari jakarta ditugaskan ke Pontianak (25), ahli dari Surabya ditugaskan ke Yogya (20), dan ahli dari Makasar ditugaskan ke Denpasar (17), jumlah total ahli yang ditugaskan: 25 + 20 + 17 = 62 Karyawan Ahli

Domisili Ahli TujuanPontianak Yogya Denpasar

Jakarta 25 31 35Surabaya 15 20 24Makasar 22 19 17

45

DASAR-DASAR OPERASIONAL RESEARCDRS. PANGESTU SUBAGYO MBADRS. MARWAN ASRI MBADR. HANI HANDOKO MBA

OPERASIONAL RESEARCH DRS RESTU MSI

TARGET PENYELESAIAN:

PROGRAM LINIER

SIMPLEKUALITAS

TRANSPORTASI

PENUGASAN

46

47