LINEAR PROGRAMMING

Dr. Drs. I Made Jiwa Astika, [Link]

Agenda Style
01 Defenisi Linear Programming

02 Fungsi Linear Programming

03 Model Linear Programming

04 Asumsi Linear Programming

 Liner Programming

Linear programming merupakan suatu model

umum yang dapat digunakan untuk memec-
ahkan masalah pengalokasian sumber-sum-
ber yang terbatas secara optimal.
Linear Programming teknik khusus yang
dapat diterapkan pada berbagai masalah
managemen seperti iklan, distribusi,
investasi, dan produksi. The linear
programming tidak hanya berguna dalam
industri dan bisnis tapi juga pada sektor
non profit seperti Education, Government,
Hospital, and Libraries.
 Fungsi Tujuan Fungsi Batasan

Fungsi tujuan merupakan Fungsi batasan merupakan

Fungsi
fungsi yang menggam- batasan matematis kapa- dalam
barkan tujuan/sasaran di sitas yang tersedia untuk
dalam permasalahan liniear dialokasikan secara optimal. Linear
programming yang berkai-
tan dengan pengaturan Pro-
sumber daya secara optimal
untuk memperoleh keun-
gram-
tungan maksimal atau biaya ming
minimal.
Permasalahan yang berhubungan dengan program
linear selalu berhubungan dengan fungsi objektif
(fungsi tujuan) berdasarkan kondisi-kondisi yang
membatasinya. Dalam hal ini, optimasinya berupa
memaksimalkan atau meminimalkan fungsi objektif.
program linear biasanya berbentuk sistem pertidak-
samaan linear. Sistem pertidaksamaan linear meng-
gunakan tanda ketidaksamaan berupa
(<), (>), (≤), (≥).
Secara umum, program linear terdiri dari dua bagian, yaitu
fungsi objektif (fungsi tujuan) dan fungsi kendala.
1. Fungsi Objektif (Fungsi Tujuan)
Fungsi objektif adalah fungsi yang nilainya akan diop-
timalkan. Fungsi objektif bisa bernilai maksimum atau
minimum. Hal ini tergantung pada kasusnya.
Jika fungsi objektif biaya produksi, nilainya dicari yang
minimum. Namun, kalau fungsi objektif berupa keun-
tungan, nilainya dicari yang maksimum.
Bentuk umum fungsi tujuan adalah maksimum atau
minimum
f(x, y) = px + qy, dengan p dan q adalah konstanta.
Model Linear Programming
Bentuk dasar linear programming:
1. Fungsi tujuan :
Maksimumkan atau minimumkan Z =+ + ... +

2. Batasan-batasan :
+ + ... + = / ≥ / ≤
+ +…+ =/≥/≤
+ +…+ =/≥/≤
, ≥0
2. Fungsi Kendala
Fungsi kendala adalah batasan-batasan yang harus
dipenuhi oleh peubah yang terdapat dalam fungsi objektif.
Bentuk umum dari fungsi kendala adalah sebagai berikut.
ax + by ≤ m atau ax + by ≥ m
cx + dy ≤ n atau cx + dy ≥ n
x ≥ 0 ; y ≥ o atau x ≥ 0 ; y ≥ o
Berikut karakteristik program linear.
Program linear dapat mengatasi permasalahan dengan
kendala-kenalanya dalam bentuk pertidaksamaan.
Program linear dapat mengatasi jumlah kendala yang
banyak.
Program linear hanya terbatas pada fungsi objektif dan
kendala linear.
Penerapan Program Linear dengan Model Matematika
Beberapa masalah mengoptimalkan yang terjadi dalam
kehidupan sehari-hari dapat diselesaikan menggunakan
program linear, dengan kendala atau batasan-batasan
yang harus diterjemahkan
ke dalam sistem pertidaksamaan linear.
Untuk menerjemahkannya digunakan model matem-
atika, yakni uraian secara matematika (sering kali
menggunakan fungsi atau persamaan) dari fenomena
dunia nyata.
Langkah-langkah menuliskan persoalan sehari-hari ke
dalam model matematika adalah sebagai berikut.
1. Tuliskan ketentuan-ketentuan yang ada ke dalam
sebuah tabel.
2. Buat permisalan untuk objek-objek yang belum
diketahui dalam bentuk variabel x dan y.
3. Buat sistem pertidaksamaan linear dari hal-hal
yang sudah diketahui.
4. Tentukan fungsi objektif.
5. Selesaikan model matematika tersebut untuk men-
dapatkan nilai optimum dari fungsi objektif.
Model matematika terdiri atas dua bagian, yaitu:
Fungsi objektif, yakni f(x, y) = px + qy
Syarat atau batasan yang berisikan kendala-kendala
yang harus dipenuhi oleh variabel x dan y
Nilai optimum fungsi objektif adalah nilai maksimum
atau minimum fungsi objektif sebagai hasil dari sub-
stitusi titik-titik ekstrem terhadap fungsi linear f(x, y) =
px + qy, penjabarannya sebagai berikut.
1. Nilai Maksimum Fungsi Objektif
Nilai maksimum f(x, y) = px + qy
dengan kendala:
ax + by ≤ m
cx + dy ≤ n
x≥0;y≥o
2. Nilai Minimum Fungsi Objektif
Nilai minimum f(x, y) = px + qy dengan
kendala:
ax + by ≥ m
cx + dy ≥ n
x≥0;y≥o
Contoh Soal Model Matematika

