Kelompok 1 PL [PDF]

Citation preview

MAKALAH PROGRAM LINIER METODE SIMPLEKS DALAM NOTASI MATRIKS



Disusun Oleh : Kelompok 1



1. Mirza Luffita Sari



(190406002)



2. Apulina Br Saragih



(190406008)



3. Piki Mulani



(190406016)



4. Aulia Dhea Dermawan (190406024)



Dosen Pengampu Fadillah, S.P.,S.Pd.,M.Pd



PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERISTAS SAMUDRA 2021



KATA PENGANTAR



Puji serta syukur penulis ucapkan kehadirat Tuhan Yang Maha Kuasa, atas limpahan anugerah-Nya, sehingga kelompok 1 dapat menyelesaikan tugas makalah pada mata kuliah Program Linier yang berjudul Metode Simpleks Dalam Notasi Matriks. kami mengucapkan terimakasih kepada Ibu Fadillah, S.P.,S.Pd.,M.Pd selaku dosen pengampu yang telah membimbing kami



dalam pengerjaan makalah. Kami menyadari



sepenuhnya bahwa dalam penulisan makalah ini masih jauh dari kesempurnaan, oleh karena itu kami mengharapkan kritik dan saran yang bersifat membangun demi kesempurnaan di masa akan datang. Akhir kata, semoga makalah ini bermanfaat bagi kita semua dan penulis selaku penyusun dan bagi pembaca penulis minta maaf jika terjadi kesalahan. Akhir kata kami ucapkan terima kasih.



Langsa, 27 November 2021



Kelompok 1



i



DAFTAR ISI



KATA PENGANTAR..............................................................................................................i DAFTAR ISI............................................................................................................................ii BAB I PENDAHULUAN........................................................................................................1 1.1 Latar Belakang..............................................................................................................1 1.2 Rumusan Masalah.........................................................................................................1 1.3 Tujuan...........................................................................................................................1 BAB II PEMBAHASAN..........................................................................................................2 2.1 Bentuk Standar Program Linier Secara Umum............................................................2 2.2 Beberapa notaasi matriks .............................................................................................6 2.3 Penyajian LP Dalam Notasi Matriks Bentuk Standar Vs Notasi Matriks Hasil Pemisahan Sesuai Solusi Pada Tahap Optimal/Suboptimal.........................................9 2.4 contoh soal dalam notasi matriks.................................................................................. 12 BAB II PENUTUP...................................................................................................................17 3.1 Kesimpulan....................................................................................................................17 3.2 Saran..............................................................................................................................17 DAFTAR PUSTAKA...............................................................................................................18



ii



BAB I PENDAHULUAN



1.1 Latar Belakang Program linier adalah suatu cara matematis yang digunakan untuk menyelesaikan masalah yang berkaitan dengan pengalokasian sumber daya yang terbatas untuk mencapai optimasi, yaitu memaksimumkan atau meminimumkan fungsi tujuan yang bergabung pada sejumlah variabel input. Penerapan program linier banyak diterapkan dalam masalah ekonomi, industri, sosial dan lain-lain. Metode penyelesaian program linier dengan metode simpleks pertamakali dikemukakan oleh George Dantzig pada tahun 1947. Metode ini menjadi terkenal ketika diketemukan alat hitung elektronik dan menjadi poluler ketika munculnya komputer. Proses perhitungan metode ini dengan melakukan iterasi berulang-ulang sampai tercapai hasil optimal dan proses perhitungan ini menjadi mudah dengan komputer. Selanjutnya berbagai alat dan metode dikembangkan untuk menyelesaikan masalah program linear bahkan sampai pada masalah riset operasi hingga tahun 1950 an seperti pemrograman dinamik, teori antrian, dan persediaan. 1.2 Rumusan Masalah  Bagaimanakah bentuk standar program linier secara umum?  Apakah yang dimaksud dengan notasi matriks?  Bagaimana cara penentuan solusi menggunakan metode simpleks dalam notasi matriks?  Bagaimanakah contoh pada metode simpleks dalam notasi matriks? 1.3 Tujuan  Mengetahui bagaimana bentuk standar program linier  Mengetahui apa yang dimaksud dengan notasi matriks dan apa manfaatnya  Mengetahui cara penentuan solusi menggunakan metode simples dalam notasi matriks  Mengetahui dan memahami contoh soal pada metode simpleks dalam notasi matriks



