Pemecah Pemrograman Linear

Tentang Pemecah Pemrograman Linear

Pemecah Pemrograman Linear adalah kalkulator online yang mencari nilai maksimum atau minimum dari fungsi objektif linear yang tunduk pada sistem pertidaksamaan atau persamaan linear. Alat ini menggunakan metode simpleks (varian Big-M) sehingga kendala <=, >=, dan = dapat dicampur secara bebas, dan untuk masalah 2-variabel, alat ini menggambar plot wilayah layak interaktif dengan setiap titik sudut dan titik optimum yang disorot.

Apa Itu Pemrograman Linear?

Sebuah masalah pemrograman linear (LP) menanyakan:

Himpunan titik yang memenuhi setiap kendala disebut sebagai wilayah layak, sebuah polihedron konveks. Teorema Fundamental Pemrograman Linear menyatakan bahwa jika LP memiliki optimum terbatas, maka optimum tersebut dicapai pada sebuah titik sudut (titik ekstrem) dari polihedron ini. Inilah sebabnya mengapa metode simpleks — yang berjalan dari satu titik sudut ke titik sudut lainnya — sangat efektif.

Bagaimana Cara Kerja Metode Simpleks

Dimulai dari titik sudut yang layak, metode simpleks berulang kali memperbaiki objektif dengan melakukan pivot ke titik sudut tetangga dengan nilai yang lebih baik. Mekanismenya:

1. Bentuk standar: ubah LP menjadi maks c^Tx dengan kendala Ax = b, x ≥ 0. Untuk kendala <=, tambahkan variabel slack; untuk >=, kurangi surplus dan tambahkan variabel artifisial dengan penalti besar −M; untuk persamaan, tambahkan variabel artifisial.
2. Tableau awal: basis terdiri dari variabel slack dan artifisial, yang memberikan titik sudut awal yang jelas.
3. Variabel masuk: pilih variabel non-basis dengan biaya tereduksi positif terbesar \( c_j - z_j \). Jika tidak ada variabel seperti itu, solusi saat ini adalah optimal.
4. Variabel keluar: dari kolom masuk, lakukan uji rasio minimum — bagi setiap RHS baris dengan entri positifnya di kolom masuk, dan pilih baris dengan rasio terkecil. Jika tidak ada entri positif, LP tidak terbatas.
5. Pivot: gunakan eliminasi Gaussian untuk membuat kolom masuk menjadi vektor unit, dengan angka 1 di baris keluar.
6. Ulangi hingga kriteria penghentian terpenuhi.

Jika ada variabel artifisial yang tetap berada di basis dengan nilai positif saat terminasi, maka LP asli tidak layak.

Metode Grafis (untuk 2 Variabel)

Untuk masalah dua variabel, wilayah layak adalah poligon konveks 2-D. Karena optimum selalu berada di titik sudut, mengenumerasi setiap titik sudut dan mengevaluasi objektif di sana sudah cukup untuk menyelesaikan masalah. Kalkulator ini melakukan enumerasi tersebut dengan memotong setiap pasangan batas kendala, hanya menyimpan perpotongan yang memenuhi semua kendala lainnya, dan mengurutkannya berlawanan arah jarum jam untuk visualisasi.

Sintaks Input

Tulis objektif pada baris pertama, lalu satu kendala per baris. Nama variabel bisa berupa pengenal apa saja (x, y, x1, laba…). Operator yang digunakan adalah <=, >=, dan =. Non-negativitas dapat ditulis sebagai x, y >= 0 sebagai pintasan.

Baris kosong dan komentar yang diawali dengan # akan diabaikan. Pemecah menerima hingga 8 variabel keputusan dan 20 kendala.

Contoh Pengerjaan

Pertimbangkan sebuah bengkel furnitur yang membuat meja dan kursi. Setiap meja menghasilkan laba \\$3 dan membutuhkan 1 unit kayu dan 2 unit tenaga kerja. Setiap kursi menghasilkan laba \\$5 dan membutuhkan 1 unit kayu, 1 unit tenaga kerja, dan 3 unit pernis. Tersedia: 10 kayu, 16 tenaga kerja, 18 pernis. Dengan x = meja dan y = kursi, LP-nya adalah:

Wilayah layak adalah sebuah segi lima. Mengevaluasi Z di setiap titik sudut:

