BAB IPENDAHULUAN

A. Latar Belakang

Salah 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 grafik merupakan salah satu metode yang dapat digunakan untuk menyelesaikan masalah pemrograman linear yang melibatkan dua peubah keputusan. Membahas mengenai masalah meminimumkan fungsi kendala bertanda , fungsi kendala bertanda = tidak ada penyelesaian layak, tidak ada penyelesaian optimal, beberapa alternatif 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 jelasnya, dalam makalah ini penulis akan membahas bagaimana kasus-kasus dapat dikenali dan ditangani saat menggunakan metode simpleks.

B. Rumusan Masalah Adapun rumusan masalah yang akan dibahas dalam makalah ini adalah sebagai berikut: 1. Bagaimana ketidaklayakan dikenali saat menggunakan metode simpleks?

2. Bagaimana cara mencari kesalahan bila muncul ketidakterbatasan?

3. Bagaimana cara mencari penyelesaian optimal alternatif?

4. Kapan pemrograman linear dikatakan mengalami degenerasi?C. Tujuan Penulisan Adapun tujuan penulisan makalah ini adalah untuk memudahkan kita dalam menyelesaiakan sesuatu pemrograman linear dengan menggunakan metode simpleks. Apabila muncul ketidaklayakan dan ketidak terbatasan. Selain itu juga dapat mengenali kapan suatu pemrograman linear itu mengalami degenerasi. BAB IIPEMBAHASAN

A. Ketidaklayakan

Ketidaklayakan terjadi bila tidak ada penyelesiaan pemrograman linear yang memenuhi semua kendala, termasuk kendala tidak negatif. Ketidaklayakan dapat dikenali bila kriteria keoptimalan mengindikasikan bahwa suatu penyelesaian optimal telah diperoleh dan satu atau lebih peubah artificial tetap berada dalam penyelesaian pada nilai positif. Perhatikan modifikasi lain dari masalah PT. Maju Terus, dengan pengandaian manajer telah menetapkan persyaratan minimum gabungan total produksi 50 satuan. Revisi formulasi masalahnya sebagai berikut: Maksimum Z = 50 x1 + 40 x2

Dengan kendala

3x1 + 5 x2 150 waktu perakitan

x2 monitor portable

8x1 + 5 x2 300 kapasitas gudang

x1 + x2 50 produksi minimum

x1, x2 0 tak negatif

Grafik penyelesaian untuk makalah ini diperlihatkan dalam gambar 2.1. kita dapat melihat bahwa tidak ada penyelesaian yang memenuhi kendala awal masalah dan kendala gabungan total produksi minimum (x1 + x2 50). Kita selesaikan modifikasi masalah ini dengan menggunakan metode simpleks.

Gambar 2.1. Grafik daerah penyelesaian untuk modifikasi masalah PT. Maju Terus.Tabel 2.1 Tabel Simpleks AwaldasarCBx1x2S1S2S3S4a4b

50400000-M

S103510000150

S20010100020

S30(8)500100300

a4-M11000-1150

zj-M-M000M-M-50M

cj zj50+M40+M000-M0

Tabel 2.2. Tabel Simpleks Hasil Iterasi PertamaDasarCBx1x2S1S2S3S4a4b

50400000-M

S100(25/8)10-3/80075/2

S20010100020

x15015/8001/80075/2

a4-m13/800-1/8-1125/2

zj50

00

M-M1875-

cj zj0

00

-M0

Dari tabel 2-3, peubah artificial a4 berada dalam penyelesaian dengan nilai positif; jadi fase I belum sesuai. Perhatikan cj zj 0 untuk semua peubah; oleh karena itu, sesuai dengan kriteria keoptimalan, ini seharusnya menjadi penyelesaian optimal. Namun demikian, penyelesaian ini tidak layak karena x1 = 30 dan x2 = 12 menghasilkan gabungan total produksi 42 satuan, bukannya paling sedikit 50 satuan. kenyataan bahwa peubah artificial berada dalam penyelesaian pada nilai a4 = 8 memberitahu kita bahwa penyelesaian akhir itu melanggar kendala keempat (x1 + x2 50) sebanyak delapan satuan.Tabel 2.3. Tabel Simpleks Hasil akhirDasarCBx1x2S1S2S3S4a4b

50400000-M

x240018/250-3/250012

S2000-8/2513/25008

x15010-5/2505/250030

a4-M00-3/250-2/25-118

zj5040

0

M-M1980-8M

cj zj00

0

-M0