1



BAB II PEMBAHASAN 2.1 Bentuk Standar Program Linier Secara Umum max z=c1 x1 + c2 x 2+ …+c n x n s . t . a11 x1 + a12 x 2+ …+a1 n x n=b1 a 21 x1 + a22 x 2+ …+a2 n x n=b2 . . .. . . .. . . .. a m 1 x 1+ am 2 x2 +…+ am 3 x3 =bm



x 1 ≥ 0(i=1,2 , … , n) Bentuk standar suatu program linier yang sudah dalam sebuah persamaan maka kemudian dapat dinyatakan kedalam notasi matriks sebagai berikut : max z=cx s . t . Ax=b x≥0 ⋮ am1 Dari bentuk standar diatas maka diperoleh a. Koefisien Teknologi Koefisien teknologi adalah suatu rasio yang menjelaskan jumlah atau nilai keluaran sektor i yang diperlukan sebagai masukan untuk menghasilkan satu unit keluaran di sektor j. Pada bentuk standar diatas yang menjadi koefisien teknologi yaitu sebagai berikut: A=¿



b. Vektor Variabel 2



x1 x x=¿ 2 ⋮ xn



[]



c. Vektor persediaan sumber daya b1 b b=¿ 2 ⋮ bm



[]



d. Vaktor Biaya/Profit c= [ c1 c 2 ⋯ c n ]



Tabel optimal dari LP Dakota Dalam bentuk tableau berikut: BV ={ s1 , x 3 , x1 } NBV ={x 2 , s2 , s 3 } Tabel 2 Baris 0 Baris 1 Baris 2 Baris 3



z 1 0 0 0



x1 0 0 0 1



x2 5 -2 -2 1.2



x3 0 0 1 0



s1 0 1 0 0



s2 10 2 2 -0.5



5 



Yang setara dengan notasi persamaan berikut: z



+ 5x2 -2x2



+ 10s2 + 10s3 = 280 + s1 + 2s2 – 8s3



-2x2 + x3 x1 + 1.25x2



+ 2s2 – 4s3



= 24 =8



– 0.5s2 + 1.5s3 = 2



3



s3 10 -8 -4 1.5



rhs 280 24 8 2



BV z = 280 s1 = 24 x3 = 8 x1 = 2



Contoh LP Kasus Dakota ( dalam bentuk standar) max z=60 x 1 +30 x 2 +20 x 3+ 0 s 1+ 0 s 2+ 0 s3 s . t . 8 x 1 +6 x 2+ x 3 + s1=48 4 x1 +2 x 2+1,5 x 3 +s 2=20 2 x1 +1,5 x 2+ 0,5 x 3 + s3=8 x 1 , x 2 , x 3 , s1 , s 2 , s3 ≥ 0



Dengan definisi dari matriks dan vektor maka didapatkan sebagai berikut : 8 6 1 1 0 0 A= 4 2 1,5 0 1 0 2 1,5 0,5 0 0 1



[



]



x1 x2 x= x 3 s1 s2 s3



[]



48 b= 20 8



[]



c=[60 3020 0 0 0] Bentuk matriks dari LP dakota max z=cx s . t . Ax=b x≥0 Penentuan notasi matriks yang dipisahkan sesuai solusi pada tahap optimal  Pada tahap optimal, kasus dakota memiliki : BV ={ s1 , x 3 , x1 } NBV ={x 2 , s2 , s 3 } Yang menjadi dasar pemisahan matriks dan vektor komponen penyusun LP.



4



 Vaktor variabel x1 x2 s1 x2 x 3 x= akan dipisah menjadi x BV = x 3 dan x NBV = s2 s1 x1 s3 s2 s3



[]



[]



[]



 Vektor komponen biaya c= [ c1 c 2 c3 c s 1 c s 2 c s3 ] =[60 30 20 0 0 0] Dipisah menjadi : c BV =[ c s 1 c 3 c 1 ]=[0 2060 ] c NBV =¿ c s 3 ¿=[30 0 0]  Matriks koefisien teknologi 8 6 1 1 0 0 A=[ a1 a2 a3 as 1 as 2 a s3 ]= 4 2 1,5 0 1 0 2 1,5 0,5 0 0 1



