Ide Dasar Program Linear [PDF]

Citation preview

MATEMATIKA EKONOMI MANAJEMEN 2019 Ide dasar Program Linear Program linear ialah suatu model optimasi persamaan linear berkenan dengan kendalakendala linear yang dihadapinya. Masalah program linear berarti adalah pencarian nilai-nilai optimun (maksimum atau minimu) sebuah fungsi pada suatu sistem atau sehimpun kendala linear. Fungsi linear yang hendak dicari nilai optimunnya, berbentuk sebuah persamaan, disebut fungsi tujuan. Sedangkan fungsi-fungsi linear yang harus terpenuhi dalam optimasi fungsi tujuan tadi., dapat berbentuk persamaan maupun pertidaksamaan, disebut fungsi kendala. Agar suatu masalah optimasi dapat diselesaikan dengan program linear, ada beberapa syarat atau karakteristik yang harus dipenuhi, yaitu: a. Masalah tersebut harus dapat diubah menjadi persamaan matematis.Ini berarti bahwa masalah tadi harus bisa diuangkan ke dalam bentuk model matematik, dalam hal ini model linear, baik berupa persamaan maupun pertidaksamaan. b. Keseluruhan sistem persamaan harus dapat dipilah-pilah menjadi satuan-satuan aktivitas; sebagai misal: a11 X 1  a12 X 2   k1 , dimana X1 dan X2 adalah aktivitas. c. Masing-masing aktivitas harus dapat ditentukan dengan tepat baik jenis maupun letaknya dalam model programasi. d. Setiap aktivitas harus dapat dikuantitaifkan sehingga masing-masing nilainya dapat dihitung dan dibandingkan. Dengan demikian di dalam suatu masalah program liner harus terdapat rangakaian “kendala-kendala” atau masukan aktivitas-keluaran. Perumusan model program liner



dapat



dilakukan melalui langkah-langkah sebagai berikut: a. Menetukan aktivitas. b. Menentukan sumnber-sumber (masukan) c. Menghitung jumlah masukan dan keluaran untuk setiap satuan aktivitas d. Menetukan kendala-kendalaaktivitas. e. Merumuslnmodel, yakni membentuk fungsi tujuan dan fungsi-fungsi kendalanya. Perumusan Model Programasi Linear. Sebuah perusahaan yang menghasilan dua macam keluaran, yaitu barang A dan barang B, menggunakan dua macam bahan mentah yakni R dan S sebagai masukannya. Baik barang A maupun barang B masing-masing menggunakan maukan R dan masukan S dalam proses produkainya. Setiap unit keluaran A memerlukan unit masukan R



dan 3 unit masukan S



MATEMATIKA EKONOMI MANAJEMEN 2019 sedangkan setiap unit B masing-masing Rp 5.000,00 dan Rp 6.00,00 per unit. Jumlah persediaan ,masukan R dan masukan S yang dimiliki oleh perusahaan ini masing-masing 100 unit dan 120 unit. Berapa unit A dan B harus dihasilkan agar penerimaan perusahaan maksimum, dengan keterbatasan atau kendala bahwa penggunaan masukan R dan masukan S masing-masing tidak melebihi 100 unit dan 120 unit? Masalah program linear yang muncul disini ialah memaksimalkan penerimaan, yakni menentukan kombinasi junlah barang A dan jumlah barang B yang sebaiknya dihasilkan sehubungan dengan kondisi-kondisi yang dihadapi. Agar dapat diselasikan sehubungan dengan model programliner, permasalahnnya harsu dituangkanke dalambentuk model tersebut,berarti harus dirumuskan fungsi tujuan yang hendak dioptimunkan dan fungsi-fungsi kendala yang dihadap.Misalkanz melambangkan penerimaan A dan juimlah B maka: Fungsi tujuannya : z = 5000 a + 6000 Fungsi kendalanya : 4a + 2b  100 3a + 4b  120 Fungsi kendal yang pertama berkenaan dengan masukan R; karena setiap yunit A memerlukan 4 unit R dan setiap unit B memerlukan 2 unit R, padahal jumlah masukan R yang dapat digunakan tidak mungkin melebihi (berarti ooleh kurang atau sama dengan) 100 unit. , maka haruslah 4a +2b  100. Sedangkan fungsikendala yang kemudan berkenaan dengan maukan atau bahan mentah S; karena setiap unit A membutuhkan 3 unit S dan setiap unit B membutihkan4 unit S, padahal jumlahmaukan S yang dapat dipakai tidakmungkinlebih dari (berarti boleh kurang dari atau samadngan) 120 unit, maka haruslah 3a + 4b  120. Perumusan fungsi tujuan dan fungsikendala ini akan lebih mudah dilakukan dengan menggunakan bantuan tabel permasalahannya,yang berisi keterangan-keterangan tentang masukan dankeluaran serta kendalanya masing-masing. Tabel 13.1. Permasalahan Keluaran



