RESEARCH OPERASIONAL LINEAR PROGRAMMING METODE SIMPLEKS KASUS MAKSIMISASI

Diajukan Untuk Memenuhi Salah Satu Tugas Mata Kuliah Riset Operasional Sosial Ekonomi Pertanian

Di Susun oleh :

1. Sulekhah (071807)

2. Desty Megadiyanti (071751)

3. Mimin Maemunah (071780)

4. Taryono (071732)

5. Susanti. N.K.N (071808)

6. Via Purnamasari (071734)

FAKULTAS PERTANIAN

UNIVERSITAS SULTAN AGENG TIRTAYASA

2011

BAB I

PENDAHULUAN

2.1 LATAR BELAKANG

Sebagian besar persoalan manajemen berkenaan dengan pengggunaan sumber secara efisisen atau alokasi sumber-sumber terbatas untuk mencapai tujuan yang diinginkan (desired objective) seperti penerimaan hasil penjualan yang harus maksimum, penerimaan devisa hasil ekspor nonmigas harus maksimum, jumlah baiaya transpor harus minimum, lamanya waktu antrian untuk menerima pelayanan sependek mungkin, dan kemakmuran rakyat sebesar-besarnya.

Dalam keadaan sumber terbatas harus dicapai suatu hasil yang optimum. Dengan perkataan lain bagaimana caranya agar dengan masukan (input) yang serba terbatas dapat dicapai hasil kerja yaitu keluaran (output) berupa produksi barang dan jasa yang optimum . Untuk itu linear programming akan memberikan banyak sekali hasil pemecahan persoalan, sebagai alternatif pengambilan tindakan, akan tetapi hanya satu yang optimum (memaksimum atau minimum). Dengan mengambil keputusan yaitu memilih alternatif harus yang terbaik (the best alternative).

Agar suatu persolan dapat dipecahkan dengan tehnik Linear Programming harus memnuhi syarat sebagai berikut. (1) Harus dapat dirumuskan secara matematis; (2) Harus jelas fungsi objektif yang linear yang harus dibuat optimum; (3) pembatasan-pembatasan harus dinyatakan dalam ketidaksamaan yang linear. (4) Bersifat additive. (5) Nilai x harus positif (tidak boleh negatif, x ≥ 0)

Untuk menentukan alternatif yang terbaik, sehingga dapat mencapai tujuan baik memaksimalkan maupun meminimumkan yang hendak dicapai. Dalam linear programming dapat menggunkan metode substitusi, metode grafik dan metode simpleks. Namun pada kasus kali ini lebih mempfokuskan pemecahan masalah dengan menggunkan metode simpleks.

2.2 PERMASALAHAN

Permasalahan yang menyangkut dengan linear programming adalah memaksimalisasi keuntungan biaya dengan meminimisasi biaya.

2.3 TUJUAN

Tujuan dalam linear programming metode simplek adalah untuk menghitung maksimisasi keuntungan dengan minimisasi biaya.

BAB II

KONSEP

2.1 Linear Programming

Linear programming merupakan suatu model umum yang dapat di gunakan sebagai pemecahan masalah pengalokasian sumber-sumber yang terbatas scara optimal. Masalah akan timbul jika seseorang di haruskan untuk memilih atau menentukan tingkat setiap kegiatan yang akan di lakukannya, di mana masing-masing kegiatan membutuhkan sumber yang sama sedangkan jumlahnya terbatas. Secara sederhana dapat di gambarkan sebuah contoh keadaan bagian produksi suatu perusahaan yang di hadapkan pada masalah penentuan tingkat produksi masing-masingjenis produk dengan memperhatikan batasan factor-faktor produksi: mesin, tenaga kerja, bahan mentah, dan sebagainya untuk memperoleh tingkat keuntungan maksimal atau biaya minimal. Dalam makalah ini akan di jelaskan tentang penentuan dalam kasus maksimalisasi dengan metode simpleks.

Suatu penyampaian masalah linier programming perlu dibentuk formulasi secara matematik dari masalah yang sedang dihadapi dengan memenuhi syarat sebagai berikut;

1. Adanya variabel keputusan yang dinyatakan dalam simbul matematik dan variabel keputusan ini tidak negatif.

2. Adanya fungsi tujuan dari variabel keputusan yang menggambarkan kriteria pilihan terbaik.fungsi ini harus dibuat dalam suatu sel fungsi linier yang dapat berupa maksimum atau minimum.

