operational research bab ii

8/2/2019 OPERATIONaL RESEARCH BAB II

1/16

BAB II

LANDASAN TEORI

2.1 Program LinierLevin et. al (1995) menyatakan bahwa programma linier merupakan teknik

matematika untuk mendapatkan alternatif penggunaan terbaik (optimum) atas

sumber sumber organisasi. Dunn (1981) menyatakan bahwa programma linier

merupakan penyajian teoritis secara sederhana mengenai hubungan antara dua atau

lebih variabel bebas (dinamakan tujuan), dengan menggunakan kendala (batas atas

dan batas bawah) nilai nilai dari variabel tersebut.Welch dan Commer (1983)

menyatakan programma linier merupakan teknik untuk menghitung kombinasi

optimum dari sumber sumber tertentu agar dapat tercapai tujuan yang semaksimal

mungkin sebagaimana yang telah ditetapkan sebelumnya.

Levin et. al (1995), menyatakan penggunaan programma linier sebagai

teknik pengambilan keputusan menggunakan tiga tahap proses, yaitu :

1. Perumusan masalah; mengumpulkan informasi yang sesuai, mempelajari

pertanyaan apa yang harus dijawab, dan membuat permasalahan ke dalam

bentuk programma linier

2. Pemecahan masalah; mencari pemecahan optimal programma linier

3. Interpretasi dan penerapan solusi; pemeriksaan bahwa solusi dari

programma linier sudah benar (dan bila tidak, harus kembali ke tahap 1

dan memperbaiki rumusannya), mengerjakan analisa sensitivitas yang

cocok dan menerapkan ke dalam praktek

Levin et. al (1995) menyatakan bahwa persyaratan utama dalam pemecahan

masalah programma linier adalah :

1. Memiliki tujuan. Umumnya tujuan utama dari sebuah programma linier

berupa bentuk memaksimasi keuntungan (laba) dan atau meminimasi

biaya. Disadari bahwa bentuk trend (kecenderungan) keuntungan dan

biaya tidak selalu berhubungan secara linier dengan volume penjualan atau

jumlah produksi.

II-1


2/16

2. Harus ada alternatif tindakan yang salah satu darinya akan mencapai tujuan.

Sebagai contoh, suatu perusahaan harus mengalokasikan kapasitasnyadalam

suatu bentuk perbandingan, misalnya 50:50, 25:75, to:30 atau dalam angka

perbandingan lainnya.

3. Sumber yang diperhitungkan dalam model merupakan persediaan terbatas.

Misalnya sebuah perusahaan mempunyai jumlah mesin, sumber daya

manusia, waktu, dan sumber daya sumberdaya lainnya yang terbatas;

dalam perusahaan konveksi fenomena ini dapat diamati melalui sebuah

fungsi sebab-akibat, untuk perusahaan yang membuat dua produk, celana

dan baju; semakin banyak waktu digunakan untuk membuat celana semakin

sedikit baju yang dapat dibuat.

4. Tujuan dan keterbatasannya dinyatakan dalam bentuk persamaan atau

pertidaksamaan matematika(formulasimatematika), dan harus ada

persamaan atau pertidaksamaan linier

2.1.1 Asumsi Program Linier

Untuk dapat menyelesaikan pemecahan masalah programma linier terdapat

beberapa asumsi / persyaratan utama yang harus dipenuhi seperti yang

dikemukakan Priyarsono (1999),Levinet.al.(1992)dan Supranto (1991 )yaitu :

1. Fungsi objektif harus didefinisikan secara jelas dan dinyatakan sebagai

fungsi objektif yang linear.

2. Harus ada alternatif tindakan/pemecahan untuk dipilih menjadi yang terbaik.

3. Sumber dan aktivitas yang diperhitungkan dalam model mempunyai jumlah

terbatas (finiteness).

4. Tujuan dan segenap keterbatasannya dinyatakan dalam bentuk persamaanatau pertidaksamaan matematika (formulasi matematika), dan harus ada

persamaan atau pertidaksamaan linier.

5. Sumbangan tiap kegiatan terhadap nilai fungsi tujuan Z diassumsikan

sebanding (proporsional) dengan taraf kegiatan xj, sebagaimana terungkap

