modul 1 model pl

1

OPERATIONS RESEARCH

Operations Research adalah suatu ilmu yang mempelajari tentang bagaimana

menentukan suatu tindakan terbaik dalam suatu keterbatasan sumber daya.

Sumber daya : uang, tenaga kerja, waktu dls.

Tindakan terbaik : kondisi optimal

Pendekatan: dalam pengambilan keputusan dapat berbentuk :

- Kuantitatif

- Art (seni) : - persepsi

- pengalaman

- kepandaian

Dalam O. R. pengambilan keputusan dengan memodelkan persoalan.

Model yang dipakai bersifat kuantitatif / matematik

Model : merupakan representasi dari sistem nyata/transformasi dari dunia nyata

S

Model

Sistem nyata (referensi)

A su ~-n!i i

model

Asumsi

2

Model matematik dari 0. R. :

variabel : sesuatu yang ingin dicari untuk dicapainya tujuan dalam keterbatasan

(Xj) sumber daya

Fungsi Tujuan : memaksimalkan / meminimalkan

Z = f {X1, X2, .......... , Xn}

Keterbatasan sumber . Kendala

Kendala : gi = fi {X1, X2,.Xn} i = 1; 2; .. m

Xj > 0 j = 1; 2; ..n

Model fungsi dari variabel keputusan

Fungsi : - linier

- non linier : kuadratik; eksponensial; dls.

Tahapan-tahapan penyelesaian model O. R. :

1) Mendefinisikan masalah : - tujuan

- alternatif tindakan

- kendala

2) Membentuk model

3) Mencari solusi masalah

4) Validasi model

5) Implementasi

3

MODEL PROGRAMA LINIER

Programa linier adalah teknik pemodelan secara matematik yang dirancang untuk

mengoptimalkan pemakaian sumber yang terbatas. Semua fungsi pada model

merupakan fungsi yang linier.

Pembuatan model Programa Linier :

Contoh :

PT X memproduksi cat luar dan cat dalam yang antara lain memerlukan dua macam

bahan baku Ml dan M2 dengan data sebagai berikut :

ton bahan baku per ton Ketersediaan

Cat luar Cat dalam per hari (ton)

Bahan baku M1

Bahan baku M2

6

1

4

2

24

6

Keuntungan /ton $ 5000 $ 4000

Hasil survei pasar menunjukkan bahwa kebutuhan cat dalam tidak melebihi kebutuhan

cat luar sebanyak 1 ton/hari, sedangkan kebutuhan cat dalam terbatas sampai 2

ton/hari.PT X ingin menentukan jumlah produksi yang optimum dari kedua jenis cat

tersebut yang memberikan keuntungan total per hari terbesar.

Model Programa linier terdiri dari tiga elemen :

1. Variabel keputusan, yaitu apa yang ingin dicari oleh model.

2. Tujuan, yaitu apa yang ingin dioptimalkan

3. Kendala, yaitu apa yang harus dipenuhi

Langkah pertama adalah penentuan variabel keputusan, kemudian disusun kendala dan

tujuan dari persoalan.

Untuk persoalan di atas ingin ditentukan jumlah produksi dari cat luar dan cat dalam yang

memberikan keuntungan total terbesar.

4

Variabel :

X1 = jumlah produksi cat luar per hari.

X2 = jumlah produksi cat dalam per hari

Fungsi tujuan :

Tujuan kita adalah memaksimalkan keuntungan total dari penjualan kedua jenis cat.

f. t. maks. Z = 5X1 + 4X2

Kendala :

- Tersedianya bahan baku :

pemakaian bahan baku jumlah bahan baku maks. oleh kedua jenis cat yang tersedia

- Bahan baku M1 : 6X1 + 4X2 < 24

- Bahan baku M2 : X1 + 2X2 < 6

- Pembatasan permintaan :

kelebihan jumlah cat dalam terhadap cat luar < 1 ton/hari

X2 - X1 < 1

permintaan terhadap cat dalam < 2 ton/hari

X2 < 2

- di samping kendala di atas tentu saja jumlah produksi kedua jenis cat tersebut

tidak boleh negatif

X1 > 0

X2 > 0

Dengan demikian model matematis dari persoalan di atas :

f. t. maks. Z = 5X1 + 4X2

d. k. 6X1 + 4X2 < 24

X1 + 2X2 < 6

- X1 + X2 < 1

X2 < 2

X1; X2 > 0

<

5

Semua penyelesaian yang memenuhi kendala adalah penyelesaian yang

layak/mungkin. Misalnya X1 = 3 ton, X2 = l ton, maka pemakaian bahan baku M1 adalah

22 ton yang masih memenuhi kendala yaitu < 24 ton. Nilai fungsi tujuan adalah Z $

19.000, demikian juga untuk kendala-kendala lainnya.

Tujuan kita adalah mencari penyelesaian yang layak dan optimal. Kita ingin

mencari kombinasi nilai X1 dan X2 sedemikian rupa yang memenuhi kendala/batasan

yang ada dan memberikan nilai Z yang terbesar.

Model P.L. di atas merupakan fungsi yang linier, di mana memenuhi hal berikut:

1. Proporsional. Kontribusi setiap variabel keputusan terhadap fungsi tujuan dan

kendala adalah sebanding dengan nilai variabel keputusan. Jika PT X memberikan

potongan harga jika pembelian barang melebihi suatu batas tertentu maka

pendapatan/ keuntungan kita tidak linier, sehingga model harus dijadikan linier

2. Dapat ditambah. Kontribusi dari semua variabel pada fungsi tujuan dan kendala

adalah jumlah langsung dari kontribusi dari setiap variabel. Sebagai contoh dua

barang yang bersaing, di mana kenaikan tingkat penjualan dari satu produk

memberikan pengaruh merugikan terhadap penjualan barang yang lain, tidak

