DEMOSES SIMANJUNTAK: TEKNIK RISET OPERASIONAL

TEKNIK RISET OPERASIONAL

Dasar Teori

Teknik riset operasional adalah membahas pokok – pokok dan garis besar pemodelan matematis dalam penelitian operasional, model – model dan tekhnik solusi masalah penugasan, masalah programa sasaran (global programing). Memberikan keterampilan untuk merumuskan dan memecahkan permasalahan nyata dalam disiplin Tekhnik komputer dengan menggunakan model – model dan teknik – teknik.

Daftar Isi :

A. Riset Operasional............................................................................................I

B. Program Liniear..............................................................................................II

C. Permasalahan Minimasi..................................................................................III

D. Metode Simplex..............................................................................................IV

E. Penyimpangan - penyimpangan bentuk standar..............................................V

F. Dualitas...........................................................................................................VI

Perkembangan Riset Operasi

Istilah Riset Operasi (Operation Reseach) pertama kali digunakan pada tahun 1940 oleh Mc Closky dan Trefthen di suatu kota kecil Bowdsey Inggris. Riset Operasional adalah suatu metode pengambilan keputusan yang dikembangkan dari studi operasi-operasi militer selama Perang Dunia II. Pada masa awal perang 1939, pemimpin militer Inggris memanggil sekelompok ahli-ahli sipil dari berbagai disiplin dan mengkoordinasi mereka ke dalam suatu kelompok yang diserahi tugas mencari cara-cara yang efisien untuk menggunakan alat yang baru ditemukan yang dinamakan radar dalam suatu sistem peringatan dini menghadapi serangan udara. Kelompok ahli Inggris ini dan kelompok-kelompok lain berikutnya melakukan penelitian (research) pada operasi-operasi (operations) militer.

Setelah kesuksesan tim riset operasional ini, militer Inggris dan Amerika Serikat melanjutkan mengaktifkan tim riset operasional. Sebagai hasilnya, tim riset operasional semakin banyak yang disebut dengan “peneliti operasi militer” yang mengaplikasikan pendekatan riset operasional pada permasalahan pertahanan nasional. Beberapa teknik yang mereka kembangkan memasukkan ilmu politik, matematik, ekonomi, teori probabilitas dan statistik.

Setelah perang, keberhasilan kelompok-kelompok penelitian operasi-operasi dibidang militer menarik perhatian para industriawan dalam dunia usaha yang berkembang semakin kompleks. Perkembangan dunia usaha ini sangat terlihat dengan jelas setelah revolusi industri. Industri semakin kompleks, sumber daya yang dimiliki digunakan untuk berbagai kegiatan atau aktivitas, organisasi industri semakin besar, dan semua itu sering menggunakan sumber daya yang terbatas. Keterbatasan sumber daya menyebabkan kepentingan masing-masing aktivitas atau bagian saling bentrok.

Melihat kesuksesan tim riset operasional pada militer, industri secara bertahap mengaplikasi penggunaan riset operasional. Sejak tahun 1951, riset operasional diaplikasikan di dunia industry dan bisnis di Inggris dan juga di Amerika Serikat. Sejak itu riset operasional memberikan dampak besar pada organisasi manajemen. Baik jumlah maupun variasi aplikasinya bertumbuh sangat cepat.

Berdasarkan survei yang dilakukan di industri Amerika Serikat terhadap teknik riset operasional yang banyak digunakan dan bidang yang banyak menggunakan teknik riset operasional, dapat dilihat pada Tabel 1 dan 2 di bawah. Tabel 1 menunjukkan peringkat penggunaan teknik riset operasional pada berbagai perusahaan. Peringkat 1 menunjukkan teknik paling banyak digunakan. Tabel 2 menunjukkan peringkat bidang yang paling banyak menggunakan teknik riset operasional dua perusahaan yang disurvei. Peringkat 1 menunjukkan bidang yang paling banyak menggunakan.

Paling sedikit ada dua faktor lainnya yang turut berkontribusi dalam pengembangan riset operasional. Pertama adalah kemajuan mendasar yang dibuat di awal dalam pengembangan teknik yang ada terhadap riset operasional. Setelah perang, banyak ilmuwan yang berpartisipasi dalam tim riset operasional atau yang mendengarkan keberhasilan tim termotivasi untuk melanjutkan penelitian relevan terhadap suatu bidang, yang menunjukkan pengembangan penting dari sudut seni yang dihasilkan. Salah satu contoh paling penting adalah ditemukannya metode simpleks untuk menyelesaikan permasalahan pemrograman linear oleh George Dantzig tahun 1947. Banyak teknik riset operasional, seperti pemrograman linear, pemrograman dinamis, teori antrian dan teori inventori telah dikembangkan dengan baik di akhir tahuan 1950-an.