Dalam terminologi metode simpleks, kita mengenali ketidaklayakan sebagai kasus dimana satu atau lebih peubah artificial berada dalam penyelesaian akhir pada nilai positif. Untuk masalah pemrograman linear dengan semua kendala dan sisi sebelah kanan tak negatif, selalu akan ada penyelesaian layak, karena tidak diperlukan peubah artificial untuk membuat tabel simpleks awal pada masalah jenis ini, maka tidak mungkin ada peubah artificial dalam penyelesaian akhir.B. Ketidakterbatasan Untuk masalah memaksimumkan, kita katakana bahwa suatu pemrograman linear tidak terbatas jika nilai penyelesaian itu dapat dibuat besar tidak terhingga tanpa melanggar kendala apapun. Jika muncul ketidakterbatasan biasanya kita mencari kesalahan dalam formulasi masalah itu. Metode simpleks akan mengidentifikasi secara otomatis ketidakterbatasan yang muncul sebelum tabel simpleks akhir tercapai. Untuk mengilustrasikan konsep ini, kita perhatikan contoh masalah tiak terbatas sebagai berikut:

Maksimumkan Z = 20x1 + 10x2

Dengan kendala :x1 + 5x2 2

x2 5

x1, x2 0

Kita menguraikan suatu peubah lebihan S1 dari persamaan kendala pertama dan menambahkan peubah susutan S2 pada kendala kedua untuk mendapatkan penyajian bentuk baku. Kemudian menghapus a1 pada iterasi pertama, tabel simpleksnya terlihat pada tabel 2.4.Tabel 2.4. Hasil iterasi pertamaDasarCBx1x2S1S2b

201000

x1010-102

S1001015

zj200-20040

cj zj010200

Karena S1 memiliki cj zj = 20 positif terbesar, maka nilai fungsi tujuan dapat ditingkatkan dengan memasukkan S1 kedalam dasar. Namun = -1 dan = 0 maka dapat dibentuk rasio bi /ai3 untuk semua >0, tidak ada nilai yang lebih besar dari nol. Ini merupakan indikasi bahwa penyelesaian pemrograman linear itu tidak terbatas. Kasus penyelesaian tidak terbatas tidak pernah terjadi dalam masalah meminimumkan biaya. Bila kita temukan suatu penyelesaian tidak terbatas pada masalah pemrograman linear, kita harus memeriksa kembali formulasi masalah itu untuk menentukan apakah telah terjadi kesalahan formulasi. C. Penyelesaian Optimal AlternatifSuatu pemrograman linear dengan dua atau lebih penyelesaian optimal dikatakan memiliki penyelesaian optimal alternatif. Untuk mengilustrasikan kasus penyelesaian optimal alternatif saat menggunakan metode simpleks, perhatikan untuk mengubah fungsi tujuan masalah PT. Maju Terus dari 50x1 + 40x2 menjadi 30x1 + 50x2 maka diperoleh revisi pemrograman linear yaitu:

Maksimumkan Z = 30x1 + 50x2

Dengan kendala :3x1 + 5x2 150 waktu perakitan

x2 20 monitor portable

8x1 + 5x2 300 kapasitas gedung

x1, x2 0 tak negatif

Tabel 2.5 tabel simpleks akhirDasarCBx1x2S1S2S3

x2500101020

S2000-8/325/31200/3

x120101/3-5/34050/3

zj305010001500

cj zj00-1000

Gambar 2. Penyelesaian grafik untuk masalah PT. Maju Terus dengan penyelesaian optimal alternatif.Semua nilai dalam baris evaluasi bersih kurang dari atau sama dengan nol, menunjukkan bahwa penyelesaian optimal telah ditemukan. Penyelesaian ini ditentukan oleh x1 = 50/3, x2 = 20, S1 = 0, S2 = 0 dan S3 = 200/3 berhubungan dengan titik ekstrim D dalam gambar 2.2. Kita perhatikan entri baris evaluasi bersih untuk S2 adalah nol, maka kita dapat memperkenalkan S2 ke dalam dasar tanpa mengubah nilai penyelesaian itu, dapat dilihat dalam tabel 2.6. berikut: Tabel 2.6. Tabel simpleks akhir baruDasarCBx1x2S1S2S3

3050000

S150018/250-3/2512

S2000-8/2513/258

X13010-5/2505/2530

zj305010001500

cj zj00-1000

Setelah memasukkan S2, kita memiliki penyelesaian layak dasar yang berada x1 = 30, x2 = 12, S1 = 0, S2 = 8 dan S3 = 0. Sehingga penyelesaian baru ini juga optimal cj - zj 0 untuk semua j. dari penjelasan di atas, kita dapat mengetahui bahwa masalah pemrograman linear memiliki penyelesaian optimal alternatif saat menggunakan pendekatan grafik dengan mengamati bahwa fungsi tujuannya paralel dengan salah satu kendala yang mengikat.D. Degenerasi Suatu pemrograman linear dikatakan mengalami degenerasi jika satu atau lebih peubah dasarnya memiliki nilai nol. Untuk melihat bagaimana terjadinya degenerasi pemrograman linear, perhatikan perubahan nilai sisi sebelah kanan dari kendala waktu perakitan pada masalah PT. Maju Terus. Modifikaisi linearnya diperlihatkan sebagai berikut:

