KASUS MAKSIMISASI

Untuk menjelaskan bagaimana metode grafik digunakan untuk memecahkan suatu

kasus maksimisasi, kita ambil contoh kasus perusahaan sepatu UD. Shuma pada bab 2.

Seperti kita ketahui, kasus perusahaan sepatu UD. Shuma hanya mengandung dua variabel

keputusan, yaitu jumlah sepatu wanita (X1) dan sepatu anak (X2) yang harus dihasilkan. Oleh

karenanya, kasus ini dapat dipecahkan dengan metode grafik.

Langkah pertama yang harus dilakukan untuk memecahkan kasus perusahaan sepatu

UD. Shuma adalah merumuskan masalah dan tujuan pemecahan masalah ke dalam bentuk

matematika. Seperti telah disinggung sebelumnya, tujuan yang ingin dicapai oleh perusahaan

UD. Shuma adalah menentukan kombinasi jumlah X1 dan X2 yang memaksimumkan

keuntungan. Upaya ini menghadapi kendala keterbatasan waktu yang dapat disediakan oleh

masing-masing unit produksi yang menangani suatu tahap produksi. Adapun model

matematika dari fungsi tujuan dang fungsi kendala kasus tersebut adalah sebagai berikut:

Fungsi tujuan: memaksimumkan kendala: 4000X1 + 1000X2

10X1 + 2X2 < 300

3X1 + 2X2 < 120

2X1 + 2X2 < 100

X1, X2 > 0

Langkah berikutnya kita buat grafik dari fungsi-fungsi kendala yang menunjukkan

berbagai kemungkinan kombinasi nilai X1 dan X2 bagi kasus perusahaan UD. Shuma. Dalam

hal ini, kita meletakkan variabel X1 (sepatu wanita) pada sumbu horisontal dan variabel X2

(sepatu anak) pada sumbu vertikal seperti yang ditunjukkan pada Gambar 3.1.

Gambar 3.1.

Diagram Cartesius dan Titik-titik Penyelesaian

Kasus Perusahaan UD. Shuma

X2 (sepatu anak)

100

75 Titik penyelesaian dengan X1 = 25 dan X2 = 75

50 Titik penyelesaian dengan

25 X1 = 75 dan X2 = 50

-50 -25 0 25 50 75 100 X1 (sepatu wanita)

-25

-50

Titik-titik pada diagram di atas menunjukkan berbagai kombinasi jumlah sepatu

wanita X1 dan jumlah sepatu anak X2 yang dapat dihasilkan. Jadi titik-titik pada diagram

tersebut menyatakan penyelesaian yang mungkin untuk kasus perusahaan UD. Shuma. Titik-

titik tersebut disebut titik-titik penyelesaian (solution points).

Karena syarat non negativity, maka nilai X1 dan X2 harus tidak negatif. Dengan

demikian, titik-titik yang mungkin hanyalah titik-titik yang berada di sebelah atas sumbu

horisontal X1 dan di sebelah kanan sumbu vertikal X2. Daerah ini ditunjukkan sebagai daerah

yang diarsir pada Gambar 3.2, di mana pada daerah tersebut nilai X1 > 0 dan X2 > 0.

Gambar 3.2.

Daerah Penyelesaian Kasus Perusahaan UD. Shuma

yang Memenuhi Syarat Non Negativity

X2

75

50

25

-50 -25 0 25 50 75 X1

Langkah selanjutnya adalah menentukan titik-titik penyelesaian yang memenuhi

kendala dari berbagai kemungkinan titik penyelesaian pada daerah yang memenuhi syarat

non negativity tersebut. Untuk itu, kita lihat ketidaksamaan fungsi kendala satu persatu.

Pertama, kita lihat ketidaksamaan fungsi kendala pengukuran dan pemotongan pola :

10X1 + 2X2 < 300

Titik-titik penyelesaian yang memenuhi ketidaksamaan ini dapat dicari dengan