Faktor kedua adalah perkembangan teknologi komputer. Perhitungan kompleks sering harus dilakukan untuk permasalahan kompleks. Jika dilakukan dengan tangan (secara manual) sering menjadi masalah dan bahkan sering tidak mungkin dilakukan. Pengembangan komputer digital elektronik dengan kemampuan melakukan perhitungan aritmetik tinggi telah memberikan penyelesian yang ribuan atau jutaan kali lebih cepat daripada yang bisa manusia lakukan dengan tangan.

Perkembangan disiplin operation research diawaili dari keberhasilan-keberhasilan penelitian dari kelompok kelompok studi militer yang kemudian telah menarik kalangan Industriawan untuk membantu memberikan berbagai solusi terhadap masalah-masalah manajerial yang rumit. Dalam perkembangannya sekarang ini, Operation Reseach (OR) banyak diterapkan dalam menyelesaikan masalah-masalah manajemen untuk meningkatkan produktivitas atau efisiensi. Operation Reseach sering dinamakan sebagai Management Science.

Arti Riset Operasi

Secara harfiah kata operation dapat didefenisikan sebagai tindakan-tindakan yang diterapkan pada beberapa masalah atau hipotesis. Sementara kata research adalah suata proses yang terorganisasi dalam mencari kebenaran akan masalah atau hipotesis tadi.

Kenyataannya, sangat sulit untuk mendefenisikan Operation Research, terutama karena batas-batasnya tidak jelas. Operation Reseach memiliki bermacam-macam penjelasan, berikut ini beberapa kutipan defenisi operation research yang dikemukan oleh para ahli operation research dalam berbagai literature.

Definisi 1

Operation research is the applicarion of the methods of science to complex problem arising in the directin and management of large system of men, machines, materials and moner in industry, business, government, and defense. The distinctive approach is to develop a scientific model of a system, incorporating measurements of factors as chance and risk, with to predict and compare the outcomes of alternative decision, strategies or control. The purpose it to help management determine its policy and actions scientifically. (Operation Reseach Society of Great Britain).

Riset operasi adalah penerapan metode-metode ilmiah terhadap masalah-masalah rumit yang muncul dalam pengarahan dan pengelolaan dari sistem besar manusia, mesin, bahan dan uang dalam industry, bisnis, pemerintahan dan pertahanan. Pendekatan khusus ini bertujuan membentuk suatu model ilmiah dari sistem, menggabungkan ukuran-ukuran faktor-faktor seperti kesempatan dan risiko, untuk meramalkan dan membandingkan hasil-hasil dari beberapa keputusan, strategi atau pengawasannya. Tujuannya adalah membantu pengambil keputusan menentukan kebijakan dan tindakannya secara ilmiah.

Defenisi 2

Operation research concerned with scientifically deciding how to best design and operate man-machine system, usually under conditions requiring the allocation of scarce resource. (Dari buku Operation Reseach Principiles and Practice, karangan A.Ravindram dan Don T. Phillips dan James J. Solberg, dikutip dari Operation Reseach Society of America)

Riset Operasi berkaitan dengan menentukan pilihan secara ilmiah bagaimana merancang dan menjalankan sistem manusia-mesin secara terbaik, biasanya membutuhkan alokasi sumber daya yang langka.

Definisi 1 dan definisi 2 ini mungkin paling penting, karena kedua definisi tersebut berasal dari dua lembaga yang paling penting di bidang operation research.

Definisi-definisi lainnya untuk memperkaya wawasan yang dikutip dari berbagai literature sebagai berikut

Definisi 3

Operations Research today refers to the application of scientific methodology of several different disciplines to problems related to the functioning or operating of some unit-business, governmental, or institutional. (Dari buku Quantitative Approaches to Management, karangan Richard I. Levin dan Charles A. Kirkpatrick).

Definisi 4

Operations research is the application of scientific method to the decision problems of business and other units of social organization, including government and military organizations. (Dari buku Fundamentals of Operations Research for Management, karangan Shiv K. Gupta dan John M. Cozzolino).

Definisi 5

Operations research may be described as a scientific approach to decision making that involves the operations of organizational systems. (Dari buku Operation Research, karangan Frederick S. Hillier dan Gerald J. Lieberman).

Definisi 6

Operations research adalah seni memberikan jawaban buruk terhadap masalah-masalah, yang jika tidak, memiliki jawab yang lebih buruk (T.L. Saaty).

Definisi 7

Operations research adalah pendekatan dalam pengambilan keputusan yang ditandai dengan penggunaan pengetahuan ilmiah melalui usaha kelompok antar disiplin yang bertujuan menentukan penggunaan terbaik sumberdaya yang terbatas. (Churchman, Ackoff dan Arnoff, 1957)

Definisi 8

