Memahami Algoritma Simpleks: Optimasi Linear yang Revolusioner

Dalam dunia pengambilan keputusan modern, menghadapi kompleksitas dan mencari solusi terbaik dari berbagai pilihan adalah tantangan yang konstan. Baik dalam bisnis, rekayasa, ekonomi, maupun ilmu pengetahuan, kita sering dihadapkan pada situasi di mana sumber daya terbatas harus dialokasikan secara optimal untuk mencapai tujuan tertentu, entah itu memaksimalkan keuntungan atau meminimalkan biaya. Inilah inti dari apa yang kita kenal sebagai optimasi linear, sebuah cabang penting dari riset operasi dan matematika terapan yang menyediakan kerangka kerja sistematis untuk memecahkan masalah semacam ini.

Di jantung optimasi linear terletak sebuah alat yang tak ternilai: Algoritma Simpleks. Dikembangkan oleh George Dantzig pada tahun 1947, algoritma ini bukan hanya sebuah metode matematis; ia adalah sebuah revolusi. Sebelum Simpleks, masalah optimasi linear yang melibatkan banyak variabel dan batasan seringkali tidak dapat dipecahkan secara praktis. Namun, dengan pengenalannya, para manajer, insinyur, dan ilmuwan kini memiliki cara yang efisien dan sistematis untuk menemukan solusi optimal, bahkan untuk masalah yang sangat besar dan rumit.

Algoritma Simpleks bekerja dengan bergerak secara iteratif dari satu solusi "sudut" yang layak ke solusi "sudut" yang lebih baik, hingga tidak ada lagi perbaikan yang mungkin dilakukan. Ini adalah pendekatan yang elegan yang memanfaatkan geometri dasar dari masalah optimasi linear, yaitu fakta bahwa solusi optimal selalu terletak pada salah satu titik sudut dari daerah fisibel (daerah yang memenuhi semua batasan). Artikel ini akan membawa Anda dalam perjalanan mendalam untuk memahami Algoritma Simpleks, mulai dari konsep dasarnya, langkah-langkah implementasinya, berbagai kasus khusus, hingga aplikasi praktisnya yang luas. Mari kita selami lebih dalam dunia optimasi linear dan algoritma yang menjadi tulang punggungnya.

1. Dasar-dasar Optimasi Linear

Sebelum kita menyelami Algoritma Simpleks, penting untuk memahami fondasi tempat ia berdiri: optimasi linear. Optimasi linear adalah teknik matematika untuk mengalokasikan sumber daya terbatas di antara berbagai kegiatan yang bersaing dengan cara terbaik yang mungkin untuk mencapai tujuan yang ditetapkan, seperti memaksimalkan keuntungan atau meminimalkan biaya. Ini adalah salah satu model optimasi yang paling banyak digunakan di dunia nyata karena kemampuannya untuk memodelkan berbagai masalah kompleks secara efektif.

1.1. Komponen Utama Model Optimasi Linear

Setiap masalah optimasi linear terdiri dari tiga komponen utama:

1.1.1. Fungsi Tujuan (Objective Function)

Fungsi tujuan adalah ekspresi matematika yang kita ingin maksimalkan atau minimalkan. Ini adalah kuantitas yang kita ingin optimalkan. Fungsi ini selalu berbentuk linear, yang berarti variabel-variabelnya tidak dipangkatkan (misalnya, tidak ada x²) dan tidak dikalikan satu sama lain (misalnya, tidak ada x₁x₂). Contoh:

• Maksimalkan Keuntungan: Z = 3x₁ + 5x₂
• Minimalkan Biaya: Z = 10x₁ + 8x₂ + 12x₃

Di sini, x₁, x₂, x₃ adalah variabel keputusan, dan koefisien (misalnya, 3, 5, 10, 8, 12) adalah konstanta yang menunjukkan kontribusi setiap variabel terhadap fungsi tujuan.

1.1.2. Variabel Keputusan (Decision Variables)

Variabel keputusan adalah kuantitas yang dapat kita kendalikan atau putuskan. Ini adalah nilai-nilai yang akan dicari oleh algoritma optimasi. Dalam konteks masalah produksi, variabel keputusan mungkin mewakili jumlah unit dari setiap jenis produk yang akan diproduksi. Dalam masalah alokasi, mereka mungkin mewakili jumlah sumber daya yang dialokasikan untuk setiap tugas.

Misalnya, jika sebuah perusahaan memproduksi dua jenis produk, A dan B, maka x₁ mungkin adalah jumlah produk A yang akan diproduksi, dan x₂ adalah jumlah produk B yang akan diproduksi.

1.1.3. Batasan (Constraints)

Batasan adalah pembatasan pada variabel keputusan, yang timbul dari keterbatasan sumber daya atau persyaratan lain dalam sistem. Batasan ini juga harus berbentuk linear (ketidaksamaan atau kesamaan). Contoh batasan meliputi:

• Keterbatasan bahan baku: 2x₁ + x₂ ≤ 100 (misalnya, membutuhkan 2 unit bahan baku per produk A dan 1 unit per produk B, dengan total 100 unit bahan baku tersedia).
• Keterbatasan waktu kerja: x₁ + 3x₂ ≤ 80
• Kebutuhan minimum: x₁ + x₂ ≥ 20
• Persyaratan spesifik: x₁ = 15

Setiap batasan membatasi nilai-nilai yang mungkin diambil oleh variabel keputusan. Bersama-sama, batasan-batasan ini membentuk sebuah daerah di ruang dimensi tinggi yang disebut daerah fisibel, yaitu himpunan semua solusi yang memenuhi semua batasan.

1.1.4. Kondisi Non-Negativitas

