Metode simpleks (simplex method) adalah algoritma yang populer digunakan untuk menyelesaikan masalah dalam pemrograman linear.[1]

Polihedron dari algoritma simpleks dalam tiga dimensi.

Nama dari algoritma ini berasal dari konsep simpleks, perumuman dari konsep segitiga atau tetrahedron pada sebarang dimensi; dan diusulkan oleh T. S. Motzkin.[2] Simpleks sebenarnya tidak digunakan, namun salah satu intepretasi menjelaskan bahwa algoritma ini berkerja pada sinar kerucut (kerucut sederhana, simplicial cones); yang sama dengan simpleks ketika menambah sebuah konstrain tambahan.[3][4][5][6] Sinar kerucut yang dimaksud adalah rusuk-rusuk dari bangun geometris yang dikenal dengan politop. Bentuk dari politop ini didefinisikan lewat kendala-kendala yang perlu dipenuhi oleh fungsi objektif.

Sejarah

sunting

Pada masa Perang Dunia II George Dantzig bekerja di AU Amerika Serikat untuk mengurus metode penjadwalan. Selama tahun 1946, rekan kerjanya menantang dia untuk menstandarkan (mechanize) proses penjadwalan, untuk mengalihkan perhatiannya dari mengambil pekerjaan-pekerjaan lain. Terinspirasi dari karya Wassily Leontief, Dantzig memformulasi masalah sebagai sistem pertidaksamaan linear. Namun pada saat itu ia tidak mengikutkan objektif sebagai bagian dalam formulasi. Tanpa sebuah objektif, ada banyak solusi yang mungkin; sehingga untuk mencari solusi yang "optimal", aturan-aturan militer perlu digunakan untuk menjelaskan objektif yang diinginkan. Pencerahan yang didapatkan Dantzig adalah banyak dari aturan-aturan militer tersebut dapat disusun menjadi sebuah fungsi objektif linear yang perlu dimaksimumkan.[7] Perkembangan metode simpleks adalah sebuah inovasi dan terjadi hanya dalam kurun waktu sekitar satu tahun.[8]

Setelah Dantzig mengikutsertakan fungsi objektif dalam formulasinya pada sekitar tahun 1947, permasalahan menjadi lebih mudah secara matematis. Dantzig menyadari satu dari pertanyaan belum terpecahkan yang tidak sengaja dia selesaikan, karena ia pikir itu adalah pekerjaan rumah dari profesornya Jerzy Neyman, dapat digunakan untuk menemukan algoritma bagi program linear. Pertanyaan itu melibatkan proses mencari eksistensi pengali Langrange untuk program linear secara umum. Program linear ini dapat terdiri dari banyak variabel, masing-masing terbatas (bounded) diantara nol dan satu, dan memenuhi kendala linear yang dinyatakan dalam bentuk integral Lebesgue. Dantzig kemudian mempublikasikan "pekerjaan rumah"-nya sebagai tesis untuk mendapatkan gelar doktor. Geometri yang digunakan dalam tesis ini memberikan Dantzig wawasan bahwa metode simpleks dapat sangat efisien.[9]

Gambaran umum

sunting
 
Sebuah sistem pertidaksamaan linear yang mendefinisikan sebuah politop sebagai daerah feasibel. Algoritma simpleks bermula dari sebuah titik ekstrem, dan berjalan sepanjang rusuk pada politop, sampai mencapai titik dengan nilai fungsi objektif yang optimal.

Algoritma simpleks bekerja pada program linear dalam bentuk kanonik (baku):

Maksimumkan  
dengan kendala   dan  

Dalam bentuk ini, vektor   adalah koefisien dari fungsi objektif,   adalah operasi transpos, dan   adalah variabel-variabel dari masalah. Selain itu,   adalah matriks berukuran   dan  . Ada cara mudah untuk menyusun sebarang program linear menjadi bentuk bakunya, sehingga penggunaan bentuk ini tidak mengurangi keumuman dari pembahasan. Dalam konteks geometri, daerah feasibel nilai   yang memenuhi kendala   dan   adalah sebuah politop konveks, yang mungkin tidak terbatas (unbounded). Sebuah titik ekstrem atau rusuk dari politop ini dikenal sebagai solusi feasibel sederhana (basic feasible solution, BFS).

