Makalah LINIER PROGAMMING SOLUSI GRAFIK DAN METODE PRIMAL SIMPLEKS MMING SOLUSI GRAFIK DAN METODE PRIMAL SIMPLEKS

LINIER PROGA LINIER PROGAMMING SOLUSI GRAFIK DAN METODE PRIMAL SIMPLEKS MMING SOLUSI GRAFIK DAN METODE PRIMAL SIMPLEKS

Makalah ini disusun untuk memenuhi tugas
pada Mata Kuliah Operations Research
Dosen Pengampu: Bambang Sri Hartono, S.E., M.Si














Disusun oleh:

1. ARIF RAHMAN HAKIM 2013216003
2. ARIF WAHYU PRABOWO 2013216005
3. MAHARANI DITA A. 2013216008
4. BUDI SEHABUDIN 2013216014
5. MILLATUL KHASANAH 2013216021
6. DAFANA SALSABIYLA 2013216048



PRODI EKONOMI SYARIAH
FAKULTAS EKONOMI DAN BISNIS ISLAM
INSTITUT AGAMA ISLAM NEGERI PEKALONGAN
2018

KATA PENGANTAR

Alhamdulillah, segala puji dan syukur penulis panjatkan kepada Allah SWT atas segala limpahan nikmat, khususnya nikmat iman, Islam, dan juga kesehatan sehingga penulis mampu menyelesaikan makalah ini. Adapun tujuan dari pembuatan makalah ini adalah  untuk memenuhi salah satu tugas mata kuliah Operations Research, yang berjudul “Linier Progamming Solusi Grafik Dan Metode Primal Simpleks”.
Makalah ini akan membahas mengenai pengertian Linier progamming, solusi grafik, serta pengertian metode primal simpleks.
Dalam penyusunan makalah ini, tentunya penulis mengalami beberapa kesulitan seperti dalam mencari sumber data yang sesuai dengan tema. Semua ini tidak akan terlaksana dengan baik, apabila tidak ada bantuan dari berbagai pihak. Oleh karena itu, kami selaku penulis mengucapkan terima kasih kepada seluruh pihak yang telah membantu dalam penyusunan makalah ini.
Penulis menyadari bahwa dalam penyusunan makalah ini masih banyak kekurangan. Oleh karena itu, penulis mengharapkan masukan, kritik, dan saran yang bersifat konstruktif.
Harapan penulis semoga makalah ini dapat bermanfaat bagi para pembaca pada umumnya dan bagi penulis pada khususnya.

Pekalongan, 21 September 2018


Penulis



DAFTAR ISI


KATA PENGANTAR i
DAFTAR ISI ii
BAB I
PENDAHULUAN 1
A. Latar Belakang Masalah 1
B. Rumusan Masalah 2
C. Tujuan Penulisan 2
BAB II
PEMBAHASAN 3
1. Linier Progamming Dalam Riset Operasi..............................................3
2. Solusi Grafik..........................................................................................4
3. Metode Simpleks Primal........................................................................8
BAB III
KESIMPULAN.................................................................................................14
DAFTAR PUSTAKA.......................................................................................16


BAB I
PENDAHULUAN


A. Latar Belakang Masalah
Sejalan dengan perkembangan dunia industry dan didukung dengan kemajuan di bidang computer, Riset Operasi semakin banyak diterapkan di berbagai bidang untuk menangani masalah yang cukup kompleks. Program linier merupakan ilmu terapan yang sangat bermanfaat dan sangat luas pemakaiannya.
Landasan teori yang mendukung akan diberikan setelah teknik penyelesaian dikuasai dengan  baik.  Beberapa  contoh  soal  yang  dapat  pembaca  telusuri untuk lebih memahami teori yang dibaca. Selanjutnya diberikan soal- soal beserta penyelesaiannya untuk ditelusuri sebagai latihan, dengan harapan pembaca dapat menguasai materi yang dipelajari.
Program  linier  dapat  diselesaikan  dengan  beberapa  cara. Cara yang paling umum adalah dengan menggunakan metode grafik. Metode grafik hanya efektif digunakan apabila banyaknya variabel pada program linier hanya dua. Jika  banyaknya variabel lebih dari dua misalnya ada tiga variabel, maka metode grafik tidak efektif lagi.
Metode simpleks diperkenalkan oleh George Dantzig yang merupakan salah  satu  metode  untuk  mencari  solusi  masalah  program  linear  dengan banyak variabel keputusan. Program linear sendiri merupakan suatu model permasalahan dengan menggunakan persamaan atau pertidaksamaan yang berbentuk linear.
Model program linear memuat dua fungsi yaitu fungsi tujuan (objective function) dan fungsi kendala (constraint function). Fungsi tujuan merupakan fungsi linear mengenai  permasalahan  yang akan dicari solusi optimalnya, contohnya adalah fungsi keuntungan. Sementara fungsi kendala merupakan fungsi linear yang menyatakan batasan-batasan yang harus dipenuhi dalam mencapai solusi optimal, contohnya adalah batasan kapasitas yang tersedia dalam berbagai kegiatan yang akan dialokasikan secara optimal.