Mayoritas masalah optimasi linear mengharuskan variabel keputusan bernilai non-negatif, yaitu xᵢ ≥ 0 untuk setiap i. Ini masuk akal dalam banyak konteks praktis; Anda tidak bisa memproduksi jumlah negatif dari sebuah produk atau menggunakan jumlah negatif dari sebuah sumber daya. Kondisi ini sangat penting karena membatasi daerah fisibel pada kuadran atau oktan positif dari sistem koordinat.

1.2. Bentuk Standar Model Optimasi Linear

Untuk menerapkan Algoritma Simpleks, masalah optimasi linear harus diubah ke dalam bentuk standar. Bentuk standar memiliki karakteristik berikut:

1. Fungsi tujuan adalah maksimasi. Jika masalah aslinya adalah minimasi, kita dapat mengubahnya menjadi maksimasi dengan mengalikan fungsi tujuan dengan -1 (misalnya, meminimalkan Z sama dengan memaksimalkan -Z).
2. Semua batasan adalah kesamaan. Ini dicapai dengan memperkenalkan variabel slack atau surplus.
3. Semua variabel keputusan adalah non-negatif.

Mari kita lihat bagaimana ketidaksamaan diubah menjadi kesamaan:

• Batasan "kurang dari atau sama dengan" (≤): Untuk mengubah a₁x₁ + a₂x₂ ≤ b menjadi kesamaan, kita menambahkan variabel slack (s₁) yang non-negatif. Variabel slack mewakili "sisa" atau jumlah sumber daya yang tidak terpakai.

  a₁x₁ + a₂x₂ + s₁ = b
  s₁ ≥ 0

• Batasan "lebih dari atau sama dengan" (≥): Untuk mengubah a₁x₁ + a₂x₂ ≥ b menjadi kesamaan, kita mengurangi variabel surplus (s₂) yang non-negatif. Variabel surplus mewakili jumlah di atas persyaratan minimum.

  a₁x₁ + a₂x₂ - s₂ = b
  s₂ ≥ 0

Jika ada variabel yang tidak terbatas dalam tanda (dapat positif, negatif, atau nol), variabel tersebut dapat diganti dengan selisih dua variabel non-negatif: x_i = x_i' - x_i'', di mana x_i', x_i'' ≥ 0.

2. Representasi Geometris dan Intuisi Algoritma Simpleks

Memahami Algoritma Simpleks secara intuitif dapat sangat terbantu dengan visualisasi geometris, terutama untuk masalah dengan dua variabel keputusan. Meskipun masalah nyata memiliki banyak dimensi, prinsip dasarnya tetap sama.

2.1. Daerah Fisibel (Feasible Region)

Ketika kita memplot semua batasan pada sistem koordinat (untuk 2 variabel, ini adalah bidang 2D), setiap batasan membentuk sebuah garis atau bidang yang membatasi ruang. Daerah yang memenuhi *semua* batasan secara bersamaan (termasuk non-negativitas) disebut daerah fisibel. Untuk masalah optimasi linear, daerah fisibel selalu merupakan polihedron cembung (convex polyhedron).

Daerah cembung berarti bahwa jika Anda mengambil dua titik mana pun di dalam daerah tersebut dan menggambar garis lurus di antara keduanya, seluruh garis tersebut juga akan berada di dalam daerah tersebut. Ini adalah properti yang sangat penting dalam optimasi linear.

2.2. Titik Sudut (Corner Points / Extreme Points)

Titik-titik di mana garis-garis batasan saling berpotongan (dan berada dalam daerah fisibel) disebut titik sudut atau titik ekstrem. Properti fundamental dari optimasi linear adalah bahwa jika ada solusi optimal, solusi tersebut selalu terletak pada salah satu titik sudut dari daerah fisibel.

Mengapa demikian? Bayangkan garis fungsi tujuan (misalnya, Z = c₁x₁ + c₂x₂). Untuk berbagai nilai Z, garis ini akan bergeser secara paralel. Jika kita ingin memaksimalkan Z, kita akan menggeser garis ini sejauh mungkin ke arah yang meningkatkan Z, tanpa meninggalkan daerah fisibel. Titik terakhir di daerah fisibel yang disentuh oleh garis fungsi tujuan saat bergerak keluar akan selalu merupakan salah satu titik sudut.

2.3. Intuisi Algoritma Simpleks

Dengan pemahaman bahwa solusi optimal ada di titik sudut, Algoritma Simpleks bekerja berdasarkan ide sederhana namun brilian: ia tidak perlu memeriksa setiap titik di daerah fisibel (yang jumlahnya tak terbatas) atau bahkan setiap titik sudut (yang bisa sangat banyak). Sebaliknya, ia memulai di salah satu titik sudut (biasanya titik asal (0,0) jika fisibel) dan kemudian secara sistematis bergerak ke titik sudut yang berdekatan yang menghasilkan nilai fungsi tujuan yang lebih baik. Proses ini diulang sampai tidak ada lagi titik sudut berdekatan yang dapat memberikan perbaikan.

Ini seperti mendaki gunung: Anda memulai di sebuah titik di kaki gunung, melihat ke segala arah untuk menemukan jalur menanjak, dan kemudian mengambil jalur yang paling curam. Anda terus melakukan ini sampai Anda mencapai puncak, di mana tidak ada lagi jalur menanjak.

3. Algoritma Simpleks: Langkah demi Langkah

Algoritma Simpleks adalah metode iteratif yang secara sistematis menjelajahi titik-titik sudut dari daerah fisibel untuk menemukan solusi optimal. Prosesnya melibatkan serangkaian "pivot" atau transformasi tabel yang setara dengan berpindah dari satu titik sudut ke titik sudut lainnya.

3.1. Persiapan: Mengubah ke Bentuk Standar