memuaskan sifat additivity

6

PENYELESAIAN PROGRAMA LINIER SECARA GRAFIS:

5)

1) 6X1 + 4X2 < 24

(1) 2) X1 + 2X2 < 6

X2 3) -Xl + X2 < l

(3) 4) X2 < 2

5) X1 > 0

6) X2 > 0

(4)

(2)

(6)

X1

Untuk menggambarkan bidang penyelesaian yang layak (yang memenuhi batasan-

batasan) pertama kita jadikan kendala pertidak-samaan menjadi persamaan. garis

persamaannya merupakan batas kendala, digambarkan seperti di atas.

Kita masukkan nilai koordinat titik A (0,0) ke dalam persamaan-persamaan tersebut.

Daerah yang memenuhi syarat setiap kendala ditunjukkan oleh garis dan tanda panah.

Sebagai contoh : Garis (1) adalah 6X1 + 4X2 = 24. Kita masukkan koordinat titik A (0,0)

ke dalam persamaan (1), akan diperoleh 6.0 + 4.0 = 0 yang lebih kecil dari 24; dengan

demikian titik-titik pada bidang dari garis (1) ke arah titik A (seperti yang ditunjukkan oleh

anak panah) memberikan nilai yang lebih kecil dari 24.

Gabungan dari keenam kendala . tersebut memberikan bidang ABCDEFA yang

merupakan bidang penyelesaian yang layak. Dengan demikian semua titik yang

berada pada bidang tersebut memenuhi keenam kendala tersebut.

7

fungsi tujuan adalah Z = 5X l + 4 X2

Pada saat garis Z melalui :

titik (0,0) Z = 0

titik (1,0) Z = 5

Z=10 Z=15 titik (2,0) Z = 10

Z= 5 titik (3,0) Z = 15

Z = 0

(0,0) (1,0) (2,0) (3,0)

Terlihat bahwa jika kita geser garis Z tersebut ke arah kanan, nilai Z bertambah besar.

Persoalan kita adalah mencari sebuah titik pada bidang ABCDEFA yang memberikan

nilai Z terbesar. Dengan perkataan lain kita mencari kombinasi Xl dan X2 yang

memberikan nilai Z terbesar yang masih berada pada bidang penyelesaian yang layak.

Secara grafis terlihat paling jauh garis Z dapat digeser sampai melalui titik C. Dengan

demikian diperoleh titik optimum adalah titik C.

Koordinat titik C diperoleh dengan memotongkan garis (l) dan garis (2).

Diperoleh : X1 = 3

X2 = 1.5

Z = 21

Jika kita masukkan koordinat titik sudut bidang penyelesaian yang layak tersebut secara

berturut-turut ke dalam persamaan garis Z akan diperoleh nilai Z yang semakin besar

kemudian menurun kembali setelah titik optimal tercapai. Hal tersebut akan kita gunakan

sebagai algoritma penyelesaian secara aljabar/simpleks pada pembahasan bab

berikutnya.

8

Penyelesaian persoalan Model Programa Linier meminimumkan

Contoh : Peternakan X memerlukan paling sedikit 800 lb. makanan untuk ayam yang diternakkan

setiap hari. Makanan tersebut terdiri dari campuran jagung dan kacang kedelai, dengan

komposisi sbb.

Lb. Per lb. Bahan baku Harga

Bahan baku Protein Serat ($/lb.)

Jagung

Kacang kedelai

0,09

0,60

0,02

0,06

0,30

0,90

Komposisi makanan tersebut paling sedikit mengandung 30 % protein dan paling banyak

mengandung 5 % serat. Perusahaan tersebut ingin meminimalkan biaya total.

Penyelesaian :

Variabel :

X l = jumlah jagung dalam makanan (lb.)

X2 = jumlah kacang kedelai dalam makanan (lb.)

Fungsi tujuan :

Meminimalkan biaya total

Min. Z = 0,30X l + 0,90X2

Kendala :

- Jumlah makanan : X1 + X2 > 800

- Jumlah protein : 0,09X1+0,60X2 > 0,3 (X1+X2)

- Jumlahserat : 0,02X1+0,06X2 < 0,05(X1+X2)

- Jumlah bahan baku : Xj > 0 j = 1; 2

9

Penyelesaian model secara grafis

Dengan demikian model adalah :

Min. Z = 0,30X1+ 0,90X2 d. k. : X1 + X2 > 800

0,21X1 - 0,30X2 < 0

0,03X1 0,01X2 > 0

X1;X2 > 0

Seperti halnya pada penyelesaian pada persoalan memaksimalkan dibuat bidang

penyelesaian yang layak, dengan menentukan daerah-2 penyelesaian yang memenuhi

syarat. Diperoleh bidang penyelesaian yang diarsir.

X2

optimum

(470.6,329.4) Z=437.64

X1

Jika pada persoalan memaksimalkan kita geser garis z ke arah kanan untuk memperoleh

sebuah titik yang memberikan nilai z yang terbesar, maka pada persoalan meminimalkan

kita geser garis z tersebut sejauh mungkin kea rah kiri sampai diperoleh sebuah titik yang

memberikan nilai z yang terkecil. Pada persoalan ini diperoleh titik optimal di titik P. Titik P

adalah titik perpotongan garis 1 dan garis 2 dengan koordinat (470,6; 329,4) dan

diperoleh z = 437,64

10

Contoh-contoh aplikasi Programa Linier

Contoh 1

Sebuah perusahaan memproduksi tiga macam barang. Pembuatan barang-barang tersebut

dilakukan melalui tiga proses produksi seperti pada gambar di bawah ini. Waktu pengerjaan setiap

barang dapat dilihat pada setiap kotak.

B 1/unit 3/unit 1/unit Barang 1 a

h a 2/unit 4/unit Barang 2 n