Operations research dijelaskan sebagai suatu metode, suatu pendekatan, seperangkat teknik, sekelompok kegiatan, suatu kombinasi beberapa disiplin, suatu perluasan dari disipilin-disiplin utama (matematika, teknik, ekonomi), suatu disiplinbaru, suatu lapangan kerja, bahkan suatu agama. OR mungkin beberapa dari semua hal ini. (S.L. Cook dalam Little Chid, 1977)

Berbagai defenisi diatas yang muncul dari berbagai ahli operation research karena begitu luasnya bidang dan kajian yang dapat dimasuki oleh disiplin ilmu operation reseach, berbagai defenisi diatas paling tidak ada rangkuman yang bisa diambil mengenai arti kata riset operasi, yaitu :

n Riset Operasi mencakup dua kata yaitu riset yang harus menggunakan metode ilmiah dan operasi yang berhubungan dengan proses atau berlangsungnya suatu kegiatan (proses produksi, proses pengiriman barang / militer / senjata, proses pemberian pelayanan melalui suatu antrian yang panjang).

n Definisi lain adalah : Riset Operasi adalah aplikasi metode ilmiah terhadap permasalahan yang kompleks dalam mengarahkan dan mengendalikan sistem yang luas mengenai kehidupan manusia, mesin-mesin, material dan uang dalam industri, bisnis, pemerintahan dan pertahanan.

TAHAPAN STUDI RISET OPERASI

Tahapan utama dalam studi Riset Operasi adalah:

1. Identifikasi permasalahan.

2. Pembangunan model.

3. Penyelesaian model.

4. Validasi model.

5. Implementasi hasil akhir.

Tahapan-tahapan tersebut dapat dijelaskan sebagai berikut :

1) Identifikasi permsalahan merupakan upaya untuk merumuskan atau menganalisis persoalan sehingga jelas tujuan apa yang akan dicapai (objectives)

2) Pembangunan model merupakan upaya dalam pembentukan model matematika untuk mencerminkan persoalan yang akan dipecahkan. Biasanya model dinyatakan dalam bentuk persamaan yang menggambarkan hubungan antara input dan output serta tujuan yang akan dicapai dalam bentuk fungsi objektif (objective function).

3) Mencari pemecahan dari model yang telah dibuat dalam tahap sebelumnya, misalnya dengan menggunakan metode simpleks.

4) Menguji model dan hasil pemecahan dari penggunaan model. Sering juga disebut melakukan validasi

Kegiatan yang dilakukan pada tahap pertama terdiri dari penentuan tujuan optimasi, identifikasi alternatif keputusan dan sumber daya yang membatasi kegiatan atau aktifitas untuk mencapai tujuan. Merumuskan atau mendefinisikan persoalan yang akan dipecahkan sesuai dengan tujuan yang akan dicapai berdasarkan keadaan objektif. Biasanya harus memperhatikan tiga hal yaitu : Pertama, uraian yang tepat mengenai tujuan yang akan dicapai, kedua, identifikasi daripada adanya alternatif dalam keputusan yang menyangkut suatu sistem, ketiga, mengenali adanya pembatasan-pembatasan (limitation, restriction dan juga persyaratan-persyaratan yang diperlukan sistem yang bersangkutan dengan pemecahan persoalan).

Tahapan ini akan dilakukan secara bersama-sama antara analis RO dengan pengguna atau pengambil keputusan. Jika identifikasi permasalahan sudah jelas dan lengkap, model keputusan dapat dibangun

Salah satu alasan pembentukan model dalam riset operasi adalah untuk menemukan variabel-variabel apa yang penting dan menonjol yang berkaitan erat dengan penyelidikan hubungan yang ada diantara variabel-variabel itu. Teknik-teknik kuantitatif seperti statistik dan simulasi bisa digunakan. Model dapat diklasifikasikan dalam banyak cara, misalnya menurut jenisnya, dimensinya, fungsinya, tujuannya, subyeknya, atau derajatnya. Kriteria yang paling biasa adalah jenis model yang meliputi iconoc (physical), analogue (diagramatic) dan symbolic (mathematical).

Model yang paling tepat harus digunakan, karena kesalahan pembentukan model akan mengakibatkan kesalahan pencapaian solusi optimum. Pemilihan model juga akan didasarkan pada waktu dan biaya yang tersedia. Tahapan penyelesaian model dilakukan dengan memilih salah satu teknik yang tersedia di RO. Penyelesaian dapat dilakukan menggunakan perangkat lunak komputer karena cukup tersedia perangkat lunak dengan berbagai kemampuan di pasaran. Untuk model yang sederhana tentunya dengan mudah dapat diselesaikan secara manual dengan atau tanpa bantuan kalkulator.