Seperti yang telah dibahas sebelumnya, langkah pertama adalah mengubah semua batasan ke bentuk kesamaan dengan memperkenalkan variabel slack atau surplus. Jika ada masalah minimasi, ubah menjadi maksimasi. Ini akan menghasilkan sistem persamaan linear yang siap untuk disajikan dalam tabel simpleks awal.

Contoh: Maksimalkan Z = 3x₁ + 2x₂ Batasan: x₁ + x₂ ≤ 4 2x₁ + x₂ ≤ 6 x₁, x₂ ≥ 0

Bentuk Standar: Maksimalkan Z = 3x₁ + 2x₂ + 0s₁ + 0s₂ Batasan: x₁ + x₂ + s₁ = 4 2x₁ + x₂ + s₂ = 6 x₁, x₂, s₁, s₂ ≥ 0

Di sini, s₁ dan s₂ adalah variabel slack.

3.2. Membuat Tabel Simpleks Awal

Setelah masalah dalam bentuk standar, kita dapat menyusun tabel simpleks awal. Tabel ini mengatur semua koefisien fungsi tujuan dan batasan dalam format matriks yang rapi.

Penjelasan kolom:

• Basis: Variabel-variabel yang saat ini ada dalam basis solusi (variabel yang bernilai positif). Pada iterasi awal, ini biasanya adalah variabel slack/surplus.
• Cj (Baris atas): Koefisien fungsi tujuan dari setiap variabel.
• Kolom Variabel (x₁, x₂, s₁, s₂, dll.): Koefisien dari variabel-variabel ini di setiap batasan.
• RHS (Right-Hand Side): Nilai konstan di sisi kanan setiap batasan.
• Zj (Baris): Nilai fungsi tujuan yang dihasilkan jika variabel yang bersangkutan masuk ke dalam basis. Dihitung sebagai Σ (Cj_basis * koefisien_kolom_variabel).
• Cj-Zj (Baris): Indikator net present value atau potensi peningkatan Z per unit variabel. Ini adalah kriteria optimalitas. Untuk maksimasi, kita mencari nilai positif terbesar. Untuk minimasi, kita mencari nilai negatif terbesar.
• Rasio: Digunakan untuk menentukan variabel keluar.

3.3. Iterasi Algoritma Simpleks

Setiap iterasi melibatkan tiga langkah utama:

3.3.1. Menentukan Variabel Masuk (Entering Variable)

Ini adalah variabel non-basis yang akan masuk ke dalam basis untuk meningkatkan nilai fungsi tujuan (Z). Untuk masalah maksimasi, pilih kolom variabel dengan nilai Cj-Zj positif terbesar. Jika semua Cj-Zj ≤ 0, solusi optimal telah tercapai. Untuk masalah minimasi (setelah dikonversi menjadi maksimasi -Z), kita akan mencari Cj-Zj positif terbesar. Jika masalah minimasi langsung (tidak dikonversi), kita mencari Cj-Zj negatif terbesar. Kolom yang dipilih ini disebut kolom pivot.

3.3.2. Menentukan Variabel Keluar (Leaving Variable)

Ini adalah variabel basis yang akan meninggalkan basis untuk memungkinkan variabel masuk. Ini ditentukan dengan menghitung rasio untuk setiap baris batasan. Rasio dihitung sebagai RHS / koefisien_di_kolom_pivot. Pilih baris dengan rasio non-negatif terkecil. Baris yang dipilih ini adalah baris pivot. Variabel basis pada baris ini adalah variabel keluar.

Catatan Penting: Rasio hanya dihitung untuk baris di mana koefisien di kolom pivot positif (>0). Jika semua koefisien di kolom pivot adalah nol atau negatif, maka masalah tersebut memiliki solusi tak terbatas (unbounded solution).

3.3.3. Melakukan Operasi Pivot

Elemen pada persimpangan kolom pivot dan baris pivot disebut elemen pivot. Tujuannya adalah mengubah elemen pivot menjadi 1 dan semua elemen lain di kolom pivot menjadi 0 melalui operasi baris elementer (seperti dalam eliminasi Gauss-Jordan). Ini secara efektif mengubah variabel masuk menjadi variabel basis baru dan mengeluarkan variabel keluar dari basis.

1. Baris Pivot Baru: Bagi seluruh baris pivot dengan elemen pivot.
2. Baris Lainnya: Untuk setiap baris lain (termasuk baris Zj), hitung: Baris Baru = Baris Lama - (Koefisien di Kolom Pivot * Baris Pivot Baru)

Ulangi langkah 3.1 hingga 3.3 sampai kondisi optimalitas terpenuhi (yaitu, semua nilai Cj-Zj ≤ 0 untuk maksimasi).

3.4. Kriteria Optimalitas dan Terminasi

Algoritma Simpleks berhenti ketika semua nilai Cj-Zj pada baris indikator (baris terakhir) adalah kurang dari atau sama dengan nol (≤ 0) untuk masalah maksimasi. Pada titik ini, tabel simpleks menunjukkan solusi optimal.

Nilai optimal fungsi tujuan (Z) ditemukan di sel Zj di bawah kolom RHS. Nilai untuk variabel keputusan yang ada di basis dapat dibaca dari kolom RHS pada baris masing-masing variabel basis. Variabel non-basis memiliki nilai 0.

4. Kasus Khusus dalam Algoritma Simpleks

Meskipun Algoritma Simpleks sangat efektif, ada beberapa kondisi atau kasus khusus yang mungkin muncul selama proses iterasi yang memerlukan perhatian dan interpretasi yang berbeda. Memahami kasus-kasus ini sangat penting untuk penerapan algoritma yang benar dan penarikan kesimpulan yang akurat.

4.1. Solusi Optimal Alternatif (Alternative Optimal Solutions)

Kadang-kadang, sebuah masalah optimasi linear dapat memiliki lebih dari satu solusi optimal, yang semuanya menghasilkan nilai fungsi tujuan yang sama persis. Ini terjadi ketika garis (atau bidang) fungsi tujuan sejajar dengan salah satu batasan yang membentuk batas daerah fisibel yang optimal.

