Program Linier PDF

Preview

Summary

Hayatun Nufus Erdawati Nurdin PROGRAM LINIER i Katalog Dalam Terbitan (KDT) Program Linier Penulis : Hayatun Nufus : Erdawati Nurdin Editor : Rezi Ariawan Layout : Rismansyah Design Cover : Cahaya Firdaus Team ISBN : 978 602 60473 8 0 vi, 139 hal (145x205mm) Cetakan Tahun 2016 Penerbit : CAHAYA FIR...

Description

Accelerat ing t he world's research.

Program Linier Hayatun Nufus Cahaya Firdaus

Cite this paper

Downloaded from Academia.edu 

Get the citation in MLA, APA, or Chicago styles

Related papers

Download a PDF Pack of t he best relat ed papers 

Opt imasi Bidang Perikanan: Pendekat an Linier Programming, Transport asi dan Goal Program… Harsuko Riniwat i

Analisis vekt or & p[erasional researc umi ailiyah T UGAS AKHIR SEMEST ER MANAJEMEN OPERASI MAT ERI PERT EMUAN KE 1-7 Marlina Sukesi

Hayatun Nufus Erdawati Nurdin

PROGRAM LINIER

i

Katalog Dalam Terbitan (KDT) Program Linier Penulis

: Hayatun Nufus : Erdawati Nurdin

Editor

: Rezi Ariawan

Layout

: Rismansyah

Design Cover

: Cahaya Firdaus Team ISBN

: 978 602 60473 8 0 vi, 139 hal (145x205mm) Cetakan Tahun 2016 Penerbit : CAHAYA FIRDAUS Publishing and Printing

Jl. Sepakat No. 101 Panam-Pekanbaru Mobile Phone : +6285265504934 Undang – undang Republik Indonesia Nomor 19 Tahun 2002 Tentang Hak Cipta

Lingkup Hak Cipta Pasal 2 1. Hak Cipta merupakan Hak Eklusif bagi Pencipta atau Pemegang Hak Cipta untuk mengumumkan atau memperbanyak ciptaannya yang timbul secara otomatis setelah suatu ciptaan dilahirkan tanpa mengurangi pembatasan menurut peraturan perundanga-undangan yang berlaku Lingkup Hak Cipta Pasal 72 1. Barang siapa dengan sengaja melanggar dan tanpa hak melakukan perbuatan sebagaimana dimaksud pasal 2 ayat 1 atau pasal 49 ayat 1 dan 2 dipidana penjara masing-masing paling singkat 1 bulan dan/atau denda paling sedikit Rp. 1.000.000,- atau pidana penjara paling lama 7 tahun dan/atau paling banyak Rp. 5.000.000.000,2. Barang siapa dengan dengaja menyiarkan, memamerkan, mengedarkan, atau menjual kepada umum suatu ciptaan atau barang hasil pelanggaran hak cipta sebagaimana dimaksud dalam ayat 1, dipidana dengan penjara paling lam 5 tahun dan atau denda paling banyak Rp. 500.000.000,-

ii

KATA PENGANTAR Alhamdulillah penulis ucapkan puji syukur kehadirat Allah SWT, karena atas berkat rahmat dan hidayah-Nya penulis dapat menyelesaikan buku ini dengan judul Program Linier. Program linier merupakan salah satu mata kuliah yang wajib diikuti oleh semua mahasiswa di Program Studi Pendidikan Matematika. Buku ini terdiri atas 15 bab yang diawali dengan pengetahuan dasar tentang program linier. Selanjutnya diikuti oleh berbagai metode yang dapat digunakan untuk menyelesaikan persoalan program linier. Secara umum, metode-metode penyelesaian ini disajikan dalam 3 sub bab, yaitu pengantar, langkah-langkah, dan contoh penerapan. Penulis mengucapkan terima kasih kepada semua pihak yang telah membantu dalam penyusunan buku ini, terutama Rezi Ariawan, M. Pd. Penulis menyadari keterbatasan ilmu dan pengalaman dalam menyusun buku ini. Oleh karena itu, saran dan kritik yang konstruktif sangat diperlukan demi kesempurnaan buku ini. Semoga buku ini dapat bermanfaat bagi kita semua.

Pekanbaru, Oktober 2016

Penulis

iii

DAFTAR ISI Halaman KATA PENGANTAR ............................................................................. iii DAFTAR ISI .......................................................................................... iv BAB 1 PENGETAHUAN DASAR PROGRAM LINIER A. Sejarah Program Linier .............................................................. 1 B. Konsep Dasar Program Linier ....................................................4 C. Ciri-ciri Program Linier ............................................................... 5 D. Model Program Linier ................................................................ 5 BAB 2 METODE GRAFIK A. Pengantar ................................................................................8 B. Langkah-langkah .......................................................................8 C. Contoh Penerapan ....................................................................9 BAB 3 METODE ALJABAR A. Pengantar .............................................................................. 12 B. Langkah-langkah ..................................................................... 12 C. Contoh Penerapan ................................................................... 13 BAB 4 METODE SUDUT A. Pengantar .............................................................................. 17 B. Langkah-langkah ..................................................................... 17 C. Contoh Penerapan-1 ................................................................ 18 D. Contoh Penerapan-2 ............................................................... 22 E. Contoh Penerapan-3 ............................................................... 23

iv

BAB 5 METODE SIMPLEKS A. Pengantar .............................................................................. 25 B. Langkah-langkah ..................................................................... 30 C. Contoh Penerapan ................................................................... 31 BAB 6 METODE SIMPLEKS DIREVISI A. Pengantar .............................................................................. 36 B. Langkah-langkah ..................................................................... 37 C. Contoh Penerapan .................................................................. 38 BAB 7 METODE BRANCH AND BOUND A. Pengantar .............................................................................. 46 B. Langkah-langkah ..................................................................... 46 C. Contoh Penerapan .................................................................. 47 BAB 8 MODEL TRANSPORTASI A. Pengantar .............................................................................. 64 B. Formulasi Matematis dari Model Transportasi .......................... 65 C. Permasalahan pada Model Transportasi ................................... 68 BAB 9 METODE NORTH WEST CORNER A. Pengantar .............................................................................. 70 B. Langkah-langkah ..................................................................... 72 C. Contoh Penerapan .................................................................. 74 BAB 10 METODE LEAST COST A. Pengantar .............................................................................. 88 B. Langkah-langkah ..................................................................... 89 C. Contoh Penerapan-1 ............................................................... 90 D. Contoh Penerapan-2 ............................................................... 94

v

BAB 11 VOGEL APPROXIMATION METHOD (VAM) A. Pengantar ............................................................................ 102 B. Langkah-langkah ................................................................... 102 C. Contoh Penerapan ................................................................ 103 BAB 12 METODE STEPPING STONE A. Pengantar ............................................................................ 112 B. Langkah-langkah ................................................................... 112 C. Contoh Penerapan ................................................................ 113 BAB 13 METODE MODI A. Pengantar ............................................................................ 119 B. Langkah-langkah ................................................................... 119 C. Contoh Penerapan ................................................................ 120 BAB 14 MODEL PENUNJUKKAN A. Pengantar ............................................................................ 125 B. Langkah-langkah ................................................................... 126 C. Contoh Penerapan ................................................................ 126 BAB 15 METODE PERJALANAN SALESMEN A. Pengantar ............................................................................ 132 B. Langkah-langkah ................................................................... 133 C. Contoh Penerapan ................................................................ 134 DAFTAR PUSTAKA ............................................................................... 139

vi

BAB 1 PENGETAHUAN DASAR PROGRAM LINIER A.

SEJARAH PROGRAM LINIER

Akar dari perkembangan program linier dapat ditelusuri kembali dalam beberapa dekade, dimana penggunaan pendekatan ilmiah dalam manajemen organisasi dimulai. Bagaimanapun juga, permulaan dari kegiatan yang disebut program linier telah mulai dikembangkan penggunaannya pada permulaan Perang Dunia Kedua. Pada saat itu, dirasa perlu untuk mengalokasikan sumber daya-sumber daya yang terbatas dan langka untuk bermacam-macam operasi militer. Dan, kegiatankegiatan dalam setiap operasi harus dilakukan dengan cara yang efektif untuk memenangkan perang. Manajemen militer Inggris dan kemudian Amerika mulai “memanggil” para ahli untuk menerapkan pendekatan ilmiah untuk keperluan strategis dan taktis militernya. Keberhasilan upaya ini tampak dalam kemenangan Angkatan Udara Inggris, peperangan di Atlantik Utara, dan sebagainya. Setelah perang dunia kedua berakhir, dengan melihat suksesnya penggunaan teori program linier dalam militer, kalangan industri menjadi tertarik pada bidang baru ini. Pertumbuhan industri (setalah perang berakhir) terjadi sangat pesat, sehingga para ahli yang menguasai teori program linier sangat dibutuhkan dalam dunia bisnis, karena masalah-masalah yang timbul pada dasarnya sama, walaupun dalam konteksnya berbeda dengan permasalahan yang dihadapi kalangan militer. Dari waktu ke waktu, kegunaan teori ini semakin dirasakan oleh perusahaan-perusahaan (terutama perusahaan besar), sehinggga mereka berlomba-lomba untuk memperkerjakan para ahli di bidang ini atau mengirimkan staf mereka untuk memperdalam ilmunya di bidang teori program linier. Beberapa tokoh yang sangan dikenal di bidang ini adalah Leonid Vitaliyevich Kantorovich, Tjalling Charles Koopmans, dan George Bernard Dantzig.

Program Linier

|1

BAB 2 METODE GRAFIK A.

PENGANTAR

Metode Grafik merupakan salah satu metode yang dapat digunakan untuk memecahkan permasalahan linier programming. Metode ini menggunakan pendekatan grafik dalam pengambilan keputusannya, dimana seluruh fungsi kendala dibuat dalam satu bagian gambar kemudian diambil keputusan yang optimum. Metode ini terbatas pada pemakaian untuk dua variabel keputusan, apabila memiliki lebih dari dua variabel keputusan, maka metode ini tidak dapat digunakan. Artinya persamaan atau pertidaksamaan harus terdiri dari dua variabel. Perhatikan contoh dibawah ini

B.

LANGKAH – LANGKAH

Ada beberapa langkah yang harus diikuti dalam menyelesaikan permasalahan program linier menggunakan mentode grafik, yaitu: 1. Buat model yang sesuai dengan masalah yang ada. Artinya, rumuskan masalah asli atau masalah yang diberikan menjadi model matematika yang sesuai dengan syarat-syarat yang diperlukan dalam model

8|

Program Linier

BAB 3 METODE ALJABAR A.

PENGANTAR

Salah satu metode yang dapat digunakan untuk menyelesaikan permasalahan program linear adalah metode aljabar. Metode ini dikatakan sebagai metode aljabar karena dalam menyelesaikan permasalahan program linear dengan menggunakan metode ini banyak menggunakan aturan-aturan aljabar, diantaranya adalah substitusi dan eliminasi. Oleh sebab itu, metode ini dikatakan sebagai metode aljabar. Untuk menyelesaikan permasalahan program linear dengan menggunakan metode ini, maka ada beberapa langkah yang harus diikuti. Berikut langkahlangkahnya. B.

LANGKAH-LANGKAH

Langkah-langkah dalam menyelesaikan permasalahan program linear menggunakan metode aljabar diantaranya: 1. Mengubah persoalan program linear yang belum dalam bentuk standar menjadi persoalan program linear yang sudah dalam bentuk standar dengan cara mengubah tanda pertidaksamaan menjadi persamaan. Untuk mengubah tanda pertidaksamaan menjadi persamaan dapat dilakukan dengan cara memasukkan “Slack Variable” dan ”Surplus Variable”. Slack Variable merupakan variabel yang ditambahkan disebelah kiri tanda ketidaksamaan, agar ketidaksamaan menjadi persamaan. Selanjutnya slack variabel digunakan apabila fungsi tujuan yang dinyatakan adalah maksimumkan atau fungsi pembatasnya bertanda (≤). Sementara surplus variabel merupakan variabel yang harus dikurangkan disebelah kiri tanda ketidaksamaan. Surplus variabel digunakan untuk fungsi tujuan yang dinyatakan adalah minimumkan atau fungsi pembatasnya bertanda (≥). Perhatikan contoh berikut:  4X1 + 2X2 ≤ 60 4X1 + 2X2 + X3 = 60 (Penambahan Slack Variable)

12 |

Program Linier

BAB 4 METODE SUDUT A.

PENGANTAR

Metode sudut merupakan salah satu metode yang dapat digunakan dalam menemukan selesaian dari permasalahan program linear. Metode sudut ini tidak jauh berbeda dengan metode grafik. Dalam menyelesaikan permasalahan program linear dengan menggunakan metode sudut, kita tidak perlu menggambarkan beberapa grafik persamaan seperti dalam metode grafik. Yang kita lakukan dalam menggunakan metode sudut adalah melakukan pengecekan apakah persamaan yang dihasilkan memenuhi atau tidak dari persamaan awal yang diberikan. B.

LANGKAH-LANGKAH

Adapun langkah-langkah yang dapat ditempuh dalam menyelesaikan permasalahan program linear dengan menggunakan metode sudut adalah: 1. Menyusun Pertidaksamaan. a. x1 ≥ 0 b. x2 ≥ 0 c. xn ≥ 0 d. x1 + x2 + ….+ xn ≤ c1 e. x1 + x2 + ….+ xn ≤ cm 2. Membuat sebuah tabel dengan komponen: a. Sudut b. Koordinat titik sudut c. Cek d. = fungsi tujuan 3. Menentukan kombinasi sudut. 4. Menentukan koordinat titik-titik sudut. 5. Melakukan pengecekan titik sudut yang diperoleh ke semua pertidaksamaan memenuhi (M) atau tidak memenuhi (TM).

Program Linier

| 17

BAB 5 METODE SIMPLEKS A.

PENGANTAR

Metode simpleks merupakan prosedur aljabar yang bersifat iteratif (pengulangan), yang bergerak selangkah demi selangkah, dimulai dari suatu titik ekstrem pada daerah fisibel (ruang solusi) menuju ke titik ekstrem yang optimum. Secara matematis, permasalahan program linier dapat ditulis sebagai berikut : Maks. atau min. : z  c1 x1  c2 x2  ...  cn xn Berdasarkan :

a11 x1  a12 x 2  ....  a1n x n  b1

a 21 x1  a 22 x 2  ....  a 2 n x n  b2 . . . a m1 x1  a m 2 x 2  ....  a mn x n  bm xi  0, i  1,2,...n 

Jika kita defenisikan

:

a11 a12 ... a1n   x1  b1  a  x  b   21 a 22 ... a 2 n   2  2 .  .  .  A  ; X   ; B  .  .  .  .  .  .         x n  bm  a m1 a m 2 ... a mn 

Program Linier

| 25

BAB 6 METODE SIMPLEKS DIREVISI A.

PENGANTAR

Metode Simpleks direvisi digunakan dengan ketentuan apabila terjadi penyimpangan-penyimpangan dari bentuk standar simpleks. Adapun penyimpangan dari bentuk standar dapat terjadi karena beberapa sebab, antara lain karena: 1.

Batasan dengan tanda sama dengan (=)

Batasan dari persoalan program linier yang bertanda sama dengan (=) harus diubah agar sesuai dengan bentuk standar, sehingga dapat diselesaikan dengan menggunakan metode simpleks. Caranya adalah dengan menambahkan variabel buatan (artivicial variable) yang bernilai positif, yang dilambangkan dengan x n 1 , xn  2 , … Sebelum variabel buatan masuk, batasan sudah berbentuk persamaan, setelah variabel buatan masuk, masih berbentuk persamaan. Akibatnya, timbul syarat agar tetap sesuai dengan persamaan semula, maka variabel buatan harus bernilai nol (0). Variabel buatan yang ditambahkan hanya merupakan syarat supaya algoritma metode simpleks dapat berjalan. Sebagai usaha agar variabel buatan segera bernilai nol (0), maka disusunlah fungsi tujuan baru dengan bentuk z  z  M x n 1 dimana M adalah bilangan positif yang sangat besar tapi tak terhingga. Dengan demikian diharapkan agar variabel buatan segera keluar dari kolom variabel dasar karena koefisiennya bernilai negatif yang sangat besar. 2.

Minimasi

Fungsi tujuan dari persoalan program linier yang bersifat minimasi harus diubah menjadi maksimasi, agar sesuai dengan bentuk standar, yaitu maksimasi., sehingga dapat diselesaikan dengan menggunakan metode simpleks. Caranya adalah dengan mengganti tanda positif dan negatif pada fungsi tujuan, sebagai berikut :

36 |

Program Linier

BAB 7 METODE BRANCH AND BOUND A.

PENGANTAR

Teknik Branch and Bound merupakan teknik solusi untuk persoalan program linier yang mengharuskan variabelnya berupa bilangan bulat. Prinsip yang mendasari teknik ini adalah bahwa total set solusi yang fisibel dapat dibagi menjadi subset-subset solusi yang lebih kecil. Subset-subset ini selanjutnya dapat dievaluasi secara sistematis sampai solusi yang terbaik ditemukan. Teknik Branch and Bound pada persoalan program linier digunakan bersama-sama dengan metode simpleks. Teknik ini menggunakan suatu diagram yang terdiri dari node dan cabang (branch) sebagai suatu kerangka dalam proses pemerolehan solusi optimal. Masing-masing node memuat solusi program linier relaksasi (program linier yg mengabaikan batas-batas bilangan bulat) sesuai dengan fungsi tujuan dan batasannya. Node pertama akan memuat solusi program linier relaksasi dari persoalan yang diberikan. Node kedua, ketiga, keempat, dan seterusnya memuat solusi program linier relaksasi dari persoalan yang diberikan ditambah dengan batasan yang terdapat pada masing-masing cabangnya. B.

LANGKAH-LANGKAH

Langkah-langkah penggunaan teknik Branch and Bound adalah sebagai berikut : 1. Dapatkan solusi simpleks optimal dari program linier relaksasi yang bersangkutan. 2. Solusi yang dihasilkan pada langkah 1 dinyatakan sebagai batas atas (upper bound) dan pembulatan ke bawah sebagai batas bawah (lower bound) pada node 1. 3. Pilihlah variabel dengan pecahan yang terbesar untuk pencabangan (branch). Ciptakan dua batasan baru untuk variabel ini. Hasilnya adalah sebuah batasan  dan sebuah batasan  . 4. Ciptakan dua node baru, satu dengan batasan  dan satu dengan batasan  .

46 |

Program Linier

BAB 8 MODEL TRANSPORTASI A.

PENGANTAR

Model transportasi pertama kali dikemukakan oleh FL. Hitch Cock pada tahun 1941. Ia menyajikannya dalam studi kasus mengenai The Distribution of Product from Several Sources to Numerous Localities. Metode inilah yang pertama-tama digunakan dalam memecahkan persoalan transportasi, yang kemudian disusul oleh T. C. Koopmans yang pada tahun 1947. Koopmans menerbitkan buku tentang sistem transportasi dengan judul Optimum Utilization of The transportation System. Masalah transportasi adalah bagian dari persoalan program linier yang membahas tentang minimasi biaya transportasi dari suatu tempat ke tempat lain. Istilah transportasi atau distribusi mengandung makna bahwa adanya perpindahan atau aliran barang dan jasa dari suatu tempat ke tempat yang lain. Kita tahu bahwa mendistribusikan barang dari suatu tempat ke tempat yang lain memerlukan alat dan biaya transportasi. Pada dasarnya setiap daerah tujuan dapat menerima komoditas dari sembarang daerah sumber, kecuali ada kendala lainnya. Kendala yang mungkin terjadi adalah tidak adanya jaringan transportasi dari suatu sumber menuju suatu tujuan atau waktu pengangkutan yang lebih lama dibandingkan masa berlaku komoditas. Secara garis besar, persoalan transportasi merupakan suatu masalah pendistribusian suatu komoditas atau produk dari beberapa sumber (supply) ke sejumlah tujuan (destination) dengan tujuan meminimumkan ongkos pengangkutan yang dibutuhkan. Ciri-ciri persoalan transportasi adalah : 1. Terdapat sejumlah sumber dan sejumlah tujuan tertentu 2. Kuantitas komoditas atau barang da...