Model dinyatakan valid jika dapat memberikan prediksi yang masuk akal akan kinerja sistem. Metode umum yang digunakan untuk memeriksa validitas model adalah membandingkan solusi yang diperoleh dengan data lalu yang tersedia dari sistem nyata. Model dikatakan valid jika pada kondisi input yang sama dengan sistem nyata menghasilkan kinerja sistem yang sama dengan sistem nyata. Dengan kata lain bahwa model sah (valid) apabila dapat memberikan prediksi yang dapat dipercaya dari hasil proses suatu sistem, disamping diakui adanya ketidaktepatan dari model tersebut untuk mewakili keadaan yang sebenarnya terjadi (real world)

Tahap terakhir merupakan implementasi. Tahapan ini mencakup penerjemahan solusi optimal yang diperoleh pada tahap penyelesaian model ke dalam instruksi operasional yang dapat dimengerti oleh individu yang menjalankan sistem.

Model Dalam Riset Operasi

Bagian terpenting dari Riset Operasi adalah bagaimana menerjemahkan permasalahan sehari-hari ke dalam model matematis. Faktor-faktor yang mempengaruhi pemodelan harus disederhanakan dan apabila ada data yang kurang, kekurangan tersebut dapat diasumsikan atau diisi dengan pendekatan yang

bersifat rasional. Dalam Riset Operasi diperlukan ketajaman berpikir dan logika.

Untuk mendapatkan solusi yang optimal dan memudahkan kita mendapatkan hasil, kita dapat menggunakan komputer. Software yang dapat digunakan antara lain: LINDO (Linear, Interactive and Discrete Optimizer) dan POM For Windows.

Catatan penting dalam permodelan riset operasi adalah sebagai berikut :

ü Penyelesaian permasalahan keputusan pertama sekali dilakukan dengan membentuk model.

ü Pada aplikasi riset operasional umumnya, tujuan dan sumber daya yang membatasi dapat ditunjukkan secara kuantitatif atau matematik sebagai fungsi variabel keputusan digunakan model matematik.

ü Tidak semua permasalahan optimasi dapat dimodelkan menggunakan model matematik.

ü Meskipun dapat dimodelkan secara matematik, tidak jarang juga model matematik yang diformulasikan terlalu kompleks untuk diselesaikan menggunakan metode solusi yang ada.

ü Pendekatan lain yang digunakan untuk mengatasi permasalahan ini adalah menggunakan model simulasi.

ü Model simulasi tidak menunjukkan secara eksplisit hubungan input dan output.

ü Model simulasi cukup mahal.

• Dilihat dari bentuk data yang digunakan, model dapat dibedakan menjadi model deterministik dan model probabilistik atau stokastik.

· Model deterministik dibangun menggunakan data yang sifatnya pasti.

· Model probabilistik dibangun menggunakan data yang sifatnya tidak pasti.

Riset Operasi Dalam Pengambilan Keputusan.

Riset operasi berusaha menetapkan arah tindakan terbaik ( optinum) dari sebuah masalah keputusan dibawah pembatasan sumber daya yang terbatas. Istilah riset operasi sering kali diasosiasikan secara ekslusif dengan penggunaan teknik – teknik matematis untuk membuat model dan menganalisa masalah keputusan. Walaupun matematika dan model matematis merupakan inti dari riset operasi, pemecahan masalah tidaklah hanya sekedar pengembangan dan pemecahan model – model matematis. Secara spesifik, masalah keputusan biasanya mencakup factor – factor pentng yang berwujud dan tidak dapat diterjemahkan secara langsung dalam bentuk model matematis

Sebuah ilustrasi yang baik dari kasus diatas adalah salah satu versi dari masalah elevator yang dikenal luas. Sebagi tanggapan terhadap keluhan para penghuni tentang lambatnya elevator disebuah bangunan perkantoran yang besar, sebauh pemecahan yang didasari oleh analisis teori jalur atrian ditemukan tidak memuaskan. Setelah mempelajari sistem tesebut lebih disebabkan oleh kebosanan karena pada kenyataan, waktu menunggu sangat singkat.

Sebuah pemecahan diajukan dimana sebuah cermin panjang dipasang ditempat masuk elevator. Keluhan menghilang karena para pengguna elevator asik memandangi diri mereka sendiridan orang lain sambil menunggu elevator. Ilutrasi elevator ini menggarisbawahi pentingnya memandang aspek matematis dari riset operasi dalam konteks yang lebih luas dari sebuah model matematis. sebagai sebuah teknik pemecahan masalah, riset operasi harus dipandang sebagai ilmu dan seni. Aspek ilmu terletak dalam penyediaan teknik – teknik matematis dan algoritma untuk memecahkan masalah keputusan yang tepat. Riset operasi adalah sebuah seni karena keberhasilan dalam semua tahap yang mendahului dan melanjuti pemecahan dari sebuah model matematis sebagian besar bergantung pada kreativitas dan kemampuan pribadi dari mereka yang menganalisis pengambilan keputusan.