pada suku cjxj dalam fungsi tujuan. Demikian pula suku aijxj dalam

II-2


3/16

kendala, sumbangan tiap kegiatan terhadap kendala proporsional dengan

taraf kegiatan tersebut.

6. Sumber-sumber dan aktivitas mempunyai sifat dapat dibagi (divisibilitas).

7. Sumber-sumber dan aktivitas mempunyai sifat dapat ditambahkan

(aditivitas)

8. Variabel keputusan harus positif, tidak boleh negatif Xj > 0,untuk semua j.

9. Model programming deterministic, artinya sumber dan aktivitas diketahui

secara pasti (single-valued expectations).

2.1.2 Karakteristik Pemrograman Linier

1. Sifat linearitas suatu kasus dapat ditentukan dengan menggunakan beberapa

cara. Secara statistik, kita dapat memeriksa kelinearan menggunakan grafik

(diagram pencar) ataupun menggunakan uji hipotesa. Secara teknis,

linearitas ditunjukkan oleh adanya sifat proporsionalitas, additivitas,

divisibilitas dan kepastian fungsi tujuan dan pembatas.

2. Sifat proporsional dipenuhi jika kontribusi setiap variabel pada fungsi

tujuan atau penggunaan sumber daya yang membatasi proporsional terhadap

level nilai variabel. Jika harga per unit produk misalnya adalah sama

berapapun jumlah yang dibeli, maka sifat proporsional dipenuhi. Atau

dengan kata lain, jika pembelian dalam jumlah besar mendapatkan diskon,

maka sifat proporsional tidak dipenuhi. Jika penggunaan sumber daya per

unitnya tergantung dari jumlah yang diproduksi, maka sifat proporsionalitas

tidak dipenuhi.

3. Sifat additivitas mengasumsikan bahwa tidak ada bentuk perkalian silang

diantara berbagai aktivitas, sehingga tidak akan ditemukan bentuk perkaliansilang pada model. Sifat additivitas berlaku baik bagi fungsi tujuan maupun

pembatas (kendala). Sifat additivitas dipenuhi jika fungsi tujuan merupakan

penambahan langsung kontribusi masing-masing variabel keputusan. Untuk

fungsi kendala, sifat additivitas dipenuhi jika nilai kanan merupakan total

penggunaaan masing-masing variabel keputusan. Jika dua variabel

keputusan misalnya merepresentasikan dua produk substitusi, dimana

II-3


4/16

peningkatan volume penjualan salah satu produk akan mengurangi volume

penjualan produk lainnya dalam pasar yang sama, maka sifat additivitas

tidak terpenuhi.

4 Sifat divisibilitas berarti unit aktivitas dapat dibagi ke dalam sembarang

level fraksional, sehingga nilai variabel keputusan non integer

dimungkinkan. Sifat kepastianmenunjukkan bahwa semua parameter model

berupa konstanta. Artinya koefisien fungsi tujuan maupun fungsi pembatas

merupakan suatu nilai pasti, bukan merupakan nilai dengan peluang

tertentu.

Keempat asumsi (sifat) ini dalam dunia nyata tidak selalu dapat dipenuhi.

Untuk meyakinkan dipenuhinya keempat asumsi ini, dalam pemrograman linier

diperlukan analisis sensitivitas terhadap solusi optimal yang diperoleh.

2.1.3 Formulasi Permasalahan

Urutan pertama dalam penyelesaian adalah mempelajari sistem relevan dan

mengembangkan pernyataan permasalahan yang dipertimbangakan dengan jelas.

Penggambaran sistem dalam pernyataan ini termasuk pernyataan tujuan, sumber

daya yang membatasi, alternatif keputusan yang mungkin (kegiatan atau aktivitas),

batasan waktu pengambilan keputusan, hubungan antara bagian yang dipelajari dan

bagian lain dalam perusahaan, dan lain-lain.

Penetapan tujuan yang tepat merupakan aspek yang sangat penting dalam

formulasi masalah. Untuk membentuk tujuan optimalisasi, diperlukan identifikasi

anggota manajemen yang benar-benar akan melakukan pengambilan keputusan dan

mendiskusikan pemikiran mereka tentang tujuan yang ingin dicapai.

2.1.4 Pembentukan model matematik

