Tugas Makalah Pot-1.docx

1

BAB I PENDAHULUAN A. Latar Belakang Pada dasarnya setiap perusahaan baik perusahaan besar maupun perusahaan kecil bertujuan untuk mencari keuntungan yang sebesar – besarnya dalam menjalankan kegiatan perusahaan,lebih – lebih dalam era globalisasi sekarang ini., maka setiap organisasi dalam dunia pekerjaan dituntut untuk senantiasa memanfaatkan sumberdaya yang dimiliki seoptimal mungkin. Metode Simpleks merupakan sebuah metode lanjutan dari metode grafik. Metode Grafik tidak dapat menyelesaikan persoalan yang memiliki variable keputusan cukup besar, sehingga untuk menyelesaikannya dibutuhkan sebuah metode yang lebih kompleks yaitu dengan menggunakan program komputer QSB (Quantitative System For Business) atau menggunakan metode simpleks. Dalam kenyataannya penggunaan komputer lebih efisien, akan tetapi metode dasar yang digunakan dalam pengoperasian komputer tetap metode simpleks. Metode simpleks merupakan salah satu teknik penentuan solusi optimal yang digunakan dalam pemograman linear. Penentuan solusi optimal didasarkan pada teknik eliminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim (ingat solusi grafik) satu per satu dengan cara perhitungan iteratif. Metode Simpleks adalah suatu metode yang secara sistematis dimulai dari suatu pemecahan dasar yang dimungkinkan ke pemecahan dasar yang lainnya dan ini dilakukan tahap demi tahap yang disebut dengan iterasi (dengan jumlah iterasi yang terbatas) sehingga pada akhirnya

2

akan tercapai suatu pemecahan dasar yang optimum dan setiap langkah menghasilkan suatu nilai dan fungsi tujuan yang selalu lebih optimal atau sama dari langkah-langkah sebelumnya. B. Rumusan Masalah 1. Apa pengertian metode simpleks ? 2. Apa saja istilah yang sangat sering digunakan dalam metode simpleks ? 3. Bagaimana ketentuan dalam penyelesaian metode simpleks? C. Tujuan 1. Mahasiswa dapat mengetahui pengertian dari metode simpleks 2. Mahasiswa dapat mengetahui istilah yang sering digunakan dalam metode simpleks 3. Mahasiswa dapat mengetahui penyelesaian dari metode simpleks

3

BAB II PEMBAHASAN A. Pengertian Metode Simpleks Metode Simpleks merupakan salah satu teknik penyelesaian dalam program linier yang digunakan sebagai teknik pengambilan keputusan dalam permasalahn yang berhubungan dengan pengalokasian sumber daya yang optimal. Metode Simpleks digunakan untuk mencari nilai optimal dari program linier yang melibatkan banyak constraint (pembatas) dan banyak variable (lebih dari dua variable). Penemuan metode ini merupakan lompatan besar dalam riset operasi dan digunakan sebagai prosedur penyelesaian dari setiap program computer. Metode penyelesaian program linier dengan metode simpleks pertama kali dikemukakan oleh George Dantzig pada tahun 1947. Metode ini menjadi terkenal ketika ditemukan alat hitung elektronik dan menjadi popular ketika munculnya computer. Proses perhitungan metode ini dengan melakukan iterasi berulang ulang sampai tercapai hasil optimal dan proses perhitungan ini menjadi mudah dengan computer. Selanjutnya berbagai alat dan metode dikembangkan untuk menyelesaikan masalah program linier bahkan sampai pada masalah riset operasi hingga tahun 1950 an seperti program dinamika, teori antrian dan persediaan Program Linier merupakan metode matematik dalam mengalokasi kan sumber daya

yang langka untuk mencapai tujuan tunggal seperti

memaksimumkan atau meminimumkan biaya. Program linier banyak diterapkan dalam membantu menyelesaikan masalah ekonomi, industri,

4