Model – Model Riset Operasi.

Model adalah abstaraksi atau penyederhanaan realitas sistem kompleks dimana hanya komponen – komponen yang relevan atau faktor – faktor yang dominan dari masalah yang dianalisis diikutsertakan. Ia menunjukan hubungan – hubungan dari aksi dalam pengertian sebab akibat. Salah satu alasan pembentukan model adalah untuk menemukan variable – variable apa yang penting. Penemuan variable – variable itu. Teknik - teknik kuantatif seperti statistic dan simulasi digunakan untukmenyelidik hubungan yang ada diantara banyak variable dalam suatu model.

Model – model riset operasi, model dapat diklasifikasikan dalam banyak cara, misalnya menurut jenisnya, dimensinya, fungsi tujuannya, subyeknya, atau derajad abstrasinya. Kriteria yang paling biasa adalah jenis model. Jenis dasar it meliputi :

a. Iconic (Physical) Model

Iconic model adalah suatu penyajian fisik yang tampak seperti aslinya dari suatu sistem nyata dengan skala yang berbeda. Contoh model ini adalah mainan anak – anak, potret, histigram, market dan lain – lain.

b. Analogue Model.

Model analogue lebih abstark dibanding model iconic, karena tak kelihatan sama antara model dengan sistem nyata. Contohnya jaringan pipa tempat air mengalir dapat digunakan dengan pngertian yang sama sebagai distribusi aliran listrik contoh lain peta dengan bermacam – macam warna merupakan model analog dimana perbedaan warna merpakan ciri, misal biru menunjukan air.

c. Matematic (simbolic) model

PROGRAM LINIEAR

PROGRAM LINIEAR

Program liniear adalah salah satu model matematika yang digunakan untuk menyelesaikan masalah optimisasi, yaitu memaksimumkan atau meminimumkan fungsi tujuan yang bergantung pada sejumlah variable input. Hal terpenting yang perlu kita lakukan adalah mencari tahu tujuan penyelesaian masalah dan apa penyebab masalah tersebut.

DUA MACAM FUNGSI PROGRAM LINIEAR:

Ø Fungsi tujuan : mengarahkan analisa untuk mendeteksi tujuan perumusan masalah

Ø Fungsi kendala : untuk mengetahui sumber daya yang tersedia dan permintaan atas sumber daya tersebut.

MASALAH MAKSIMASI

Maksimasi dapat berupa memaksimalkan keuntungan atau hasil. Contoh:

PT. EL TIGRE TEKSTIL memiliki sebuah pabrik yang akan memproduksi 2 jenis produk, yaitu kain sutera dan kain wol. Untuk memroduksi kedua produk diperlukan bahan baku benang sutera, bahan baku benang wol, dan tenaga kerja. Maksimum penyediaan benang sutera adalah 60kg perhari, benang wol 30kg perhari dan tenaga kerja 40jam perhari. Kebutuhan setiap unit produk akan bahan baku dan jam tenaga kerja dapat dilihat dalam tabel.

Jenis Bahan Baku dan Tenaga Kerja	Kain Sutera	Kain Wol	Maksimum Penyediaan
Benang Sutera	2	3	60kg
Benang Wol	-	2	30kg
Tenaga Kerja	2	1	40Jam

Kedua jenis produk memberikan keuntungan sebesar 40juta untuk kain sutera dan 30juta untuk kain wol. Masalahny adalah bagaimana menentukan jumlah unit setiap jenis produk yang akan di produksi setiap hari agar keuntungan yang diperoleh bisa maksimal.

Langkah – lanhgkah :

1. Tentukan Variable

X1 = Kain sutera

X2 = Kain Wol

2. Fungsi tujuan

Zmax = 40X1 + 30X2

3. Fungsi kendala / batasan

1) 2X1 + 3X2_60 (benang sutera)

2) 2X2_30 (benang wol)

3) 2X1 + X2_40 (tenaga kerja)

4. Membuat Grafik

1) 2X1 + 3X2 = 60

X1 =0, X2 = 60/3 = 20

X2 =0, X1 = 60/2= 30

2) 2X2_30

X2 = 15

3) 2X1 + X2_40

X1 = 0, X2 = 40

X2 = 0, X1 = 40/2 = 20

40 3

15 E C 2

A B 1

0 20 30 X1

Daerah Penyelesaian

Cara Mendapatkan solusi Optimal :

1. Dengan Mencari nilai Z setiap titk ekstrim.

Ø Titik A

X1 = 0, X2 = 0

Masukan nilai X1 dan X2 ke Z

Z = 40 . 0 + 30 . 0 = 0

Ø Titik B

X1 = 20, X2 = 0

Masukan nilai X1 dan X2 ke Z

Z = 40 . 20 + 30 . 0 = 800

