Model Program Linier

 Model Program Linier

Program Linear adalah suatu cara untuk penyelesaian masalah dengan menggunakan persamaan atau pertidaksamaan linear yang mempunyai banyak penyelesaian, dengan memperhatikan syarat-syarat agar diperoleh hasil yang maksimum/minimum (penyelesaian optimum).

Berikut ini beberapa contoh soal cerita dalam penyelesaian dengan program linier :

1. Aini, Nia, dan Nisa pergi bersama-sama ke toko buah. Aini membeli 2 kg apel, 2 kg anggur, dan 1 kg jeruk dengan harga Rp 67.000,00. Nia membeli 3 kg apel, 1 kg anggur, dan 1 kg jeruk dengan harga Rp 61.000,00. Nisa membeli 1 kg apel, 3 kg anggur, dan 2 kg jeruk dengan harga Rp. 80.000,00. Tentukan harga 1 kg apel, 1 kg anggur, dan 4 kg jeruk.
   
   Pembahasan :
   misalkan :
   apel = x
   anggur = y
   jeruk = z
   Dari soal, dapat disusun sistem persamaan linear sebagai berikut :
   1). 2x + 2y + z = 67.000
   2). 3x + y + z = 61.000
   3). x + 3y + 2z = 80.000
   Ditanya : x + y + 4z = ....?
   Untuk menjawab pertanyaan seperti ini umumnya yang harus kita cari terlebih dahulu adalah harga satuan masing-masing barang. 
   Dari persamaan no 1 dan 2 diperoleh persamaan 4 :

   

   Dari persamaan no 2 dan 3 diperoleh persamaan 5 :

   

   Dari persamaan no 4 dan 5 diperoleh :

   

   
   Jadi harga untuk 1 kg apel, 1 kg anggur, dan 4 kg jeruk adalah :
   x + y + 4z = 12.000 + 18.000 + 4(7000) = Rp 58.000,00.
   
   
2. Pada sebuah toko buku, Ana membeli 4 buku, 2 pulpen dan 3 pensil dengan harga Rp 26.000,00. Lia membeli 3 buku, 3 pulpen, dan 1 pensil dengan harga 21.000,00. Nisa membeli 3 buku dan 1 pensil dengan harga Rp. 12.000,00. Jika Bibah membeli 2 pulpen dan 3pensil, maka tentukan biaya yang harus dikeluarkan oleh Bibah.
   
   Pembahasan :
   misalkan :
   buku = x
   pulpen = y
   pensil = z
   Dari soal, dapat disusun sistem persamaan linear sebagai berikut :
   1). 4x + 2y + 3z = 26.000
   2). 3x + 3y + z = 21.000
   3). 3x + z = 12.000
   Ditanya : 2y + 3z = ....?
   Untuk menjawab pertanyaan seperti ini umumnya yang harus kita cari terlebih dahulu adalah harga satuan masing-masing barang. Karena yang ditanya harga 2y + 3z, maka kita hanya perlu mencari harga satuan y dan z.
   Dari 3x + 3y + z = 21.000 dan 3x + z = 12.000, diperoleh harga satuan pulpen yaitu :

   

   
   
   Selanjtunya, substitusi nilai y pada persamaan 1 dan 2 sebagai berikut :
   Jadi, harga 2 pulpen dan 3 pensil adalah :
   2y + 3z = 2(3.000) + 3(2.400) = Rp 13.200,00.
   
   
3. Seorang pemilik toko sepatu ingin mengisi tokonya dengan sepatu laki-laki paling sedikit 100 pasang dan sepatu wanita paling sedikit 150 pasang. Toko tersebut hanya dapat menampung 400 pasang sepatu. Keuntungan setiap pasang sepatu laki-laki adalah Rp 10.000,00 dan keuntungan setiap pasang sepatu wanita adalah Rp 5.000,00. Jika banyaknya sepatu laki-laki tidak boleh melebihi 150 pasang, maka tentukanlah keuntungan terbesar yang dapat diperoleh oleh pemilik toko.
   
   Pembahasan :
   Pada soal ini, untuk mengetahui keuntungan terbesar maka yang menjadi fungsi tujuan atau fungsi objektifnya adalah keuntungan penjualan sepatu. Jadi fungsi tujuannya adalah :
   F(x,y) = 10.000x + 5.000y
   Dengan pemisalan :
   sepatu laki-laki = x
   sepatu perempuan = y
   Sistem pertidaksamaan untuk soal tersebut adalah sebagai berikut :
    x + y <= 400
   100 => x <= 150
   150 => y <= 250
   Karena maksimum sepatu laki-laki hanya 150 pasang, maka maksimum sepatu perempuan = 400 - 150 = 250.
   Dari sistem pertidaksamaan tersebut, maka diperoleh grafik sebagai berikut :
   

   

   Sistem pertidaksamaan linear

   
   Dari grafik jelas telihat bahwa keuntungan maksimum berada pada titik pojok paling atas yaitu titik (150,250). Maka nilai maksimum dari fungsi tujuan F(x,y) = 10.000x + 5000y adalah :
   F(150,250) = 150 (10.000) + 250 (5.000) = 2.750.000
   Jadi, keuntungan terbesar yang dapat diperoleh pemilik toko adalah Rp 2.750.000,00.
   
   