Dapat ditunjukkan untuk program linear dalam bentuk baku, jika fungsi objektif mempunyai nilai maksimum di daerah feasibel, maka nilai maksimum ini terletak di (setidaknya satu) titik ekstrem.[10] Hal ini menyederhanakan program linear menjadi sebuah masalah komputasi yang mudah, karena hanya terdapat terhingga banyaknya titik ekstrem; walaupun jumlah titik ekstrem dapat terlalu banyak untuk dapat ditangani.[11] Selain itu, juga dapat dibuktikan jika sebuah titik ekstrem tidak memberikan fungsi objektif nilai yang maksimum, maka ada rusuk dari titik tersebut yang "mengarahkan" fungsi objektif ke nilai yang lebih tinggi.[12] Jika panjang rusuk terhingga, maka rusuk akan terhubung dengan sebuah titik ekstrem lain yang memiliki nilai fungsi objektif lebih tinggi; namun jika panjang rusuk tak hingga, nilai fungsi objektif akan tidak terbatas dan program linear tidak memiliki solusi. Algoritma simpleks menerapkan wawasan ini, dengan "berjalan" sepanjang rusuk-rusuk dari politop untuk mencapai titik ekstrem dengan nilai fungsi objektif paling besar; atau berhenti ketika mencapai rusuk dengan panjang tak terbatas. Algoritma selalu berakhir (terminates) karena ada terhingga banyaknya rusuk pada politop. Selain itu, karena kita menelurusi rusuk-rusuk dalam "arah yang sama" dengan fungsi objektif, kita berharap hanya sedikit rusuk yang perlu dikunjungi.[12]

Solusi dari program linear dikerjakan dalam dua tahap. Pada Tahap I, sebuah titik ekstrem ditentukan. Tergantung dari program yang dikerjakan, hal ini dapat dilakukan secara trivial, atau dengan menerapkan algoritma simpleks ke suatu modifikasi dari program semula. Tahap ini dapat menghasilkan sebuah solusi feasibel sederhana, atau tidak sama sekali (karena daerah feasibel kosong). Untuk kasus kedua, program linear dikatakan tidak feasibel. Selanjutnya pada Tahap II, algoritma simpleks diterapkan pada solusi feasibel sederhana yang didapat pada Tahap I sebagai titik mulai pengerjaan. Hasil dari Tahap II adalah sebuah solusi feasibel yang optimal, atau sebuah rusuk dengan panjang terbatas (yang menyebabkan nilai fungsi tidak terbatas dari atas).[13][14][15]

Bentuk baku

sunting

Sebuah program linear dapat diubah ke dalam bentuk baku dengan cara sebagai berikut:[16] Pertama, untuk setiap variabel dengan nilai batas bawah yang berbeda dengan 0, sebuah variabel baru didefinisikan untuk merepresentasikan selisih antara variabel asal dan batas bawahnya. Variabel asal selanjutnya dapat dihilangkan dengan melakukan subtitusi. Sebagai contoh, misalkan ada kendala  

Sebuah variabel baru,  , didefinisikan sebagai

 

Persamaan kedua dapat digunakan untuk menghilangkan semua kemunculan   di program linear yang dikerjakan. Dengan cara ini, semua batas bawah dari kendala-kendala dapat diubah agar bernilai nonnegatif.

Kedua, untuk setiap kendala dalam bentuk pertidaksamaan yang tersisa, sebuah variabel baru yang disebut variabel lempai (slack), didefinisikan untuk mengubah pertidaksamaan tersebut menjadi sebuah persamaan. Variabel ini merepresentasikan perbedaan antara kedua sisi pertidaksamaan, dan diasumsikan bernilai nonnegatif. Sebagai contoh, dua pertidaksamaan berikut

 

