MAKALAH

LINEAR PROGRAMMING : METODE GRAFIK DAN METODE SIMPLEKS

Diajukan untuk pemenuhan tugas mata kuliah ekonomi teknik

Disusun Oleh :

Cahyaningtyas

Wilda Ningrum R

Bagas Pumbarino 4312100077

Satrio Agi Nugroho

M. Yusuf Jamil

JURUSAN TEKNIK KELAUTAN

FAKULTAS TEKNOLOGI KELAUTAN

INSTITUT TEKNOLOGI SEPULUH NOPEMBER

2015

DAFTAR ISI

DAFTAR ISI...............................................................................................................................i

BAB 1 PENDAHULUAN.........................................................................................................2

1. Latar Belakang................................................................................................................2

2. Rumusan Masalah...........................................................................................................2

3. Tujuan.............................................................................................................................2

BAB 2 PEMBAHASAN............................................................................................................3

1. PEMOGRAMAN LINEAR............................................................................................3

1. 1 Pengertian Pemograman Linear...............................................................................3

1. 2 Karakteristik Pemograman Linear...........................................................................4

1. 3 Formulasi Model Matematika..................................................................................4

2. METODE SIMPLEKS....................................................................................................6

2. 1 Pengertian Metode Simpleks...................................................................................6

2. 2 Beberapa Istilah dalam Metode Simpleks...............................................................6

2. 3 Bentuk Baku............................................................................................................7

2. 4 Langkah – Langkah Penyelesaian............................................................................8

BAB 3 PENUTUP....................................................................................................................12

1. Kesimpulan...................................................................................................................12

i

BAB 1 PENDAHULUAN

1. Latar BelakangSalah satu pendekatan yang dapat dilakukan untuk menyelesaikan masalah

manajemen sains adalah pemrograman linear. Pemrograman 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 simbol-simbol matematika tertentu, jika kita inginkan bantuan pemrograman linear sebagai alat analisisnya.

Metode simpleks merupakan salah satu teknik penentuan solusi optimal yang digunakan dalam pemrograman linier. Penentuan solusi optimal didasarkan pada teknik eliminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim (ingat solusi grafik) satu persatu denagan cara perhitungan interatif. Sehingga penentuan solusi optimal dengan simpleks dilakukan dengan thap demi tahap yang disebut interasi.Perbedaan kedua metode diatas sangat jelas, bahwa metode grafik hanya mampu digunakan untuk dua kendala saja. Namun metode simpleks mampu menyelesaikan masalah dengan lebih dari dua kendala. Itu artinya metode simpleks memiliki minimal tiga kendala didalamnya.

Pada makalah ini, kami akan membahas mengenai pemograman linear dan metode simpleks, yang kemudian diaplikasikan dalam penyelesaian studi kasus yang diberikan.

2. Rumusan MasalahAdapun rumusan masalah yang akan kami bahas pada makalah ini adalah1. Bagaimana karakteristik dan model matematis dari pemograman linear ?2. Bagaimana penyelesaian salah satu kasus menggunakan pemograman linear ?3. Bagaimana langkah-langkah penyelesaian dalam metode simpleks ?4. Bagaimana penyelesaian salah satu kasus dengan menggunakan metode simpleks ?

3. TujuanAdapun tujuan dari pembuatan makalah ini adalah untuk menyelesaikan suatu kasus dengan menggunakan pemograman linear dan metode simpleks dengan langkah-langkah yang sistematis.

2

BAB 2 PEMBAHASAN

1. PEMOGRAMAN LINEAR

1. 1 Pengertian Pemograman Linear

Pengertian pemograman linear menurut para ahli :

a. George B. Dantzig (1947)

Linear programming merupakan pengembangan lebih lanjut dari konsep-konsep aljabar linear.

b. Nasedi dan Anwar (1985) dalam Tarmizi (2005)

Linear Programming adalah salah satu teknis analisis dari kelompok teknik riset operasional yang menggunakan model matematik. Tujuannya adalah untuk mencari, memilih dan menentukan alternatif yang terbaik dari antara sekian alternatif grafis dan metode analisis secara aljabar (metode simpleks).

