Makalah Program Linear

Uncategorized 10 Minutes

MAKALAH

PROGRAM LINEAR

Dosen Pengampu

Fitriana Yolanda, M.Pd

Oleh:

NURUL SHAQILA (176410340)

PROGRAM STUDI PENDIDIKAN MATEMATIKA

FAKULTAS KEGURUAN DAN ILMU PENDIKAN

UNIVERSITAS ISLAM RIAU

2019

KATA PENGANTAR

Alhamdulillah,puji beserta syukur kami sampaikan kepada Allah SWT atas rahmat dan karunia-Nya kami dapat menyelesaikan tugas ini yaitu makalah tentang Program Linear.Shalawat beserta salam tak lupa pula kami persembahkan kepada junjungan kita semua yaitu ruh nabi besar Muhammad SAW,semoga kita mendapat syafaatnya di akhirat kelak,amin.

Selanjutnya kami mengucapkan terimakasih kepada dosen pembina yang telah berkenan membimbing kami dalam menyelesaikan makalah ini dengan baik.Karena keterbatasan pengetahuan dan pengaalaman,kami menyadari bahwa makalah ini masih jauh dari kata kesempurnaan,sebab di dalamnya masih banyak terdapat kesalahan dan kekurangan,baik yang kami sengaja maupun yang tidak kami sengaja.

Kritikan dan saran yang membangun sangat kami harapkan untuk memperbaiki makalah kami kedepannya.Demikian yang dapat kami sampaikan semoga makalah ini dapat  menambah pengetahuan dan pengalaman bagi para pembaca.

                                                                                    Pekanbaru, 25 April 2019

                                                                                                     Penulis

DAFTAR ISI

KATA PENGANTAR ……………………………………………………………………………… i

DAFTAR ISI……………………………………………………………………………………………. ii

BAB I PENDAHULUAN…………………………………………………………………………. 1

  1. Latar Belakang………………………………………………………………………………. 1
    1. Rumusan Masalah………………………………………………………………………….. 2
    1. Tujuan Penulisan……………………………………………………………………………. 2

BAB II PEMBAHASAN……………………………………………………………………. ……. 3

  1. Pengertian metode simpleks………………………………………………………………. 3
  2. Metode simpleks dengan menggunakan bentuk baku…………………………… 5

BAB III PENUTUP…………………………………………………………………………… ….. 12

  1. Kesimpulan…………………………………………………………………………………… 12
  2. Saran……………………………………………………………………………………………. 12

DAFTAR PUSTAKA………………………………………………………………………… ….. 13

BAB1

PENDAHULUAN

  1. Latar Belakang

Salah satu pendekatan yang dapat dilakukan untuk menyelesaikan masalah manajemen sains adalah pemograman linear. Pemograman linear merupakan kelompok teknik analisis kuantitatif yang mengandalkan model matematika atau model simbolik sebagai wadahnya. Artinya, setiap masalah yang kita hadapi dalam suatu sistem permasalahan tertentu perlu dirumuskan dulu dalam symbol matematika tertentu, jika kita ingin bantuan pemograman linear sebagai alat analisisnya.

Metode grafik merupakan salah satu metode yang dapat digunakan untuk menyelesaikan masalah pemograman linear yang melibatkan dua peubah keputusan. Membahas mengenai msalah meminimumkan fungsi kendala bertanda >=, fungsi kendala bertanda = t tidak ada penyelsaian layak, tidak ada penyelesaian optimal, beberapa alternative optimal, dan wilayah kelayakan yang tidak terikat dapat terjadi saat menyelesaikan masalah pemrograman linear dengan menggunakan prosedur penyelesaian grafik. Kasus-kasus ini juga dapat terjadi saat menggunakan metode simpleks. Untuk lebih jelaasnya dalam makalah ini penulis akan membahas bagaimana kasus-kasus dapat dikenali dan ditangani saat menggunakan 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 yang dimulai dengan penyelesaian dasar feasible (PDF) dan jika PDF bukan penyelesaian optimal maka akan dicari PDF lain yang lebih baik 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 (i-1).

  • Rumusan Masalah
  • Apa itu Pengertian Metode Simpleks?
  • Bagaimana Cara Menyelesaikan Soal Metode Simpleks Menggunakan Bentuk Baku?
  • Tujuan Penulisan
  • Untuk mengetahui apa pengertian dari metode Simpleks
  • Untuk mengetahui bagaimana cara penyelesaian soal metode simpleks dengan menggunakan bentuk baku