b 1/unit 2/unit Barang 3 a

k u

Operasi 1

Operasi 2

Operasi 3

Oleh karena mesin tersebut juga dipakai untuk pembuatan barang lain, maka

waktu produksi yang tersedia dari setiap proses terbatas sebesar 430, 460, dan 420

menit untuk setiap prosesnya. Studi pasar memperlihatkan keuntungan setiap macam

barang berturut-turut sebesar $ 3, $ 2, dan $ 5 per unit. Tentukan tingkat produksi yang

optimal.

Penyelesesaian :

Model Programa Linier :

Variabel

Xj = jumlah produksi barang j; j = 1, 2,3

Fungsi tujuan

Maks. Z = 3X1 + 2X2 + 5X3

Kendala :

- Proses produksi l : 1X1 + 2X2 + 1X3 < 430

- Proses produksi 2 : 3X1 + 0X2 + 2X3 < 460

- Proses produksi 3 : 1X1 + 4X2 + 0X3 < 420

X1; X2; X3 > 0

11

Contoh 2 persoalan bis

Perusahaan bis ingin meminimalkan jumlah bis yang beroperasi. Berdasarkan studi

jumlah bis yang diperlukan beroperasi pada setiap waktu adalah seperti pada gambar

berikut. Setiap bis dengan beberapa pertimbangan beroperasi 8 jam per hari. Pimpinan

menetapkan akan memberangkatkan bis setiap 4 jam. Tentukan berapa banyak bis pada

setiap jam pemberangkatan.

12

10

8 7

4 4

0.00 4.00 8.00 12.00 16.00 20.00 24.00 4.00 8.00

X1 X3 X5 X1

X2 X4 X6

Penyelesaian :

Variabel

Xj = jumlah bis yang diberangkatkan pada setiap

jam pemberangkatan j = 1, 2,.6

Fungsi tujuan

Min. Z X1 + X2 + X3 + X4 X5 + X6

Kendala

- Jam operasi 0.00 - 4.00 : X1 + X6 > 4

- Jam operasi 4.00 - 8.00 : X1 + X2 > 8

- Jam operasi 8.-00 - 12.00 : X2 + X3 > 10

- Jam operasi 12.00 - 16.00 : X3 + X4 > 7

- Jam operasi 16.00 - 20.00 : X4 + X5 > 12

- Jam operasi 20.00 - 24.00 : X5 + X6 > 4

Xj > 0 j=1; 2; .6

12

Contoh 3 : Persoalan pabrik kertas

Sebuah pabrik kertas memproduksi kertas dengan lebar 20'. Pesanan pelanggan di luar ukuran

standar, permintaannya dipenuhi dengan memotong lebar kertas ukuran standar. Perusahaan

memperoleh pesanan dengan jumlah rol seperti di bawah ini :

Pesanan Lebar yang diminta () Jumlah rol yang diminta (rol) 1

2

3

5

7

9

150

200

300

Tujuan perusahaan adalah memotong kertas dengan jumlah kertas yang terbuang

sesedikit mungkin.

Penyelesaian :

Untuk memperoleh lebar yang diminta, dapat dilakukan berbagai kombinasi pemotongan,

di mana diperoleh lebar kertas terbuang berbeda di samping itu terdapat kelebihan rol

yang tidak tersuplai/terpakai. Jadi persoalan kita adalah meminimalkan luas kertas yang

tidak terpakai, baik yang lebarnya tidak memenuhi syarat maupun jumlah rol yang terlalu

banyak.

Penyelesaian :

Setelah dianalisa terdapat enam cara pemotongan kertas seperti di bawah ini :

Pemotongan jenis : Jumlah rol

Ukuran rol 1 2 3 4 5 6 yang diminta

5

7

9

0

1

1

2

1

0

2

0

1

4

0

0

1

2

0

0

0

2

150

200

300

Lebar sisa 4 3 1 0 1 2

Variabel :

Xj adalah jumlah rol yang dipotong menurut tipe pemotongan j.

Xj > 0 j = 1;2;..6

13

Hasil/jumlah rol yang diperoleh dari setiap jenis pemotongan sbb. :

- Ukuran 5': 0X1 + 2X2 + 2X3 + 4X4 + IX5 + 0X6 150 = Y1

- Ukuran 7': 1X1 + 1X2 + 0X3 + 0X4 + 2X5 + 0X6 200 = Y2

- Ukuran 9': 1Xl + 0X2 + lX3 + 0X4 + 0X5 + 2X6 300 = Y3

jumlah produksi jumlah jumlah permintaan rol sisa

Variabel : Yi = jumlah rol sisa ukuran i i = 1; 2; 3

Jika panjang kertas pada setiap rol L :

- Luas kertas yang tidak terpakai karena terlalu pendek :

[4X1 +3X2 + X3 + 0X4 + X5 + 2X6]L

- Luas kertas yang tidak terpakai karena terlalu banyak :

[5Y1 + 7Y2 + 9Y3]L

Dengan demikian luas kertas total yang terbuang :

[4X1 +3X2 + X3 + 0X4 + X5 + 2X6]L + [5YI + 7Y2 + 9Y3]L

Tujuan kita adalah meminimalkan luas kertas yang terbuang :

f t. min. Z = [4X1 +3X2 + X3 + X5 + 2X6]L + [5Y1 + 7Y2 + 9Y3]L

oleh karena L adalah konstanta dapat dihilangkan

model menjadi :

fungsi tujuan :

min. Z = 4X1+3X2 + X3 + X5 + 2X6 + 5Y1 + 7Y2 + 9Y3

dengan kendala :

0X1 + 2X2 + 2X3 + 4X4 + IX5 + 0X6 Y1 = 150

1X1 + 1X2 + 0X3 + 0X4 + 2X5 + 0X6 Y2 = 200