3. Adanya kendala sumber daya yang dibuat dalam satu set fungsi linier.

A. Aspek – Aspek linier programming

1. Aplikasi Model Linier Programming

Model Linier programming dapat diaplikasikan untuk menyelesaikan berbagai masalah diantaranya yaitu;

a. Masalah product mix atau kombinasi produksi,yaitu; menentukan berapa jumlah dan jenis produk yang harus dibuat agar diperoleh keuntungan maksimum atau biaya minimum dangan memperhatikan sumber daya yang dimiliki.

b. Masalah perencanaan investasi, yaitu; berapa banyak dana yang akan ditanamkan dalam setiap alternative investasi,agar memaksimumkan return on investment atau net present value dengan memperhatikan kemampuan dana tersedia dan ketentuan setiap alternatif investasi.

c. Masalah perencanaan produksi dan persediaan, yaitu; menentukan berapa banyak produk yang akan diproduksi setiap periode,agar meminimumkan biaya persediaan ,sewa,lembur dan biaya subkontrak.

d. Masalah perencanaan advertensi / promosi, yaitu; berapa banyak dana yang akan dikeluarkan untuk kegiatan promosi,agar diperoleh efektivitas penggunaan media promosi.

e. Masalah diet, yaitu; berapa banyak setiap sumber makanan digunakan untuk membuat produk makanan baru.

f. Masalah pencampuran,yaitu;berapa banyak jumlah setiap bahan yang akan digunakan untuk membuat bahan baru.

g. Masalah distribusi / transportasi , yaitu; jumlah produk yang akan dialokasikan ke setiap lokasi pemasaran.

2. Asumsi Model linier programming

Terdapat empat asumsi dasar dalam penyelesaian masalah dengan model linier programming,yaitu;

a. Liniaritas :fungsi tujuan (objective function) dan kendala (constraint equations)dapat dibuat satu set fungsi linier.

b. Divisibility : nilai variabel keputusan dapat berbentuk pecahan atau bilangan bulat(integer)

c. Nonnegativity :nilai variabel keputusan tidak boleh negatif atau sama dengan nol.

d. Certainty : semua keterbatasan maupun koefisien variabel setiap kendala dan fungsi tujuan dapat ditentukan secara pasti.

Keempat asumsi diatas harus dipenuhi apabila ingin menyelesaikan masalah model linier programming.jika masalah tidak dapat memeuhi asumsi tersebut, persoalan tersebut dapat diselesaikan dengan program matematik yang lain seperti; integer programming, goal programming, nonlinier programming, dan dynamic programming.

3. Formulasi Model linier programming

Untuk membuat Fomulasi model linier programming atau sering juga disebut model matematik linier programming,terdapat tiga langkah utama yang harus dilakukan , yaitu;

1. Tentukan variabel keputusan atau variabel yang ingin diketahui dan gambarkan dalam simbul matematik.

2. Tentukan tujuan dan gambarkan dalam satu sel fungsi linier dari variabel keputusan yang dapat berbentuk maksimum atau minimum.

3. Tentukan kendala dan gambar dalam bentuk persamaan linier atau ketidaksamaan linier dari variabel keputusan.

Di dalam model linier programming dikenal dua macam fungsi yaitu fungsi tujuan (objective function) dan fungsi batasan (Constraint function). Fungsi tujuan adalah fungsi yang menggambarkan tujuan atau sasaran didalam permasalahan linier programming yang berkaitan dengan pengaturan secara optimal sumber daya agar dip eroleh keuntungan maksimal atau biaya yang minimal. Pada umumnya nilai yang akan dioptimalkan dinyatakan sebagai Z.

Dalam pembahasan model linier programming digunakan simbol-simbol sebagai berikut :

m : macam batasan-batasan sumber atau fasilitas yang tersedia

n : macam kegiatan yang menggunakan sumber atau fasilitas tersebut

i : nomor setiap macam sumber atau fasilitas yang tesedia(i : 1,2,3,….,m)

j : nomor setiap macam kegiatan yang menggunakan sumber ataufasilitas yang tersedia (j : 1,2,3,…,n)

x j : tingkat kegiatan ke j (j : 1,2,3,…,n)