akan diubah bentuknya menjadi

 

Jauh lebih mudah melakukan manipulasi aljabar pada pertidaksamaan yang disusun dalam bentuk ini. Untuk pertidaksamaan yang melibatkan operator ≥, beberapa penulis merujuk variabel lempai sebagai variabel surplus.

Ketiga, semua variabel yang tidak terbatas nilainya dihapus dari program linear. Hal ini dapat dilakukan dengan dua cara. Cara pertama dilakukan dengan menuliskan variabel tersebut sebagai sebuah persamaan berisi variabel-variabel lain, lalu menghilangkan semua kemunculannya di program linear dengan subtitusi. Cara lain adalah dengan menyatakan variabel tersebut sebagai selisih dua variabel yang terbatas nilainya. Sebagai contoh jika nilai   tidak dibatasi, nilainya dapat ditulis sebagai

 

Persamaan ini selanjutnya digunakan untuk mengeliminasi   dari program linear.

Setelah proses-proses tersebut dilakukan, daerah feasibel akan memiliki bentuk

 

Dalam pembahasan, umumnya berguna untuk mengasumsikan bahwa rank dari   sama dengan banyak baris dari matriks tersebut. Hal ini tidak mengurangi keumuman, karena antara sistem   mengandung persamaan yang redundan (sehingga dapat dihapus), atau sistem tersebut tidak konsisten (sehingga tidak memiliki solusi).[17]

Tablo simpleks

sunting

Sebuah program linear dalam bentuk baku dapat representasikan sebagai sebuah tablo (tableau) berikut

 

Baris pertama matriks di atas mendefinisikan fungsi objektif, sedangkan sisanya mendefinisikan kendala-kendala dari program. Nol pada kolom pertama merepresentasikan vektor nol dengan dimensi yang sama dengan vektor   (beberapa penulis menggunakan konvensi tablo yang berbeda). Jika kolom dari matriks   diatur agar mengandung matriks identitas berukuran   (yakni banyaknya baris di  ) maka tablo dikatakan dalam bentuk kanonik.[18] Variabel-variabel yang bersesuaian dengan kolom-kolom dari matriks identitas disebut dengan variabel sederhana (basic variables), sedangkan variabel yang tersisa disebut variabel bebas (free variables, atau nonbasic).

Jika nilai dari variabel bebas ditetapkan sama dengan 0, maka nilai dari variabel sederhana dapat dengan mudah ditentukan sebagai entri dari  . Lebih lanjut, solusi ini adalah sebuah solusi feasibel sederhana. Intepretasi aljabar kejadian ini terlihat dengan memandang koefisien-koefisien dari persamaan linear yang direpresentasikan setiap baris, dapat bernilai  ,  , atau suatu bilangan lainnya. Setiap baris akan memiliki   kolom bernilai  ,   kolom dengan nilai koefisien  , sedangkan kolom yang tersisa berisi nilai koefisien lainnya (kolom-kolom ini merepresentasikan variabel-variabel bebas). Dengan membuat nilai setiap variabel bebas sama dengan nol pada setiap baris, kita memastikan setiap variabel yang direpresentasikan oleh   pada kolom dari  , akan sama dengan nilai   pada baris tersebut. Sebaliknya, jika diberikan sebuah solusi feasibel sederhana, kolom yang berkorespodensi dengan variabel yang bernilai tidak nol, dapat dikembangkan menjadi sebuah matriks tak singular. Jika tablo yang bersangkutan dikalikan dengan invers dari matriks ini, maka tablo tersebut berubah menjadi bentuk kanoniknya.[19]

Misalkan

 

adalah sebuah tablo dalam bentuk kanoniknya. Operasi baris dasar dapat diterapkan pada baris pertama untuk menghilangkan koefisien   dari fungsi objektif. Hasil akhir dari proses ini adalah sebuah tablo bentuk kanonik dalam format

 

dengan   menyatakan nilai fungsi objektif pada solusi feasibel sederhana yang bersangkutan. Koefisien baru   menyatakan kerugian relatif (relative cost), yakni representasi dari laju perubahan fungsi objektif relatif terhadap variabel-variabel bebas.[14]