Ø Titik C

Mencari titik potong (1) dan (3)

2X1 + 3X2 = 60

2X1 + X2 = 40

2X2 = 20 X1 = 10

Masukan X2 ke kendala (1)

2X1 + 3X2 = 60

2X1 + 3 . 10 = 60

2X1 + 30 = 60

2X1 = 30 X1 = 15

Masukan nilai X1 dan X2 ke Z

40X1 + 30X2 = 40 . 15 + 30 . 10 = 600 + 300 = 900 (optimal)

Ø Titik D

2X2 = 30

X2 = 15

Masukan X2 ke kendala (1)

2X1 + 3 . 15 = 60

2X1 + 45 = 60

2X1 = 15 X1 = 7,5

Masukan nilai X1 dan X2 ke Z

Z = 40 . 0 + 30 . 0 = 450

Kesimpulan :

Untuk memperoleh keuntungan optimal, maka X1 = 15 dan X2 = 10 dengan keuntungan sebesar Rp 900Juta.

2. Dengan cara menggeser garis fungsi tujuan.

Solusi optimal akan tercapai pada saat garis fungsi tujuan menyinggung daerah feasible (daerah yang diliputi oleh semua kendala) yang terjauh dari titik origin. Pada gambar, solusi optimal tercapai pada titik C yaitu persilangan garis kendala (1) dan (3).

TITIK C

Mencari titik potong (1) dan (3)

2X1 + 3X2 = 60

2X1 + X2 = 40

2X2 = 20

X2 = 10

Masukan X2 ke kendala (1)

2X1 + 3X2 = 60

2X1 + 3 . 10 = 60

2X1 + 3X2 = 60

2X1 = 30 < - > X1 = 15

Masukan nilai X1 dan X2 ke Z

40 X1 + 30X2 = 40 . 15 + 30 . 10 = 600 + 300 =900

Permasalahan Minimasi.

Permasalahan Minimasi

Minimasi dapat berupa meminmumkan biaya produksi. Solusi optimal tercapai pada sat fugsi garis fugsi tujuan menyinggung daerah fasible yang terdekat dengan titik origin. Contoh :

Perusahaan makanan ROYAL merencanakan untuk membuat dua jenis makanan yaitu Royal Bee dan Royal Jely. Kedua jenis makanan tersebut mengandung Vitamin dan Protein. Royal Bee paling sedikit di produksi 2 unit da Royal Bee paling sedikit di produksi 1 unit. Tabel berikut menunjukan jumlah vitamin dan protein dalam setiap jenis makkanan.

Jenis Makanan	Vitamin (Unit)	Protein (unit)	Biaya Per unit (ribu rupiah)
Royal Bee	2	2	100
Royal Jelly	1	3	80
Minimum Kebutuhan	8	12

Bagaimana menentukan kombnasi kedua jenis makanan agar meminimumkan biaya produksi.

Langkah - langkah:

1. Tentukan Variable

X1 = Royal Bee

X2 = Royal Jelly

2. Fungsi Tujuan

Zmin = 100 X1 + 80 X2

3. Fungsi Kendala

1) 2X1 + X2 _8 (Vitamin)

2) 2 X1 + 3X2_12 (Protein)

3) X1_2

4) X2_1

4. Membuat Grafik

1) 2 X1 + X2 = 8

X1 = 0, X2 = 8

X2 = 0, X1 = 6

2) 2X1 + 3 X2 = 12

X1 = 0, X2 = 4

X2 =0, X1 = 6

3) X1 = 2

4) X2 = 1

(1)

(3)

(2)

4 C

1 A

2 4 6

Solui optimal tercapai pada titik B (terdekat dengan titik origin) , yaitu persilangan garis kendala (1) dan (2).

2X1 + X2 = 8

2X1 + X2 = 12

-2X2 = -4 <-> X2 = 2

Masukan kendala X2 ke kendala (1)

2X1 + X2 = 8

2X1 + 2 =8

2X1 = 6 <-> X1 = 3

Masukan nilai X1 dan X2 ke Z

Zmin = 100X1 + 80X2 = 100 . 3 + 80 . 2 = 300 + 160 = 460

Kesimpulan

Untuk meminimumkan biaya produksi, maka X1 = 3 dan X2 = 2 dengan biaya produksi 460 rupiah.

Metode Simplex

METODE SIMPLEX

Metode grafik tidak dapat menyelesaikan persoalan liniear program yang memiliki variable keputusan yang cukup besar atau lebih dari dua, maka untuk menyelesaikan diugnakan mtode simplex.

Beberapa ketentuan yang perlu diperhatikan, antara lain :

1. Nilai kanan (NK/ RHS) fungsi tujuan harus nol (0).

2. Nilai kanan (RHS) fungsi kendala harus positif. Apabila negatif, nilai tersebut harus dikalikan -1.