BAB II

PEMBAHASAN

  1. Pengertian Metode Simpleks

Metode simpleks ini adalah metode yang biasanya digunakan untuk  memecahkan setiap permasalahan pada pemrogramman linear yang  kombinasi variabelnya terdiri dari tiga variabel atau lebih, untuk lebih jelasnya mengenai metode simpleks, kita lihat beberapa definisi di bawah ini:

Metode Simpleks adalah Suatu prosedur matematis untuk mencari solusi optimal dari suatu masalah pemrograman linear yang didasarkan pada proses iterasi (Media Anugerah Ayu  1993: 25)

Metode simpleks adalah suatu metode yang secara sistematis dimulai dari suatu penyelesaian dasar yang fisibel ke pemecahan dasar fisibel lainnya, yang dilakukan berulang-ulang (iteratif) sehingga tercapai suatu penyelesaian optimum. (Eddy Herjanto  1999: 191)

Metode simpleks adalah suatu prosedur aljabar, yang melalui serangkaian operasi-operasi berulang, dapat memecahkan suatu masalah yang terdiri dari tiga variabel atau lebih. (T. Hani Handoko  2000: 385)

Ada tiga sifat dari bentuk baku linear programing untuk metode simpleks ini, diantaranya:

  1. Sifat yang pertama adalah semua batasan adalah persamaan (dengan tidak ada nilai negatif pada sisi kanan)
  2. Sifat yang kedua adalah semua variabel tidak ada yang bernilai negatif, dan
  3. Sifat yang ketiga adalah fungsi tujuan dapat berupa minimisasi atau maksimisasi.

Sebelum menyelesaikan  permasalahan dengan menggunakan metode simpleks. Terlebih dahulu masalah tersebut harus diubah kedalam bentuk formulasi model linear programing. Setelah berbentuk suatu model linear programming, maka model tersebut harus diubah terlebih dahulu ke dalam bentuk baku, dimana semua batasan diekspresikan sebagai persamaan dengan menambahkan variabel slack atau surplus sebagaimana diperlukan, maka dapat diterapkan prosedur penyelesaian dengan menggunakan metode simpleks.

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.
    1. 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.
    1. 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).
    1. 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.
    1. 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.
    1. 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.
    1. 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.
    1. 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).
    1. Baris pivot (baris kerja) adalah salah satu baris dari antara variabel basis yang memuat variabel keluar.
    1. Elemen pivot (elemen kerja) adalah elemen yang terletak pada perpotongan kolom dan baris pivot. Elemen pivotakan menjadidasar perhitungan untuk tabel simpleks berikutnya.
    1. Variabel masuk adalah variabel yang terpilih untuk menjadi variabel basis pada iterasiberikutnya. Variabel masuk dipilih satu dari antara variabel non basis pada setiap iterasi. Variabel ini pada iterasi berikutnya akan bernilai positif.
    1. 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 iterasi. Variabel ini pada iterasi berikutnya akan bernilai nol.
  • Metode Simpleks dengan Menggunakan 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.

