LINEAR PROGRAMMING DENGAN

METODE GRAFIK

Keti Purnamasari, S.E.,M.si

 Pengertian Linear Programming

Program linier merupakan model matematik untuk

mendapatkan alternatif penggunaan terbaik atas
sumber-sumber organisasi. Program linier adalah
suatu teknik perencanaan yang bersifat analitis yang
analitisnya menggunakan model matematis, dengan
tujuan menemukan beberapa kombinasi alternatif
pemecahan optimum terhadap persoalan.
 Simbol-Simbol dalam
Model/Persamaan dalam LP

I =nomor dari sumber daya

j = nomor aktivitas
m =banyaknya sumber
n =banyaknya aktivitas
aij =kebutuhan setiap unit aktivitas j akan sumber I
bi =banyaknya sumber I yang tersedia
Cj =manfaat yang diperoleh oelh setiap unit aktivitas
Xj =ukuran (unit) aktivitas
Z =fungsi tujuan
 Terminologi Umum untuk LP

1. Fungsi Tujuan, bisa memaksimumkan atau meninimumkan

Z=c1X1+c2X2+…..+cnXn

2. Fungsi Batasan/Kendala/Constraint
• Batasan Fungsional, menunjukkan alokasi yang tersedia
am1X1+am2X2+am3X3+….. +amnXn bm
• Batasan Nonnegatif, hasil tidak boleh negatif
X10 ; X20
 PEMECAHAN PERSOALAN PROGRAM
LINIER DENGAN MENGGUNAKAN
METODE GRAFIK
Gambarkan sebuah bidang koordinat dengan kedua variabel
sebagai sumbu-sumbu koordinat.
Gambarkan garis-garis fungsi batasan dengan menganggap
batasannya sebagai persamaan.
Tentukan daerah dalam bidang koordinat yang memenuhi semua
batasan, daerah ini disebut sebagai daerah layak (feasible region).
Tentukan koordinat titik sudut (disebut sebagai titik ekstrim).

Hitung harga fungsi tujuan untuk semua titik sudut, kemudian

pilih harga yang optimal sebagai pemecahan persoalan.
Persiapan menggambar
 Menggambar Garis dari Suatu
Fungsi
Gambar garis untuk Gambar garis untuk
Fungsi 5X1+8X240
Tujuan : 8X1+8X2100
8X1+8X2=100 5X1+8X2=40
Maks Jika X1=0, maka
Z=3X1+7X2 Jika X1=0, maka
8X1+8X2=100 5X1+8X2=40
Kendala : 5(0)+8X2=40
8X1+8X2100 8(0)+8X2=100
X2=12,5 X2=5
5X1+8X2 40 Maka titik koordinat (0,5)
X1,X2 0 Maka titik koordinat (0, 12,5)

Jika X2=0, maka Jika X2=0, maka

8X1+8X2=100 5X1+8X2=40

8X1+8(0)=100 5X1+8(0)=40
X1=12,5 X1=8
Maka titik koordinat (12,5, 0) Maka titik koordinat (8,0)
Menggambar Garis dari
Suatu Fungsi
 Mencari Titik Potong antara Dua
Garis
• Titik A (0,0) : Z = 3(0) + 7(0) = 0
• Titik B (0,5) : Z = 3(0) + 7(5) = 35
• Titik C (8,0) : Z = 3(8) + 7(0) = 24
Ternyata titik yang menghasilkan laba terbesar
adalah B = 35 dengan X1=0 dan X2=35
 Contoh Soal:

Galiyours merupakan sebuah perusahaan konveksi yang

memproduksi pakaian wanita yaitu gamis dan tunik. Produk
ini harus diproses melalui penjahitan dan finishing
(pemasangan pernak-pernik). Fungsi proses penjahitan
memiliki 60 jam kerja dan fungsi proses finishing memiliki 48
jam kerja. Untuk menghasilkan satu gamis dibutuhkan
masing-masing 4 jam dan 2 jam untuk penjahitan dan
finishing, sedang satu tunik membutuhkan masing-masing 2
jam dan 4jam untuk penjahitan dan finishing. Laba untuk tiap
gamis $8 dan tiap tunik $6. Tentukan kombinasi terbaik dari
jumlah gamis dan tunik yang harus diproduksi agar
menghasilkan laba maksimal !
 Informasi Produksi Galiyours