lXl + 0X2 + lX3 + 0X4 + 0X5 + 2X6 Y3 = 300

Xj > 0 j = 1; 2; 6

Yi > 0 i = 1; 2; 3

14

Contoh 4 : Persoalan penyeimbangan lini produksi

Sebuah perusahaan membuat satu macam barang yang terdiri dari tiga buah komponen,

yaitu 2 buah komponen 1, 1 buah komponen 2, dan 3 buah komponen 3. Semua

komponen tersebut dapat dibuat pada dua departemen. Waktu pembuatan setiap

komponen pada kedua departemen berbeda. Pada tabel berikut diberikan kecepatan

produksi dan jumlah produksi yang dialokasikan per minggu pada kedua departemen tsb.

Buatlah model Programa Linier yang memaksimalkan jumlah produksi yang dihasilkan.

Kapasitas Kecepatan produksi (unit/jam)

Departemen yng. tersedia

(jam/minggu)

Komponen 1 Komponen 2 Komponen 3

1

2

200

160

8

6

5

12

10

4

Penyelesaian :

Variabel : Xij = jumlah jam produksi yang disediakan untuk membuat

komponen i pada departemen j i = 1,2,3 j = 1,2

Jumlah komponen yang dihasilkan :

komponen l : 8X11 + 6X12

komponen 2 : 5X21 + 12X22

komponen 3 : 10X31 + 4X32

Tujuan :

memaksimalkan barang sebanyak mungkin dari semua komponen yang ada.

Satu barang jadi terdiri dari 2 buah komponen 1, 1 buah komponen 2 dan 3 buah komponen 3,

sehingga jumlah barang jadi yang diperoleh sebanyak jumlah barang jadi yang dapat dibuat

dari komponen yang jumlahnya terkecil.

Maks. Z = min. {1/2(8X11 + 6X12);(5X21 + 12X22);1/3(10X31 + 4X32)}

Fungsi di atas tidak linier, perlu dijadikan linier.

Jumlah barang yang diproduksi = Y = {1/2(8X11+6X12);(5X21+12X22);1/3(10X31+4X32)}

Dengan demikian fungsi tujuan menjadi :

15

Maks. Z = Y

Jumlah barang jadi yang dapat dibuat > jumlah barang jadi. dari setiap jenis komponen yang dibuat

1/2(8X11 + 6X12) > Y

(5X21 + 12X22) > Y

1/3(10X31 + 4X32) > Y

Kendala :

X 11 + X21 + X31 < 200 jam yang tersedia pada dept. 1

X12 + X22 + X32 < 160 jam yang tersedia pada dept. 2

Dengan demikian model menjadi :

Maks. Z = Y

d.k. X11 + X21 + X31 < 200

X21 + X22 + X32 < 160

8X11 + 6X12 2Y > 0

5X21 + 12X22 - Y > 0

10X31 + 4X32 3Y > 0

Xij > 0 i=1, 2, 3

j = 1, 2

Variabel : Xij = jumlah komponen i yang dibuat pada departemen j i = 1,2,3 j = 1,2

Jumlah komponen yang dihasilkan :

komponen l : X11 + X12

komponen 2 : X21 + X22

komponen 3 : X31 + X32

16

Tujuan :

memaksimalkan barang sebanyak mungkin dari semua komponen yang ada.

Satu barang jadi terdiri dari 2 buah komponen 1, 1 buah komponen 2 dan 3 buah komponen 3, sehingga jumlah barang jadi yang diperoleh sebanyak jumlah barang jadi yang dapat dibuat dari komponen yang jumlahnya terkecil.

Maks. Z = min. {1/2(X11 + X12);(X21 + X22);1/3(X31 + X32)}

Fungsi di atas tidak linier, perlu dijadikan linier.

Jumlah barang yang diproduksi = Y = {1/2(X11+X12);(X21+X22);1/3(X31+X32)}

Dengan demikian fungsi tujuan menjadi :

Maks. Z = Y

Jumlah barang jadi yang dapat dibuat > jumlah barang jadi. dari setiap jenis komponen yang dibuat 1/2(X11 + X12) > Y

(X21 + X22) > Y

1/3(X31 + X32) > Y

Kendala :

1/8X 11 + 1/5X21 + 1/10X31 < 200 jam yang tersedia pada dept. 1

1/6X12 + 1/12X22 + 1/4X32 < 160 jam yang tersedia pada dept. 2


Maks. Z = Y

d.k. 1/8X11 + 1/5X21 + 1/10X31 < 200

1/6X21 + 1/12X22 + 1/4X32 < 160

X11 + X12 2Y > 0

X21 + X22 - Y > 0

X31 + X32 3Y > 0

Xij; Y > 0 i = 1, 2, 3

j = 1, 2

17

Contoh 5 : Programa Tujuan

Pada umumnya ruas kiri dan ruas kanan kendala mempunyai hubungan ; =, namun

dapat menguntungkan dengan melanggar kendala yang ada, namun demikian dengan

dilanggarnya kendala kita dikenakan penalti. Sebagai contoh kita dapat membeli bahan

baku lebih besar dari dana yang tersedia, namun untuk itu kita dikenakan penalti yaitu

harus membayar bunga bank atas pinjaman dan yang kita lakukan yang pada akhirnya

mengurangi keuntungan yang akan diperoleh.

Persoalan

Sebuah perusahaan memproduksi dua macam barang berturut-turut pada dua buah

mesin yang berbeda. Waktu yang tersedia pada kedua mesin tersebut masing-masing 8

jam. Namun batas waktu tersebut dapat dilampaui dengan melakukan kerja lembur.

Biaya lembur adalah $ 5/jam. Jam lembur yang diijinkan adalah 4 jam per hari.

Kecepatan produksi kedua mesin dan keuntungan per unit dari kedua barang tsb. adalah

