BAB I

MASALAH OPTIMASI
A. Masalah Optimisasi
Dalam hidup sehari-hari manusia cenderung untuk hidup berprinsipkan ekonomis,
dengan usaha sesedikit mungkin dapat memperoleh hasil sebanyak mungkan. Banyak hal
yang dicari nilai optimumnya misalnya pendapatan maksimum, ongkos maksimum, hidup
yang paling nyaman, … dsb, maka timbullah masalah optimisasi.
Apabila gejala yang dioptimumkan di atas ternyata kuantitatif, maka masalah optimum
menjadi masalah ekstrem yang tak lain adalah maksimum dan minimum. Karena yang
akan dibahas hanyalah maslah kuantitatif maka istilah optimum dan ekstrem akan
digunakan kedua-duanya dengan arti yang sama. Dalam pelajaran kalkulus. Pasal ekstem
tadi sebagian sudah dibahas, maka dibawah ini pembicaraan akan dimulai dengan
meninjau ulang masalah ekstrem untuk kemudian sampai ke masalah program linear.
1. Optimisasi Fungsi Tanpa Kendala
Bila diberikan fungsi satu peubah, , yang terdiferensialkan n + 1 kali, maka lewat
penderetan taylor di sekitar X0dapat disimpulkan bahwa :
Bila f ' (X0) = f" (X0) = … = f''' (X0) = 0, sedangkan fn +1(X0) ≠ 0.
i) Untuk n genap : terdapat titik infleksi bagi f (X) di (X0)
ii) Untuk n gasal : terjadi ekstrem
fn +1(X0)< f (X) mencapai maksimum di X0
fn +1(X0)> f (X) mencapai minimum di X0
contoh A.1 :
a. Y= f (x) = sub x, maka
f '(x) = cos x
f"(x) = - sin x
untuk x = π /2, f ' (π /2) = 0
f"(π /2) = -1
jadi di sini n = 1 (gasal), sehingga terjadi ekstrem
karena f"(π /2) < 0 maka sin x mencapai maksimum untuk x = (π /2) +2kπ .
untuk x = 3 f ' (π /2) = 0
f"(π /2) = 1
karena f"(3π /2) < 0 maka sin x mencapai minimum di x = 3π /2 +2kπ .
b. y = f(x) = x4 -4x3
f '(x) = 4x3- 12x2 = 4x2(x-3)
f"(x) = 12x2 – 24x = 12x (x-2)
untuk x = 3, f '(3) = 0 f"(3) =36 > 0, maka y mencapai minimum di x = 3
 untuk x = 0, f '(0) = 0 f"(0) = > 0, f'''(0) = -24 ≠ 0. jadi di sini n genap, maka di x
= 0 terjadi titik infleksi stasioner ( pada grafiknya garis singgung di titik infleksi
akan mendatar)

untuk fungsi dua perubah dengan rumus : z = F(x,y) yang terdiferensial dua kali bila
di P (x0,y0)dipenuhi :
δz δz
=0 = 0 ( syarat stasioner)
δx δy
2
δ 2z δ 2z δ 2z 
∆= − > 0 . Maka z akan mencapai ekstrem di P (x0,y0)
δx 2 δy 2 δxδy 

Lebih lanjut bila :

δ z2
> 0 , maka yang timbul adalah ekstrem minimum
δx 2
δ z2
< 0 , maka yang timbul adalah ekstrem maksimum
δy 2

Contoh A.2 :
Produksi dua macam sepatu (s1 dan s2) memberikan fungsi laba bulanan sbb :
= -x2 - xy - 2y2 + 5x +13y
Dengan L : laba
x : tingkat produksi S1 ( banyaknya S1 yang diproduksi)
y : tingkat produksi S2 ( banyaknya S2 yang diproduksi)
dicari nilai (x,y) yang memaksimumkan L

penyelesaian : dari syarat stasionel diperoleh P(1,3) sebagai titik stasioner dan telah
dihitung ditemukan bahwa ∆ = 7 ( positif), sehingga L mencapai ekstrem di (x,y) =

δ 2 z 
(1,3). Lebih jauh  2  = -2 (negatif), berarti ekstrem maksimum, sehingga
 δx 
disimpulkan bahwa supaya laba maksimum sebaiknya diproduksi 1 unit S1 dan 3 unit
S2 perbulan ( satu unit berarti 1000 pasang sepatu)
Ekstrem-ekstrem di atas disebut ekstrem stasioner karena terjadi saat nilai turunan
menjadi nol. Ternyata ada jenis ekstrem yang lain seperti diuraikan dalam
pembahasan berikut.

2. Optimisasi Fungsi dengan Kendala

Contoh A.3 :
 Pagar kawat sepajang 24 m akan digunakan memagari kandang ayam berbentuk
persegi panjang. Bagaimana ukuran kandangg supaya luasnya maksimum ?
Penyelesaian :
Misalkan p : panjang kandang
q : lebar kandang, maka luasnya L = pq
sedangkan kelilingnya 2 (p + q) = 24
soal menjadi :
mencari p dan q (tak negatif) yang memaksimumkan L = pq dengan syarat bahwa 2 (p
+ q)

soal ini disebut soal ekstrem fungsi 2 perubah dengan kendala berbentuk persamaan