4. Seorang pembuat kue mempunyai 8 kg tepung dan 2 kg gula pasir. Ia ingin membuat dua macam kue yaitu kue dadar dan kue apem. Untuk membuat kue dadar dibutuhkan 10 gram gula pasir dan 20 gram tepung sedangkan untuk membuat sebuah kue apem dibutuhkan 5 gram gula pasir dan 50 gram tepung. Jika kue dadar dijual dengan harga Rp 300,00/buah dan kue apem dijual dengan harga Rp 500,00/buah, tentukanlah pendapatan maksimum yang dapat diperoleh pembuat kue tersebut.
   
   Pembahasan :
   Untuk mengetahui pendapatan maksimum, maka terlebih dahulu kita menyusun sistem pertidaksamaan dan fungsi tujuan dari soal cerita tersebut. Karena yang ditanya pendapatan maksimum, maka tentu harga jual kue merupakan fungsi tujuan pada soal ini. Untuk menyusun sistem pertidaksamaan, yang perlu kita lakukan adalah menentukan variabel dan koefisiennya.
   
   
   Bahan yang tersedia:
   Tepung = 8 kg = 8000 g
   Gula = 2 kg = 2000 g
   
   Misalkan :
   kue dadar = x 
   kue apem = y 
   
   Maka jumlah tepung, gula, dan harga jual merupakan koefisien. Agar lebih mudah, kita dapat memasukkan data yang ada pada soal ke dalam bentuk tabel seperti berikut :
   
   

   
   
   Dari tabel di atas dapat disusun sistem pertidaksamaan sebagai berikut :
   20x + 50y = 800 ---> 2x + 5y <= 800
   10x +5y = 2000 ---> 2x + y <= 400
   x >= 0 dan y >= 0 
   dengan fungsi tujuan f(x,y) = 300x + 500y 
   Kemudian gambarkan sistem pertidaksamaan yang sudah disusun dalam grafik. Untuk garis 2x + 5y = 800
   x = 0, y = 160 ---> (0, 160)
   y = 0, x = 400 ---> (400, 0)
   Untuk garis 2x + y = 400
   x = 0, y = 400 ---> (0, 400)
   y = 0, x = 200 ---> (200, 0)
   

   

   Sistem pertidaksamaan linear

   
   Titik B merupakan titik potong garis 2x + 5y = 800 dengan garis 2x + y = 400

   

   
   Selanjutnya substitusikan titik A, B, dan C ke fungsi tujuan :
   A(0, 160) ---> F(x,y) = 300(0) + 500(160) = 80.000
   B(100, 150) ---> F(x,y) = 300(100) + 500(150) = 105.000
   C(200, 0) ---> F(x,y) = 300(200) + 500(0) = 60.000
   
   Jadi, pendapatan maksimum yang bisa diperoleh pedagang kue itu adalah Rp 105.000,00.
   
   