Masukan



Kendala masukan



A



B



R



4



2



100



S



3



4



120



5000



6000



MATEMATIKA EKONOMI MANAJEMEN 2019 Bentuk Umum Model Programasi Linear Sebagaimana telah dinyatakan sebelumnya, masalah program linear tak lain adalah masalah optimasi bersyarat, yakni pencarian nilai maksimum (maksimasi) atau pencarian nilai miniun (minimasi)sesuatu fungsi tujuan berkenaan dengan keterbatasan-keterbatas atau kendala yang harus dipenuhi, Masalah-masalah tersebut secara umum dapat dirumuskan sebgai berikut: a. Masalah maksimasi Maksimumkan fungsi tujuan



z  c1 x1  c 2 x 2  .......c n x n terhadap kendala-kendala



a11 x1  a12 x 2  .......a1n x n  b1



a 21 x1  a 22 x 2  .......a 2 n x n  b1 . .



. .



. .



. .



a m1 x1  a m 2 x 2  .......a mn x n  bm dimana



xi  0 , j = 1,2,……,n n



Ringkasnya, maksimumkan z = n



a x



0 i



j 1



 b,



c x j 1



xi  0 dimana :



b. Masalah minimisasi Minimunkan fungsi tujuan



z  c1 x1  c2 x2  .......cn xn terhadap kendala-kendala



a11 x1  a12 x 2  .......a1n x n  b1 a 21 x1  a 22 x 2  .......a 2 n x n  b2 . .



. .



1 i



. .



. .



a m1 x1  a m 2 x 2  .......a mn x n  bm



i = 1, 2, …..,m.



MATEMATIKA EKONOMI MANAJEMEN 2019 dimana



xi  0



j = 1,2,……,n n



Ringkasnya, maksimumkan n



a x j 1



0 i



z=



c x j 1



j



j



 b,



xi  0



i = 1, 2, …..,m.



Masalah maksimasi dijumpai misalnya dalam kasus penentuan kombinasi jumlah produk (produc-mix) guna memperoleh profit maksimum. Sedangkan masalah minimasi ditemui misalnya dalam kasus upaya menekan biaya produksi. Variabel x1, yang mencerminkan aktivitas, dalam program linear disebut juga variabel keputusan (decision variable). Variabel keputusan tidak boleh negatif, karena di dalam setiap rumusan model program liner (harus) selalu dicantumkan notasi x1  0. Hal ini dikenal dengan sebutan “ pembatasan ketidaknegatifan” (non-negatif restriction) Kendala-kendala dalam sebuah programasi linear tidak selalu harus berbetuk pertidaksamaan yang seragam. Dalam kasus tertentu dapat terjadi dalam salah satu kendala, atau lebih, berbentuk persamaan. Dapat pula terjadi di dalam sebuah masalah terdapat kendala pertidaksamaan berbentuk  maupun  . Penyelesaian masalah programasi linear dapat dikerjakan dengan tiga macam cara atau metode, yaitu metode grafik (geometri), metode aljabar dan metode simplex. Metode Grafik Penyelesaian



dengan



metode



grafik



atau



geometri



dilakukan



dengan



jalan



menggambarkan fungsi kendala maupun fungsi tujuan pada sistem sepasang sumbu–silang, dimana sumber-sumber horizontal dan vertikal masing-masing mencerminkan jumlah setiap keluaran. Langkah-langkah penyelesaiann dengan metode grafik adalah sebagai berikut: a. Gambarkan fungsi-fungsi kendalanya. b. Tentukan area laik (feasible area) bagi masalah yang bersangkutan, yakni area yang dibatasi oleh garis-garis kendala. c. Gambarkan fungsi tujuannya dengan menetapkan sebarang nilai z