B. Rumusan Masalah
Berdasarkan latar belakang permasalahan tersebut, maka dapat dikemukakan rumusan masalah sebagai berikut.
1. Bagaimana cara mengetahui Linier Progamming Dalam Riset Operasi ?
2. Bagaimana cara mengetahui Solusi Grafik ?
3. Bagaimana cara mengetahui Metode Simpleks Primal ?
C. Tujuan Penulisan
Berdasarkan rumusan masalah tersebut, tujuan penulisan makalah ini adalah sebagai berikut :
1. Mengetahui Linier Progamming Dalam Riset Operasi.
2. Mengetahui Solusi Grafik
3. Mengetahui Metode Simpleks Primal.













BAB II
PEMBAHASAN


1. Linier Progamming dalam Riset Operasi
Program Linear (PL) adalah suatu pendekatan matematis untuk menyelesaikan suatu permasalahan agar didapatkan hasil yang optimal. Permasalahan yang sering diselesaikan dengan Linear Programming adalah dalam pengalokasian factor-faktor produksi yang terbatas jumlahnya terhadap berbagai kemungkinan produksi sehingga didapatkan manfaat yang optimal (maksimal dan minimal). Sasaran maksimal, misalnya secara efisien sehingga manfaat yang ingin dicapai (jumlah produksi/nilai penjualan/laba, dan lain-lain) menjadi maksimal.  Sasaran minimal misalnya, bagaimana mencari kombinasi produksi agar penggunaan faktor-faktor produksi minimal tetapi manfaat yang dicapai (dari kombinasi produksi) tidak lebih rendah dari angka yang diinginkan.
a. Arti dan fungsi program linier.
Linier programming adalah alat analisis atas masalah yang mempunyai variabel-variabel bersifat deterministik terukur dan masing-masing mempunyai hubungan linier satu sama lain. Linier programing(LP) merupakan alat analisis yang menunjang keberhasilan riset operasi dalam memecahkan berbagai masalah sehingga dapat diambil suatu keputusan yang tepat.
b. Model dua variabel (MDV)
Model dua variabel merupakan bentuk p yang paling sederhana, dinama masalah yang akan dipecahkan hanya mempunyai dua parametrik yang deterministik (terukur) . dikarenakan hanya memiliki 2 variabel sehingga dapat digambarkan secara grafik. Untuk rekontruksi model LP ini perlu diperhatikan 3 hal sebagai berikut:
- Tujuan pemecahan masalah yang diformulasikan dalam fungsi tujuan.
- Mengamati variabel-variabel yang terdapat dalam masalah tersebut.
- Kendala yang membatasi variabel-variabel tersebut harus ditentukan sehingga diperoleh suatu kondisi yang optimum. Hal ini untuk memformulasikan fungsi-fungsi kendala.