Tahap berikutnya yang harus dilakukan setelah memahami permasalahan

optimasi adalah membuat model yang sesuai untuk analisis. Pendekatan

konvensional riset operasional untuk pemodelan adalah membangun model

matematik yang menggambarkan inti permasalahan. Kasus dari bentuk cerita

diterjemahkan ke model matematik. Model matematik merupakan representasi

II-4


5/16

kuantitatif tujuan dan sumber daya yang membatasi sebagai fungsi variabel

keputusan. Model matematika permasalahan optimal terdiri dari dua bagian.

Bagian pertama memodelkan tujuan optimasi. Model matematik tujuan selalu

menggunakan bentuk persamaan. Bentuk persamaan digunakan karena kita ingin

mendapatkan solusi optimum pada satu titik. Fungsi tujuan yang akan dioptimalkan

hanya satu. Bukan berarti bahwa permasalahan optimasi hanya dihadapkan pada

satu tujuan. Tujuan dari suatu usaha bisa lebih dari satu. Tetapi pada bagian ini kita

hanya akan tertarik dengan permasalahan optimal dengan satu tujuan.

Bagian kedua merupakan model matematik yang merepresentasikan sumber

daya yang membatasi. Fungsi pembatas bisa berbentuk persamaan (=) atau

pertidaksamaan ( atau ). Fungsi pembatas disebut juga sebagai konstrain.

Konstanta (baik sebagai koefisien maupun nilai kanan) dalam fungsi pembatas

maupun pada tujuan dikatakan sebagai parameter model. Model matematika

mempunyai beberapa keuntungan dibandingakan pendeskripsian permasalahan

secara verbal. Salah satu keuntungan yang paling jelas adala model matematik

menggambarkan permasalahan secara lebih ringkas. Hal ini cenderung membuat

struktur keseluruhan permasalahan lebih mudah dipahami, dan membantu

mengungkapkan relasi sebab akibat penting. Model matematik juga memfasilitasi

yang berhubungan dengan permasalahan dan keseluruhannya dan

mempertimbangkan semua keterhubungannya secara simultan. Terakhir, model

matematik membentuk jembatan ke penggunaan teknik matematik dan komputer

kemampuan tinggi untuk menganalisis permasalahan.

Di sisi lain, model matematik mempunyai kelemahan. Tidak semua

karakteristik sistem dapat dengan mudah dimodelkan menggunakan fungsi

matematik. Meskipun dapat dimodelkan dengan fungsi matematik, kadang-kadangpenyelesaiannya sulit diperoleh karena kompleksitas fungsi dan teknik yang

dibutuhkan.

Bentuk umum pemrograman linier adalah sebagai berikut :

II-5


6/16

Fungsi tujuan :

Maksimumkan atau minimumkan

z = c1x1 + c2x2 + ... + cnxn

Sumber daya yang membatasi :

a11x1 + a12x2 + ... + a1nxn = / / b1

a21x1 + a22x2 + + a2nxn = / / b2

am1x1 + am2x2 + + amnxn = / / bm

x1, x2, , xn 0

Simbol x1, x2, ..., xn (xi) menunjukkan variabel keputusan. Jumlah variabel

keputusan (xi) oleh karenanya tergantung dari jumlah kegiatan atau aktivitas yang

dilakukan untuk mencapai tujuan. Simbol c1,c2,...,cn merupakan kontribusi masing-

masing variabel keputusan terhadap tujuan, disebut juga koefisien fungsi tujuan

pada model matematiknya.Simbol a11, ...,a1n,...,amn merupakan penggunaan per unit

variabel keputusan akan sumber daya yang membatasi, atau disebut juga sebagai

koefisien fungsi kendala pada model matematiknya. Simbol b1,b2,...,bm

menunjukkan jumlah masing-masing sumber daya yang ada. Jumlah fungsi kendala

akan tergantung dari banyaknya sumber daya yang terbatas.

Pertidaksamaan terakhir (x1, x2, , xn 0) menunjukkan batasan non

negatif. Membuat model matematik dari suatu permasalahan bukan hanya menuntut

kemampuan matematik tapi juga menuntut seni permodelan. Menggunakan seni

akan membuat permodelan lebih mudah dan menarik.