[



]



Dipisahkan menjadi BV ={ s1 , x 3 , x1 } → {a s1 , a3 , a1 } NBV ={ x 2 , s2 , s 3 } → {a 2 , a s 2 , a s 3 } 1 1 8 B= { as 1 , a3 , a1 }= 0 1,5 4 Sesuai anggota BV 0 0,5 2



[



]



6 0 0 N= { a2 , as 2 , as 3 } = 2 1 0 1,5 0 1



[



]



Sesuai anggota NBV



Setelah semua posisi dirubah kemudia kita kembali ke LP Kasus Dakota ( dalam bentuk standar)



5



max z=60 x 1 +30 x 2 +20 x 3+ 0 s 1+ 0 s 2+ 0 s3 s . t . 8 x 1 +6 x 2+ x 3 + s1=48 4 x1 +2 x 2+1,5 x 3 +s 2=20 2 x1 +1,5 x 2+ 0,5 x 3 + s3=8 x 1 , x 2 , x 3 , s1 , s 2 , s3 ≥ 0 Kemudian bentuk diatas diubah sesuai dengan urutan dari BV ={ s1 , x 3 , x1 } NBV ={x 2 , s2 , s 3 } Sehingga bentuk standarnya berubah menjadi : max z=0 s1 +20 x 3+ 60 x 1 +30 x 2+ 0 s 2+ 0 s3 s . t . s 1+ x 3 +8 x 1+ 6 x 2 +0 s2 +0 s3=48 0 s1 +1,5 x3 + 4 x 1+ 2 x 2+ s 2+ 0 s 3=20 0 s1 +0,5 x 3+ 2 x 1+ 1,5 x 2 +0 s 2 +s 3=8 x 1 , x 2 , x 3 , s1 , s 2 , s3 ≥ 0



2.2 Beberapa Notasi Matriks s1 Dapat dilihat bahwa jika sudah dipisahkan jadi vektornya BV x3 dimana koefisien x1



{}



x2 koefisennya jadi koefisen di B. Demikian juga dengan vektor NBV s 2 dimana s3



{}



koefisen-koefisienya adalah koefisen yang ada di N Setelah diatur ulang maks Z =0 s1 +20 x3 +60 x 1 +30 x2 +0 s2 +0 s3 s1 + x 3+ 8 x1 +6 x 2+ ¿ 48 1.5 x 3+ 4 x 1+ 2 x 2 +s 2=20 0.5 x 3+ 2 x 1 +1.5 x 2 + s3=8 s1 , x 3 , x 1 , x2 , s 2 , s3 ≥ 0 Maks Z



0 s1 +20 x3 +60 x 1 s1 + x 3+ 8 x1 1.5 x 3+ 4 x 1 0.5 x + 2 x



30 x 2+ 0 s 2+0 s3 6



6 x2 2 x2 + s2



s.t



BV



NBV



Kemudian ubah ke dalam bentuk matriks dengan memisahkan variabelnya B



X BV



[ N



[



1 1 8 s1 0 1.5 4 x 3 0 0.5 2 x 1



][ ]



X NBV



6 0 0 x2 2 1 0 s2 1.5 0 1 s3



][ ]



Pemisahan secara lengkap dan sudah melibatkan pemisahan baris 0 maks Z =0 s1 +20 x3 +60 x 1 +30 x2 +0 s2 +0 s3 s.t



s1 + x 3+ 8 x1 +6 x 2=48



1.5 x 3+ 4 x 1+ 2 x 2 +s 2=20 0.5 x 3+ 2 x 1 +1.5 x 2 +s 3=8 s1 , x 3 , x 1 , x2 , s 2 , s3 ≥ 0 Dengan notasi matriks yang sudah dipisahkan s1 x2 Maks Z = [ 0 20 60 ] x 3 + [ 30 0 0 ] s 2 x1 s3



[]



[]



Hasilnya skalar sehingga yang digunakan adalah perkalian vektor baris dikali vektor kolom



7



[



s.t



1 1 8 s1 6 0 0 x2 48 = 0 1.5 4 x 3 + 2 1 0 s2 20 0 0.5 2 x 1 1.5 0 1 s3 8



][ ] [



][ ] [ ]



s1 x2 x3 ≥ 0 s 2 ≥0 x1 s3