Dalam tabel simpleks, kondisi ini terdeteksi ketika baris Cj-Zj untuk variabel non-basis memiliki nilai nol (0) pada solusi optimal. Artinya, jika variabel non-basis tersebut masuk ke dalam basis, nilai Z tidak akan berubah, tetapi komposisi variabel basis akan berubah, menghasilkan titik sudut optimal yang berbeda.

Ketika ini terjadi, semua solusi yang merupakan kombinasi linear cembung dari titik-titik sudut optimal alternatif juga merupakan solusi optimal. Ini memberikan fleksibilitas kepada pengambil keputusan.

4.2. Solusi Tak Terbatas (Unbounded Solutions)

Masalah optimasi linear dikatakan memiliki solusi tak terbatas jika nilai fungsi tujuan dapat ditingkatkan (untuk maksimasi) atau diturunkan (untuk minimasi) tanpa batas, tanpa melanggar batasan apa pun. Secara geometris, ini berarti daerah fisibel terbuka ke arah yang memungkinkan fungsi tujuan untuk terus meningkat (atau menurun).

Dalam Algoritma Simpleks, kondisi ini terdeteksi ketika, setelah memilih variabel masuk (misalnya, kolom dengan Cj-Zj positif terbesar), semua koefisien di kolom pivot yang sesuai adalah nol atau negatif. Dalam kasus seperti itu, tidak ada variabel keluar yang dapat dipilih karena rasio minimum tidak dapat dihitung (kita tidak bisa membagi dengan nol atau nilai negatif untuk rasio). Ini menandakan bahwa kita bisa terus menambahkan variabel masuk tersebut ke basis tanpa batas, dan nilai Z akan terus meningkat.

Solusi tak terbatas seringkali mengindikasikan bahwa model optimasi awal salah formulasi, mungkin ada batasan penting yang terlewatkan atau salah diidentifikasi.

4.3. Tidak Ada Solusi Fisibel (Infeasible Solutions)

Masalah optimasi linear disebut tidak fisibel jika tidak ada satu pun titik yang memenuhi *semua* batasan secara bersamaan. Secara geometris, ini berarti daerah fisibel adalah himpunan kosong; tidak ada area yang dapat dilalui.

Kondisi ini biasanya terdeteksi saat menggunakan metode Algoritma Simpleks Dua Fase atau Metode Big M (yang akan kita bahas kemudian) untuk menangani batasan ≥ atau = yang memerlukan variabel buatan. Jika pada akhir iterasi Simpleks, salah satu variabel buatan masih tetap berada di basis dengan nilai positif, itu berarti batasan yang terkait tidak dapat dipenuhi, dan masalah tersebut tidak memiliki solusi fisibel.

Situasi tidak fisibel juga menunjukkan adanya kesalahan dalam formulasi masalah, di mana batasan-batasan saling bertentangan satu sama lain.

4.4. Degenerasi (Degeneracy)

Degenerasi terjadi ketika satu atau lebih variabel basis memiliki nilai nol (0). Ini dapat terjadi ketika rasio minimum yang digunakan untuk memilih variabel keluar memiliki lebih dari satu nilai yang sama dan terkecil. Jika ada dua atau lebih baris yang memberikan rasio minimum yang sama, memilih salah satunya untuk menjadi variabel keluar dapat menyebabkan variabel basis lain yang seharusnya tetap di basis, justru menjadi nol pada iterasi berikutnya.

Dampak utama degenerasi adalah potensi untuk cycling (perputaran). Cycling terjadi ketika algoritma berulang kali melewati serangkaian tabel simpleks yang sama tanpa mencapai solusi optimal, karena nilai fungsi tujuan tidak meningkat di setiap iterasi degeneratif. Meskipun jarang terjadi dalam praktiknya, ada aturan tambahan (seperti Aturan Bland) yang dapat digunakan untuk mencegah cycling.

5. Metode Big M dan Dua Fase

Seperti yang telah dibahas, Algoritma Simpleks memerlukan solusi basis fisibel awal untuk memulai. Namun, untuk masalah yang memiliki batasan "lebih dari atau sama dengan" (≥) atau "sama dengan" (=), titik asal (0,0,...,0) seringkali bukan solusi fisibel karena variabel slack yang bernilai nol akan melanggar batasan ini. Untuk mengatasi ini, kita memperkenalkan variabel buatan (artificial variables) dan menggunakan salah satu dari dua metode: Metode Big M atau Metode Dua Fase.

5.1. Variabel Buatan (Artificial Variables)

Variabel buatan adalah variabel non-negatif yang ditambahkan ke batasan ≥ atau = untuk menciptakan solusi basis fisibel awal. Mereka tidak memiliki makna fisik dalam masalah asli dan hanya digunakan sebagai alat bantu untuk memulai proses Simpleks.

• Untuk batasan a₁x₁ + a₂x₂ ≥ b: tambahkan variabel surplus -s₁ dan variabel buatan +A₁. Hasilnya: a₁x₁ + a₂x₂ - s₁ + A₁ = b.
• Untuk batasan a₁x₁ + a₂x₂ = b: tambahkan variabel buatan +A₂. Hasilnya: a₁x₁ + a₂x₂ + A₂ = b.

Tujuan utama dari kedua metode ini adalah memastikan bahwa semua variabel buatan keluar dari basis pada solusi optimal akhir, karena mereka adalah variabel yang "tidak diinginkan" dan harus bernilai nol.

5.2. Metode Big M