5. Menjelang hari raya Idul Adha, Pak Mahmud hendak menjual sapi dan kerbau. Harga seekor sapi dan kerbau di Medan berturut-turut Rp 9.000.000,00 dan Rp 8.000.000,00. Modal yang dimiliki pak Mahmud adalah Rp 124.000.000,00. Pak Mahmud menjual sapi dan kerbau di Aceh dengan harga berturut-turut Rp 10.300.000,00 dan Rp 9.200.000,00. Kandang yang ia miliki hanya dapat menampung tidak lebih dari 15 ekor. Agar mencapai keuntungan maksimum, tentukanlah banyak sapi dan kerbau yang harus dibeli pak Mahmud.
   
   Pembahasan :
   Karena ditanya keuntungan, tentu fungsi tujuannya adalah besar keuntungan dari penjualan sapi dan kerbau. Untuk itu, tentukan terlebih dahulu keuntungan menjual sapi dan kerbau sebagai berikut :
   untung sapi = Rp 10.300.000,00 - Rp 9.000.000,00 = Rp 1.300.000,00
   untung kerbau = Rp 9.200.000,00 - Rp 8.000.000,00 = Rp 1.200.000,00
   Misalkan banyak sapi = x dan banyak kerbau = y, maka fungsi tujuan menjadi :
   F(x,y) = 1.300.000x + 1.200.000y
   Model matematika yang memenuhi soal adalah :
   x >= 0 ---> banyak sapi tidak mungkin negatif
   y >= 0 ---> banyak kerbau tidak mungkin negatif
   x + y <= 15 ---> karena kandang hanya dapat menampung 15 ekor.
   Karena modal Pak Mahmud Rp 124.000.000,00 maka :
   9.000.000x + 8.000.000y <= 124.000.000  ---> disederhanakan menjadi :
   9x + 8y <= 124
   Selanjutnya, kita tentukan titik koordinat masing-masing garis agar dapat kita gambar dalam grafik.
   Untuk x + y = 15
   jika x = 0, maka y = 15 ---> (0,15)
   jika y = 0, maka x = 15 ---> (15,0)
   Untuk 9x + 8y = 124
   jika x = 0, maka y = 15,5 ---> (0, 16) ---> digenapkan karena jumlah sapi tidak mungkin 1/2.
   jika y = 0, maka x = 13,7 ---> (13 ,0) ---> digenapkan menjadi 13 karena melihat kondisi grafik, titik ini akan menjadi titik pojok, jadi 13,7 tidak digenapkan ke 14 karena jika dibulatkan ke 14 maka akan lebih dari Rp 124.000.000,00.
   

   

   
   

   Dari grafik di atas dieproleh tiga titik pojok yang memenuhi syarat untuk menghasilkan nilai maksimum yaitu titik A, B, dan C. Titi A dan C dapat ditentukan secara langsung yaitu A(0,15) dan C(13,0). Titik B merupakan titik potong antara garis x + y = 15 dan 9x + 8y = 124.
   x + y = 15 , maka x = 15 - y ---> substitusi ke persamaan 9x + 8y = 124
   9(15 - y) + 8y = 124
   135 - 9y + 8y = 124
   y = 11
   x + y = 15
   x + 11 = 15
   x = 4 ----> jadi titik B(4,11)
   
   Selanjutnya substitusi masing-masing titik ke fungsi tujuan :
   A(0,15) ---> f(x,y) = 1.300.000(0) + 1.200.000(15) = 18.000.000
   B(4,11) ---> f(x,y) = 1.300.000(4) + 1.200.000(11) = 18.400.000
   C(13,0) ---> f(x,y) = 1.300.000(13) + 1.200.000(0) = 16.900.000
   Jadi, agar keuntungannya maksimum, jumlah sapi dan kerbau yang harus dibeli pak Mahmud adalah 4 ekor sapi dan 11 ekor kerbau.
                
   
6. Seorang pedagang menjual buah mangga dan pisang dengan menggunakan gerobak. Pedagang tersebut membeli mangga dengan harga Rp 8.000,00/kg dan pisang Rp 6.000,00/kg. Modal yang tersedia Rp 1.200.000,00 dan gerobaknya hanya dapat menampung mangga dan pisang sebanyak 180 kg. Jika harga jual mangga Rp 9.200,00/kg dan pisang Rp 7.000,00/kg, maka tentukanlah laba maksimum yang diperoleh pedagang tersebut.
   
   Pembahasan : 
   Karena ditanya laba maksimum, maka fungsi tujuannya adalah keuntungan dari menjual buah mangga dan buah pisang perkilonya.
   Berikut untung penjualan :
   mangga = 9.200 - 8.000 = 1.200
   pisang = 7.000 - 6000 = 1.000
   misalkan :
   mangga = x
   pisang = y
   maka fungsi tujuannya adalah :
   F(x,y) = 1.200x + 1.000y
   Model matematika atau sistem pertidaksamaan yang memenuhi soal tersebut adalah :
   x + y <= 180
   8.000x + 6.000y <= 1.200.000 ---> 4x + 3y <= 600
   x >= 0
   y >= 0
   Titik potong masing-masing garis terhadap sumbu x dan sumbu y :
   Garis x + y = 180
   untuk x = 0 , y = 180 ---> (0, 180)
   untuk y = 0, x = 180 ---> (180,0)
   Garis 4x + 3y = 600
   untuk x = 0, y = 200 ---> (0, 200)
   untuk y = 0, x = 150 ---> (150, 0)
   Himpunan penyelesaian sistem pertidaksamaan adalah :
   

   

   
   Dari grafik diketahui ada tiga titik pojok yaitu A, B, dan C. Titik C merupakan perpotongan antara garis x + y = 180 dengan 4x + 3y = 600.

   

   
   Substitusi titik pojok pada fungsi objektif F(x,y) 1.200x + 1.000y :
   A (0, 180) ---> F(x,y) =1.000(180) = 180.000
   B (60, 120) ---> F(x,y) = 1.200(60) + 1.000(120) = 192.000
   C (150,0) ---> F(x,y) = 1.200(150) = 180.000
   Jadi laba maksimum yang diperoleh pedagang buah adalah Rp 192.000,00.