militer, social, dan lain-lain. Karakteristik persoalan dalam program linier adalah sebagai berikut : 1. Ada tujuan yang ingin dicapai 2. Tersedia beberapa alternatif untuk mencapai tujuan 3. Sumberdaya dalam keadaan terbatas 4. Dapat dirumuskan dalam bentuk matematika (persaman/ketidaksamaan) B. Istilah dalam metode simpleks 1. Iterasi : tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai table sebelumnya. 2. Variabel non basis : variable yang nilainya diatur menjadi nol pada sembarang iterasi. 3. Variabel basis : variabel yang nilainya bukan nol pada sembarang iterasi. 4. Solusi atau Nilai Kanan (NK) : nilai sumber daya pembatas yang masih tersedia. 5. Variabel Slack : variabel yang ditambahkan ke model matematika kendala untuk mengkonversi pertidaksamaan ≤ menjadi = 6. Variabel surplus : variabel yang dikurangkan dari model matematika untuk mengkonversikan pertidaksamaan ≥ menjadi persamaan = 7. Variabel buatan : variabel yang ditambahkan ke dalam model matematika kendala dengan bentuk ≥ atau = untuk difungsikan sebagai variabel basis awal. 8. Kolom Pivot (Kolom Kerja) : kolom yang memuat variabel masuk.

5

9. Baris Pivot (Baris Kerja) : salah satu baris dari antara variabel baris yang memuat variabel keluar. 10. Elemen Pivot (Elemen Kerja) : elemen yang terletak pada perpotongan kolom dan baris pivot. 11. Variabel masuk : variabel yang terpilih untuk menjadi variabel basis pada iterasi berikutnya. 12. Variabel keluar : variabel yang keluar dari variabel basis pada iterasi berikutnya dan digantikan dengan variabel masuk. C. Ketentuan dalam penyelesaian metode simpleks 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

6

variabel ini secara fisik tidak mempunyai arti, dan hanya digunakan untuk kepentingan perhitungan saja. 5. Fungsi kendala dengan tanda = harus ditambah artificial variable (M) Dalam penyelesaian metode simpleks terdapat beberapa cara yang digunakan dalam menyelesaiakan metode simpleks ini . Antara lain : 1. Masalah Maksimasi Untuk menyelesaikan masalah maksimasi maka programasi linear harus lebih dahulu ditulis dalam bentuk standar. Dengan bentuk standar dimaksudkan adalah permasalahan programasi linear yang berwujud permasalahan maksimasi dengan batasan-batasan (kendala) yang bertanda kurang dari atau sama dengan

( ≤ ) yang menunjukkan keterbatasan

sumber daya yang tersedia. Untuk bentuk-bentuk lain seperti masalah minimisasi

maupun

penyimpangan–penyimpangan

lain

batasanbatasan yang berlaku akan dibicarakan tersendiri. merupakan langkah-langkah menggunakan metode simpleks yaitu : a. Mengubah fungsi tujuan dan batasan-batasan b. Menyusun persamaan-persamaan di dalam tabel c. Memilih kolom kunci d. Memilih baris kunci e. Merubah nilai-nilai pada baris kunci f. Mengubah nilai-nilai selain pada baris kunci g. Melanjutkan perbaikan/pengulangan/literasi 2. Kendala (Syarat) Bertanda “ = “

dalam Berikut

7

Kendala berbentuk sama dengan (=) juga tidak memiliki variabel basis. Oleh karena itu tambahan satu variabel basis semu, agar tabel awal simpleks dapat dibentuk. Misalkan,2𝑥1 + 4𝑥2 = 20 , dapat diubah menjadi 2𝑥1 + 4𝑥2 + 𝑄 = 20, dimana Q adalah variabel basis semu. Meskipun semua kendala telah memiliki variabel basis, tetapi penambahan variabel semu tersebut bukan penyelesaian yang fisibel bagi masalah aslinya. Variabel semu harus dikurangi nilainya hingga menjadi nol. Ada dua metode yang dapat dilakukan untuk mengnolkan variabel semu yaitu : a. Metode M besar Dalam metode ini, koefisien fungsi tujuan untuk variabel semu diberi nilai yang sangat besar yaitu negatif M atau – M untuk fungsi tujuan maksimum dan positif M atau + M untuk fungsi tujuan minimum. b. Metode dua fase (dua tahapan) Dalam metode dua fase, penyelesaian dipisahkan menjadi dua tahapan. Setiap tahapan menggunakan tabel simpleks dan proses kerjanya tetap menggunakan langkah-langkah metode simpleks. 