Seorang penjahit pakaian mempunyai persediaan 16 meter kain sutera, 15 meter

katun, dan 11 meter kain wool yang akan dibuat dua model pakaian dengan per-
incian sebagai berikut.
1. Model A membutuhkan 2 m sutera, 1 m wool, dan 1 m katun per unit.
2. Model B membutuhkan 1 m suteral, 2 m wool, dan 3 m katun per unit.
Keuntungan pakaian model A Rp3.000,00 per unit dan keuntungan pakaian model
B Rp5.000,00 per unit.
Tentukan berapa banyak masing-masing pakaian harus dibuat agar didapat keun-
tungan yang sebesar-besarnya.
Jawab:
Permasalahan di atas dapat disajikan dalam tabel
berikut.
Misalnya, jumlah model A yang dibuat adalah x unit,
dan jumlah model B yang dibuat adalah y unit.
Permasalahan ini merupakan maksimalisasi keuntun-
gan, yaitu:
f(x, y) = 3.000x + 5.000y
dengan kendala:
2x + y ≤ 16
x + 2y ≤ 11
x + 3y ≤ 15
x ≥ 0; y ≥ 0
Daerah penyelesaian dari kendala permasalahan
tersebut ditunjukkan oleh gambar berikut.
 2x +y =16 x1..... 2x +y =16 x1

x + 2y = 11 x2... 2x + 4y = 22
0 - 3y = -6
1
y=2

2x +2 =16
x + 2y = 11 x2 2 2x = 16-2
3 2x = 14
x=7

2 x,y
(7, 2)
x +2. 4=11
7
x = 11-8
x=3
 A(8, 0) titik potong garis 2x + y = 16 dengan
sumbu X
 B(7, 2) titik potong garis 2x + y = 16 dengan garis
x + 2y = 11
 C(3, 4) titik potong garis x + 2y = 11 dengan garis
x + 3y = 15
 D(0, 5) titik potong garis x + 3y = 15 dengan
sumbu Y
ADVERTISEMENT

Lakukan pengujian titik-titik ekstrem tersebut pada

fungsi objektif f(x, y) = 3.000x + 5.000y dan diper-
oleh:
 f(A) = f(8, 0) = 3.000(8) + 5.000(0) = 24.000
 f(B) = f(7, 2) = 3.000(7) + 5.000(2) = 31.000
 f(C) = f(3, 4) = 3.000(3) + 5.000(4) = 29.000
 f(D) = f(0, 5) = 3.000(0) + 5.000(5) = 25.000
Dari hasil substitusi titik ekstrem tersebut, diperoleh
 Metode Program Linear

1. Metode Grafik 2. Metode Matematik

Metode grafik digunakan

untuk menyelesaikan
permasalahan jika
hanya terdapat dua vari-
abel keputusan. Programmer
Merumuskan Masalah Linear Programming
Sebuah perusahaan Furniture yang akan membuat meja dan kursi.
Keuntungan yang diperoleh dari satu unit meja adalah Rp 70.000,-
sedangkian keuntungan yang diperoleh dari satu unit kursi adalah
Rp. 50.000,-. Namun untuk meraih keuntungan tersebut Perusahaan
menghadapi kendala keterbatasan jam kerja. Untuk pembuatan 1 unit
meja memerlukan 4 jam kerja. Untuk pembuatan 1 unit kursi
membutuhkan 3 jam kerja. Untuk pengecatan 1 unit meja dibutuhkan 2
jam kerja, dan untuk pengecatan 1 unit kursi dibutuhkan 1 jam kerja-
Jumlah jam kerja yang tersedia untuk pembuatan meja dan kursi
adalah 240 jam per minggu sedang jumlah jam kerja untuk pengecatan
adalah 100 jam per minggu. Berapa jumlah meja dan kursi yang se-
baiknya diproduksi agar keuntungan perusahaan maksimum ?
 1. Fungsi Tujuan
P = (Rp. 70.000 x jumlah meja + Rp. 50.000 x jumlah kursi) yang diproduksi
atau secara matematis dapat dituliskan :
Maksimumkan Z = 70.000 X1 + 50.000 X2
2. Fungsi kendala :
4 X1 + 3 X2 ≤ 240 (kendala departemen pembuatan)
2X1 + 1 X2 ≤ 100 (kendala departemen pengecatan)
X1, X2 ≥ 0 (kendala non negatif pertama)
Salah satu syarat yang harus dipenuhi dalam Linear Programming adalah asumsi nilai X1
dan X2 tidak negatif. Artinya bahwa X1 ≤ 0 (jumlah meja yang diproduksi adalah lebih
besar atau sama dengan nol) . X2 ≤ 0 (jumlah kursi yang diproduksi adalah lebih besar
atau sama dengan nol)
Diselesaikan dengan grafik Titik potong kedua kendala dapat diselesaikan
dengan substitusi atau eliminasi

