Program Linear: Muqodimah

1. Muqodimah Optimisasi

A. Pendahuluan Optimisasi: Cara Mencari Nilai Terbaik dalam Hidup (dan Matematika)

Halo, Sixtyfourians! Pernahkah kalian berfikir, "Bagaimana cara mendapatkan hasil terbaik dari segala sesuatu?" Mungkin untung maksimum dari jualan, atau biaya minimum saat bikin acara?

Nah, itulah inti dari Optimisasi! Ini adalah cabang matematika yang intinya mencari nilai optimum (terbaik), entah itu maksimum (tertinggi) atau minimum (terendah) dari suatu fungsi atau situasi. Dalam kehidupan sehari-hari, kita selalu berhadapan dengan masalah optimisasi, lho!

B. Dua Tipe Utama Masalah Optimisasi

1. Optimisasi Fungsi Tanpa Kendala (Unconstrained Optimisation)

Ini adalah tipe masalah yang paling sederhana. Kita hanya punya satu fungsi, f(x), dan kita ingin tahu di mana nilai x akan membuat f(x) mencapai puncaknya (maksimum) atau lembahnya (minimum), tanpa ada batasan apa pun pada nilai x.

Contoh: Jika kalian punya fungsi sederhana, kita bisa menggunakan turunan pertama (f′(x)) untuk mencari calon titik optimum. Jika f′(x) = 0, itu adalah titik stasioner. Untuk menentukan apakah itu maksimum atau minimum, kita bisa lihat turunan kedua (f′′(x)) atau turunan yang lebih tinggi.

2. Optimisasi Fungsi dengan Kendala (Constrained Optimisation)

Nah, ini yang sering terjadi di dunia nyata. Kita ingin mencari nilai optimum, tapi ada syarat atau batasan (kendala) yang harus dipatuhi. Kita mencari maks(min)f(x) dengan x ∈ Ω, di mana Ω adalah himpunan semua kendala.

2. Mengenal Bentuk Umum Optimisasi dengan Kendala

Untuk masalah yang lebih rumit, terutama yang melibatkan banyak variabel atau fungsi nonlinear, ada formulasi yang lebih umum:

1. Ekstrem dengan Kendala Berbentuk Persamaan

Ini adalah masalah saat kendala kita adalah persamaan (= 0).

Cari variabel xⱼ yang mengoptimalkan f = F(x₁, x₂, ..., xₙ)

Dengan kendala gᵢ(x₁, x₂, ..., xₙ) = 0, untuk i = 1, 2, …, m.

Metode Andal: Untuk menyelesaikan masalah ini (terutama yang nonlinear), sering digunakan Metode Lagrange (atau Pengali Lagrange), yang memungkinkan kita memasukkan kendala ke dalam fungsi tujuan.

2. Ekstrem dengan Kendala Pertidaksamaan

Ini lebih kompleks lagi, karena kendalanya adalah pertidaksamaan (≤ 0, ≥ 0).

Cari variabel xⱼ yang mengoptimalkan f = F(x₁, x₂, ..., xₙ)

Dengan kendala gᵢ(x₁, x₂, ..., xₙ) (≤, = ,≥) 0, untuk i = 1, 2, …, m.

Jika fungsi-fungsi F dan g semua linear, masalah ini disebut Program Linear (Linear Program/LP), yang merupakan salah satu kasus khusus optimisasi yang sangat sering digunakan di berbagai bidang, mulai dari bisnis hingga logistik! Akan tetapi jika diantara fungsi-fungsi F dan g ada yang tidak linear, masalah ini bukan program linear, melainkan Program Non-Linear (Non-Linear Program/NLP).

Intinya: Optimisasi adalah seni dan ilmu untuk membuat keputusan terbaik di tengah keterbatasan yang ada. Ini adalah tool penting untuk memaksimalkan keuntungan, meminimalkan biaya, atau sekadar mendapatkan ukuran kandang ayam yang paling efisien!

3. Program Linear: Blueprint untuk Keputusan Bisnis Terbaik!

Halo, Sixtyfourians! Pernahkah kalian dihadapkan pada situasi di mana sumber daya terbatas (seperti waktu, uang, atau bahan baku) tapi kalian harus mendapatkan hasil yang maksimal (untung besar) atau mengeluarkan biaya minimal? Jika ya, kalian sedang berhadapan dengan masalah Program Linear (PL)!. Program Linear adalah alat matematika super ampuh yang masuk dalam kategori Optimisasi dengan Kendala. Intinya, PL membantu kita menemukan kombinasi aktifitas terbaik untuk mencapai tujuan (misalnya, untung paling tinggi) di bawah batasan-batasan (kendala) yang ada.

A. Pilar Utama Masalah Program Linear

Sebuah masalah bisa diselesaikan dengan PL jika memenuhi empat syarat kunci:

1. Ada Pilihan Kegiatan: Harus ada beberapa cara atau faktor yang bisa dikombinasikan (misalnya, memproduksi Barang A atau Barang B).

2. Ada Sumber Daya Terbatas: Harus ada batasan sumber daya (seperti kapasitas mesin, stok bahan mentah).

3. Ada Fungsi Tujuan: Harus ada target yang jelas untuk di-optimalkan (Maksimalkan Untung atau Minimalkan Biaya).

4. Relasi Semuanya Linear: Hubungan antara semua faktor (tujuan dan kendala) harus berbentuk persamaan/pertidaksamaan linear (bukan kuadrat, kubik, dsb.).

B. Anatomi Model Matematika PL

Untuk memecahkan masalah PL, langkah pertamanya adalah mengubah masalah nyata (misalnya, masalah pabrik atau peternakan) menjadi Model Matematika. Proses ini melibatkan 3 langkah inti:

1. Penentuan Variabel Keputusan (xⱼ).

Ini adalah hal-hal yang harus kalian putuskan besarannya.

2. Penentuan Fungsi Tujuan (f)

Inilah sasaran utama kalian:

• Maksimisasi, contoh: f(x, y) = 4x + 3y dengan mencari keuntungan tertinggi.

• Minimisasi, contoh: f(x, y) = x + 2y dengan mencari biaya terendah.

3. Penentuan Fungsi Batasan (Kendala)

Ini adalah batasan-batasan sumber daya yang kalian miliki.

Bentuk Umum PL:

Optimalkan f(x₁, x₂, ..., xₙ) = c₁x₁ + c₂x₂ + ... + cₙxₙ dengan kendala

aᵢ₁x₁ + aᵢ₂x₂ + ... + aᵢₙxₙ (≤, = ,≥) bᵢ

serta kendala non-negatif xⱼ ≥ 0

Catatan Penting: Kendala  (nilai variabel tidak boleh negatif) sangat umum karena dalam kasus nyata, kita tidak bisa memproduksi atau membeli barang dalam kuantitas minus!

C. Metode Apa yang Digunakan untuk Menyelesaikan PL?

Setelah model matematika jadi, kita harus menyelesaikannya untuk menemukan nilai  dan  yang optimal. Ada beberapa metode utama:

• Metode Grafik: Paling mudah dan cepat, tapi hanya bisa dipakai jika variabel keputusannya hanya dua (misalnya x dan y).

• Metode Simpleks: Metode aljabar yang paling sering digunakan untuk masalah dengan banyak variabel (tiga atau lebih).

• Metode Simpleks Revisi, Dual, dan Khusus: Ini adalah varian yang lebih canggih, digunakan untuk kasus-kasus khusus (seperti masalah Transportasi atau Penugasan).

Intinya, Program Linear adalah langkah awal bagi siapa pun yang ingin membuat keputusan terukur dan terjamin optimal di tengah keterbatasan.

Contoh Permasalahan

1. Perusahaan Uniform Romeo Foxtrot Alfa (disingkat URFA)

Perusahaan URFA ingin tahu berapa banyak Barang P1 dan P2 yang harus diproduksi agar untung maksimal. Mereka dibatasi oleh stok 3 bahan mentah (A, B, C).

a. Berikut ini tabelnya:

Bahan Mentah	Kebutuhan P1	Kebutuhan P2	Stok Maksimum
A	1	1	50
B	1	2	80
C	3	2	140
Harga Jual	Rp4,000	Rp3,000

b. Model Matematisnya:

• Variabel Keputusan: x = Produksi P1; y = Produksi P2.

• Fungsi Tujuan (Maksimalisasi):

Maks f = 4x + 3y

• Kendala (Keterbatasan Bahan):

x + y ≤ 50 (Bahan A)

x + 2y ≤ 80 (Bahan B)

3x + 2y ≤ 140 (Bahan C)

x ≥ 0, y ≥ 0

2. Peternakan Pak Rosyid

Peternak Rosyid ingin mencampur makanan M1 dan M2 untuk sapi. Tujuannya adalah memastikan nutrisi A, B, dan C terpenuhi minimal, tapi dengan biaya paling kecil.

a. Berikut ini tabelnya:

Nutrisi	Kandungan M1	Kandungan M2	Kebutuhan Minimum
A	3	1	27
B	1	1	21
C	1	2	30
Harga Beli	4	2

b. Model Matematisnya:

• Variabel Keputusan: x = Timbangan M1 (pon); y = Timbangan M2 (pon).

• Fungsi Tujuan (Minimalisasi):

Min f = 4x + 2y

• Kendala (Kebutuhan Nutrisi):

3x + y ≥ 27 (Nutrisi A)

x + y ≥ 21 (Nutrisi B)

x + 2y ≥ 30 (Nutrisi C)

x ≥ 0, y ≥ 0