Maksimumkan Z = 50x1 + 40x2

Dengan kendala

3x1 + 5x2 175 waktu perakitan

x2 20 monitor portable

8x1 + 5x2 300 kapasitas gedung

x1, x2 0 tak negatif Tabel 2.7. Tabel simpleks setelah iterasi pertamaDasarCBx1x2S1S2S3b

5040000

S10025/810-3/8125/2

S200101020

x15015/8001/875/2

zj50250/80001875

cj zj070/8000

Entri dalam baris evaluasi bersih menunjukkan bahwa x2 harus memasuki dasar itu. Maka kita hitung rasio yang tepat untuk menentukan baris pivot, diperoleh:

, maka terlihat hubungan antara baris pertama dan kedua. Ini merupakan indikasi bahwa kita akan memiliki suatu degenerasi penyelesaian layak dasar pada iterasi berikutnya. Tabel 2.8. Tabel simpleks setelah iterasi berikutnyaDasarCBx1x2S1S2S3

5040000

x240018/250-3/2520

S2000-8/2513/250

x15010-5/2505/2525

zj504070/250130/252050

cj zj00-70/250-130/25

Bilamana kita memiliki hubungan dalam rasio minimum , akan selalu ada peubah dasar yang sama dengan nol dalam tabel berikutnya. Oleh karena itu, kita tidak merekam endosikan untuk memperkenalkan langkah-langkah khusus ke dalam metode simpleks guna menghapus kemungkinan terjadinya degenerasi. Jika saat melakukan iterasi algoritma simpleks muncul suatu hubungan untuk rasio minimum , maka kita hanya merekomendasikan untuk memilih baris atas sebagai baris pivot. BAB IIIPENUTUPA. Kesimpulan

Adapun kesimpulan yang dapat penulis kemukakan adalah sebagai berikut: 1. Ketidaklayakan dapat dikenali bila kriteria keoptimalan mengindikasikan bahwa suatu penyelesaian optimal telah diperoleh dan satu atau lebih peubah artificial tetap berada dalam penyelesaian pada nilai positif.2. Pemrograman linear maksimum tidak terbatas jika dimungkinkan untuk membuat nilai penyelesaian optimal sebesar yang diinginkan tanpa melanggar kendala manapun.

3. Apabila suatu pemrograman linear memiliki dua atau lebih penyelesaian optimal maka dikatakan memiliki penyelesaian optimal alternatif.4. Suatu pemrograman linear dikatakan mengalami degenerasi jika satu atau lebih peubah dasarnya memiliki nilai nol.

B. Saran Adapun saran yang penulis dapat kemukakan adalah apabila materi pada makalah ini dianggap kurang menunjang, maka pembaca dapat menambahkan refrensi dari sumber lain.DAFTAR PUSTAKAAnton, Howard., Rorres, Chirs. 2004. Aljabar Linear Elementer Edisi Kedelapan. Jakarta: Erlangga.Mairy, Du. 1999. Matematika Terapan Untuk Bisnis dan Ekonomi. Yogyakarta: BPFE-Yogyakarta.Subagyo, Pangestu., Asri, Marwan. Dan handoko, Hani., 2000, Dasar dasar Operations Research. Yogyakarta: BPFE-Yogyakarta.Tiro, Muhammad Arif. Pengenalan Manajemen Sains. Cet 1: Makassar: Andira Publisher. 2004. Taha, H.A. 2010. Riset Operasi Suatu Pengantar. Tangerang: Bina Rupa Aksara.

Widiarsono, Teguh. 2004. Tutorial Praktis Belajar Matlab. Jakarta.

DAFTAR ISIHALAMAN JUDUL

iKATA PENGANTAR

ii

DAFTAR ISI

iii

BAB I PENDAHULUAN

1

A. Latar Belakang

1

B. Rumusan Masalah

1

C. Tujuan Penulisan

2

BAB II PEMBAHASAN

3

A. Ketidaklayakan

3

B. Ketidakterbatasan

6

C. Penyelesaian Optimal Alternatif

7

D. Degenerasi

9

BAB III PENUTUP

11

A. Kesimpulan

11

B. Saran

11

DAFTAR PUSTAKA

12

Penyelesaian awal untuk persyaratan produksi total

60

50

X2

30

20

Penyelesaian layak masalah awal

X1

X2

60

50

30

D

E

20

C

B

30x1+50x2=1500

A

X1

37.5

50

PAGE

_1303046943.unknown

_1303047197.unknown

_1303047198.unknown

_1303047195.unknown

_1303047196.unknown

_1303046961.unknown

_1303044710.unknown

_1303046909.unknown

_1303046934.unknown

_1303046043.unknown

_1303046853.unknown

_1303045833.unknown

_1303044660.unknown

_1303044696.unknown

_1303044625.unknown