menentukan garis yang memenuhi persamaan 10X1 + 2X2 < 300. Garis ini dapat ditemukan

dengan cara menetapkan dua titik pada sumbu vertikal dan horisontal yang memenuhi

persamaan 10X1 + 2X2 = 300 dan kemudian menghubungkan kedua titik tersebut. Hasilnya,

semua titik yang terletak sepanjang garis tersebut akan memenuhi persamaan di atas.

Guna menentukan titik pada sumbu vertikal, kita misalkan X1 = 0. Dengan

memasukkan nilai X1 tersebut ke dalam persamaan, kita dapat menentukan nilai X2, sebagai

berikut :

10(0) + 2X2 = 300

2X2 = 300

X2 = 150

Dari sini kita mendapatkan titik pada sumbu vertikal dengan koordinat (0,150).

Sedang koordinat titik pada sumbu horisontal dapat kita cari dengan menetapkan X2 = 0. Kita

akan mendapatkan :

10X1 + 2(0) = 300

X1 = 30

Dengan demikian titik pada sumbu horisontal ini mempunyai koordinat (30,0).

Dengan dua titik tersebut yaitu (0,150) dan (30,0) kita dapat menggambarkan garis

yang memenuhi persamaan 10X1 + 2X2 = 300, seperti terlihat pada Gambar 3.3. Garis ini

merupakan garis kendala (contraint line) bagi pengukuran dan pemotongan pola. Namun

perlu diingat bahwa kendala pengukuran dan pemotongan pola yang sebenarnya adalah 10X1

+ 2X2 < 300. Oleh karenanya, titik-titik penyelesaian yang memenuhi kendala ini hanyalah

titik-titik yang berada di sepanjang garis dan di bawah garis kendala. Hal ini dapat kita

buktikan dengan mengambil sembarang titik di sekitar garis kendala tersebut. Misal titik

(10,0) yang menunjukkan X1 = 10 dan X2 = 10. Kita dapatkan 10(10) + 2(10) = 120 (< 300).

Dengan demikian titik (10,10) memenuhi kendala. Sebaliknya titik (40,60) yang berada di

atas garis kendala menghasilkan 10(40) + 2(60) = 520 (> 300). Jadi titik (40,60) tidak

memenuhi kendala.

Gambar 3.3.

Garis Kendala Pengukuran dan Pemotongan Pola

X2

150 (0,150)

125

100 10X1 + 2X2 = 300

75 (40,60)

50

25 (10,10)

0 25 50 75 100 X1

Dengan demikian dapat disimpulkan bahwa titik-titik yang terletak pada dan di

bawah garis kendala saja yang memenuhi kendala pengukuran dan pemotongan pola. Daerah

di bawah garis kendala ini disebut daerah yang layak (feasible region) dan ditunjukkan

sebagai daerah yang diarsir pada Gambar 3.4.

Dengan cara yang sama, kita dapat menggambarkan garis kendala untuk pengeleman

dan pengeringan 3X1 + 2X2 < 120. Pertama-tama kita tentukan titik yang memenuhi

persamaan kendala 3X1 + 2X2 = 120. Dengan memisalkan nilai X1 = 0, kita dapat

menentukan nilai variabel X2 yaitu sebesar 3(0) + 2X2 = 120 atau X2 = 60, sehingga kita

dapatkan titik (0,60). Selanjutnya dengan memisalkan nilai X2 = 0, kita dapatkan 3X1 + 2(0) =

120 atau X1 = 40 atau titik (40,0). Dengan menghubungkan titik (0,60) dan (40,0) kita dapat

menggambarkan garis kendala pengeleman dan pengeringan. Adapun daerah yang memenuhi

ketidaksamaan kendala pengeleman dan pengeringan adalah yang diarsir pada Gambar 3.5.

Gambar 3.4.

Daerah Layak yang Memenuhi Kendala

Pengukuran dan Pemotongan Pola

X2

150

125

