Matematika Sains Volume 2 Nomor 2 Tahun 2024
APLIKASI ALJABAR LINIER PADA PEMROGRAMAN LINIER
Mirtawati Program Studi Matematika FST Universiatas Islam As-SyafiAoiyah Jakarta e-issn: 2987-2979 DOI: https://doi.
org/10.
34005/ms.
ABSTRAK
Pemrograman linier merupakan model matematika untuk menentukan harga ekstrim dari fungsi fungsi linier, bila variabelnya harus memenuhi satu atau lebih kendala dalam bentuk persamaan atau Penyelesaian masalah pemrograman linier dengan metode simpleks adalah metode yang paling popular diantara metode penyelesaian yang lain.
Makalah ini juga menuliskan metode simpleks untuk menyelesaikan pemrograman linier namun dengan penekanan pada aplikasi aljabar linier pada metoda simpleks.
Keyword : Pemrograman Linier.
Sistem Persamaan Linier.
OBE
PENDAHULUAN
Pemrograman linier merupakan salah satu metoda pemecahan masalah di dalam operasi riset .
Pemrograman linier berkaitan dengan perencanaan alokasi sumber sumber terbatas seperti bahan baku, dana atau hasil produksi untuk didistribusikan ke dalam kegiatan yang kompetitif dan layak dengan tujuan mencapai hasil yang optimal (Ayuningsih et al.
, 2.
Pemrrograman linier terstuktur menurut tiga .
rangkaian unsur dasar yaitu :
Decision variables dan parameter Decision variables adalah peubah yang tidak diketahui besarnya dan harus dipecahkan dalam model, sedangkan yang dimaksud parameter adalah peubah dalam system dapat bersifat deterministik dan probabilistik Fungsi Kendala Dengan memperhitungkan limit fisik suatu system, maka suatu model harus membatasi Decision variables pada nilai yang feasible .
Fungsi Tujuan Fungsi Tujuan adalah tolak ukur efektifitas suatu system sebagai fungsi matematika dari Decision variables, dinotasikan dengan yc Pemecahan masalah pemrograman linier dapat dilakukan dengan berbagai cara diantaranya cara geometris, namun cara ini tidak cukup praktis, bahkan tidak dapat dilakukan untuk lebih tiga variable.
Cara lainnya adalah dengan metode simpleks .
implex metho.
Pemecahan masalah dengan metode simpleks dapat dilakukan pada sebarang jumlah variable.
Pemecahan masalah dengan metode simpleks banyak menggunakan konsep aljabar linier seperti matriks dan sistem persamaan linier.
Artikel ini menjelaskan penggunaan aljabar linier pada penyelesaian masalah pemrograman linier dengan metode simpleks.
Aplikasi akan diberikan pada Matematika Sains Volume 2 Nomor 2 Tahun 2024 masalah pemrograman linier dengan 3 variabel.
II.
PUSTAKA
Pemrograman Linier Pemrograman linier adalah menentukan harga ekstrim dari fungsi fungsi linier, bila variabelnya harus memenuhi satu atau lebih kendala dalam bentuk persamaan atau pertidaksamaan.
Model pemrograman linier memiliki bentuk standar sebagai berikut :
Fungsi tujuan : mengoptimalkan fungsi berikut :
ycs = yca1 ycu 1 yca2 ycu 2 U yca3 ycu 3 Yang memenuhi syarat kendala :
yca11 ycu 1 yca12 ycu 2 U yca1ycu ycu ycu = yca1 yca21 ycu 1 yca22 ycu 2 U yca2ycu ycu ycu = yca2 ycayco1 ycu 1 ycayco2 ycu 2 U ycaycoycu ycu ycu = ycaycu ycu ycn Ou ycu untuk ycn = 1, 2.
A ycu Dengan :
ycs = nilai fungsi tujuan ycayc = sumbangan per unit kegiatan, untuk masalah maksimasi ycaj akan menunjukkan keuntungan atau penerimaan per unit, sedangkan untuk minimasi akan menunjukkan biaya per Ae unit.
ycuyc = banyaknya kegiatan, yc = 1,2, .
ycu ycaycnyc = banyaknya sumber daya ycn yang dikonsumsi sumber daya j ycaycn = Jumlah sumber daya, ycn = 1,2, .
ycu Konsep Aljabar Linier dalam Pemrograman Linier Bentuk standar pemrograman linier, dapat dituliskan dalam notasi matriks berikut :
Optimalkan fungsi tujuan :
ycs = yaycycU Syarat kendala : yaycU = yaA ycUOu0 Definisi:
Suatu vektor ycu1 ycu ycU = ( U2 ) ycuycu Matematika Sains Volume 2 Nomor 2 Tahun 2024 dinamakan pemecahan dasar dari system linear yaycU = yaA jika n = m Definisi :
Operasi baris elementer (OBE) dapat diterapkan dalam suatu matriks, dengan menggunakan salah satu dari operasi berikut :
Kalikan baris ycn dengan scalar yco O 0 Jumlahkan perkalian pada1, dengan baris lainnya Pertukarkan dua baris Definisi :
Dalam sebuah pemrograman linier standar, sebuah pemecahan yang mugkin yang juga merupakan pemecahan dari system yaycU = yaA dinamakan basic feasible solution i.
METODOLOGI :
Pemrograman linier memiliki tujuan khusus yaitu mengoptimumkan fungsi tujuan.
Untuk memdapatkan nilai optimum dari fungsi tujuan tersebut, maka tahap Ae tahap berikut dapat dilakukan.
Transformasikan persamaan pemrograman linier kedalam persamaan bentuk standar, caranya adalah sebagai berikut :
Konversikan masalah minimasi menjadi masalah maksimasi dengan mendefinisikan ulang fungsi tujuan, yaitu : ycA = Oeyc Ubahlah pertidaksamaan Ou menjadi O pada persamaan kendala dengan mengalikan persamaan dengan -1.
Ubahlah pertidaksamaan O menjadi sama dengan (=) pada persamaan kendala dengan menambahkan variable slact pada kedua ruas.
Untuk setiap variable slack yang digunakan, ditetapkan koefisien ycaycn = 0 pada fungsi tujuan, ini dimaksudkan agar nantinya nilai variable slack pada fungsi tujuan tidak akan mempengaruhi hasil fungsi tujuan.
Transformasikan persamaan bentuk standar kedalam bentuk system persamaan linier, dengan aturan persamaan fungsi tujuan diletakkan dibawah persamaan syarat kendala atau sebaliknya, fungsi tujuan diletakkan di baris paling atas.
Transformasikan system persamaan linier kedalam bentuk matriks Tentukan penyelesaian matriks untuk mendapatkan nilai optimum, perolehan nilai optimum ditandai dengan baris terakhir atau naris paling atas .
ungsi tujua.
sudah tidak lagi mengandung nilai negative.
IV.
HASIL DAN PEMBAHASAN
Model dengan Pemrograman linier akan memiliki persamaan yang mungkin saja dapat dengan mudah dicari solusinya, tetapi juga tidak jarang sulit diselesaikan hingga tidak diperoleh solusinya.
Sebagai Matematika Sains Volume 2 Nomor 2 Tahun 2024 ilustrasi dibawah ini akan diberikan dua macam model pemrograman linier :
Misal diberikan permasalahan pemrograman linier untuk memaksimumkan fungsi tujuan yc dari persamaan berikut :
yc = 3ycu 1 4ycu 2 2ycu 3 Dengan syarat kendala :
3ycu 1 2ycu 2 4ycu 3 O 15 3ycu 1 2ycu 2 3ycu 3 O 7 Dan : ycu 1 , ycu 2 , ycu 3 Ou 0 2ycu 1 ycu 2 ycu 3 O 6 Karena pada permasalahan pemrograman linier diatas persamaan kendalanya sudah dalam bentuk O, maka untuk memperoleh bentuk standar hanya tinggal melakukan langkah c, sehingga diperoleh persamaan bentuk standar sebagai berikut :
yc = 3ycu 1 4ycu 2 2ycu 3 0ycu 4 0ycu 5 0ycu 6 Dengan syarat :
3ycu 1 2ycu 2 4ycu 3 ycu 4 = 15 3ycu1 2ycu 2 3ycu 3 ycu 5 = 7 2ycu 1 ycu 2 ycu 3 ycu 6 = 6 Dan :
ycu1, ycu2 , ycu3, ycu4, ycu5, ycu6 Ou 0 Tahap selanjutnya adalah mentranformasi persamaan bentuk standar menjadi bentuk system persamaan linier, yaitu :
3ycu 1 2ycu 2 4ycu 3 ycu 4
= 15
3ycu1 2ycu 2 3ycu 3
= 7
2ycu 1 ycu 2 ycu 3 ycu5 ycu6 = 6 Oe3ycu1 Oe 4ycu2 Oe 2ycu3 0 ycu4 0ycu5 0ycu6 yc = 0 Bentuk matriks dari system persamaan linier diatas adalah :
Matematika Sains Volume 2 Nomor 2 Tahun 2024
Oe3
Oe4 Oe2
1 0 0
0 1 0
0 0 0
0 0 0
3 = ( 7 )
ycu4 ycu .
cu 6 ) Atau dalam bentuk matriks yang diperbesar :
ycu1 ycu2 ycu3 ycu4 Oe3 Oe4 Oe2 ycu5 ycu6 yc 0 15 ycu 4 7 ) ycu5 0 6 ycu6 0 0 ycs ycaycn Perhatikan baris yc .
aris terakhi.
, perhatikan pula kolom dari bilangan negatif terbesar dari baris tersebut .
cu 5 ), bagilah setiap elemen kolom ycaycn dengan setiap elemen kolom ycu 2 .
engan meniadakan pembagian pada baris terakhi.
, pilihlah nilai paling kecil, diperoleh nilai paling kecil terletak di baris ycu 5 kolom ycu 2 , selanjutnya :
Karena hasil operasi bagi elemen terkecilnya berada di baris ycu5, maka lakukan operasi bagi setiap elemen pada baris ycu5 dengan elemen pada baris ycu5 kolom ycu2 Membuat sisa elemen pada kolom ycu2 sama dengan 0.
Dengan OBE sehingga ycu1 ycu2 ycu3 ycu4 ycu5 ycu6 yc ycaycn ycu6 ycs Oe Oe ycu4 ycu2 Perhatikan kembali baris z, perhatikan pula kolom dari bilangan yang masih negatif dari baris tersebut, kemudian ke iterasi selanjutnya dengan cara yang sama, maka diperoleh hasil sebagai berikut :
Matematika Sains Volume 2 Nomor 2 Tahun 2024 ycu1 ycu2 ycu3 ycu4 Oe ycu5 ycu6 Oe Oe yc ycaycn 3 ycu4 3 ycu2 ycu1 ycs Oe Perhatikan kembali baris z, terlihat bahwa setiap elemen di dalam baris z sudah tidak mengandung nilai negative .
engan meniadakan elemen paling kana.
maka dapat dikatakan bahwa nilai optimum pada permasalahan pemrograman linier telah diperoleh ycu1 = , ycu 2 = , ycu 3 = 0, ycu 4 = ,yc = Atau dengan meniadakan variable slack, nilai optimumnya adalah :
ycu1 = , ycu 2 = , ycu 3 = 0, yc = Misal diberikan permasalahan pemrograman linier untuk memaksimumkan fungsi tujuan z dari persamaan berikut :
yc = 3ycu 1 Oe ycu 2 4ycu 3 Dengan syarat kendala:
2ycu 1 Oe 2ycu 2 3ycu 3 O 5 ycu 1 4ycu 2 Oe 2ycu 3 O 1 Dan :
3ycu 1 6ycu 3 O 4 3ycu 1 6ycu 3 O 4 ycu1, ycu2 , ycu3 Ou 0 Karena pada permasalahan pemrograman linier diatas persamaan kendalanya sudah dalam bentuk O, maka untuk memperoleh bentuk standar hanya tinggal melakukan langkah yca, sehingga diperoleh persamaan bentuk standar sebagai berikut :
Matematika Sains Volume 2 Nomor 2 Tahun 2024 yc = 3ycu 1 Oe ycu 2 4ycu 3 0ycu 4 0ycu 5 0ycu 6 Dengan Syarat:
2ycu 1 Oe ycu 2 4ycu 3 ycu 4 ycu 1 4ycu 2 Oe 2ycu 3 3ycu 1 ycu5 6ycu 3 ycu6 = 4 ycu1, ycu2 , ycu3, ycu4, ycu5, ycu6 Ou 0 Dan :
Tahap selanjutnya adalah mentranformasi persamaan bentuk standar menjadi bentuk system persamaan linier, yaitu:
2ycu 1 Oe ycu 2 4ycu 3 ycu 4 ycu 1 4ycu 2 Oe 2ycu 3 3ycu 1 ycu5 6ycu 3 ycu6 = 4 Oe3ycu 1 ycu 2 Oe 4ycu 3 0ycu 4 0ycu 5 0ycu 6 yc Bentuk matriks dari system persamaan linier diatas adalah :
Oe3 Oe1 Oe4 Oe2 0 0 1 ycu2 0 0 0 ] ycu 3 = .
1 0 0 ycu4
0 1 0
cu6 ] Atau dalam bentuk matriks yang diperbesar :
ycu1 ycu2 ycu3 ycu4 ycu5 ycu6 yc ycaycn Oe3 Oe4 Oe1 ycu4 Oe2 ycu5 ycu6 Matematika Sains Volume 2 Nomor 2 Tahun 2024 Perhatikan baris z .
aris terata.
, perhatikan pula kolom dari bilangan negatif terbesar dari baris tersebut .
cu 3 ), bagilah setiap elemen kolom ycaycn dengan setiap elemen kolom ycu 3 .
engan meniadakan pembagian pada baris terata.
, pilihlah nilai paling kecil, diperoleh nilai paling kecil terletak di baris ycu 6 kolom ycu 3 , selanjutnya :
Karena hasil operasi bagi elemen terkecilnya berada di baris ycu 6, maka lakukan operasi bagi setiap elemen pada baris ycu 6 dengan elemen pada baris ycu6 kolom ycu3 Membuat sisa elemenv pada kolom ycu 3 sama dengan 0, dengan OBE sehingga ycu1 ycu2 ycu3 ycu4 ycu5 Oe1 Oe1 ycu6 Oe yc ycaycn ycu4 ycu5 ycu3 Perhatikan kembali baris z, perhatikan pula kolom dari bilangan yang masih negatif dari baris tersebut, kemudian lakukan operasi yang sama di iterasi selanjutnya, maka diperoleh hasil sebagai berikut:
ycu1 ycu2 ycu3 ycu4 Oe2 ycu5 ycu6 Oe Oe yc ycaycn ycu4 ycu1 ycu3 Perhatikan kembali baris z, terlihat bahwa setiap elemen di dalam baris z sudah tidak mengandung nilai negative .
engan meniadakan elemen paling kana.
maka dapat dikatakan bahwa nilai optimum pada permasalahan pemrograman linier telah diperoleh Matematika Sains Volume 2 Nomor 2 Tahun 2024 ycu1 = , ycu2 = 0 , ycu3 = , ycu4 = ,yc = Atau dengan meniadakan variable slack, nilai optimumnya adalah :
ycu1 = , ycu2 = 0 , ycu3 = ,yc = SIMPULAN Model pemrograman linier merupakan model matematika untuk menentukan harga ekstrim dari fungsi fungsi linier, bila variabelnya harus memenuhi satu atau lebih kendala dalam bentuk persamaan atau pertidaksamaan.
Penyelesaian model pemrograman linier dengan menggunakan metode simpleks, sama artinya dengan menggunakan aljabar linier dengan perlakuan tertentu untuk menyelesaikan permasalahan.
Konsep aljabar linier yang digunakan antara lain matriks, system persamaan linier juga Operasi baris elementer.
Dari dua ilustrasi yang diberikan pada hasil dan pembahasan menunjukkan bahwa tidak ada perbedaan jumlah iterasi bila fungsi tujuan .
diletakkan pada baris paling bawah atau baris paling atas pada system persamaan linier
DAFTAR PUSTAKA