Program Linier

Program Studi
Te k n i k S i p i l
PEMROGRAMAN LINIER

Tujuan :
1. Memahami prinsip dan asumsi
model LP
2. Mampu memformulasikan
masalah ke dalam model LP
Introduction
Teknik pengambilan keputusan dalam
permasalahan yang berhubungan dengan
pengalokasian sumber dasar secara
optimal
Suatu model umum yang digunakan dalam
pemecahan masalah pengalokasian sumber-sumber
yang terbatas secara optimal.
Masalah tersebut timbul apabila seseorang
diharuskan untuk memilih atau menentukan tingkat
setiap kegiatan yang akan dilakukan, yang masing-
masing kegiatan membutuhkan sumber yang sama
sedangkan jumlahnya terbatas.

Prinsip
Setiap organisasi berusaha mencapai tujuan
yang telah ditetapkan sesuai dengan
keterbatasan sumber daya.
Implementasi
• Perbankan: Portofolio Investasi
• Periklanan
• Industri Manufaktur: Penggunaan
Mesin – Kapasitas Produksi
• Pengalokasian
Sumberdaya/komposisi
bahan/material
• Distribusi dan pengangkutan
• Penugasan karyawan
 •Naik turunnya nilai Z
•Penggunaan sumber atau fasilitas yang tersedia
akan berubah secara sebanding (proportional)
Asumsi dengan perubahan tingkat kegiatan

Dasar Proportionality
Progra
m •Nilai tujuan tiap kegiatan tidak saling mempengaruhi
•Kenaikan dari nilai tujuan (Z) yang diakibatkan oleh kenaikan
Linier suatu kegiatan dapat ditambahkan tanpa mempengaruhi
bagian nilai Z yang diperoleh dari kegiatan lain

Additivity
 • Keluaran (output) • Asumsi yang
yang dihasilkan oleh menyatakan bahwa
Asumsi setiap kegiatan semua parameter yang
terdapat dalam model
Dasar dapat berupa Program Linier (aij, bi,
bilangan pecahan.
Progra Demikian pula
cj) dapat diperkirakan
dengan pasti,
m dengan nilai Z yang
dihasilkan
meskipun jarang
dengan tepat.
Linier Determinist
Divisibility ic
(Certainty)
Karakteristik
Persoalan
• Ada tujuan yang ingin dicapai
• Tersedia beberapa alternatif untuk mencapai
tujuan
• Sumberdaya dalam keadaan terbatas
• Dapat dirumuskan dalam bentuk matematika
(persamaan/ketidaksamaan)
Contoh pernyataan ketidaksamaan:
Untuk menghasilkan sejumlah meja dan kursi secara
optimal, total biaya yang dikeluarkan tidak boleh
lebih dari dana yang tersedia.
Pernyataan bersifat Normatif
Penyelesaian
Persoalan
 Jenis ‘Fungsi’ Program Linier
• Fungsi yang menggambarkan tujuan sasaran dalam
Fungsi permasalahan program linier yang berkaitan dengan
pengaturan secara optimal sumberdaya, untuk
Tujuan memperoleh keuntungan maksimal atau biaya minimal.
• Umumnya, nilai yang dioptimalkan dinyatakan sebagai Z

Fungsi • Bentuk penyajian secara matematis Batasan-Batasan

kapasitas yang tersedia yang akan dialokasikan
Batasan secara optimal ke berbagai kegiatan.
Model Program Linier
Model Matematis
Simbol persamaan LP
Z = var kriteria (nilai fungsi tujuan)
xj = var keputusan/level aktivitas (x1, x2, ,… xn)
cj = kontribusi var keputusan terhadap tujuan
aij = penggunaan sumber daya ke i oleh aktivitas j
(a11, … amn)
bj = jumlah sumber daya tersedia

Dimana :
i = 1, 2, …m
j = 1, 2,…n
 SOLUSI

Solusi layak (feasible solution) :

solusi yang memenuhi seluruh
fungsi kendala pada masalah LP
Solusi optimum : nilai terbaik bagi
fungsi tujuan yang terdapat pada
daerah solusi layak,
Umumnya hanya terdapat satu
solusi optimum
Penyelesaian
Persoalan
Contoh
Model
Program
Model manakah yang dapat diselesaikan
dengan program linier
Linier
 Tahapan Perumusan Program