100 10X1 + 2X2 = 300

75

50

25

0 25 50 75 100 X1

Demikian juga untuk kendala pengeslepan, kita dapatkan titik (0,50) dan (50,0) dari

persamaan 2X1 + 2X2 = 100. Daerah layak yang memenuhi kendala pengeslepan ini

ditunjukkan pada gambar 3.6.

Gambar 3.5.

Daerah Layak yang Memenuhi Kendala

Pengeleman dan Pengeringan

X2

150

125

100

75 (0,60)

50 3X1 + 2X2 = 120

25 (40,0)

0 25 50 75 100 X1

Gambar 3.6.

Daerah yang Layak Memenuhi Kendala Pengeslepan

X2

150

125

100

75

50 (0,50) 2X1 + 2X2 = 100

25 (50,0)

0 25 50 75 100 X1

Sekarang kita mempunyai tiga grafik yang memperlihatkan titik-titik yang

memenuhi ketiga kendala. Dalam programasi linear kita harus dapat mengidentifikasi titik-

titik penyelesaian yang memenuhi semua kendala secara bersama-sama. Untuk dapat

melakukan hal ini, kita gabungkan ketiga garis kendala di atas ke dalam satu bidang dan

kemudian mencari daerah titik-titik penyelesaian yang memenuhi semua kendala.

Gabungan ketiga grafik ini diperlihatkan pada Gambar 3.7. dan daerah yang

memenuhi semua kendala ditunjukkan sebagai daerah yang diarsir. Daerah ini disebut

daerah penyelesaian yang layak (feasible region). Titik-titik yang berada pada batas daerah

yang layak atau yang berada di dalamnya disebut titik-titik penyelesaian yang layak

(feasible solution points).

Gambar 3.7.

Daerah Penyelesaian Layak bagi Perusahaan UD. Shuma

X2

160

140

120

80

60

40

daddd 20 20 layak

-20 0 20 40 60 X1

Setelah kita menentukan penyelesaian layak (yaitu yang memenuhi semua kendala),

langkah selanjutnya adalah menentukan penyelesaian optimal adalah penyelesaian yang

memberikan nilai terbaik bagi fungsi tujuan.

Pencarian penyelesaian optimal ini kita lakukan dengan mencoba berbagai titik

penyelesaian (X1, X2) dan menghitung nilai fungsi tujuan 4000X1 + 1000X2. Kesulitan yang

Daerah layak

timbul dari cara ini adalah terdapat banyak sekali (bahkan tak terbatas) titik penyelesaian

layak, sehingga tidak mungkin untuk mengevaluasi seluruh titik penyelesaian layak yang ada.

Cara yang dapat kita tempuh adalah menentukan garis fungsi tujuan terlebih dahulu.

Adapun fungsi tujuan dalam kasus perusahaan UD. Shuma adalah Z = 4000X1 + 1000X2

dimana Z adalah besarnya keuntungan. Persamaan fungsi tujuan ini dapat dituliskan menjadi

1000X2 = Z – 4000X1

atau X2 = 1/1000Z – 4X1

Persamaan ini menunjukkan hubungan X1 dan X2. Garis dari persamaan ini mempunyai

intersep sebesar 1/1000 Z dan slope sebesar 4 dengan kemiringan negatif (dari kiri atas ke

kanan bawah).

Dari persamaan tersebut, kita akan menemukan bahwa untuk sembarang nilai Z yang

akan berubah adalah nilai intersep, sedangkan nilai slope tetap sebesar 4. Dengan demikian,

garis fungsi tujuan akan bergerak sejajar/paralel satu sama lain. Kita ambil contoh untuk nilai

Z = 100.000 dan Z = 250.000, kita akan mendapatkan persamaan garis sebagai berikut :

Untuk Z = 100.000 X2 = (1/1000) (100.000) – 4X1 = 100 – 4X1

Untuk Z = 250.000 X2 = (1/1000) (250.000) – 4X1 = 250 – 4X1

