PROGRAM LINEAR

PROGRAM LINEARSistem Pertidaksamaan Linear dengan Dua peubah

Kalimat matematika x + y £ 4 , y > 2x + 8 dan sejenisnya disebut pertidaksamaan linear dengan dua peubah. Himpunan penyelesaiannya digambarkan pada bidang Cartesius.

Contoh 1 :

Gambarkan grafik himpunan penyelesaian dari : x + y £ 4 , x , y Î R.

Jawab : 1. Gambar garis x + y = 4

Y Garis membagi bidang menjadi dua daerah.

2. Semua titik dari grafik himpunan penye-

5– lesaian x + y £ 4 terletak pada salah satu

4– daerah tersebut. Untuk menentukan daerah

3– grafik penyelesaian diambil titik yang tidak

2– terletak pada garis x + y = 4 , biasanya

1– titik (0,0).

0 1 2 3 4 5 6 X 3. Untuk x = 0 dan y = 0 kalimat x + y £ 4

menjadi benar, karena 0 + 0 £ 4. Artinya

titik (0,0) terletak pada grafik himpunan

penyelesaian dari x + y £ 4.

Gambar 5.1 4. Daerah penyelesaian ditunjukkan dengan

arsiran, seperti pada gambar 5.1.

Contoh 2 :

Gambar grafik himpunan penyelesaian dari : y > 2 x + 8 , x , y Î R.

Jawab : Y 1. Digambarkan garis y = 2 x + 8 dengan ga-

ris putus-putus, karena garis y = 2 x + 8

8 – tidak ikut dalam himpunan penyelesaian.

7 – 2. Ambil titik (0,0).

6 – Untuk x = 0 dan y = 0 kalimat y = 2 x + 8

5 – menjadi salah karena 0 > 0 + 8.

4 – 3. Daerah himpunan penyelesaian diarsir

3 – seperti gambar 5.2

2 –

1 –

-4 -3 -2 -1 0 X

Gambar 5.2

Contoh 3 :

Tentukan himpunan penyelesaian dari sistem pertidaksamaan 2 x + 3 y £ 12 , x ³ 0 ,

y ³ – 2 dan x , y Î R

Jawab : Y Himpunan penyelesaian dari sistem

5 x = 0 pertidaksamaan adalah irisan dari

(0,4) himpunan penyelesaian masing-ma

3– sing pertidaksamaan. Disini bagian

2– 2x + 3y £ 12 yang diarsir adalah daerah yang

1– bukan penyelesaian, sehingga

0 1 2 3 4 5 6 7 X daerah yang bersih menjadi him-

–1 – punan penyelesaian seperti tampak

–2 seperti gambar 5.3.

–3 – y = –2





Gambar 5.3

Latihan 1
Gambarlah grafik himpunan penyelesaian sistem pertidaksamaan berikut !
x ³ 4 , x, y Î R d. x ³ –2 , x, y Î R
y £ –3, x, y Î R e. y £ 4 , x, y Î R
3 x + y ³ 6, x , y Î R f. 3 x + 2 y > 18, x, y Î R
Gambarlah grafik himpunan sistem pertidaksamaan berikut untuk x , y Î R !
2 £ x £ 5 , 0 £ y £ 4
x + y £ 4 , x ³ 0 , y ³ 0
x + 2 y £ 4 , 2 x + 3 y £ 12 , x ³ 0 , y ³ 0
y £ 8 – x , y £ 3 , x ³ 0 , y ³ 0
Gambarkan himpunan penyelesaian sistem pertidaksamaan berikut untuk x , y Î R !
x + y ³ 4 , 2 x + y ³ 6 , x ³ 0 , y ³ 0
x £ 4 , y £ x , y ³ -x
2 x + 3 y ³ 12 , x ³ 2 , y ³ 2
x + y ³ 8 , x £ 8 , y ³ 0 , y £ x
Tentukanlah sistem pertidaksamaan dari daerah yang diarsir pada gambar berikut.

a. Y b. Y

4

6

4 2

0 X 0 X

4 8 –1 3






c. Y d. Y

4

3

2

1