7. Sebuah perusahaan properti memproduksi dua macam lemari pakaian yaitu tipe lux dan tipe sport dengan menggunakan 2 bahan dasar yang sama yaitu kayu jati dan cat pernis. Untuk memproduksi 1 unit tipe lux dibutuhkan 10 batang kayu jati dan 3 kaleng cat pernis, sedangkan untuk memproduksi 1 unit tipe sport dibutuhkan 6 batang kayu jati  dan 1 kaleng cat pernis. Biaya produksi tipe lux dan tipe sport masing-masing adalah Rp 40.000 dan Rp 28.000 per unit. Untuk satu periode produksi, perusahaan menggunakan paling sedikit 120 batang kayu jati dan 24 kaleng cat pernis. Bila perusahaan harus memproduksi lemari tipe lux paling sedikit 2 buah dan tipe sport paling sedikit 4 buah, tentukan banyak lemari tipe lux dan tipe sport yang harus diproduksi agar biaya produksinya minimum.
   
   Pembahasan:
   Karena yang ditanya adalah biaya produksi minimum, maka ongkos produksi masing-masing tipe lemari merupakan fungsi tujuannya. Bila kita misalkan tipe lux = x dan tipe sport = y, maka fungsi tujuannya adalah sebagai berikut :
   F(x,y) = 40.000x + 28.000y
   Selanjutnya, model matematika untuk kendala yang diberikan adalah seperti di bawah ini. Perhatikan bahwa tanda pertidaksamaan yang digunakan untuk soal penentuan nilai minimum adalah lebih besar dari sama dengan (>=) seperti di bawah ini :
   x >= 2 ---> karena tipe lux paling sedikit 2 buah
   y >= 4 ---> karena tipe sport paling sedikit 4 buah
   10x + 6y >= 120 ---> kayu jati yang digunakan paling sedikit 120 batang
   3x + y >= 24 ---> cat pernis yang digunakan paling sedikit 24 kaleng
   Titik potong masing-masing kendala terhadap sumbu x dan sumbu y adalah sebagai berikut :
   untuk 10x + 6y = 120
   misal x = 0, maka y = 20 ---> (0,20)
   misal y = 0, maka x = 12 ---> (12,0)
   untuk 3x + y = 24
   misal x = 0, maka y = 24 ---> (0,24)
   misal y = 0, maka x = 8 ---> (8,0)
   Setelah itu kita gambarkan grafik sesuai dengan titik-titik yang telah kita peroleh dan tentukan daerah himpunan penyelesaiannya. Karena lebih besar sama dengan (>=), maka daerah himpunan penyelesaiannya adalah daerah di atas/kanan garis.
   

   

   
   Dari garfik di atas jelas terlihat bahwa terdapat tiga titik pojok yang akan diuji untuk dilihat titik manakah yang menghasilkan nilai minimum.
   Titik C merupakan perotongan antara garis y = 4 dan 10x + 6y = 120. Dengan mensubstitusi nilai y = 4 pada persamaan 10x + 6y = 120, maka diperoleh :
   10x + 6(4) = 120
   10x = 96
   x = 9,6 = 9 ---> digenapkan 9 karena tidak mungkin 0,6 buah.
   maka titik C(9,4)
   Titik B merupakan perpotongan antara garis 10x + 6y = 120 dan garis 3x + y = 24. Dengan metode substitusi diperoleh :
   3x + y = 24 ---> y = 24 - 3x ---> substitusi ke persamaan 10x + 6y = 120
   10x + 6(24 - 3x) = 120
   10x + 144 - 18x = 120
   -8x = -24
   x = 3
   Sunstitusi x = 3 ke persamaan y = 24 - 3x
   y = 24 - 3(3) = 15 ---> titik B(3,15)
   Titik A merupakan perpotongan antara garis 3x + y = 24 dengan x = 2. Dengan mensubstitusikan nilai x pada persamaan 3x + y = 24, maka diperoleh :
   3(2) + y = 24
   y = 24 - 6
   y = 18 ---> titik A(2,18)
   Langkah terakhir, substitusi masing-masing titik ke fungsi tujuan F(x,y) = 40.000x + 28.000y sebagai berikut :
   A(2,18) ---> F(x,y) = 40.000(2) + 28.000(18) = 584.000
   B(3,15) ---> F(x,y) = 40.000(3) + 28.000(15) = 540.000
   C(9,4) ---> F(x,y) = 40.000(9) + 28.000(4) = 482.000
   Jadi agar biaya produksi minimum, perusahaan sebaiknya memproduksi 9 buah lemari tipe lux dan 4 buah lemari tipe sport dengan biaya produksi Rp 482.000,00
   
   
8. Seorang pedagang furnitur ingin mengirim barang dagangannya yang terdiri atas 1.200 kursi dan 400 meja. Untuk keperluan tersebut, ia akan menyewa truk dan colt. Truk dapat memuat 30 kursi lipat dan 20 meja lipat, sedangkan colt dapat memuat 40 kursi lipat dan 10 meja lipat. Ongkos sewa sebuah truk Rp 200.000,00 sedangkan ongkos sewa sebuah colt Rp 160.000,00. Tentukan jumlah truk dan colt yang harus disewa agar ongkos pengiriman minimum.
   
   Pembahasan :
   Agar ongkos kirim minimum, maka fungsi tujuannya adalah ongkos sewa. Misal truk = x dan colt = y, maka fungsi tujuannya menjadi :
   F(x,y) = 200.000x + 160.000y
   Model matematika yang memenuhi soal di atas adalah sebagai berikut :
   30x + 40y >=1.200 ---> 3x + 4y >= 120
   20x + 10y >= 400 ---> 2x + y >= 40
   x >= 0
   y >= 0
   
