Sebelum membentuk tableau, pastikan LP Anda sudah dalam bentuk standar (tiga syarat):
Syarat
Kondisi Asli
Bentuk Standar
1. Fungsi tujuan
Maksimasi (atau minimasi)
Tetap sama
2. Semua kendala
≤ (lebih kecil sama dengan)
Diubah ke = dengan menambah slack variable
3. Semua variabel
Harus tidak negatif
$X_{1}, X_{2} \geq 0$ tetap berlaku
Kelak di kuliah lanjut: kendala ≥ pakai surplus variable + artificial variable; kendala = langsung pakai artificial variable. Hari ini fokus ke kasus ≤ dulu. Bentuk standar (standard form) adalah representasi LP di mana semua kendala berbentuk persamaan dan semua variabel non-negatif.
Slack Variable — Mengubah ≤ Menjadi =
Menambahkan Slack Variable pada Setiap Kendala ≤
Kendala Asli (Pertidaksamaan)
$2X_{1} + 4X_{2} \leq 100$ (jam kerja)
$3X_{1} + 2X_{2} \leq 90$ (material)
Setelah Ditambah $S_{1}, S_{2}$
$2X_{1} + 4X_{2} +$ $S_{1}$ = 100
$\to S_{1} =$ sisa jam kerja
$3X_{1} + 2X_{2} +$ $S_{2}$ = 90
$\to S_{2} =$ sisa material
$$S_{1}$$ dan $$S_{2} \geq 0$$. Bila $S_{1} = 0$: kendala jam binding (terpakai penuh). Bila $S_{1}$ > 0: masih ada sisa kapasitas. Slack variable (S) adalah variabel non-negatif yang merepresentasikan sisa kapasitas tidak terpakai.
Coba Sendiri: Lihat Lagi Daerah Layak Sebelum Masuk Simpleks
Setiap iterasi simpleks berpindah antar corner point — segarkan ingatan visual Anda tentang daerah layak dan corner points dengan simulator grafis.
Basic Feasible Solution — Titik Sudut dalam Algebra
Solusi Dasar (Basic Solution)
Dari n variabel total (keputusan + slack), pilih m variabel sebagai basic variables (= tidak nol). Sisa = non-basic variables (= 0).
Di sini: 4 variabel total $(X_{1}, X_{2}, S_{1}, S_{2}), 2$ kendala $(m=2) \to 2$ basic + 2 non-basic.
BFS Awal — Titik Asal (0,0)
BFS Awal: tetapkan $X_{1}=0, X_{2}=0$ (non-basic); maka $S_{1}=100, S_{2}=90$ (basic).
Ini adalah titik asal (0,0) di grafis — belum ada produksi, semua kapasitas belum terpakai.
Simpleks = bergerak dari satu BFS ke BFS tetangga yang lebih baik, hingga tidak ada yang lebih baik lagi. Basic variable adalah variabel bernilai tidak-nol saat ini ("masuk basis"); non-basic variable bernilai nol ("di luar basis").
Bagian 2 — Membangun Simplex Tableau
Konstruksi Tableau Awal
Baris kendala • Baris Z • Pembacaan BFS awal
HDN-1 — Step A: Kasus Dua Produk, Formulasi & Tableau Awal
Data Produksi
$P1 (X_{1})$
$P2 (X_{2})$
Kapasitas
Jam kerja/unit
2
4
100 jam
Material (kg)/unit
3
2
90 kg
Profit (Rp ribu)/unit
30
40
—
Formulasi LP & Bentuk Standar
Maks $Z = 30X_{1} + 40X_{2}$
$2X_{1} + 4X_{2} \leq 100$
$3X_{1} + 2X_{2} \leq 90$
$X_{1}, X_{2} \geq 0$
Bentuk standar $(+ S_{1}, S_{2})$:
$2X_{1} + 4X_{2} + S_{1} = 100$
$3X_{1} + 2X_{2} + S_{2} = 90$
$Z - 30X_{1} - 40X_{2} = 0$
$X_{1} =$ jumlah unit $P1; X_{2} =$ jumlah unit P2. RHS (right-hand side) = nilai kapasitas. BFS awal: $X_{1}=0, X_{2}=0 \to S_{1}=100, S_{2}=90, Z=0$.
Anatomi Simplex Tableau
Tableau Awal — Dibaca dari Kanan ke Kiri
Basis
$X_{1}$
$X_{2}$
$S_{1}$
$S_{2}$
RHS
$S_{1}$
2
4
1
0
100
$S_{2}$
3
2
0
1
90
Z
−30
−40
0
0
0
Kolom Basis: variabel yang saat ini basic $(S_{1}=100, S_{2}=90)$.
Kolom RHS: nilai variabel basic saat ini; Z=0 = belum ada profit.
Baris Z: koefisien negatif → variabel masih bisa menaikkan Z.
−40 paling negatif $\to X_{2}$ adalah kandidat entering variable pertama. Kolom pivot (pivot column) = kolom $X_{2}$.
Baris Z & Koefisien Negatif — Membaca Sinyal Optimal
Ada Koefisien Negatif di Baris Z
Solusi belum optimal. Variabel dengan koefisien paling negatif = kandidat entering variable (meningkatkan Z lebih cepat).
→ LANJUT ITERASI
Semua Koefisien ≥ 0 di Baris Z
Solusi sudah optimal. Tidak ada variabel non-basic yang bisa menaikkan Z lagi.
→ BACA SOLUSI
Kondisi optimalitas (maksimasi): tidak ada koefisien negatif di baris Z. Dari tableau awal: −40 dan −30 → belum optimal → iterasi diperlukan.
Bagian 3 — Iterasi Pivot
Langkah demi Langkah Menuju Optimal
Entering variable • Leaving variable (minimum ratio test) • Operasi baris • Iterasi
Aturan 1 — Pilih Entering Variable (Kolom Pivot)
Entering variable = variabel non-basic dengan koefisien PALING NEGATIF di baris Z j* = argmin $\{ c̄_{j} : c̄_{j}$ < 0 } $$(c̄_{j} =$$ reduced cost $$X_{j} di$$ baris Z)
Kondisi
Tindakan
$c̄_{j}$ < 0 untuk beberapa j
Pilih j dengan $c̄_{j}$ paling negatif $\to$ entering variable
Semua $c̄_{j} \geq 0$
Solusi sudah optimal → BERHENTI
Intuisi: koefisien paling negatif $\to$ variabel yang paling cepat meningkatkan Z per unit yang ditambahkan. Reduced cost $(c̄_{j})$ mengukur seberapa besar Z meningkat per unit $X_{j}$; negatif berarti menguntungkan untuk dimasukkan.
Dari tableau awal: $c̄_X_{1}=-30, c̄_X_{2}=$−40 $\to$ entering variable $$= X_{2}$$
Aturan 2 — Pilih Leaving Variable (Minimum Ratio Test)
Minimum Ratio Test: rasio_i = RHS_i ÷ a_ij* (hanya baris dengan a_ij* > 0) Leaving variable = baris dengan rasio minimum (terkecil, tidak negatif)
Penerapan pada HDN-1 (entering $= X_{2}$, kolom pivot $= X_{2})$:
Baris
Variabel Basic
Koefisien $X_{2}$
RHS
Rasio
1
$S_{1}$
4
100
100÷4 = 25 ← minimum
2
$S_{2}$
2
90
90÷2 = 45
Elemen pivot (pivot element) = koefisien di perpotongan baris pivot (baris 1) dan kolom pivot $(X_{2}) =$ 4. Leaving variable $= S_{1}$ (rasio paling kecil). Abaikan baris dengan koefisien $\leq 0 di$ kolom pivot.
Pilih kolom pivot (entering variable) dan baris pivot (leaving variable via ratio test), lalu jalankan operasi baris dan amati tableau berubah hingga optimal.
Lihat kolom "Basis". Variabel di sana bernilai RHS-nya: $X_{2}=15, X_{1}=20$.
Langkah 2 — Variabel Non-Basic
= 0
Variabel tidak ada di kolom Basis bernilai nol: $S_{1}=0, S_{2}=0$ → kedua kendala binding.
Langkah 3 — Nilai Z
1200
Rp ribu
Baca RHS baris Z = nilai Z optimal. Profit maksimum = Rp 1.200 ribu.
Slack nol $(S_{1}=S_{2}=0) \to$ kapasitas jam kerja & material terpakai habis. Binding constraint (kendala aktif) = sumber daya yang bernilai tinggi untuk diperluas.
Coba Sendiri: Operasi Baris Elementer = Aljabar Linier Dasar
Pivot pada tableau simpleks adalah operasi baris elementer — pelajari kembali perpotongan dua persamaan linier agar pivot terasa natural.
Studi Kasus Indonesia — PT Pertamina Lubricants
Kilang Cilacap memproduksi dua pelumas andalan. Manajer produksi harus menentukan bauran optimal (product mix).
Data Produksi (per 1.000 liter)
Fastron (F)
Prima XP (P)
Kapasitas
Jam mesin
3
2
120 jam
Base oil (ton)
2
4
100 ton
Margin (Rp juta)
45
35
—
Maks Z = 45F + 35P 3F + 2P ≤ 120; 2F + 4P ≤ 100 F, P ≥ 0
Berapa ribu liter Fastron & Prima XP per shift untuk memaksimalkan margin?
Tambah 10 jam lembur (biaya Rp 60 juta) — worthwhile?
Margin Fastron turun dari 45 → 35 — bauran produksi berubah?
Pertanyaan 2 & 3 dijawab oleh Analisis Sensitivitas — Bagian 4.
Bagian 4 — Analisis Sensitivitas
"Kalau Kondisi Berubah, Apakah Solusi Kita Masih Berlaku?"
Shadow price • Allowable range koefisien tujuan • Interpretasi manajerial
Mengapa Sensitivitas? Dunia Nyata Tidak Pasti
What-If 1 — Profit Berubah
Margin Fastron turun dari Rp 45 jt → Rp 35 jt. Apakah bauran produksi optimal berubah?
→ Allowable Range Koefisien Tujuan
What-If 2 — Kapasitas Ditambah
Tawaran lembur: tambah 10 jam kapasitas mesin. Berapa tambahan margin yang didapat?
→ Shadow Price × ΔCapacity
What-If 3 — Kapasitas Berkurang
Pasokan base oil bulan ini berkurang dari 100 ton → 80 ton. Seberapa turun margin?
→ Shadow Price × ΔCapacity
Prinsip Utama
Perubahan dalam allowable range → basis tidak berubah, hitung Z baru langsung. Di luar range → re-solve (jalankan ulang LP).
Excel Solver → Sensitivity Report → langsung dapat semua angka.
Shadow Price — Nilai Marginal Sumber Daya
Shadow Price $(y_{i}) = \Delta Z \div \Delta $RHS$_{i}$ (parameter lain tetap) Sumber: koefisien S_i di baris Z pada tableau final
Shadow Price > 0
Kendala binding — terpakai penuh. Menambah kapasitas akan meningkatkan Z. Layak diinvestasikan bila biaya penambahan < shadow price.
Shadow Price = 0
Kendala non-binding — ada slack. Menambah kapasitas tidak mengubah Z; sumber daya berlebih, bukan bottleneck.
Shadow price BUKAN harga pasar. Ia adalah nilai internal satu unit kapasitas ekstra, diukur dalam satuan fungsi tujuan (misal: Rp ribu profit per jam ekstra). Istilah lain di Excel Solver: Dual Value.
HDN-2 — Membaca Shadow Price dari Tableau Final
Tableau final HDN-1 (ulang dari Slide 16):
Basis
$X_{1}$
$X_{2}$
$S_{1}$
$S_{2}$
RHS
$X_{2}$
0
1
⅜
−¼
15
$X_{1}$
1
0
−¼
½
20
Z
0
0
7,5
5
1200
Langkah
Tindakan
Nilai
1
Lihat baris Z, kolom $S_{1}$
7,5
2
Lihat baris Z, kolom $S_{2}$
5
3
Interpretasi $S_{1}$ (jam kerja): tiap 1 jam ekstra $\to Z$ naik Rp 7.500
Worthwhile bila biaya < 7.500
4
Interpretasi $S_{2}$ (material): tiap 1 kg ekstra $\to Z$ naik Rp 5.000
Worthwhile bila biaya < 5.000
Kedua kendala binding $(S_{1}=S_{2}=0) \to$ keduanya bernilai untuk diperluas. Verifikasi: 7,5×100 + 5×90 = 750 + 450 = 1200 ✓
Coba Sendiri: Baca Shadow Price & Allowable Range
Ubah RHS salah satu kendala dalam batas allowable range-nya, lalu amati bagaimana Z bergerak linear sesuai shadow price — dan apa yang terjadi begitu RHS melewati batas itu.
Seberapa jauh profit per unit boleh berubah tanpa mengubah basis (= bauran produksi optimal)?
Allowable Decrease (AD) = min { c̄_k ÷ ȳ_kj } untuk ȳ_kj > 0 Allowable Increase (AI) = min { c̄_k ÷ |ȳ_kj| } untuk ȳ_kj < 0 ȳ_kj = koefisien non-basic k pada baris $X_{j} di$ tableau final
Penerapan untuk $X_{2} (c_{2}=40$, baris $X_{2} di$ tableau final: [0, 1, ⅜, −¼ | 15]):
Allowable range $$c_{2} = [20, 60]$$. Selama $c_{2} \in [20, 60]$, basis optimal tidak berubah $(X_{1}=20, X_{2}=15$ tetap). Jika $c_{2}$ keluar dari range $\to re-$solve.
Kerjakan Soal B-1 s.d. B-3 di Lampiran B (latihan mandiri)
Bawa laptop saat Pertemuan 5 — langsung pakai Excel Solver
Tugas: Kerjakan soal di Lampiran B dan kirim via EMAS UNDIP (elearning2.undip.ac.id) sebelum Pertemuan 5. EMAS = E-Learning Management Adaptive System UNDIP.