untuk menyelesaikan contoh ini soal dapat di ubah menjadi soal ekstrem fungsi 2
perubah tanpa kendala dengan cara mengeleminasikan salah satu perubahnya
misalnya q sbb :
tulis q = 12 – p, dan L = p(12 – p) harus dimaksimumkan. Didapati p = 6,
sehingga q = 6 dan memberikan L maksimum 36.
Ini berarti bahwa kandang harus dibuat dengan ukuran 6 m kali 6 m ( berarti
berbentuk bujur sangkar)

Contoh A.4 :
Tentukan semua ekstrem fungsi F(x) =x2 bila -1≤ x ≤ 2
Ternyata di samping x = 0 yang memberikan ekstrem minimum (stasioner) terdapat
pula x = -1 dan x = 2 yang sama-sama memberikan maksimum bagi f(x).
lihat gambar 1.1

Gambar 1.1
x
Kedua ekstrem ini bukan ekstrem stasioner tetapi disebut ekstrem batas, karena timbul
pada batas daerah x. soal seperti ini di sebut soal ekstrem dengan kendala berbentuk
pertidaksamaan, karena perubah tak gayui ( variable bebas) x harus memenuhi kendala
(syarat) berbentuk pertidaksamaan.
Suatu fungsi linear seperti f (F(x,y) = 100 – x – y tidak mempunyai ekstrem stasioner

δf δf
karena Dan δy tidak pernah menjadi nol. Tetapi bila kepada x dan y diberikan
δx
kendala misalnya : x ≤ 0 dan y ≤ 0, maka f akan mencapai minimum 40 di (x,y) =
(40,20). Ekstrem di sini juga beruupa ekstrem batas. Jenis ekstrem seperti inilah yang
terutama dijumpai dalam pembahasan program linear.
RUMUSAN UMUM
Secara umum masalah dengan kendala dapat dirumuskan sbb :

a. Ekstrem dengan kendala berbentuk peersamaan :

Mencari xj yang mengoptimumkan f = F(x1,x2,x3, …, xn) dengan kendala gj
(x1,x2,x3,…,xn) = 0, i = 1,2,3,…,m.
b. Ekstrem dengan kendala berbentuk pertidaksamaan :
Mencari xj yang menoptimumkan f = F(x1,x2,x3, …, xn) dengan kendala gj
(x1,x2,x3,…,xn) (≤ , =, ≥ )0, i = 1,2,3,…,m
(sedangkan (≤ , =, ≥ ) dimaksudkan setiap kendala memilih satu di antara ketiga
relasi dan tidak harus semua sama.
3. Masalah Program Linear
Sebagai kejadian khusus daari butir (rumusan umum) di atas, jika f dan semua g linear
sedangkan xj juga harus memenuhi syarat tak negative : xj ≥ 0, j =1,2,3,…,n, maka
masalah ini disebut masalah program linear ( disingkat PL)
Jadi ekstrem dalam PL selalu berupa ekstrem batas.
Secara umum, masalah program linear dapat dirumuskan sbb :

Mencari x1,x2,x3, …, xn yang memaksimumkan (atau meminimumkan) :

F = c1x1+c2x2+…+cnxn
Dengan kendala :
a11x1+a12x2+…=a1nxn (≤ , =, ≥ ) b1
a21x1+a22x2+…=a2nxn (≤ , =, ≥ ) b2
……………………………………….
am1x1+am2x2+…=amnxn (≤ , =, ≥ ) bm

Rumusaan tersebut dapat diringkas sbb :

Mencari xj.j = 1,2,…,n yang memaksimumkan (meminumkan)
f = Σc j x j
1

Dengan kendala
n
Σai x j ( ≤, =, ≥)bi i = 1,…,m
j =1

xj ≥0 j = 1,…,m
Dengan cara tulis matrik dapat ditulis :
Mencari x yang memaksimumkan (meminimumkan)
 f=CX
dengan kendala
AX(≤ , =, ≥ ) B
Dengan
 x1   b1 
x  b 
X =  2 Amxn = ( xij ) B= 2 C = ( c1 , c 2 ,..., c n )
 ...   ... 
   
 xn  bm 

Contoh A.s :
Mencari x dan Y yang memenuhi :
x+y ≤ 8
3x + y ≥ 0
2x + y ≥ 2
x≥ 0
y ≥ 0, dan
memaksimumkan
f(x,y) = 50 x + 100 y

B. Rangkuman
Jika dibentuk himpunan komponen penyusun masalah optimisasi fungsi tanpa kendala
(misal A) : himpunan komponen penyusun masalah optimisasi fungsi dengan kendala
(misal B): dan himpunan komponen penyusun masalah program linear (misal C), maka
hubungan antar komponen

Fungsi
Sasaran Kendala

Kendala linear
& Xi tak-negatif

Fungsi
Sasaran A B
Gambar 1.2

BAB II
MODEL MATEMATIKA
Dalam hidup sehari-hari selalu ada saja masalah yang dihadapi oleh suatu Negara suatu
perusahaan, atau oleh seseorang tertentu. Secara umum masalah (problem) dapat
ditafsirkan sebagai suatu kesenjangan antara cita-cita (tujuan) dan keadaan sekarang.
Menyelesaikan masalah berarti menjembatani kesenjangan diatas.
Analisis system membeerikan langkah-langkah penyelesaian sbb :
1. mengindetifikasi (mempertegas) masalahnya,
2. mencari metode-metode penyelesaian :
3. memilih metode yang paling cocok, paling murah, atau paling cepat (optimisasi)
4. melaksanakan (implementasi)
5. mengevaluasi hasil
apabila masalah nyata di atas atau ssebagian masalah tersebut bersifat komutatif maka
matematika dapat membantunya. Pada langkah 1. matematika berusaha untuk
merumuskan masalah dalam arti menerjemahkan masalah ke bahasa matematika (misal
menjadi suatu bentuk aljabar). Kerja ini disebut menyusun model matematis dari masalah
di atas. Hasilnya ( misalkan berupa relasi aljabar) disebut : model matematis bagi
masalah tersebut.
Tentu saja suatu model tidak dapat menggambarkan masalahnya dengan tepat karena
untuk sampai ke model. Masalah nyata sudah mengalami beberapa penyederhanaan
(karena adanya asumsi-asumsi). Tetapi model di usahakan sedekat mungkin dengan
aslinya.
Penyelesaian model (berarti penyelesaian soal matematika) tergantung kepada pasal
matematika yang terkait dengan model. Pada umumnya semakin dekan model dengan
aslinya makin sulit model diselesaikan. Sebaliknya, makin bayak anggapan-anggapan
(penyederhanaan) maka model makin mudah diselesaikan meski dengan hasil yang
kurang teliti
B. Pemodelan Masalah Program Linear
Pola umum atau skenario masalah yang dapat dimodelkan dengan program lineat sbb :
• adanya pilihan komnbinasi beberapa faktor kegiatan
• adanya sumber penunjang beserta batasnya
• adanya fungsi sasaran yang harus dioptimumkan
• relasi yang timbul antaraa faktor-faktor semuanya linear
contoh B.1
sekelompok petani transmigran mendapatkan 6 ha tanah yang dapat ditanami padi,
jagung dan palawija lainnya. Karena keterbatasan sumber daya petani harus menentukan
berapa bagian yang harus ditanami padi dan berapa yang harus ditanami jagung, sedang
palawija lain ternyata tidak menguntungkan.
Dalam satu masa tanam, tenaga yang tersedia hanya 2590 jam-orang, pupuk juga
terbgatas, tak lebih dari 480 kg, sedangkan air dan sumber daya lainnya dianggap cukup
tersedia
Diketahui pula bahwa untuk menghasilkan 1 kuintal padi diperlukan 12 jam-orang tenaga
dan 4 kg pupuk, dan untuk 1 kuintal jagung diperlukan 9 jam-orang tenaga dan 2 kg
pupuk. Kondisi tanah memungkinkan menghasilkan 50 kuintal padi ha atau 20 kuintal
jagung per ha
Pendapatan petani dari 1 kuintal padi adalah Rp. 32000,- sedangkan dari 1 kuinttal jagung
Rp. 20.000,- dan dianggap bahwa semua hasil tanamnya selalu habis terjual
Masalah bagi petani adalah bagaimana rencana (program_ produksi yang
memaksimumkan pendapatan total ? artinya berap ha tanah ditanami padi dan bewrapa
yang ditanami jagung
Perumusan Masalah
Melihat ketentuan-ketentuan yang diketahui, lebih baik bila diandaikan sebagai perubah
bebasnya bukan banyak hektar tanah ( untuk padi dan untuk jagung), melainkan
banyaknya keintal kebutuhan tanah untuk 1 kuintal padi menjadi 0,02 ha sedangkan
untuk 1 kuintal jagung 0,05 ha
Untuk mempermudah penyusunan model, disusun tabel pertolongan sbb :
perkuintal
sumber batas sumber satuan
padi jagung
tanah 0,02 0,05 ≤6 ha
tenaga 12 9 ≤ 1590 jam-orang
pupuk 4 2 ≤ 480 kg
pendapatan 32 20 maksimum Rp. 1000
Catatan :
• Satuan jam-orang adalah banyaknya orang kali banyak jam bekerja
• Air dianggap berlimpah sehingga bukan kendala ( jika ada dendala air,
maka satuannya adalah banyak jam membuka salutan tesiet untuk mengalirkan air)
• Batasan sumber tersebut kebetulan semuanya berupa batas atas
Misalkan x : banyak kuintal padi yang diproduksi
y : banyak kuintal jagung nayg diproduksi
maka keterbatasan tanah akan menimbulkan kendala yang berbunyi “ banyaknya ha tanah
yang diperlukan untuk x kuintal padi dan untuk y kuintal jagung tidak boleh melebihi 6
ha”. Syarat ini dirumuskan sbb ; 0,02 x + 0,05 y ≤6
demikian pula untuk syarat tenaga, akan dirumuskan sbb: 12 x + 9 y ≤1590. untuk
syarat pupuk dirumuskan sbb ; 4 x +2 y ≤480
mengingat s dan y di sini mewakili besaran yang tidak boleh negatif, maka harus
ditambahkan syarat tak negatig bagi keduanya, x ≥0 dan y ≥ 0
terakhir dirumuskan besarnya pendapatan total yang harus dimaksimumkan ialah
f = 32x + 20 y (satuan dalam ribu rupiah)
bila disederhanakan, relasi-relasi di atas akan menjadi

Mencari x dn y yang memenuhi :

x ≥0 (1)
y ≥0 (2)
2x + 5y ≤ 600 (3)
4x + 3y ≤ 530 (4)
2x + y ≤ 240 (5)
Dan memaksimumkan : f = 32x + 20 y (6)

Keterangan ;
• Relasi 1 dan 2 disebut kendala tak negatif
• Relasi 3,4, dan 5 disebut : kendala utama
• Relasi 6 disebut fungsi sasaran
• Perubah s dan y disebut perubah keputusan
• Koefesien kendala utama disebut koefesian teknis
• Suku tetap ruas kanan kendala utama disebut : suku tetap
• Koefisien fungsi sasaran disebut : koefesian ongkos
Setelah dirumuskan, semua relasi dalam model di atas ternyata linear dalam x dan y,
maka memang masalah diatas termasuk masalah program linear.
Menyatakan bahwa relasi dalam kendala maupun fungsi sasaran adalah linear secara
matematis sebetulnya sudah cukup jelas, tetapi para penyusun model kadang-kadang
masih merincinya atas beberapa asas sbb :
• Kesebandingan (proportionality)
Misalkan fungsi sasaran f = 32x + 20 y. Bila di x dilipatkan 2 maka peran serta padi
dalam fungsi sasaran ( yaitu 32 x) akan berlipat 2 juga. Benarkan bahwa bila
seorang tukang batu bekerja 4 jam pada pagi hari dapat memasang batu bata
sebanyak ½ m3. maka bila dia bekerja 8 jam ( dari pagi sampai sore) dia pasti dapat
memasang i m3?
• Keterjumlahan ( additivity)
bila laba dari padi sebesar 32 x dan laba dari jagung sebesar 20 y, maka laba total
diperoleh dengan menjumlahkan keduanya sehingga menjadi 32x + 20 y, ini adalah
asas keterjumlahan
• Dapat Terbagi ( divisibility)
• Perubah keputusan boleh bernilai bilangan pecahan dan tidak harus bulat
Gontoh B.2
Sebuah pabrik yang menggunakan 2 tanur (TB : tanur biasa ; TT: tanur padas tinggi)
untuk produksinya dinyatakan mencemari linggkungan lewat asapnya yang ternyata
 mengandung beleran oksida dan hidrokarbon melebihi ambang yang diperbolehkan.
Pemilik menyusun tim peneliti yang bertugas mengatasinya.
Tabel 2.2 tabel pengurangan kadar pencemaran
Saringan Ganti BBM
TB TT TB TT
belerang
30 20 50 80
oksida
hidrokarbon 18 22 20 16

Tim mengusulkan adanya 2 magam jalan ke luar ialah : pemasangan saringan, dan
penggatian BBM yang digunakan disertai dengan pengaturan banyaknya TB dan TT yang
dikenai pencegahan di atas. Dari hasil penelitian diperoleh data penguranan pencemaran
terkait dengan keempat usaha di atas
Pabrik tersebut tercatat membuat pencemaran dengan kelebihan 200 satuan belerang
oksida dan 100 satuan hidrokarbon dari ambang yang diperbolehkan maka penyusutan
masing-masing paling tidak harus sama dengan angka kelebihan di atas
Diketahui bahwa dana untuk satu satuan usaha terkait dengan jenis tanur adalah sb :

Saringan BBM
TB 6 10
TT 8 12
Disyaratkan pula bahwa jumlah satuan kedua macam usaha untuk TT tidak boleh lebih
dari 20 % dari seluruh usaha
Berapa satuan masing-masing usaha sebaiknya dilaksanakan sehingga semua kendala
dipenuhi dan dengan biaya total minimum ?
Perumusan
Suatu satuan usaha dapat berupa pnggantian satu unit satingan, atau beda jumlah
penggunaan BBM yang baru dengan yang lama, dsb.
Dari uraian di atas terlihat bahwa terdapat 4 faktor yang ukurannya akan menjadi
perubah-perubah bagi model masalah ini, yaitu keempat macam satuan usaha di atas
Misalkan : X1 = banyak satuan usaha saringan untuk TB
X1 = banyak satuan usaha saringan untuk TT
X3 = banyak satuan usaha ganti BBM untuk TB
X4 = banyak satuan usaha ganti BBM untuk TT
Syarat terakhir dapat dirumuskan, sbb :
X2 + X4 ≤1/5 (X1 + X2 + X3 + X4)
Atau diringakas ;
- X1 + 4 X2 – X3 + 4 X4 ≤0
Tabel 2.3
Tabel Usaha Mengatasi Pencamaran

X1 X2 X3 X4
Belerang oksida 30 20 50 80 ≥ 200
hidrokarbon 18 22 20 16 ≥ 100
Syarat tambahan -1 4 -1 4 ≤ 0
Biaya total 6 8 10 12 minimal

Selanjutnya perumusan menjadi

Mencari X1,X2, X3, X4 tidak negative yang memenuhi
30 X1+ 20 X2 + 50 X3 + 80 X4 ≥ 200
18 X1+ 22X2 + 20 X3 + 16 X4 ≥ 100
- X1 + 4 X2 – X3 + 4 X4 ≤ 0
Dan meminimumkan f = 6 X1+ 8X2 + 10X3 + 12 X4
Catatan :
• Soal ini berpola minimum, sedangkan contoh B.1. berpola maksimum
• Kendala dapat timbul dari berbagai macam alas an, misalnya syarat-sayarat
peraturan dsb, jadi tidak harus bersifat sumber sungguhan
C. Rangkuman
• Langkah-langkah penyelesaian masalah dengan bantuan model matematika :

Masalah Penyederhanaan Masalah yang pemodelan Model

nyata disederhanakan Matematika

Penyelesaian

pelaksanaan Penyelesaian tafsir Penyelesaian

Masalah Nyata dalam model

Pola masalah yang dapat dimodelkan dengan program linear sbb :

o Adanya pilihan kombinasi beberapa fakror kegiatan
o Adanya sumber penunjang beserta batasnya
o Adanya fungsi sasaran yang harus dioptimumkan
o Relasi yang timbul antara faktor-faktor semuanya linear
D. Latihan
Apakah permasalah berikut termasuk masalah PL :
1. mencari alas an X,Y tak negative yang memenuhi 3X – Y ≥ 0 ; X + Y ≤ 5, dan
meminimumkan f = 20XY – X + Y
2. tentukan nila X yang memaksumumkan fungsi f = 3X4 + 4X5 + 12 X6
3. tentukan semua titik optimum(maksimum dan minimum) fungsi f = 2X – X – 4
bila daerah asal dibatasi sbb : -1 < X ≤ 1 : -1 < X ≤ 1
4. alcohol dapat dihasilkan dari 3 macam buah-buahan A,P dan V, dan masing-
masing dapat diolah dengan 2 macam proses misalnya AAAAAI = buah A
diproses menurut cara dan A = buah A diproses menurut cara 2 dst. Berturut-
turut, A1, A2, P1, P2, V1, dan V2 dapat menghasilkan alkohol sebanyak 3%, 2,5
%, 3,5 %, 4%,5% dan 4,5% dari berat buah sebelummya, kapasitas mesin adalah
ton buah-buahan per hari dan selalu dipenuhi pemborong yang menyuplai buah A
hanya mau melayani jika paling sedikit masuk 400 kg pe hari sebaliknya buah P
dan V masing-masng hanya dapat diperoleh 350 kg per hari. Program manakah
yang harus dipilih supaya hasil alkohol perharinya maksimum ?
5. sebuah perusahaan akan membeli paling sedikit buah mesin untuk perluasan
pabriknya. Harga yang baru 5 juta per unit. Di luar juga dapat dibeli mesin bekas
dengan umur 2 tahun, 3 tahun, dan 4 tahun yang harganya diukur dari harga baru
akan susut 3 juta pertahunnya keepat jenis di atas yang baru umur 2 tahun, 3
tahun, dan 4 tahun mempunyai ukuran yang berbeda-beda, berturut-turut akan
memakan tempat 3, 4, 5, dan 6 m per unitnya sedangkan ongkos perawatanyaan
berturut-turut 0, 1, 2, dan 4 juta pertahunnya bila tempat yang tersedia untuk
semua mesin yang dibeli tersebut hanya 5 m dan ongkos perawatan total yang
disediakan hanya juta pertahun, berapa unit dari jenis-jenis mesin diatas
sebaiknya dibeli supaya batas-batas kendala tidak dilanggar dan uang pembelian
total mimimum ?
6. (Trimming Problem: masalah sisa pemotongan). Saya akan membuat rak buku
yang kerangkanya terbuat dari besi siku lubang yang dipotong-potong kemudian
dirangkai dengan sekkrup. Untuk rak saya tersebut diperlukan potongan
sepanjang 5 cm sebanyak buah, panjang cm diperlukan potongan sepanjang5 cm
sebanyak buah, panuang cm sebanyak buah, dan panjang ,5 cm sebanyak
potong. Ternyata batangan besi siku lubang yang dijual di took mempunyai
panjang standar 3 m, sehingga saya harus berpikir cukup berapa batang besi yang
saya beli, dan bagaimana cara mengatur pemotongannya supaya panjang total sis
potongan minimal (dengan demikian kerugian saya mimimal)
7. (Caterer Problem : Napkin Problem). Untuk melayani komperensi selama hari
harus disediakan serbet maka. Untuk hari 1,2,3 berturut-turut diperlukan 40,70,60
 helai serbet makan. Harga beli baru Rp. 200 sehelai. Ongkos mencuci kilat
(semalam siap) Rp. 80 Per helai. Untuk meminimalkan ongkos total, berapa helai
harus dibel, berapa bekas hari ke harus dicuci kilat (untuk hari ke 2) dan dicuci
biasa (untuk hari ke 3) dan berapa bekas hari ke 2 harus dicuci kilat (untuk hari
ke 3).
8. biro iklan membuat rencana acara TV selama 30 menit yang diisi komidi diselingi
iklan. Biro iklam minta untuk iklan tersedia paling sedikit 3 menit sedang dari
pihak TV mensyaratkan bahwa iklan tak boleh lebih dari 5 menit dalam sekali
penampilan. Pemain komidi dapat main paling lama 22 menit. Di samping itu ada
band yang mau main selam kekosongan komidi atau iklan , dan
9. masalah campuran produk (Produk-Mix Problem). Sebuah perusahaan
memfaktur, memproduksi 2 macam produk (yaitu A dan B) yang masing-masing
diproses melalui 2 departemen (D1 dan D2). Produk A memerlukan 3 jam per-
unit di D1 dan 4 jam per-unit di D2, sedangkan produk B memerlukan 2 jam per-
unit di D1 dan 6 jam per-unit di D2. kapasitas maksimum jam kerja di unit D1
dan ^ jam per unit di D2 adalah260 jam. Setiap unit produk A akan mendatangkan
keuntungan 5, sedangkan setiap unti produk B mendatangkan keuntungan 6.
Tentukan berapa jumlah Produk A dan Produk B dibuat agar mendatangkan
keuntungan maksimum ?
10. model campruan Diet (Diet-Mix-Problem). Seseorang yang sedang melaksanakan
diet, merencanakan menu makan siang yang terdiri dari 3 macam bahan makanan,
yaitu A, B, C sebanyak paling sedikit gram. Diketahui bahwa pada setiap gram
A mengandung 50mg Vitamin- 1; 20 mg vitamin-2, dan 10 mg vitamin-3. pada
setiap 100 gram B mengandung 30 mg vitamin-1;10 mg vitamin-2, dan 50mg
vitamin-3. sedangkan pada setiap 100 grtam C mengandung mg vitamin-1; 30
mg vitamin-2; dan 20 mg vitamin-3. harga bahan makanan per-100 gram berturut-
turut adalah 0,10 ; 0,15 ; dan 0,12. diperoleh informasi pula bahwa kebutuhan
mimimum ketiga vitamin tersebut berturut-turut adalah 290mg; 200 mg; dan
210mg. tentukan komposisi menu dengan ongkos minimum ?
11. model penganngaran modal (Capital Budgering Modeal). Seorang pengusaha
memiliki dan 1.000.000,- akan diinvestasikan dalam beberapa usaha. Terdapat 6
buah usaha layak investasi, yaitu A, B, C, D, E, dan f. dari studi kelayakan
tehadapa calon usaha tsb, diperoleh informasi sbb :
12. masalah Transportasi (Transportation Problem). Terdapat sebuah bahan pangan
yang harus didistirbusikan dari 3 daerah produsen (yaitu :P1,P2, dan P3) menuju
3 daerah konsumen (yaitu; K1, K2, dan K 3 ). Kapasitas terpasang dari ke-3
produses berturut-turut adalah 100, 90, 120 satuan. Permintaan akan bahan
 pangan tersebut berturu-turut adalah : 70,100,60. Sedangkan ongkos kirim C11 = 4
(dari P1-K1); c12 = 6; c13 = 5; c21 =10 ; c22 = 3 ;c23 = 4 ; c31 = 6 ; c32 = 8 ; c33 = 7.
persoalan : bagaimana pola distribusi bahan pangan tersebut agar total biaya
transpotasi minimum
13. sebuah perusahaan mainan memproduksi mainan-mekanik, yaitu : tuk dan kapal.
Mainanm truk dijual dengan 5 dan kapl dijual dengan 7 per-unit. Ongkos produksi
per-unit berturut-turut sebesar 3 dan 5 perusahaan tidak memiliki hambatan dalam
pemasarannya. Divisi yang terkait dengan proses produksi adalah divisi
pembuatan komponen penyusu mainan mamakan (divisi-A), dan divisi perakitan
komponen ( divisi-B ). Jikalau dibisi-A hanya mengerjakan produk truk saja,
maka dalam 1 bulan dapat menghsilkan 1 juta set komponen mainan truk. Namum
jika hanya mengerjakan kapal saja , maka hanya dapat diselesaikan ½ -nya saja
sedangkan dibisi-B dapat melakukan perakitan maksimum 0,8 juta mainan (Truk
dan kapal), setiap bulan. Jikalau anda manajer produksi. Rencanakan jumlah
produksi kedua macam maninan agar diperoleh keuntungan perusahaan
maksimum
14. subuah prudusun pipa menerima pesanan untuk memproduksi pipa dengan
beberapa spesifikasi berikut :
15. seorang manajer pemasaran [Link] AAA alam ,emgiklankan beberapa barang
dagangan baru pada Koran A atau Koran B, masing-masing 1 halaman penuh.
Tarip pada koran A= 60 dan pada koran B =50, setiap kali muat. Manajer tsb
berharap agar setiap kali iklan muncul pada koran A terdapat penambahan
pembaca iklan sebesar 2.000 orang pembava dari pelanggan-tetap koran tsb.
Sedangkan jika muncul di koran B terdapat penambahan pembaca sebesar 1000
orang pembaca. Sedangkan bagi pembaca bukan pelanggan, manajer berharap
memperoleh penambahan pembaca iklan sebesar 3000 (koran A), dan 4000
(koran B). Dalam perhitungan sang manajer titik impas akan dicapai jika promosi
tersebut dapat menjangkau sekurangnya 50.000 pelanggan-tetap koran dan 90.000
bukan pelanggan. Berapa hari sebaiknya iklan dipasang pada kedua koran tsb agar
biaya minimum dan tetap memenuhi titik impas.
16. Teori Comparative Advantage. Dua negara akan berdagang macam produk,
namakan X1 dan X2. kedua negara tersebut namakan A dan B. pada negara A,
produksi dari setiap 1 satuan X1 dapat digantikan dengan produksi 1 satuan X2
dan sebaliknya. Sedangkan pada negara B produksi dari setiap 1 satuan X1 dapat
digantikan dengan 2 satua X2. sebaliknya (satuan barang untuk untuk kedua
produk sama). Pada pasar internasional telah disepakati harga X1 = pl. dan harga
X2 = p. Pada kondisi tertentu, jika kedua negara melakukan spesialisasi maka
 kedua negara akan lebih makmur dan produksi du/da akan menjadi optimal. (teori
comparative advantage). Tinjau negara B, jika term-of-trade (perbandingan nilai
tukar kedua barang = p1/p2) bernilai 1.5 dan produksi maksimum sebesar 6
satuan (jika hanya membuat produk X2 saja). Berikan solusi terbaik untuk negara
B berapa banyak produksi X1dab X2

BAB III
DAERAH LAYAK, GARIS SENILAI, PENYELESAIAN OPTIMUM
 A. Daerah Layak, Garis Senilai, Penyelesaian Optimum
Contoh . : lihat masalah produksi pada contoh2.1 di depan
Perumusan masalah berbunyi :
Mencari x dan y yang memenuhi
x ≥0
y ≥0
2x + 5y ≤ 600
4x + 3y ≤ 530
2x + y ≤ 240
Dan memaksimumkan f = 32x + 20y
Himpunan penyelesaian dari sistem pertidaksamaan (1 s.d 5) berupa kumpulan pasangan
terurut (x,y) yang membentuk daerah tertutup OABCD. Perhatikan gambar 3.1

D
C
B(95,50)
F

A X
2 O 4 3
5
f = 100 f = 4040
Gambar 3.1

Pasangan (x,y) yang memenuhi semua kendala di atas (1 s.d 5) disebut penyelesaian
layak. Sedangkan titik wakilnya di dalam bidang koordinat disebut titik layak. Himpunan
titik layak disebut daerah layak pada contoh di atas adalah daera segilima OABCD
termasuk batasnya (F)
Sekarang ditinjau fungsi sasaran f = 32x + 20y. Untuk menggambarkan fungsi ini
diperlukan ruang dimensi 3, kecuali jika kepada f diisikan nilai tetap, yaitu 32x + 20y =
k (tetap), lalu dapat dilukis dalam bidang. Grafik fungsi sasaran ini berupa garis lurus dan
disebut garis senilai (isofuant, isoprofit, isocost), karena menggambarkan pasangan-
pasangan (x,y) yang memberikan nilai f yang sama
Y

40

f = 800 f = 1000 f = 2000 X

Pada gambar tersebut terlukis 3 garis senilai, ialah f = 800 (berarti 32x + 20y = 800, dan
melalui (0,40)), kemudian f = 1000 dan f = 2000. jelas bahwa ketiga garis saling sejajar
dengan gradien -8,5.
Lebih jauh dapat disimpulkan bahwa makin ke kanan garis senilai digeser makin besar
nilai f yang diberikan.
Kembali ke soal semula. Yang dicari ialah penyelesaian optimum (optimum solution),
disingakta p.o. yaitu penyelesaian layak yang memaksimumkan nilai f. secara gambar
berarti mencari anggota F yang membuat nilai f sebesar mengkin ini terjadi dengan cara
menggambasr 2 garis senilai, misalnya f = 1000 dan f = 2000, melihat arah membesarnya
f lalu menggeser garis senilai kea rah itu sampai ke titik irisannya dengan f yang terakhir.
Titik itulah titik optimum sebagai gambar dari p.o.
Karena kedua garis senilai yang dilukiskan di atas diperlukan guna menyelidiki
kemiringan (gradien) garis senilai dan arah membesarnya (arah pergeseran), maka
keduanya disebut juga sebagai garis selidik. (tidak cukup satu melainkan harus dua,
mengapa ?)
Dalam contoh titik terakhir F yang memberikan nilai f terbesar adalah titik B yaitu titik
potong batas kendala 4(4x + 3y = 530)dan batas kendala 5(2x + y = 240). Setelah
koordinatnya dihotung ditemukan titik optimum B(95,50) yang memberikan nilai f maks
= 4040. ini berarti p.o. sudah ditemukan, yaitu : (x,y) = (95,50) sedang nilai f maks =
4040. disebut nilai program
Penafsiran Kembali
Kembali ke masalah nyat, penyelesaian optimum berbunyi: untuk memaksimumkan
pendapatan total maka sebaiknya diproduksi 95 kuintal padi dan 50 kuintal jagung. Ini
berarti luas tanah untuk penanaman padi ial 1,9 ha dan untuk penanaman jagung 2,5 ja,
dan akan didapat pendapatan maksumum Rp.4.040.000,-
Dari segi kendala utama terlihat bahwa tanah masih bersisa 1,6 ha, sedangkan tenaga dan
pupuknya habis terpakai, maka kendala dan pupuk disebut kendala yang membatasi
(restrictive). Sedangkan kendala tanah tidak membatasi
Contoh 3.2 (Masalah Ramuan)
Suatu pabrik farmasi menghasilkan 2 macam kapsul obat flu yang diberi nama tluin dan
fluon. Masing-masing memuat tiga unsure utama dengan kadar kandungannya tertera
dalam tabel 3.1.
Menurut dokter seseorang yang sakit flu buasa akan sembuh bila dalam 3 hari (secara
diratakan) minimum menelan 12 grai aspirin, 74 grai bikarbonan dan 24grai kodein. Bila
harga fluin Rp.200 Dan fluon Rp. 300 per kapsul, bagaimana rencana (program)
pembelian seorang pasien flu (artinya berapa kapsul fluin dan berapa kapsul fluon harus
dibeli) supaya cukup untuk menyembuhkan dan meminimumkan ongkos pembelian total.
Tabel3.1 Kandungan Unsur (Dalam Grain)
Per kapsul
UNSUR
FLUIN FLUON
Aspirin 2 1
Bikarbonat 5 8
Kodein 1 6

X Y Batas
UNSUR
FLUIN FLUON Minimal
Aspirin 2 1 12
Bikarbonat 5 8 74
Kodein 1 6 24
Harga 200 300 24

Penyelesaian
Guna mempermudah perumusan disusun tabel persiapan (tabel 3.2.)
Dengan memisalkan x = banyak fluin yang dibeli dan y = banyak flaon yang dibeli maka
perumusan menjadi
Mencari x,y yang memenuhi :
2x + y ≥ 12 (1)
5x +8y ≥ 74 (2)
x+ 6y ≥ 24 (3)
x ≥ 0 (4)
y≥ 0 (5)
dan meminimumkan f = 200x + 300 y (6)
penyelesaian soal ini terlukiskan pada gambar 3.3.
daerah layak berupa daerah terluka PABCDQ, maka dikatakan bahwa daerah layak tak
terbatas (unbounded). Dengan melukis 2 garis selidik f = 0 dan f = 4000 disimpulkan
bahwa garis senilai mempunyai gradient -2/3 dan akan mengecil bila digeser ke kiri
(bawah).
Untuk menemukan titik optimum maka dimulai dari f = 4000 garis senilai digeser ke kiri
haingga sampai ke irisan yang terakhir garis tersebut dengan B, yaitu titik B (2,8) sebagai
perpotongan kendala -1 dan 2. inilah titik optimumnya
Nilai f yang sesuai ialah f = 2800, inilah nilai programnya yang berupa f minimum. Jadi
supaya uang pembelian total minimum sebaiknya dibeli 2 butir fluin dan 8 butir fluon,
dan uang pembeliannya adalah Rp. 2800.
.
Y

A
F

D
f =4000
f min = 2800
f =0

Contoh 3.3
Suatu soal PL berbunyi
Mencari u,v tak negative yang memenuhi
2u - v ≤ 4 (1)
3u + v ≤ 11 (2)
u + 2v ≤ 8 (3)
-u + 3v ≤ 3 (4)
Dan meminimumkan f = 100 – 20 u – 10v

Penyelesaian
Penyelesaian soal ini terlukiskan pada gambar 3.4.

Y (2)

D (4)

B
A
X
(3)
f =60 fmin =18
f=80 Gambar. 3.4
Soal tsb memuat δ kendala, yaitu: 4 kendala utama dan 2 kendala tak negative tetapi
daerah layak hanya berupa segiempat ABCD.
Dengan melukis 2 garis selidik, missal f = 80 (melalui (1,0)) dan f = 60 (melalui (2,0))
disimpulkan bahwa garis senilai yang mempunyai gradien (-2) itu akan memberi nilai f
yang mengecil bila digeser ke kanan (atas)
Titik optimumnya ditemukan di C(14/5,13/5) ialah perpotongan batas kendala-2 dan
kendala-3, sehingga [Link] ialah (u,v) = (14/5,13/5). dengan nilai program f min = 18
Pada kasus ini, tampak bahwa keenam kendala yang efektif menyusun F hanyalah empat
buah, yaitu u ≥ 0 dan kendala -2; kendala-3 dan kendala-4 sedangkan kendala u ≥ 0 dan
kendala -1 dengan sendirinya akan terpenuhi bila keempat kendala di muka sudah
terpenuhi. Jadi sebetulnya, kedua kendala terakhir itu dapat dilupakan (ditinggalkan).
Kendala u ≥ 0 dan kendala-1 lalu disebut berlebihan (redundant).
Contoh 3.4
Tentukan x, y, z yang meminimumkan f = 100x + 100y + 70z. dengan kendala
2x + 2y + z ≤ 22 (1)
Y + 2z ≤ 25 (2)
2x + y + 2z ≤ 30 (3)
x + ≥ 0 (4)
z ≥ 0 (5)
y ≥ 0 (6)
Penyelesaian
Soal dengan tiga perubah ini kebetulan memuat satu kendala yang berbentuk persamaan
(kendala) sehingga salah satu perubah dapat dieliminasikan dengan mcara menyatakan
dengan dua perubah yang lain
Degan demikian soal dapat disusutkan menjadi soal baru yang hanya memuat dua
perubah saja dan akan dapat diselesaikan dengan metode grafik
Penyusutan dikerjakan sebagai berikut :
Soal Asli Soal tersusut
(1) 2x + 2y + z ≤ 22
(2) y + 2z ≤ 25