Programasi Linier

sunlip w 1
 Definisi

-suatu model yg dapat digunakan dlm

pemecahan masalah pengalokasian sumber
daya yang terbatas scr optimal
-Suatu metode programasi yang variabelnya
disusun dengan persamaan linear

sunlip w 2
 Aplikasinya
• Bidang marketing: pemilihan media periklanan, riset
pemasaran, dan distribusi produk
• Bidang produksi/operasi: penentuan kombinasi produk,
penjadwalan proses produksi, penjadwalan tugas karyawan,
dan lain-lain.
• Bidang keuangan: pemilihan portfolio investasi.
• Bidang ekonomi makro: pengaruh kebijakan pemerintah dan
perubahan pasar pada sektor ekonomi.
• Bidang Pertanian: perencanaan usaha tani,meminimkan biaya
makanan dalam pencampuran makanan ternak,alokasi
produksi dan distribusi yang menuju maksimisasi keuntungan
pabrik gula.
• Pada pemerintahan(Biro perencanaan Pertaniandan
[Link], Transmigrasi ) juga telah memanfaatkan
LP sbg alat bantu membuat keputusan.
• Bidang lainya:[Link],perdagangan,kesehatan dll

sunlip w 3
 Karakteristik Permasalahan
Programasi Linier
• memiliki tujuan (objective function) untuk
memaksimumkan atau meminimumkan
sesuatu (kuantitas),
• memiliki restriksi (konstrain) yang
membatasi tingkatan pencapaian tujuan
(objective function).
• Adanya beberapa alternatif tindakan yang
bisa dipilih.
sunlip w 4
 Contoh Kasus
(Render and Stair, 2000:306)

• Perusahaan menganggarkan $8.000 per minggu

untuk periklanan pada 4 media: TV, Koran,
Radio prime time, dan Radio non prime time.
Jangkauan iklan, biaya, dan batasan maksimum
periklanan pada keempat media disajikan pada
tabel berikut.

sunlip w 5
 Contoh Kasus
(Render and Stair, 2000:306)
Media Daya jangkau Biaya per Iklan
(orang) iklan ($) Maksimum
per Minggu
TV (per mnt) 5.000 800 12

Koran (per 8.500 925 5

halaman)
Radio 1 (per 2.400 190 25
30 detik)
Radio 2 (per 2.800 380 20
mnt)
sunlip w 6
metode kuantitatif
 Contoh Kasus
(Render and Stair, 2000:306)
• Perusahaan menetapkan beberapa
rancangan:
– Minimal ada 5 spot iklan di radio
– Tidak lebih dari $1.800 dana dialokasikan
pada media radio.
• Perusahaan menginginkan jangkauan
audience sebanyak-banyaknya melalui
berbagai media iklan.

sunlip w 7
 Formulasi dari
permasalahan
• Mengidentifikasi dan menotasikan variabel
keputusan
– Definisikan variabel keputusan dengan baik
• Memformulasikan fungsi tujuan
• Memformulasikan fungsi kendala
• Memasukkan kendala nonnegativitas

sunlip w 8
 Identifikasi dan Notasi Variabel
Keputusan
• ada empat variabel keputusan yang
merepresentasikan jumlah iklan pada
berbagai media:
X1 = jmlh iklan pada TV per minggu
X2 = jmlh iklan pada Koran per minggu
X3 = jmlh iklan pada Radio 1 per minggu
X4 = jmlh iklan pada Radio 2 per minggu
sunlip w 9
 Formulasi Fungsi Tujuan
• Tujuan: maksimumkan jangkauan
audience

Maks: Zj = 5.000 X1 + 8.500 X2 +

2.400 X3 + 2.800 X4

sunlip w 10
 Formulasi Fungsi Kendala
• Ada 7 fungsi kendala (apa saja ?)

X1 ≤ 12
X2 ≤ 5
X3 ≤ 25
X4 ≤ 20
800 X1 + 925 X2 + 290 X3 + 380 X4 ≤ 8.000
X3 + X4 ≥ 5
290 X3 + 380 X4 ≤ 1.800
X1, X2, X3, X4 ≥ 0
sunlip w 11
Cara penyelesaian: a) Metode Grafis
b) Metode Simpleks
Metode Grafis:
Ada dua hal dalam solution yaitu memenuhi constraint ( feasible solution),
memenuhi constraint dan objectif ( optimal solution).

Contoh 1. Suatu perusahaan memproduksi 2 barang dan diproses dalam