[] []



Atau Maks Z = C BV X BV + C NBV X NBV B X BV + NX NBV =b



S.t.



X BV , X NBV ≥ 0



Pemisahan yang tadinya dalam bentuk Maks Z = CX semuanya matriks vektor S.t. AX≤ b Setara dengan pemisahan yang diatas Jika belu diketahui BV dan NBV nya tidak bisa dilakukan pemisahan walaupun setara dengan bentuk standar konsep notasi matriks tidak bisa dilakukan Penggunaan notasi matirks yang diterapkan dalam tablo optimal  Kesetaraan notasi pada tableu optimal z +5 x2 +10 s 2 +10 s 3=280 −2 x2 + s1 +2 s 2−8 s 3=24 −2 x2 + x 3 +2 s 2−4 s 3=8 x 1+ 1.25 x 2−0.5 s2 +1.5 s 3=2  Dengan BV ={ s1 , x 3 , x1 } NBV ={ x 2 , s2 , s 3 }  Baris kendala (selain baris 0/fungsi obyektif) dalam susunan yang dirubah sesuai BV dan NBV: z +0 s 1+ 0 x3 +0 x 1 +5 x2 +10 s 2 +10 s 3=280 1 s1 +0 x 3+ 0 x 1−2 x 2+ 2 s2 −8 s3=24 8



0 s1 +1 x 3 +0 x 1−2 x2 +2 s 2 −4 s3 =8 0 s1 +0 x 3+ 1 x 1+ 1.25 x 2−0.5 s2 +1.5 s 3=2 Atau setelah disusun menurut BV dan NBV bentuknnya menjadi s1−2 x 2+ 2 s2 −8 s 3=24 x 3−2 x 2+2 s2 −4 s3 =8 x 1+ 1.25 x 2−0.5 s2 +1.5 s 3=2 Setelah itu akan ditunjukkan sifat istimewa di BV. Membentuk vektor BV sehingga dapat dituliskan 1 0 0 s1 0 1 0 x3 disebut dengan vektor 0 0 1 x1



[ ][ ]



I. X BV



Vektor X BV berhubungan dengan identitas Tujuan dari operasi matriks nantinya adalah merubah yang menjadi BV supaya mempunyai bentuk kanonik atau X BV . I . Awalnya ada sesuatu akhirnya menjadi identitas. Awalnya B X BV + NX NBV dalam tahapan ini dengan BV yang sudah optimal Cirinya adalah disuatu tahapan tertentu yang jadi BV harus berada dalam bentuk matriks berarti perlu ada perubahan bagaimana bentuk B X BV + NX NBV → I . X BV Koefisen bagi BV berupa bentuk kanonik atau matriks identitas



1 0 0 0 1 0 0 0 1



[ ]



2.3 Penyajian LP Dalam Notasi Matriks Bentuk Standar Vs Notasi Matriks Hasil Pemisahan Sesuai Solusi Pada Tahap Optimal/Suboptimal LP dalam Notasi Matriks Bentuk Standar secara umum : Maks =CX S.t. AX¿ b x≥0 LP (bentuk awal/standar) dalam Notasi Matriks Hasil Pemisahan Sesuai Solusi pada Tahap Optimal/Sub Optimal Maks Z = C BV X BV + C NBV X NBV



9



B X BV + NX NBV =b



S.t.



X BV , X NBV ≥ 0 Dari bentuk ini akan dibentuk solusi pada tahap yang dituju, di mana BV mempunyai bentuk kanonik. Jika BV dan NBV nya diketahui maka dapat merubah bentuk standar yang asli menjadi bentuk yang dipisahkan sesuai BV NBV pada tahapan yang dituju struktur inilah yang digunakan untuk mecari cara atau menjelaskan cara bagaimana merubah bentuk umum menjadi bentuk tahapan yang dituju ditahapan yang dituju X BV harus punya pengali dalam bentuk identitas atau dalam bentuk kanonik a. Konsep Perhitungan Matriks yang dibutuhkan Untuk Baris Kendala  Baris kendala bentuk awal/standar dalam notasi matriks B X BV + NX NBV =b  Koefisien kendala bagi BV pada solusi dengan BV tertentu akan bentuk kanonik, yang berasal dari perkalian : B−1 B=I  Perkalian dilakukan pada seluruh ruas di persamaan kendala notasi matriks bentuk awal/standar B−1 ( B X BV + NX NBV )=B−1 (b) B−1 B X BV + B−1 NX NBV =B−1 ( b ) I . X BV +B−1 NX NBV =B−1 ( b ) X BV + B−1 NX NBV =B−1 ( b )  Sesuai notasi matriks yang sudah didefinisakan sebelumnya : 1 1 8 1 2 −8 −1 2 −4 B= 0 1.5 4 dan invers yang bersesuaian B = 0 0 0.5 2 0 −0.5 1.5