c. Sofjan Assauri (1999)

Linear Programing merupakan suatu teknik perencanaan yang menggunakan model matematika dengan tujuan menemukan kombinasi-kombinasi produk yang terbaik dalam menyusun alokasi sumber daya yang terbatas guna mencapai tujuan yang digunakan secara optimal.

d. Sri Mulyono (2002)

Linear Programing merupakan suatu teknik perencanaan yang menggunakan model matematika dengan tujuan menemukan kombinasi-kombinasi produk yang terbaik dalam menyusun alokasi sumber daya yang terbatas guna mencapai tujuan yang digunakan secara optimal.

e. Siringoringo (2005)

Pemrograman Linear merupakan metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. Pemrograman Linear banyak diterapkan dalam masalah ekonomi, industri, militer, sosial dan lain-lain. Pemrograman Linear berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linear dengan beberapa kendala linear.

Secara umum, pengertian dari pemograman linear adalah metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. PL banyak diterapkan dalam masalah ekonomi, industri, militer, social dan lain-lain. PL berkaitan dengan penjelasan suatu

3

kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier.

1. 2 Karakteristik Pemograman Linear

Karakteristik persoalan dalam program linier adalah sebagai berikut :

Ada tujuan yang ingin dicapai

Tersedia beberapa alternatif untuk mencapai tujuan

Sumberdaya dalam keadaan terbatas

Dapat dirumuskan dalam bentuk matematika (persaman/ketidaksamaan)

1. 3 Formulasi Model Matematika

Masalah keputusan yang sering dihadapi analis adalah mengalokasikan secara optimum keterbatasan/kelangkaan sumber daya dapat berupa uang, tenaga kerja, bahan mentah, kapasitas mesin, waktu, ruang atau teknologi. Tugas analisis adalah mencapai hasil terbaik yang mungkin dengan keterbatasan sumber daya itu. Hasil yang diinginkan mungkin ditunjukan sebagai maksimasi dari beberapa ukuran profit, penjualan dan kesejahteraan, atau minimasi pada biaya, waktu dan jarak. Masalah optimasi ini dapat diselesaikan dengan program linear.

Langkah-langkah dalam penyusunan model program linier adalah sebagai berikut :

Definisikan Variabel Keputusan (Decision Variable)

Variabel yang nilainya akan dicari

Rumuskan Fungsi Tujuan:

1. Maksimisasi atau Minimisasi z = c1x1 + c2x2 + … + cnxn

2. Tentukan koefisien dari variabel keputusan

Simbol x1, x2, …, xn (xi) menunjukkan variabel keputusan.

Simbol c1,c2,…,cn merupakan koefisien fungsi tujuan pada model matematiknya

Rumuskan Fungsi Kendala Sumber daya:

1. Tentukan kebutuhan sumberdaya untuk masing- masing peubah keputusan.

2. Tentukan jumlah ketersediaan sumberdaya sbg pembatas.

a11x1 + a12x2 + … + a1nxn = /≤ / ≥ b1

a21x1 + a22x2 + … + a2nxn = /≤ / ≥ b2

…

am1x1 + am2x2 + … + amnxn = /≤ / ≥ bm

x1, x2, …, xn ≥ 0

Simbol a11, …,a1n,…,amn merupakan koefisien fungsi kendala pada model matematiknya

4

Simbol b1,b2,…,bm menunjukkan jumlah masing-masing sumber daya yang ada

Tetapkan kendala non-negatif

Setiap keputusan (kuantitatif) yang diambil tidak boleh mempunyai nilai negatif.

Contoh Kasus

Suatu perusahaan menghasilkan dua produk, meja dan kursi yang diproses melalui duabagian fungsi : perakitan dan pemolesan. Pada bagian perakitan tersedia 60 jam kerja, sedangkan pada bagian pemolesan hanya 48 jam kerja. Untuk menghasilkan 1 meja diperlukan 4 jam perkitan 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 Rp. 80.000 dan Rp. 60.000,-