MATEMATIKA EKONOMI MANAJEMEN 2019 d. Lakukan pergeseran seperlunya atas kurva atau garis tujuan, dengan mengubah–ubah nilai z, agar ditentukan titik penyelesaian optimal. e. Titik penyeleasian optimal adalah titik sudut terjauh dari area laik yang dapat dicapai oleh garis tujuan. Dalam masalah maksimasi, sudut area laik terjauh biasanya berupa sudut teratas atau terkanan, sedangkan dalam masalah minimasi, sudut area laik terjauh biasanya berupa sudut terbawah atau terkiri (tergantung pada lereng garis tujuannya). y



y



y



5



5



5



5x + 4y = 20



5x



+ 4y ≤ 20



x 0



(a)



5x + 4y ≤ 20



x



4



0



(b)



x



4



0



(c)



4



Gambar 13.1. Kurva Persamaan Linear Dengan Tanda ≤ Panel (a) memperlihatkan gambar dari sebuah persamaan. Wilayah persamaan 5x+ 4y = 20 adalah titik-titik sepanjang garis yang bersangkutan. Sedangkan panel (b) dan (c) memperlihatkan gambar dari sebuah pertidaksmaan. Tanda-tanda silang pada panel (b) mengisyaratkan bahwa bidang dibelah atas/kanan garis tidak termasuk wilayah pertidaksamaan 5x + 4 y  20, jadi wilayahnya adalah mulai dari garis yang bersangkutan ke bawah/kiri. Atau dengan cara yang ditunjukkan oleh panel (c); anak panah disitu menjelaskan wilayah yang termasuk di dalam pertidaksamaan 5x + 4 y  20 . Banyak cara dapat dilakukan untuk menggambarkan wilayah suatu pertidaksamaan linear. Yang jelas, gambarannya bukan semata-mata berupa sebuah garis. Untuk pertidaksamaamn yang bertanda  , perhatikan contohcontoh berikut. y



y



5



y



5



5



5x + 4y = 20



5x



+ 4y ≥ 20



x 0



(a)



4



5x + 4y ≥ 20



x 0



(b)



4



x 0



(c)



4



MATEMATIKA EKONOMI MANAJEMEN 2019 Gambar 13.2. Kurva Persamaan Linear Dengan Tanda ≥ Bidang di bawah/kiri garis tidak termasuk wilayah 5x + 4 y  20 . Kasus Maksimumkan fungsi tujuan z = 5000 a + 6000 b Terhadap kendala-kendala : 4a + 26  100 3a + 4b  120 a, b  0



Area penyelesaian yang laik (feasible area) bagi masalah yang dihadapi oleh perusahaan ini adalah OKLM yang diarsir. Menghasilkan kombinasi jumlah A dan B diatas/kanan bidang OKLM merupakan hal yang tidak mungkin dapat dilakukan, mengingat keterbatasan sumberdaya atau masukan (dalam hali ni bahan mentah) yang dimiliki. Area diluar bidang OKLM disebut area (unfeasible area) Pada panel (b) yang gambaran diperbesar, fungsi tujuan z = 5000a + 6000 b digambarkan dengan mencobakan nilai-nilai z tertentu. Disini terlihat bahwa sudut area laik terjauh yang dapat dicapai oleh garis fungsi tujuan adalah titik L. Titik Lini, yang merupakan perpotongan antara kedua garis kendala, terletak pada kedudukan = 16 dan b = 18. Berarti penyelsaian optimalnya adalah memproduksi barang A sebanyak 16 unit dan barang B sebanyak18 unit. Penerimaan maksimum yang diperoleh dengan kombinasi ini adalah z = 5000(16) + 6000(18) =188.000



MATEMATIKA EKONOMI MANAJEMEN 2019 Bila perlu, hasil penyelesaian ini dapat diuji kebenarannya. Pengujian dilakukan terhadap kendala-kendala yang ada, guna membuktikan kelaikan dan terhadap semua kemungkinan penyesaian -yakni sudu-sudut area laik (feasible area) guna membuktikan optimalitas. a. Pengujian terhadap kendala: 4a + 2b  100  4(16)+ 2 (18)  100 terpenuhi 3a + 4b  120  3 (16)+ (18)  100 terpenuhi Karena ruas kiri fungsi mencerminkan jumlah masukan yang terpakai dan ruas kanan menunjukkan jumlah masukan yang tersedia, maka dengan membandingkan kedua ruas dapat diketahui jumlah masukan yang tersisa atau yang tidak terapkai. Dalam kasus ini, baik masukan R (lihat pengujian terhadap kendala pertama) maupun masukan S (lihat pengujian terhadap kendala kedua) semuanya terpakai habis, tidak ada yang tersisa. Bedasarkan pengujian terhadap kendala-kendala ini terbukti bahwa kombinasi produksi 16 unit A dan 18 unit B adalah laik. b. Pengujian terhadap optimalitas: K (0,30)  z = 5000 (0)+ 6000 (30)