Suatu persoalan disebut persoalan program linier apabila memenuhi hal-hal

sebagai berikut :

1. Tujuan (objective)Apa yang menjadi tujuan permasalahan yang dihadapi yang ingin

dipecahkan dan dicari jalan keluarnya. Tujuan ini harus jelas dan tegas yang

disebut fungsi tujuan (objective function). Fungsi tujuan tersebut dapat

berupa dampak positif, manfaat-manfaat, atau dampak negatif, kerugian-

kerugian, resiko-resiko, biaya-biaya, jarak, waktu yang ingin

diminimumkan.

II-6


7/16

2. Alternatif perbandingan.

Harus ada sesuatu atau alternatif yang ingin diperbandingkan, misalnya

antara kombinasi waktu tercepat dan biaya tertinggi dengan waktu terlambat

dan biaya terendah, atau alternatif padat modal dengan padat karya,

proyeksi permintaan tinggi dengan rendah, dan seterusnya.

3. Sumber Daya

Sumber daya yang dianalisis harus berada dalam keadaan terbatas. Misalnya

keterbatasan tenaga, bahan mentah terbatas, modal terbatas, ruangan untuk

menyimpan barang terbatas, dan lain-lain. Pembatasan harus dalam

ketidaksamaan linier (linier inequality). Keterbatasan dalam sumber daya

tersebut dinamakan sebagai fungsi kendala atau syarat ikatan.

4. Perumusan Kuantitatif.

Fungsi tujuan dan kendala tersebut harus dapat dirumuskan secara

kuantitatif dalam model matematika.

5. Keterikatan Perubah.

Perubah-perubah yang membentuk fungsi tujuan dan fungsi kendala

tersebut harus memiliki hubungan keterikatan hubungan keterikatan atau

hubungan fungsional. Perumusan Model Persoalan Program Linier Pada

dasarnya secara umum, persoalan program linier dapat dirumuskan dalam

suatu model dasar/model.

Metode simpleks merupakan prosedur aljabar yang bersifat iteratif,

yang bergerak selangkah demi selangkah, dimulai dari suatu titik ekstrem

pada daerah fisibel (ruang solusi) menuju ke titik ekstrem yang optimum. Untuk

dapat lebih memahami uraian selanjutnya, berikut ini diberikan pengertian dari

beberapa terminologi dasar yang banyak digunakan dalam membicarakanmetode simpleks. Untuk itu, perhatikan kembali model programa linier berikut:

Maks. atau min : z = c1 x1 + c2 x2 +... + cn xn

berdasarkan:

a11 x1 + a12 x2 + ... + a1n xn = b1

II-7


8/16

a12 x1 + a22 x2 + ... + a2 n xn = b2

.

.

am1 x 1 + am 2 x 2 + . . . + a m n x n = bm

xi 0 (i = 1, 2, ..., n)

Jika kita definisikan: maka pembatas dari model tersebut dapat dituliskan ke

dalam bentuk sistem persamaan AX = b. Perhatikan suatu sistem AX = b dari

m persamaan linier dalam n variabel (n > m)

1. Solusi basis

Solusi basis untuk AX = b adalah solusi di mana terdapat sebanyak-

banyaknya m variabel berharga bukan nol.

Untuk mendapatkan solusi basis dari AX = b maka sebanyak (n - m)

variabel harus dinolkan. Variabel-variabel yang dinolkan ini disebut

variabel nonbasis (NBV). Selanjutnya, dapatkan harga dari n - (n - m) =

m variabel lainnya yang memenuhi AX = b, yang disebut variabel basis

(BV).

2. Solusi basis fisibel

Jika seluruh variabel pada suatu solusi basis berharga nonnegatif, maka

solusi itu disebut solusi basis fisibel (BFS).

3. Solusi fisibel titik ekstrem

Yang dimaksud dengan solusi fisibel titik ekstrem atau titik sudut ialah

solusi fisibel yang tidak terletak pada suatu segmen garis yang

menghubungkan dua solusi fisibel lainnya. Jadi, titik-titik (0,0), (0,6),

(2,6), (4,3), dan (4,0) adalah solusisolusi fisibel titik sudut atau titik-