Berapa jumlah meja dan kursi yang optimal dihasilkan ?

Penyelesaian:

Definisi variabel keputusan:

Keputusan yang akan diambil adalah berapakah jumlah meja dan kursi yg akan dihasilkan. Jika meja disimbolkan dengan X1 dan kursi dengan X2, maka definisi variabel keputusan :

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

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

PROSES Waktu yang dibutuhkan per unit Total jam tersediaMeja Kursi

Perakitan 4 2 60Pemolesan 2 4 48Laba per unit 80000 60000

Perumusan fungsi tujuan:

Laba untuk setiap meja dan kursi yg dihasilkan masing- masing Rp. 80.000 dan Rp. 60.000. tujuan perusahaan adalah untuk memaksimumkan laba dari sejumlah meja dan kursi yang dihasilkan . dengan demikian, fungsi tujuan dapat ditulis

Fungsi Maks.:

Laba = 80.000 Meja + 60.000 kursi

Z = 8X1 + 6X2 (dalam Rp 10.000,-)

Perumusan fungsi kendala:

Dengan kendala:

5

4X1 + 2X2 ≤60

2X1 + 4X2 ≤48

Kendala non-negatif:

Meja dan kursi yang dihasilkan tidak memiliki nilai negatif.

X1 ≥ 0

X2 ≥ 0

2. METODE SIMPLEKS

2. 1 Pengertian Metode Simpleks

Beberapa definisi metode simpleks menurut para ahli :

a. Media Ayu Anugerah (1999)

Metode Simpleks adalah Suatu prosedur matematis untuk mencari solusi optimal dari suatu masalah pemrograman linear yang didasarkan pada proses iterasi.

b. Eddy Herjanto (1999)

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.

c. T. Hani Handoko (2000)

Metode simpleks adalah suatu prosedur aljabar, yang melalui serangkaian operasi-operasi berulang, dapat memecahkan suatu masalah yang terdiri dari tiga variabel atau lebih.

Secara singkat, metode simpleks adalah merupakan salah satu teknik penentuan solusi optimal yang digunakan dalam pemrograman linier. Penentuan solusi optimal didasarkan pada teknik eliminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim (ingat solusi grafik) satu persatu denagan cara perhitungan interaktif. Sehingga penentuan solusi optimal dengan simpleks dilakukan dengan thap demi tahap yang disebut iterasi.

Jadi sangat jelas perbedaannya dengan pemograman linear biasa (metode grafis), bahwa metode grafik hanya mampu digunakan untuk dua kendala saja. Namun metode simpleks mampu menyelesaikan masalah dengan lebih dari dua kendala. Itu artinya metode simpleks memiliki minimal tiga kendala didalamnya.

2. 2 Beberapa Istilah dalam Metode Simpleks

Ada beberapa istilah yang sangat sering digunakan dalam metode simpleks, diantaranya :a) Iterasi adalah tahapan perhitungan dimana nilai dalam perhitungan itu tergantung

dari nilai tabel sebelumnya.

6

b) 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.

c) 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).

d) 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.

e) 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.

f) 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.

g) 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.

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

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

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

k) 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.

l) Variabel keluar adalah variabel yang keluar dari variabel basis pada iterasi berikutnya dan digantikan oleh variabel masuk. Variabel keluar dipilih satu dari

7

antara variabel basis pada setiap iiterasi. Variabel ini pada iterasi berikutnya akan bernilai nol.

2. 3 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 :

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

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

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

2. 4 Langkah – Langkah Penyelesaian

Dalam menyelesaikan masalah linear programming, dilakukan perhitungan iterasi dengan menggunakan table. Tabel awal yang dibuat berdasarkan model baku matematika yang ada dinamakan Tabel Awal Simpleks selanjutnya dilakukan perhitungan iterasi. Untuk menyelesaikan contoh kasus pada bagian sebelumnya, Tahap-tahap dalam metode simpleks adalah yaitu :

1. Menentukan fungsi tujuan dan fungsi-fungsi kendala

Misalkan x1 = Meja dan x2 = Kursi