Tentukan titik koordinat garis kendala yang diperoleh sebagai beikut :
untuk 3x + 4y >= 120
misal x = 0, maka y = 30 ---> (0,30)
misal y = 0, maka x = 40 ---> (40,0)
untuk 2x + y >= 40
misal x = 0, maka y = 40 ---> (0,40)
misal y = 0, maka x = 20 ---> (20,0) 
Gambarkan ke dalam grafik dan tentukan daerah himpunan penyelesaiannya seperti berikut :

Dari grafik di atas,diperoleh titik A(0,40), B(8,24), dan C(40,0). Untuk memastikan titik mana yang menghasilkan nilai minimum, ada baiknya kita uji satu-persatu.
A(0,40) ---> F(x,y) = 200.000(0) + 160.000(40) = 6.400.000
B(8,24) ---> F(x,y) = 200.000(8) + 160.000(24) = 5.440.000
C(40,0) ---> F(x,y) = 200.000(40) + 160.000(0) = 8.000.000

Jadi agar biaya pengiriman minimum, pedagang tersebut sebaiknya menyewa 8 truk dan 24 colt.


9. Seorang petani memiliki tanah tidak kurang dari 10 hektar. Ia merencanakan akan menanami padi seluas 2 hektar sampai dengan 6 hektar dan menanam jagung seluas 4 hektar sampai dengan  6 hektar. Untuk menanam padi perhektarnya diperlukan biaya Rp 400.000,00 sedangkan untuk menanam jagung per hektarnya diperlukan biaya Rp 200.000,00. Agar biaya tanam minimum, tentukan berapa banyak masing-masing padi dan jagung yang harus ditanam.
   
   Pembahasan :
   Dengan memisalkan padi = x dan jagung = y, fungsi tujuan yang memenuhi soal di atas adalah sebagai berikut :
   F(x,y) = 400.000x + 200.000y
   Model matematika yang memenuhi soal di atas adalah :
   x >= 2 ---> paling sedikit 2 hektar padi
   x <= 6 ---> paling banyak 6 hektar padi
   y >= 4 ---> paling sedikit 4 hektar jagung
   y <= 6 ---> paling banyak 6 hektar padi
   x + y >= 10 ---> tanah tidak kurang 10 hektar
   

   

   
   Dari grafik diketahui titik pojok A(4,6), B(6,6), dan C(6,4). Substitusi ke fungsi tujuan F(x,y) = 400.000x + 200.000y, maka diperoleh :
   A(4,6) ---> F(x,y) = 400.000(4) + 200.000(6) = 2.800.000
   B(6,6) ---> F(x,y) = 400.000(6) + 200.000(6) = 3.600.000
   C(6,4) ---> F(x,y) = 400.000(6) + 200.000(4) = 3.200.000
   Jadi agar biaya tanam minimum, petani sebaiknya menanam 4 hektar padi dan 6 hektar jagung.

Teknik Artificial Variabel

Progam Linier dengan kendala  Metode Teknik M

Pembahasan terdahulu hanya kendala bertanda ≤ , topik pembahasan selanjutnya untuk kendala bertanda ≥ dan atau bertanda =  maka untuk menyelesaikan kasus tersebut kita memerlukan variable dummy(variable palsu) atau artificial var. sehingga basis awal bisa tetap ada .Untuk tanda ≥ masih menggunakan variable S dan R sedangkan untuk tanda (=) menggunakan variable dummy R saja.

 

Contoh :

Maksimumkan Z = 3X1 + 5X2

Berdasarkan kendala :

X1 ≥ 4

2X2 ≥ 12

3X1 + 2X2 = 18

X1, X2 ≥ 0

PL dg kendala  atau = lanjutan

Jika dituliskan dalam bentuk standar :

Maksimumkan Z = 3X1 + 5X2 +0S1 + 0S2 – MR1– MR2 – MR3

Atau

Z – 3X1 – 5X2 + 0S1 + 0S2 + MR1 + MR2 + MR3 = 0

X1 - S1 + R1 = 4

2X2 – S2 + R2 = 12

3X1 + 2X2 + R3 = 18

X1, X2 , S1 , S2 , R1 , R2 , R3 ≥ 0

Perhatikan bahwa penalty M di atas bertanda (–) karena fungsi tujuannya maksimasi, jika fungsi tujuannya minimasi, maka penalty bertanda (+), dengan M adalah bilangan yang cukup besar.

 

Contoh 1 Solusi PL dg Teknik M

Metoda Big M (metode penalty)

Contoh 1 : Cari solusi PL berikut ini

Maksimumkan Z = 3X1 + 5X2

Berdasarkan kendala :