Garis keuntungan untuk Z = 100.000 dapat kita gambarkan dengan memisalkan X1 =

0, sehingga X2 = 100- 4(0) = 100. Berarti kita mempunyai titik dengan koordinat (0,100).

Sedang untuk X2 = 0, kita memperoleh nilai X1 sebesar 0 = 100 – 4X1 atau X1 = 25, sehingga

kita dapatkan titik (25,0). Dengan menghubungkan titik (0,100) dan (25,0) kita akan

memperoleh garis keuntungan Z = 100.000. Cara yang sama dapat kita lakukan untuk

menggambarkan garis keuntungan Z = 250.000, yang diperoleh dengan menghubungkan titik

(0,250) dan (62.5,0).

Kalau kita menggambarkan kedua garis keuntungan ini, maka kita akan menemukan

bahwa semakin besar nilai Z semakin jauh garis keuntungan ini dari titik origin (lihat Gambar

3.8). Dengan demikian, nilai Z yang maksimum ditemukan pada garis keuntungan yang

terjauh dari titik origin tetapi yang masih terdapat di dalam atau pada batas daerah

penyelesaian layak. Garis yang dimaksud adalah garis yang memenuhi nilai X1 = 25,7 dan X2

= 21,5 atau Z sebesar 124,300 (lihat Gambar 3.9).

Gambar 3.8.

Berbagai Alternatif Garis Keuntungan Perusahaan UD. Shuma

X2

160

140Garis keuntungan 4000X1 + 1000X1 = 250.000

120

100 Garis keuntungan 4000X1 + 1000X2 = 100.000

80 Garis keuntungan 4000X1 + 1000X2 = 124.300

60 40

20

-20 0 20 40 60 X1

Karena titik (25.7, 21.5) berada pada garis kendala pengukuran dan pemotongan pola

serta garis kendala pengeleman dan pengeringan, maka nilai variabel keputusan X1 dan X2

harus memenuhi kendala pengukuran dan pemotongan pola 10X1 + 2X2 = 300 dan kendala

pengeleman dan pengeringan 3X1 + 2X2 =120. Sebenarnya dengan menggunakan dua

persamaan tersebut kita mencari nilai penyelesain optimal X1 dan X2 tanpa harus

menggunakan garis keuntungan terlebih dahhulu seperti yang baru saja kita lakukan. Kita

dapat melakukan hal ini dengan cara sebagai berikut:

Dari persamaan kendala pengukuran dan pemotongan pola 10X1 + 2X1 =300 bisa kita

ubah menjadi 2X1 = 300 – 10X1atauX2=150 – 5X1.

Dengan mensubtitusikan nilai X2 tersebut kedalam persamaan kendala pengeleman

daan pengeringan kita mendapatkan:

3X1 + 2(150-5X1)= 120

3X1 + 300 -10 X1 =120

7X1 =180

X1 =180/7 =25,7

Sehingga X2 =150 -5X1 =150-5(25,7)=150-12,85=21,5.

Jadi titik penyelesaian yang tepat untuk perusshaan sepatu UD. Shuma adalah 25,7

unit sepatu wanita dan 21, 5 unit sepatu anak.

Gambar 3.9.

Penyelesaian Optimal Kasus Perusahaan UD. Shuma

X2

160

140

120

100

80 Garis keuntungan 4000X1 + 1000X2 = 124.300

60

40

20

-20 0 20 40 60 X1

Dengan singkat dapat dikatakan bahwa penentuan nilai yang tepat dari variabel

keputusan bagi penyelesaian optimal dalam kasus programasi linear yang mengandung dua

variabel keputusan dapat dilakukan dengan mencari dua persamaan simultan yang berkaitan

dengan titik penyelesaian tersebut.

Titik Ekstrem dan Penyelesaian Optimal

Kalau kita perhatikan penyelesaian kasus perusahaan UD. Shuma di atas, kita akan