seperti pada tabel berikut.

Kec. Produksi (unit/jam)

Mesin Barang 1 Barang 2

1

2

5

4

6

8

Keuntungan/unit $ 6 $ 4

Model ini sama dengan contoh 1 kecuali di sini terdapat lembur, yang mengakibatkan

adanya biaya tambahan / berkurangnya keuntungan.

Variabel : Xj = jumlahproduksi barang j j=1;2

Jika tidak ada lembur kendala dapat ditulis :

1/5X1 + 1/6X2 < 8 (mesin 1)

1/4X2 + 1/8X2 < 8 (mesin 2)

Dengan adanya lembur kendala menjadi :

1/5X1 + 1/6X2 - Y1 = 8

1/4X1 + 1/7X2 - Y2 = 8

di mana Y1 dan Y2 adalah variabel yang merupakan jam lembur atau kelebihan jam

produksi. Yl dan Y2 tersebut adalah variabel yang tak terbatas pada tanda.

Jika Yi positif Yi merupakan jam lembur

Jika Yi negatif Yi merupakan kelebihan jam produksi dan

berarti tidak ada lembur.

18

Jam lembur maks.(0,Yi)

Biaya lembur = jam lembur x biaya lembur/jam

= 5 x maks.(0,Yi)

Model:

f.t. maks. Z = 6X1 + 4X2 5 {maks.(0,Yl) + maks(0,Y2))

keuntungan biaya lembur

Dengan kendala:

1/5X1 + 1/6X2 - Yl = 8

1/4Xl + 1/8X2 - Y2 = 8

Y1 < 4

Y2 < 4

X1; X2 > 0 dan Y1; Y2 tidak terbatas pada tanda

Model tersebut fungsi tujuannya tidak linier perlu dijadikan linier.

Wi = maks. (0,,Yi)

Wi = maks(0,Yi) dapat ditulis menjadi

Wi > Yi

Wi > 0

Model menjadi :

f.t. maks. Z = 6X1 + 4X2 - 5WI - 5W2

d. k. 1/5X1 + 1/6X2 Y1 = 8

1/4Xl + 1/8X2 Y2 = 8

Y1 < 4

Y2 < 4

Y1 - W1 < 0

Y2 - W2 < 0

X1; X2; W1; W2 > 0 dan Y1; Y2 tidak terbatas pada tanda

Persoalan tersebut juga dapat diselesaikan sbb. :

Variabel : Xj = jumlahproduksi barang j j=1;2

Jika tidak ada lembur kendala dapat ditulis :

1/5X1 + 1/6X2 < 8 (mesin 1)

1/4X2 + 1/8X2 < 8 (mesin 2)

Dengan adanya lembur kendala menjadi :

19

1/5X1 + 1/6X2 + Y1- - Y1+ = 8

1/4X1 + 1/7X2 + Y2- - Y2+ = 8

di mana Y1- dan Y2- adalah variabel yang merupakan kelebihan jam produksi,

dan Y1+ dan Y2+ adalah variabel yang merupakan jam lembur.

Y1+; Y2+; Y1- ; Y2- > 0

Dengan demikian biaya lembur = 5 x (Y1+ + Y2+)

Model:

f.t. maks. Z = 6X1 + 4X2 5 x (Y1+ + Y2+)

keuntungan biaya lembur

Dengan kendala:

1/5X1 + 1/6X2 + Y1- - Y1+ = 8

1/4X1 + 1/7X2 + Y2- - Y2+ = 8

Y1+ < 4

Y2+ < 4

X1; X2; Y1+; Y2+; Y1- ; Y2- > 0

Contoh 6. Kebijaksanaan pinjaman bank

Bank X mempertimbangkan kebijaksanaan pinjaman dana 12 juta pada berbagai jenis

pinjaman. Tabel berikut adalah data dari berbagai jenis pinjaman tsb.

Jenis pinjaman Tingkat suku bunga

Kemungkinan pinjaman tidak tertagih

Pribadi

Kendaraan

Perumahan

Pertanian

Perdagangan

0.140

0.130

0.120

0.125

0.100

0.10

0.07

0.03

0.05

0.02

Pinjaman yang tak tertagih tidak menghasilkan bunga. Kompetisi dengan lembaga

keuangan lain pada wilayah kerja bank tersebut menyebabkan bank X mengalokasikan

paling sedikit 40 % dananya untuk pinjaman pertanian dan perdagangan. Untuk

membantu industri perumahan, pinjaman untuk perumahan paling sedikit 50 % dari total

pinjaman pribadi, kendaraan dan perumahan. Bank juga menetapkan rata-rata hutang tak

tertagih tidak lebih dari 0,04. Buatlah model Programa Linier dari persoalan di atas.

20

Penyelesaian :

Variabel : Xj = alokasi pinjaman untuk jenis pinjaman j j = 1, 2, ., 5

Fungsi tujuan :

Memaksimalkan pendapatan total dari bunga bank yang diperoleh dikurang hutang yang

tak tertagih.

f.t. maks. Z = 0.14(0.9X1)+ 0.13 (0.93X2) + 0.12(0.97X3) + 0.125(0.95X4)

+ 0.1(0.98X5) - 0.1X1 - 0.07X2 - 0.03X3 - 0.05X4 - 0.02X5

setelah disederhanakan diperoleh :

maks. Z = 0.026X l + 0.0509X2 + 0.0864X3 + 0.06875X4 + 0.078X5

Kendala

1) Dana total : X1 + X2 + X3 + X4 + X5 = 12

2) Pinjaman pertanian dan perdagangan : X4 + X5 > 0.4 x l2

X4 + X5 > 4.8

3) Pinjaman perumahan : X3 > 0.5(X1 + X2 + X3)

X1 + X2 X3 < 0

4) Batasan pinjaman yang tak tertagih :