X1 ≤ 4

2X2 ≤ 12

3X1 + 2X2 = 18

X1, X2 ≥ 0

Penyelesaian :

Karena pembatas ketiga bertanda ( = ), maka untuk mendapatkan solusi basis awalnya kita harus menambahkan variable artificial sehingga diperoleh bentuk :

Maksimumkan :

Z = 3X1 + 5X2 + 0.S1 + 0.S2 – MR1

Contoh 1 Solusi PL dg Teknik M

Berdasarkan kendala :

X1 + S1 = 4

2X2 + S2 = 12

3X1 + 2X2 + R1 = 18

X1, X2, R1 , S1, S2 ≥ 0

Untuk memasukan model diatas kedalam bentuk table, maka terlebih dahulu subtitusikan R1 dari persamaan kendala ketiga :

R1 = 18 - 3X1 + 2X2

Kemudian masukan kedalam persamaan Z :

Z = 3X1 + 5X2 + 0.S1 + 0.S2 – M(18 - 3X1 + 2X2 )

Atau

Z = (3M + 3)X1 + (2M – 5)X2 + 0.S1 + 0.S2 – 18M atau

Z - (3M + 3)X1 - (2M – 5)X2 - 0.S1 - 0.S2 = -18M

Sehingga tabel simpleks awal (iterasi 0) dan iterasi ke 1 diberikan dalam tabel berikut ini :

Solusi Masalah Menggunakan Metode Big M

Persoalan di atas mempunyai model PL sbb. :

min z = 2x1 + 3x2 , dengan Z adalah biaya produksi

Berdasarkan kendala :

0.5x1 + 0.25x2 ≤ 4 (gula)

x1 + 3x2 ≥ 20 (Vitamin C)

x1 + x2 = 10 (10 ons dalam 1 botol)

x1, x2  0

Bentuk standar PL masalah ini ditampilkan dalam slide berikut :

Solusi Masalah Menggunakan Metode Big M

Baris 1 : -z + 2x1 + 3x2 = 0

Baris 2 : 0.5x1 + 0.25x2 + s1 = 4

Baris 3 : x1 + 3x2 - s2 = 20

Baris 4 : x1 + x2 = 10

Dengan menggunakan teknik artificial variables, yakni dengan menambahkan variabel artifisial a2 pada baris ketiga dan a3 pada baris keempat. Variabel a2 dan a3 ditulis hitam, maka diperoleh :

Baris 1 : -z + 2x1 + 3x2 = 0

Baris 2 : 0.5x1 + 0.25x2 + s1 = 4

Baris 3 : x1 + 3x2 - s2 + a2 = 20

Baris 4 : x1 + x2 + a3 = 10

Metode Dua Phasa

Digunakannya konstanta M ( bilangan positif yang sangat besar) sebagai penalty, bisa terjadi kesalahan perhitungan, terutama apabila perhitungan itu dilakukan dengan menggunakan computer. Kesalahan itu bisa terjadi karena koefisien fungsi tujuan relative sangat kecil dibandingkan dengan harga M sehingga computer akan memperlakukannya sebagai koefisien yang berharga nol. Kesulitan ini bisa dikurangi dengan menggunakan metoda dua fase. Disini konstanta M dihilangkan dengan cara menyelesaikan persoalan dalam dua fase sebagai berikut : 

 

Fase 1 : Fase ini digunakan untuk menguji apakah persoalan yang kita hadapi memiliki solusi fisibel atau tidak. Pada fase ini fungsi tujuan semula diganti dengan meminimumkan jumlah variable artifisialnya. Jika nilai minimum fungsi tujuan baru ini berharga nol, berarti persoalan memiliki solusi fisibel, lanjutkan ke fase 2 tetapi, jika nilai minimum fungsi tujuan baru ini berharga positif, maka persoalan tidak memiliki solusi fisibel.

STOP

 

Metode Dua Phasa Lanjutan

Fase 2 :

Gunakan solusi basis optimum dari fase 1 sebagai

solusi awal bagi persoalan semula. Dalam hal ini

ubahlah bentuk fungsi tujuan fase 1 dengan

mengembalikannya pada fungsi tujuan persoalan

semula.

Pemecahan persoalan dilakukan dengan cara seperti biasa.

METODE SIMPLEKS DALAM PROGRAM LINIER

METODE SIMPLEKS DALAM PROGRAM LINIER

Metode simpleks merupakan salah satu teknik penyelesaian dalam program linier yang digunakan  sebagai teknik pengambilan keputusan dalam permasalahan yang berhubungan dengan  pengalokasian sumberdaya secara optimal. Metode simpleks digunakan untuk mencari nilai optimal  dari program linier yang melibatkan banyak constraint (pembatas) dan banyak variabel (lebih dari dua variabel). Penemuan metode ini merupakan lompatan besar dalam riset operasi dan digunakan  sebagai prosedur penyelesaian dari setiap program computer.