menemukan bahwa penyelesaian optimal dari kasus programasi linear tersebut terdapat pada

titik ekstrem daerah layak dari kasus bersangkutan. Jadi kita tidak perlu lagi mengevaluasi

setiap titik penyelesaian yang layak, tetapi cukup menentukan titik ekstrem yang memberikan

nilai fungsi tujuan yang terbaik.

Apabila kita lihat kembali daerah layak dari kasus perusahaan UD. Shuma, maka

tampak bahwa kasus ini mempunyai lima titik ekstrem pada daerah layaknya, seperti

ditunjukkan pada Gambar 3.10 berikut.

Gambar 3.10

Titik-titik Ekstrem dari Daerah Layak

Kasus Perubahan Sepatu UD. Shuma

X2

160

140

120

100

80

60 2

40 3

20 4 1 5

-20 0 20 40 60 X1

Untuk membuktikan bahwa cara tersebut benar, kita dapat menguji masing-masing

titik ekstrem kedalam fungsi tujuan dan menentukan titik ekstrem yang memberikan nilai

yang paling besar ( pada kasus maksimisasi) untuk Z.

Titik ekstrem 1(0,0)

Fungsi tujuan Z= 4000X1 + 1000X2 =4000(0) + 1000(0) =0

Titik ekstrem 2: (0,50)

Z =4000X1 + 1000X2 =4000(0) +1000(50) =50.000

Titik ekstrem 3: (20,30)

Z =4000X1 + 1000X2 =4000(20) + 1000(30) = 110.000

Titik ekstrem 4: (25.7, 21.5)

Z =4000X1 + 1000X2 =4000(25.7)+ 1000(21.5)= 124.300

Titik ekstrem 5: (30,0)

1

Z= 4000x1 + 1000X2 =4000(30)+ 1000(0) =120.000

Hasil pengujian titik-titik ekstrem terhadap fungsi tujuan memperlihatkan bahwa

nilai fungsi tujuan Z yang paling besar, yaitu 124.300 tercapai pada titik ekstrem 4 (25.7,

21.5). Dari sini terbukti bahwa cara ini memberikan hasil yang sama dengan cara

sebelumnya.

Karena variabel X1 dan X2 menunjukkan unit sepatu yang akan dihasilkan, maka

tidak masuk akal kalai nilai variabel-variabel tersebut berupa pecahan. Oleh karena itu, kita

dapat melakukan pembulatan terhadap nilai X1 dan X2 serta menguji apakah hasil pembulatan

tersebut masih memenuhi kendala. Bila pembulatan dapat dilakukan dengan cara

membulatkan X1 dan/atau X2 ke atas atau kebawah, berarti terdapat 4 alternatif pembulatan

yang dapat dilakukan. Hasil pembulatan dan pengujian terhadap masing-masing kendala

adalah sebagai berikut:

1. X1= 26 dan X2 = 22

Kendala pengukuran dan pemotongan pola:

10(26) + 2(22) =260 +44 =304 (>300)

Oleh karena itu nilai X1 dan X2 tersebut sudah tidak memnuhi kendala pengukuran dan

pemotongan pola berarti titik penyelesaian tidak dapat dipakai dan karenanya kita tidak

perlu mengujinya pada kendala lain.

2. X1 =25 dan X2 =21

Kendala pengukuran dan pemotongan pola:

10(25) + 2(21) =250 +42 =292 (<300)

Berarti titik ini memenuhi kendala pengukuran dan pemotongan pola dan karenaya kita

dapat mencoba menguji apakah nialai variabel keputusan X1 dan X2 terssebut memenuhi

kendala yang lain juga. Untuk kendala pengeleman dsan pengeringan:

3(25) + 2(21) =75 +42 =117 (<120)

Kendala pengeslepan:

2(25) +2 (21) =50 +42 =92 (<100)

Kita lihat bahwa nilai X1 =25 dan X2 =21 memenuhi semua kendala, namun belum tentu