Metode Big M mengintegrasikan variabel buatan langsung ke dalam fungsi tujuan. Untuk memastikan variabel buatan keluar dari basis, mereka diberi penalti yang sangat besar dalam fungsi tujuan. Dalam masalah maksimasi, koefisien variabel buatan dalam fungsi tujuan adalah -M (di mana M adalah angka positif yang sangat besar). Dalam masalah minimasi, koefisiennya adalah +M.

Langkah-langkah Metode Big M:

1. Formulasi: Ubah masalah ke bentuk standar. Tambahkan variabel slack, surplus, dan buatan sesuai kebutuhan.
2. Modifikasi Fungsi Tujuan: Tambahkan -M * (jumlah variabel buatan) ke fungsi tujuan jika maksimasi, atau +M * (jumlah variabel buatan) jika minimasi.
3. Tabel Awal: Buat tabel simpleks awal. Pastikan semua variabel buatan menjadi bagian dari solusi basis awal.
4. Iterasi Simpleks: Lanjutkan Algoritma Simpleks seperti biasa. Penalti M yang sangat besar akan memaksa variabel buatan untuk keluar dari basis secepat mungkin.
5. Kriteria Optimalitas:
   • Jika pada solusi optimal, tidak ada variabel buatan di basis, atau jika ada, nilainya nol, maka solusi optimal asli telah ditemukan.
   • Jika pada solusi optimal, ada variabel buatan di basis dengan nilai positif, maka masalah asli tidak memiliki solusi fisibel.

Metode Big M relatif mudah diimplementasikan, tetapi pemilihan nilai M yang "cukup besar" bisa menjadi tantangan dan berpotensi menyebabkan masalah presisi numerik dalam komputasi.

5.3. Metode Dua Fase (Two-Phase Method)

Metode Dua Fase mengatasi potensi masalah numerik dari Big M dengan memisahkan proses optimasi menjadi dua fase yang berbeda.

Fase 1: Mencari Solusi Fisibel Awal

1. Formulasi: Ubah masalah ke bentuk standar. Tambahkan variabel slack, surplus, dan buatan.
2. Fungsi Tujuan Baru: Buat fungsi tujuan baru yang hanya bertujuan untuk meminimalkan jumlah semua variabel buatan.

   Minimalkan W = A₁ + A₂ + ... + A_k

   Ini setara dengan memaksimalkan W' = -A₁ - A₂ - ... - A_k.
3. Iterasi Simpleks: Terapkan Algoritma Simpleks untuk fungsi tujuan W.
4. Kriteria Fase 1:
   • Jika nilai optimal W = 0 dan semua variabel buatan telah keluar dari basis (atau nilai mereka nol), maka solusi basis fisibel telah ditemukan. Lanjutkan ke Fase 2.
   • Jika nilai optimal W > 0, maka masalah asli tidak memiliki solusi fisibel. Berhenti.

Fase 2: Optimasi Fungsi Tujuan Asli

1. Tabel Awal Fase 2: Gunakan tabel simpleks akhir dari Fase 1 (setelah menghapus kolom variabel buatan) sebagai tabel awal untuk Fase 2.
2. Fungsi Tujuan Asli: Ganti baris Cj-Zj dengan koefisien dari fungsi tujuan asli. Hitung ulang baris Zj dan Cj-Zj untuk variabel basis saat ini.
3. Iterasi Simpleks: Lanjutkan Algoritma Simpleks seperti biasa dengan fungsi tujuan asli hingga solusi optimal ditemukan.

Metode Dua Fase lebih kuat secara numerik karena tidak memerlukan nilai M yang sangat besar, sehingga mengurangi potensi kesalahan pembulatan.

6. Dualitas (Duality) dalam Optimasi Linear

Setiap masalah optimasi linear, yang disebut masalah primal, memiliki masalah pasangannya yang terkait erat, yang disebut masalah dual. Konsep dualitas adalah salah satu konsep paling mendalam dan berguna dalam optimasi linear, memberikan wawasan baru tentang struktur masalah dan interpretasi ekonomi dari solusi.

6.1. Masalah Primal dan Dual

Misalkan kita memiliki masalah primal dalam bentuk maksimasi:

Maksimalkan Z = c₁x₁ + c₂x₂ + ... + c_nx_n
Batasan:
a₁₁x₁ + a₁₂x₂ + ... + a₁nx_n ≤ b₁
a₂₁x₁ + a₂₂x₂ + ... + a₂nx_n ≤ b₂
...
a_m₁x₁ + a_m₂x₂ + ... + a_mnx_n ≤ b_m
x_j ≥ 0 untuk j=1,...,n

Masalah dualnya akan berbentuk minimasi:

Minimalkan W = b₁y₁ + b₂y₂ + ... + b_my_m
Batasan:
a₁₁y₁ + a₂₁y₂ + ... + a_m₁y_m ≥ c₁
a₁₂y₁ + a₂₂y₂ + ... + a_m₂y_m ≥ c₂
...
a₁ny₁ + a₂ny₂ + ... + a_mny_m ≥ c_n
y_i ≥ 0 untuk i=1,...,m

Ada hubungan sistematis antara primal dan dual:

• Jumlah variabel dual sama dengan jumlah batasan primal.
• Jumlah batasan dual sama dengan jumlah variabel primal.
• Koefisien fungsi tujuan primal menjadi nilai sisi kanan batasan dual.
• Nilai sisi kanan batasan primal menjadi koefisien fungsi tujuan dual.
• Matriks koefisien batasan dual adalah transpos dari matriks koefisien batasan primal.
• Batasan ≤ dalam primal maksimasi menjadi batasan ≥ dalam dual minimasi.
• Variabel non-negatif dalam primal tetap non-negatif dalam dual.

6.2. Teorema Dualitas Kuat (Strong Duality Theorem)

Salah satu hasil terpenting dalam dualitas adalah Teorema Dualitas Kuat, yang menyatakan bahwa jika masalah primal memiliki solusi optimal, maka masalah dualnya juga memiliki solusi optimal, dan nilai fungsi tujuan optimal keduanya sama: Z_optimal = W_optimal.