Salah satu teknik penentuan solusi optimal yang digunakan dalam pemrograman linier adalah metode simpleks.  Penentuan solusi optimal menggunakan metode simpleks didasarkan pada teknik eleminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim satu per satu dengan cara perhitungan iteratif. Sehingga penentuan solusi optimal dengan simpleks dilakukan tahap demi tahap yang disebut dengan iterasi. Iterasi ke-i hanya tergantung dari iterasi sebelumnya (i-1).
 

Ada beberapa istilah yang sangat sering digunakan dalam metode simpleks, diantaranya yaitu : 

1.Iterasi adalah tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai tabel sebelumnya.
2.Variabel non basis adalah variabel yang nilainya diatur menjadi nol pada sembarang iterasi. Dalam       terminologi umum, jumlah variabel non basis selalu sama dengan derajat bebas  dalam sistem persamaan. 
3.Variabel basis merupakan variabel yang nilainya bukan nol pada sembarang iterasi. Pada solusi awal, variabel basis merupakan variabel slack (jika fungsi kendala merupakan pertidaksamaan ≤ ) atau variabel buatan (jika fungsi kendala menggunakan  pertidaksamaan ≥ atau =). Secara umum, jumlah variabel basis selalu sama  dengan  jumlah fungsi pembatas (tanpa fungsi non negatif).
4. Solusi atau nilai kanan merupakan nilai sumber daya pembatas yang masih tersedia. Pada solusi awal, nilai kanan atau solusi sama dengan jumlah sumber daya pembatas  awal yang ada, karena aktivitas belum dilaksanakan.
5. Variabel slack adalah variabel yang ditambahkan ke model matematik kendala untuk mengkonversikan  pertidaksamaan ≤ menjadi persamaan (=). Penambahan variabel ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel slack akan berfungsi sebagai variabel basis.
6. Variabel surplus adalah variabel yang dikurangkan  dari model matematik kendala untuk mengkonversikan  pertidaksamaan ≥ menjadi persamaan (=). Penambahan ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel surplus tidak dapat berfungsi sebagai variabel basis.
7. Variabel buatan adalah variabel yang ditambahkan ke model matematik kendala dengan bentuk ≥ atau = untuk difungsikan sebagai variabel basis awal. Penambahan variabel ini terjadi pada tahap inisialisasi.Variabel ini harus bernilai 0 pada solusi optimal, karena kenyataannya variabel ini tidak ada. Variabel hanya ada di atas kertas.
8. Kolom pivot (kolom kerja) adalah kolom yang memuat variabel masuk. Koefisien pada kolom ini akn menjadi pembagi nilai kanan untuk menentukan baris pivot (baris kerja).
9. Baris pivot (baris kerja) adalah salah satu baris dari antara variabel basis yang memuat variabel keluar.
10. Elemen pivot (elemen kerja) adalah elemen yang terletak pada perpotongan kolom dan baris pivot. Elemen pivot akan menjadi dasar perhitungan untuk tabel simpleks berikutnya.
11. Variabel masuk adalah variabel yang terpilih untuk menjadi variabel basis pada iterasi berikutnya. Variabel masuk dipilih satu dari antara variabel non basis pada setiap iterasi. Variabel ini pada iterasi berikutnya akan bernilai positif.
12. Variabel keluar adalah variabel yang keluar dari variabel basis pada iterasi berikutnya dan digantikan oleh variabel masuk. Variabel keluar dipilih satu dari antara variabel basis pada setiap iiterasi. Variabel ini pada iterasi berikutnya akan bernilai nol.

BENTUK BAKU

Sebelum melakukan perhitungan iteratif untuk menentukan solusi optimal, pertama sekali bentuk umum pemrograman linier dirubah ke dalam bentuk baku terlebih dahulu. Bentuk baku dalam metode simpleks tidak hanya mengubah persamaan kendala ke dalam bentuk sama dengan, tetapi setiap fungsi kendala harus diwakili oleh satu variabel basis awal. Variabel basis awal menunjukkan status sumber daya pada kondisi sebelum ada aktivitas yang dilakukan. Dengan kata lain, variabel keputusan semuanya masih bernilai nol. Dengan demikian, meskipun fungsi kendala pada bentuk umum pemrograman linier sudah dalam bentuk persamaan, fungsi kendala tersebut masih harus tetap berubah.

Ada beberapa hal yang harus diperhatikan dalam membuat  bentuk baku, yaitu :

1. Fungsi kendala dengan pertidaksamaan ≤ dalam bentuk umum, dirubah menjadi persamaan (=) dengan menambahkan satu variabel slack.
2. Fungsi kendala dengan pertidaksamaan ≥ dalam bentuk umum, dirubah menjadi persamaan (=) dengan mengurangkan satu variabel surplus.
3. Fungsi kendala dengan persamaan dalam benttuk umum,ditambahkan satu artificial variabel (variabel buatan).

Contoh Soal :

Selesaikan kasus berikut ini menggunakan metode simpleks :