[



]



[



s1 x2 6 0 0 48 N= 2 1 0 , X BV = x 3 , X NBV = s 2 ,b= 20 1.5 0 1 8 x1 s3



[



] [] [] []



X BV + B−1 NX NBV =B−1 ( b )



10



]



s1 1 2 −8 6 0 0 x 2 1 2 −8 48 + = x3 0 2 −4 2 1 0 s2 0 2 −4 20 0 −0.5 1.5 1.5 0 1 0 −0.5 1.5 8 x1 s3



[ ][



][ ] [



][



][ ]



Perhitungan operasi matriks baris kendala pada contoh Dakota X BV + B−1 NX NBV =B−1 b atau I X BV +B−1 NX NBV =B−1 b 1 0 0 s1 1 2 −8 6 0 0 x 2 1 2 −8 48 0 1 0 x3 + 0 2 −4 2 1 0 s 2 = 0 2 −4 20 0 0 1 x 1 0 −0,5 1,5 1,5 0 1 s 3 0 −0,5 1,5 8



[ ][ ] [ [ ][ ] [



][ ] [



][



][ ]



1 0 0 s1 −2 2 −8 x 2 24 + = 0 1 0 x3 −2 2 −4 s 2 8 0 0 1 x 1 1,25 −0,5 1,5 s 3 2



][ ] [ ]



Yang merupakan elemen-elemen baris kendala pada tableau optimal LP Dakota 1 0 0 s1 −2 2 −8 x 2 24 0 1 0 x3 + −2 2 −4 s 2 = 8 0 0 1 x 1 1,25 −0,5 1,5 s 3 2



[ ][ ] [ Tableau 2 Baris 0 Baris 1 Baris 2 Baris 3



z 1 0 0 0



][ ] [ ]



x1 0 0 0 1



x2 5 -2 -2 1.25



x3 0 0 1 0



s1 0 1 0 0



s2 10 2 2 -0.5



s3 10 -s -4 1.5



rhs 280 24 s 2



BV z = 280 s1 = 24 s2 = 8 s3 = 2



X BV + B−1 NX NBV =B−1 b 1 0 0 s1 1 2 −8 6 0 0 x 2 1 2 −8 48 0 1 0 x3 + 0 2 −4 2 1 0 s 2 = 0 2 −4 20 0 0 1 x 1 0 −0,5 1,5 1,5 0 1 s 3 0 −0,5 1,5 8



[ ][ ] [ [ ][ ] [



][



][ ] [ ][ ] [ ]



1 0 0 s1 −2 2 −8 x 2 24 0 1 0 x3 + −2 2 −4 s 2 = 8 0 0 1 x 1 1,25 −0,5 1,5 s 3 2



11



][ ]



 Perhitungan baris kendala solusi untuk BV →pasti dalam bentuk kanonik 1 0 0 Bagi kolom s1 → 0 , bagikolom s2 → 1 , bagikolom x 1 → 0 0 0 1



[]



[]



[]



 Perhitungan baris kendala solusi untuk NBV, dapat dilakukan per kolom dengan hubungan: −2 2 −1 −1 Bagi kolom x 2 → B a2= −2 , bagi kolom s 2 → B a2= 2 1,25 −0,25



[ ] []



[ ] []



−8 24 −1 Bagi kolom s2 → B as = −4 , bagi kolom rhs → B b= 8 1,5 2 Operasi matriks dari tableu awal menjadi tableau pada tahapan tertentu (optimal sub atau sub optimal)  Kolom untuk variabel/peubah xj dalam kendala di tableau tahapan yang dituju: B−1 a j −1



