Linier Programming
Merupakan model matematika yang Suatu teknis matematika yang
digunakan untuk menyelesaikan dirancang untuk merencanakan
masalah optimisasi, yaitu dan membuat keputusan dalam
Program Linier – memaksimumkan atau mengalokasikan sumber daya yang
meminimumkan fungsi tujuan yang terbatas untuk mencapai tujuan
bergantung pada sejumlah variabel perusahaan
Metode Grafik input dengan memperhatikan
berbagai keterbatasan (kendala)
dalam sumber daya
Dr. Sri Sarjana
Hal terpenting yang perlu kita lakukan adalah mencari tahu tujuan
penyelesaian masalah dan apa penyebab masalah tersebut.
1Fungsi Program Linear
Tujuan • Fungsi tujuan : Menggambarkan
tujuan/sasaran berkaitan dengan
! Memaksimumkan Keuntungan pengalokasian sumber daya secara
(maximum profit) optimal, untuk memperoleh keuntungan
! Meminimumkan biaya (minimum maksimal
cost) • Fungsi kendala/batasan : Bentuk
penyajian matematis batasan-batasan
kapasitas yang tersedia yang akan
dialokasikan secara optimal dalam
berbagai kegiatan
3
Data Model Linier Programming
Pemakaian Sumber Per Unit Kapasitas
Karakteristik Program Linier: Kegiatan Kegiatan (Keluaran) Sumber
± Ada tujuan yang ingin dicapai (Fungsi Tujuan) à Harus Sumber 1 2 3 ..................... n
“ Fungsi Linier
± Tersedia beberapa alternatif untuk mencapai tujuan
1
2
3
a11
a21
a31
a12
a22
a32
a13 ..................... a1n
a23 ..................... a2n
a33 ..................... a3n
b1
b2
b3
± Sumberdaya dalam keadaan terbatas (Fungsi Kendala) .
.
.
.
.
.
.
.
.
.
.
.
à Harus Fungsi Linier . . . . . .
± Dapat dirumuskan dalam bentuk matematika m am1 am2 a13 .................... anm bm
ΔZ pertambahan C1 C2 C3 ..................... Cn
(persamaan/ketidaksamaan) tiap unit
Tingkat X1 X2 X3 ..................... Xn
Kegiatan
5 6
Fungsi Tujuan
Maksimum Z = C1X1 + C2X2 + C3X3 ........CnXn
Ciri-ciri Linier Programming
Fungsi Kendala/Batasan
v Penyelesaian masalah mengarah pada pencapaian tujuan
1) a11X1 + a12X2 + a13X3 ..........+ a1nXn ≤ b1 maksimisasi atau minimisasi.
2) a21X1 + a22X2 + a23X3 ..........+ a2nXn ≤ b2
. Fungsi Batasan Fungsional v Kendala yang ada membatasi tingkat pencapaian tujuan
. v Ada beberapa alternatif penyelesaian
.
m) am1X1 + am2X2 + am3X3 .........+ amnXn ≤ bn v Hubungan matematis bersifat linear
dan
X1 ≥ 0, X2 ≥ 0, .......... Xn ≥ 0, Fungsi Batasan Non negatif
7 8
Langkah-langkah Perumusan
Linier Programming
Pendekatan Linier Programming
'HILQLVLNDQ 9DULDEHO .HSXWXVDQ
R9DULDEHO\DQJQLODLQ\DDNDQGLFDUL
Metode Grafik Metode Simpleks
5XPXVNDQ )XQJVL 7XMXDQ
R0DNVLPLVDVLDWDX0LQLPLVDVL Digunakan Digunakan
R7HQWXNDQNRHILVLHQGDULYDULDEHONHSXWXVDQ untuk untuk
menyelesaikan menyelesaikan
permasalahan permasalahan
5XPXVNDQ )XQJVL .HQGDOD 6XPEHUGD\D
dimana variabel dimana variabel
R7HQWXNDQNHEXWXKDQVXPEHUGD\DXWNPDVLQJPDVLQJNHSXWXVDQ
keputusan sama keputusan dua
R7HQWXNDQMXPODKNHWHUVHGLDDQVXPEHUGD\DVEJSHPEDWDV
dengan dua atau lebih
7HWDSNDQ NHQGDOD QRQQHJDWLI
R6HWLDSNHSXWXVDQ\DQJGLDPELO WLGDNEROHKPHPSXQ\DLQLODLQHJDWLI
9 10
Contoh Kasus
Jati Furniture merupakan perusahaan furniture yang
memiliki spesialisasi dalam pembuatan meja dan kursi.
Namun Jati Furniture menghadapi kendala keterbatasan
jam kerja guna mendapatkan keuntungan. Perlu waktu 4
jam kerja untuk membuat 1 unit meja, sedang untuk
membuat 1 unit kursi membutuhkan 3 jam kerja. Selain itu,
METODE diperlukan pengecatan tiap unit meja
membutuhkan waktu 2 jam kerja, sedangkan pengecatan
yang
tiap unit kursi perlu 1 jam kerja. Tersedia 240 jam kerja per
minggu untuk pembuatan meja dan kursi sedang jumlah
GRAFIK jam kerja untuk pengecatan adalah 100 jam per minggu.
Nilai keuntungan yang diperoleh tiap unit meja adalah $7,-
sedang keuntungan yang diperoleh dari tiap unit kursi
adalah $5,-. Berapa jumlah meja dan kursi yang sebaiknya
diproduksi agar keuntungan perusahaan maksimum?
11
PEMBAHASAN Fungsi Tujuan
Identifikasi Tujuan
Memaksimumkan Profit
Place your screenshot here Total Keuntungan = Keuntungan Per Unit Meja x jumlah Meja
Produk yang ($7 x X1)
Kendala yang Dihadapi
dihasilkan:
Keterbatasan waktu pembuatan +
dan pengecatan • Meja (X1) Keuntungan Per Unit Kursi x jumlah Kursi
• Kursi (X2) ($5 x X2)
Maka Fungsi Tujuan Zmax = 7X1 + 5X2
13 14
Fungsi Kendala / Batasan
Syarat Linear Programming
Alokasi waktu per produk
Kendala Pertama : q X1 ≥ 0 (jumlah meja yang diproduksi adalah lebih besar atau
Ø Untuk pembuatan 1 unit meja (X1)
ØKetersediaan waktu bagian sama dengan nol)
memerlukan 4 jam kerja. Untuk pembuatan 1
pembuatan 240 jam unit kursi (X2) membutuhkan 3 jam kerja.
q X2 ≥ 0 (jumlah kursi yang diproduksi adalah lebih besar
Kendala Kedua sehingga 4X1 + 3 X2 ≤ 240
atau sama dengan nol)
ØKetersediaan waktu bagian Ø Untuk pengecatan 1 unit meja (X1)
pengecetan 100 jam dibutuhkan 2 jam kerja, dan untuk
pengecatan 1 unit kursi (X2) dibutuhkan 1
jam kerja
sehingga 2X1 + 1X2 ≤ 100
15
Formulasi Permasalahan Grafik Fungsi Kendala 1
Fungsi tujuan :
Maksimisasi Z = $7X1 + $5X2
Kendala 1:
4 X1 + 3 X2 = 240
Fungsi kendala : memotong sumbu X1 pada saat X2 = 0
4 X1 + 0 = 240
4 X1 + 3 X2 ≤ 240 (kendala departemen pembuatan)
X1 = 240/4
2X1 + 1 X2 ≤ 100 (kendala departemen pengecatan) X1 = 60.
X1 ≥ 0 (kendala non negatif pertama) memotong sumbu X2 pada saat X1 = 0
X2 ≥ 0 (kendala non negatif kedua) 0 + 3 X2 = 240
X2 = 240/3
X2 = 80
17 18
Grafik Fungsi Kendala 2 Titik potong bisa dicari dengan cara
substitusi atau eliminasi
2 X1 + 1X2 = 100 A
X2 = 100 - 2 X1
Kendala 2:
4 X1 + 3 X2 = 240
2 X1 + 1 X2 = 100
4 X1 + 3 (100 - 2 X1) = 240
memotong sumbu X1 pada saat X2 = 0
2 X1 + 0 = 100
Menentukan 4 X1 + 300 - 6 X1 = 240
- 2 X1 = 240 - 300
X1 = 100/2
X1 = 50
Titik Potong - 2 X1 = - 60
X1 = -60/-2 = 30.
memotong sumbu X2 pada saat X1 =0
0 + X2 = 100
& Feasible X2 = 100 - 2 X1
X2 = 100 - 2 * 30
X2 = 100 - 60
X2 = 100
area X2 = 40
Sehingga saling berpotongan pada C
titik (30, 40).
Tanda ≤ pada kedua kendala ditunjukkan pada area sebelah kiri dari garis kendala.
Sebagaimana nampak pada gambar feasible area meliputi daerah sebelah kiri dari titik A
(0; 80), B (30; 40), dan C (50; 0).
19 20
Menentukan Keuntungan Optimal
Mencari nilai tertinggi dari titik-titik yang berada pada feasible area
A
Zmax = 7X1 + 5X2
.HXQWXQJDQSDGDWLWLN2 DGDODK [ [
.HXQWXQJDQSDGDWLWLN$ DGDODK [ [
.HXQWXQJDQSDGDWLWLN% DGDODK [ [
.HXQWXQJDQSDGDWLWLN& DGDODK [ [
.HXQWXQJDQWHUWLQJJLMDWXKSDGDWLWLN%PDNDVHEDLNQ\D
SHUXVDKDDQPHPSURGXNVLPHMDVHEDQ\DNXQLWGDQNXUVL
C
VHEDQ\DNXQLWGDQSHUXVDKDDQPHPSHUROHKNHXQWXQJDQ
RSWLPDOVHEHVDU
21