Maksimum z = 8 x₁ + 9 x₂ + 4x₃

Kendala :

x₁ + x₂ + 2x₃ ≤ 2

2x₁ + 3x₂ + 4x₃ ≤ 3

7x₁ + 6x₂ + 2x₃ ≤ 8

x₁,x₂,x₃ ≥ 0

Penyelesaian :

Bentuk bakunya adalah :

Maksimum z = 8 x₁ + 9 x₂ + 4x₃ + 0s₁ + 0s₂ + 0s₃ atau

                     z - 8 x₁ - 9 x₂ - 4x₃ + 0s₁ + 0s₂ + 0s₃ = 0

Kendala :

x₁ + x₂ + 2x₃ + s₁  = 2

2x₁ + 3x₂ + 4x₃ + s₂ = 3

7x₁ + 6x₂ + 2x₃  + s₃ = 8

x₁,x₂,x₃ ,s₁ , s₂ , s₃ ≥ 0

Solusi / table awal simpleks :

VB	X1	X2	X3	S1	S2	S3	NK	Rasio
Z	-8	-9	-4	0	0	0	0
S1	1	1	2	1	0	0	2
S2	2	3	4	0	1	0	3
S3	7	6	2	0	0	1	8

Karena nilai negative terbesar  ada pada kolom X₂, maka kolom X₂ adalah kolom pivot dan X₂ adalah variabel masuk. Rasio pembagian nilai kanan  dengan kolom pivot terkecil adalah 1 bersesuaian  dengan  baris s₂, maka baris s₂ adalah baris pivot dan s₂ adalah varisbel keluar. Elemen pivot adalah 3.

VB	X1	X2	X3	S1	S2	S3	NK	Rasio
Z	-8	-9	-4	0	0	0	0
S1	1	1	2	1	0	0	2	2
S2	2	3	4	0	1	0	3	1
S3	7	6	2	0	0	1	8	8/6

Iterasi 1

Nilai pertama yang kita miliki adalah nilai baris  pivot baru (baris x₂). Semua nilai pada baris s₂ pada tabel solusi awal dibagi dengan 3 (elemen pivot).

VB	X1	X2	X3	S1	S2	S3	NK	Rasio
Z
S1
x2	2/3	1	4/3	0	1/3	0	1
S3

Perhitungan nilai barisnya :

Baris z :

             -8         -9         -4         0          0          0          0

    -9 (  2/3          1         4/3       0          1/3        0          1 )   -

            -2           0          8         0           3         0         9

Baris s₁ :

             1          1          2          1          0          0          2

     1   (2/3        1          4/3       0          1/3       0          1 ) -

            1/3       0          2/3       1          -1/3      0          1

Baris s3 :

             7          6          2          0          0          1          8

     6  ( 2/3        1          4/3        0          1/3       0          1 ) -

            3          0          -6         0          -2         1          2

Maka tabel iterasi 1 ditunjukkan tabel di bawah. Selanjutnya kita periksa apakah tabel sudah optimal atau belum. Karena nilai baris z di bawah variabel x₁ masih negatif, maka tabel belum optimal. Kolom dan baris pivotnya ditandai pada tabel di bawah ini :

VB	X1	X2	X3	S1	S2	S3	NK	Rasio
Z	-2	0	8	0	3	0	9	-
S1	1/3	0	2/3	1	-1/3	0	1	3
X2	2/3	1	4/3	0	1/3	0	1	3/2
S3	3	0	-6	0	-2	1	2	2/3

Variabel masuk  dengan demikian adalah X₁ dan variabel  keluar adalah S₃ .Hasil perhitungan iterasi ke 2 adalah sebagai berikut :

Iterasi 2 :

VB	X1	X2	X3	S1	S2	S3	NK	Rasio
Z	0	0	4	0	5/3	2/3	31/3
S1	0	0	4/3	1	-1/9	-1/9	7/9
X2	0	1	8/3	0	7/9	-2/9	5/9
X1	1	0	-2	0	-2/3	1/3	2/3

Tabel sudah optimal, sehingga perhitungan iterasi dihentikan !

Perhitungan dalam simpleks menuntut ketelitian  tinggi, khususnya jika angka yang digunakan adalah pecahan. Pembulatan harus diperhatikan dengan baik. Disarankan jangan menggunakan bentuk bilangan desimal, akan lebih teliti jika menggunakan bilangan pecahan. Pembulatan dapat menyebabkan iterasi lebih panjang atau bahkan tidak selesai karena ketidaktelitian dalam melakukan pembulatan.

Perhitungan iteratif dalam simpleks pada dasarnya merupakan pemeriksaan satu per satu titik-titik ekstrim layak pada daerah penyelesaian. Pemeriksaan dimulai dari kondisi nol (dimana semua aktivitas/variabel keputusan bernilai nol). Jika titik ekstrim berjumlah n, kemungkinan terburuknya kita akan melakukan perhitungan iteratif sebanyak n kali.