2 X1 + X2 = 100
X2 = 100 - 2 X1
4 X1 + 3 X2 = 240
4 X1 + 3 (100 - 2 X1) = 240
4 X1 + 300 - 6 X1 = 240
- 2 X1 = 240 - 300
= - 60
X1 = -60/-2 = 30.
X2 = 100 - 2 X1
X2 = 100 - 2 * 30
= 100 - 60
= 40
Feasible region (area layak) meliputi daerah
sebelah kiri dari titik A (0; 80), B (30; 40),
dan C (60; 0)

Kedua kendala akan saling berpotongan

pada titik (30, 40).
Menentukan solusi yang optimal, ada dua cara yang bisa digunakan yaitu :
1. dengan menggunakan garis profit (iso profit line)
Penyelesaian dengan menggunakan garis profit adalah penyelesaian dengan
menggambarkan fungsi tujuan. Kemudian fungsi tujuan tersebut digeser ke
kanan sampai menyinggung titik terjauh dari dari titik nol, tetapi masih berada
pada area layak (feasible region).

Garis isoprofit dari Z = 70000X1 + 50000X2

70000X1 + 50000X2 = 3500000

Disederhanakan : 7X1 + 5X2 = 35
Maka garis iso profit jadi (0, 70) dan (50, 0)

Iso-profit line adalah garis dimana disetiap titik pada garis tersebut
memiliki keuntungan yang sama.
2. dengan titik sudut (corner point)
Penyelesaian dengan menggunakan titik sudut (corner point) artinya Harus
mencari nilai tertinggi dari titik-titik yang berada pada area layak (feasible
region). Dapat dilihat bahwa ada 4 titik yang membatasi area layak, yaitu titik
0 (0,0), A (0, 80), B (30, 40), dan C (50, 0).
Keuntungan pada titik O (0, 0) = (70.000 x0) + (50.000 x 0) = 0.
Keuntungan pada titik A (0; 80) = (70.000 x 0) + (50.000 x 80) = 4.000.000
Keuntungan pada titik B (30; 40) = (70.000 x 30) + (50.000 x 40) =4.100.000.
Keuntungan pada titik C (50; 0) = (70.000 x 50) + (50.000 x 0) = 3.500.000.

Karena keuntungan tertinggi jatuh pada titik B, maka sebaiknya

perusahaan memproduksi meja sebanyak 30 unit dan kursi sebanyak
40 unit, dan perusahaan memperoleh keuntungan optimal sebesar
4.100.000.
 Masalah Minimalisasi

Min Z = 5X + 7Y
X + 3Y ≥ 6
5X + 2Y ≥ 10
Y≥4
X, Y ≥ 0

Hitung Min Z?
Thank you
 TUGAS!!
1. Suatu perusahaan obat nyamuk memproduksi 2 macam obat pembunuh nyamuk cair,yaitu jenis “su-
per” dan jenis “biasa”. Keduanya dibuat dari bahan dasar yang sama, yaitu cairan A dan B, namun
dengan komposisi yang berbeda . Untuk membuat 1 liter obat nyamuk super dibutuhkan 10 cc bahan A
dan 4 cc bahan B,sedangkan 1 liter obat nyamuk biasa membutuhkan 2 cc bahan A dan 2 cc bahan B.
Penjualan tiap liter obat nyamuk super memberikan keuntungan sebesar Rp 5000, sedangkan jenis bi-
asa sebesar Rp 2000. Perusahaan tersebut ingin membuat sebanyak-banyaknya, namun ia memiliki
keterbatasan dalam hal penyediaan bahan baku. Tiap minggu ia hanya mampu menyediakan 100 cc
bahan A dan 50 cc bahan [Link] jumlah obat yang harus dibuat (dengan kendala yang ada) agar
keuntungan yang didapatkannya maksimum !

2. min z 50x1 + 100x2

Constrain:
7X1 + 2X2 ≥ 28
2X1 + 12X2 ≥ 24
X1 , X2 ≥ 0
3. Farmer Jane owns 45 acres of land. She is going to plant each with wheat or corn. Each acre planted
with wheat yields $200 profit; each with corn yields $300 profit. The labor and fertilizer used for each
acre are given in Table 1. One hundred workers and 120 tons of fertilizer are available. Use linear pro-
gramming to determine how Jane can maximize profits from her land.

Wheat Corn
Labor 3 workers 2 workers
Fertilizer 2 tons 4 tons

4. Furnco manufactures desks and chairs. Each desk uses 4 units of wood, and each chair 3.
A desk contributes $40 to profit, and a chair contributes $25. Marketing restrictions require
that the number of chairs produced be at least twice the number of desks produced. If 20
units of wood are available, formulate an LP to maximize Furnco’s profit. Then graphically
solve the LP.