Riset Operasi (Metode Grafik)
Home »
Operational Research
» Riset Operasi (Metode Grafik)
I. Program Linear: Metode Grafik
Program linear adalah suatu pendekatan problem-solving yang dikembangkan untuk membantu manager dalam membuat keputusan.
Pada program linear terdapat dua elemen dasar (properties) yaitu :
Fungsi tujuan dapat berupa maksimisasi atau minimisasi dari suatu kuantitas
Fungsi kendala adalah fungsi yang membatasi tingkat pencapaian dari fungsi tujuan tersebut.
A. Problem Maksimisasi Sederhana
A.1 Ilustrasi
TAS Inc. adalah suatu industri kecil yang memproduksi tas sekolah.
Para distributor TAS sangat antusias pada rencana perusahaan untuk membuat dua desain baru tas sekolah
yaitu model ransel dan model klasik dan mereka bersedia untuk membeli semua produk baru tersebut dalam 3 bulan mendatang.
Setelah melalui serangkaian penelitian mengenai semua tahap pekerjaan, manajemen perusahaan menyatakan bahwa kedua produk baru tersebut akan melalui tahapan pengerjaan yang meliputi:
1. Pemotongan
2. Penjahitan
3. Penyelesaian akhir
4. Pemeriksaan dan pengepakan
Manager produksi telah menganalisa bahwa untuk menghasilkan satu tas model Ransel memerlukan 2 jam pengerjaan pada bagian pemotongan, 2 jam pada bagian penjahitan, 1 jam pada bagian penyelesaian, dan 2 jam pada bagian pemeriksaan dan pengepakan.
Pada sisi lain, untuk menghasilkan satu tas model Klasik diperlukan 2 jam pengerjaan pada bagian pemotongan, 3.3 jam pada bagian penjahitan, 0.5 jam pada bagian penyelesaian dan 1.5 jam pada bagian pemeriksaan dan pengepakan.
Informasi pengerjaan tersebut disajikan pada tabel berikut:
Waktu yang diperlukan (jam)
Jenis Produksi Pemotongan Penjahitan Penyelesaian Pemeriksaan dan Pengepakan
Model Ransel 2 2 1 2
Model Klasik 2 3.3 0.5 1.5
Bagian akuntansi telah menganalisis bahwa setelah menghitung semua perkiraan biaya
produksi dan harga jual maka akan diperoleh keuntungan sebesar Rp. 30.000,- untuk
setiap tas model Ransel dan Rp. 20.000,- untuk model Klasik yang diproduksi. Dari
departemen produksi diperoleh informasi bahwa untuk 3 bulan mendatang hanya tersedia
800 jam kerja pada bagian pemotongan, 1000 jam pada bagian penjahitan, 300 jam pada
bagian penyelesaian dan 650 jam pada bagian pemeriksaan dan pengepakan.
Masalah yang dihadapi oleh perusahaan TAS Inc. adalah menentukan berapa banyak tas
model Ransel, dan berapa banyak model Klasik yang harus diproduksi untuk
memaksimumkan keuntungan dengan memperhatikan ketersediaan waktu kerja pada
setiap bagian tersebut. Jika anda ditugaskan bada bagian produksi, keputusan apa yang
anda buat, yaitu berapa banyak tas Model Ransel dan Model Klasik masing-masing harus
diproduksi dalam waktu 3 bulan mendatang? Tulislah keputusan anda pada tempat
berikut dan anda akan memeriksa keputusan tersebut nanti.
Jumlah tas
Model Ransel
Jumlah tas
Model Klasik
Total
Keuntungan
2. Fungsi Tujuan
Seperti dinyatakan di depan bahwa pada setiap program─── linear terdapat fungsi tujuan
untuk memaksimumkan atau meminimumkan sesuatu. Pada kasus perusahaan TAS Inc.,
tujuannya adalah memaksimumkan keuntungan. Kita dapat menuliskan tujuan tersebut
kedalam notasi matematik yaitu:
X1 = jumlah tas model Ransel yang diproduksi
X2 = jumlah tas model Klasik yang diproduksi
Keuntungan perusahaan berasal dari dua sumber yaitu dari produksi tas model Ransel
(X1) dan dari model Klasik (X2). Karena keuntungan dari model Ransel adalah Rp.
30.000,- per unit dan model Klasik Rp. 20.000,- per unit maka total keuntungan
perusahaan adalah Rp. 30.000 X1 + Rp. 20.000 X2, dimana 30.000X1 merupakan
kontribusi keuntungan model Ransel dan Rp. 20.000 X2 merupakan kontribusi dari model
Klasik. Bila total keuntungan dilambangkan oleh simbol Ζ dalam puluhan ribu rupiah
(Rp. 10.000) maka:
Total keuntungan = Ζ = 3 X1 + 2 X2
Problem perusahaan TAS adalah menentukan nilai variabel X1 dan variabel X2 yang
memberikan nilai maksimum Ζ. Dalam termonologi program linear variabel X1 , X2
disebut variabel keputusan (decision variables). Karena tujuan -- yaitu memaksimumkan
keuntungan-- merupakan fungsi dari variabel keputusan maka persamaan Ζ = 3 X1 +2 X2
disebut dengan fungsi tujuan (objective function). Dengan demikian tujuan dari
perusahaan TAS dapat dinyatakan dengan:
Max Ζ = 3 X1 + 2 X2
Setiap kombinasi produksi tas Model Ransel dan Klasik merupakan solusi dari masalah
ini. Namun demikian hanya solusi yang memenuhi semua kendala atau pembatas yang
dinyatakan sebagai solusi yang layak (feasible solusions). Kombinasi produksi yang
layak (feasible solusions) dan memberikan keuntungan maksimum merupakan kombinasi
yang optimum atau disebut juga solusi optimum (optimal solusion).
Sejauh ini kita belum dapat menentukan optimal solusion bahkan feasible solusions dari
perusahaan TAS karena kita belum melihat semua kendala yang ada. Untuk mengetahui
feasible solusions maka kita perlu mengidentifikasi semua kendala (constraints).
3. Kendala atau Pembatas (constraints)
Setiap tas model ransel atau klasik harus melalui empat tahapan pengerjaan seperti yang
telah disebut di atas dan karena adanya kendala ketersediaan waktu pada masing-masing
bagian maka dapat diperkirakan bahwa jumlah produksi tas oleh perusahaan akan
terbatas.
Dari informasi produksi diketahui bahwa setiap unit tas model Ransel memerlukan 2 jam
pengerjaan pada bagian pemotongan sehingga total waktu yang dibutuhkan untuk
memotong X1 tas model Ransel adalah 2X1. Di sisi lain untuk menghasilkan satu unit tas
model klasik juga dibutuhkan 2 jam pengerjaan pada bagian pemotongan sehingga total
waktu yang dibutuhkan untuk memotong X2 tas model Klasik adalah 2X2 . Dengan
demikian total waktu yang dibutuhkan untuk memotong X1 tas model Ransel dan X2 tas
model Klasik dinyatakan sebagai:
Total waktu pemotongan yang diperlukan = 2 X1 + 2 X2
Karena manager produksi menyatakan bahwa waktu kerja yang tersedia pada bagian
pemotongan adalah 800 jam maka produksi kedua model tas tersebut harus memenuhi
persyaratan pembatas berikut:
2 X1 + 2 X2 ≤ 800
dimana simbol ≤ menyatakan lebih kecil atau sama dengan. Pertidaksamaan di atas
menunjukkan bahwa jumlah jam kerja yang digunakan untuk proses pemotongan tas
sebanyak X1 dari model Ransel dan X2 untuk model Klasik harus lebih kecil atau sama
dengan jumlah maksimum jam kerja yang masih tersedia di bagian tersebut.
Dari tabel di atas juga terlihat bahwa untuk menghasilkan satu unit tas model Ransel
memerlukan 2 jam penjahitan sedangkan setiap tas model Klasik memerlukan 3.3 jam.
Oleh karena jam kerja yang tersedia hanya 1000 jam, maka fungsi pembatas untuk bagian
panjahitan adalah:
2 X1 + 3.3 X2 ≤ 1000
Dengan cara yang sama kita dapat menyusun fungsi pembatas untuk bagian penyelesaian,
yaitu:
X1 + 0.5 X2 ≤ 300
dan fungsi pembatas untuk bagian pemeriksaan dan pengepakan adalah:
2 X1 + 1.5 X2 ≤ 650
Sejauh ini kita telah merumuskan model matematik dari semua kendala jam kerja pada
setiap bagian proses produksi. Apakah masih ada kendala yang terlupakan? Mungkinkah
perusahaan TAS memproduksi X1 tas model Ransel dan atau X2 model klasik yang
negatif ? Jawabnya sudah jelas tidak mungkin. Oleh karena itu untuk mencegah X1 dan
X2 bernilai negatif maka perlu dimasukkan dua kendala tambahan dalam model yaitu:
X1 ≥ 0 dan X2 ≥ 0
tanda ≥ berarti lebih besar atau sama dengan. Dua kendala yang terakhir ini memastikan
bahwa solusi dari masalah program linear tidak akan pernah bernilai negatif sehingga ia
dikatakan sebagai kendala non negatif (non-negativity constraints). Kendala non negatif
merupakan hal yang umum dijumpai pada program linear dan dituliskan sebagai:
X1, X2 ≥ 0
4. Formulasi Matematik
Formulasi matematik dari masalah perusahaan TAS sekarang sudah lengkap dengan
mentranslasikan masalah riil perusahaan menjadi suatu model matematik. Model lengkap
dari perusahaan TAS adalah:
Max 3 X1 + 2 X2
dengan kendala (subject to, = s.t.)
2 X1 + 2 X2 ≤ 800 pemotongan (P)
2 X1 + 3.3 X2 ≤ 1000 penjahitan (J)
X1 + 0.5 X2 ≤ 300 penyelesaian (S)
2 X1 + 1.5 X2 ≤ 650 pemeriksaan dan pengepakan (R&K)
X1, X2 ≥ 0
Langkah berikutnya adalah mencari kombinasi nilai X1 dan X 2 yang memenuhi semua
kendala serta menghasilkan nilai dari fungsi tujuan yang lebih besar atau sama dengan
nilai pada feasible solusion. Bila hal ini telah dilakukan maka solusi optimum akan
tercapai.
5. Solusi Grafik
Program linear yang hanya melibatkan dua variabel (X1, X2 ) dapat diselesaikan dengan
metode grafik. Untuk masalah yang melibatkan lebih dari dua variabel keputusan maka
penyelesaianya dilakukan dengan metode Simplex. Setelah tahun 1980-an seiring dengan
perkembangan mikrokomputer maka solusi dari masalah program linear dapat dilakukan
dengan komputer. Beberapa program yang dapat digunakan adalah: LINDO, LINGGO,
dan THE MANAGEMENT SCIENTIST.
Penggunaan metode grafik dimulai dengan menentukan sumbu horisontal (X1)dan sumbu
vertikal (X2) sehingga nilai dari variabel keputusan X1 berada pada sumbu horisontal dan
nilai dari variabel keputusan X2 berada pada sumbu vertikal. Karena setiap titik
merupakan solusi yang mungkin (possible), maka titik-titik pada grafik merupakan
solusion points (titik-titik solusi). Solusion point dimana X1 = 0 dan X2 = 0 disebut titik
origin.
Langkah berikutnya adalah menentukan manakah dari titik-titik solusi yang berhubungan
dangan feasibel solusion. Karena X1, X2 adalah nonnegatif maka kita hanya
mempertimbangan sebagian saja dari grafik tersebut yang memenuhi persyaratan nonnegatif
X1, X2 ≥ 0 [lihat panel (a) pada grafik]. Selanjutnya adalah menggambarkan grafik
dari semua fungsi pembatas (constraints) seperti diformulasikan pada model matematik.
Dari model tersebut terlihat bahwa fungsi pembatas pemotongan dicerminkan oleh
pertidaksamaan:
2 X1 + 2 X2 ≤ 800
Untuk mendapatkan titik-titik solusi yang memenuhi kondisi ini dimulai dengan
menggambarkan hubungan tersebut sebagai suatu persamaan yaitu titik-titik yang
memenuhi persamaan 2 X1 + 2 X2 = 800. Karena persamaan ini merupakan garis lurus
maka ia dapat digambarkan dengan mencari dua titik yang memenuhi persamaan
tersebut dan selanjutnya menarik garis yang melalui kedua titik tersebut. Titik pertama
diperoleh dengan menetapkan nilai X1 = 0 dan mendapatkan nilai X2 = 40 yang
memenuhi persamaan tersebut. Titik kedua diperoleh dengan menetapkan X2 = 0 dan
mendapatkan nilai X1 = 40. Apabila titik pertama (X1 = 0, X2 = 40) dan titik kedua (X1
= 40, X2 = 0) dihubungkan maka diperoleh garis lurus seperti pada grafik panel (b).
Karena fungsi pembatas proses pemotongan merupakan pertidaksamaan
2 X1 + 2 X2 ≤ 800
manakah titik-titik solusi yang memenuhi pertidaksamaan tersebut? Karena semua titik
pada garis memenuhi persamaan 2X1 + 2X2 = 800 maka kita yakin bahwa semua titik
pada garis tersebut memenuhi fungsi kendala. Namun manakah titik-titik solusi yang
memenuhi pertidaksamaan 2X1 + 2X2 < 800? Setiap titik yang berada di bagian dalam
kurva menuju titik origin seperti ditunjukkan oleh tanda panah adalah titik-titik solusi.
Dengan cara yang sama kita dapat menggambarkan fungsi pembatas untuk bagian
penjahitan (panel c), bagian penyelesaian (panel d), serta bagian pemeriksaan dan
pengepakan (panel e).
Sekarang kita telah mendapatkan empat grafik terpisah untuk masing-masing fungsi
kendala. Dalam program linear kita perlu mengidentifikasi titik-titik solusi yang
memenuhi semua kendala secara simultan. Untuk itu kita perlu menggambarkan keempat
kendala tersebut dalam satu salib sumbu dan memperhatikan daerah yang terdiri dari
titik-titik yang memenuhi keempat kendala secara simultan (panel f). Karena solusi yang
memenuhi keempat kendala tersebut dikenal dengan feasible solusion, maka daerah yang
merupakan titik-titik solusi disebut feasible solusion region atau sederhananya feasible
region. Setiap titik pada garis batas feasible region atau di dalam feasible region adalah
titik solusi yang feasible (feasible solusion point).
Gambar 2 menampilkan kembali feasible region yang memenuhi keempat fungsi
pembatas dengan skala yang lebih besar agar lebih memudahkan menemukan solusi
optimal.
Solusi optimal dapat diketahui dengan mengevaluasi setiap feasible solusion dan solusi
yang memberikan nilai fungsi tujuan yang terbesar adalah solusi optimal. Masalahnya
adalah feasible solusion tersebut jumlahnya tidak terhingga. Oleh karena itu langkah yang
paling efisien adalah dengan menentukan satu nilai feasible solusion dan
menggambarkannya pada kurva feasible region. Setelah itu menggeser garis fungsi tujuan
tersebut hingga menyinggung titik dari daerah feasible yang terluar (Gambar 3). Titik
singgung itulah yang merupakan solusi optimal dari program linear tersebut.
X2 X2
400
P
Non negativity
200
0 X1 0 200 400 X1
0 200 400 X1 0 200 400 600 X1
0
X2
400
200
200 400 X1 0 200 400 X1
X2
600
400
200
J
S
(a)
(b)
(c)
(d)
X2 (e) (f)
400
200
X2
600
400
200
R&K
Gambar 1. Feasible solusion untuk setiap fungsi pembatas
•
•
•
•
0 200 400 600 X1
X2
600
400
200
Pemotongan
Penjahitan
Penyelesaian
Pemeriksaan dan pengepakan
Gambar 2. Feasible region yang memenuhi keempat
fungsi pembatas secara simultan
Feasible region
•
•
c
•
Feasible region
0 200 400 600 X1
X2
600
400
200
3X1 + 2X2 = 950 persamaan fungsi tujuan
Solusi optimal
a
b
d
(250 , 100)
Gambar 3. Solusi optimal dari perusahaan TAS Inc.
•
Untuk memperoleh solusi optimal yang tepat sangat tergantung pada tingkat ketelitian
skala pembuatan grafik. Dengan mengacu pada gambar 3 tersebut di atas dapat
disimpulkan bahwa kombinasi produksi yang memberikan keuntungan maksimum
ditunjukkan oleh titik ekstrim c yaitu 250 unit tas model Ransel (X1) dan 100 unit tas
model Klasik (X2).
Untuk lebih meyakinkan akurasi solusi optimal dapat dilakukan dengan menyelesaikan
persamaan simultan yang berhubungan dengan titik perpotongan dua garis. Dengan
memperhatikan gambar 2 dan gambar 3 terlihat bahwa solusi optimal berada pada titik c
yang merupakan perpotongan fungsi pembatas penyelesaian
X1 + 0.5 X2 = 300 (1)
dengan fungsi pembatas pemeriksaan dan pengepakan yaitu :
2 X1 + 1.5 X2 = 650 (2)
Dari persamaan (1) diperoleh
X1 = 300 - 0.5 X2 . (3)
Dengan mensubstitusikan nilai X1 ke dalam persamaan (2) didapat nilai X2 , yaitu:
2(300 - 0.5 X2) + 1.5 X2 = 650
600 - X2 + 1.5 X2 = 650
0.5 X2 = 650 - 600
X2
= 50/0.5
= 100
Setelah memasukkan nilai X2 = 100 ke dalam persamaan (3) untuk diperoleh nilai X1
yaitu:
X1 = 300 - 0.5 X2
= 300 - 0.5 (100)
= 300 - 50
= 250
Solusi dari persamaan simultan tersebut menghasilkan nilai X1 = 250 dan X2 = 100 yang
sesuai dengan hasil dari metode grafik. Dengan memasukkan nilai solusi optimal tersebut
ke dalam fungsi tujuan maka diperoleh
Z = 3 X1 + 2 X2
= 3 (250) + 2 (100)
= 950
Karena fungsi tujuan tersebut dinyatakan dalam puluhan ribu rupiah maka keuntungan
perusahaan adalah 9.500.000 rupiah. Tingkat keuntungan ini merupakan keutungan
tertinggi yang dapat dicapai oleh perusahaan TAS Inc.
Ringkasan prosedur problem maksimisasi
1. Persiapkan grafik feasible solusion points untuk setiap fungsi pembatas
2. Tentukan feasible region dengan mengidentifikasi titik-titik solusi yang memenuhi
semua fungsi pembatas secara simultan.
3. Gambarkan garis fungsi tujuan yang menunjukkan nilai dari variabel X1 dan X2 serta
menghasilkan nilai tertentu dari fungsi tujuan.
4. Geser garis fungsi tujuan ke arah luar paralel dengan garis pertama (menjauhi titik
origin) hingga menyinggung bagian terluar dari feasible region.
5. Sebuah titik feasible solusion yang memberikan nilai tertinggi pada fungsi tujuan
merupakan solusi optimal.
6. Solusi optimal terletak pada salah satu titik ekstrim dari feasible region.
Slack variables
Sebagai tambahan dari solusi optimal yaitu X1 = 250 unit tas model Ransel dan X2 = 100
unit tas model klasik dan keuntungan yang diharapkan yaitu Rp. 9.500.000,- manajemen
perusahaan juga ingin mendapatkan informasi mengenai waktu kerja yang digunakan
pada masing-masing bagian produksi. Kita dapat memperoleh informasi ini dengan
mensubstitusikan nilai variabel X1 = 250 dan X2 = 100 kedalam setiap fungsi pembatas,
yaitu:
2 (250) + 2 (100) = 700 jam pada bagian pemotongan
2 (250) + 3.3 (100) = 830 jam pada bagian penjahitan
(250) + 0.5 (100) = 300 jam pada bagian penyelesaian
2 (250) + 1.5 (100) = 650 jam pada bagian pemeriksaan dan pengepakan
Hasil di atas menunjukkan bahwa produksi X1 = 250 unit tas model Ransel dan X2 = 100
unit tas model Klasik telah menggunakan semua kapasitas waktu yang tersedia pada
bagian penyelesaian serta bagian pemeriksaan dan pengepakan namun masih tersisa 100
jam (yaitu 800-700) pada bagian pemotongan dan 170 jam (yaitu 1000-830) pada bagian
penjahitan. Bagian dari sumberdaya yang tidak habis digunakan ini dalam terminology
riset operasi disebut slack untuk kendala yang terkait dengan sumberdaya tersebut.
B. Problem Minimisasi Sederhana
Kasus perusahaan TAS Inc. adalah contoh masalah maksimisasi; namun banyak
masalah program linear berhubungan dengan minimisasi. Berikut adalah masalah
minimisasi yang dihadapi oleh perusahaan SBN.
1. Ilustrasi
Perusahaan SBN memproduksi dua jenis bahan kimia untuk pembuatan sabun yaitu
untuk sabun mandi (soaps) dan sabun cuci (detergens). Berdasarkan pada analisa
ketersediaan bahan baku dan permintaan bulan mendatang maka manajemen
memutuskan untuk menghasilkan total barang 1 dan barang 2 seperti tersebut di atas
minimal sebanyak 350 galon. Untuk bulan depan telah diperoleh pesanan barang 1 tidak
kurang dari 125 galon. Untuk menghasilkan setiap galon barang 1 memerlukan 2 jam
pengerjaan sedangkan barang 2 memerlukan 1 jam waktu pengerjaan. Ketersediaan
waktu pengerjaan untuk bulan depan hanya tersisa 600 jam. Tujuan perusahaan SBN
adalah menghasilkan barang 1 dan 2 yang memenuhi persyaratan di atas dengan total
biaya produksi yang minimum. Biaya produksi untuk menghasilkan barang 1 adalah $ 2
per galon sementara biaya untuk barang 2 adalah $ 3 per galon.
Untuk menyelesaikan masalah perusahaan SBN maka model linear dari masalah tersebut
perlu disusun. Pertama adalah menetapkan variabel keputusan dan fungsi tujuan, sebagai
berikut:
X1 = jumlah barang 1 yang harus diproduksi (galon)
X2 = jumlah barang 2 yang harus diproduksi (galon)
Oleh karena biaya produksi barang 1 sebesar $ 2 per galon dan biaya untuk barang 2
adalah $ 3 per galon maka fungsi tujuan yang menyangkut minimisasi dinyatakan oleh
persamaan berikut:
Min 2 X1 + 3 X2
Berikutnya adalah menyusun kendala yang dihadapi yaitu pertama, permintaan untuk
barang 1 minimal 125 galon. Jadi kendalanya adalah:
X1 ≥ 125
Oleh karena total kombinasi kedua barang paling tidak 350 galon maka kendala kedua
dapat ditulis sebagai berikut:
X1 + X2 ≥ 350
Akhirnya karena ketersediaan waktu pengerjaan hanya 600 jam sementara untuk
menghasilkan satu galon barang 1 memerlukan 2 jam pengerjaan dan untuk
menghasilkan satu galon barang 2 memerlukan 1 jam maka kita menuliskan kendala
ketiga sebagai berikut:
2X1 + X2 ≤ 600
Setelah menambahkan kendala non negatif maka model linear dari masalah di atas dapat
ditulis sebagai berikut:
Min 2 X1 + 3 X2
s.t.
X1
≥ 125 Permintaan barang 1
X1
+ X2 ≥ 350 Total produksi
2X1 + X2 ≤ 600 Waktu pengerjaan
X1
, X2 ≥ 0
Karena masalah linear tersebut hanya memiliki dua variabel keputusan maka metode
grafik dapat digunakan untuk menyelesaikannya. Langkah pertama adalah dengan
menggambarkan garis fungsi kendala secara terpisah maka feasible solution untuk
masing-masing kendala dapat ditentukan. Dengan menggabungkan semua feasible
solution yang ada maka diperoleh feasible region seperti pada gambar berikut:
Minimum X1 = 125
Waktu pengerjaan
2X1 + X2 = 600
Produksi
X1 + X2 = 350
0 100 200 300 400 500 600 X1
X2
600
500
400
300
200
100
Gambar 4. Feasible region yang memenuhi semua fungsi
pembatas
2X1 + 3X2 = 1200
2X1 + 3X2 = 800
•
X2
600
500
400
300
200
100
0 100 200 300 400 500 600 X1
Solusi Optimum
(X1= 250, X2 = 100)
Gambar 5. Solusi optimal dari perusahaan SBN
Untuk menemukan solusi biaya minimum, maka perlu digambarkan garis fungsi tujuan
dengan nilai biaya tertentu. Misalkan kita menggambarkan garis fungsi tujuan dengan
nilai 1200 yaitu 2X1 + 3X2 = 1200 seperti terlihat pada gambar 5 di atas. Dari gambar
tersebut terlihat jelas bahwa terdapat titik-titik solusi yang memberikan nilai 1200. Untuk
mendapatkan nilai X1 dan X2 yang menghasilkan biaya minimum maka kita menggeser
garis fungsi tujuan tersebut kearah yang menghasilkan nilai yang lebih kecil yaitu ke arah
kiri-bawah hingga memotong titik terluar dari feasible region. Titik terluar umumnya
merupakan salah satu dari titik-titik ekstrim pada feasible region. Dari gambar tersebut
terlihat bahwa garis fungsi tujuan 2X1 + 3X2 = 800 memotong feasible region di titik
ekstrim X1 = 250 dan X2 = 100. Titik ekstrim inilah yang memberikan solusi biaya yang
minimum dengan nilai 800. Dari kedua gambar tersebut juga terlihat bahwa pada solusi
optimum kendala waktu pengerjaan dan kendala produksi total saling bersilangan
(binding).
Ringkasan prosedur problem Minimisasi
1. Persiapkan grafik feasible solusion points untuk setiap fungsi pembatas
2. Tentukan feasible region dengan mengidentifikasi titik-titik solusi yang memenuhi
semua fungsi pembatas secara simultan.
3. Gambarkan garis fungsi tujuan yang menunjukkan nilai dari variabel X1 dan X2 serta
menghasilkan nilai tertentu dari fungsi tujuan.
4. Geser garis fungsi tujuan ke arah kiri-bawah paralel dengan garis pertama (menuju
titik origin) hingga menyinggung bagian terluar dari feasible region.
5. Sebuah titik feasible solusion yang memberikan nilai terkecil pada fungsi tujuan
merupakan solusi optimal.
6. Solusi optimal terletak pada salah satu titik ekstrim dari feasible region.
C. Penyusunan model (Modeling)
Modeling adalah suatu proses mentranslasikan pernyataan verval dari suatu problem ke
dalam suatu pernyataan matematik. Pada kasus sederhana yang melibatkan dua variabel
keputusan dan beberapa fungsi pembatas, formulasi model dapat dilakukan dengan
cepat. Namun pada kasus yang besar dan rumit dengan melibatkan banyak variabel
keputusan dan kendala maka diperlukan suatu pedoman penyusunan model untuk
membantu menemukan solusi dari persoalan tersebut.
Proses formulasi program linear merupakan suatu seni dengan imajinasi tinggi yang
memerlukan banyak latihan dan pengalaman. Meskipun setiap problem memiliki
keunikan tersendiri namun ia juga memiliki kesamaan-kesamaan umum. Pedoman
penyusunan model akan sangat berguna terutama bagi mereka yang baru mempelajari
program linear.
1. Pahami persoalan secara komprehensif
Bacalah persoalan secara cepat dan cermat untuk membayangkan faktor apa saja
yang terlibat. Identifikasi faktor-faktor tersebut untuk dimasukkan kedalam model.
Jika persoalan tersebut sangat rumit, buatlah catatan seperlunya karena ia akan
membantu dalam menentukan fokus dari persoalan tersebut.
2. Tulislah pernyataan verbal dari fungsi tujuan dan kendala
Pernyataan verbal ini nantinya akan ditraslasikan ke dalam pernyataan matematik.
Pada tahap ini fungsi tujuan dapat berupa maksimumkan keuntungan atau
minimumkan biaya operasi. Meskipun mereka yang sudah berpengalaman sering
mengalami kesulitan bila meninggalkan tahap ini.
3. Definisikan setiap variabel keputusan
Renungkan, keputusan apa yang harus dibuat oleh sang manager. Faktor-faktror apa
saja yang dapat dikontrol. Pendefinisian variabel keputusan harus ditujukan untuk
memudahkan formulasi matematik dari fungsi tujuan dan sisi kiri dari fungsi
pembatas.
4. Tulislah fungsi tujuan sebagai fungsi dari variabel keputusan
Translasikan pernyatan verbal dari fungsi tujuan pada tahap 2 ke dalam pernyataan
matematik. Fungsi tujuan haruslah merupakan fungsi linear dari variabel keputusan.
5. Tulislah kendala sebagai fungsi dari variabel keputusan
Translasikan pernyatan verbal dari semua kendala pada tahap 2 ke dalam pernyataan
matematik. Sisi kiri dari persamaan/pertidaksamaan haruslah merupakan fungsi
linear dari variabel keputusan.
Setelah melalui tahap tersebut kita mendapatkan model liner yang merepresentasikan
persoalan yang dikaji. Penyelesaian dari model tersebut akan menghasilkan solusi
optimal berupa nilai dari variabel keputusan, nilai dari slack/surplus variabel. Solusi
dengan komputer akan memberikan tambahan informasi seperti reduced cost, dual
prices, dan analisis sensitivitas bagi fungsi tujuan dan semua kendala. Melalui
interpretasi yang benar terhadap semua informasi yang diperoleh dapat menghasilkan
keputusan yang dapat dipertanggungjawabkan secara ilmiah.
Program linear adalah suatu pendekatan problem-solving yang dikembangkan untuk membantu manager dalam membuat keputusan.
Pada program linear terdapat dua elemen dasar (properties) yaitu :
- tujuan (objective) dan
- kendala (constraints).
Fungsi tujuan dapat berupa maksimisasi atau minimisasi dari suatu kuantitas
Fungsi kendala adalah fungsi yang membatasi tingkat pencapaian dari fungsi tujuan tersebut.
A. Problem Maksimisasi Sederhana
A.1 Ilustrasi
TAS Inc. adalah suatu industri kecil yang memproduksi tas sekolah.
Para distributor TAS sangat antusias pada rencana perusahaan untuk membuat dua desain baru tas sekolah
yaitu model ransel dan model klasik dan mereka bersedia untuk membeli semua produk baru tersebut dalam 3 bulan mendatang.
Setelah melalui serangkaian penelitian mengenai semua tahap pekerjaan, manajemen perusahaan menyatakan bahwa kedua produk baru tersebut akan melalui tahapan pengerjaan yang meliputi:
1. Pemotongan
2. Penjahitan
3. Penyelesaian akhir
4. Pemeriksaan dan pengepakan
Manager produksi telah menganalisa bahwa untuk menghasilkan satu tas model Ransel memerlukan 2 jam pengerjaan pada bagian pemotongan, 2 jam pada bagian penjahitan, 1 jam pada bagian penyelesaian, dan 2 jam pada bagian pemeriksaan dan pengepakan.
Pada sisi lain, untuk menghasilkan satu tas model Klasik diperlukan 2 jam pengerjaan pada bagian pemotongan, 3.3 jam pada bagian penjahitan, 0.5 jam pada bagian penyelesaian dan 1.5 jam pada bagian pemeriksaan dan pengepakan.
Informasi pengerjaan tersebut disajikan pada tabel berikut:
Waktu yang diperlukan (jam)
Jenis Produksi Pemotongan Penjahitan Penyelesaian Pemeriksaan dan Pengepakan
Model Ransel 2 2 1 2
Model Klasik 2 3.3 0.5 1.5
Bagian akuntansi telah menganalisis bahwa setelah menghitung semua perkiraan biaya
produksi dan harga jual maka akan diperoleh keuntungan sebesar Rp. 30.000,- untuk
setiap tas model Ransel dan Rp. 20.000,- untuk model Klasik yang diproduksi. Dari
departemen produksi diperoleh informasi bahwa untuk 3 bulan mendatang hanya tersedia
800 jam kerja pada bagian pemotongan, 1000 jam pada bagian penjahitan, 300 jam pada
bagian penyelesaian dan 650 jam pada bagian pemeriksaan dan pengepakan.
Masalah yang dihadapi oleh perusahaan TAS Inc. adalah menentukan berapa banyak tas
model Ransel, dan berapa banyak model Klasik yang harus diproduksi untuk
memaksimumkan keuntungan dengan memperhatikan ketersediaan waktu kerja pada
setiap bagian tersebut. Jika anda ditugaskan bada bagian produksi, keputusan apa yang
anda buat, yaitu berapa banyak tas Model Ransel dan Model Klasik masing-masing harus
diproduksi dalam waktu 3 bulan mendatang? Tulislah keputusan anda pada tempat
berikut dan anda akan memeriksa keputusan tersebut nanti.
Jumlah tas
Model Ransel
Jumlah tas
Model Klasik
Total
Keuntungan
2. Fungsi Tujuan
Seperti dinyatakan di depan bahwa pada setiap program─── linear terdapat fungsi tujuan
untuk memaksimumkan atau meminimumkan sesuatu. Pada kasus perusahaan TAS Inc.,
tujuannya adalah memaksimumkan keuntungan. Kita dapat menuliskan tujuan tersebut
kedalam notasi matematik yaitu:
X1 = jumlah tas model Ransel yang diproduksi
X2 = jumlah tas model Klasik yang diproduksi
Keuntungan perusahaan berasal dari dua sumber yaitu dari produksi tas model Ransel
(X1) dan dari model Klasik (X2). Karena keuntungan dari model Ransel adalah Rp.
30.000,- per unit dan model Klasik Rp. 20.000,- per unit maka total keuntungan
perusahaan adalah Rp. 30.000 X1 + Rp. 20.000 X2, dimana 30.000X1 merupakan
kontribusi keuntungan model Ransel dan Rp. 20.000 X2 merupakan kontribusi dari model
Klasik. Bila total keuntungan dilambangkan oleh simbol Ζ dalam puluhan ribu rupiah
(Rp. 10.000) maka:
Total keuntungan = Ζ = 3 X1 + 2 X2
Problem perusahaan TAS adalah menentukan nilai variabel X1 dan variabel X2 yang
memberikan nilai maksimum Ζ. Dalam termonologi program linear variabel X1 , X2
disebut variabel keputusan (decision variables). Karena tujuan -- yaitu memaksimumkan
keuntungan-- merupakan fungsi dari variabel keputusan maka persamaan Ζ = 3 X1 +2 X2
disebut dengan fungsi tujuan (objective function). Dengan demikian tujuan dari
perusahaan TAS dapat dinyatakan dengan:
Max Ζ = 3 X1 + 2 X2
Setiap kombinasi produksi tas Model Ransel dan Klasik merupakan solusi dari masalah
ini. Namun demikian hanya solusi yang memenuhi semua kendala atau pembatas yang
dinyatakan sebagai solusi yang layak (feasible solusions). Kombinasi produksi yang
layak (feasible solusions) dan memberikan keuntungan maksimum merupakan kombinasi
yang optimum atau disebut juga solusi optimum (optimal solusion).
Sejauh ini kita belum dapat menentukan optimal solusion bahkan feasible solusions dari
perusahaan TAS karena kita belum melihat semua kendala yang ada. Untuk mengetahui
feasible solusions maka kita perlu mengidentifikasi semua kendala (constraints).
3. Kendala atau Pembatas (constraints)
Setiap tas model ransel atau klasik harus melalui empat tahapan pengerjaan seperti yang
telah disebut di atas dan karena adanya kendala ketersediaan waktu pada masing-masing
bagian maka dapat diperkirakan bahwa jumlah produksi tas oleh perusahaan akan
terbatas.
Dari informasi produksi diketahui bahwa setiap unit tas model Ransel memerlukan 2 jam
pengerjaan pada bagian pemotongan sehingga total waktu yang dibutuhkan untuk
memotong X1 tas model Ransel adalah 2X1. Di sisi lain untuk menghasilkan satu unit tas
model klasik juga dibutuhkan 2 jam pengerjaan pada bagian pemotongan sehingga total
waktu yang dibutuhkan untuk memotong X2 tas model Klasik adalah 2X2 . Dengan
demikian total waktu yang dibutuhkan untuk memotong X1 tas model Ransel dan X2 tas
model Klasik dinyatakan sebagai:
Total waktu pemotongan yang diperlukan = 2 X1 + 2 X2
Karena manager produksi menyatakan bahwa waktu kerja yang tersedia pada bagian
pemotongan adalah 800 jam maka produksi kedua model tas tersebut harus memenuhi
persyaratan pembatas berikut:
2 X1 + 2 X2 ≤ 800
dimana simbol ≤ menyatakan lebih kecil atau sama dengan. Pertidaksamaan di atas
menunjukkan bahwa jumlah jam kerja yang digunakan untuk proses pemotongan tas
sebanyak X1 dari model Ransel dan X2 untuk model Klasik harus lebih kecil atau sama
dengan jumlah maksimum jam kerja yang masih tersedia di bagian tersebut.
Dari tabel di atas juga terlihat bahwa untuk menghasilkan satu unit tas model Ransel
memerlukan 2 jam penjahitan sedangkan setiap tas model Klasik memerlukan 3.3 jam.
Oleh karena jam kerja yang tersedia hanya 1000 jam, maka fungsi pembatas untuk bagian
panjahitan adalah:
2 X1 + 3.3 X2 ≤ 1000
Dengan cara yang sama kita dapat menyusun fungsi pembatas untuk bagian penyelesaian,
yaitu:
X1 + 0.5 X2 ≤ 300
dan fungsi pembatas untuk bagian pemeriksaan dan pengepakan adalah:
2 X1 + 1.5 X2 ≤ 650
Sejauh ini kita telah merumuskan model matematik dari semua kendala jam kerja pada
setiap bagian proses produksi. Apakah masih ada kendala yang terlupakan? Mungkinkah
perusahaan TAS memproduksi X1 tas model Ransel dan atau X2 model klasik yang
negatif ? Jawabnya sudah jelas tidak mungkin. Oleh karena itu untuk mencegah X1 dan
X2 bernilai negatif maka perlu dimasukkan dua kendala tambahan dalam model yaitu:
X1 ≥ 0 dan X2 ≥ 0
tanda ≥ berarti lebih besar atau sama dengan. Dua kendala yang terakhir ini memastikan
bahwa solusi dari masalah program linear tidak akan pernah bernilai negatif sehingga ia
dikatakan sebagai kendala non negatif (non-negativity constraints). Kendala non negatif
merupakan hal yang umum dijumpai pada program linear dan dituliskan sebagai:
X1, X2 ≥ 0
4. Formulasi Matematik
Formulasi matematik dari masalah perusahaan TAS sekarang sudah lengkap dengan
mentranslasikan masalah riil perusahaan menjadi suatu model matematik. Model lengkap
dari perusahaan TAS adalah:
Max 3 X1 + 2 X2
dengan kendala (subject to, = s.t.)
2 X1 + 2 X2 ≤ 800 pemotongan (P)
2 X1 + 3.3 X2 ≤ 1000 penjahitan (J)
X1 + 0.5 X2 ≤ 300 penyelesaian (S)
2 X1 + 1.5 X2 ≤ 650 pemeriksaan dan pengepakan (R&K)
X1, X2 ≥ 0
Langkah berikutnya adalah mencari kombinasi nilai X1 dan X 2 yang memenuhi semua
kendala serta menghasilkan nilai dari fungsi tujuan yang lebih besar atau sama dengan
nilai pada feasible solusion. Bila hal ini telah dilakukan maka solusi optimum akan
tercapai.
5. Solusi Grafik
Program linear yang hanya melibatkan dua variabel (X1, X2 ) dapat diselesaikan dengan
metode grafik. Untuk masalah yang melibatkan lebih dari dua variabel keputusan maka
penyelesaianya dilakukan dengan metode Simplex. Setelah tahun 1980-an seiring dengan
perkembangan mikrokomputer maka solusi dari masalah program linear dapat dilakukan
dengan komputer. Beberapa program yang dapat digunakan adalah: LINDO, LINGGO,
dan THE MANAGEMENT SCIENTIST.
Penggunaan metode grafik dimulai dengan menentukan sumbu horisontal (X1)dan sumbu
vertikal (X2) sehingga nilai dari variabel keputusan X1 berada pada sumbu horisontal dan
nilai dari variabel keputusan X2 berada pada sumbu vertikal. Karena setiap titik
merupakan solusi yang mungkin (possible), maka titik-titik pada grafik merupakan
solusion points (titik-titik solusi). Solusion point dimana X1 = 0 dan X2 = 0 disebut titik
origin.
Langkah berikutnya adalah menentukan manakah dari titik-titik solusi yang berhubungan
dangan feasibel solusion. Karena X1, X2 adalah nonnegatif maka kita hanya
mempertimbangan sebagian saja dari grafik tersebut yang memenuhi persyaratan nonnegatif
X1, X2 ≥ 0 [lihat panel (a) pada grafik]. Selanjutnya adalah menggambarkan grafik
dari semua fungsi pembatas (constraints) seperti diformulasikan pada model matematik.
Dari model tersebut terlihat bahwa fungsi pembatas pemotongan dicerminkan oleh
pertidaksamaan:
2 X1 + 2 X2 ≤ 800
Untuk mendapatkan titik-titik solusi yang memenuhi kondisi ini dimulai dengan
menggambarkan hubungan tersebut sebagai suatu persamaan yaitu titik-titik yang
memenuhi persamaan 2 X1 + 2 X2 = 800. Karena persamaan ini merupakan garis lurus
maka ia dapat digambarkan dengan mencari dua titik yang memenuhi persamaan
tersebut dan selanjutnya menarik garis yang melalui kedua titik tersebut. Titik pertama
diperoleh dengan menetapkan nilai X1 = 0 dan mendapatkan nilai X2 = 40 yang
memenuhi persamaan tersebut. Titik kedua diperoleh dengan menetapkan X2 = 0 dan
mendapatkan nilai X1 = 40. Apabila titik pertama (X1 = 0, X2 = 40) dan titik kedua (X1
= 40, X2 = 0) dihubungkan maka diperoleh garis lurus seperti pada grafik panel (b).
Karena fungsi pembatas proses pemotongan merupakan pertidaksamaan
2 X1 + 2 X2 ≤ 800
manakah titik-titik solusi yang memenuhi pertidaksamaan tersebut? Karena semua titik
pada garis memenuhi persamaan 2X1 + 2X2 = 800 maka kita yakin bahwa semua titik
pada garis tersebut memenuhi fungsi kendala. Namun manakah titik-titik solusi yang
memenuhi pertidaksamaan 2X1 + 2X2 < 800? Setiap titik yang berada di bagian dalam
kurva menuju titik origin seperti ditunjukkan oleh tanda panah adalah titik-titik solusi.
Dengan cara yang sama kita dapat menggambarkan fungsi pembatas untuk bagian
penjahitan (panel c), bagian penyelesaian (panel d), serta bagian pemeriksaan dan
pengepakan (panel e).
Sekarang kita telah mendapatkan empat grafik terpisah untuk masing-masing fungsi
kendala. Dalam program linear kita perlu mengidentifikasi titik-titik solusi yang
memenuhi semua kendala secara simultan. Untuk itu kita perlu menggambarkan keempat
kendala tersebut dalam satu salib sumbu dan memperhatikan daerah yang terdiri dari
titik-titik yang memenuhi keempat kendala secara simultan (panel f). Karena solusi yang
memenuhi keempat kendala tersebut dikenal dengan feasible solusion, maka daerah yang
merupakan titik-titik solusi disebut feasible solusion region atau sederhananya feasible
region. Setiap titik pada garis batas feasible region atau di dalam feasible region adalah
titik solusi yang feasible (feasible solusion point).
Gambar 2 menampilkan kembali feasible region yang memenuhi keempat fungsi
pembatas dengan skala yang lebih besar agar lebih memudahkan menemukan solusi
optimal.
Solusi optimal dapat diketahui dengan mengevaluasi setiap feasible solusion dan solusi
yang memberikan nilai fungsi tujuan yang terbesar adalah solusi optimal. Masalahnya
adalah feasible solusion tersebut jumlahnya tidak terhingga. Oleh karena itu langkah yang
paling efisien adalah dengan menentukan satu nilai feasible solusion dan
menggambarkannya pada kurva feasible region. Setelah itu menggeser garis fungsi tujuan
tersebut hingga menyinggung titik dari daerah feasible yang terluar (Gambar 3). Titik
singgung itulah yang merupakan solusi optimal dari program linear tersebut.
X2 X2
400
P
Non negativity
200
0 X1 0 200 400 X1
0 200 400 X1 0 200 400 600 X1
0
X2
400
200
200 400 X1 0 200 400 X1
X2
600
400
200
J
S
(a)
(b)
(c)
(d)
X2 (e) (f)
400
200
X2
600
400
200
R&K
Gambar 1. Feasible solusion untuk setiap fungsi pembatas
•
•
•
•
0 200 400 600 X1
X2
600
400
200
Pemotongan
Penjahitan
Penyelesaian
Pemeriksaan dan pengepakan
Gambar 2. Feasible region yang memenuhi keempat
fungsi pembatas secara simultan
Feasible region
•
•
c
•
Feasible region
0 200 400 600 X1
X2
600
400
200
3X1 + 2X2 = 950 persamaan fungsi tujuan
Solusi optimal
a
b
d
(250 , 100)
Gambar 3. Solusi optimal dari perusahaan TAS Inc.
•
Untuk memperoleh solusi optimal yang tepat sangat tergantung pada tingkat ketelitian
skala pembuatan grafik. Dengan mengacu pada gambar 3 tersebut di atas dapat
disimpulkan bahwa kombinasi produksi yang memberikan keuntungan maksimum
ditunjukkan oleh titik ekstrim c yaitu 250 unit tas model Ransel (X1) dan 100 unit tas
model Klasik (X2).
Untuk lebih meyakinkan akurasi solusi optimal dapat dilakukan dengan menyelesaikan
persamaan simultan yang berhubungan dengan titik perpotongan dua garis. Dengan
memperhatikan gambar 2 dan gambar 3 terlihat bahwa solusi optimal berada pada titik c
yang merupakan perpotongan fungsi pembatas penyelesaian
X1 + 0.5 X2 = 300 (1)
dengan fungsi pembatas pemeriksaan dan pengepakan yaitu :
2 X1 + 1.5 X2 = 650 (2)
Dari persamaan (1) diperoleh
X1 = 300 - 0.5 X2 . (3)
Dengan mensubstitusikan nilai X1 ke dalam persamaan (2) didapat nilai X2 , yaitu:
2(300 - 0.5 X2) + 1.5 X2 = 650
600 - X2 + 1.5 X2 = 650
0.5 X2 = 650 - 600
X2
= 50/0.5
= 100
Setelah memasukkan nilai X2 = 100 ke dalam persamaan (3) untuk diperoleh nilai X1
yaitu:
X1 = 300 - 0.5 X2
= 300 - 0.5 (100)
= 300 - 50
= 250
Solusi dari persamaan simultan tersebut menghasilkan nilai X1 = 250 dan X2 = 100 yang
sesuai dengan hasil dari metode grafik. Dengan memasukkan nilai solusi optimal tersebut
ke dalam fungsi tujuan maka diperoleh
Z = 3 X1 + 2 X2
= 3 (250) + 2 (100)
= 950
Karena fungsi tujuan tersebut dinyatakan dalam puluhan ribu rupiah maka keuntungan
perusahaan adalah 9.500.000 rupiah. Tingkat keuntungan ini merupakan keutungan
tertinggi yang dapat dicapai oleh perusahaan TAS Inc.
Ringkasan prosedur problem maksimisasi
1. Persiapkan grafik feasible solusion points untuk setiap fungsi pembatas
2. Tentukan feasible region dengan mengidentifikasi titik-titik solusi yang memenuhi
semua fungsi pembatas secara simultan.
3. Gambarkan garis fungsi tujuan yang menunjukkan nilai dari variabel X1 dan X2 serta
menghasilkan nilai tertentu dari fungsi tujuan.
4. Geser garis fungsi tujuan ke arah luar paralel dengan garis pertama (menjauhi titik
origin) hingga menyinggung bagian terluar dari feasible region.
5. Sebuah titik feasible solusion yang memberikan nilai tertinggi pada fungsi tujuan
merupakan solusi optimal.
6. Solusi optimal terletak pada salah satu titik ekstrim dari feasible region.
Slack variables
Sebagai tambahan dari solusi optimal yaitu X1 = 250 unit tas model Ransel dan X2 = 100
unit tas model klasik dan keuntungan yang diharapkan yaitu Rp. 9.500.000,- manajemen
perusahaan juga ingin mendapatkan informasi mengenai waktu kerja yang digunakan
pada masing-masing bagian produksi. Kita dapat memperoleh informasi ini dengan
mensubstitusikan nilai variabel X1 = 250 dan X2 = 100 kedalam setiap fungsi pembatas,
yaitu:
2 (250) + 2 (100) = 700 jam pada bagian pemotongan
2 (250) + 3.3 (100) = 830 jam pada bagian penjahitan
(250) + 0.5 (100) = 300 jam pada bagian penyelesaian
2 (250) + 1.5 (100) = 650 jam pada bagian pemeriksaan dan pengepakan
Hasil di atas menunjukkan bahwa produksi X1 = 250 unit tas model Ransel dan X2 = 100
unit tas model Klasik telah menggunakan semua kapasitas waktu yang tersedia pada
bagian penyelesaian serta bagian pemeriksaan dan pengepakan namun masih tersisa 100
jam (yaitu 800-700) pada bagian pemotongan dan 170 jam (yaitu 1000-830) pada bagian
penjahitan. Bagian dari sumberdaya yang tidak habis digunakan ini dalam terminology
riset operasi disebut slack untuk kendala yang terkait dengan sumberdaya tersebut.
B. Problem Minimisasi Sederhana
Kasus perusahaan TAS Inc. adalah contoh masalah maksimisasi; namun banyak
masalah program linear berhubungan dengan minimisasi. Berikut adalah masalah
minimisasi yang dihadapi oleh perusahaan SBN.
1. Ilustrasi
Perusahaan SBN memproduksi dua jenis bahan kimia untuk pembuatan sabun yaitu
untuk sabun mandi (soaps) dan sabun cuci (detergens). Berdasarkan pada analisa
ketersediaan bahan baku dan permintaan bulan mendatang maka manajemen
memutuskan untuk menghasilkan total barang 1 dan barang 2 seperti tersebut di atas
minimal sebanyak 350 galon. Untuk bulan depan telah diperoleh pesanan barang 1 tidak
kurang dari 125 galon. Untuk menghasilkan setiap galon barang 1 memerlukan 2 jam
pengerjaan sedangkan barang 2 memerlukan 1 jam waktu pengerjaan. Ketersediaan
waktu pengerjaan untuk bulan depan hanya tersisa 600 jam. Tujuan perusahaan SBN
adalah menghasilkan barang 1 dan 2 yang memenuhi persyaratan di atas dengan total
biaya produksi yang minimum. Biaya produksi untuk menghasilkan barang 1 adalah $ 2
per galon sementara biaya untuk barang 2 adalah $ 3 per galon.
Untuk menyelesaikan masalah perusahaan SBN maka model linear dari masalah tersebut
perlu disusun. Pertama adalah menetapkan variabel keputusan dan fungsi tujuan, sebagai
berikut:
X1 = jumlah barang 1 yang harus diproduksi (galon)
X2 = jumlah barang 2 yang harus diproduksi (galon)
Oleh karena biaya produksi barang 1 sebesar $ 2 per galon dan biaya untuk barang 2
adalah $ 3 per galon maka fungsi tujuan yang menyangkut minimisasi dinyatakan oleh
persamaan berikut:
Min 2 X1 + 3 X2
Berikutnya adalah menyusun kendala yang dihadapi yaitu pertama, permintaan untuk
barang 1 minimal 125 galon. Jadi kendalanya adalah:
X1 ≥ 125
Oleh karena total kombinasi kedua barang paling tidak 350 galon maka kendala kedua
dapat ditulis sebagai berikut:
X1 + X2 ≥ 350
Akhirnya karena ketersediaan waktu pengerjaan hanya 600 jam sementara untuk
menghasilkan satu galon barang 1 memerlukan 2 jam pengerjaan dan untuk
menghasilkan satu galon barang 2 memerlukan 1 jam maka kita menuliskan kendala
ketiga sebagai berikut:
2X1 + X2 ≤ 600
Setelah menambahkan kendala non negatif maka model linear dari masalah di atas dapat
ditulis sebagai berikut:
Min 2 X1 + 3 X2
s.t.
X1
≥ 125 Permintaan barang 1
X1
+ X2 ≥ 350 Total produksi
2X1 + X2 ≤ 600 Waktu pengerjaan
X1
, X2 ≥ 0
Karena masalah linear tersebut hanya memiliki dua variabel keputusan maka metode
grafik dapat digunakan untuk menyelesaikannya. Langkah pertama adalah dengan
menggambarkan garis fungsi kendala secara terpisah maka feasible solution untuk
masing-masing kendala dapat ditentukan. Dengan menggabungkan semua feasible
solution yang ada maka diperoleh feasible region seperti pada gambar berikut:
Minimum X1 = 125
Waktu pengerjaan
2X1 + X2 = 600
Produksi
X1 + X2 = 350
0 100 200 300 400 500 600 X1
X2
600
500
400
300
200
100
Gambar 4. Feasible region yang memenuhi semua fungsi
pembatas
2X1 + 3X2 = 1200
2X1 + 3X2 = 800
•
X2
600
500
400
300
200
100
0 100 200 300 400 500 600 X1
Solusi Optimum
(X1= 250, X2 = 100)
Gambar 5. Solusi optimal dari perusahaan SBN
Untuk menemukan solusi biaya minimum, maka perlu digambarkan garis fungsi tujuan
dengan nilai biaya tertentu. Misalkan kita menggambarkan garis fungsi tujuan dengan
nilai 1200 yaitu 2X1 + 3X2 = 1200 seperti terlihat pada gambar 5 di atas. Dari gambar
tersebut terlihat jelas bahwa terdapat titik-titik solusi yang memberikan nilai 1200. Untuk
mendapatkan nilai X1 dan X2 yang menghasilkan biaya minimum maka kita menggeser
garis fungsi tujuan tersebut kearah yang menghasilkan nilai yang lebih kecil yaitu ke arah
kiri-bawah hingga memotong titik terluar dari feasible region. Titik terluar umumnya
merupakan salah satu dari titik-titik ekstrim pada feasible region. Dari gambar tersebut
terlihat bahwa garis fungsi tujuan 2X1 + 3X2 = 800 memotong feasible region di titik
ekstrim X1 = 250 dan X2 = 100. Titik ekstrim inilah yang memberikan solusi biaya yang
minimum dengan nilai 800. Dari kedua gambar tersebut juga terlihat bahwa pada solusi
optimum kendala waktu pengerjaan dan kendala produksi total saling bersilangan
(binding).
Ringkasan prosedur problem Minimisasi
1. Persiapkan grafik feasible solusion points untuk setiap fungsi pembatas
2. Tentukan feasible region dengan mengidentifikasi titik-titik solusi yang memenuhi
semua fungsi pembatas secara simultan.
3. Gambarkan garis fungsi tujuan yang menunjukkan nilai dari variabel X1 dan X2 serta
menghasilkan nilai tertentu dari fungsi tujuan.
4. Geser garis fungsi tujuan ke arah kiri-bawah paralel dengan garis pertama (menuju
titik origin) hingga menyinggung bagian terluar dari feasible region.
5. Sebuah titik feasible solusion yang memberikan nilai terkecil pada fungsi tujuan
merupakan solusi optimal.
6. Solusi optimal terletak pada salah satu titik ekstrim dari feasible region.
C. Penyusunan model (Modeling)
Modeling adalah suatu proses mentranslasikan pernyataan verval dari suatu problem ke
dalam suatu pernyataan matematik. Pada kasus sederhana yang melibatkan dua variabel
keputusan dan beberapa fungsi pembatas, formulasi model dapat dilakukan dengan
cepat. Namun pada kasus yang besar dan rumit dengan melibatkan banyak variabel
keputusan dan kendala maka diperlukan suatu pedoman penyusunan model untuk
membantu menemukan solusi dari persoalan tersebut.
Proses formulasi program linear merupakan suatu seni dengan imajinasi tinggi yang
memerlukan banyak latihan dan pengalaman. Meskipun setiap problem memiliki
keunikan tersendiri namun ia juga memiliki kesamaan-kesamaan umum. Pedoman
penyusunan model akan sangat berguna terutama bagi mereka yang baru mempelajari
program linear.
1. Pahami persoalan secara komprehensif
Bacalah persoalan secara cepat dan cermat untuk membayangkan faktor apa saja
yang terlibat. Identifikasi faktor-faktor tersebut untuk dimasukkan kedalam model.
Jika persoalan tersebut sangat rumit, buatlah catatan seperlunya karena ia akan
membantu dalam menentukan fokus dari persoalan tersebut.
2. Tulislah pernyataan verbal dari fungsi tujuan dan kendala
Pernyataan verbal ini nantinya akan ditraslasikan ke dalam pernyataan matematik.
Pada tahap ini fungsi tujuan dapat berupa maksimumkan keuntungan atau
minimumkan biaya operasi. Meskipun mereka yang sudah berpengalaman sering
mengalami kesulitan bila meninggalkan tahap ini.
3. Definisikan setiap variabel keputusan
Renungkan, keputusan apa yang harus dibuat oleh sang manager. Faktor-faktror apa
saja yang dapat dikontrol. Pendefinisian variabel keputusan harus ditujukan untuk
memudahkan formulasi matematik dari fungsi tujuan dan sisi kiri dari fungsi
pembatas.
4. Tulislah fungsi tujuan sebagai fungsi dari variabel keputusan
Translasikan pernyatan verbal dari fungsi tujuan pada tahap 2 ke dalam pernyataan
matematik. Fungsi tujuan haruslah merupakan fungsi linear dari variabel keputusan.
5. Tulislah kendala sebagai fungsi dari variabel keputusan
Translasikan pernyatan verbal dari semua kendala pada tahap 2 ke dalam pernyataan
matematik. Sisi kiri dari persamaan/pertidaksamaan haruslah merupakan fungsi
linear dari variabel keputusan.
Setelah melalui tahap tersebut kita mendapatkan model liner yang merepresentasikan
persoalan yang dikaji. Penyelesaian dari model tersebut akan menghasilkan solusi
optimal berupa nilai dari variabel keputusan, nilai dari slack/surplus variabel. Solusi
dengan komputer akan memberikan tambahan informasi seperti reduced cost, dual
prices, dan analisis sensitivitas bagi fungsi tujuan dan semua kendala. Melalui
interpretasi yang benar terhadap semua informasi yang diperoleh dapat menghasilkan
keputusan yang dapat dipertanggungjawabkan secara ilmiah.
sumber : soejatmiko.blogspot.com
0 komentar:
Post a Comment