dua mesin,mesin 1 berkapasitas 120 jam sedang mesin II
berkapasitas 180 jam. Barang 1 diproses pada mesin I selama 6
jam dan 4 jam di mesin II,sedangkan barang 2 diproses mesin I
selama 3 jam dan 10 jam pada mesin II. Laba output untuk barang
1 Rp 45,- per unit, sedang laba output barang 2 sebesar Rp 55,-,
Berapa laba maksimum bila memproduksi kedua barang tersebut.
Jawab:

Barang Waktu Laba/unit

Mesin I Mesin II
X1 6 4 45
X2 3 10 55
Kapasitas 120 180
sunlip w 12
metode kuantitatif
Max Z = 45X1 + 55X2 Fungsi tujuan(objective Fungtion)
6X1 + 3X2 ≤ 120
4X1 + 10X2 ≤ 180 Fungsi kendala(constraint fungtion)
X1,X2 ≥ 0

6X1 + 3X2 ≤ 120 6X1 + 3X2 = 120 1)

4X1 + 10X2 ≤ 180 4X1 + 10X2 = 180 2)

1) 6X1 + 3X2 = 120 , bila X1=0 3X2 = 120 X2 = 40 (0;40)

bila X2= 0 6X1 = 120 X1 = 20 (20;0)
2) 4X1 + 10X2 = 180 , bila X1 = 0 10X2 = 180 X2 = 18 (0;18)
bila X2 = 0 4X1 = 180 X1 = 45 ( 45;0)
1) x 2 12X1 + 6X2 = 240
2) X 3 12X1 + 30X2 = 540 -
-24X2= -300
X2 = 12,5

X2 = 12,5 mk 6X1 + 3(12,5) = 120 (X1;X2) = (13,75 ; 12,5)

6X1 +37,5 = 120
X1 = (120 – 37,5) / 6 = 13,75

sunlip w 13
 X2
A (0 ;18) Z = 45(0) + 55(18) = 990
(0; 40) B (13,75 ; 12,5)
C (20 ; 0)
Z = 45(13,75) + 55( 12,5) = 1306,25
Z = 45(20) + 55(0) = 900

Jadi laba maksimum sebesar 1306,25 dengan X1 diproduksi sbr 13,75

dan X2 diproduksi sbr 12,5

A(0; 18)
B(13,75 ;12,5)

C (20;0) (45; 0) X1

sunlip w 14
Latihan 1
“PT Mau Usaha” memproduksi 2 barang ,setiap unit barang I perlu bahan A 2 kg dan
bahan B 2 kg. Setiap unit barang II perlu bahan A 3 kg dan bahan B 3 kg. Bahan A
tersedia 6 ton sedang bahan B tersedia 9 ton.
Sumbangan terhadap laba setiap unitnya Rp 3,- untuk barang I dan R4,- untuk barang
II.
PT Mau Usaha berkeinginan untuk memaksimumkan laba
Pertanyaan: a). formulasikan permasalhan tsb
b). Berapa barang I dan barang II diproduksi agar diperoleh keuntungan
maksimum
c). Gambarkan .
Latihan 2: Perusahaan mebel “Nyaman” memproduksi meja dan kursi. Proses produksi keduanya
membutuhkan jam tenaga kerja di departemen pertukangan kayu dan pengecatan.
Setiap meja membutuhkan 4 dan 2 jam tenaga kerja departemen pertukangan kayu
dan
pengecatan,secara [Link] kursi membutuhkan 3 dan 1 jam tenaga kerja
departemen pertukangan kayu dan pengecatan secara berurutan. Selama periode
produksi saat ini
tersedia 240 dan 100 jam tenaga kerja didepartem pertukangan kayu dan
[Link] meja menghasilkan profit $7 dan sebuah kursi menghasilkan
keuntungan . Permasalahan perusahaan adalah untuk menentukan kemungkinan
kombinasi meja dan kursi terbaik untuk memperoleh keuntungan maksimal.
Latihan 3: Maksimumka Z = 6000 X1 + 4000 X2
2X1.+ 3X2 ≤ 24
2X1 + X2 ≤ 16
X1 + 4X2 ≤ 27
X1 dan X2 ≥0
Dengan metode grafis,sunlip
tentukan
w X1 dan X2 yang memaksimum laba 15
 Asumsi Dasar PL
• Kepastian (certainty)
• Proporsionalitas (proportionality)
• Additivitas (additivity)
• Divisibilitas (divisibility)
• Nonnegatif (nonnegativity)

sunlip w 16
 asumsi