Beberapa ketentuan yang perlu diperhatikan dalam penyelesaian metode simpleks :

  1. Nilai kanan fungus tujuan harus nol (0).
  2. Nilai kanan fungsi kendala harus positif. Apabila negative, 1.
  3. Fungsi kendalan dengan tanda ≤ harus diubah ke bentuk = dengan menambahkan variabel slack/surplus. Variabel slack/surplus disebut juga variabel dasar. Penambahan slack variabel menyatakan kapasitas yang tidak digunakan atau tersisa pada sumber daya tersebut. Hal ini karena ada kemungkinan kapasitas yang tersedia tidak produksi.
  4. Fungsi kendala dengan tanda ≥ diubah ke bentuk ≤ dengan cara mengkalikan dengan -1, lalu diubah ke bentuk persamaan = dengan ditambahkan variabel slack. Kemudian karena nilai kanan nya negative, dikalikan lagi dengan -1 dan ditambahkan artificial variabel (M). Artificial variabel ini secara fisik tidak mempunyai arti, dan hanya digunakan untuk kepentingan perhitungan saja.
  5. Fungsi kendala dengan tanda = harus ditambah artificial variable.

Contoh soal :

Suatu perusahaan menghasilkan dua produk, meja dan kursi yang diproses melalui dubagian fungsi : perakitan dan pemolesan. Pada bagian perakitan tersedia 60 jam kerja, sedangkan pada bagian pemolesannya hanya 48  jam kerja. untuk menghasilkan 1 meja diperlukan 4 jam kerja perakitan dan 2 jam kerja pemolesan, sedangkan untuk menghasilkan 1 kursi diperlukan 2 jam kerja perakitan dan 4 jam kerja pemolesan. Laba untuk setiap meja dan kursi yang dihasilkan masing-masing 80.000 dan 60.000 . berapa jumlah meja dan kursi yang optimal dihasilkan ?

Penyelesaian :

X1 = jumlah meja yang akan dihasilkan (dalam satuan unit)

X2 = jumlah kursi yang akan dihasilkan (dalam satuan unit)

Perumusan persoalan dalam bentuk tabel:

Proses Waktu yang dibutuhkan per unit Total jam kerja yang tersedia Perakitan
perakitan 4 2 60
Pemolesan 2 4 48
Laba/Unit 80000 60000  

Perumusan fungsi tujuan:

Fungsi Maks:

Laba = Z = 8X1 + 6X2 (dalam satuan Rp 10.000)

Perumusan fungsi kendala:

Dengan kendala ;

1. 4X1 + 2X2 ≤ 60

2. 2X1 + 4X2 ≤ 48

Kendala non negatif X1, X2 ≥ 0

Metode Simpleks Maksimisasi

  1. Menentukan fungsi tujuan dan fungsi-fungsi

kendala Misalkan X1 = Meja dan X2 = Kursi

Fungsi tujuan : Z = 8X1 + 6X2

Fungsi-fungsi kendala :

4X1 + 2X2 ≤ 60

2X1 + 4X2 ≤ 48

  • Mengubah fungsi tujuan dan fungsi-fungsi kendala ke bentuk standar. Bentuk standar simpleks:

Z – 8X1 – 6X2 = 0

4X1 + 2X2 + X3 = 60

2X1 + 4X2 + X4 = 48

Dengan X3 dan X4 adalah variabel slack

  • Membuat tabel simpleks awal
  • Menentukan kolom kunci dan baris kunci sebagai dasar iterasi.
  • Kolom kunci ditentukan oleh nilai Z yang paling kecil (Negatif).
  • Baris kunci ditentukan berdasarkan nilai indeks terkecil.

Cara menentukan indeks =

  • Menentukan nilai elemen cell yaitu nilai perpotongan antara kolom kunci dengan baris kunci
Variabel Dasar Z X1 X2 S1 S2 NK Indeks
Z 1 -8 -6 0 0 0 –
S1 0 4 2 1 0 60 15
S2 0 2 4 0 1 48 24
  • Melakukan iterasi

Dengan menentukan baris kunci baru dan baris baris lainnya termasuk Z.

  • Membuat baris kunci baru

Baris Kunci Baru =

                              Baris Kunci Baru (X1) =

                              X1 = 1   ½    ¼    0    15

Variabel Dasar Z X1 X2 S1 S2 NK
Z            
X1 0 1 0 15
S2            
  • Nilai baris yang lain  = Baris lama – (Nilai baris kunci baru) x angka kolom kunci baris ybs
  • Membuat baris variabel baru