Kegiatan Waktu yang dibutuhkan x = jumlah gamis yang
untuk satu unit produk dibuat
(jam) Total
jam y = jumlah tunik yang
Gamis Tunik tersedia dibuat
Z = jumlah kontribusi
laba seluruh gamis
Penjahitan 4 2 60
dan tunik
Finishing 2 4 48
Laba/Unit $8 $6
Model program liniernya adalah :
Maksimumkan laba : Z= 8x + 6y
Dengan batasan :
4x + 2y  60  Fungsi batasan proses penjahitan
2x + 4y  48  Fungsi batasan proses finishing
 Menggambar Garis dari Suatu Fungsi

Gambar garis untuk 4X+2Y=60 Gambar garis untuk 2X+4Y=48

4X+2Y=60 2X+4Y=48
Jika X=0, maka 4X+2Y=60 Jika X=0, maka 2X+4Y=48
0+2Y=60 0+4Y=48
Y=30 Y=12
Maka titik koordinat (0,30) Maka titik koordinat (0,12)

Jika Y=0, maka 4X+2Y=60 Jika Y=0, maka 2X+4Y=48

4X+0=60 2X+0=48
X=15 X=24
Maka titik koordinat (15,0) Maka titik koordinat (24,0)
Menggambar Garis dari Suatu Fungsi

F
Mencari Titik Potong antara Dua Garis
Dari grafik di atas titik sudut yang diketahui adalah A, E,
dan C sedangkan titik sudut D dapat dicari dengan
eliminasi antara persamaan 1 dan 2, yaitu :
4x + 2y = 60 x 2  8x + 4y = 120
2x + 4y = 48 x 1  2x + 4y = 48 -
6x = 72, maka x = 12

Substitusikan x = 12 ke dalam persamaan kedua:

2x + 4y = 48
4y = 24
y=6

Titik F (6,12)
 PENYELESAIAN :
Langkah berikutnya, hitung nilai empat titik sudut dengan
cara mensubstitusikan ke dalam fungsi tujuan untuk
melihat kombinasi mana yang menghasilkan laba
terbesar
Titik A (0,0) : Z = 8(0) + 6(0) = 0
Titik D (0,12) : Z = 8(0) + 6(12) = 72
Titik C (15,0) : Z = 8 (15) + 6(0) = 120
Titik D (12,6) : Z = 8(12) + 6(6) = 132
Ternyata titik yang menghasilkan laba terbesar adalah D=
$132. Jadi, untuk menghasilkan laba terbesar perusahaan
harus membuat gamis sebanyak 12 buah dan tunik
sebanyak 6 buah.

15
 Tes Formatif 1

Ikan Kopra
Produksi 1.500.000 1.200.000 180.000.000
Pemasaran 1.800.000 1.800.000 225.000.000
Tambahan Ekspor 20.000.000 17.500.000

Fungsi Tujuan : Maksimumkan 200X1+175X2

Batasan :
15X1+12X21.800
18X1+18X22.250
 Menggambar Garis dari Suatu
Fungsi

15X1+12X2=1.800 18X1+18X2=2.250
Jika X1=0, maka 15X1+12X2=1.800 Jika X1=0, maka 18X1+18X2=2.250
15(0)+12X2=1.800 18(0)+18X2=2.250
X2=150 X2=125
Maka titik koordinat (0, 150) Maka titik koordinat (0, 125)

Jika X2=0, maka 15X1+12X2=1.800 Jika X2=0, maka 18X1+18X2=2.250

15X1+12(0)=1.800 18X1+18(0)=2.250
X1=120 X1=125
Maka titik koordinat (120, 0) Maka titik koordinat (125, 0)
Menggambar Garis dari
Suatu Fungsi
Mencari Titik Potong antara Dua Garis
15X1+12X2=1.800 dikali 18
18X1+18X2=2.250 dikali 15

270X1+216X2=32.400
270X1+270X2=33.750 -
-54 X2 = -1.350
X2 = 25