2. Solusi Grafik
Sebagaimana yang telah dikemukakan bahwa program linier yang  melibatkan  hanya  dua  variabel  dapat  diselesaikan  dengan metode grafik. Berikut ini diberikan contoh soal untuk menjelaskan hal tersebut :
Seorang ibu rumah tangga mempunyai 2 jenis bahan baku untuk membuat 2 macam kue, yakni karamel dan lapis legit. Kedua bahan baku tersebut adalah 12 kg terigu dan 15 kg telur. Harga lapis legit adalah Rp. 50.000 per loyang sedangkan karamel Rp. 30.000 per  loyang. Anda sebagai mahasiswa ekonomi dimintai tolong untuk memecahkan masalah berikut : “ berapa jumlah karamel dan lapis legit yang dapat dibuat sekaligus agar penghasilan tambahan ibu tersebut optimum atau sebesar-besarnya?”
Untuk memecahkan masalah tersebut anda harus membuat model pemecahannya, diawali dengan membuat gambaran sistemmatikanya sebagai berikut :
a. Tujuan : untuk membuat fungsi tujuan
b. Kendala : untuk membuat fungsi kendala

Menurut resep misalnya diketahui bahwa untuk membuat karamel diperukan 2 kg terigu dan 1 kg telur segangkan untuk lapis legit diperukan 1 kg terigu dan 2 kg telur. Berdasarkan data yang tersedia anda dapat membuat bagan matriks sebagai berikut :

Jenis bahan
Lapis legit
karamel Jumlah maksimum bahan
Terigu 1kg 2kg 12kg
Telur 2kg 1kg 15kg

Tujuannya menjual kedua kue tersebut, yakni Rp. 50.000 kali jumlah lapis legit ditambah Rp. 30.000 kali jumlah karamel agar perolehan laba ibu maksimal. Selanjutnya kita dapat membuat modeo matematikanya dengan cara berikut fungsi tujuannya : 50 lapis legit ) tambah 30 karamel (k)→ maksimum
Fungsi kendala
Bahan terigu : 1ll + 2k ≤ 12
Bahan telur : 2ll +1k ≤ 15
   ≥ 0, k ≥ 0 (artinya lapis legit dan karamel lebih besar atau sama dengan nol)
1. Penyelesaian masalah dengan cara matematis dan grafis
a. Penyelesaian secara matematis
Fungsi kendala dianalisis dengan cara eliminasi sehingga jumlah ll maupun k dapat mudah dihitung.
1ll + 2k ≤ 12    ×2    2ll + 4k ≤ 24
2ll + 1k ≤ 15    ×1    2ll + 1k ≤ 15
           3k ≤ 9
K ≤ 3

1ll + 2k ≤ 12
1ll + 2 × 3 ≤ 12
1ll + 6 ≤ 12
1 ll ≤ 12–6
1ll  ≤ 6
Jadi penghasilan optimum  yang diperoleh ibu adalah 6 × Rp 50000 + 3 × Rp 30000 = Rp 390000
b. Penyelesain secara grafis

     k
15
14
13
12 Kurva telur
11
10
9
8
7
6 Q Titik kombinasi optimum
5
4
3 M     Kurva terigu
2
1
0             N                  
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 16  17            ll
7,5
2. Analisis sensitivitas
Analisis sensitivitas adalah analisis yang bertujuan untuk mengamati kemungkinan terjadinya perubahan parameter. Sebab dengan berubahnya parameter dapat mengakibatkan berubahnya hasil optimasi. Parameter yang dapat berubah adalah harga jual produk : persediaan bahan, baik terigu atau telur.
Harga jual lapis legit dan karamel berubah menjadi Rp 100000 dan Rp 75000 per loyang. Karena permintaan meningkat ibu sebagai produsen memperoleh tambahan modal sehingga persediaan terigu dan telur menjadi 3 kali lipat. Persediaan terigu menjadi 36 kg sedangkan persedian telur menjadi 45kg.
Fungsi tujuan : Rp 10000 ll + Rp 75000 k → maksimum
Fungsi kendaan : terigu : 1ll + 2k ≤ 36
Telur : 2ll + 1k ≤ 45
a. Penyelesaian secara matematis
1ll + 2k ≤ 36 ×2   2ll + 4k ≤ 72
2ll + 1k ≤ 45    ×1   2ll + 1k ≤ 45
          3k ≤ 27
       k ≤ 27/3 = 9 unit
1ll + 2k ≤ 36
1ll + 2(9) ≤ 36
1ll + 18 ≤ 36
1ll ≤ 36 – 18
1ll ≤ 18 unit
Jadi tujuan berubah menjadi : 18 (100.000) +  9 (75.000) =2.475.000
b. Analisis grafis
      k