Selain itu, Teorema Dualitas Lemah menyatakan bahwa nilai fungsi tujuan dari setiap solusi fisibel primal selalu kurang dari atau sama dengan nilai fungsi tujuan dari setiap solusi fisibel dual (untuk masalah maksimasi-minimasi).

6.3. Interpretasi Ekonomi (Harga Bayangan / Shadow Prices)

Variabel dual (yᵢ) memiliki interpretasi ekonomi yang sangat kuat, sering disebut harga bayangan (shadow prices) atau nilai marjinal (marginal values). Sebuah harga bayangan untuk batasan tertentu menunjukkan seberapa banyak nilai fungsi tujuan optimal akan berubah jika sisi kanan batasan tersebut (misalnya, jumlah sumber daya yang tersedia) ditingkatkan sebesar satu unit, dengan asumsi semua faktor lain tetap konstan.

Misalnya, jika harga bayangan untuk batasan bahan baku adalah $2, ini berarti jika kita mendapatkan tambahan satu unit bahan baku, keuntungan total kita akan meningkat sebesar $2. Informasi ini sangat berharga untuk pengambilan keputusan manajemen, seperti memutuskan apakah akan berinvestasi pada sumber daya tambahan atau tidak.

6.4. Keuntungan Menggunakan Dualitas

• Efisiensi Komputasi: Terkadang, masalah dual lebih mudah atau lebih cepat dipecahkan daripada masalah primal, terutama jika masalah dual memiliki lebih sedikit batasan.
• Analisis Sensitivitas: Solusi dual secara langsung memberikan informasi penting untuk analisis sensitivitas (bagaimana perubahan dalam parameter input mempengaruhi solusi optimal).
• Interpretasi Ekonomi: Seperti yang disebutkan, harga bayangan memberikan wawasan berharga tentang nilai marginal sumber daya.
• Konfirmasi Optimalitas: Memecahkan kedua masalah (primal dan dual) dan mendapatkan nilai fungsi tujuan yang sama merupakan konfirmasi bahwa solusi optimal telah ditemukan.

7. Analisis Sensitivitas

Dalam dunia nyata, parameter model optimasi linear (seperti koefisien fungsi tujuan, koefisien batasan, dan nilai sisi kanan batasan) jarang sekali tetap konstan. Harga bahan baku bisa naik, ketersediaan tenaga kerja bisa berubah, atau permintaan pasar berfluktuasi. Oleh karena itu, penting untuk memahami bagaimana perubahan pada parameter ini dapat mempengaruhi solusi optimal. Inilah tujuan dari analisis sensitivitas (sensitivity analysis) atau analisis pasca-optimalitas.

Analisis sensitivitas menjawab pertanyaan "bagaimana jika?" tanpa harus memecahkan kembali seluruh masalah optimasi dari awal setiap kali ada sedikit perubahan parameter.

7.1. Perubahan Koefisien Fungsi Tujuan (Cj)

Bagaimana jika keuntungan per unit produk (koefisien c_j) berubah? Analisis sensitivitas dapat menentukan rentang nilai di mana koefisien ini dapat berubah tanpa mengubah komposisi variabel basis optimal. Selama koefisien tetap dalam rentang ini, titik sudut optimal yang sama akan tetap optimal, meskipun nilai Z optimal akan berubah.

Dalam tabel simpleks akhir, ini terkait dengan baris Cj-Zj. Jika perubahan c_j menyebabkan salah satu Cj-Zj yang sebelumnya negatif atau nol menjadi positif (untuk maksimasi), maka solusi basis optimal mungkin perlu dihitung ulang.

7.2. Perubahan Nilai Sisi Kanan Batasan (bi)

Bagaimana jika ketersediaan sumber daya (nilai b_i) berubah? Analisis ini menentukan rentang nilai sisi kanan batasan di mana solusi basis yang sama tetap fisibel, meskipun nilai variabel basis dan Z optimal akan berubah. Informasi ini sangat berguna untuk perencanaan kapasitas dan negosiasi sumber daya.

Perubahan pada b_i secara langsung memengaruhi kelayakan solusi. Jika b_i berubah sedemikian rupa sehingga batasan melintasi titik sudut optimal, maka komposisi basis optimal akan berubah.

Ini secara langsung berkaitan dengan harga bayangan. Harga bayangan memberi tahu kita persis berapa banyak Z optimal akan berubah per unit perubahan b_i, selama perubahan tersebut berada dalam rentang tertentu.

7.3. Penambahan Variabel Baru

Bagaimana jika ada produk baru yang ingin kita pertimbangkan untuk diproduksi? Kita dapat mengevaluasi apakah produk baru ini menguntungkan tanpa harus memecahkan ulang masalah. Caranya adalah dengan menghitung nilai Cj-Zj (kontribusi bersih) untuk variabel baru tersebut menggunakan koefisien batasan yang ada. Jika Cj-Zj positif (untuk maksimasi), maka memasukkan variabel baru akan meningkatkan Z, dan masalah perlu dipecahkan ulang.

7.4. Penambahan Batasan Baru

Bagaimana jika ada peraturan pemerintah baru atau kapasitas produksi tambahan yang harus dipenuhi? Batasan baru ini dapat ditambahkan ke solusi optimal yang sudah ada dan diperiksa apakah solusi tersebut masih fisibel. Jika solusi optimal yang lama melanggar batasan baru, maka masalah perlu dipecahkan ulang dengan menambahkan batasan tersebut.

Analisis sensitivitas adalah alat penting bagi para pengambil keputusan karena ia memberikan pemahaman yang lebih dalam tentang ketahanan solusi optimal terhadap ketidakpastian dalam parameter masalah. Ini memungkinkan mereka untuk membuat keputusan yang lebih informasi dan fleksibel di lingkungan yang dinamis.