15X1+12X2=1.800
15X1+12(25)=1.800
15X1+300=1.800
15X1=1.500
X1=100
 PENYELESAIAN :
Langkah berikutnya, hitung nilai empat titik sudut dengan
cara mensubstitusikan ke dalam fungsi tujuan untuk
melihat kombinasi mana yang menghasilkan laba
terbesar :
Maksimumkan 200X1+175X2
Titik A (0,0) : Z = 200(0) + 175(0) = 0
Titik E (120,0) : Z = 200(120) + 175(0) = 24.000
Titik C (0,125) : Z = 200(0) + 175(125) = 21.875
Titik D (100,25) : Z = 200(100) + 175(25) = 24.375
Jadi, perusahaan pengolahan ikan yang diikutkan diklat
X1= 100 dan perusahaan pengolahan kopra yang
diikutkan diklat adalah X2=25 agar volume ekspor naik,
karena akan menaikkan ekspor sebesar 24.375.
20
 BEBERAPA MASALAH TEKNIS DALAM
PROGRAM LINIER

1. No Feasible Solution
Ketika tidak ada solusi untuk masalah LP yang Contoh :
memenuhi semua kendala yang diberikan maka X1 + 2X2 ≤ 6
tidak ada solusi yang layak. Hal ini terjadi untuk
2X1 + X2 ≤ 8
permasalahan dengan kendala yang saling
bertentangan. X1 ≥ 7
Misalnya, jika salah satu kendala yang disediakan
oleh manajer pemasaran yang menyatakan bahwa
setidaknya 300 meja harus diproduksi (X1≥300)
untuk memenuhi permintaan penjualan. Namun
manajer produksi memberikan batasan bahwa tidak
ada lebih dari 220 meja yang diproduksi (X1≤220)
karena kekurangan kayu.
Maka analis riset operasi mengkoordinasikan
konflik ini dimana salah satu manajer harus
merevisi masukannya atau mungkin dengan
memperoleh lebih banyak bahan baku dari sumber
yang baru, atau mungkin permintaan penjualan
bisa diturunkan dengan mengganti model meja
yang baru untuk memenuhi kebutuhan pelanggan.
21
 BEBERAPA MASALAH TEKNIS DALAM
PROGRAM LINIER

2. Unboundedness
Kadang-kadang program linier tidak memiliki solusi yang terbatas. Ini berarti bahwa
dalam maksimalisasi sebuah masalah, misalnya, satu atau variabel solusi yang lebih,
dan laba, dapat dibuat besar tak berhingga tanpa melanggar kendala apapun. Jika kita
mencoba untuk memecahkan masalah seperti ini secara grafis, kita akan
mendapatkan daerah layak yang terbuka.

Contoh :
Maximize profit = 3X1 + 5X2
subject to :
X1 ≥ 5
X2 ≤ 10
X1 + 2X2 ≥ 10
X1, X2 ≥ 0

22
 BEBERAPA MASALAH TEKNIS DALAM
PROGRAM LINIER
3. Redundancy
Batasan (constraint) yang redundant tidak mempengaruhi daerah layak. Dengan kata
lain, salah satu kendala mungkin lebih mengikat atau ketat daripada yang lain.
batasan redundant ini tidak dipergunakan dalam pertimbangan karena tidak
mempengaruhi daerah layak.

Contoh :
Maximize profit = X1 + 2X2
subject to :
X1 + X2 ≤ 20
2X1 + X2 ≤ 30
X1 ≤ 25
X1, X2 ≥ 0

23
 BEBERAPA MASALAH TEKNIS DALAM
PROGRAM LINIER

4. Alternate Optimal Solutions

Masalah LP mungkin memiliki dua atau lebih alternatif solusi optimal. Secara grafis,
pada kasus ini terjadi ketika garis isoprofit atau isocost fungsi tujuan secara tepat
sejajar dengan salah satu constraint atau dengan kata lain memiliki slope yang sama.
Contoh :
Maximize profit = 3X1 + 2X2
subject to :
6X1 + 4X2 ≤ 24
X1 ≤ 3
X1, X2 ≥ 0

24