45
40
35 kurva telur
30
25
20 Q
15
10      M                 kurva terigu
5
0  N
        10 18   20       25       30       36       40        ll
22,5
2. Metode Simplex Primal
Metode simpleks adalah metode yang dapat digunakan untuk menyelesaikan persoalan manajerial yang telah diformulasikan terlebih dahulu ke dalam persamaan matematika program linear yang mempunyai variable keputusan mulai dari lebih besar atau samadengan 2 (dua) sampai multivariable.  Sedangkan metode grafik hanya dapatdigunalan apabila jumlah variable keputusan maksimal 2 (dua) buah. Sehingga dapat disimpulkan bahwa suatu persoalan linear programing yang diselesaikan denganmetode grafik juga dapat diselesaikan dengan metode simpleks, sebaliknya suatu persoalan yang hanya bisa diselesaikan dengan metode simplex tidak dapat diselesaikan dengan metode grafik.
Metode simplex primal bertolak dari upaya membuat solusi dengan cara optimal dari masalah yang telah dibahas dalam bab sebelumnya, bukan dengan cara matematika atau grafis. Berdasarkan metode grafis, seperti contoh dalam gambar 2.1, titik kombinasi optima dicapai  pada titik M, dilanjutkan dengan analisis sensivitas (gambar 2.2) dimana titik M telah berubah karena parameternya berubah.
Contoh soal:
Suatu perusahaan mempunyai masalah yang dinyatakan dalam bentuk linear programming (LP) sebagai berikut
Fungsi tujuan : 50 ll + 30k (maksimum)
Fungsi kendala : terigu : 1ll + 2k kurang dari 12
   Telur : 2 ll + 1k kurang dari 15
Menurut kenyataan hidup kapasitas mesin selalu mempunyai sisa kapasitas yang tidak terpakai. Mengapa? Karena memang demikianlah yang terjadi. Misalnya anda memiliki 2meter kain untuk dijadikan baju kemeja dengan ukuran badan anda. Lalu anda meminta ke tukang jahit supaya tidak ada sisa kain sedikitpun. Tentu saja tukang jahit tersebut akan menolak, karena kain tersebut harus dipotong sehingga akan ada sisa kain yang terbuang.
Kembali pada soal diatas, baik bahan baku telur (tl) atau terigu (tr) akan mempunyai sisa yang terbuang. Sisa telur disingkat Stl dan sisa terigu disingkat Str.  
Jawaban :
Terigu  : 1ll + 2k ≤ 12 berubah menjadi 1 ll + 2k + Stg = 12
Telur : 2 ll + 1k ≤ 15 berubah menjadi 2 ll + 1k + Stl = 15
Agar kedua fungsi tadi dapat disatukan (diintegrasikan) dalam 1 matriks maka kedua fungsi harus mempunyai variabel dan parameter yang sama.
Fungsi terigu mempunyai variabe ll, k, dan Stg, tetapi belum mempunyai variabel sisa telur (Stg). Ingat, sesuatu hal atau bilangan  ditambah angka nol maka nilainya tidak berubah. Jadi:
Terigu : 1 ll + 2k + 1Stg + 0 Stl =12
Begitu pula fungsi telur, mempunyai variabel ll,k, dan Stl, tetapi belum mempunyai variabel sisa terigu (Stg), dan jika tambahkan menjadi:
Telur : 2 ll +1 k + 0 Stg + 1 Stl = 15
Analog untuk fungsi  tujuan, ditambahkan 0 Stl  dan 0 Stg :
50 ll + 30 k + 0 Stg  + 0 Stl (nilainya tetap karena ditambah nol)
Selanjutnya untuk memudahkan penulisan agar lebih sederhana, ll kita ubah menjadi x1 sedangkan k kita ubah menjadi x2 lalu Stg kita ubah menjadi S1 sedang Stl kita ubah menjadi  S2, maka kita peroleh hal berikut.
Fungsi tujuan : 50x1 + 30 x2  + 0 S2  maksimum
Fungsi kendala : Terigu : x1 + 2x2 + 1 S1 + 0 S2 = 12
   Telur : 2x + x2  + 0 S1 + 1 S2 = 15