Fase pertama, bertujuan untuk menghilangkan variabel semu



Fase kedua, tabel akhir fase pertama merupakan tabel awal fase kedua

3. Masalah Minimumisasi Masalah minimisasi sangat mungkin ditemui di dalam formulasi LP (Linear Program). Bagaimana menyelesaikan masalah LP jika fungsi

8

tujuannya berbentuk minimisasi? Untuk menangani masalah ini, ada dua metode yang dapat dilakukan, yaitu: a. Metode 1 : Mengubah fungsi tujuan minimum menjadi maksimum b. Metode 2 : Fungsi tujuan minimum dimasukkan dalam tabel (tetap seperti aslinya) 4. Masalah Primal dan Dual Teori dualitas merupakan salah satu konsep programa linier yang penting dan menarik ditinjau dari segi teori dan praktisnya. Ide dasar yang melatarbelakangi teori ini adalah bahwa setiap persoalan programa linier mempunyai suatu programa linier lain yang saling berkaitan yang disebut “dual”, sedemikian sehingga solusi pada persoalan semula (yang disebut "primal”) juga memberi solusi pada dualnya. Pendefinisian dual ini akan tergantung pada jenis pembatas, tandatanda variabel, dan bentuk optimasi dari persoalan primalnya. Akan tetapi, karena setiap persoalan programa linier harus dibuat dalam bentuk standar lebih dahulu sebelum modelnya dipecahkan , maka pendefinisian dibawah ini akan secara otomatis meliputi ketiga hal di atas. Bentuk umum masalah primal dual adalah sebagai berikut: a. Menentukan koefisien fungsi tujuan variabel-variabel basis awal b. Menentukan koefisien fungsi tujuan variabel-variabel nonbasis awal c. Menentukan nilai ruas kanan (solusi) dari variabel-variabel basis d. Menentukan koefisien pembatas

9

BAB III KASUS METODE SIMPLEX DI PERTAMBANGAN A. Kasus 1 PT. JAYA melakukan penambanagan pada pit 1 dan pit 2 dimana pada pit 1 mengahasilkan mineral bijih high quality 3 ton dan mineral bijih low quality 1 ton dan pit 2 menghasilkan mineral bijih besi high quality 4 ton dan mineral bijih low quality 2 ton,penabambangan bijih besi high quality dan bijih besi low quality pada PT. JAYA kurang lebih 120 ton 40 ton masing waktu kerjanya adalah 8 jam dan waktu keseluruhannya dalah 160 jam. Berapakah yang harus di produksi pada PT.JAYA untuk mendapatkan laba maksimal (z = 30X1 + 40X2)

Tempat Penambangan PIT 1

High Quality

PIT 2

Low Quality

3

1

Masa Kerja (Jam) 8

4

2

8

120

40

160

Z = 30x1 + 40x2 Fungsi Kendala : - PIT 1 : 3x1 + 4x2 ≤ 120 - PIT 2 : x1 + 2x2 ≤

40

- Masa kerja : 8x1 + 8x2 ≤

160

Batasan Non Negatif : X1 , X2 , S1 , S2 , S3 ≥ 0 Langkah-langkah pengerjaan :

Laba Keuntungan 30 40

10

1. Mengubah fungsi tujuan dan fungsi kendala Fungsi Tujuan : Z = 30X1 + 40X2 max Z – 30X1 – 40X2 = 0 Fungsi Kendala : 

PIT 1: 3X1 + 4X2 ≤ 120



PIT 2 : X1 + 2X2 ≤ 40



Masa kerja : 8 X1 + 8X2 ≤ 160 - 8 X1 + 8 X2 + S3 ≤

3 X1 + 4 X2 + S1 ≤ 120 X1 + 2X2 + S2 ≤

40 160

2. Menyusun Persamaan Ke Dalam Tabel NB

X1

X2

S1

S2

S3

NILAI

INDEKS

KANAN Z

-30

-40

0

0

0

0

S1

3

4

1

0

0

120

S2

1

2

0

1

0

40

S3

8

8

0

0

1

160

3. Menentukan kolom kunci. Kolom kunci adalah kolom yang mempunyai nilai baris Z yang bernilai negative dengan angka terbesar. NB

X1

X2

S1

S2

S3

NILAI

INDEKS

KANAN Z

-30

-40

0

0

0

0

S1

3

4

1

0

0

120

30

S2

1

2

0

1

0

40

20

S3

8

8

0

0

1

160

20

11

4. Menentukan baris kunci Menentukan baris kunci adalah milai indeks terkecil. Indeks = Nilai kanan (NK) Nilai kolam kunci NB

X1

X2

S1

S2

S3

NILAI

INDEKS

KANAN Z

-30

-40

0

0

0

0

S1

3

4

1

0

0

120

30

S2

1

2

0

1

0

40

20

S3

8

8

0

0

1

160

20

A. Menentukan nilai baris kunci Baris kunci baru = baris kunci / angka kunci NB NB

X1

X2

S1

S2

S3

NILAI

INDEKS

KANAN Z S1 S2 S3

1

1

0

0

1/8

20

B. Mengubah nilai-nilai selain baris kunci Baris baru = baris lama – (nilai kolom kunci * nilai baris kunci baru) Z -30 -40 0 0 0 -40 1

1

0

0 0 1/8 20

dikalikan

12

Z -30 -40

0 0 0

0

-40 -40 -40

0 0 -5 -800 dikurangi

S1 3 4

1 0 0

120

4

0 0 1/8

20 dikalikan dengan 4

S1 3 4

1 0 0

120

4

4 4

0 0 1/2

80 dikurangi

-1 0

1 0 -1/2

40

1 1

S2 1 2 0 1 0

40

2

20 dikalikan dengan 2

1 1

0 0 1/8

S2 1 2 0 1 0

40

2

40 dikurangi

2 2 0 0 1/4 -1 0 0 1 -1/4

0

C. Masukan nilai baru Tabel nilai baru NB

X1

X2

S1

S2

S3

NILAI

INDEKS

KANAN Z

10

0

0

0

5

800

S1

1

0

1

0

-1/2

40

S2

-1

0

0

1

-1/4

0

S3

1

1

0

0

1/8

20

Jadi pada pit 2 didapatkan 20 keuntungan optimum yang didapatkan $800.Dan dimasukan ke dalam nilai fungsinya 30X1 + 40X2 = $800 disimpulkan bahwa

13

pada penambangan yang paling efektif dan mendapatkan keuntungan yang optimum dengan menambang pada pit 2 berdasarka metode simpleks

14

BAB IV PENUTUP

A. Kesimpulan Metode Simpleks merupakan salah satu teknik penyelesaian dalam program linier yang digunakan sebagai teknik pengambilan keputusan dalam permasalahn yang berhubungan dengan pengalokasian sumber daya yang optimal. Metode Simpleks digunakan untuk mencari nilai optimal dari program linier yang melibatkan banyak constraint (pembatas) dan banyak variable (lebih dari dua variable) . B.Kritik dan Saran Kami sebagai penyusun menyadari bahwa masih terdapat kekurangan didalam makalah kami maka, maka dari itu kritik dan saran yang membangun dari pembaca sangat kami harapkan