–2 0 3 5 X 0 1 3 5 X

–1

B. Model matematika



Seorang ibu ingin membuat dua jenis roti. Untuk membuat jenis roti A diperlukan tepung 200 gram dan mentega 25 gram. Untuk jenis roti B diperlukan tepung 100 gram dan mentega 50 gram. Ibu ini ingin membuat roti sebanyak mungkin dari bahan yang tersedia yaitu tepung 4 kg dan mentega 1,2 kg, sedangkan bahan yang lain cukup.

Untuk menyelesaikan soal tersebut di atas dengan matematika, terlebih dahulu harus diterjemahkan ke dalam bahasa matematika yang disebut Model Matematika:
Roti jenis A Roti jenis B Persediaan
Tepung (gr) 200 100 4000
Mentega (gr) 25 50 1200


Misalkan banyaknya roti jenis A adalah x dan banyaknya roti jenis B adalah y, maka terdapat hubungan :

200 x + 100 y £ 4000 ® 2x + y £ 40 …… (1)

25 x + 50 y £ 1200 ® x + 2 y £ 48 …… (2)

karena banyak roti (x dan y) adalah bilangan bulat positif, maka

x ³ 0 …… (3)

y ³ 0 …… (4)

Persoalan selanjutnya mencari x dan y sedemikian hingga jumlah x dan y menjadi sebesar mungkin atau memaksimumkan x + y dengan syarat (1) sampai dengan (4).

Untuk itu dengan menggunakan model matematika, kita selesaikan soal di atas, yaitu mencari himpunan penyelesaian dari sistem pertidaksamaan di atas, untuk x, y Î R.

Grafik tersebut tampak pada gambar 5.4

50 yang ditunjukkan oleh daerah yang

bersih yaitu daerah OAEC, merupakan

40– D(0,40) irisan dari grafik himpunan penyelesaian

pertidaksamaan (1) sampai (4)

30–

Setiap anggota dari himpunan pe-

20– C(0 , 24) nyelesaian disebut suatu penyele-

E saian yang mungkin.

10–

A (20,0) B(48,0) Misalkan titik (0,0), (0,24), (10,19)

0 10 20 30 40 50 (11,18), (12,16), (20,0) adalah pe-

nyelesaian yang mungkin

Gambar 5.4

Untuk memperoleh penyelesaian yang sebaik mungkin, dicari titik-titik yang koordinatnya memenuhi syarat-syarat yang diberikan dan memberikan nilai maksimum untuk x + y (jumlah roti seluruhnya).

Kita selidiki nilai x + y di titik-titik pada atau dekat batas-batas segi banyak OAEC, sehingga diperoleh:
x 0 0 10 11 12 20
y 0 24 19 18 16 0
x + y 0 24 29 29 28 20


Nilai maksimum dari x + y adalah 29 yang ditunjukkan di titik (10,19) dan (11,18), artinya dapat dibuat 10 roti A dan 19 roti B atau 11 roti A dan 18 roti B.

Dalam program linear , bentuk linear ax + by yang dioptimumkan (dimaksimumkan/diminimumkan) disebut bentuk obyektif atau fungsi sasaran yang ditulis dengan f(x,y) = ax + by.

Bentuk ini adalah bagian yang penting dalam Program Linear.

Latihan 2

1. a. Perlihatkanlah himpunan penyelesaian sistem pertidaksamaan berikut : x ³ 0 , y ³ 0

x + y £ 3 , x + 2 y £ 4 untuk x, y Î R

b. Tandailah dengan noktah-noktah, setiap titik yang memenuhi sistem pertidaksamaan, dan tulislah nilai-nilai x + y pada setiap titik.

c. Titik-titik manakah pada himpunan penyelesaian yang membuat x + y maksimum dan minimum ?

2. a. Tandailah dengan noktah-noktah, setiap titik yang memenuhi sistem pertidaksamaan x + y £ 4 , 2 x + y £ 6 , x ³ 0 , y ³ 0 untuk x, y Î R

b. Titik manakah yang menjadikan 2 x + y mencapai maksimum ?