= 180.000



L (16,18)  z = 5000 (16)+ 6000 (18) = 188.000 M (25, 0)  z = 5000 (25)+ 6000 (0) = 125.000 Titik O (0, 0) tak perlu diuji karena jelas z =0. Sedangkan titik J danN juga tidak perlu diuji karena luar area laik. Berdasarkan pengujian optimalitas ini terbukti bahwa titik L. Kombinasi produksi 16 A dan 18 B, adalah yang terbaik. Metode Aljabar Metode aljabar dilakukan melalui penyelidikan optimalitas secara bertahap sampai penyelesaian yang optimal. Pada setiap tahap penyelesaian dilakukan pengujian mengenai kelaikan (feasibility) penyelesaian yang bersangkutan, dan penyelidikan (detection) mengenai kemungkinan perbaikan optimalitas untuk tahap penyelesaian berikutnya. (Pekerjaan ini mirip dengan penyelidikan optimalitas sudut-sudut area laik yang terdapat di dalam metode grafik). Sebelum penyelesaian tahap pertama dimulai, perlu dilakukan standarisasi rumusan model, yakni mengubah kendala- kendala yang masih berbetuk pertidaksamaan menjadi bentuk persamaan. Caranya ialah dengan memasukkan unsur variabel semu pada ruas kiri fungsi kendala. Untuk fungsi kendala yang bertanda  , dilakukan penambahan “varaibwel senjang’



MATEMATIKA EKONOMI MANAJEMEN 2019 (slack variable). Sedangkan untuk fungsi kendala bertanda  , dilakukan pengurangan “variabel surplus” (surplus varible). Contoh: 2x1 + 5 x2  40 menjadi



2x1 + 5 x2 + s = 40



2x1 + 5 x2  40 menjadi



2x1 + 5 x2 -s = 40



Penyelesaian metode aljabar diawali dengan me-nol-kan semua variabel keputusan, ini meruapakan penyelesaian tahap pertama. Kemudian dilanjutkan dengan penyelesaian tahaptahap berikutnya, dengan mepertimbangkan kelaikan dan optimalitasnya. Pekerjaan dikatakan selesai (penyelesaian dianggap optimal) apabila pada suatu tahap penyelesaian tertentu tidak terdapat lagi kemungkinan perbaikan optimalitas. Secara umum langkah-langkah penyelesaian dengan metode aljabar, setelah model permasalahannya dirumuskan sebagai berikut: a. Lakukan standarisasi ru,usan model. b. Kerjakan penyelesaian tahap pertama dengan me-nol-kan semua variabel keputusan. c. Kerjakan penyelesaian tahap pertama dengan me-nol-kan semua variabel keputusan berdasarakan koefisien-koefisien variabel keputusan yang terdapat pada fungi tujuan, tentukan salah satu variabel dengan optimalitas “terbaik” (sesuiai dengan masalahnya : maksimisasi atau minimisasi) d. Kerjakan penyelesaian tahap berikutnya berdasarkan keliakan variabel pilihan tadi, yakni selidiki optimalitas fungsi tujuan dan sidik apakah masih terdapat kemungkinan perbaikan optimalitas (terdapat atau tidaknya kemungkinan perbaikan optimalitas akan terlihat dari persamaan fungsi-fungsi tujuan baru terbentuk pada tahap ini) e. Jika sudah tidak terdapat kemungkinan perbaikan optomalitas berarti pekerjaan selesai, penyelesaian optimal tercapai. Jika masih terdapat kemungkinan perbaikan, ulangi langkah ke-3 dan ke-4 terus menerus sampai diperoleh penyelesaian optimal. Kasus. Andaikan masalah yang diahadapi PT “ Double-X” dalam Kasus 81 di depan, yakni: Maksimumkan z = 25x1 + 15x2 Terhadap



3x1 + 3x2  24 ………… (kendala masukan K) 2x1 + 4x2  20 …………..(kendala masukan L) 3x1



 21 ………… (kendala masukan M)