• Kepastian:koef dlm fungsi tujuan dan kendala dpt diketahui dgn
pasti dan tidak berubah selama periode analisa.
• proporsionalitas dlm fungsi tujuan dan kendala,bahwa naik turunya
nilai Z dan penggunaan sumber yang tersedia akan berubah scr
sebanding dgn tingkat kegiatan.
• Additivity: bahwa nilai tujuan tiap kegiatan tidak saling
mempengaruhi,kenaikan nilai Z akibat kenaikan suatu kegiatan
dapat ditambahkan tanpa mempengaruhi nilai Z yang diperoleh dari
kegiatan lain.
• Divisibility: bahwa output yg dihasilkan oleh setiap kegiatan dapat
berupa bilangan pecahan misal: Z = 100.5 X1=8.4.
• Non negatif: bahwa semua variabel adalah positif

sunlip w 17
Metode Simpleks
Pendekatan grafis mudah untuk diselesaikan bila terbatas dua variabel,namun bila
lebih dari dua variabel akan kesulitan untuk menggambarkan,karena itu muncul metode simpleks.
Dalam menyelasaikan metode simpleks ada dua cara
Cara 1
langkah langkahnya sbb:
1. formulasi fs objektif dan fs kendala
2. Ubah dari pertidaksamaan menjadi persamaan
3. Tabel transaksi
4. Menentukan kolom kunci(KK), carilah selisih(Cj – Zj) terbesar
5. Menentukan baris kunci(BK) , carilah baris yg memiliki nilai ganti
terkecil(terendah) dgn jalan membagi kuantitas dengan angka
pada kolom kunci.
6. Menentukan nomor kunci (Nk) yaitu perpotongan antara KK dengan BK.
7. Transformasi baris lain,dengan jalan mengurangi angka angka pd baris ybs dengan
hasil kali antara angka angka pd BK dan ratio tetap.
ratio tetap(r) = (angka pd KK) / Nk.
Jadi Baris baru(Bb) = BL – ABK x r, dimana Bb = baris baru; BL = baris lama, ABK =
angka pada baris kunci , r = ratio tetap.
8. Uji optimalisasi, dikatakan optimal bila angka angka pd baris (Cj – Zj) sudah tidak
ada yang positif.
9. Bila belum optimal, mk ulangi langkah 4 s/d 8.

sunlip w 18
metode kuantitatif
Dari Contoh 2, bila dikerjakan dengan M simpleks

[Link]: Maks Z = 3X1 + 4X2 thd

2X1+ X2 ≤ 6000
2X1 + 3X2 ≤ 9000
X1 ;X2 ≥ 0
2. 2X1+ X2 + S1 = 6000
2X1 + 3X2 +S2 = 9000

3 Tabel 1
Program Objek Kuantitas 3 4 0 0 Cj
X1 X2 S1 S2
S1 0 6000 2 1 1 0
S2 0 9000 2 3 0 1 BK

Zj 0 0 0 0
Cj - Zj 3 4 0 0

KK

6000/1 = 6000
9000/3 = 3000 nilai ganti terendah,indikasi sbg BK
sunlip w 19
 6. Nk ,perpotongan antara KK dgn BK = 3
7. BKb = BK/ Nk 3000 2/3 1 0 1/3
rasio tetap =AKK/Nk =1/3
Transformasi baris lain
S1 : 6000 2 1 1 0
1/3x(9000 2 3 0 1) -
3000 4/3 0 1 -1/3
Tabel 2
Program Objektif Kuantitas 3 4 0 0
X1 X2 S1 S2 BK

S1 0 3000 4/3 0 1 - 1/3

X2 4 3000 2/3 1 0 1/3
Zj 8/3 4 0 4/3
Cj -Zj 1/3 0 0 -4/3

KK

3000/(4/3)= 2250, indikasi sbg baris kunci

3000/ (2/3) = 4500

sunlip w 20
 BKb = BK/Nk 2250 1 0 ¾ -1/4
r=½
Transformasi baris lain:
X2 : 3000 2/3 1 0 1/3
(½)x 3000 4/3 0 1 -4/3 -
Tabel 3 1500 0 1 -1/2 1

Prog Obj Kuantitas 3 4 0 0

X1 X2 S1 S2
X1 3 2250 1 0 ¾ -1/4
X2 4 1500 0 1 -1/2 1
Zj 3 4 ¼ 5/4
Cj - Zj 0 0 -1/4 -5/4