titik ekstrem. Apabila ada sejumlah n (n < 3) buah variabel keputusan,maka definisi di atas tidak cocok lagi untuk mengidentifikasi solusi

fisibel titik sudut (titik ekstrem) sehingga pembuktiannya harus dengan

cara aljabar.

Ada tiga sifat pokok titik ekstrem ini, yaitu:

Sifat 1.a : Jika hanya ada satu solusi optimum, maka pasti ada satu titik

ekstrem.

II-8


9/16

Sifat 1.b : Jika solusi optimumnya banyak, maka paling sedikit ada dua titik

ekstrem yang berdekatan. (Dua buah titik ekstrem dikatakan

berdekatan jika segmen garis yang menghubungkan keduanya itu

terletak pada sudut dari batas daerah fisibel.)

Sifat 2 : Hanya ada sejumlah terbatas titik ekstrem pada setiap persoalan.

Sifat 3 : Jika suatu titik ekstrem memberikan harga z yang lebih baik dari

yang lainnya, maka pasti solusi itu merupakan solusi optimum.

Sifat 3 ini menjadi dasar dari metode simpleks yang prosedurnya

meliputi 3 langkah sebagai berikut:

1. Langkah inisialisasi: mulai dari suatu titik ekstrem (0,0).

2. Langkah iteratif: bergerak menuju titik ekstrem berdekatan yang lebih baik.

Langkah ini diulangi sebanyak diperlukan.

3. Aturan penghentian: memberhentikan langkah ke-2 apabila telah sampai pada

titik ekstrem yang terbaik (titik optimum).

Algoritma simpleks dimulai dari titik A (0,0) yang biasa disebut

sebagai solusi awal (starting solution). Kemudian bergerak ke titik sudut yang

berdekatan, bisa ke B atau ke E. Dalam hal ini, pemilihan (B atau E) akan

bergantung pada koefisien fungsi tujuan. Karena koefisien x2 lebih besar

daripada x1, dan fungsi tujuannya maksimasi, maka solusi akan bergerak

searah dengan peningkatan x2 hingga mencapai titik ekstrem E. Pada titik B

proses yang sama diulangi untuk menguji apakah masih ada titik ekstrem lain

yang dapat memperbaiki nilai fungsi tujuan. Karena titik ekstrem D (2,6)

memberikan nilai fungsi tujuan yang lebih baik daripada titik E (0,6) dan titik

C (4,3), maka iterasi berhenti, dengan titik D (2,6) sebagai titik optimum.

Dengan demikian, ada dua aturan yang berlaku dalam memilih titikekstrem yang berikut setelah mencapai suatu titik ekstrem tertentu, yaitu:

1. Titik ekstrem yang berikutnya ini harus merupakan titik ekstrem yang

berdekatan dengan titik ekstrim yang sudah dicapai. Sebagai contoh,

dari titik A tidak bisa bergerak langsung ke titik D atau C karena

mereka tidak berdekatan.

2. Solusi ini tidak akan pernah kembali ke titik ekstrem yang telah dicapai

II-9


10/16

sebelumnya. Misalnya dari E tidak akan kembali lagi ke A.

Sebagai ringkasan dari ide metode simpleks ini ialah bahwa metode ini

selalu dimulai pada suatu titik sudut fisibel, dan selalu bergerak melalui

titik sudut fisibel yang berdekatan, menguji masing-masing titik

mengenai optimalitasnya sebelum bergerak pada titik lainnya.

Untuk mengekspresikan ide ini dalam konteks metode simpleks,

diperlukan suatu korespondensi antara metode grafis dan metode simpleks

mengenai ruang solusi dan titik-titik sudut (titik-titik ekstrem) sebagai berikut:

Table 2.1 Korespondensi Metode Grafis Dengan Metode Simpleks

Defenisi geomatris

(metode grafis)Defenisi aljabar (metode simpleks)

Ruang solusi Pembatas-pembatas dalam bentuk standar

Titik-titik sudut/ekstrem Solusi-solusi basis dari bentuk standar

Maka, sebagai ilustrasi dari representasi ruang solusi secara aljabar ini,

kita lihat contoh bentuk standar model persoalan di bawah ini:

Maksimumkan: z = 3x1 + 5x2 + OS1 + OS2 + OS3

Berdasarkan pembatas :