3. Fungsi kendala dengan tanda “_” harus diubah ke bentuk “=” dengan menambahkan variable slack/surplus. Variable slack/surplus disebut juga variable dasar.

4. Fungsi kendala dengan tanda “_” diubah ke bentuk “_” dengan cara mengalikan dengan -1, lalu diubah ke bentuk persamaan dengan ditambahkan variable slack. Kemudian karena RHS-nya negatif, dikalikan lagi dengan -1 dan ditambah artifical variable (M).

5. Fungsi kendala dengan tanda “=” harus ditambah artifical variable (M).

Pembuatan tabel simplex

Contoh Soal :

Kendala :

1) 2X1 <= 8

2) 3X2 <= 15

3) 6X1 + 5 X2 <= 30

Langkah- langkah :

1. Mengubah fungsi tujuan dan fungsi kendala (lihat beberapa ketentuan yang harus diperhatikan di atas!).

Fungsi tujuan.

Z = 3X1 + 5X2 => Z - 3X1 - 5X2 = 0

Fungsi kendala:

1) 2X1_8 => 2X1 + X3 = 8

2) 3X2_15 => 3X2 + X4 = 15

3) 6X1 + 5X2 _30 => 6X1 + 5X2 + X5 = 30

(X3 , X4 dan X5 adalah variable slack)

2. Menyusun persamaan – persamaan ke dalam tabel.

Var.Dsr	Z	X1	X2	X3	X4	X5	NK	Index
Z	1	-3	-5	0	0	0	0
X3	0	2	0	1	0	0	8
X4	0	0	3	0	1	0	15
X5	0	6	5	0	0	1	30

Var.Dsr	Z	X1	X2	X3	X4	X5	NK	Index
Z	1	-3	-5	0	0	0	0
X3	0	2	0	1	0	0	8
X4	0	0	3	0	1	0	15
X5	0	6	5	0	0	1	30

3. Memilih baris kunci

INDEX = Nilai Kanan(NK)

Nilai Kolom Kunci

Baris kunci adalah baris yang mempnyai index terkecil

Var.Dsr	Z	X1	X2	X3	X4	X5	NK	Index
Z	1	-3	-5	0	0	0	0
X3	0	2	0	1	0	0	8	-
X4	0	0	3	0	1	0	15	5
X5	0	6	5	0	0	1	30	6

Angka kunci koef angka kolom kunci

4. Mengubah nilai – nilai baris kunci => dengan cara membaginya dengan angka kunci

Baris baru kunci = baris kunci : angka kunci

Sehingga tabel menjadi sperti berikut:

Var.Dsr	Z	X1	X2	X3	X4	X5	NK	Index
Z	1	-3	-5	0	0	0	0
X3	0	2	0	1	0	0	8	-
X2	0	0	3	0	1/3	0	15	5
X5	0	6	5	0	0	1	30	6

5. Mengubah nilai – nilai selain baris kunci sehingga nilai – nilai kolom kunci (selain baris kunci) = 0

Baris baru = baris lama – (koefisien angka kolom kunci X nilai baris baru kunci)

Baris Z

Baris lama [-3 -5 0 0 0 0 ]

NBBK -5 [0 1 0 1/3 0 5 ]

Baris baru -3 0 0 5/3 0 25

Baris X3

Baris lama [ 2 0 1 0 0 8 ]

NBBK 0 [ 0 1 0 1/3 0 5 ]

Baris baru 2 0 1 0 0 8

Baris X5

Baris lama [ 6 5 0 0 1 30 ]

NBBK 0 [ 0 1 0 1/3 0 5 ]

Baris baru 6 0 0 -5/3 1 5

Masukan nilai di atas ke dalam tabel, sehingga tabelenjadi berikut:

Var.Dsr	Z	X1	X2	X3	X4	X5	NK	Index
Z	1	-3	0	0	5/3	0	25
X3	0	2	0	1	0	0	8
X2	0	0	1	0	1/3	0	5
X5	0	6	0	0	-5/3	1	5

Var.Dsr	Z	X1	X2	X3	X4	X5	NK	Index
Z	1	-3	0	0	5/3	0	25
X3	0	2	0	1	0	0	8	4
X2	0	0	1	0	1/3	0	5	-
X5	0	6	0	0	-5/3	1	5	5/6

Z	1	0	0	0	5/6	1/2	271/2	Zmax
X3	0	0	0	1	5/9	-1/3	6 1/3
X2	0	0	1	0	1/3	0	5
X1	0	6	0	0	-5/3	1/6	5/6

Diperoleh hasil : X1 = 5/6 , X2 = 5 , Zmax = 271/2

Penyimpangan Penyimpangan Bentuk Standar

Penyimpangan – Penyimpangan Bentuk Standar

