Titik Awal Simpleks

Simpleks adalah metode yang digunakan dalam masalah pemrograman linier untuk mendapatkan solusi untuk masalah pemrograman linier. Sebagai rekap, masalah pemrograman linear melibatkan penentuan nilai maksimum atau minimum dari fungsi obyektif yang diberikan serangkaian batasan. Batasan akan membentuk batas polihedron. Di bawah asumsi dari set kendala yang cembung setiap titik di polyhedron akan menghasilkan nilai ekstrim dari fungsi tujuan baik maksimum atau minimum.

Karena batas yang layak menjadi cembung vertex akan menghasilkan minimum lokal yang juga merupakan minimum global. Demikian pula dalam fungsi cekung, maksimum lokal juga akan menjadi maksimum global karena fungsi menjadi cekung. Untuk meringkas fungsi cembung adalah tempat titik pada fungsi selalu berada di dalam garis yang terhubung antara dua titik pada batas fungsi.

Metode Simplex dimulai dengan menetapkan nilai variabel non-dasar menjadi 0 dan kemudian melanjutkan untuk menemukan nilai optimal dari fungsi obyektif dengan mengidentifikasi arah perolehan atau pengurangan tertajam dari nilai fungsi obyektif. Tetapi simpleks mengasumsikan titik awal di mana variabel non-dasar ditetapkan ke 0 masing-masing. Nilai optimum dari fungsi obyektif ditemukan setelah beberapa iterasi di mana algoritma memilih titik dengan gain maksimum dari nilai absolut dari fungsi obyektif. Metode Simplex efisien karena tidak menyebutkan semua kemungkinan solusi, tetapi menyatu dengan nilai aktual dalam jumlah pencarian yang lebih sedikit.

Di sini jika ada 4 atau 5 simpul dari polyhedron dan solusi optimal ditemukan setelah 5 iterasi (misalnya) maka orang harus memahami bahwa ada asumsi yang melekat bahwa solusi yang layak pertama ditentukan dengan menetapkan variabel non-dasar menjadi 0 yang merupakan (0,0) koordinat dari polyhedron.

Disini perlu dicatat bahwa dengan memperbaiki variabel-variabel non-dasar menjadi 0 sebagai titik awal dari simpleks dapat diasumsikan titik awal yang jauh dari optimal. Jadi Simplex dapat direvisi untuk membuat angka perkiraan cerdas tentang keberadaan di mana iterasi perlu dimulai. Tidak ada jalan dari Simplex kira-kira sebanding dengan kekuatan jumlah kendala. Seseorang dapat menerapkan beberapa metode probabilistik dan mendapatkan aturan heuristik untuk membuat Simplex mulai pada titik dekat yang optimal.

Leave a Reply

Your email address will not be published. Required fields are marked *