a. Format Matriks Simplex Primal
Sebelum melanjutkan hal tersebut diatas, kiranya perlu terebih dahulu diketahui bentuk format matriks simplex primal, yaitu terdiri dari berikut ini.
1. Baris yang disebut basic atau baris yang memuat semua variabel yang dimiliki seluruh fungsi-fungsi persamaan (equation).
2. Baris tujuan  (objective) dengan simbol Z untuk menampung angka-angka yang terdapat pada fungsi tujuan.
3. Baris untuk semua fungsi persamaan kendala, yakni untuk menampung angka-angka yang dimiliki seluruh fungsi kendala.
Bentuknya adalah sebagai berikut:

Baris
Z
Variabel
Solusi Kolom indeks
Z Persamaan tujuan
 Beberapa
  persamaan
  kendala


Baris indeks
b. Contoh Analisis Simpex Primal
Mari kita masukkan (entry) semua angka-angka pada fungsi tujuan maupun fungsi-fungsi kendala dari masalah di atas. Masukkan setiap angka fungsi tujuan, maupun fungsi kendala sesuai kontak (sel) pada kolom masing-masing. Misalnya, angka 50 dari fungsi tujuan dimasukkan pada kolom x1, angka 30 pada kolom x2, dan seterusnya. Matriks tabel 3.2 ini disebut Model Reddy Mikks, yaitu cara menghitung secara rinci dalam primal simplex (PS).
(1) (2) (3) (4) (5) (6) (7) (8)
keterangan
Baris Z X1 X2 S1 S2 solusi Kolom indeks
Z 1 50 30 0 0 0 Persamaan tujuan
S1 0 1 2 1 0 12 Persamaan kendala S1
S2 0 2 1 0 1 15 Persamaan kendala S2
Baris indeks
Bila semua angka telah dimasukkan ke dalam matriks -1/PS selanjutnya matriks -1/PS tersebut harus diproses lebih lanjut, yakni denga mengisi atau menghitung angka pada setiap kolom pada baris indeks. Caranya sebagai berikut.
1. Perhatikan angka-angka (dari variabel x1, x2, S1, S2). Angka-angka tersebut terpisah satu sama lain dengan dibatasi kolom misalnya dalam sel (S1, x1).
2. Perhatikan angka-angka dalam kolom Z, tetapi hanya untuk baris S1 dan S2 dalam sel (S1, Z) dan (S2, Z ) masing-masing terdapat angka 0 (nol). Sebut saja angka-angka tersebut sebagai angka konstanta (dalam kolom Z).
3. Rumus angka baris indeks adalah
Angka baris indeks = (Ʃ angka dalam kolom variabel × konstanta                 dalam kolom Z) – masing-masing angka dalam kolom objektif)

Contoh angka baris indeks untuk kolom (3)
Angka pada sel ( S1,S) x angka pada sel (S1,x1) + angka pada sel (S2,Z) × angka pada sel (S2,x1) – angka pada sel (Z,x1)
= (0×1) × (0×2) – 50 = –50 (kolom 3)

Kolom 4
Angka sel  (S1, Z) × (S1,x2) + (S2,Z) × (S2,X2) – sel (Z,x2)
= (0×2) + (0×1) – 30 = –30
Kolom 5
= (0×1) + (0×1) – 0 = 0
Kolom 6
= (0×0) + (0×1) = 0

4. Mencari kolom kunci ( KK )
Diantara angka –50, –30, 0, dan 0, angka terkecil adalah –50. Oleh karena itu, kolom (3) yang mempunyai angka baris indeks –50 merupakan kolom kunci (Key Column).

(1) (2) (3) (4) (5) (6) (7) (8)
keterangan
Baris Z X1 X2 S1 S2 solusi Kolom indeks
Z 1 50 30 0 0 0
S1 0 1 2 1 0 12 12/1 = 12
S2 0 2 1 0 1 15 15/2 = 7,5

Baris indeks –50 –30 0 0

Baris kunci
Kolom kunci