3. a. Gambarkanlah himpunan penyelesaian dari sistem pertidaksamaan (x , y Î R)

x + y £ 6 , 2 x + y ³ 3 , x ³ 1 , x £ 4 , y ³ 0

b. Tentukanlah koordinat titik-titik sudut dari segi banyak himpunan penyelesaian !

c. Tentukanlah nilai minimum dan maksimum bentuk obyektif f(x,y) = 4 x + y dari titik-titik sudut segi banyak pada (3.b.)
Tentukanlah nilai maksimum dari fungsi obyektif f(x,y) = 5 x + 4 y yang memenuhi sistem 2 x + 3 y £ 12 ,

2 x + y £ 8 , x ³ 0 dan y ³ 0 untuk x , y Î R

5. Luas tempat parkir adalah 420 m2. Tempat parkir yang diperlukan sebuah sedan 5 m2 dan luas rata-rata sebuah truk 15 m2. Biaya parkir untuk sebuah sedan Rp. 300,00 dan untuk truk Rp. 500,00. Tempat parkir dapat menampung tidak lebih dari 60 kendaraan.
Misalkan banyak sedan yang diparkir x buah dan banyak truk y buah. Buatlah model matematikanya.
Berapa sedan dan truk dapat diparkir agar pemasukan uang parkir sebesar mungkin ?

6. Seorang penjahit mempunyai 60 m kain tetoron dan 40 m kain katun. Dari bahan tersebut akan dibuat 2 macam busana untuk dijual. Busana A memerlukan 3 m kain tetoron dan 1 m kain katun, sedangkan busana B memerlukan 2 m kain tetoron dan 2 m kain katun. Berapa banyak busana A dan busana B yang harus dibuat agar mendapat keuntungan sebesar-besarnya, bila keuntungan satu jas Rp. 80.000,00 dan satu rok Rp. 60.000,00 ?

7. Sebuah pabrik sepeda dapat membuat 25 buah sepeda setiap minggunya. Modal sebuah sepeda kualitas A sebesar Rp. 300.000,00 dan sepeda kualitas B sebesar Rp. 400.000,00 per buah. Pabrik tidak akan mengeluarkan modal lebih dari Rp. 8.400.000,00 setiap minggunya.
Andaikan produksi setiap minggu adalah x sepeda kualitas A dan y sepeda kualitas B, tulislah sistem persamaan yang harus dipenuhi dalam x dan y.
Bila pabrik mengharap laba Rp. 100.000,00 untuk setiap sepeda kualitas A dan Rp. 150.000,00 untuk setiap sepeda kualitas B, tulislah laba dalam xdan y setiap minggu
Tentukanlah banyak sepeda setiap jenis agar diperoleh laba maksimum. Berapa laba maksimum tersebut ?

8. Sebuah pesawat udara mempunyai tempat duduk tidak lebih dari 48 penumpang. Setiap kelas utama boleh membawa bagasi 60 kg sedang untuk kelas ekonomi boleh membawa 20 kg. Pesawat hanya dapat membawa 1,44 ton bagasi.
Bila banyak penumpang kelas utama x dan banyak penumpang kelas ekonomi y, tuliskan empat pertidaksamaan dalam x dan y.
Bila harga tiket untuk setiap kelas utama Rp. 500.000,00 dan kelas ekonomi Rp. 300.000,00 , tentukanlah jumlah pemasukan dari tiket dalam x dan y.
Tentukanlah banyak penumpang masing-masing kelas dan berapa pemasukan maksimum yang diperoleh setiap penerbangan.

9. Seorang penjaja buah-buahan yang menggunakan gerobak, menjual pisang barangan dan pisang emas. Harga pembelian pisang barangan Rp. 1000,00 tiap kg dan pisang emas Rp. 400,00 tiap kg. Modal yang tersedia hanya Rp. 250.000,00 dan gerobak hanya dapat memuat tidak lebih dari 400 kg. Keuntungan satu kg pisang barangan Rp. 300,00 dan pisang emas Rp. 150,00. Berapa kg masing-masing jenis pisang yang harus dibeli agar keuntungannya maksimum ?