1. Fungsi batasan dengan tanda sama dengan (=)

ð Ditambah dengan variable buatan

Contoh :

Fungsi kendala :

1) 2X1 <= 8 => 2X1 + X3 = 8

2) 3X2 <= 15 => 3X2 + X4 = 15

3) 6X1 + 5X2 = 30 => 6X1 + 5X2 + X5 = 30

Fungsi tujuan:

Z = 3X1 + 5X2 => Z - 3X1 - 5X2 – MX5 = 0

Nilai setiap variable dasar (X5) harus sebesar 0, sehingga fungsi tujuan harus dikurangi dengn M dikalikan dengan baris batasan yang bersangkutan (3). Nilai baris Z sebagai berikut :

[ -3 -5 0 0 M , 0 ]

M [ 6 0 0 1 , 30 ]

(-6M-3) (-5M-5) 0 0 0 -30M

Tabel

Var.Dsr	Z	X1	X2	X3	X4	X5	NK	Index
Z	1	-6M-3	-5M-5	0	0	0	30M
X3	0	2	0	1	0	0	8	4
X4	0	0	3	0	1	0	15	-
X5	0	6	5	0	0	1	30	5

VD	Z	X1	X2	X3	X4	X5	NK	Index
Z	1	0	-5M	3M+3/2	0	0	-6M+12
X1	0	1	0	1/2	0	0	4	-
X4	0	0	3	0	1	0	15	5
X5	0	0	5	-3	0	1	6	6/5

Z	1	0	0	-3/2	0	M+1	18
X1	0	1	0	1/2	0	0	4	8
X4	0	0	0	9/5	1	-3/5	19/3	5/27
X2	0	0	1	-3/5	0	1/5	6/5	-2

Z	1	0	0	0	5/6	M+1/2	271/2	Max
X1	0	1	0	0	-5/18	1/6	5/6
X3	0	0	0	1	5/9	-1/3	61/3
X2	0	0	1	0	1/3	0	5

2. Fungsi tujuan : Minimasi

Soal minimasi harus diubah menjadi maksimasi dengan cara mengganti tanda positif dan negatif pada fungsi tujuan.

Contoh

Minimumkan Z = 3X1 + 5X2

Fungsi Batasan : 1). 2X1 = 8

2). 3X2_15

3). 6X1 + 5X_30

Penyelesaian

Fungsi batasan : 1). 2X1 + X3 = 8

2). 3X2 + X4 = 15

3). 6X1 + 5X2 – X5 + X6 = 30

Fungsi tujuan menjadi :

Maksimumkan (-Z) = 3X1 - 5X2 - MX3 - MX6

Diubah menjadi fungsi implisit => -Z = 3X1 + 5X2 + MX3 + MX6

Nilai – niai variable dasar (X3 dan X6 ) harus = 0, maka :

[ 3 5 M 0 0 M , 0 ]

-M [2 0 1 0 0 0 , 8 ]

-M [6 5 0 0 -1 1 , 30]

(-8M+3) (-5M+5) 0 0 M , -38M

Tabel

VD	Z	X1	X2	X3	X4	X5	X6	NK	Indx
Z	-1	-8M+3	-5M+5	0	0	0	0	-38
X3	0	2	0	1	0	0	0	8	4
X4	0	0	3	0	1	0	0	15
X6	0	6	-5	0	0	-1	1	30	5

Z	-1	3	-5M+5	4M-3/2	0	M	0	-6M-12
X1	0	1	0	½	0	0	0	4
X4	0	0	3	0	1	0	0	15	5
X6	0	0	5	-3	0	-1	1	6	6/5

Z	-1	0	0	M+3/2	0	1	M+1	-18	min
X1	0	1	0	½	0	0	0	4
X4	0	0	1	9/5	1	3/5	-3/5	5 2/5
X2	0	0	1	-3/5	0	-1/5	1/5	6/5

(Karena –Z = -18 , maka Z = 18)

Penyelesaian optimal : X1 = 4, X2 = 6/5 , dan Zmin =18

Dualitas.

DUALITAS

Dualitas sebuah pemodelan pemrograman liniear, terdapat dua konsep yang saling berlawanan. Konsep yang pertama kita sebut prima dan yang kedua Dual. Bentuk dual adalah kebalikan dari bentuk prima. Hubungan primal dan dual sebagai berikut:

Masalah Primal (atau Dual) Masalah Dual (atau Primal)

Koefisien fungsi tujuan...........................................Nilai kanan fungsi batasan

Maksimumkan Z (atau Y).......................................Variable Yi (atau Xi)

Batasan i .................................................................Yi >= 0

Bentuk <=................................................................Yi >= dihilangkan

Variable Xj .............................................................Batasan j

Xj ............................................................................Bentuk >=

Xj hilangkan............................................................Bentuk =

Contoh 1 :