Operasi pivot

sunting

Operasi pivot (poros, sumbu) adalah implementasi dari operasi geometris "memindahkan" nilai fungsi objektif dari sebuah solusi feasibel sederhana ke solusi feasibel lainnya. Pertama, sebuah elemen pivot   yang nilainya tidak sama dengan nol, dipilih dari sebuah kolom variabel bebas. Anggap baris yang mengandung elemen tersebut adalah baris ke-  pada tablo. Berikutnya, baris yang mengandung elemen ini dikali dengan   (sehingga nilai dari elemen pivot menjadi sama dengan 1). Kemudian kelipatan dari baris ini ditambahkan ke baris-baris lainnya sedemikian sehingga elemen-elemen di kolom variabel bebas tersebut bernilai sama dengan 0. Dengan kata lain, kolom variabel bebas yang mengandung elemen pivot (yakni kolom ke- ) menjadi sama dengan kolom ke-  dari sebuah matriks identitas.

Operasi ini mengubah kolom variabel bebas menjadi kolom variabel sederhana. Tablo masih dalam bentuk kanonik, namun himpunan variabel bebasnya berubah satu elemen.[13][14]

Algoritma

sunting

Misalkan sebuah program linear sudah tersaji dalam bentuk kanonik. Algoritma simpleks bekerja dengan menerapkan operasi pivot secara berulang untuk mendapatkan solusi feasibel sederhana yang lebih baik. Pemilihan elemen pivot pada setiap langkah sebagian besar ditujukan untuk mencari solusi yang lebih baik.

Pemilihan kolom pivot

sunting

Jika ada lebih dari satu entri pada baris fungsi objektif (terletak di baris pertama pada tablo) yang bernilai positif, ada kebebasan dalam memilih kolom yang akan menjadi variabel sederhana; beberapa aturan pemilihan[20] seperti algoritma Devex[21] dikembangkan untuk memilih kolom. Jika semua entri objektif bernilai 0 atau kurang dari itu, maka tidak ada kolom pivot yang dapat pilih, dan solusi yang didapat sudah optimal. Keoptimalan dapat terlihat karena baris fungsi objektif setara dengan persamaan dengan bentuk

 

Mengubah aturan pemilihan agar memilih entri bernilai negatif dari baris fungsi objektif, akan membuat algoritma mencari minimum dari fungsi objektif ketimbang maksimum.

Pemilihan baris pivot

sunting

Setelah kolom pivot terpilih, pemilihan baris pivot sebagian besar dilakukan agar solusi yang didapat masih feasibel. Pertama, hanya entri bernilai positif pada kolom pivot yang dipertimbangkan, karena entri-entri ini yang memastikan nilai variabel tetap nonnegatif. Namun jika tidak ada entri bernilai positif pada kolom pivot, maka variabel dapat bernilai sembarang nilai nonnegatif; dalam kasus ini fungsi objektif tidak terbatas dari bawah, sehingga tidak memiliki minimum.

Selanjutnya, baris pivot yang dipilih perlu menjaga variabel-variabel sederhana lainnya tetap positif. Jika kolom pivot adalah kolom ke- , maka baris ke-  untuk pivot dipilih sehingga nilai  bernilai minimum untuk semua  ; dengan  . Pemilihan ini disebut tes rasio terkecil (minimum ratio test).[20] Jika ada lebih dari satu kolom dengan nilai minimum yang sama, aturan pemilihan variabel (dropping variable choice rule)[22] dapat digunakan untuk menentukan baris.

Contoh

sunting

Perhatikan program linear

Minimumkan  
Dengan kendala
 

Dengan menambah variabel lempai   dan  , program linear akan memiliki tablo bentuk kanonik

 

dengan kolom ke-5 dan ke-6 menandakan variabel sederhana   dan  . Solusi feasibel sederhana yang berkorespodensi dengan tablo ini adalah

 