x1 + S1 = 4

2x2 + S2 = 12

3x1 + 2x2 + S3 = 18

Dari uraian sebelumnya, ada dua hal yang dapat kita simpulkan, yaitu:

1. Karena bentuk standar persoalan ini memiliki 3 persamaan pembatas

dengan 5 anu, maka setiap titik ekstrem pasti memiliki sebanyak 2 (=

5-3) variabel yang berharga nol.

2. Titik-titik ekstrem yang berdekatan, berbeda hanya pada 1 variabel.

Kesimpulan pertama menunjukkan bahwa kita dapat mengidentifikasi

titik-titik ekstrem suatu ruang solusi secara aljabar, dengan cara mengenolkan

sebanyak (n - m) variabel. Banyaknya persamaan pembatas fungsional adalah

II-10


11/16

m, sedangkan banyaknya variabel (m n) adalah n.

Secara matematis, solusi yang diperoleh dari pengenolan (n - m)

variabel itu kemudian disebut sebagai solusi basis (basic solution). Jika suatu

solusi basis dapat memenuhi pembatas-pembatas nonnegatif, maka solusi ini

disebut sebagai solusi basis fisibel (feasible basic solution). Variabel-variabel

yang dinolkan disebut sebagai variabel-variabel nonbasis (non-basic

variables), dan sisanya disebut sebagai variabel-variabel basis (basic

variables). Jumlah iterasi maksimum dalam metode simpleks adalah sama

dengan jumlah maksimum solusi basis dalam bentuk standar.

Dari kesimpulan yang kedua, titik ekstrem yang berdekatannya hanya

berbeda pada satu variabel, kita dapat menetapkan titik ekstrem berikutnya

dengan mengganti variabel nonbasis (variabel yang dinolkan) yang telah

dicapai dengan variabel basis yang telah dicapai. Sebagai contoh, misalkan

bahwa kita sedang berada di titik A dan akan bergerak ke titik E. Untuk dapat

mencapai titik E ini kita naikkan harga variabel nonbasis x 2 dari nilainya

semula (yaitu 0) hingga mencapai titik E. Pada titik E, variabel S2 (yang

sebelumnya merupakan variabel basis di titik A) secara otomatis menjadi nol,

artinya menjadi variabel nonbasis. Dengan demikian, pergantian ini terjadi

antara x2 dan S2, seperti terlihat pada tabel berikut:

Tabel 2.2 Pergantian Variabel Basis dan Nonbasis

Titik ekstrem Variabel nonbasis Variabel basis

A

B

x1 , x2

X1 , S2

S1, S2 , S3

S1, x2 , S3

2.2 Algoritma Simpleks Untuk Persoalan Maksimasi

Untuk menyelesaikan persoalan programa linier dengan menggunakan

metode simpleks, lakukanlah langkah-langkah berikut:

1. Konversikan formulasi persoalan ke dalam bentuk standar.

2. Cari solusi basis fisibel (BFS).

3. Jika seluruh NBV mempunyai koefisien non-negatif (artinya berharga

positif atau nol) pada baris fungsi tujuan (baris persamaan z yang biasa

II-11


12/16

juga disebut baris 0), maka BFS sudah optimal. Jika pada baris 0 masih

ada variabel dengan koefisien negatif, pilihlah salah satu variabel yang

mempunyai koefisien paling negatif pada baris 0 itu. Variabel ini akan

memasuki status variabel basis, karena itu variabel ini disebut sebagai

variabel yang masuk basis (entering variable, disingkat EV).

4. Hitung rasio dari (Ruas kanan) / (Koefisien EV) pada setiap baris

pembatas di mana EV-nya mempunyai koefisien positif. Variabel basis

pada baris pembatas dengan rasio positif terkecil akan berubah status

menjadi variabel nonbasis. Variabel ini kemudian disebut sebagai

variabel yang meninggalkan basis atau leaving variable, disingkat LV.

Lakukan operasi baris elementer (ERO) untuk membuat koefisien EV

pada baris dengan rasio positif terkecil ini menjadi berharga 1 clan

berharga 0 pada baris-baris lainnya.

Kembali ke langkah 3.

Catatan : Jika ditemukan lebih dari satu baris yang mempunyai rasio

