Pemrograman Linear — Metode Simpleks & Solusi Grafis

Pemrograman linear adalah metode untuk mencari nilai terbaik dari suatu objektif linear, seperti keuntungan maksimum atau biaya minimum, dengan tunduk pada kendala linear. Pada masalah dengan dua variabel, solusi grafis mencari daerah feasible lalu memeriksa titik-titik sudutnya. Pada masalah yang lebih besar, metode simpleks menggunakan ide titik sudut yang sama secara aljabar.

Gunakan pemrograman linear hanya ketika fungsi objektif dan kendalanya bersifat linear. Jika hubungannya melengkung, berbentuk kurva, atau bergantung pada hasil kali seperti $xy$, maka model tersebut bukan program linear.

Definisi Pemrograman Linear

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

dengan kendala seperti

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

ditambah pertidaksamaan linear serupa, bersama syarat seperti $x_i \ge 0$ ketika nilai negatif tidak masuk akal.

Himpunan semua titik yang memenuhi setiap kendala disebut daerah feasible. Pemrograman linear menanyakan: di antara titik-titik feasible itu, mana yang memberikan nilai objektif terbaik?

Cara Kerja Metode Grafis

Jika hanya ada dua variabel keputusan, Anda dapat menggambar setiap kendala pada bidang $xy$. Irisan dari semua daerah yang diizinkan adalah daerah feasible.

Setiap titik di daerah itu adalah solusi yang valid. Fungsi objektif memberikan suatu nilai pada masing-masing titik.

Untuk program linear, ada satu fakta penting: jika solusi optimal ada, maka setidaknya satu solusi optimal terjadi di titik sudut daerah feasible. Itulah sebabnya metode grafis berfokus pada titik sudut, bukan memeriksa setiap titik di daerah arsiran.

Contoh Soal: Menyelesaikan Masalah Pemrograman Linear Secara Grafis

Misalkan sebuah toko membuat dua produk, $A$ dan $B$.

• Keuntungan per unit $A$: $3$
• Keuntungan per unit $B$: $5$
• Batas waktu mesin: setiap unit $A$ memakai $1$ jam, setiap unit $B$ memakai $2$ jam, dan tersedia paling banyak $8$ jam
• Batas perakitan: setiap unit $A$ memakai $1$ jam, setiap unit $B$ memakai $1$ jam, dan tersedia paling banyak $5$ jam

Misalkan $x$ adalah jumlah unit $A$ dan $y$ adalah jumlah unit $B$.

Maksimumkan

$$P = 3x + 5y$$

dengan syarat

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

Cari titik sudut

Dari sumbu dan garis-garis kendala, titik sudut feasible adalah

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

Titik $(2,3)$ diperoleh dengan menyelesaikan persamaan batas

$$x + 2y = 8,\quad x + y = 5$$

Dengan mengurangkan keduanya diperoleh $y = 3$, lalu $x = 2$.

Uji fungsi objektif di setiap titik sudut

Hitung keuntungan pada setiap titik sudut:

• Di $(0,0)$, $P = 0$
• Di $(5,0)$, $P = 15$
• Di $(0,4)$, $P = 20$
• Di $(2,3)$, $P = 21$

Jadi keuntungan maksimum adalah

$$P = 21$$

pada

$$(x,y) = (2,3)$$

Itulah metode grafis dalam satu kalimat: gambarkan daerah feasible, cari titik sudutnya, lalu hitung nilai objektif di sana.

Intuisi Metode Simpleks

Metode grafis praktis hanya ketika ada dua variabel, dan kadang-kadang tiga jika Anda bersedia membayangkan daerah 3D. Masalah optimasi nyata sering memiliki banyak variabel, sehingga menggambar daerah feasible tidak lagi realistis.

Metode simpleks mempertahankan logika titik sudut yang sama, tetapi melakukannya secara aljabar. Secara umum, metode ini berpindah dari satu titik sudut feasible ke titik sudut feasible lain yang memperbaiki nilai objektif, lalu berhenti ketika tidak ada perpindahan ke titik tetangga yang memberi nilai lebih baik.

Jadi model mental yang baik adalah:

• Metode grafis: melihat titik sudut
• Metode simpleks: menelusuri titik sudut tanpa menggambarnya

Deskripsi ini adalah intuisi, bukan algoritma lengkapnya. Prosedur simpleks yang sebenarnya menggunakan tableau atau bentuk aljabar yang setara untuk menentukan variabel mana yang masuk dan keluar pada setiap langkah.

Mengapa Titik Sudut Penting

Fungsi objektif linear membentuk garis level seperti

$$3x + 5y = k$$

untuk berbagai nilai $k$. Saat Anda menggeser garis itu ke arah keuntungan yang lebih besar, titik terakhir saat garis itu masih menyentuh daerah feasible adalah tempat maksimum terjadi.

Pada banyak gambar, sentuhan terakhir itu terjadi di satu titik sudut. Jika garis objektif sejajar dengan salah satu sisi batas, beberapa titik pada sisi itu bisa sama-sama optimal. Dalam kasus itu, tetap ada setidaknya satu titik sudut yang optimal.

Kesalahan Umum

Mengacaukan feasible dengan optimal

Suatu titik bisa memenuhi semua kendala tetapi tetap tidak memaksimumkan atau meminimumkan objektif. Feasible hanya berarti diperbolehkan.

Lupa syarat nonnegatif

Jika $x$ dan $y$ menyatakan jumlah yang diproduksi atau dikirim, nilai negatif biasanya tidak masuk akal. Menghilangkan $x \ge 0$ atau $y \ge 0$ dapat mengubah masalah.

Menganggap setiap jawaban harus berupa bilangan bulat

Pemrograman linear biasa memperbolehkan nilai pecahan. Jika variabel harus berupa bilangan bulat, seperti jumlah truk atau jumlah pekerja, Anda memerlukan model pemrograman integer atau syarat keintegeran tambahan.

Menganggap setiap masalah punya jawaban terbaik

Beberapa program linear tidak feasible, artinya tidak ada titik yang memenuhi semua kendala. Yang lain tak terbatas, artinya objektif dapat terus membaik tanpa batas. Anda hanya memperoleh optimum hingga jika kendalanya benar-benar cukup membatasi masalah.

Menggunakan metode grafis saat variabel terlalu banyak

Begitu jumlah variabel banyak, menggambar bukan lagi alat yang tepat. Di situlah simpleks atau metode optimasi lain menjadi diperlukan.

Kapan Pemrograman Linear Digunakan

Pemrograman linear digunakan ketika keputusan saling bersaing untuk sumber daya yang terbatas dan baik tujuan maupun batasannya dapat dimodelkan secara linear. Contoh umum meliputi perencanaan produksi, transportasi, penjadwalan tenaga kerja, pencampuran, penjadwalan, dan alokasi anggaran.

Model hanya sebaik asumsi yang digunakan. Jika hubungan nyata tidak cukup mendekati linear, atau jika variabel harus berupa bilangan bulat, program linear biasa mungkin hanya menjadi titik awal.

Coba Soal Serupa

Ambil soal cerita kecil dengan dua produk, dua batas sumber daya, dan satu fungsi keuntungan. Tentukan variabelnya, gambarkan kendalanya, lalu uji sendiri titik-titik sudutnya. Setelah ide itu benar-benar dipahami, metode simpleks akan jauh lebih mudah dimengerti karena metode itu hanya memperluas logika yang sama ke dimensi yang lebih tinggi.