aij : banyak sumber diperlukan untuk menghasilkan setiap unit keluaran atau output kegiatan j (i : 1,2,3,…,m dan j : 1,2,3,…,n)

bi : banyak sumber ( fasilitas ) i yang tersedia untuk dialokasikan ke setiap unit kegiatan (i : 1,2,3,…,n)

Z : nilai yang dioptimalkan ( maksimum atau minimum)

Cj : kenaikan nilai Z apabila ada pertambahan tingkat kegiatan dengan satu satuan atau merupakan sumbangan setiap satuan keluaran kegiatan j terhadap nilai Z

Tabel 1. Data untuk model linier programming

Kegiatan Sumber	Pemakaian sumber per unit (keluaran) 1 2 3 ...... n	Kapasitas produksi
1	a11 a12 a13 ..... a1n	b1
2	a21 a22 a23 ..... a2n	b2
3	a31 a22 a23 ..... a3n	b3
.....	..... ..... ..... ..... ......	......
M	am1 am2 am3 .... amn	bm
∆Z : pertambahan tiap unit Tingkat kegiatan	C1 C2 C3 .... Cn X1 X2 X3 ..... Xn

Atas dasar pengertian diatas maka dapat dirumuskan model matematis sebagai berikut :

Fungsi tujuan :

Maksimasi Z = C1X1 + 2X2 + C3X3 + …. + CnXn ...............( 1 )

Minimasi Z = C1X1 + C2X2 + C3X3 + …. + CnXn.............( 2 )

Batasan-batasan :

a. a11x1 + a12x2 + a13x3 + …. + a1mXn < b1 ...............( 3 )

b. a21x1 + a22x2 + a23x3 + …. + a2mXn < b2 ................( 4 )

c. am1x1 + am2x2 + am3x3 + … .+ amnXn < bm ................ ( 5 )

x1 > 0, x2 > 0

2.2 Metode Simplek

A. Pendahuluan

Ø Metode simpleks adalah suatu prosedur aljabar (yang bukan secara grafik) untuk mencari nilai optimal dari fungsi tujuan dalam masalah optimasi yang terkendala.

Ø Perhitungan dalam metode simpleks didasarkan pada aljabar matriks, terutama mencari invers matirks untuk penyelesaian persamaan linier simultan, oleh karena itu penyelesaian optimal dengan metode simpleks diawali pengubahan kendala pertidaksamaan menjadi persamaan.

Ø Untuk mencari nilai optimum dengan menggunakan metode simpleks dilakukan dengan proses pengulangan (iterasi) dimulai dari penyelesaian dasar awal yang layak (feasible) hingga penyelesaian dasar akhir yang layak dimana nilai dari fungsi tujuan telah optimum.

B. Persyaratan Metode Simpleks

Terdapat tiga persayaratan untuk memecahkan masalah linier programing, yaitu :

Ø Semua kendala pertidaksamaan harus diubah menjadi persamaan.

Ø Sisi kanan dari tanda pertidaksamaan kendala tidak boleh adanya negatif.

Ø Semua variabel dibatasi pada nilai non negatif.

C. Penulisan Standar dari Metode Simpleks

Berdasarkan ketiga persyaratan di atas, maka kita dapat menulis bentuk standar dari metode simpleks sebagai berikut :

1. Masalah Linier Programing dengan Fungsi Tujuan Maksimisasi.

Sebagai contoh untuk dua variabel dan dua kendala :

Maksimumkan : p = C₁ X₁ + C₂X₂

Dengan Kendala:

Bentuk standar metode simpleks di atas dapat ditulis menjadi :

a. Fungsi tujuan bentuk eksplisit diubah menjadi bentuk implisit.

- p + C₁ X₁ + C₂ X₂ = 0

b. Kendala bentuk pertidaksamaan (tanda £) diubah menjadi persamaan dengan cara menambahkan variabel slack pada ruas kiri, sehingga menjadi :

dimana : S₁ dan S₂ adalah variabel slack (non negatif).

a. Dalam notasi matriks, kita peroleh :

b. Tabel Simpleks Pertama

Tabel 2. Tabel simpleks pertama

Variabel Dasar	p	X₁ X₂ S₁ S₂	Nilai kanan (konstanta)
p S₁ S₂	-1 0 0	+C₁ +C₂ 0 0 a₁₁ a₁₂ 1 0 a₂₁ a₂₂ 0 1	0 K₁ K₂