Sekarang kita selesaikan dengan metode aljabar.



MATEMATIKA EKONOMI MANAJEMEN 2019 Standarisasi model Maksimumkan z = 25x1 + 15x2



(I)



Terhadap fungsi batasan sebagai berikut : 3x1 + 3x2 + s1 = 24 atau s1 = 24 – 3x1 -32 (II) 2x1 + 4x2 + s1 = 20 atau s1 = 20 – 2x1 –4x2 (III) 3x1



+



s1 = 21 atau s1 = 21 – 3x1



(IV)



Penyeleesaian tahap pertama : x1 = 0, x2 = 0



x1  0   Karena x 2  0 maka berdasarakan (1), (II),(III) dan (IV): Z = 0,



s1 =24,



s2 =20 dan



s1 =21



Menurut persamaan fungsi tujuan (persamaan (1), setiap unit X1 mendatangka profit 15. Berarti untuk penyelesaian tahap berikut sebaiknya terlebih dahulu”diproduksi”barang X1, sementara X2 tetap dipertahankan nol. Jumlah X1 yang sebaiknya diproduksi diusahakan seoptimal mungkin, yakni jumlah terbanyak namun tetap dalam batas-batas kelaikan. Jika x2 = 0 dan semua masuklan K, L serta M terpakai habis (dengan perkataan lain s1 = s2 = s3 = 0), maka Menurut (II) : x1= 24/3 = 8  tak laik Menurut (III) : x1= 20/2 = 10  tak laik Menurut (IV): x1= 21/3 = 7  tak laik X1=8 dan x1 =10 tidak laik karena jumlah masukan M yang dimiliki tidak mencukupi. Perhatikan persamaan (IV); jika x1= 8 berarti dibutuhkan 3(8) = 24 unit masukan M, padajhal persediaannya tidak melebihi 21unit/ Jadi, jumlah x1 yang optimal (terbanyak dan laik) untuk dianalisis pada tahap penyelesaian berikutnya adalah 7 unit. Penyelesaian tahap kedua : x1 =7, x2 =0 Karena x1 = 7 dan x2= 0 maka berdasarkan (I)



: z = (25 )(7)+ 15 (0) = 175



(II)



: s1= 24 - 3 (7) - 3(0) = 3



(III)



: s1= 20 - 2 (7) - 4(0) = 6



(IV)



: s1= 21 - 3 (7) - 4(0) = 0



Pada tahap ini perlu dilakukan penyesuaian terhadap pertsamaan fungsi tujuan yakni dengan mensubstitusikan x1 dari persamaan (IV).



MATEMATIKA EKONOMI MANAJEMEN 2019 Menurut (IV) : 3x1 + s1 =21 



1 s3 x1 = 7 - 3



Berarti 3x1 = 21 – s3



Mengapa persamaan (IV) harus diubah dalam satuan variabel keputusan ? Karena pada tahap ini varaibel semuanya (s1) sama dengan nol! Mengapa perubahan tersebut dinyatakan dalam satuan variabel x1? Karena pada tahap ini x1, merupakan variabel keputusan yang dianalisis! Selanjutnya, dengan mensubstitusikan persamaan (V) ke dalam persamaan fungsi tujuan asli (I), diperoleh persamaan fungsi tujuan baru. z = 25 x1 + 15 x2 1 z = 25 (7- 3 s1) + 15 x2 25 z = 175 - 3 s1) + 15 x2



Dari persamaan fungsi tujuan yang baru ini terlihat bahwa optimalitas bisa diperbaiki dengan memproduksi (memulai atau menambah) barang X2, yang setiap unitnya mendatangkan profit 15. Sedangkan jumlah barang X1, pada tahap penyelesaian berikutnya tidak berubah (tetap x1 =7) sebab di dalam fungsi tujuan yang baru ini tidak tercantum lagi variabel x1. Koefisien –25/3 pada variabel s3 mencerminkan bahwa jika s3 bertambah satu unit (masukan M yang tidak digunakan bertambah satu unit), maka profit berkurang sebesar 25/3. Jelas kita tidak akan melakukan hal ini sebab justru akan memperburuk optimalitas. Sebisa-bisanya justru variabel semua di sini diusahakan nol, yang berarti tidak ada masukan tersisa. Uraian



di



atas



menyimpulkan



bahwa



pada



tahap