positif terkecil, pilihlah salah satu. Caia ini tidak akan mempengaruhi basil

perhitungan akhir.

2.2.1Algoritma Simpleks Untuk Persoalan Minimasi

Untuk menyelesaikan persoalan LP dengan fungsi tujuan me-

minimumkan z, ada dua cara yang dapat dilakukan, yaitu:

1. Mengubah fungsi tujuan dan persamaannya, kemudian menyelesaikannya

sebagai persoalan maksimasi.

2. Memodifikasi langkah 3 sehingga menjadi:

Jika seluruh NBV pada baris 0 mempunyai koefisien yang berharganonpositif (artinya berharga negatif atau nol), maka BFS sudah optimal.

Jika pada baris 0 masih ada variabel dengan koefisien positif, pilihlah

salah satu variabel yang berharga paling positif pada baris 0 itu, untuk

menjadi EV.

2.2.2 Kasus Khusus dalam Penggunaan Algoritma Simpleks

II-12


13/16

1. Degenerasi

Kasus ini terjadi apabila satu atau lebih variabel basis berharga nol (b

= 0) sehingga iterasi yang dilakukan selanjutnya bisa menjadi suatu

loop yang akan kembali pada bentuk sebelumnya. Kejadian ini disebut

cyclingatau circling.

2. Solusi optimum banyak

Suatu persoalan dapat memiliki lebih dari satu solusi optimum. Kasus

ini terjadi apabila fungsi tujuan paralel dengan fungsi pembatas, di

mana paling sedikit salah satu dari variabel nonbasis (pada persamaan z

pada iterasi terakhir) mempunyai koefisien berharga nol. Akibatnya,

walaupun variabel tersebut dinaikkan harganya (dijadikan variabel

basis), harga z tetap tidak berubah. Karena itu, solusi-solusi optimum

yang lain ini biasanya dapat diidentifikasi dengan cara menunjukkan

iterasi-iterasi tambahan pada metode simpleksnya, di mana variabel-

variabel nonbasis yang berkoefisien nol itu selalu dipilih untuk menjadi

entering variable.

3. Solusi tak terbatas

Kasus ini terjadi apabila ruang solusi tidak terbatas sehingga nilai

fungsi tujuan dapat meningkat (untuk maksimasi) atau menurun (untuk

minimasi) secara tidak terbatas. Apabila persoalannya dapat

diselesaikan secara grafis (berdimensi dua), maka kasus ini akan mudah

terdeteksi. Akan tetapi, jika persoalan yang dihadapi berdimensi tiga

atau lebih, maka untuk mendeteksi apakah solusinya terbatas atau tidak,

dilakukan dengan cara:

a. Perhatikan koefisien-koefisien pembatas dari variabel nonbasis padasuatu iterasi. Jika koefisien-koefisien tersebut berharga negatif atau nol,

berarti solusinya tak terbatas.

b. Jika koefisien fungsi tujuan variabel tersebut berharga negatif (untuk

maksimasi) atau positif (untuk minimasi), maka nilai fungsi tujuannya

tidak terbatas

II-13


14/16

2.3 Analisis Sensitivitas

Seorang analis jarang dapat menentukan parameter model Program Linier

seperti (m, n, Cj, aij, bi) dengan pasti karena nilai parameter ini adalah fungsi dari

beberapa uncontrolable variable. Sementara itu solusi optimal model Program

Linier didasarkan pada parameter tersebut. Akibatnya analis perlu mengamati

pengaruh perubahan parameter tersebut terhadap solusi optimal. Analisa perubahan

parameter dan pengaruhnya terhadap solusi Program Linier disebutPost Optimality

Analisis. Istilah post optimality menunjukkan bahwa analisa ini terjadi setelah

diperoleh solusi optimal, dengan mengasumsikan seperangkat nilai parameter yang

digunakan dalam model. Atau Analisis Postoptimal (disebut juga analisis pasca

optimal atau analisis setelah optimal, atau analisis kepekaan dalam suasana

ketidaktahuan) merupakan suatu usaha untuk mempelajari nilai-nilai dari peubah-

peubah pengambilan keputusan dalam suatu model matematika jika satu atau

beberapa atau semua parameter model tersebut berubah atau menjelaskan pengaruh