Jadi bengkel tersebut harus membuat 6 meja dan 4 kursi untuk laba maksimum sebesar \\$38. Kendala kayu dan tenaga kerja bersifat mengikat (nilainya sama dengan RHS pada saat optimum); pernis memiliki slack 0 (juga mengikat dalam kasus ini), yang berarti ketiga sumber daya telah habis digunakan.

Masalah Umum & Apa yang Dideteksi Pemecah

Aplikasi

• Bauran produk & perencanaan produksi — berapa banyak dari setiap produk yang harus dibuat untuk laba maksimum di bawah keterbatasan sumber daya.
• Masalah diet & pencampuran — meminimalkan biaya diet atau pakan yang tetap memenuhi standar nutrisi minimum.
• Transportasi & penugasan — meminimalkan biaya pengiriman ketika penawaran dan permintaan harus seimbang.
• Optimasi portofolio — memaksimalkan pengembalian yang diharapkan di bawah kendala risiko atau eksposur (yang dilinearisasi).
• Aliran jaringan — aliran maksimum dan aliran biaya minimum dapat direduksi menjadi LP dengan matriks koefisien unimodular total.
• Penjadwalan — penyusunan jadwal tenaga kerja dengan persyaratan shift dan batas total jam kerja.

Cara Menggunakan Kalkulator Ini

1. Ketik LP Anda di kotak teks. Baris pertama harus dimulai dengan Maximize atau Minimize. Setiap baris berikutnya adalah satu kendala, satu per baris.
2. Gunakan pintasan x, y >= 0 untuk menyatakan non-negativitas bagi semua variabel yang terdaftar sekaligus.
3. Klik Selesaikan Masalah LP. Pemecah akan melaporkan nilai optimal Z, nilai optimal setiap variabel keputusan, daftar kendala mengikat, dan untuk LP 2-variabel, plot wilayah layak interaktif.
4. Arahkan kursor ke titik sudut pada plot untuk melihat koordinat dan nilai Z-nya. Titik optimum disorot dengan bintang.
5. Tinjau tableau simpleks untuk melihat setiap pivot dan melacak bagaimana metode tersebut memperbaiki Z. Kolom masuk disorot dengan warna kuning; baris keluar dengan warna merah.

Pertanyaan yang Sering Diajukan

Apa itu masalah pemrograman linear?

Masalah pemrograman linear (LP) mencari nilai maksimum atau minimum dari fungsi objektif linear pada sekumpulan variabel keputusan yang memenuhi sistem pertidaksamaan atau persamaan linear. Himpunan layak adalah polihedron konveks, dan optimum selalu dicapai pada salah satu titik sudutnya — fakta kunci yang dimanfaatkan oleh metode simpleks.

Bagaimana cara kerja metode simpleks?

Metode simpleks berjalan di sepanjang titik-titik sudut polihedron layak. Setiap langkah (sebuah "pivot") menukar satu variabel dalam basis dengan variabel lainnya, berpindah ke titik sudut tetangga dengan objektif yang lebih baik. Algoritma berhenti ketika tidak ada pivot yang dapat meningkatkan Z — titik tersebut kemudian menjadi optimal. Alat ini menggunakan varian Big-M sehingga kendala <=, >=, dan = dapat dicampur.

Apa itu wilayah layak?

Wilayah layak adalah kumpulan semua nilai variabel yang memenuhi setiap kendala secara bersamaan. Untuk 2 variabel, ini adalah poligon konveks 2-D; untuk n variabel, ini adalah polihedron n-dimensi. Polihedron yang kosong berarti LP tidak layak; polihedron yang membentang tanpa batas ke arah perbaikan berarti LP tidak terbatas.

Apa arti "tidak terbatas" (unbounded) dalam pemrograman linear?

Sebuah LP dikatakan tidak terbatas ketika wilayah layak meregang hingga tak terhingga ke arah di mana objektif terus membaik. Misalnya, Maksimalkan x dengan kendala x ≥ 0 saja tidak memiliki maksimum terbatas. LP dunia nyata yang menghasilkan hasil tidak terbatas biasanya menunjukkan adanya kendala yang hilang — sering kali berupa batas atas pada sumber daya atau variabel.

Apa arti "optima alternatif"?