Krn pada baris (Cj – Zj) kususnya dibawah X1 dan X2 sdh tdk ada
yg positif mk dikatakan sudah optimal dengan nilai optimal
sebesar 2250(3) + 1500(4) = 12750, X1 diproduksi 2250 dan X2
diproduksi 1500
sunlip w 21
Metode Simpleks:
Cara 2
Langkah2 nya
1. Formulasi
2. Merubah fs tujuan ,dgn memindah ruas kanan kekiri
3. Merubah “≤” “=“ dgn menambah slack variable(S)
4. Memasukan dalam tabel
5. Pilih kolom kunci(KK), yaitu kolom pd baris Z yang nilainya paling
negatif.
6. Pilih baris kunci(BK),yaitu baris yang mempunyai indeks positif
terkecil. Indeks baris = ( nilai kanan =nk) / (nilai pd KK)
6a. Tentukan Angka Kunci(AK) ,perpot KK dgn BK
7. Merubah BK menjadi BKB(baris kunci baru) dgn jalan membagi BK
dgn AK BKB=( BK) / (AK)
8. Transformasi baris lain dgn jalan NBB = NBL – KKKx(BKB)
9. Uji optimalisasi, bila pd baris Z sudah tidak ada nilai negatif berarti
optimal.
10. Bila masih ada nilai negatif, belum optimal mk ulangi 5 s/ d 9
Ctt: KKK= koef kolom kunci,AK = Angka Kunci, NBB= nilai baris baru,
NBL= nilai baris lama

sunlip w 22
metode kuantitatif
Max Z = 3X1 + 4X2 - max Z - 3X1 -4X2 =0
2X1+ X2 ≤ 6000 2X1+ X2 +S1 = 6000
2X1 + 3X2 ≤ 9000 2X1 + 3X2 +S2 = 9000
KK

VD Z X1 X2 S1 S2 NK
Z 1 -3 -4 0 0 0
S1 0 2 1 1 0 6000
KK S2 0 2 3 0 1 9000 BK

Z 1 - 1/3 0 0 4/3 12000

S1 0 4/3 0 1 - 1/3 3000 BK

X2 0 2/3 1 0 1/3 3000

Z 1 0 0 ¼ 5/4 12750
X1 0 1 0 3/4 -¼ 2250
X2 0 0 1 -1/2 2/3 1500

sunlip w 23
Prosedurnya:
BKB 2/3 1 0 1/3 3000
Transformasi:
Z -3 - 4 0 0 0
- (-4) 2/3 1 0 1/3 3000
-1/3 0 0 4/3 12000

S1 2 1 1 0 6000

-(1) 2/3 1 0 1/3 3000

4/3 0 1 -1/3 3000

BKB 1 0 ¾ -1/4 2250

Transformasi:
Z -1/3 0 0 4/3 12000
- (-1/3) 1 0 3/4 -1/4 2250

0 0 ¼ 5/4 12750

X2 2/3 1 0 1/3 3000

-( 2/3) 1 0 ¾ -1/4 2250

0 1 -1/2 2/3 1500

sunlip w 24
 Konsep Slack Variable, Surplus
Variable, dan Artificial Variable
Sebelum algorithma perhitungan (metode
simplek) diaplikasikan, suatu persoalan
harus memiliki initial feasible solution
(IFS).
Jika semua variabel keputusan sama dengan
nol, solusi yang feasibel harus ada.
 Untuk fungsi kendala ≤, IFS diperoleh
dengan cara menambahkan slack variable
(Si) pada fungsi kendala tersebut.
sunlip w 25
 Konsep Slack Variable, Surplus
Variable, dan Artificial Variable
Slack variable merepresentasikan
resources yang tidak terpakai
(menganggur)
Untuk fungsi kendala =, IFS diperoleh
dengan cara menambahkan artificial
variable (Ai) pada fungsi kendala tersebut.
Secara ekonomi, Ai tidak mempunyai arti

sunlip w 26
 Konsep Slack Variable, Surplus
Variable, dan Artificial Variable
Untuk fungsi kendala ≥, IFS diperoleh
dengan cara mengurangkan Surplus
variable (Si) dan menambahkan Artificial
Variable (Ai) pada fungsi kendala tersebut.

Suplus Variable adalah resources yang harus

ditambahkan pada suatu fungsi kendala.

sunlip w 27
 Interpretasi Tabel Optimal
• Solusi Optimal
• Informasi Tentang Resources
• Tingkat Substitusi
• Baris Net Profit

sunlip w 28
 Solusi Optimal
• Interpretasi dari solusi optimal berkaitan
dengan nilai variabel keputusan dan fungsi
tujuan yang optimal.