8. Keterbatasan dan Alternatif Algoritma Simpleks

Meskipun Algoritma Simpleks adalah alat yang sangat kuat dan serbaguna, penting untuk menyadari keterbatasannya dan memahami mengapa metode alternatif kadang-kadang lebih disukai atau diperlukan.

8.1. Kompleksitas Komputasi

Secara teori, Algoritma Simpleks memiliki kompleksitas waktu kasus terburuk yang eksponensial. Ini berarti, dalam beberapa kasus yang dibuat khusus, waktu yang dibutuhkan untuk menemukan solusi bisa meningkat secara eksponensial dengan ukuran masalah (jumlah variabel dan batasan). Meskipun dalam praktiknya, Simpleks biasanya bekerja dengan sangat efisien untuk sebagian besar masalah dunia nyata (dengan kompleksitas waktu rata-rata yang lebih dekat ke polinomial), adanya kasus terburuk ini tetap menjadi pertimbangan.

Untuk masalah optimasi linear yang sangat besar, terutama yang melibatkan ribuan atau jutaan variabel dan batasan, bahkan kinerja rata-rata Simpleks kadang-kadang tidak cukup cepat.

8.2. Isu Numerik

Algoritma Simpleks melibatkan banyak operasi aritmetika floating-point. Untuk masalah dengan koefisien yang sangat besar atau sangat kecil, atau ketika masalah degeneratif terjadi, dapat muncul masalah presisi numerik dan pembulatan. Hal ini dapat menyebabkan ketidakstabilan, hasil yang tidak akurat, atau bahkan kegagalan algoritma untuk menemukan solusi.

Metode seperti Metode Big M, yang menggunakan angka "sangat besar" (M), secara inheren rentan terhadap masalah presisi numerik jika M tidak dipilih dengan hati-hati atau jika komputasi tidak dilakukan dengan aritmetika presisi tinggi.

8.3. Asumsi Linearitas

Keterbatasan paling mendasar dari optimasi linear (dan karenanya Algoritma Simpleks) adalah asumsi linearitas. Ini mengasumsikan bahwa semua hubungan dalam model—baik fungsi tujuan maupun batasan—adalah linear. Artinya, setiap peningkatan satu unit dalam sebuah variabel menghasilkan perubahan proporsional yang konstan pada fungsi tujuan atau batasan. Dalam banyak situasi dunia nyata, hubungan ini bisa jadi non-linear (misalnya, adanya skala ekonomi, biaya tetap, atau efek interaksi).

Ketika asumsi linearitas tidak terpenuhi, model optimasi linear mungkin tidak akurat merepresentasikan masalah, dan solusi yang dihasilkan oleh Simpleks mungkin tidak optimal dalam konteks dunia nyata.

8.4. Alternatif: Metode Interior-Point

Sebagai respons terhadap keterbatasan Simpleks, terutama kompleksitas kasus terburuknya dan kebutuhan untuk memecahkan masalah berskala sangat besar, metode alternatif telah dikembangkan. Yang paling menonjol adalah metode interior-point (interior-point methods).

Berbeda dengan Simpleks yang bergerak di sepanjang tepi daerah fisibel dari satu titik sudut ke titik sudut lainnya, metode interior-point bergerak melalui *interior* daerah fisibel. Mereka mendekati solusi optimal secara bertahap, seringkali mengikuti "jalur pusat" melalui interior. Metode ini memiliki kompleksitas waktu polinomial kasus terburuk yang terbukti, yang berarti waktu komputasi mereka meningkat secara lebih dapat diprediksi dengan ukuran masalah.

Algoritma interior-point modern (seperti algoritma Karush-Kuhn-Tucker) telah terbukti sangat efektif untuk masalah optimasi linear berskala besar, seringkali mengungguli Simpleks dalam hal waktu komputasi untuk masalah yang sangat besar. Namun, mereka cenderung lebih kompleks untuk diimplementasikan dan mungkin tidak seefisien Simpleks untuk masalah berukuran kecil hingga menengah.

Meskipun demikian, Algoritma Simpleks tetap menjadi metode yang sangat relevan dan sering digunakan karena kemudahan konsepnya, interpretasi ekonomi yang jelas dari harga bayangan, dan kinerja praktisnya yang sangat baik untuk sebagian besar masalah.

9. Aplikasi Algoritma Simpleks

Algoritma Simpleks adalah tulang punggung dari banyak keputusan operasional dan strategis di berbagai industri. Kemampuannya untuk mengoptimalkan alokasi sumber daya menjadikannya alat yang tak ternilai dalam menghadapi kompleksitas dunia modern. Berikut adalah beberapa bidang aplikasi utamanya:

9.1. Manajemen Produksi dan Operasi

• Perencanaan Produksi: Menentukan jumlah optimal dari berbagai produk yang akan diproduksi untuk memaksimalkan keuntungan, dengan mempertimbangkan keterbatasan bahan baku, kapasitas mesin, dan tenaga kerja.
• Penjadwalan: Mengoptimalkan jadwal produksi, shift kerja, atau pemeliharaan untuk meminimalkan waktu henti atau biaya.
• Campuran Produk Optimal: Menemukan rasio campuran bahan baku terbaik untuk menghasilkan produk tertentu (misalnya, makanan ternak, bensin) yang memenuhi spesifikasi dengan biaya terendah.
• Alokasi Sumber Daya: Mengalokasikan mesin, pekerja, atau bahan baku yang terbatas ke berbagai tugas atau lini produksi.

9.2. Logistik dan Manajemen Rantai Pasokan