3



 Kolom untuk rhs dalam kendala di tableau tahapan yang dituju: B−1 b Konsep perhitungan matriks yang dibutuhkan untuk baris nol (fungsi obyektif)  Bentuk awal/standar dalam notasi matriks max z=¿ C BV X BV +C NBV X NBV ¿ s ∙t ∙ BX BV + NX NBV =b X BV , X NBV ≥ 0  Perhatikan fungsi obyektif yang sudah diubah menjadi notasi baris nol bentuk awal: z−BX BV −NX NBV =0  Pada tableau tahapan tertentu (optimal/sub optimal) sesuai BV yang dituju: Koefisien baris nol BV akan bernilai nol melalui proses eliminasi dengan baris kendala Koefisien baris nol NBV ≠ 0, berubah mengikuti operasi hitung proses eliminasi 2.4 Contoh Soal Dalam Notasi Matriks contoh LP yang Cuma melibatkan 2 variabel , Bentukan awal LP : Max z = x1 + 4x2 s.t x1+ 2x2 ≤6 12



2x1 + x2≤8 x1,x2 ≥0 Diketahui solusi optimal mempunyai: BV = { x2 , s2 } , NBV ={ X1 + S1 } Tentukan tableau optimal dengan menggunakan metode matriks! Langkah pertama mencari XBV dan XNBV x2 s2



[]



XBV =



x1 s1



[]



XNBV =



Kemudain merubah tanda pada fungsi kendala dan menambahkan variabel surplus pada fungsi max z dan fungsi kendala Bentuk standar LP Max z = x1+ 4x2 + 0s1 + 0s2 s.t x1 + 2x2 + s1 2x1 + x2



=6 + s2 = 8



x1, x2 ,s1,s2≥ 0



Pada solusi optimal : BV = {x2 , s2 } , NBV ={ X1 + S1 } Tentukan notasi matriks yang pertama pemisahan antara BV dan NBV 1 0 20 2 -1 B= dan B = 11 −1 1 2



[ ]



N =[ a1 a s ₁ ] =



[ ]



[ 1120 ]



₁



Dan CBV = [ C ₂ Cs₂ ]



= [ 4 0]



CNBV = [ C ₁ Cs₁ ] =[ 1 0 ] Lalu buatlah tableau sesia informasi yang didapatkan 13



Max z = x1+ 4x2 + 0s1 + 0s2 s.t x1 + 2x2 + s1 2x1 + x2



=6 + s2 = 8



x1, x2 ,s1,s2≥ 0 Pada solusi optimal : BV = {x2 , s2 } , NBV ={ X1 + S1 }  Untuk mencari x2 pada solusi optimal BV yaitu pada baris pertama berinilai 1 selainnya 0  Untuk mencari s2 pada solusi optimal BV yaitu pada baris kedua berinilai 1 selainnya 0  Untuk mencari x1 menggunakan rumus B-1 . a1 1 0 2 -1 . a 1= 1 B = −1 2 1 2



[ ] [] [] [ ] [] []



1 2 B-1. a1 = 3 2



 Untuk mencari s1 menggunakan rumus B-1 . a s 1 1 0 2 -1 . a s 1= 1 B = −1 0 1 2 1 2 B-1.a s 1 = −1 2



Tableu optimal Baris 0 Baris 1 Baris 2



z



x1 1 2 3 2



x2



s1 0 1 0



1 2 −1 2



Selanjutnya dengan konsep yang sama tentukan ruas kanan nya



14



s2



rhs 0 0 1



1 −1 2 Dengan menggunakan B b= −1 2



[ ]



¿



0



6 [ 8] 1



[35] Tableu optimal Baris 0 Baris 1



x1



z



x2



1 2 3 2



Baris 2



s1 0 1 0



1 2 −1 2



s2



rhs 0 0



3



1



5



Selanjutnya terapkan rumus untuk perhitungan baris 0 Rumus perhitungan baris 0 kita sudah terbantu dengan BV yang sudah diisi 0  Baris 0 untuk BV selalu bernilai 0  Perhitungan baris 0 untuk NBV selalu memerlukan C BV B−1 Menggunakan rumusan C BV B−1 as−c j c j=koefisen baris z yang dibentuk diC BV C NBV a s=a yang dimaksu d C BV = [C 2 C s 2 ] =[ 4 0 ] 1 B−1= 2 −1 2



[ ] 0 1