C. Penggunaan garis selidik dalam menentukan nilai optimum

Pada bab sebelumnya sudah dipelajari cara menentukan optimum dari suatu fungsi obyektif dengan cara mensubstitusikan titik-titik yang memenuhi himpunan penyelesaian. Menghitung nilai fungsi obyektif dan menentukan titik yang mengakibatkan fungsi obyektif menjadi maksimum atau minimum. Selain dengan cara itu dapat juga ditentukan penyelesaian optimum dari fungsi obyektif ialah dengan menggunakan garis selidik ax + by = k dengan k Î bilangan real dengan mengambil nilai k, misalnya k1, k2, k3, … dst, kita dapatkan garis-garis selidik :

Garis-garis selidik ini mempunyai

gradien yang sama, sehingga

garis-garis selidik saling sejajar

Contoh :

Tentukanlah nilai maksimum dan minimum dari bentuk x + 2 y yang memenuhi sistem pertidaksamaan :

x + 3 y £ 9 , 2 x + y £ 8 , x ³ 0 , y ³ 0 untuk x , y Î R !

Penyelesaian :

Pada gambar 5.5 garis tipis mempunyai persamaan x + 2 y = k , untuk k = 0, 1, 2, 3, 4, 5, 6, 7

Semakin besar k, maka garis tersebut semakin jauh dari titik pangkal.
Untuk k = 0 memberikan garis yang melalui titik pangkal, yang memberikan nilai minimum dari x + 2 y yaitu nol
Untuk k = 1, memotong daerah penyelesaian menjadi bangun segitiga, di mana x + 2 y kurang atau sama dengan 1
Untuk menentukan nilai optimum x + 2 y digambarkan garis yang sejajar dengan garis (b)

10 x + 2y =7 , melalui titik E merupakan

titik terujung dari daerah penyelesaian

8 yang mungkin.

6 Garis yang dicari adalah x + 2 y = 7 ,

x+2y=7 sehingga nilai maksimum dari x + 2 y

4 adalah 7.

E(3,2)

2




0 2 4 6 8 10

x+2y=4 x+2y=5

x+2y=2 x+2y=3

x+2y=0 x+2y=1

Gambar 5.5.