• Optimalisasi Rute: Menentukan rute pengiriman yang paling efisien untuk meminimalkan jarak atau waktu tempuh, seringkali dikenal sebagai masalah Vehicle Routing Problem (VRP) atau Traveling Salesman Problem (TSP) yang, meskipun non-linear secara murni, sering didekati atau menjadi sub-masalah dari model linear.
• Perencanaan Distribusi: Mengoptimalkan lokasi gudang dan pusat distribusi serta alur barang untuk meminimalkan biaya transportasi dan inventaris.
• Manajemen Inventaris: Menentukan tingkat persediaan optimal untuk berbagai produk untuk memenuhi permintaan sambil meminimalkan biaya penyimpanan dan risiko kehabisan stok.

9.3. Keuangan dan Investasi

• Manajemen Portofolio: Membangun portofolio investasi yang memaksimalkan keuntungan yang diharapkan sambil membatasi risiko, atau meminimalkan risiko untuk tingkat keuntungan tertentu, dengan alokasi ke berbagai aset.
• Perencanaan Anggaran Modal: Memilih proyek investasi terbaik dari serangkaian pilihan dengan keterbatasan anggaran.
• Penentuan Harga Obligasi: Meskipun lebih kompleks, beberapa model penetapan harga obligasi atau instrumen keuangan dapat menggunakan optimasi linear sebagai bagian dari prosesnya.

9.4. Sumber Daya Manusia

• Penjadwalan Karyawan: Mengoptimalkan jadwal kerja untuk staf di rumah sakit, call center, atau fasilitas produksi untuk memenuhi kebutuhan staf pada waktu tertentu sambil meminimalkan biaya lembur.
• Alokasi Tugas: Menugaskan karyawan dengan keterampilan tertentu ke proyek yang berbeda untuk memaksimalkan produktivitas atau meminimalkan biaya.

9.5. Ilmu Pengetahuan dan Rekayasa

• Desain Eksperimen: Mengoptimalkan parameter dalam eksperimen untuk mencapai hasil yang diinginkan.
• Desain Sistem: Mengoptimalkan desain komponen atau sistem rekayasa untuk memenuhi spesifikasi kinerja dengan biaya minimum atau efisiensi maksimum.
• Lingkungan: Mengelola limbah, alokasi air, atau emisi polutan untuk meminimalkan dampak lingkungan atau biaya kepatuhan.

Daftar ini hanyalah sebagian kecil dari banyaknya aplikasi Algoritma Simpleks. Intinya, di mana pun ada kebutuhan untuk membuat keputusan terbaik dalam menghadapi sumber daya yang terbatas dan tujuan yang jelas, optimasi linear dengan Algoritma Simpleks seringkali menjadi solusi yang sangat relevan dan efektif.

10. Kesimpulan

Dari pembahasan yang mendalam ini, jelas bahwa Algoritma Simpleks bukan hanya sekadar deretan langkah-langkah matematis, melainkan sebuah pilar fundamental dalam bidang optimasi linear yang telah merevolusi cara kita menyelesaikan masalah alokasi sumber daya. Sejak pertama kali diperkenalkan oleh George Dantzig, algoritma ini telah menjadi instrumen krusial bagi para pengambil keputusan di berbagai sektor, memungkinkan mereka untuk mengubah kompleksitas menjadi keputusan yang efisien dan optimal.

Kita telah menjelajahi dasar-dasar optimasi linear, memahami bagaimana masalah dunia nyata dapat diformulasikan ke dalam model matematis yang melibatkan fungsi tujuan, variabel keputusan, dan batasan. Representasi geometris menunjukkan kepada kita mengapa solusi optimal selalu berada di titik sudut daerah fisibel, sebuah wawasan yang menjadi inti intuisi di balik Algoritma Simpleks.

Langkah demi langkah, kita memahami bagaimana Algoritma Simpleks secara iteratif bergerak dari satu titik sudut ke titik sudut yang lebih baik melalui proses pemilihan variabel masuk, variabel keluar, dan operasi pivot pada tabel simpleks. Penggunaan metode seperti Big M dan Dua Fase menunjukkan bagaimana algoritma ini dapat menangani berbagai jenis batasan, memperluas jangkauan aplikasinya.

Konsep dualitas membuka dimensi baru dalam pemahaman masalah optimasi, menawarkan interpretasi ekonomi yang kaya melalui harga bayangan dan memberikan alat analisis yang kuat. Sementara itu, analisis sensitivitas memungkinkan kita untuk mengevaluasi ketahanan solusi terhadap perubahan parameter, sebuah fitur esensial dalam lingkungan bisnis yang tidak pasti.

Meski memiliki keterbatasan, terutama dalam kompleksitas kasus terburuk dan asumsi linearitas yang ketat, Algoritma Simpleks tetap menjadi metode yang dominan karena efisiensi praktisnya dan interpretasi hasilnya yang jelas. Untuk masalah yang sangat besar, metode interior-point muncul sebagai alternatif yang kuat, melengkapi ekosistem alat optimasi.

Aplikasi Algoritma Simpleks mencakup spektrum yang luas, mulai dari mengoptimalkan jadwal produksi, merancang rute pengiriman, mengelola portofolio investasi, hingga mengalokasikan tenaga kerja secara efisien. Di setiap bidang ini, Simpleks membantu organisasi dan individu membuat keputusan yang lebih cerdas, memaksimalkan nilai, dan meminimalkan biaya.

Pada akhirnya, Algoritma Simpleks adalah testimoni akan kekuatan pemikiran algoritmik dalam memecahkan masalah kompleks. Ini adalah alat yang terus berevolusi dan beradaptasi, tetap relevan dan tak tergantikan dalam pencarian kita akan efisiensi dan keunggulan. Dengan pemahaman yang kokoh tentang prinsip-prinsipnya, kita siap untuk memanfaatkan kekuatannya dalam menghadapi tantangan optimasi di masa depan.