N= [ a1 a s 1 ] =



[12 10]



C NBV =[ C 1 C s 1 ] =[ 1 0 ] b= 6 8



[]



1 C BV B−1=[ 4 0 ] 2 −1 2



[ ] 0 1



15



¿[2 0] (akan digunakan berkali-kali untuk perhitungan baris 0) Tableu optimal Baris 0 Baris 1



z



x1



x2 0 1



1 2 3 2



Baris 2



s1



0



s2



1 2 −1 2



rhs 0 0



3



1



5



 Perhitungan baris 0 untuk NBV sesuai dengan notasi matriks Kolom x 1 C 1 =C BV B−1 a1−C1



¿[2 0]



[ 12]−1



=2–1 =1 Tableu optimal Baris 0 Baris 1



z



x1



x2 1



0 1



1 2 3 2



Baris 2



s1



0



s2



1 2 −1 2



rhs 0 0



3



1



5



Kolom s1 C s 1=C BV B−1 as 1−C s 1



¿[2 0]



[ 10]−0



=2–0 =2



Tableu optimal Baris 0



z



x1



x2 1



s1 0 16



s2 2



rhs 0



1 2 3 2



Baris 1 Baris 2



1 2 −1 2



1 0



0



3



1



5



Kolom rhs c BV B−1 b



[2 0] 6



[8 ]



¿12 Sehingga perhitungan baris nol untuk NBV sesuai notasi mariks: Tableau optimal Baris 0



z 1



X1 1



X2 0



S1 2



S2 0



rhs 12



Baris 1



0



1 2



1



1 2



0



3



Baris 2



0



3 2



0



−1 2



1



5



Tableau diatas sudah optimal karena baris 0 tidak ada lagi negartif Tableau pada solusi optimal Tableau optimal Baris 0



z



X1



X2



S1



S2



rhs



BV



1



1



0



2



0



12



z=12



Baris 1



0



1 2



1



1 2



0



3



X1=3



Baris 2



0



3 2



0



−1 2



1



5



X2=5



Koefisien baris nol semua bertanda (+) Solusi optimal X1=0 X2=3



S2=5 S1=0 dan z=12 BAB III 17



PENUTUP



3.1 Kesimpulan 1. Pada bentuk standar program linier yang akan kita ubah kedalam bentuk notasi matriks maka akan didapatkam yaitu variabel teknologi, variabel biaya, variabel sumber daya dan variabel profit. 2. Manfaat Dari Perhitungan Notasi Matriks  Mendapatkan solusi pada tahapan tertentu tanpa proses iterasi, melainkan dengan operasi hitung matriks dan vektor  Informasi yang diperlukan LP tahap awal dan himpunan BV yang terbentuk pada tahapan yang diinginkan yaitu tahap suboptimal atau tahap optimal. 3. Notasi matriks adalah lambang atau simbol dalam penulisan matriks BV ={ s1 , x 3 , x1 } NBV ={x 2 , s2 , s 3 } ↓ s1 x BV = x 3 x2



[]



↓ x2 x NBV = s2 s3



[]



4. Solusi suatu sistem persamaan dalam notasi matriks adalah dengan perkalian invers. 3.2 Saran Kami sebagai penulis, menyadari bahwa makalah ini banyak sekali kesalahan dan sangat jauh dari kesempurnaan.Tentunya, kami akan terus memperbaiki makalah dengan mengacu pada sumber yang dapat dipertanggungjawabkan nantinya. Oleh karena itu, kami sangat mengharapkan kritik dan saran tentang pembahasan makalah diatas.



18



DAFTAR PUSTAKA



https://www.google.com/url? sa=t&source=web&rct=j&url=https://123dok.com/cument/zgw42o6y-algoritmasimpleks-dalam-notasimatriks.html&ved=2ahUKEwjB8LH7urztAhUg_XMBHTJFBcwQFjABegQICBAC &usg=AOvVaw1wtUcWdFp09z3N204yIOrH https://www.google.com/url?sa=t&source=web&rct=j&url=https://adoc.pub/matriksalgoritma-pemrograman-definisimatriks.html&ved=2ahUKEwjB8LH7urztAhUg_XMBHTJFBcwQFjAHegQIBRAB &usg=AOvVaw0htS40MVvRxq77JvZSW9VU



19