PENGENALAN PROGRAM LINEAR
PROGRAM LINEAR
• Merupakan alat yang digunakan untuk menyelesaikan masalah optimasi
suatu model linear dengan keterbatasan-keterbatasan sumber daya yang
tersedia.
• Banyak digunakan untuk menyelesaikan masalah optimasi dalam bentuk
linear.
• Bentuk linear artinya bahwa seluruh fungsi dalam model merupakan fungsi
linear.
• Tujuan utama dari program linear ini adalah menentukan nilai optimum
(maksimal/minimal) dari fungsi tujuan yang telah ditetapkan.
• Fungsi pada model ada dua macam:
– Fungsi tujuan, untuk menentukan nilai optimum dari fungsi tersebut yaitu nilai
maksimal untuk masalah keuntungan dan nilai minimal untuk masalah biaya
– Fungsi pembatas, diperlukan berkenaan dengan adanya keterbatasan sumber
daya yang tersedia, misalnya jumlah bahan baku yang terbatas, waktu kerja,
jumlah tenaga kerja, luas gudang persediaan.
METODE GRAFIK
• CONTOH1:
• Pada suatu hari minggu Anis akan kedatangan teman-
tamannya, oleh karena itu untuk menjamu temannya itu,
Anis akan membuat dua macam roti, yaitu roti cokelat dan
roti keju. Semua bahan untuk membuat kedua jenis roti
tersebut telah disiapkan, dan ternyata jumlah keju dan
jumlah cokelatnya terbatas, yaitu 300 gram keju dan 200
gram cokelat. Bahan-bahan lain seperti gandum, gula,
mentega dan lain-lain cukup. Sebuah roti keju memerlukan
30 gram keju dan 10 gram cokelat. Sedangkan roti cokelat
memerlukan 10 gram keju dan 20 gram cokelat.
• Tentukan banyaknya masing-masing roti agar jumlah roti
yang dibuat sebanyakbanyaknya!
• Penyelesaian
Untuk menyederhanakan masalah ini, kita
buat tabel berkenaan dengan masalah pada
contoh 1
• Pembuatan model matematika:
Fungsi tujuan:
Maksimumkan Z = x1 + x2
Fungsi pembatas:
30 x1 + 10 x2 ≤ 300
10 x1 + 20 x2 ≤ 200
x1 ≥ 0, x2 ≥ 0
• Untuk membuat grafik, pertama-tama buatlah sistem sumbu
koordinat dengan sumbu x1 mendatar dan sumbu x2 tegak,
kemudian buatlah garis dengan persamaan:
30 x1 + 10 x2 = 300
• Selanjutnya dengan cara yang sama, digambar dari fungsi pembatas
10 x1 + 30 x2 ≤ 200, sehingga diperoleh grafik seperti pada Gambar 3
• Dari teorema di atas, maka nilai maksimum akan terjadi di titik (0,
0), (10, 0), (8, 6), atau (0, 10). Fungsi tujuan pada persoalan ini
adalah memaksimumkan Z = x1 + x2, sehingga nilai Z dari titik-
titik ujung itu seperti pada tabel 2.
• Dari Tabel 2, terlihat bahwa, nilai Z maksimum terjadi pada titik
(8, 6) dengan nilai Z = 14. Ini berarti bahwa supaya diperoleh
jumlah roti maksimum, maka harus dibuat 8 buah roti keju dan 6
buah roti cokelat.
• Selain menggunakan tabel, dapat pula digunakan garis
selidik.
• Garis selidik adalah garis-garis yang persamaannya diperoleh
dari fungsi tujuan dengan memberikan nilai k (Z = k, k
berubah-ubah), dengan demikian diperoleh garis-garis yang
sejajar dengan fungsi tujuan dengan Z = 0. Nilai Z optimal
akan terjadi dengan menggeser garis selidik ini ke titik ujung
paling dekat dengan garis selidik di Z = 0 untuk fungsi tujuan
minimum dan titik paling jauh dengan garis selidik di Z = 0
untuk fungsi tujuan maksimum.
• Pada soal di atas, garis selidiknya adalah x1 + x2 = k. Kita
memulai dengan k = 0, sehingga salah satu garis selidiknya
adalah x1 + x2 = 0.
• CONTOH 2:
• Tuan Jaka akan memindahkan 120 kotak besar
dan 180 kotak kecil, dengan dua jenis mobil
angkut yaitu mobil A dan mobil B. Mobil A dapat
mengangkut 8 kotak besar dan 4 kotak kecil,
sedangkan mobil B dapat mengangkut 10 kotak
besar dan 20 kotak kecil. Bilamana sewa mobil A,
Rp 100.000 sebuah dan sewa mobil B, Rp 150.000
sebuah.
• Tentukan banyaknya masing-masing mobil agar
total sewa mobil minimum!
TERIMA KASIH