0.lX1 + 0.07X2 + 0.03X3 + 0.05X4 + 0.02X5 ----------------------------------------------------------- < 0.04 X1 + X2 + X3 + X4 + X5

0.06X1 + 0.03X2 - 0.01X3 + 0.01X4 - 0.02X5 < 0 5) Kendala non negatif : Xj > 0 j = 1, 2 , , 5

Model menjadi :

Fungsi Tujuan :

Z = 0.026X1 + 0.0509X2 + 0.0864X3 + 0.06875X4 + 0.078X5

Dengan Kendala :

X1 + X2 + X3 + X4 + X5 < 12

X4 + X5 > 4.8

X1 + X2 X3 < 0

0.06X1 + 0.03X2 - 0.01X3 + 0.01X4 - 0.02X5 < 0

Xj > 0 j = 1, 2 , , 5

21

Contoh 7 : Perencanaan Produksi dan pengendalian Persediaan

(Model Produksi Periode Tunggal)

Dalam mempersiapkan produksi untuk periode yang akan datang, sebuah perusahaan

yang memproduksi pakaian jenis 1, 2, 3, dan 4. semua produk diproduksi berturut-turut

pada departemen 1, 2, 3, dan 4. Perusahaan telah menerima pesanan untuk keempat

macam produk. Data waktu produksi, kapasitas produksi, jumlah pesanan, keuntungan

per unit serta prnalti per unit dapat dilihat pada tabel. Buatlah model Programa Linier

yang mengoptimalkan produksi.

Waktu produksi per unit (jam) Kapasitas

Departemen Produk 1 Produk 2 Produk 3 Produk 4 (jam)

1

2

3

4

0,30

0,25

0,45

0,15

0,30

0,35

0,50

0,15

0,25

0,30

0,40

0,10

0,15

0,10

0,22

0,05

1000

1000

1000

1000

Permintaan (unit) 800 750 600 500

Keuntungan ($/unit) 30 40 20 10

Penalti ($/unit) 25 20 10 8

Penyelesaian :

Variabel : xj = jumlah produk j yang dibuat, j = 1, 2, 3, 4

Perusahaan paling banyak memproduksi sebanyak permintaan :

x1 < 800; x2 < 750; x3 < 600; x4 < 500

Pendapatan bersih = Total keuntungan total penalti

Terdapat variabel baru yaitu jumlah produk yang tidak tersuplai;

sj = jumlah produk j yang tidak tersuplai, j = 1, 2, 3, 4

Dalam hal ini kendala permintaan di atas berubah menjadi :

x1 + s1 = 800; x2 + s2 = 750; x3 + s3 = 600; x4 + s4 = 500

22

Fungsi tujuan :

Maks. z = 30x1 + 40x2 + 20x3 + 10x4 15s1 20s2 10s3 8s4

Kendala produksi departemen :

Departemen 1 : 0,30x1 + 0,30x2 + 0,25x3 + 0,15x4 < 1000

Departemen 1 : 0,25x1 + 0,35x2 + 0,30x3 + 0,10x4 < 1000

Departemen 1 : 0,45x1 + 0,50x2 + 0,40x3 + 0,22x4 < 1000

Departemen 1 : 0,15x1 + 0,15x2 + 0,10x3 + 0,05x4 < 1000


f. t. maks. z = 30x1 + 40x2 + 20x3 + 10x4 15s1 20s2 10s3 8s4

0,30x1 + 0,30x2 + 0,25x3 + 0,15x4 < 1000

0,25x1 + 0,35x2 + 0,30x3 + 0,10x4 < 1000

0,45x1 + 0,50x2 + 0,40x3 + 0,22x4 < 1000

0,15x1 + 0,15x2 + 0,10x3 + 0,05x4 < 1000

x1 + s1 = 800

x2 + s2 = 750

x3 + s3 = 600

x4 + s4 = 500

xj; sj > 0 j = 1, 2, 3, 4

23

Contoh 8 : Model Produksi-Persediaan periode jamak

Sebuah perusahaan mempunyai kontrak untuk mensuplai barang X untuk 6 bulan yang

akan datang berturut-turut sebesar 100, 250, 190, 140, 220, dan 110 unit. Biaya produksi

dari bulan ke bulan berbeda, tergantung pada biaya tenaga kerja, material dls. Biaya

pada bulan-bulan tersebut diperkirakan sebesr $ 50, $ 45, $ 55, $ 48, $ 52, dan $ 50.

Untuk memanfaatkan perbedaan tersebut perusahaan dapat memproduksi lebih pada

saat biaya rendah untuk disimpan sebagai persediaan dan dipakai pada periode

berikutnya pada saat biaya tinggi, namun timbul biaya persediaan sebesar $ 8 per unit

per bulan. Buatlah model programa linier yang meminimalkan biaya total.

Penyelesaian :

Variabel : Xj = jumlah produksi pada bulan j, j = 1, 2, . . , 6

Ij jumlah persediaan yang ada pada akhir bulan j

Persediaan yang masuk pada awal bulan 1 = I0 = 0

Tujuan kita adalah meminimalkan biaya produksi dan biaya persediaan

Biaya produksi total = 50x1 + 45x2 + 55x3 + 48x4 + 52x5 + 50x6

Biaya persediaan total = 8(I1 + I2 + I3 + I4 + I5 + I6)

Jadi fungsi tujuan adalah :

min. Z = 50x1 + 45x2 + 55x3 + 48x4 + 52x5 + 50x6 + 8(I1 + I2 + I3 + I4 + I5 + I6)

Aliran dari produksi persediaan dan permintaan dapat digambarkan sbb.

x1 x2 x3 x4 x5 x6 I = 0 I1 I2 I3 I4 I5 I6 100 250 190 140 220 110

Gambar : skema dari sistem produksi-persediaan