Baris S2 Baru = Baris S2 Lama – (Nilai Kolom Kunci Baris yang sesuai * Baris Kunci Baru)

                              Baris S2 Baru = (2  4  0  1  48) – (2)*(1  ½  ¼  0 15)

                                                      = 0  3  -1/2  1 18

Variabel  Dasar Z X1 X2 S1 S2 NK
Z            
X1 0 1 0 15
S2 0 0 3 – 1 18
  • Membuat baris Z baru

Baris Z Baru = Baris Z Lama – ( Nilai Kolom Kunci Baris yang sesuai * Baris  Kunci Baru)

                        Baris Z Baru = (-8  -6  0  0  0) – (-8)*(1  ½  ¼  0 15)

                                               = 0  -2  2  0 120

Variabel  Dasar Z X1 X2 S1 S2 NK
Z 1 0 -2 2 0 120
X1 0 1 0 15
S2 0 0 3 – 1 18

Lakukan iterasi kembali sampai tidak ada nilai baris Z yang negative

Tabel Simpleks Iterasi-1

Variabel  Dasar Z X1 X2 Slack Variabel NK Indeks
S1 S2
Z 1 0 -2 2 0 120 -60
X1 0 1 0 15 30
S2 0 0 3 – 1 18 6
  • Membuat baris kunci baru

Baris Kunci Baru (X2) =

X2 = 0 1 -1/6  1/3 6

Variabel  Dasar Z X1 X2 Slack Variabel NK
S1 S2
Z            
X1            
X2 0 0 1 – 6
  • Membuat Baris Z baru

Baris Z Baru = (0  -2  2  0  120) – (-2)*(0  1  -1/6  1/3 6)

                       = 0  0  5/3  2/3 132

Variabel  Dasar Z X1 X2 Slack Variabel NK
S1 S2
Z            
X1 0 1 0 – 12
X2 0 0 1 – 6
  • Membuat baris variabel baru

Baris X1 Baru = (1  ½  ¼  0  15) – (1/2)*(0  1  -1/6  1/3 6)

                         = 1  0  1/3  -1/6 12

Tabel Simpleks Iterasi-1

Variabel  Dasar Z X1 X2 Slack Variabel NK
S1 S2
Z 1 0 0 132
X1 0 1 0 – 12
X2 0 0 1 – 6

Hasil:

Karena nilai-nilai pada baris Z sudah tidak ada yang negatif, berarti iterasi selesai, dan solusi yang diperoleh adalah : X1 = Meja = 12, X2 =  Kursi = 6 dan Nilai fungsi tujuan Z (laba) = 132 (dalam puluhan ribu rupiah). Artinya, untuk memperoleh keuntungan yang maksimal sebesar Rp 1.320.000, maka perusahaan sebaiknya memproduksi meja sebanyak 12 unit dan kursi sebanyak 6 unit. Dari tabel tersebut juga diketahui nilai X3 dan X4 tidak ada (X3 dan X4 = 0), artinya seluruh waktu kerja (Perakitan dan Pemolesan) sudah      habis      digunakan, tidak      ada      waktu      yang    tersisa.

BAB III

PENUTUP

  1. Kesimpulan

Metode Simpleks adalah suatu cara yang lazim dipakai untuk menentukan kombinasi optimal dari tigavariabel atau lebih.

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.
    1. Fungsi kendala dengan pertidaksamaan ≥ dalam bentuk umum, dirubah menjadi persamaan (=) dengan mengurangkan satu variabel surplus.

DAFTAR PUSTAKA

Aminudin. 2005. Prinsip-Prinsip Riset Operasi,: Erlangga.

Pangestu, S., Asri, M. dan Handoko, H. 2000. Dasar-Dasar Operation Research: Yogyakarta

Zamit, Y. Manajemen Kuantitatif, BPFE: Yogyakarta

https://id.scribd.com/doc/265217071/metode-simpleks

Unknown's avatar

Published by nurulshaqila

Published

Leave a comment