perubahan data terhadap penyelesaian optimal yang sudah ada.

Dapat diketahui bahwa dunia nyata yang diabstraksikan dan

disimplifikasikan ke dalam model PL, tidak sederhana seperti rumusan PL

sederhana tersebut. Oleh karena itu dalam dunia pengelolaan dan kehidupan dunia

nyata, selalu dihadapkan pada pertanyaanpertanyaan keragu-raguaan seperti apa

yang akan terjadi, jika ini dan itu berubah?

Persoalan peluang dan ketidakpastiaan pertanyaan-pertanyaan tersebut harus

dapat dijawab dalam rangka meyakinkan pendirian terhadap sesuatu yang akan

diputuskan kelak. Dengan demikian hasil yang diharapkan tersebut adalah hasil

yang memang paling mungkin dan paling mendekati, atau perkiraan yang

paling tepat. Uji kepekaan hasil dan pasca optimal (sebut saja selanjutnya analisispostoptimal) yang dapat memberikan jawaban terhadap persoalan-persoalan

tersebut diatas. Analisis postoptimal sangat berhubungan erat dengan atau

mendekati apa yang disebut Program Parametrikal atau AnalisisParametrisasi.

Perubahan atau variasi dalam suatu persoalan Program Linier yang biasanya

dipelajari melalui Post Optimality analysis dapat dipisahkan ke dalam tiga

kelompok umum, yaitu :

II-14


15/16

1. Analisa yang berkaitan dengan perubahan diskrit parameter untuk melihat

berapa besar perubahan dapat ditolerir sebelum solusi optimal mulai

kehilangan optimalitasnya, ini dinamakan Analisa Sensitivitas. Jika suatu

perubahan kecil dalam parameter menyebabkan perubahan drastis dalam

solusi, dikatakan bahwa solusi adalah sangat sensitif terhadap nilai

parameter itu. Sebaliknya, jika perubahan parameter tidak mempunyai

pengaruh besar terhadap solusi dikatakan solusi relatif insensitif terhadap

nilai parameter tersebut.

2. Analisa yang berkaitan dengan perubahan struktural. Masalah ini muncul

bila persoalan Program Linier dirumuskan kembali dengan menambahkan

atau menghilangkan kendala dan atau variabel untuk menunjukkan operasi

model alternatif. Perubahan struktural ini dapat dimasukkan dalam analisa

sensitivitas.

3. Analisa yang berkaitan dengan perubahan kontinu parameter untuk

menentukan urutan solusi dasar yang menjadi optimal jika perubahan

ditambah lebih jauh, ini dinamakan Parametric-Programming. Diketahui

Model Matematika Persoalan Program Linier adalah sebagai berikut:

Menentukan nilai dari X1, X2, X3, ....., Xn sedemikian rupa sehingga :

Z = C1 X1 + C2 X2 + .... +Cj Xj +....+Cn Xn

= =

n

j 1

Cj Xj (Optimal[maksimum/minimum])

Yang kemudian disebut sebagai Fungsi Tujuan (Objective Function) dengan

pembatasan (Funsi Kendala / Syarat Ikatan) :

a11 X1 + a12 X2 +.....+a1n Xn atau b1 , P

a21 X1 + a22 X2 +.....+a2n Xn atau b2,

am1 X1 + am2 X2 +....+ amn Xn atau bm,

atau =

n

j 1

aij Xj atau bi untuk i = 1,2,3, , m.

II-15


16/16

dan X10, X2 0,...,Xn 0 atau Xj 0, dimana j = 1, 2, 3,...., n (syarat

non-negatif).

Berdasarkan Model Matematika Persoalan Program Linier di atas analisis

sensitivitas dapat dikelompokkan berdasarkan perubahan-perubahan parameter:

1. Perubahan koefisien fungsi tujuan (Cj),

2. Perubahan Koefisien teknologi (aij) (koefisien input-output),

3. Perubahan Nilai-Sebelah-Kanan (NSK) fungsi kendala) (bi),

4. Adanya tambahan fungsi kendala baru (perubahan nilai m)

5. Adanya tambahan perubahan (variabel) pengambilan keputusan (Xj)

(perubahan nilai n).

II 16

operational research bab ii

Documents