sunlip w 29
 Informasi Tentang
Resources
• Informasi tentang resources dapat
diketahui dari nilai slack variable (dan juga
surplus variable) pada tabel optimal.

sunlip w 30
 Tingkat Substitusi
• Koefisien negatif mengindikasikan
tambahan variabel kolom akan
menyebabkan variabel baris meningkat
sebesar nilai absolut koefisien tersebut;
dan
• Koefisien positif mengindikasikan
tambahan variabel kolom akan
menyebabkan variabel baris berkurang
sebesar nilai absolut koefisien tersebut.

sunlip w 31
 Baris Net Profit
• pada tabel optimal baris ini memberikan
informasi tentang shadow price atau
opportunity cost dari resources yang
dimiliki.
• Implikasi dari opportunity cost/shadow
price ini secara praktikal adalah biaya
pengadaan tambahan resources harus
tidak melebihi opportunity cost/shadow
price.

sunlip w 32
metode kuantitatif
 Contoh soal
• Perush mebel Apik memproduksi meja dan kursi,dalam
pembuatanya butuh jam tenaga kerja di bag pertukangan dan
[Link] membuat meja butuh waktu pertukangan dan
pemlituran masing-masing 4 dan 2,sedangkan untuk membuat kursi
butuh waktu 3 dan 1 jam tenaga kerja di bag pertukangan dan
[Link] periode tsb kapasitas yang tersedia 240 dan 100
jam tenaga kerja pertukangan dan [Link] meja
menghasilkan profit $7 dan $5 untuk [Link] perush tsb
memperoleh keuntungan maximum buatlah kombinasi meja dan
kursi yang harus diproduksi

sunlip w 33
 penyelesaikan
• X1 = jlh meja yang akan diproduksi,X2 = jlh kursi yang akan
diproduki.
• Max Z = 7X1 +5X2.
• 4X1 + 3X2 ≤ 240 dan 2X1 + X2 ≤100 ;X1 . X2 ≥0

sunlip w 34
 penyelesaikan
• X1 = jlh meja yang akan diproduksi,X2 = jlh kursi yang akan
diproduki.
• Max Z = 7X1 +5X2.
• 4X1 + 3X2 ≤ 240 dan 2X1 + X2 ≤ 100 X1dan X2 ≥ 0

sunlip w 35
 Soal/latihan 1
• Perus atap memproduksi 3 jenis A B dan C,ketiga jenis atap ini
menggunakan bahan mentah yang [Link] produksi dilakukan
dgn alat yang sudah [Link] tiga bagian dalam proses produksi
yaitu [Link], [Link] dan bagian pengeringan dgn alokasi waktu
sbb.(dalam menit)
Bagian
Jenis atap

A B C
Cetak
10.7 5 2
Press
5.4 10 4
Pengeringan
0.7 1 2

sunlip w 36
 Mesin-mesin pada setiap bagian dapat bekerja selama:

2700(Cetak);2210 menit(press) dan 445 menit(pengeringan)

• Setelah dijual masing-masing memberikan

kontribusi sebesar Rp100,-untuk A,
Rp150.- untuk B dan Rp.200,- untuk C.
• Bila perush ingin memaksimumkan
keuntungan,berapa masing-masing harus
diproduksi? Berikan keterangan
seperlunya

sunlip w 37
 Identifikasi/fomulasi
• Max Z = 100X1 +150X2 +200X3
• 10.7 X1 + 5X2 + 2 X3 ≤ 2705
• 5.4 X1 +10 X2 + 4 X3 ≤ 2210
• 0.7 X1 + X2 +2 X3 ≤ 445

sunlip w 38
 Soal/latihan 2
Pendapatan bersih tiap Ha(Rp24 000)untuk jA dan
Rp 16000 untuk jB
Input Yang Banyak input yg diperlukan untuk tiap ha
tersedi usahatani
a jenis A jenis B
Tanah(Ha) 35 1 1

Modal(Rp) 480 16 8

Tenaga 800 10 24
kerja(org/hr)

sunlip w 39
 Langkah langkah operasional
QM
• Kondisikan pd QM pilih Module,dan pilih program yg sesuai misal linear programing
• Pilih File: New (baru) dan Open (sdh tersimpan)
• Title:.... Isi misal latihan ,coba dll
No of Constraints .... , No of Variables ....
Objektive Max / Min Ok
Data table
Solve
Window
- Linear Programing Results
- Ringing
- Solution List
- Iterations
- Graph

sunlip w 40