Optima alternatif terjadi ketika lebih dari satu titik mencapai nilai objektif terbaik yang sama. Secara geometris, objektif sejajar dengan tepi pengikat poligon, sehingga setiap titik di sepanjang tepi tersebut — dan setiap kombinasi konveks dari titik ujungnya — adalah optimal. Pemecah menandai hal ini ketika variabel keputusan non-basis memiliki biaya tereduksi nol saat terminasi.

Berapa banyak variabel dan kendala yang diterima pemecah ini?

Hingga 8 variabel keputusan dan 20 kendala. Plot wilayah layak interaktif hanya digambar untuk masalah 2-variabel; dengan 3 variabel atau lebih, Anda tetap mendapatkan solusi numerik simpleks yang lengkap, tableau langkah-demi-langkah, dan laporan kendala mengikat.

Bacaan Lebih Lanjut

• Pemrograman linear — Wikipedia
• Algoritma simpleks — Wikipedia
• Metode Big M — Wikipedia
• Dualitas dalam optimasi — Wikipedia

Operasi matematika tingkat lanjut:

• Kalkulator Antilog
• Kalkulator Fungsi Beta
• Kalkulator Koefisien Binomial
• Kalkulator Distribusi Binomial
• Kalkulator Bitwise
• Kalkulator Teorema Limit Tengah
• Kalkulator Kombinasi
• Kalkulator Fungsi Kesalahan Pelengkap
• Kalkulator Bilangan Kompleks Unggulan
• Kalkulator Entropi
• Kalkulator fungsi kesalahan
• Kalkulator Peluruhan Eksponensial
• Kalkulator Pertumbuhan Eksponensial Presisi Tinggi
• Kalkulator Integral Eksponensial
• Kalkulator Eksponen (Presisi Tinggi)
• Kalkulator Faktorial
• Kalkulator Fungsi Gamma
• Kalkulator Rasio Emas
• Kalkulator Setengah Hidup
• Kalkulator Pertumbuhan Persentase
• Kalkulator Permutasi
• Kalkulator Distribusi Poisson
• Kalkulator Akar Polinomial dengan Langkah-Langkah Terperinci
• Kalkulator Probabilitas
• Kalkulator Distribusi Probabilitas
• Kalkulator Proporsi
• Kalkulator Rumus Kuadrat
• Kalkulator Ilmiah
• Kalkulator Notasi Ilmiah Unggulan
• Kalkulator Angka Penting Baru
• Kalkulator Jumlah Kubik
• Kalkulator Jumlah Angka Berurutan
• Kalkulator Jumlah Kuadrat
• Generator Tabel Kebenaran
• Kalkulator Teori Himpunan
• Generator Diagram Venn (3 Himpunan)
• Kalkulator Teorema Sisa Cina
• Kalkulator Fungsi Totien Euler
• Kalkulator Algoritma Euklides Diperluas
• Kalkulator Invers Multiplikatif Modular
• Kalkulator Pecahan Lanjutan
• Kalkulator Jalur Terpendek Dijkstra
• Kalkulator Pohon Rentang Minimum
• Validator Urutan Derajat Graf
• Kalkulator Derangement Subfaktorial
• Kalkulator Bilangan Stirling
• Kalkulator Prinsip Sarang Merpati
• Kalkulator Distribusi Stasioner Rantai Markov
• Kalkulator Pembulatan Baru
• Kalkulator Distribusi Binomial Negatif Baru
• Kalkulator Permutasi dengan Pengulangan Baru
• Kalkulator Eksponensial Modular Baru
• Kalkulator Akar Primitif
• Penyederhana Aljabar Boolean Baru
• Pemecah Peta Karnaugh (K-Map) Baru
• Kalkulator Pewarnaan Graf Baru
• Kalkulator Pengurutan Topologi Baru
• Kalkulator Matriks Ketetanggaan Baru
• Kalkulator Inklusi-Eksklusi Baru
• Pemecah Pemrograman Linear Baru
• Pemecah Masalah Penjual Keliling (TSP) Baru
• Pemeriksa Jalur Hamilton Baru
• Pemeriksa Grafik Planar Baru
• Kalkulator Aliran Jaringan (Aliran Maksimum) Baru
• Pemecah Masalah Pernikahan Stabil Baru
• Kalkulator Orde Teori Grup Baru
• Kalkulator Ring dan Lapangan Baru