Selanjutnya, kolom ke-2, ke-3, dan ke-4 dapat digunakan sebagai kolom pivot. Untuk contoh ini akan dipilih kolom ke-4. Nilai dari  untuk baris ke-2 dan baris ke-3 secara berurutan adalah 10/1 = 10 dand 15/3 = 5. Karena minimum dari kedua nilai ini adalah 5, baris ke-3 dipilih sebagai baris pivot. Setelah menerapkan operasi pivot pada tablo, akan dihasilkan tablo

 

Sekarang kolom ke-4 dan ke-5 merepresentasikan variabel sederhana   dan  . Solusi feasibel sederhana dari tablo tersebut adalah 

Tidak ada entri positif di baris fungsi objektif, sehingga operasi pivot tidak dapat dilakukan. Lebih lanjut, fungsi objektif yang berkorespondensi dengan tablo,

 

sudah optimal, dengan nilai minimum dari   adalah −20 (hasil subtitusi  ).

Membentuk tablo awalan

sunting

Secara umum program linear tidak tersaji dalam bentuk kanonik, sehingga tablo bentuk kanonik yang ekuivalen perlu disusun terlebih dahulu sebelum algoritma simpleks dapat berjalan. Hal ini dapat dilakukan dengan memperkenalkan variabel-variabel buatan (artificial). Kolom-kolom dari matriks identitas ditambahkan sebagai vektor kolom dari variabel-variabel ini. Jika nilai   suatu kendala bernilai negatif, persamaan perlu dikali dengan -1 sebelum menambahkan kolom matriks identitas. Hal ini tidak akan mengubah himpunan solusi feasibel maupun solusi optimal, dan memastikan bahwa variabel-variabel lempai (slack) pada awalnya akan membentuk solusi feasibel. Walau tablo yang dibuat akan berbentuk kanonik, tablo ini tidak sama dengan masalah yang sebenarnya dikerjakan. Untuk itu sebuah fungsi objektif baru dibentuk, yang nilainya sama dengan jumlah semua variabel buatan, dan algoritma simpleks diterapkan untuk mencari minimum dari fungsi objektif ini. Program linear yang dimodifikasi ini disebut dengan masalah Tahap I.[23]

Algoritma simpleks yang diterapkan pada masalah Tahap I pasti berakhir dengan sebuah nilai minimum dari fungsi objektif baru. Hal ini dikarenakan fungsi objektif tersebut adalah jumlah dari variabel-variabel bernilai nonnegatif, yang nilainya terbatas dari bawah oleh 0. Jika minimum fungsi ini adalah 0, maka variabel-variabel buatan dapat dieliminasi dari tablo yang dihasilkan, hal ini akan membentuk tablo kanonik yang ekuivalen dengan masalah yang sebenarnya. Algoritma simpleks selanjutnya dapat diterapkan untuk mencari solusi; langkah ini disebut Tahap II. Namun jika minimum dari fungsi objektif baru bernilai positif, maka tidak ada solusi feasibel (dengan semua variabel buatan bernilai nol) untuk masalah Tahap I. Hal ini mengimplikasikan masalah yang sebenarnya memiliki daerah feasibel yang kosong, sehingga masalah tersebut tidak memiliki solusi.[13][14][24]

Contoh

sunting

Diberikan sebuah program linear:

Minimumkan  

Dengan kendala: 

Hal ini dapat direpresentasikan dengan sebuah tablo (belum berbentuk kanonik):

 

Bentuk dua variabel buatan baru   dan  , dan fungsi objektif baru  . Hal ini akan membentuk tablo baru Persamaan-persamaan yang mendefinisikan masalah yang sebenarnya tetap dipertahankan untuk Tahap II. Dari konstruksinya,   dan   adalah variabel sederhana karena mereka adalah bagian dari matriks identitas. Namun, fungsi objektif   saat ini mengasumsikan   dan   keduanya bernilai 0. Untuk mengoreksi nilai dari fungsi objektif, dengan   dan  , Baris ketiga dan keempat pada tablo ditambahkan ke baris pertama, menghasilkan tablo

 