Dari contoh di atas terlihat bahwa apabila kemiringan garis selidik terletak di antara dua garis yang diketahui, maka nilai maksimum/minimum terletak pada titik potong kedua garis (gambar 5.6.a), sedangkan apabila kemiringan garis selidik lebih curam, maka jawaban terletak pada titik potong dengan sumbu X (gambar 5.6.b) dan apabila kemiringannya lebih landai, kita peroleh titik potong dengan sumbu Y ((gambar 5.6.c)

Y Y Y






garis selidik garis selidik

garis selidik





O X O X O X

(a) (b) (c)

Gambar 5.6

Latihan 3
a. Gambarkanlah grafik himpunan penyelesaian yang memenuhi sistem pertidaksamaan

2 x + y £ 6 , x + y £ 5 , x ³ 0 dan y ³ 0 !

b. Gambarkanlah garis selidik x + 4 y = k , untuk k Î B !

c. Tentukanlah nilai maksimum dari x + 4 y !
a. Gambarkanlah grafik himpunan penyelesaian dari pertidaksamaan (x, y Î R)

x + y £ 6 , 2 x + y ³ 3 , x ³ 1 , x £ 4 , y ³ 0 !

b. Gambarkanlah garis-garis yang sejajar garis 4 x + y = k

c. Tunjukkanlah nilai minimum dari 4 x + y adalah 5 dan nilai maksimumnya 18 !
a. Gambarkanlah grafik himpunan penyelesaian dari sistem pertidaksamaan (x, y Î R) :

x + y ³ 3 , x + 2 y £ 12 , x ³ 1 , x £ 6 dan y ³ 0 !

b. Gambarkanlah garis selidik 2 x + y = k untuk k Î B !

c. Tentukanlah nilai maksimum dan minimum untuk 2 x + y !
Y Noktah-noktah pada gambar adalah himpunan

penyelesaian dari sistem pertidaksamaan untuk

5 – · · x, y Î R.

4 – · · · · a. Gambarkanlah garis-garis selidik 2 x + y = k ,

3 – · · · · · untuk k Î B !

2 – · · · · · · b. Tentukanlah nilai maksimum dan minimum

1 – · · · · · · dari 2 x + y !

| | | | | | X

0 1 2 3 4 5 6
Noktah-noktah pada gambar di samping memperlihat

Y kan himpunan penyelesaian sistem pertidaksamaan

5– 1 £ x £ 5 dan1 £ y £ 4 untuk x , y Î C.

4– · · · · ·

3– · · · · · a. Tandailah nilai dari 2x + 3y pada setiap titik!

2– · · · · · b. Tulislah pasangan berurutan (x,y) yang memenuhi

1– · · · · · 2 x + 3 y = 10 !

| | | | | c. Tentukan himpunan penyelesaian 2 x + 3 y < 7 !

0 1 2 3 4 5 X d. Tentukanlah nilai maksimum dan minimum 2x + 3y

dan di titik mana hal itu terjadi !



Y Daerah yang diarsir pada gambar adalah himpunan

4 R(1,4) penyelesaian suatu sistem pertidaksamaan

S(0,3) Q(4,3) a. Gambarkanlah garis-garis yang ditentukan oleh

2 2 x + y = k untuk k Î R, melalui titik O , P , Q,

1 R dan S !

0 | | | | | X b. Tentukanlah nilai k yang terbesar dan terkecil

0 1 2 3 4 P(5,0) Di titik mana itu terjadi ?
Untuk membuat roti A diperlukan tepung 80 gram dan mentega 40 gram. Roti B memerlukan tepung 60 gram dan mentega 20 gram. Persediaan tepung 2500 gram dan mentega 2300 gram, sedangkan bahan lain cukup tersedia.
Misalkan banyak roti A x buah dan roti B y buah, tentukan empat buah pertidaksamaan yang memenuhi !
Bila keuntungan roti A Rp. 300,00 per buah dan roti B Rp. 200,00 per buah, tunjukkanlah keuntung-an yang diperoleh adalah K = 100 (3 x + 2 y) !
Berapa banyak roti A dan B agar diperoleh keuntungan maksimum ?
Seorang penjaja keliling dengan naik sepeda mengantarkan 2 jenis tissu Luks dan Spesial ke warung-warung. Ia hanya dapat membawa maksimum 500 bungkus tissu. Harga pembelian tissu Luks Rp. 250,00 per bungkus dan tissu Spesial Rp. 125,- per bungkus. Modal yang tersedia hanya Rp. 100.000,00. Keuntungan tissu Luks Rp. 75,- per bungkus sedangkan tissu Spesial Rp. 25,- per bungkus.
Misalkan banyak tissu Luks x bungkus dan tissu Spesial y bungkus. Buatlah model matematikanya !
Tunjukkan keuntungan yang diperoleh adalah P = 25 (3 x + y) !
Tentukan banyak masing-masing tissu agar keuntungan maksimum !
Diketahui sistem pertidaksamaan : x ³ 0 , y ³ 0 , 2 x + y £ 12 dan x + 2 y £ 12

Tentukan nilai maksimum dari fungsi sasaran berikut :
f(x,y) = 2 x + 5 y
f(x,y) = 2 x + 4 y
f(x,y) = 3 x + 3 y
f(x,y) = 4 x + y

Carilah kesimpulan dari soal itu dengan membuat garis bilangan dari gradien yang diketahui dan letak gradien fungsi sasaran !
10. Diketahui sistem pertidaksamaan : x ³ 0 , y ³ 0 , 4 x + 3y ³ 24 dan x + 2 y ³ 18 serta 5 x + 2y ³ 30.

Tentukan nilai minimum dari fungsi sasaran yakni :
f(x,y) = 2 x + 5 y
f(x,y) = 2 x + 4 y
f(x,y) = 3 x + 3 y
f(x,y) = 4 x +2 y
f(x,y) = 6 x + y

Sumber : fardiansyah7fold.wordpress.com