5. Menentukan baris kunci (Key Row).
Untuk menentukan baris kunci (Key Row) kita harus menghitung terlebih dahulu angka-angka yang terdapat dalam kolom indeks ( kolom nomor 8).
 Angka kolom indeks = angka dalam sel (S1, solusi) dan sel (S2, solusi)    dibagi dengan angka yang terdapat daam kolom kunci pada masing-masing baris.
Cara menghitungnya adalah sebagi berikut
Angka 12/1 = 12
Angka 15/2 = 7,5

6. Menentukan angka kunci
Perpotongan antara kolom kunci (Key Column) dengan baris kunci ( Key Row) merupakan angka kunci (Key  Number), yakni angka 2.

Dalam model Reddy Mikks, semua batasan adalah <. Sifat ini, bersamaan dengan fakta bahwa sisi kanan dari semua batasan adalah nonnegatif, memberikan kita pemecahan dasar awal yyang layak yang terdiri dari semua variabel slack. Kondisi seperti ini tidak dipenuhi oleh semua model Linier Progamming, sehingga menimbulkan kebutuhan untuk merancang sebuah prosedur perhitungan otomatis untuk memulai iterasi simpleks.

 
BAB III
KESIMPULAN


Program linier merupakan ilmu terapan yang sangat bermanfaat dan sangat luas pemakaiannya. Permasalahan yang sering diselesaikan dengan Linear Programming adalah dalam pengalokasian factor-faktor produksi yang terbatas jumlahnya terhadap berbagai kemungkinan produksi sehingga didapatkan manfaat yang optimal (maksimal dan minimal). Sebagaimana yang telah dikemukakan bahwa program linier yang  melibatkan  hanya  dua  variabel  dapat  diselesaikan  dengan metode grafik.
Model program linear memuat dua fungsi yaitu fungsi tujuan (objective function) dan fungsi kendala (constraint function). Fungsi tujuan merupakan fungsi linear mengenai  permasalahan  yang akan dicari solusi optimalnya, contohnya adalah fungsi keuntungan. Sementara fungsi kendala merupakan fungsi linear yang menyatakan batasan-batasan yang harus dipenuhi dalam mencapai solusi optimal, contohnya adalah batasan kapasitas yang tersedia dalam berbagai kegiatan yang akan dialokasikan secara optimal.
Metode simpleks diperkenalkan oleh George Dantzig yang merupakan salah  satu  metode  untuk  mencari  solusi  masalah  program  linear  dengan banyak variabel keputusan. Program linear sendiri merupakan suatu model permasalahan dengan menggunakan persamaan atau pertidaksamaan yang berbentuk linear.
Sehingga dapat disimpulkan bahwa suatu persoalan linear programing yang diselesaikan denganmetode grafik juga dapat diselesaikan dengan metode simpleks, sebaliknya suatu persoalan yang hanya bisa diselesaikan dengan metode simplex tidak dapat diselesaikan dengan metode grafik.
Analisis sensitivitas adalah analisis yang bertujuan untuk mengamati kemungkinan terjadinya perubahan parameter. Sebab dengan berubahnya parameter dapat mengakibatkan berubahnya hasil optimasi.
Dalam model Reddy Mikks, semua batasan adalah <. Sifat ini, bersamaan dengan fakta bahwa sisi kanan dari semua batasan adalah nonnegatif, memberikan kita pemecahan dasar awal yyang layak yang terdiri dari semua variabel slack. Kondisi seperti ini tidak dipenuhi oleh semua model Linier Progamming, sehingga menimbulkan kebutuhan untuk merancang sebuah prosedur perhitungan otomatis untuk memulai iterasi simpleks.
 
DAFTAR PUSTAKA


Prawirosentono, Suyadi. Riset Operasi. 2005.  Jakarta: PT Bumi Aksara
Sumber: http://abdullahbasuki.files.wordpress.com/2010/03/ro-2 pengenalan riset operasional1.ppt diakses tanggal 20 September 2018
Sumber:http://www.academia.edu/3449276/Program Linear dengan Metode Simplex diakses tanggal 20 September 2018
Syahputra, Edi.  Program Linier. 2015. Medan: Unimed Press.
Taha, Hamdy A. Riset Operasi. Tangerang: Binarupa Aksara.