Dari gambar diperoleh keseimbangan antara produksi, persediaan dan permintaan :

Persediaan awal + Jumlah produksi Jumlah permintaan = Persediaan akhir

Persediaan awal + Jumlah produksi Persediaan akhir = Jumlah permintaan

24

Dengan demikian terdapat hubungan kendala :

In-1+ xn In = Dn

Dn = Jumlah permintaan pada bulan n

Diperoleh :

Bulan 1 : x1 I1 = 100

2 I1 + x2 I2 = 250

3 I2 + x3 I3 = 190

4 I3 + x4 I4 = 140

5 I4 + x5 I5 = 20

6 I5 + x6 I6 = 110


min. Z = 50x1 + 45x2 + 55x3 + 48x4 + 52x5 + 50x6 + 8(I1 + I2 + I3 + I4 + I5 + I6)

dengan kendala :

x1 I1 = 100

I1 + x2 I2 = 250

I2 + x3 I3 = 190

I3 + x4 I4 = 140

I4 + x5 I5 = 20

I5 + x6 I6 = 110

25

Contoh 9 : Persoalan kilang minyak

Sebuah perusahaan yang memproduksi bahan bakar mempunyai kilang di A yang

kapasitas produksinya adalah 1.500.000 bbl. Minya mentah per hari. Produk akhir dari

kilang tersebut adalah bensin jenis 1, 2 dan 3 yang masing-2 bensin biasa dengan angka

oktan 87, bensin premium dengan angka oktan 89 dan bensin super dengan angka

oktan 92. Kilang tersebut memproses minyak mentah dalam tiga tahap. Pertama pada

unit distilasi yang menghasilkan bensin dengan angka oktan 82 pada tingkat 0,2 bbl. per

bbl minyak mentah. Kedua pada unit pemecah yang menghasilkan bensin dengan angka

oktan 98. dengan menggunkan sebagian bensin yang dihasilkan pada unit distilasi pada

tingkat 0,5 bbl. Bensin angka oktan 98 untuk setiap bbl bensin angka oktan 82. Ketiga

pada unit pencampur, dengan mencampur bensin dengan angka oktan 82 yang berasal

dari unit distilasi dan bensin dengan angka oktan 98 yang berasal dari unit pemecah.

Perusahaan memperkirakan keuntungan bensin biasa adalah $ 6,70 bensin premium

adalah $ 7,20 dan bensin super adalah 8,10. kapasitas unit pemecah adalah 200.000 bbl

bensin angka oktan 82 per hari. Batas permintaan bensin biasa adalah 50.000 bbl,

bensin premium adalah 30.000 bbl, dan bensin super adalah 40.000 bbl per hari. Buatlah

model Programa Linier yang memekasimalkan keuntungan total.

Penyelesaian :

Variabel : xij = jumlah input tahap i yang di proses menjadi bensin j; j = 1, 2, 3

i = 1 adalah bensin yang keluar unit distilasi

i = 2 adalah bensin yang keluar unit pemecah

dengan menggunakan definisi ini diperoleh :

Produksi per hari bensin biasa = x11 + x21 bbl per hari

Produksi per hari bensin premium = x12 + x22 bbl per hari

Produksi per hari bensin super = x13 + x23 bbl per hari

Output produksi harian produksi harian produksi harian unit pencampur dari bensin biasa dari bensin premium dari bensin super = (x11 + x21) + (x11 + x21) + (x13 + x23) bbl per hari

= + +

26

x11 + x12 + x13

5 : 1 2 : 1

X21 + x22 + x23

Angka angka

Oktan 82 oktan 98

Jumlah hasil distilasi (AO=82) yang masuk ke unit pencampur

Jumlah hasil pemecah (AO=98) yang masuk ke unit pencampur

Jumlah hasil distilasi (AO=82) yang masuk ke unit pemecah

Jumlah minyak mentah yang diproses pada kilang

Tujuan dari model adalah memaksimalkan keuntungan total yang dihasilkan dari

penjualan ketiga jenis bensin :

Fungsi Tujuan : maks. Z = 6,7(x11 + x21) + 7,2(x12 + x22) + 8,1(x13 + x23)

Kendala dari persoalan ini adalah :

1. jumlah suplai tidak lebih dari 1.500.000 bbl per hari :

5(x11 + x12 + x13) + 10(x21 + x22 + x23 ) < 1.500.000

2. input unit pemecah tidak lebih dari 200.000 bbl per hari

2(x21 + x22 + x23 ) < 200.000

3. permintaan bensin biasa paling banyak 50.000 bbl per hari

x11 + x21 < 50.000

4. permintaan bensin premium paling banyak 30.000 bbl per hari

x12 + x22 < 30.000

5. permintaan bensin super paling banyak 40.000 bbl per hari

x13 + x23 < 40.000

Unit distilasi

Unit pemecah

Unit pencampur

x11+x21 bensin biasa angka oktan 87

x12+x22 bensin premium angka oktan 89

x13+x23 bensin super angka oktan 92

= x11 + x12 + x13 bbl per hari

= x21 + x22 + x23 bbl per hari

= 2(x21 + x22 + x23 ) bbl per hari

= 5(x11 + x12 + x13) + 10(x21 + x22 + x23 ) bbl per hari

27

6. angka oktan bensin biasa paling sedikit adalah 87

angka oktan rata-rata : 82x11 + 98x21 > 87 x11 + x21

7. angka oktan bensin premium paling sedikit adalah 89


8. angka oktan bensin super paling rendah adalah 92



Fungsi Tujuan : maks. Z = 6,7(x11 + x21) + 7,2(x12 + x22) + 8,1(x13 + x23)

5(x11 + x12 + x13) + 10(x21 + x22 + x23 ) < 1.500.000

2(x21 + x22 + x23 ) < 200.000