Pilih kolom ke-5 sebagai kolom pivot; sehingga baris pivot yang dipilih haruslah baris ke-4. Tablo baru yang terbentuk adalah 

Lalu pilih kolom-3 sebagai kolom pivot; hal ini mengharuskan baris ke-3 sebagai baris pivot. Langkah ini akan menghasilkan 

Nilai fungsi objektif saat ini bernilai 0 (sudah minimum), dan variabel-variabel buatan dapat dihilangkan agar menghasilkan tablo kanonik yang ekuivalen dengan masalah yang sebenarnya. Tablo tersebut adalah: 

Dalam contoh masalah ini, untungnya, tablo sudah optimal dari nilai minimum dari fungsi objektif (yang sebenarnya) adalah −130/7.

Referensi

sunting
  1. ^ Murty, Katta G. Linear programming. John Wiley & Sons Inc.1, 2000. Diarsipkan dari versi asli tanggal 2019-02-14. 
  2. ^ (Murty 1983, Comment 2.2)
  3. ^ (Murty 1983, Note 3.9)
  4. ^ Stone, Richard E.; Tovey, Craig A. (1991). "The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review. 33 (2): 220–237. doi:10.1137/1033049. JSTOR 2031142. MR 1124362. 
  5. ^ Stone, Richard E.; Tovey, Craig A. (1991). "Erratum: The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review. 33 (3): 461. doi:10.1137/1033100. JSTOR 2031443. MR 1124362. 
  6. ^ Strang, Gilbert (1 June 1987). "Karmarkar's algorithm and its place in applied mathematics". The Mathematical Intelligencer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185. 
  7. ^ Dantzig, George B. (April 1982). "Reminiscences about the origins of linear programming". Operations Research Letters. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8. Diarsipkan dari versi asli (PDF) tanggal May 20, 2015. 
  8. ^ Albers and Reid (1986). "An Interview with George B. Dantzig: The Father of Linear Programming". College Mathematics Journal. 17 (4): 292–314. doi:10.1080/07468342.1986.11972971. Diarsipkan dari versi asli tanggal 2023-03-06. 
  9. ^ Dantzig, George (May 1987). "Origins of the simplex method" (PDF). Dalam Nash, Stephen G. A History of Scientific Computing. Association for Computing Machinery. hlm. 141–151. doi:10.1145/87252.88081. ISBN 978-0-201-50814-7. Diarsipkan dari versi asli (PDF) tanggal May 29, 2015. 
  10. ^ (Murty 1983, Theorem 3.3)
  11. ^ (Murty 1983, hlm. 143, Section 3.13)
  12. ^ a b (Murty 1983, hlm. 137, Section 3.8)
  13. ^ a b c Dantzig, George Bernard; Thapa, Mukund N. (2003). Linear programming. 2: Theory and extensions. New York Heidelberg: Springer. ISBN 978-0-387-98613-5. 
  14. ^ a b c d D. Nering, Evar; W. Tucker, Albert (1993). Linear Programs and Related Problems. Academic Press. 
  15. ^ Vanderbei, Robert J. (2008). Linear programming: foundations and extensions. International series in operations research & management science (edisi ke-3. ed). New York, NY: Springer. ISBN 978-0-387-74387-5. Diarsipkan dari versi asli tanggal 2006-06-13. 
  16. ^ (Murty 1983, Section 2.2)
  17. ^ (Murty 1983, hlm. 173)
  18. ^ (Murty 1983, section 2.3.2)
  19. ^ (Murty 1983, section 3.12)
  20. ^ a b (Murty 1983, hlm. 66)
  21. ^ Harris, Paula MJ. "Pivot selection methods of the Devex LP code." Mathematical programming 5.1 (1973): 1–28
  22. ^ (Murty 1983, hlm. 67)
  23. ^ (Murty 1983, hlm. 60)
  24. ^ Padberg, M. (1999). Linear Optimization and Extensions (edisi ke-2). Springer-Verlag.