Linier
Definiskan
variable keputusan
(decision variable)
Rumuskan
Variabel yang Fungsi Tujuan Rumuskan
nilainya akan Fungsi Kendala
dicari Maksimasi atau Sumberdaya
Minimasi Tetapkan kendala non-
Tentukan kebutuhan negative
Tentukan koefisien
sumberdaya untuk
dari variable masing-masing Setiap kepuusan
keputusan peubah keputusan (kuntitatif) yang
Tentukan jumlah diambil tidak
ketersediaan boleh mempunyai
sumberdaya sebagai nilai negatif
pembatas
Beberapa konsep penting Extre Titik-titik sudut
dalam penyelesaian me daerah kelayakan
(feasible region)
persoalan program linier points

Terjadi karena
Redu adanya kendala Infeasi
Tidak ada solusi
yang tidak ble
ndan mempengaruhi solutio
karena tidak semu
kendala terpenuhi
cy daerah
kelayakan
n

Solusi yang Solusi yang

tidak Unbou disebabkan karena
memberikan nded fungsi tujuan dibuat
Altern nilai yang unik, solutio tanpa batas dan tida
ative terjadi bila garis n melanggar fungsi
fungsi tujuan kendala
optima berimpit
dengan salah
satu kendala
Konsep Penyelesaian Persoalan
Program Linier
 Studi Kasus
Konsultan perumahan rakyat memiliki dua alternatif konsep
praktis pembangunan jembatan yaitu girder bridge dan
truss bridge yang diproses melalui dua bagian fungsi
diantaranya Oprit dan Railing.
Pada Bagian Oprit tersedia 60 jam kerja sedangkan pada
bagian Railing 48 jam kerja.
Untuk menghasilkan 1 girder bridge diperlukan 4 jam kerja
Oprit dan 2 jam kerja Railing,
sedangkan untuk menghasilkan 1 truss bridge diperlukan 2
jam kerja Oprit dan 4 jam kerja Railing.
Laba untuk setiap girder bridge dan truss bridge yang
dihasilkan masing-masing Rp800.000 dan 600.000.
Berapa jumlah girder bridge dan truss bridge yang optimal
dihasilkan pada wilayah perumahan rakyat tersebut?
 Perumusan Persoalan Model Program
Linier
Keputusan yang akan diambil adalah berapakah jumlah girder bridge dan truss bridge yang akan
Definisi dihasilkan.
Perumusan
Jika girder bridge disimbolkan dengan M dan truss bridge dengan K, maka definisi variable
variable Fungsi
keputusan:
keputusan
M = jumlah Tujuan
girder bridge yang akan dihasilkan dalam satuan unit)
K = jumlah truss bridge yang akan dihasilkan (dalam satuan unit)

Laba untuk setiap girder bridge dan truss bridge yang dihasilkan masing-masing Rp800.000 dan
Rp600.000.
Tujuan konsultan untuk memaksimumkan laba dari sejumlah girder bridge dan truss bridge yang
dihasilkan. Demikian, fungsi tujuan dapat ditentukan:
Maksimasi: Laba = 8M + 6K (dalam satuan Rp100.000)
 Perumusan Persoalan Model Program
Linier
Kendala Proses Oprit Kendala Proses Railing
Untuk menghasilkan 1 girder bridge Untuk menghasilkan 1 girder bridge
Perumusan
diperlukan 4 jam kerja. diperlukan 2 jam kerja,
Fungsi Kendala
untuk menghasilkan 1 truss bridge diperlukan Untuk menghasilkan 1 truss bridge
diperlukan 4 jam kerja.
2 jam kerja. Waktu yang tersedia 48 jam kerja
Waktu yang tersedia 60 jam kerja 2M + 4K ≤ 48
4M + 2K ≤ 60

Kendala Non-negatif
girder bridge dan truss bridge yang
dihasilkan tidak memiliki nilai negatif
M≥0
K≥0
Penyelesaian
Perumusan persoalan dalam bentuk tabel
Proses Waktu yang dibutuhkan per Total jam
unit tersedia
girder bridge truss bridge (K)
(M)
Oprit 4 2 60
Railing 2 4 48
Laba per unit
Perumusan 800.000 600.000bentuk matematika
persoalan dalam
(Rp)
Maksimasi: Laba = 8M + 6K (dalam satuan Rp100.000)
Dengan kendala:
4M + 2K ≤ 60
2M + 4K ≤ 48
M≥0
K≥0
Penyelesaian Grafik
Gambarkan masing-masing fungsi
kendala pada grafik yang sama.

Rp13.200.000