penyelesaian



berikutnya



harus”diproduksi” barang X2 (harus x2  0), sedangkan jumlah X1 harus dipertahankan 7 unit. Masalahnya berapa unit X2 yang optimal untuk diproduksi ? kembali kita perlu melakukan analisis seperti pada tahap pertama. Jika 1 = 7 dan semua masukan terpakai habis (s1 = 0, s2 = 0, s3 = 0), maka, Menurut (II) : x2 = 3/3 = 1  laik Menurut (III) : x2 = 6/4



= 1,5  tak laik



Menurut (IV): x2 tidak dapat dinyatakan, karena persamaan ini tidak mengandung variabel x2.



MATEMATIKA EKONOMI MANAJEMEN 2019 X2= 1,5 tidak laik sebab (bersama-sama) dengn x1 = 7) berarti dibutuhkan masukan K sejumlah 25,5 unit ujipersamaan(II )! , padahal hanya tersedia 24 unit. Dengan demikian kombinasi jumlah optimal yang harus dianalisis berikutnya adalah x = 7 dan x= 1. Penyelesaian tahap ketiga : x1 = 7, x2 =1



Berdasarkan



x1  7   x 2  1 maka menurut (I), (II), (III) dan (IV):



Z = 190, s1 = 0, s2 = 2 dan s3 = 0 Karena penyertaan x2 dalam analisis menyebabkan s1 = 0, maka persamaa(II) yang mengandung s1 perlu diubah ke dalam satuan x2 untuk kemudian – bersama-sama dengan persamaan (IV) yang telah diubah menjadi (V) – disubstistusikan ke dalam fungsi tujuan yang asli, guna mengetahui kemungkinan perbaikan optimalitas lebih lanjut. Menurut (II) : 3x1 + 3 x2 + s1 = 24 3x2 = 24 –3x1 – s1  x2 = 8 – x1 – 1/3 s1



(VII)



selanjutnya, demgan mensubstistusikan (V) dan (VII) ke dalam fungsi tujuan yang asli (I), diperoleh sebuah fungsi tujuan yang baru lagi. Z = 25x1 + 15x2 = 25 (7-1/3 s1) + (8-x1-1/3 s1) = 175 -25/3 s1 + 120-15x1-5s1) =



295 -5 s1 – 25/3 s2 –15 (7 – 1/3 s1)



= 295 -5 s1 – 25/3 s2 –105 + 5s3



 z = 190-5s



1



–10/3 s3



Disini terlihat tidak ada lagi variabel x1 dan x2, berarti sudah tidak dimungkinkan lagi perbaikan optimalitas melalui penambahan x1 dan x2. Karena tidak terdapat lagi kemungkinan perbaikan optimalitas, berarti x1 dan x2 yang dicapai pada tahap ini sudah optimal. Jadi, optimalitas tercapai pada x1 = 7 dan x2 = 1, dengan z =190. Perhatikan kembali persamaan (VIII). Disitu terlihat s1 dan s3 berkoefisien negatif, berarti penambahan setiap unit s1 atau s3akan mengurangi optimalitas. Ini mengisyaratkan bahwa kita harus mempertahankan s1 = 0 dan s3 = 0. Apabila x1 = 7 dan x2 =1 tadi dimasukkan ke dalam persamaan-persamaan yang mengandung s1 dan s3 = 0. Selanjutnya, ketidakhadiran variabel S2 (yang mencerminkan sisa masukan L) di dalam persamaan z optimal di atas menandakan bahwa