Fungsi Tujuan : Z = 8x1 + 6x2

Fungsi-fungsi Kendala:

4 x1 + 2 x2≤60

2x1 + 4 x2 ≤ 48

2. Mengubah fungsi tujuan dan fungsi kendala ke bentuk baku

Bentuk Baku Simpleks:

Z−8 x1−6 x2=0

8

4 x1+2 x2+x3=60

2 x1+4 x2+x 4=48

Dengan x3 dan x4 adalah variabel slack.

3. Membuat tabel simpleks awalMenentukan 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 = Nilai kanan(NK )Kolomkunci(KK )

Menentukan nilai elemen cell yaitu nilai perpotongan antara kolom kunci de

ngan baris kunci.

Langkah-langkah di atas disajikan pada tabel simpleks berikut ini.

Tabel 1 : Tabel Awal Simpleks

Variabel dasar

Z X1 X2 Slack Variabel Nilai Kanan

IndeksX3 X4

Z 1 -8 -6 0 0 0 0X3 0 4 2 1 0 60 15X4 0 2 4 0 1 48 24

4. Melakukan Iterasi

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

Membuat baris kunci baru

baris kunci baru=baris kunci lamaelemen cell

baris kunci baru ( x1 )=[ 4 2 1 0 60 ]

4

¿ [1 12

14

0 15]Membuat baris Z baru

baris Z baru=baris Z lama−¿

Baris Z baru= [−8 −6 0 0 0 ]−(−8 )[1 12

14

0 15]= [0 −2 2 0 120 ]

9

Membuat baris variabel baru

Baris x4 Baru = Baris x4 Lama – (Nilai Kolom Kunci Baris yang Sesuai* Baris Kunci Baru)

Baris x4 Baru = [ 2 4 0 1 48 ]−2[1 12

14

0 15]¿ [0 3

−12

1 18]Baris kunci baru (x1), baris Z baru, baris x4 baru, nilai-nilainyaa disajikan pada tabel simpleks berikut. Tabel simpleks ini adalah tabel simpleks hasil iterasi pertama.

Tabel 2 : Tabel Simpleks hasil iterasi 1

Variabel dasar

Z X1 X2 Slack Variabel Nilai Kanan

IndeksX3 X4

Z 1 0 -2 2 0 120 -60X1 0 1 ½ ¼ 0 15 7,5X4 0 0 3 ½ 1 18 6

5. Lakukan Iterasi Kembali sampai tidak ada nilai baris Z yang negatif.

 Membuat baris kunci baru

Baris Kunci baru (x2) = [0 312

1 18]3

¿ [0 116

13

6 ] Membuat baris Z baru

baris Z baru=[ 0 −2 2 0 120 ]−(−2)[0 116

13

6]¿ [0 0

53

23

132]Membuat baris variabel baru

Baris x1 baru=[1 12

14

0 15]−12 [0 1

16

13

6]¿ [1 0

13

−16

12]

10

Baris kunci baru (x2), baris Z baru, baris (x1) baru,nilai-nilainya disajikan pada tabel

simpleks berikut. Tabel simpleks ini adalah tabel simpleks iterasi kedua.

Tabel 3 : Tabel Simpleks hasil iterasi 3

Variabel dasar

Z X1 X2 Slack Variabel Nilai KananX3 X4

Z 1 0 0 5/3 2/3 132X1 0 1 0 1/3 -1/6 12X2 0 0 1 -1/6 1/3 6

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 maksimum 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.

11

BAB 3 PENUTUP

1. Kesimpulan

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 sama dengan

2 (dua) sampai multivariable. Sedangkan metode grafik hanya dapat digunalan apabila

jumlah variable keputusan maksimal 2 (dua) buah. Sehingga dapat disimpulkan bahwa suatu

persoalan linear programing yang diselesaikan dengan metode grafik juga dapat diselesaikan

dengan metode simpleks, sebaliknya suatu persoalan yang hanya bisa diselesaikan dengan

metode simplex tidak dapat diselesaikan dengan metode grafik.

12