program linier

PEMOGRAMAN LINIERKELOMPOK 1

ADE ADRIANAHERIYANTO PANGABEAN

RIRI LIDYA FATHIRAZULFIATRI

Merupakan peralatan manajemen yang menyertakan ilmu pengetahuan,matematik dan logika dalam kerangka pemecahan masalah-masalah yang dihadapi sehari-hari sehingga akhirnya permasalahan-permasalahan terebut dapat dipecahkan secara optimal. (Miller dan M.K Starr)

PENELITIAN OPERASIONAL

Ciri-ciri Peneltian Operasional

Menguji hubungan fungsional dan suatu sistem secara keseluruhan.

Menggunakan pendekatan tim campuran atau interdisiplin.

Menganut metode ilmiah. Membuka persoalan-persoalan baru untuk dipelajari.

Linier programming adalah suatu teknis matematika yang dirancang untuk membantu manajer dalam merencanakan dan membuat keputusan dalam mengalokasikan sumber daya yang terbatas untuk mencapai tujuan perusahaan.

A. Defenisi PL

PL memiliki 4 ciri khusus yaitu :

Penyelesaian masalah mengarah pada pencapaian tujuan maksimisasi atau minimisasi.

Kendala yang ada membatasi tingkat pencapaian tujuan Ada beberapa alternatif penyelesaian Hubungan matematis bersifat linear

Selain 4 ciri khusus tadi PL juga memiliki 5 syarat tambahan yang harus diperhatiakan sebagai asumsi dasar yaitu : a. Certainty (kepastian)b. Proportionality (proporsionalitas)c. Additivity (penambahan)d. Divisibility (bisa dibagi-bagi)e. Non-negative variable (variabel tidak negatif)

Dalam memformulasikan model Pemograman Linier terdapat 3 cara yaitu :a. Tentukan variabel keputusan yang ingin diketahui,

kemudian gambarkan dengan symbol aljabar.b. Tentukan semua keterbatasan atau kendala dan

gambarkan dalam bentuk persamaan atau pertidaksamaan linier dari variabel keputusan tadi.

c. Tentukan kriteria atau tujuan dan gambarkan dalam bentuk fungsi linier dari variabel keputusan tadi (maksimasi atau minimasi).

B. Cara Memformulasikan PL

Contoh 1suatu perusahaan akan menjadwalkan produksi

dari penambangan batubara yang membutuhkan dua jenis sumber yaitu jam kerja dan kapasitas muatan alat. Perusahan telah merencanakan tiga jenis model dan ketiganya membutuhkan sumber dan keuntungan yang terlihat pada tabel 1 dibawah ini.

MODEL

A B C

Waktu kerja(per jam)

7 3 5

Kapasitas (ton/jam)

4 4 5

Keuntungan ($/jam)

17 10 15

Tabel 1

1. Metode Grafik Metode grafis dapat digunakan apabila

persoalan pemograman Linier yang akan diselesaikan paling banyak mengandung tiga variabel keputusan.

Tujuan dari metode grafis bukan untuk mendapatkan metode yang praktis bagi pemecahan model pemograman linier, karena umumnya persoalan pemograman linier melibatkan sejumlah variabel yang banyak.

C. Metode Penyelesaian PL

Langkah – langkah Penyelesaian Metode ini : Merumuskan masalah yang asli menjadi model

matematika yang sesuai dengan syarat-syarat yang diperlukan dalam model Program Linier, yang mempunyai fungsi tujuan, fungsi kendala, syarat ikatan non-negatif.

Kendala-kendala yang ada digambar hingga dapat diperoleh daerah penyelesaiannya.

Nilai fungsi sasaran (fungsi tujuan) dihitung disetiap titik sudut daerah penyelesaian.

Dipilih nilai yang sesuai dengan fungsi tujuan(jika memaksimumkan berarti nilainya terbesar, begitu sebaliknya).

Jawaban soal sebenarnya sudah diperoleh.

Contoh 2Suatu Perusahaan Tambang Batubara memiliki dua