titilk ini yang akan kita pilih sebagai titik penyelesaian yang dimaksud. Kita harus

membandingkan dengan titik lain yang juga memenuhi semua kendala yang memberikan

nilai fungsi tujuan Z lebih besar.

3. X1 =25 dan X2 =22

Kendala dan pengukuran pemotongan pola:

10(25) +2 (22)=250 +44 =294 (<300)

Kendala pengeleman dan pengeringan:

3(25) + 2(22) =75 +44 = 119 (<120)

Kendala pengeslepan:

2(25) +2(22) = 50 + 44=94 (<100)

Titik nilai juga memenuhi semua kendala.

4. X1 = 26 dan X2 = 21

Kendala pengukuran dan pemotongan pola:

10(26) + 2(21) = 260 +42 = 302 (<300)

Dari beberapa alternatif kombinasi X1 dan X2 di atas, terdapat dua alternatif yang

memenuhi semua kendala, yaitu (25.21) dan (25.22). Untuk menentukan kombinasi mana

yang akan dipilih kita uji kedua titik tersebut terhadap fungsi tujuan Z.

Untuk titik (25,21), nilai Z=4000(25) + 1000(21)= 121.000.

Untuk titik (25,22), nilai Z=4000(25) + 1000(22)= 122.000.

Karena titik (25,22) memberikan nilai fungsi tujuan yang lebih besar, maka

penyelesaian nyata bagi perusahaan UD. Shuma adalah memproduksi 25 unit sepatu wanita

dan 22 unit sepatu anak dengan keuntungan sebesar RP122.000,00. Untuk pembahasan

selanjutnya, kita akan mengabaikan pembulatan tersebut dan kita akan menggunakan

penyelesaian asli, yaitu X1 = 25,7 dan X2 =21,5.

VARIABEL SLACK

Dari nilai optimal variabel keputusan yang kita peroleh. Kita dapat mengetahui total

waktu yang digunakan pada setiap tahap produksi, sebagai berikut :

Pada tahap pengukuran dan pemotongan pola = 300 menit.

Tahap pengeleman dan pengeringan = 120 menit.

Tahap pengeslepan = 94,4 menit.

Penyelesaian ini memberikan informasi kepada pimpinan perusahaan bahwa

produksi 25,7 unit sepatu wanita dan 21, 5 unit sepatu anak menggunakan seluruh waktu unit

produksi pengukuran dan pemotongan pola serta unit produksi pengeleman dan pengeringan.

Sedang unit produksi pengeslepan hanya mengguakan 94,4 menit dari 100 menit yang dapat

disediakan oleh unit produksi tersebut. Berarti ada sisa waktu sebesar (100 - 91,1) = 5,6 menit

yang tidak digunakan pada unit produksi pengeslepan. Sisa waktu yang demikian merupakan

kapasitas produksi yang tidak digunakan (idle). Dalam program linier, kapasitas yang idle

seperti ini disebut sebagai slack dari unit produksi bersangkutan.

Slack dari suatu kendala terdapat pada kendala dengan tanda lebih kecil sama

dengan ( < ). Sebaliknya, dalam kasus dengan kendala bertanda lebih besar sama dengan

( > ), kapasitas idle tersebut disebut surplus. Mengenai hal ini akan kita bahas lebih lanjut

dalam metode simpleks.

Hingga di sini kita dapat menyimpulkan prosedur penyelesaian kasus maksimisasi

dengan metode grafik sebagai berikut:

1. Nyatakan masalah (fubgsi tujuan dan fungsi kendala) ke dalam bentuk matematika.

2. Gambarkan fungsi-fungsi kendala dalam suatu grafik.

3. Tentukan titik-titik ekstrem yang membatasi daerah yang layak

4. Uji masing-masing titik ekstrim tersebut terhadap nilai fungsi tujuan dan tentukan titik

yang memberikan nilai paling besar sebagai titik penyelesaian optimal.