MEMAKSIMUMKAN HASIL PRODUKSI DENGAN MENGGUNAKAN ALGORITMA SIMPLEKS DALAM PROGRAMASI LINIER Oleh Sri Hartini
tyk pertidaksamaan dipakai sebagai pembatasUntuk memecahkan masalah produksi dalam ilmu ekonomi, dapatdilakukan dengan rumusan matematika yang kemudian diselesaikan dengan Algoritma Simpleks. Dimulai dari permasalahan produksi yang ingin memaksimumkan suatu
tujuan diubah kedalam rumusan matematis dengan bentuk persamaan dan pertidaksamaan. Bentuk persamaan dipakai sebagai fungsi tujuan (Z)yang akan dimaksimumkan, sedangkan ben-
Pendahuluan Dalam ilmu e\onomi seringkali diiumpai beberapa masalah yang menyangkut di bidang pajak, subsidl, devisa, produksi dan sebagainya'
Untuk masalah produksi banyak kaitannya dengan sumber-sumber yang terbatas, misalnya terbatasnya waktu, biaya, bahan, material dan
sebagainya. Disisi lain dengan terbatasnya sumber-sumber tersebut, mengharapkan pendapatan yang maksimum. Sesuai pendapat Bambang Sugiarto (1986: 15), ilmu ekonomi adalah ilmu yang mempelajari cara bagaimana mempergunakan benda-benda yang serba terbatas sehingga bisa dicapai suatu kemakmuran. Dengan mengalokasikan sumber-sUmber yang terbatas, tetapi dapat mencapai tujuan yang diinginkan, merupakan teknik matematika yang dinamakan programasi matematika. Dalam halkhusus, apabila pengukuran dari tujuan yang diinginkan merupakan fungsi linier,
demikian juga kendala atau sumber yang
A4
an-pembatasan yang ada didalam permasalahan produksi tersebut. Setelah itu pertidaksamaanpertidaksamaan diubah kedalam bentuk persamaan-persamaan dengan menambahkan variable Slack (Si) dan diubah lagi kedalam bentuk
matriks. Dari bentuk matriks tersebut diubah kedalam bentuk tabel Algoritma Simpleks dan kemudian dilakukan operasi melalui proses pivoting dengan metode eliminasi Gauss'
terbatas merupakan fungsi linier, maka programasi itu disebut programasi linier. Menurut \,Van Usman (1985:5.1) yang dimaksud programasi linier adalah memaksimumkan atau meminimumkan fungsi linier dari beberapa variable utama yang selanjutnya disebut fungsi obyektif , dengan,kendala-kendala atau batasanbatasan yang ada merupakan suatu system pertidaksainaan linier. Sedangkan persoalan program iir-rier yaitu persoalan untuk menentukan besarnya masing-masing nilai variable sedemikian rupa sehingga nilai fungsi tuiuan atau fungsi obyektif yang linier menjadi optimum dengan memperhatikan pembatasanpembatasan yang ada. Pembatasan-pembatas' an ini dinyatakan dalam pertidaksamaan linier Menurut Edi Soewardi (1983:28) yang dimak sud program linier adalah teknik matematit untuk menemukan penggunaan terbaik sumber sumber organisasi. Jadi programasi linier acialat suatu metode untuk mencapai tuiuan sebesar besarnya atau sekecil-keciinya dengan pem batasan-pembatasan yang ada. Jelaslah bahwi Fakultas Keguruan dam llmu Pendidikal
s='
programasi linier merupakan alat untuk memecahkan persoalan-persoalan ekonomi secara kwantitatif. Persoalannya adalah bagaimana didalam keadaan yang serba terbatas itu masih bisa mencapai sesuatu yang sebaik-baiknya. Penggunaan Algoritma Simpleks dalam memecahkan persoalan programasi linier merupakan alternative lain jika persoalan tersebut tidak bisa diselesaikan dengan menggunakan grafik. Sebagaimana diketdhui, menggunakan grafik hanya dapat digambar untuk persoalan yang mempunyai dua variable (bidang datar) atau persoalan yang dualnya mempunyai dua variabel dan yang tiga variable (dalam ruang) sulit dilakukan. Secara umum persoalan program linier dapat diselesaikan dengan menggunakan Algoritma Simpleks dengan persoalan yang mempunyai lebih dari atau sama dengan 2 variabel.
Fembahasan Algoritma Simpleks adalah suatu metode atau prosedur perhitungan rJrntuk menentukan penyelesaian pada suatu system persamaan guna menentukan optimalitas dari penyelesaian tersebut. Menurut Bambang Sugiarto (i986:38) Algoritma adalah suatu himpunan kaidah-kaidah atau prosedur yang sistimatis untuk mendapatkan penyelesaian pada suatu persoalan. Sedangkan meiode Simpieks adalah suatu cara yang didasarkan atas aljabar matriks dengan melalui proses dengan menggunakan metode eliminasi Gauss. Salah satu interpretasi yang
dapat diberikan pada persoalan prograrnasi linier adalah persoalan maksimisasi keuntungan didalam batasan. Ini berarti fungsi tujuan itu adalah fungsi keuntungan yang secara umum ditulis : Z = CL X1 + CZ XZ + C3 X3 .....Cn Xn untuk persoalan yang mernpunyaivariabel. X1, X2. X3. ......Xn maslng-masing menunjukkan banyaknya barang yang dihasilkan, sedangkan C1 , C2. C3......Cn adalah ke-
Univrrcltaa
tYi
ralodra ln dramayu
untungan yang diperoleh dari pengahasilan per unit barang. Batasan input yang tersedia ditulis dalam bentuk pertidaksamaan : a 11 X1 + a 72X2 + a f3 XS a 21 Xl + a22X2 + a23X3
+ ......+ a 1n Xn d" hl + .......+ aZnXnd,,h2 a 31 X1 + a 32X2 + a 33 X3 +.......+ a 3n Xn d" h3 l a m1
Xl + amZX2
+ a m3 X3 + ......+ a mn Xn d"
hrlr
Karena XL,X2, X3 ........Xn merupakan out put yang dihasilkan, maka interpretasi yang dapat diberikan kepada a ij adalah banyaknyg input ke I yang diperlukan untuk menghasilldar: satu unit barang ke j. Sedangkan hi adiilHh banyaknya input ke I yang tersedia dari bat&sun tersebut. Artinya pembatasan input itu iltHd{ boleh melebihi hi. Dengan demikian untuk menghasilldon m macam barang dengan memakai m macarn-rifnput yang masing-masing berjumlah tertie*ao;. adalah dengan mencari nilai-nilai X'y.angi maksimum. Untuk memaksimumkan suatu masal#h produksi dengan menggunakan Algoritrnee Simpleks pada prograrnasi linier, dapat dlliH*i pada persoalan berikut : Misalnya: Suatu pabrik mebel membuat 3 mmarn meja, yaitu meja makan (X1), meja,tbrntu (X2) dan meja kantor (X3) Meja maliarr. memerlukan 3 jam untuk mengamplasd*rrr 1 jam untuk mengecat. Meja tamu memerirlukan 1 jam untuk mengamplas dan 5 jfm untuk mengecat. Meja kantor memerlukmr-r 3 jam untuk mengamplas dan 2 jam untulk mengecat. Keuntungan margin untuk mejila makan adalah $ tS per unit, untuk meign tamu $ 20 per unit dan untuk meja kanton^ $ 24 per unit.
Bagaimanakah mengalokasikan wal{trrr produksi, sehingga mendapatkan keuntungun margin yang maksimum, jika tersedia 120,jgrm untuk mengamplas dan 60 jam untuH,. mengecat?
&
Penyelesaian
:
Pada tahap awal, dibuat tabel keperluan waktu yang digunakan untuk membuat meja
Waktu
Meja Makan
Meja Tamu
Meja Kantor
Persediaan
Mengamplas Mengecat
3
1
1
5
3 2
L20 60
Keuntungan Margin
$rs
$zo
$z+
Jika banyaknya meja makan (X1), banyaknya meja tamu (X2) dan banyaknya meja kantor (X3), maka tabel berikutnya sebagai berikut : Waktu
Meja Makan
Meja Tamu
Meja Kantor
Persediaan
Mengamplas Mengecat
3Xl
x2 5X2
3X3
x1
t20
2X3
60
Keuntungan Margin
$rs
$zo
$zq
Rumusan matematispya
: Fungsi tujuan
:
: Maksimumkan Z= 15 X1 + 20X2 + Dengan pembatasan 3 Xl + X2 + 3 X3 d" 120
:
24X3
X1 +5X2+2X3d" 60 X1,X2,X3 e" 0 Dua pertidaksamaan pertama merupakan konstren-konitren teknis yang ditetapkan oleh tersedianya input, sedangkan pertidaksamaan X1,X2,X3 e" 0 merupakan konstren ketidaknegatifan untuk menghindarkan harga negative.
Langkah penggunaan Algoritma Simpleks
1)
:
Mengubah pertidaksamaan menjadi persamaan dengan menambah variable-variabel slack.(Si) dimana Si adalah suatu harga positif yang sama dengan selisih antara a 11 X1 + alZ X2 + a 13 X3 ...... dan hi
:
3 X1 +X2 + 3 X3 + 51 : 120 X1 + SXZ + 2 X3 + 52: 60
46
Fakultas i(eguruan dan l:mu Pendidikan
2) Mengubah
persamaan-persamaan konstren dalam bentuk matriks
x1
1310x220 x3: 520rsl60 S2 3) Membuat tabel simpleks permulaan yang terdiri dari koefisien matriks dan vector kolom dari konstan. Tambahkan baris indicator yaitu negative dari koefisien-koefisien fungsi tujuan dan suatu koefisien nol untuk masing-masing variable slack. Elemen kolom konstan dari baris terakhir juga nol, sesuai ciengan nilai dari fungsi fujuan/fungsi obyektif asal (X1 = X2: X3 = 0)
4)
Selanjutnya elemen pivot diubah menjadi angka 1 yaitu kalikan baris ke 2 Dengan l/2 , diperoleh tabel berikut :
x1 x2 x3 51 52 3 1 310 t/z ZYz (1) 0 Yz -15 -20 -24 0
Konstan
120 30
Setelah mereduksi elemen pivot menjadi 1,
selesaikan elemen yang lain pada Kolom pivot diubah menjadi angka nol, yaitu pada baris 1 kurangkan 3 kali baris 2 dan pada baris 3 tambahkan? kalibaris 2, diperoleh tabel berikut :
Pivoting
Pivoting adalah proses penyelesaian m persamaan dalam n variable, meliputi Pengubahan elemen pivot menjadi 1 dan semua elemen-elemen lainnya dalam Kolom
pivot diubah menjadi nol, seperti dalam metode eliminasi Gauss.
Indikator negative dengan harga absolute yang terbesar merupakan kolom pivot. Untuk menentukan elemen pivot yaitu dengan mengambil rasio terkecildari Hasil bagi dari elemen-elemen kolom konstan dengan elemen-elemen kolom Pivot, jadi pada persoalan ini, kolom pivot pada kolom dengan elemen indicator (-24) dan elemen pivot adalah rasio terkecil dari (120/3,60/ 2: 40,30 )maka Baris ke 2 kotom ke 3 merupakan elemen pivot.
Universitas Wiralodra lndramayu
Selagi pada elemen baris indicator masih ada yang bertanda negative, maka dilakukan pivoting kembali. Karena -3 dalam kolom pertama merupakan satu-satunya indicator negative, maka elemen pivotnya adalah rasio terkecil dari (30/l 1/2,30/ Yz = 20, 60), jadi (11/z) menjadi elemen pivot berikutnya. Selanjuinya elemen pivot diubah ke angka 1, yaitu kalikan baris 1 dengan 2/3, diperoleh tabel berikut: Konstan
47
Setelah mereduksi eiemen pivot menjadi angka 1. selesaikan elemen pivot yang lain pada kolom pivot diubah ke angka nol, yaitu pada baris 2 kurangkan 1/zkali baris 1 dan
Adapun langkah-langkah dalam menggunakan algoritma simpleks pada persoalan program linier untuk memaksimumkan suatu tujuan adalah :
pada baris 3 tambahkan 3 kali baris 1, diperoleh tabel berikut
-
Konstan
-
Buat rumusan persoalan kedalam rumusan matematika, yaitu dalam bentuk persamaan untuk fungsi tujuan yang dimaksimumkan dan dalam bentuk pertidaksamaan untuk pembatasan.
-
Ubahlah pertidaksamaan menjadi persamaan dengan menambahkan variable slack, kemudian ubahlah ke bentuk matriks.
-
Dari bentuk matriks, ubahlah ke bentuk
2/3
-7/3
-1
0
Pada tabel tersebut, elemen baris indica-
tor atau elemen pada baris terakhir tidak ada elemen yang bertanda negative. Dengan demikian pivoting atau proses perhitungan selesai.
Jadi secara matriks nilai X1 = 20, X2: 0, X3 : 20 dan Z - 780. Dengan demikian pada tabel terakhir ini memberikan jaWaban bahwa, agar mendapatkan keuntungan yang maksimum dengan terbatasnya waktu yang tersedia, maka pabrlk mebel tersebut harus memproduksi meja makan sebanyak 20 unit, meja tamu sebanyak 0 unit dan meja kantor sebanyak 20 unit. Sehingga akan diperoleh keuntungan margin sebesar $ ZSO dengan hasil perhitungan dari fungsi tujuan : Z : 15 X1 + 20 X2 + 24 X3 Z: 15 (20) + 20 (0) + 24 (20): 300 +
-a 0+480:780. Penutup
Buat tabel sesuai dengan keperluan dan pembatasan yang tersedia dalam persoalan yang diinginkan.
:
tabel simpleks dengan menambah baris indicator.
-
Lakukan pivoting berulang sampai pada tahap elemen baris indicator tidak ada yang bertanda negative.
-
Tabel terakhir menunjukkan hasil yang dicari yaitu nilai maksimum dari fungsi tujuan dan variable-variabel keputusan yang diinginkan.
Daftar Pustaka Bambang Sugiarto. 1986.Linear Programing. Universitas Sebelas Maret Surakarta.
Edi Soewardi, K. 1983. Linear Programing. Sinar Baru Bandung. Wan Usman, MA. 1985. Programasi Linier. Universitas Terbuka. Karunika Jakarta.
Dapat disimpulkan bahwa memaksimumkan hasil produksi dengan menggunakan algoritma simpleks pada programasi linier diperlukan pengetahuan mengenai matriks dan perhitungan dalam proses menggunakan metode eliminasi Gauss, dan juga pada proses pivoting.
4A
Fakultas Keguruan dan llmu Pendidikan