MATEMATIKA EKONOMI MANAJEMEN 2019 pada tahap penyelesaian optimal ini s2  0. Berarti terdapat sisa masukan L yang tidak terpakai. Jika hasil x1= 7 dan x2 = 1 dimasukkan ke dalam persamaan (III) yangmengandung s2, terbukti bahwa s2 = 2. dengan perkataan lain, terdapat 2 unit L yang tidak taerpakai pada tingkat produksi ini. Hasil-hasil perhitungan secara aljabar ini terbukti konsisten dengan hasil perhitungan secara grafiksebelumnya. Hasil-hasil inipun konsisten pula dengan hasil perhitungan secara simplex, yang akan ditemui di dalam sub-bab berikut. Catatan tentang metoda aljabar Secara teoritik, metoda alabar lebih bermanfaat dibandingkan dengan metoda grafik, karena dapat digunakan untuk penyelesaian masalah dengan jumlah variabel keputusan berapapun. Sayangnya, rangkaian penyalesaiannya cukup panjang sehingga bisa membingungkan atau bahkan menjemukan. Untuk menyelesaikan masalah dengandua variabel keputusan, jelas metoda grafik lebih praktis daripada metoda aljabar. Ketidakpraktisannya menyebabkan meyoda ini kurang begitu populer. Oleh karenanya banyak buku teks yang memuat materi programasi linier tidak mencantumkan metoda ini dalam bahasannya. Untuk menyelesaikan masalah dengan lebih baik dari dua variabel keputusan, orang lebih cenderung menggunakan metoda simplex karena lebih praktis. Akan tetapi patut dicatat bahwa metoda simplex sesungguhnya bersumber dari metoda ini, dan banyak paket programasi liner pada komputer justru diprogram berdasarkan prinsip-prinsip metoda aljabar, meskipun keluaran (output)-nya disajikan dalam tabulasi simplex. Metode Simplex Metoda simplex dikerjakan secara sistematik bermula dari suatu penyelesaian dasar yang laik (feasible basic solution ) ke penyelesaian dasar yang laik berikutnya. Hal ini dilakukan berulang-ulang (iterative, algorithmic) hingga ditemukan penyelesaian yang optimal. Dalam pengerjaan secara simplax ini peranan matriks berikut kaidah-kaidahnya sangat berarti. Seperti halnya dengan metoda aljabar, di sinipun terlebih dahulu harus dilakukan standarisasi rumusan model, sebelum tahap penyelesaian awal dikerjakan. Fungsi-fungsi kendala yang masih berbentuk pertidaksamaan harus diubah dulu menjadi berbentuk persamaan, yakni dengan menambahkan “variabel senjang” (slack variabel), pada fungsi kendala yang bertanda , dan mengurangkan “variabel surplus” (surplus variabel) pada fungsi kendala yang bertanda . Secara umum, fungsi-fungsi kendala yang standar dapat dituliskan sebagai berikut :



MATEMATIKA EKONOMI MANAJEMEN 2019 a11 + a12 x2 + ………….+ a1n xn







s1



= b1



a21 + a22 x2 + ………….+ a2n xn







s2



= b2



.



.



.



.



.



.



.



.



.



.







am1 + am2 x2 + ………….+ amn xn n



Ringkasnya :



a j 1



ij



x j bi



sm



= bm



i = 1,2,3,……………,m



Hasil-hasil perhitungan pada setiap setiap tahap pengerjaan disajikan ke dalam bentuk tablo (tabel matriks). Berdasarkan angka-angka yang muncul di tablo inilah dilakukan analisis dan ditarik kesimpulan. Dalam metoda simplex dikenal dua macam model penyajian tablo, yaitu : a. Tablo berkolom variabel dasar b. Tablo berbaris cj  zj Meskipun kesimpulan akhir dari analisis simplex dengan kedua model tablo ini sama, namun karena baris dan kolom yang terdapat di masing-masing tablo berlainan perlakuan terhadapnya berbeda. a. Simplex dengan tablo berkolom variabel dasar Sebagaimana telah dikemukakan sebelumnya, metode simplex diawali dengan standarisasi model. Metode simplex dengan tablo jenis ini tidak saja mensyaratkan standarisasi fungsi-fungsi kendala, tetapi juga standarisasi fungsi tujuan, yakni mengubahnya menjadi persamaan terbentuk implisit. Secara mum, rumusan model yang standar untuk metode simplex dengan tablo berkolom varibel dasar adalah: Optimunkan z – c1x1 – c2x2 - ……-cnxn = 0 Terhadap a11 + a12 x2 + ………….+ a1n xn







s1



= b1



a21 + a22 x2 + ………….+ a2n xn







s2



= b2



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



am1 + am2 x2 + ………….+ amn xn







sm



= bm



MATEMATIKA EKONOMI MANAJEMEN 2019



Bentuk tablonya: V



Z X1



X2 …



Xn



S1



S2 …… Sn



S



D



Persamaan –z



Z



1



C1



S1



0



a11



a12 ..



a 1n



1



0 …...



0



b1



S2



0



a21



a22 ..



a 2n



0



1 …… 0



b2



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



Sm



0



am1



matriks utama



C2…



xm2..



Cn



amn



0



0



0 …...



0 ......... 0



0