lokasi penambangan. Lokasi I setiap hari menghasilkan 1 ton batubara kualitas A, 3 ton kualitas B dan 5 ton kualitas C. Lokasi II menghasilkan setiap hari menghasilkan 2 ton batubara untuk masing-masing kualitas. Dalam waktu kurang dari dua bulan perusahaan harus memenuhi pesanan 80 ton batubara kualitas A, 160 ton kualitas B dan 200 ton kualitas C. Jika diketahui biaya penambangan di lokasi I adalah Rp 2.000.000/hari dan di lokasi II adalah Rp 1.500.000, tentukan jumlah hari penambangan di lokasi I dan lokasi II agar pesanan dapat terpenuhi dengan biaya semurah mungkin !

Penyelesaian : X = Lokasi IY = Lokasi II

Kualitas Lokasi I Lokasi II Batasan

A 1 2 80

B 3 2 160

C 5 2 200

Fungsi kendala :

X + 2Y ≥ 803X + 2Y ≥ 1605X + 2y ≥ 200X,Y ≥ 0

X + 2Y ≥ 80 3X + 2Y ≥160 5X + 2y≥200

X 0 80 0 53.3 0 40

Y 40 0 80 0 100 0

0 10 20 30 40 50 60 70 80 900

20

40

60

80

100

120

123

5X + 2Y ≥200

3X + 2Y ≥ 160

X + 2Y ≥ 80

(40,20)

(50,20

)

Jadi titik optimumnya adalah (40,20) artinya biaya produksi minimum jika perusahaan mengoperasikan lokasi I selama 40 hari dan lokasi II selama 20 hari.

(X,Y) Z = 2.000.000X + 1.500.000Y

(40,20) 110.000.000

(20,50) 115.000.000

2. Metode SimpleksMetode grafik tidak dapat menyelesaikan

persoalan linear program yang memilki variabel keputusan yang cukup besar atau lebih dari dua, maka untuk menyelesaikannya digunakan 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.

Langkah yang harus dilakukan dalam menyelesaikan metode ini sebagai berikut :

Tulis persamaan fungsi tujuan dan fungsi kendala dari permasalahan.

Nilai kanan(NK) fungsi tujuan harus nol (0). Fungsi kendala dengan tanda “≤ dan ≥” harus diubah

ke bentuk “=” dengan menambahkan variabel slack/surplus. Variabel slack/surplus disebut juga variabel dasar. Misalkan X + Y ≤ 20 maka X + Y + Z = 20.

X , Y dan Variabel buatan harus ≥ 0

Contoh soal :

Fungsi tujuanZ = 3X1 + 5X2

Fungsi kendala 2 X1 ≤ 83X2 ≤ 156X 1 + 5X2 ≤ 30

Penyelesaian :Langkah yang pertama kita lakukan adalah

merubah bentuk “≤” menjadi “=“. Dengan menambahkan variabel dasar .

Fungsi TujuanZ = 3X1 + 5X2 Z - 3X1 + 5X2 = 0

Fungsi kendala 2 X1 ≤ 8 2 X1 + S1 = 83X2 ≤ 15 3X2 + S2 = 156X 1 + 5X2 ≤ 30 6X 1 + 5X2 + S3 = 30

Kolom kunci warna merah dan baris kunci warna kuning.

Variabel dasar Z X1 X2 S1 S2 S3 solusi

Z 1 -3 -5 0 0 0 0

S1 0 2 0 1 0 0 8

S2 0 0 3 0 1 0 15

S3 0 6 5 0 0 1 30

Lakukan iterasi 2

Variabel dasar Z X1 X2 S1 S2 S3 solusi

Z 0 -3 0 0 5/3 0 25

S1 0 2 0 1 0 0 8

S2 0 0 1 0 1/3 0 5

S3 0 6 0 0 5/3 1 5

Iterasai 3

Jadai dari tabel tersebut terlihat solusi persamaan Dimana Zmaks = 27 1/2 , X1 5/6 dan X2 5

Variabel dasar Z X1 X2 S1 S2 S3 solusi

Z 1 0 0 0 5/6 1/2 27 1/2

S1 0 0 0 1 5/9 -1/3 6 1/3

S2 0 0 1 0 1/3 0 5

S3 0 1 0 0 -5/18 1/6 5/6

Z = 3X1 + 5X2

TERIMA KASIH