x11 + x21 < 50.000

x12 + x22 < 30.000

x13 + x23 < 40.000

82x11 + 98x21 > 87(x11 + x21)

82x12 + 98x22 > 89(x12 + x22)

82x13 + 98x23 > 92x13 + x23)

Xij > 0 i = 1, 2

J = 1, 2, 3

28

ANALISA KEPEKAAN SECARA GRAFIS

Analisa kepekaan merupakan suatu analisa terhadap penyelesaian optimal yang telah

diperoleh sebelumnya. Di sini kita ingin mengetahui pengaruh perubahan dari parameter-

parameter pada model terhadap kondisi optimal yang telah diperoleh.

Pada pembahasan di sini analisa kepekaan secara grafis ini ditinjau dari :

1) perubahan koefisien fungsi tujuan

2) perubahan ruas kanan kendala

PERUBAHAN KOEFISIEN FUNGSI TUJUAN

Berapa besar perubahan pada koefisien fungsi tujuan dapat terjadi tanpa mempengaruhi

titik sudut optimal ?

C1 atau

C2

C1 atau

C2

Bentuk umum fungsi tujuan maks./min. Z = C1 X l + C2X2

Jika ditulis dalam bentuk y = aX + b X2 = - C1/C2X l + Z/C2

Garis Z koefisien arahnya adalah - C1/C2. Garis Z dapat makin datar atau makin tegak.

Garis tersebut makin datar jika nilai C1 turun atau nilai C2 naik. Sebaliknya garis tersebut

makin tegak jika C1 naik atau C2 turun nilainya.

Agar titik optimal tetap pada titik optimal C (X1 = 3 dan X2 = 1 ) yang telah diperoleh

sebelumnya, koefisien arah dari garis Z dapat berubah dalam batas-batas tertentu.

Persoalannya adalah berapa besar perubahan nilai C1 dan C2 agar tetap optimal di titik

C.

Garis Z dari persoalan pabrik cat dapat bergerak pada daerah Z sejajar dengan garis (1)

dan (2).

Garis1 : 6X1 + 4X2 = 24 X2 = - 6/4 X1 + 24/4 X2 = - 3/2X1 + 6

Koefisien arah garis 1 -3?2

Garis 2 : X1 + 2X2 = 6 X2 = - 1/2 X1 + 6/2

29

Koefisien arah garis (1) adalah -3/2 dan garis (2) adalah -1/2.

Dengan demikian nilai C1/C2 = 1/2 : 3/2 atau C2/C1 = 2/3 : 2 Berapa kisaran C1 jika C2 tetap = 4 C1 / 4 = 1/2 : 3/2 C1 = 2 : 6 Titik optimal tetap pada titik C pada keuntungan cat luar C1 berada sebesar antara

$2.000 sampai dengan $ 6.000 dengan keuntungan cat dalam C2 tetap $ 4.000

Dengan cara yang sama diperoleh keuntungan cat luar C2 berada sebesar antara $ 3334

sampai dengan $10.000. dengan keuntungan cat luar C1 tetap $ 5.000 agar tetap optimal

pada titik C

NILAI PER UNIT DARI SUMBER

Pada kebanyakan model Programa Linier, kendala biasanya mewakili pemakaian sumber

yang terbatas. Ruas kanan merupakan batas tersedianya sumber. Pada bagian ini

dipelajari kepekaan dari penyelesaian optimal terhadap perubahan dari ketersediaan

sumber.

Nilai per unit dari sumber adalah tingkat perubahan dari nilai optimal dari fungsi tujuan

sebagai perubahan dari tersedianya sumber.

Dari persoalan pabrik cat kendala 1 dan 2 merupakan pembatasan pemakaian bahan

baku M1 dan M2. Ingin ditentukan nilai per unit dari kedua sumber tersebut.

Titik optimum dari persoalan pabrik cat adalah titik C. Titik C adalah perpotongan antara

garis 1 dan garis 2. Jika ketersediaan M1 berubah, maka. titik optimum C akan bergerak

sepanjang garis DG. Setiap perubahan M1 di luar garis tsb. tidak layak, karena titik

optimal tidak lagi berada pada perpotongan antara garis 1 dan 2. (lihat gambar berikut).

Dengan demikian titik D (2,2) dan titik G (6,0) merupakan daerah yang memenuhi syarat

bagi pergerakan M1.

D

M1=36

M1=20

G

30

Pada saat garis M1 melalui titik D diperoleh (dengan memasukkan koordinat titik D) nilai

ruas kanan sebesar 20 dan melalui titik G nilai ruas kanan sebesar 36. Dengan demikian

range nilai M1 20 < M1 < 36. Jika D1 adalah nilai perubahan bahan baku M1 , dengan

M1 = 24 + D1 maka range nilai D1 : - 4 < D1 < 12. Dengan demikian agar menjamin titik

C tersebut tetap merupakan perpotongan antara M1 dan M2 maka bahan baku M1 dapat

turun paling banyak sebesar 4 ton dan dapat naik sebanyak 12 ton.

Nilai Z pada saat titik optimum berada pada titik D adalah 18 dan pada saat berada di titik

G nilai Z = 30

NILAI PER UNIT DARI SUMBER ADALAH YI :

Perubahan jumlah sumber i akan mempengaruhi nilai Z. Setiap unit perubahan nilai

sumberi i memberikan perubahan nilai Z sebesar Yi, di mana :

Perubahan nilai Z dari titik D sampai titik G Yi = ---------------------------------------------------------- Perubahan nilai M l dari titik D smpai titik G

Dengan demikian nilai Y1 = 2036

1830

= 3/4

Dengan cara yang sama diperoleh :

Y2 = 43/20

203/60

= 1/2

Y3 = 2/31

2121

= 0

Y4 = 2/32

2121

= 0

modul 1 model pl

Documents