0 Persamaan–S1 Persamaan–S2 .



Persamaan -Sn



bn



matriks utama Amxn



Inxn



Keterangan : 1.



Kolom Variabel dasar (VD) Kolom variabel-variabel dasar (basic variabel), disebut juga variabel-variabel anol



(nonzero variables), yaitu variabel-variabel yang nilainya ditunjukkan oleh konstanta-konstanta yang bersesuaian di kolom S. Pada penyelesaian awal atau tablo pertama, kolom VD ini berisi semua variabel semu. Pada tahap-tahap berikutnya variebl-veraibel yang termuat di kolom ini akan berganti-ganti, keculai z yang senatiasa hadir disitu sejak penyelesaian awal hingga penyelesaian akhir. Variabel-variabel lain yang tidak tercantum di kolom ini dinamakan veriebelveribel dasar (nonbasic varibel) atau veribel nol (zero veriables). 2. Kolom z



MATEMATIKA EKONOMI MANAJEMEN 2019 Kolom ini sebenarnya hanya berfungsi sebagai “pelengkap” isinya selalu sama (1, 0, 0,….0) sejak penyelesaian awal hingga penyelesaian akhir karenanya boeh tidak dicantumkan di dalam tablo. 3. Kolom-kolom varibel Kolom ini berisi koefisien-koefisien dari masing-masing varibel dalam persamaan yang bersesuaian; yakni aij untuk variabel asli xj dan 0 atau 1 utuk varibel-veribel semu sj, untuk tablo pertama (penyelesaian awal). 4. Kolom S Kolom S (“solution”) ini berisi nilai-nilai ruas kanan dari persamaan-persamaan implisit yang terdapat di dalam model, baik persamaan fungsi tujuan maupun persamaan –persamaan fungsi kendala. Angka-angka yang tercantum di kolom S ini mencerminkan nilai z dan nilai-nilai varibel dasar pada tahap penyelesaian yang bersangkutan. Langkah-langkah Pengerjaan Langkah-langkah pengerjaan program linear secara simplex dengan tablo berkolom varibel dasar adalah sebagai berikut: a. Rumuskan dan standarisasikan modelnya. b. Bentuk tablo pertama dengan menetapkan semua varibel semu sebagai variabel dasar (semua varibel asli sebagai varibel dasar). c. Tentukan satu “varibel pendatang” (entering varible) di antara varibel-varibel berikutnya. Varibel pendatang ialah varibel dasar yang nilainya pada baris –z paling negatif dalam kasus maksimasi,atau palimg positif dalam kasus minimasi. d. Tentukan satu “variabel perantau” (leaving veriabel) diantara varibel veribel dasar yang ada, untuk menjadi varibel dalam tablo berikutnya. Varibel perantau ialah varibel dasar yang memiliki “rasio solusi” dngan nilai positif terkecil. Kolom yang mengandung varibel pendatang dunamakan kolom kunci, sedangkan baris yang mengandung varibel perantau dinamakan baris kunci. Unsur di dalam tablo yang merupakan perpotongn antara baris kunci dan kolom kunci dinamakan unsur kunci. Rasio solusi adalahhasil bagi konstanta pada kolom S terhadap unsur sebaris pada kolom kunci. Dalam menentukan varibel perantau atau baris kunci,abaikan rasio solusi yang brnilai nol dan negatif, baik untuk kasus maksimasi maupun minimasi.



MATEMATIKA EKONOMI MANAJEMEN 2019 e. Bentuk tablo berikutnya dengan memasukkan varibel pendatang ke kolom VD dan mengeluarkan varibel perantau dari kolom VD, serta lakukan transformasi baris-baris tablo, termasuk baris. Transformasi baris kunci, yang sekarang bervariasi dasar baru, dilakukan sebagai berikut; Baris kunci baru = baris kunci lam: unsur kunci Sedangkan transforamsi baris –baris lainnya. Baris baru = baris lama- (unsur pada kolom kuncinya x baris kunci baru) f. Lakukan pengujian optimalitas. Jika semua koefisien variabel dasar pada baris – z sudah tidak ada lagi yang negatif(untuk kasus maksimasi; atau sudah tidakada lagi yang postif untuk kasus minimasi), berarti penyelesaian sudah optimal,tidak perlu dibentuk tablo selanjutnya. Jika masihberarti penyelesaian belum optimal,ulangi lagi langkah ke-3 sampai ke – 6.