BAB II LANDASAN TEORI

BAB II

LANDASAN TEORI

Persoalan utama yang dihadapi oleh seorang manajer atau pengambil keputusan adalah bagaimana mengalokasikan suatu sumber yang terbatas diantara berbagai aktivitas atau proyek.

Program linear adalah suatu metode yang dapat digunakan dalam menentukan alokasi sumber dengan cara yang optimal. Metode ini adalah suatu alat yang digunakan secara luas dalam penelitian operasi dan telah banyak membantu dalam membuat keputusan pada sebagian besar industri manufaktur dan dalam bidang finansial atau organisasi pelayanan.

Dalam istilah program linear, kata program berarti program matematis. Dalam konteks ini artinya proses perencanaan yang mengalokasikan sumber; tenaga kerja, materi, mesin atau modal dengan kemungkinan cara yang terbaik (optimal) sehingga biaya diminimumkan atau keuntungan dimaksimumkan. Dalam program linear sumber ini dikenal sebagai variabel keputusan. Kriteria dalam memilih nilai terbaik dari variabel keputusan (seperti maksimumkan keuntungan atau minimumkan biaya) dikenal sebagai himpunan konstrain.

Kata linear menunjukkan bahwa kriteria dalam memilih nilai terbaik pada variabel keputusan dapat digambarkan oleh fungsi linear dari variabel-variabel ini; yakni fungsi aljabarnya hanya mengandung pangkat pertama variabel dengan tidak ada hasil perkalian. Sebagai contoh; 23x1 dan 4x2 merupakan variabel keputusan yang benar. Sedangkan 23 x12 , 4 x22 dan (4 x1.2 x2 ) tidak benar. Semua persoalan dapat dinyatakan dalam bentuk garis lurus, bidang atau bentuk geometris lain yang sejenis.

Universitas Sumatera Utara

6

Sebagai tambahan untuk syarat linear, ditetapkan batasan non-negatif yang berarti variabel tidak boleh berharga negatif. Sehingga tidak mungkin diperoleh sumber yang negatif.

2.1.

Persoalan Transportasi

Persoalan tranportasi merupakan suatu persoalan yang membahas masalah pendistribusian suatu komoditi atau produk dari sejumlah sumber (supply) ke sejumlah tujuan (demand) dengan tujuan meminimumkan ongkos pengangkutan yang terjadi. Suatu persoalan transportasi memiliki model sebagai berikut.

2.2.

Model Persoalan Transportasi

Persoalan umum transportasi dapat dinyatakan dalam representasi jaringan berikut:

S1

S2

Sm

1

(Cij, Xij)

1

2

2

.

.

.

.

.

.

m

D1

D2

Dn

n

Gambar Representasi Jaringan Model Persoalan Transportasi

2.2.1. Definisi Model Tsransportasi

Berdasarkan gambar diketahui bahwa terdapat m sumber dan n tujuan, masing-masing dinyatakan oleh sebuah node. Node-node tersebut dihubungkan oleh garis atau panah. Panah (i,j) yang menghubungkan sumber i ke tujuan j membawa 2 jenis informasi: biaya transportasi Cij, dan jumlah yang diangkut Xij. Jumlah supply pada sumber i adalah Si dan jumlah demand pada tujuan j adalah Dj. Tujuan dari model tersebut


7

adalah untuk menentukan Xij yang belum diketahui yang akan meminimumkan total biaya transportasi Cij dan memenuhi semua batasan supply dan demand.

2.2.2. Model Matematika

Andaikan terdapat m pusat sumber/supply dan n pusat tujuan/demand. Suatu produk x akan diangkut dari sumber i ke tujuan j (i = 1, 2, …, m dan j = 1, 2, …, n) dengan ongkos angkut per unit sebesar Cij, maka jumlah produk sebesar Xij dikirimkan dari pusat sumber Si ke pusat tujuan Dj, sehingga model matematika persolan transportasi adalah sebagai berikut:

Fungsi tujuan m

n

∑∑ c x

Min Z =

=i 1 =j 1

(1)

ij ij

Dengan kendala: m

= ∑ xij i =1 n

= xij ∑ j =1 m

= Si , j 1, 2,..., n = D j , i 1, 2,..., m

(2)

n

∑S = ∑D

i =i 1 =j 1

j

xij ≥ 0

di mana: Xij adalah peubah pengambil keputusan, dalam hal ini jumlah produk yang diangkut dari titik sumber i ke titik tujuan j Si adalah jumlah yang disediakan untuk diangkut (supply/sumber) dari titik sumber i Dj adalah jumlah yang diminta untuk didatangkan (demand/kebutuhan) di titik tujuan j Cij adalah ongkos pengangkutan per unit produk xij yang bersangkutan m adalah jumlah pusat sumber n adalah jumlah pusat permintaan/tujuan. Dalam keadaan di mana jumlah sumber tidak sama dengan jumlah permintaan maka diperoleh model khusus persoalan sebagai berikut:


8

Fungsi tujuan

Min Z =

m

n

∑∑ c x

=i 1 =j 1

ij ij

Dengan kendala: m

∑x i =1 n

∑x j =1

≤ Si , j = 1, 2,..., n

ij

ij

≥ Dj ,i = 1, 2,..., m

(3)

xij ≥ 0 Persoalan transportasi juga dapat dinyatakan dalam bentuk matriks:

Fungsi tujuan : m

n

Min ∑∑ Cij X ij

(4)

=i 1 =j 1

Dengan batasan:

Ax ≤ b

(5)

x ≥0 di mana : = b (S1 , S 2 , ..., S m , − D1 , − D2 , ..., − Dn )T adalah vektor ruas kanan pembatas

Α = matriks koefisien persoalan transportasi

Berdasarkan P. Siagian, untuk m persamaan kendala sumber dan n persamaan kendala tujuan maka total kendala sebanyak (m+n) sistem kendala, tetapi hanya (m+n1) persamaan yang bebas, sedang satu lagi (boleh yang mana saja) merupakan persamaan yang dapat dinyatakan sebagai kombinasi linear dari persamaan lainnya, atau dengan kata lain salah satu kendala merupakan kendala yang berlebih. Ini dapat dilihat dari sifat keseimbangan persoalan transportasi, yaitu :

m

∑

Si =

n

∑D

=i 1 =j 1

j

sehingga : m

n

∑∑

=i 1 =j 1

X ij =

m

n

∑∑

=i 1 =j 1

X ij

(6)


9

atau :  n −1  m n + X X X ij ∑  ∑ ij in  = ∑∑ =i 1 =j 1 = 1 = 1 i j  m

(7)

akhirnya : m

= ∑ X in =i 1

m

n

m n −1

∑∑ X ij − ∑∑ X ij

=i 1 =j 1

(8)

=i 1 =j 1

Dari hasil diatas ditunjukkkan bahwa persamaaan pada ruas kiri yaitu persamaan ke-n dapat dinyatakan sebagai kombinasi dari persamaan pada ruas kanan, atau dengan kata lain sesungguhnya persamaan ke-n sudah terpenuhi berdasarkan persamaan pada ruas kanan. Karena itu persamaan ke-n dapat disingkirkan dari sistem, sehingga hanya ada (m+n-1) persamaan yang benar-benar bebas artinya berbeda satu dengan yang lain.

Menurut teori program linear, jika sistem kendala terdiri dari (m+n-1) persamaan bebas dengan mn variabel, maka variabel basis yaitu variabel yang tidak berharga nol xij ≠ 0 , terdiri dari (m+n-1) variabel dan variabel nonbasis ada sebanyak mn – (m+n-1) = (m-1)(n-1) buah yaitu untuk xij = 0. Karena itu jawab layak basis yang terdiri dari variabel ≠ 0 , tidak lebih dari (m+n-1) variabel, diantaranya tentu terdapat satu jawab layak basis optimal.

Sebagai ilustrasi, jika terdapat dua daerah sumber A1 dan A2 dan tiga daerah tujuan, T1, T2 dan T3. Masing-masing sumber memiliki kapasitas 50 dan 70 satuan. Sedangkan daerah tujuan masing-masing memiliki kebutuhan sebanyak 40, 60 dan 20 satuan. Maka jika daerah sumber A1 telah mengirimkan sebanyak 50 satuan dan sumber A2 telah mengirimkan sebanyak 70 satuan, dan juga jika daerah tujuan T1 dan T2 masing-masing telah menerima 40 dan 60 satuan, maka daerah tujuan T3 dengan sendirinya harus menerima sisanya yaitu 20 satuan. Karena itu daerah tujuan T3 adalah kendala yang berlebihan. Jadi, hanya ada empat persamaan bebas yaitu persamaan A1, A2, T1 dan T2, karena itu hanya ada empat variabel basis.


10

2.3 Total Unimodularitas dari Matriks Transportasi

Suatu matriks transportasi dapat dinyatakan dalam bentuk sebagai berikut : 1 0    0  Α =  0 1  0   0

0 0    0 0 0 0 1 1  1 0 0 0 0 0    0 0 0 0 0 0 0 0 0 1 1  1 0 0 0 0 1 0 0 0 0 1 0 0 0  1 0 0 0 0 1 0 0 0 0 1 0 0        0 0 1 0 0 0 0 1 0 0 0 0 1 

1  1 0 0 0 0 0 0 0 1 1  1 0

0

0 0

0 0 1

0 0 0 0 0 1 0 0 0 

0

0

1 0

0 0 0 0 0 0 

0 0

0 0

0 0

0 0 0 0

0 0

Kendala sumber

(9)

Kendala tujuan

Matriks Koefisien PersoalanTransportasi

Satu sifat yang paling penting yang dimiiki oleh matriks transportasi adalah sifat total unimodular. Matriks Α adalah total unimodular jika determinan dari setiap submatriks bujursangkar yang dibentuk dari matriks Α memiliki nilai -1, 0 atau 1.

Dalam kasus matriks transportasi, karena semua entrinya 1 atau 0 maka setiap submatriks berukuran 1x1 memiliki determinan bernilai 1 atau 0. Selanjutnya, submatriks yang berukuran (m + n) x(m + n) memiliki determinan bernilai 0 karena

rank ( Α ) =

m + n − 1 . Terakhir akan

ditunjukkan bahwa

suatu submatriks

kxk (1 < k < m) juga memunuhi sifat ini. Andaikan Α k

adalah suatu submatriks berukuran

kxk

dari

Α . Harus

ditunjukkan bahwa det( Α k ) = ± 1 atau 0. Dengan induksi pada k , andaikan bahwa sifat benar untuk Α k −1 (jelas sifat ini benar untuk Α1 ). Ingat kembali bahwa setiap kolom dari Α k mungkin tidak memiliki entri 1, memiliki sebuah entri 1 atau memiliki dua entri 1. 1. Jika suatu kolom Α k tidak memiliki entri 1 maka det ( Α k ) = 0


11

2. Jika, dalam kasus lain, suatu kolom dari Α k memiliki dua entri 1, maka satu dari entri 1 akan muncul pada baris sumber dan entri 1 lainnya akan muncul pada baris tujuan. Dalam kasus ini jumlah dari baris sumber dari Α k sama dengan jumlah dari baris tujuan dari Α k . Sehingga baris dari Α k adalah bergantung linier dan det ( Α k ) = 0 . 3. Terakhir, jika suatu kolom dari Α k memiliki sebuah entri 1 maka ekspansi det( Α k ) dengan minor dari kolomnya, diperoleh : det( Α k ) = ± det( Α k −1 ) di mana Α k −1 adalah submatriks berukuran (k − 1) x(k − 1) . Tetapi oleh hipotesis induksi, det( Α k −1 ) = ± 1 atau 0. Sehingga sifat ini benar untuk Α k dan hasil ditunjukkan.

2.4 Karakteristik Persoalan Transportasi

Seperti telah dijelaskan sebelumnya, persoalan transportasi merupakan tipe khusus dari persoalan program linear. Dikatakan demikian karena persoalan transportasi memiliki beberapa karakter atau sifat yang membedakannya dengan persoalan program linear lainnya, diantaranya :

2.4.1. Persoalan transportasi cenderung memiliki variabel dan konstrain yang cukup banyak. Hal ini dapat dimaklumi karena kegiatan dari persoalan transportasi yang mengalokasikan suatu komoditi dari sejumlah sumber dengan kapasitas yang berbeda-beda dan masing-masing sumber ke sejumlah tujuan yang membutuhkan komoditi itu dengan tingkat kebutuhan yang berbeda-beda pula. Karena itu penyelesaian persoalan tranportasi dengan menggunakan metode penyelesaian program linear biasa, seperti simpleks, menjadi tidak efektif digunakan karena penggunaan metode simpleks memerlukan penambahan variabel

surplus/slack dan

variabel artificial

yang

akan

menambah

penghitungan dalam penyelesaiannya.


12

2.4.2. Adanya hubungan keseimbangan. Dalam persolan transportasi umumnya diasumsikan bahwa total sumber harus sama dengan total tujuan. Namun dalam persoalan nyata hal ini tentunya tidak selamanya bisa terpenuhi, akan tetapi persoalan tersebut dapat dijadikan seimbang dengan menambah sumber dummy atau tujuan dummy. Bila total sumber a lebih besar dari total tujuan b maka tambahkan variabel dummy pada tujuan sebesar selisih dari total sumber dan total tujuan, yaitu sebesar (a – b). Sebaliknya, bila total tujuan b lebih besar dari total sumber a, maka tambahkan variabel dummy pada sumber sebesar selisih dari total tujuan b dan total sumber a, yakni sebesar (b – a). Dan perlu diingat bahwa sesungguhnya tidak ada terjadi pengalokasian ke sumber atau tujuan dummy ini, sehingga biaya yang ditimbulkan juga tidak ada, atau cij adalah bernilai 0.

2.5 Solusi Persoalan Transportasi

Sebelum menguraikan metode penyelesaian, diberikan

beberapa definisi sebagai

referensi persoalan transportasi : Solusi fisibel, merupakan himpunan alokasi non-negatif X ij ≥ 0 yang

memenuhi

kendala baris dan kolom. Solusi fisibel awal, merupakan sebuah solusi fisibel dengan jumlah alokasi positifnya adalah (m+n-1) untuk suatu persoalan dengan m sumber dan n

tujuan.

Solusi optimal, adalah sebuah solusi yang meminimumkan biaya alokasi.

Seperti dalam metode simpleks, model-model transportasi juga diselesaiakan dengan menggunakan sebuah tabel. Andaikan terdapat m daerah sumber; serta n daerah tujuan; dengan biaya transportasi dari sumber i ke tujuan j adalah Cij (i = 1, 2, …, m dan j = 1, 2, …, n) dan jumlah yang diangkut dari sumber i ke tujuan j adalah xij (i = 1, 2, …, m dan j = 1, 2, …, n). Maka bila disusun ke dalam sebuah bentuk tabel tranportasi diperoleh:


13

Tabel 2.1 Tabel Persoalan Transportasi Ke Dari

Tujuan 1

2

…

j

…

C21 X21

. . . . .

. . .

. . .

Ci1

Ci2

Cij

2

C1n X1n C2n X2n

S1 S2

m u

Cm

1

Xm2 D2

S1 . . .

. . .

Xm1 D1

Cm

Cm2

Cm1

Cin

. . .

Demand

. . .

. . . m

. . .

i

S

b

r

C22 X22

e

C11

. . .

C12

. . .

C11 X11 C21 X21

1

Supply

n

Sm

n

Xm1 Dj

Xmn Dn

ΣSi=ΣDj

2.5.1. Tahapan Penyelesaian Persoalan Transportasi

2.5.1.1. Tahap penentuan solusi basis awal Ada 3 metode yang umum digunakan dalam penetuan solusi basis awal, yakni : 1. Metode Pojok Barat-Laut, metode ini bekerja cenderung lebih mudah dibanding metode lainnya, akan tetapi metode ini memiliki kelemahan karena lebih menitikberatkan pada proses jadi nilai menjadi terabaikan, sehingga metode ini tidak memberikan solusi yang optimum. 2. Metode biaya sel minimum, metode ini bekerja dengan mengalokasikan sumber pada sel-sel yang memiliki biaya terkecil terlebih dahulu. Dibandingkan dengan metode Northwest Corner, metode minimum cost biasanya lebih unggul dalam pencapaian nilai optimal. Secara logika hal ini dapat diterima karena metode Northwest

Corner

tidak

memperhitungkan

biaya

sama

sekali

dalam

pengalokasiannya, sedangkan metode minimum cost memperhitungkan biaya. 3. Metode Pendekatan vogel, metode ini biasanya memberikan hasil yang lebih baik dibanding metode northwest corner dan minimum cost. Namun penyelesaian dengan metode ini juga cenderung lebih kompleks.

2.5.1.2. Tahap uji optimalitas Tahap

uji optimalitas

mancakup

penetuan

entering

variable dan leaving

variable. Tahap uji optimalitas merupakan tahap berikutnya dari teknik pemecahan


14

persoalan transportasi untuk mengetahui apakah solusi yang diperoleh sudah optimal atau belum. Ada 2 metode yang dapat digunakan dalam uji optimalitas ini, yaitu metode Batu Loncatan dan metode Distribusi yang dimodifikasi (MODI). Metodemetode diatas merupakan metode yang umum digunakan untuk menyelesaikan persoalan transportasi. Namun pada tulisan ini seperti telah dijelaskan di muka akan digunakan algoritma Arsham-Khan untuk menyelesaikan persoalan transportasi.

2.5.2. Algoritma Arsham-Kahn

Ada beberapa keunggulan algoritma ini, yaitu : 1. Tidak ada variabel artificial (seperti dalam simpleks) atau penambahan variabel slack/surplus (seperti dalam dual simpleks) 2. Semua analisis postoptimal tersedia 3. Terlihat lebih cepat dari metode program linear lainnya 4. Kesederhanaannya: hanya menggunakan Gauss Jourdan Pivotting.

Sebelum menguraikan langkah-langkah penyelesaian dengan algoritma ini, terlebih dahulu diperkenalkan notasi-notasi yang akan dipergunakan. PT

: persoalan transportasi

PL

: program linear

SS

: stepping-stone

GJP : Gauss-Jourdan Pivotting VB : variabel basis HVB : himpunan variabel basis FE

: fisibelitas

BP

: baris pivot (baris yang ditentukan untuk variabel masuk)

KP

: kolom pivot (kolom yang berhubungan dengan variabel masuk)

EP

: elemen pivot

BT : baris terbuka (sebuah baris yang belum diisi variabel basis ; diberi label [?] [?] : label untuk baris yang belum diisi variabel basis (baris terbuka) NSK : nilai sebelah kanan K/B : rasio kolom, yakni NSK/KP


15

Algoritma ini dimulai dengan inisialisasi persiapan dan diikuti oleh dua tahapan. Tahap pertama merupakan iterasi VB untuk membangun HVB yang mungkin fisibel atau tidak. Tahap kedua merupakan iterasi FE untuk membangun solusi yang fisibel dan optimum. Kedua tahapan ini menggunakan transformasi GJP. Akan tetapi berbeda dalam metode memilih EP. Iterasi VB menggunakan kriteria simpleks, yang dimodifikasi hanya untuk memilih baris terbuka yang belum diisi VB. Strategi ini membawa

kepada

tercapainya

titik

optimal,

dan

terkadang

menyebabkan

ketidakfisibelan. Iterasi FE, jika dibutuhkan, membawa kembali solusi kepada fisibelitas dengan menggunakan kriteria dual simpleks untuk memilih EP.

Jelas, dalam suatu persoalan transportasi yang setimbang, satu dari (m+n) konstrain adalah berlebih. Dari pada mengeliminasi konstrain secara sebarang, maka pada algoritma ini dieliminasi konstrain yang akan lebih banyak memberikan pengurangan jumlah iterasi pada tahap pertama.

Adapun dalam tahapan-tahapan ini masing-masing dapat dikelompokkan berdasarkan operasi yang menambah keefisienan dalam pengerjaannya. Langkah 0.1 dan 0.2 mengeliminasi konstrain yang akan lebih banyak mengurangi jumlah iterasi. Kelompok kedua terdiri dari tiga operasi: 1.2c, 2.2a dan 2.2d, yang bersama-sama secara progresif mengurangi ukuran tabel.

Iterasi 0 (Persiapan) 0.0 – Formulasi matriks-biaya PT 0.1 – Reduksi baris-kolom (atau reduksi kolom-baris) Dari setiap baris kurangkan terhadap biaya terkecil. Akumulasi pengaruh dari setiap reduksi baris menjadi biaya awal. Demikian, dari setiap kolom kurangkan terhadap biaya terkecil. Akumulasi pengaruh dari setiap reduksi kolom menjadi biaya awal. 0.2 – Eliminasi konstrain berlebih Periksa baris atau kolom yang memiliki nilai nol terbanyak Eliminasi konstrain tersebut. 0.3 – Bentuk tabel simpleks


16

Gunakan sebuah baris untuk setiap konstrain dan sebuah kolom

untuk

setiap

variabel. Jangan menambahkan variabel artificial 0.4 – Tentukan HVB Untuk setiap kolom yang merupakan vektor satuan, beri label baris dengan nama variabel pada kolom tersebut. Beri label baris yang lain dengan tanda tanya (?). 0.5 – Hapus kolom VB.

Iterasi 1 (Tahap VB) 1.0 – Uji terminasi iterasi HVB Jika terdapat label (?) atau terdapat baris terbuka, maka lanjutkan iterasi VB. Jika tidak HVB telah lengkap; mulai tahap FE (langkah 2.0). 1.1 – Pilih VB dari EP KP : Pilih nilai Cij terkecil dan tetapkan sebagai bakal kolom. BP : Pilih baris terbuka sebagai bakal baris. EP : Pilih bakal baris dan kolom dengan K/B non-negatif terkecil. Jika tidak ada K/B non-negatif, pilih K/B yang bernilai absolut terkecil. Jika elemen pivotnya bernilai nol, maka pilih Cij terbaik selanjutnya. 1.2 – Penambahan HVB (a) Lakukan GJP. (b) Ubah label baris (?) dengan nama variabel. (c) Pindahkan KP dari tabel. Lanjutkan iterasi HVB (kembali ke 1.0)

Iterasi 2 (Tahap FE) 2.0 – Uji terminasi iterasi FE Jika NSK non-negatif, maka tabel sudah optimal. Interpretasikan hasilnya. Jika terdapat NSK negatif maka lanjutkan iterasi FE (langkah 2.1). 2.1 – Pilih FE dari EP BP : Baris dengan NSK paling negatif . KP : Kolom dengan sebuah elemen negatif pada BP. Pilih kolom dengan Cij terkecil.


17

2.2 – Transformasi FE (a) Simpan KP di luar tabel. (b) Lakukan PGJ biasa. (c) Tukarkan label KP dan BP. (d) Ganti KP baru dengan KP lama yang disimpan dalam (a). Lanjutkan iterasi FE (kembali ke 2.0)

Bagian Akhir Algoritma Tahap pertama dari algoritma ini dapat digolongkan sebagai pencarian himpunan variabel basis yang menuju kepada titik optimal. Tahap kedua, jika diperlukan, membawa kembali kepada fisibelitas. Pada kedua tahapan tersebut digunakan GaussJourdan pivoting. Namun, kriteria pemilihannya berbeda untuk tiap tahap. Tahap pertama menggunakan kriteria simplek biasa, dibatasi hanya memilih baris terbuka. Jika diperlukan, fisibelitas ditiadakan. Tahap kedua menggunakan kriteria dual simpleks biasa, dan memastikan penghentian algoritma.

Garis Besar Pembuktian Algoritma Dasar teori dari algoritma ini secara luas terletak pada sifat unimodular dari matriks koefisien dalam tabel simpleks persoalan transportasi; yaitu nilai-nilai koefisiennya adalah 0, -1 atau 1. Dengan menggunakan ketentuan bahwa matriks unimodular tetap unimodular setelah dilakukan Gauss-jourdan pivoting. Berdasarkan formulasi program linear, optimalitas diperoleh ketika semua Cij non-negatif dan algoritma berakhir.

Algoritma ini dimulai dengan semua Cij non-negatif. Terlihat bahwa, dengan menggunakan operasi yang diberikan untuk memperoleh solusi basis dan fisibel, Cij tetap non-negatif. Langkah 0.1 : jelas, dengan reduksi baris-kolom ( kolom-baris) matriks biaya, sifat non-negatif dari Cij ini tetap terjaga. Langkah 0.2

: jumlah variabel basis terbaca yang ada sama dengan jumlah Cij = 0 pada baris (kolom) yang berhubungan dengan kendala yang terpilih untuk dieliminasi sebagai kendala berlebih.


18

Langkah 0.5 : menghapus kolom basis, diijinkan jika variabel tersebut ditambahkan menjadi sebuah

basis, bukan mengganti variabel. (Hal ini

mengurangi kompleksitas secara signifikan, dan tabel yang dihasilkan lebih kecil dari ukurannya). Langkah 1.1 : kriteria pemilihan. Dengan memilih Cij terkecil menjamin bahwa himpunan Cij tetap non-negatif setelah pivoting. Jika pivoting tidak memungkinkan (tidak terdapat C/R yang berhingga/finite), pilih Cij terkecil selanjutnya. Akan tetapi, nilai dari Cij terkecil tidak berubah karena elemen baris pivot pada kolom tersebut adalah nol. Langkah 2.1 : jika ada sebuah NSK < 0, maka terdapat paling sedikit satu elemen bernilai -1 pada baris itu. Jika ini tidak terjadi, maka konstrainnya tidak konsisten atau berlebih, yang tidak mungkin terjadi pada formulasi program linear persoalan transportasi.

2.5.3 Eliminasi Gauss-Jourdan

Dalam aljabar linear, eliminasi Gauss-Jordan adalah versi dari eliminasi Gauss. Pada metode eliminasi Gauus-Jordan elemen-elemen di bawah maupun di atas diagonal utama suatu matriks dijadikan nol. Hasilnya adalah matriks tereduksi yang berupa matriks diagonal satuan (Semua elemen pada diagonal utama bernilai 1, elemenelemen lainnya nol).

Jika eliminasi Gauss-Jordan diterapkan dalam matriks persegi, metode tersebut dapat digunakan untuk menghitung invers dari matriks. Eliminasi Gauss-Jourdan hanya

dapat

dilakukan

dengan

menambahkan

matriks

identitas

dengan

dimensi yang sama dari suatu matriks persegi A, dan melalui operasioperasi matriks:

[ AI ]

⇒  IA−1 

Sehingga pada hasil akhir akan diperoleh invers dari matriks A tersebut.


19

2.5.4 Penghitungan Matriks Invers Basis Β −1

Seperti telah dijelaskan sebelumnya bahwa dalam solusi persoalan transportasi yang diperoleh dari algoritma Arsham-Kahn tidak akan diperoleh matriks basis invers Β −1 , yang diperlukan untuk analisis postoptimal. Hal ini terjadi karena dalam metode penyelesaian ini tidak ada penambahan variabel artifisial.

Namun, nilai ini dapat diperoleh dengan memformulasikan bentuk parametrik NSK pada persoalan transportasi dan menyelesaikannya dengan algoritma ini sehingga diperoleh informasi tersebut dengan sedikit tambahan penghitungan.

Andaikan terdapat persoalan transportasi berikut, Persoalan Z1 m

n

Minimumkan Z1 = ∑∑ Cij X ij ,

(10)

=i 1 =j 1

Dengan batasan supply, m

∑X i =1

ij

= Si

untuk j = 1, 2, …, n

(11)

= Dj

untuk i = 1, 2, …, m

(12)

dan batasan demand, n

∑X j =1

ij

X ij , D j , Si ≥ 0

Tanpa menghilangkan bentuk umumnya, diberikan batasan yakni persolan transportasi seimbang, yakni : m

∑S

=

n

∑D ,

i =i 1 =j 1

j

sehingga salah satu dari m+n batasan merupakan batasan yang berlebih dan dapat ditiadakan. Bentuk parametrik dari Z1 menjadi : Persolaan Z2

Minimumkan = Z2

m

n

∑∑ (C

=i 1 =j 1

ij

+ Cij' ) X ij

(13)


20 20

Dengan batasan, m

∑X =

Si + ∆Si

ij

i =1 n

∑ X=

(14)

D j + ∆D j untuk i = 1, 2, …, m

ij

j =1

untuk j = 1, 2, …, n

(15)

Di mana parameter NSK, ∆Si dan ∆D j dan nilai parameter biaya Cij' merupakan data yang belum pasti nilainya. Jelas, persoalan tersebut akan tetap seimbang jika memenuhi: m

∑ ∆S

n

∑ ∆D

=

i =i 1 =j 1

(16)

j

Agar diperoleh bentuk NSK non-negatif pada gangguan persoalan transportasi tersebut, gangguan parameter harus memenuhi kondisi berikut : Si + ∆Si ≥ 0, dan D j + ∆D j ≥ 0

(17)

Sehingga dengan menyelesaikan persoalan dengan algoritma Arsham-Kahn diperoleh bentuk tabel berikut :

Tabel Awal

? ? ?

X VB

X NB

Β

Ν

CVB

CNB

NSK

 ∆Si  b+Ι   ∆D j 

Tabel Akhir X NB XV Β

Β −1Ν

NSK

 ∆Si  Β −1b + Β −1    ∆D j 

CNB − CVB Β −1Ν

Tabel awal dibagi menjadi koefisien variabel basis Β , koefisien variabel nonbasis Ν , yang juga muncul pada tabel akhir, dan kolom NSK yang terdiri dari nilai


21

nominal NSK dan parameter gangguan ∆Si dan ∆D j , dan Ι merupakan matriks identitas berorde (m+n-1), atau dapat ditulis : ∆S1 ∆S 2  ∆S p ∆D1 ∆D2  ∆Dq

1 0    0 I=  0  0    0

0 1

 0  0

0 0

0 0

0 0 0

 1  0  0

0 1 0

0 0 1

0

 0

0

0

 0  ∆S1  0  ∆S 2    0  ∆S p  0  ∆D1   0  ∆D2    1  ∆Dq

Di mana: p + q = m + n – 1. Seperti telah dijelaskan sebelumnya solusi persoalan akan terdiri dari sebanyak m+n-1 variabel atau terdapat sebanyak m+n-1 variabel basis, jadi matriks B merupakan koefisien dari m+n-1 variabel ini. Namun

dalam

proses penyelesaian persolan

dengan algoitma Arsham-Khan, kolom-kolom variabel akan dihapus begitu variabel tersebut dimasukkan ke dalam basis, atau dengan kata lain kolom untuk variabel basis ditiadakan. Akan tetapi berdasarkan tabel awal dan karena persoalan ini diselesaikan dengan metode Gauss-Jourdan maka berlaku

[Β  Ι ] ⇒ Ι  Β −1 

sehingga diperoleh

hasil seperti pada tabel akhir. Analisis sensitivitas dilakukan setelah diperoleh matriks invers basis Β −1 , yaitu matriks koefisien dari ∆Si

dan ∆D j

pada solusi

optimal X ij* (∆Si , ∆D j ) .

2.6 Analisis Sensitivitas Pada Persoalan Transportasi

Analisis sensitivitas pada persoalan program linear dilakukan setelah diperoleh solusi optimal karena adanya perubahan suatu nilai sebelah kanan atau koefisien fungsi objektif. Berdasarkan perubahan tersebut maka diperiksa dampak perubahannya terhadap solusi optimal dan nilai optimal. Uji terhadap perubahan solusi optimal dan nilai optimal tersebut disebut analisis sensitivitas.


22

Sebagai contoh , jika solusi optimal adalah sebagai berikut : −1 = xΒ* Β= b, Z * CΒ Β −1b

(18)

Di mana CΒ adalah vektor koefisien dari fungsi objektif yang koefisiennya berhubungan dengan indeks variabel basis, xΒ* adalah solusi optimal basis dan Z * adalah nilai optimal. Jadi, rasio perubahan solusi optiml dan nilai optimal terhadap perubahan b k adalah sebagai berikut :

dxΒ* i dxΒ* −1 * = Β atau = y= 1, 2, ..., m i ,k , k db db k

(19)

di mana yi*,k merupakan elemen ke (i,k) dari matriks Β −1 .

Analisis sensitivitas pada parameter sebelah kanan persoalan transportasi tidak dapat dilakukan dengan menggunakan metode analisis sensitivitas yang digunakan pada persoalan program linear biasa. Hal ini disebabkan, karena satu parameter, beberapa parameter mungkin berubah secara simultan atau serentak karena perubahan parameter harus juga memenuhi persamaan keseimbangan model transportasi ( ∑ Si = ∑ D j ) (karena keseimbangan persoalan transportasi, paling sedikit satu lagi parameter sebelah kanan harus diubah). Untuk menguji dan mengukur nilai ini, digunakan konsep diferensial lengkap.

Definisi : Untuk fungsi y = f ( x) , didefinisikan: (a) dx , disebut diferensial x, dengan hubungan dx = ∆x . (b) dy , disebut diferensial y, dengan dy = f ′( x)dx .

Dari definisi, diferensial peubah bebas adalah sama dengan pertambahan peubah tersebut, tetapi diferensial peubah yang bergantung tidak sama dengan pertambahan peubah tersebut.


23

Untuk fungsi 2 variabel bebas x dan y, z = f(x, y), didefinisikan dx = ∆x dan

dy = ∆y . Bila x berubah sedangkan y tetap, z merupakan fungsi dari x saja dan diferensial parsial z terhadap x didefinisikan sebagai = d x z f x= ( x, y ) d x

∂z dx . ∂x

Dengan cara yang sama, diferensial parsial z terhadap y didefinisikan sebagai

∂z dy . Diferensial total dz didefinisikan sebagai jumlah diferensial ∂y

= d y z f y= ( x, y ) d y parsialnya, yaitu,

dz =

∂z ∂z dx + dy ∂x ∂y

(20)

Untuk fungsi w = F ( x, y, z , ..., t ) , diferensial total dw didefinisikan sebagai

dw =

∂w ∂w ∂w ∂w dx + dy + dz + ... + dt ∂x ∂y ∂z ∂t

(21)

Andaikan bahwa, diantara nilai sebelah kanan k parameter diubah. Selanjutnya, berdasarkan sifat keseimbangan persoalan transportasi,

∑s = ∑d i

j

dan

∆d j < d j dan ∆si < si harus dipenuhi. Maka berdasarkan konsep diferensial total,

diperoleh persamaan berikut :

= dx * Bi

∂xB*i ∂b1

db1 +

∂xB*i ∂b 2

db 2 + ... +

∂xB*i ∂b m

db m

(22)

Dengan memperhatikan konsep umum perubahan dalam kasus diferensial lengkap, dapat dianggap bahwa db1 = ∆b1 , sehingga diperoleh dxB*i = ∆xB*i . Dengan menggantikan

dxB*i db k

= yi*,k dalam persamaan (22) dan juga dengan memperhatikan

perubahan dalam k parameter nilai sebelah kanan, persamaan berikut diperoleh :


24

∆xB*i = yi*,1∆b1 + yi*,2 ∆b 2 + ... + yi*,k ∆b k

(23 )

yi*, j , j = 1, 2, ..., k adalah faktor baris ke i dari matriks Β −1 dan juga

Karena

berdasarkan sifat unimodular pada Β −1 , persamaan berikut diperoleh :

∆xΒ* = i

k

∑ α (∆b ) , =i j =1

i

1, 2, ..., m

α= 1, − 1 atau 0

(24)

Seperti telah dijelaskan sebelumnya, pada analisis sensitivitas suatu persoalan, perubahan parameter tidak boleh mengubah basis optimal yang telah diperoleh. Sehingga, setelah perubahan nilai sebelah kanan, harus dipenuhi : xΒ* i + ∆xΒ* i ≥ 0, i =1, 2, ..., m

(25)

yang menyatakan kemampuan basis tetap fisibel setelah perubahan. Solusi optimal fisibel dan basis tidak berubah setelah perubahan parameter sebelah kanan secara simultan diuji sebagai berikut : perlu dicari batasan ∆bi yang tidak membawa ke dalam bentuk infisibel atau tidak layak pada solusi optimal. Sebagai contoh, persamaan berikut dipenuhi untuk ∆bi :

xΒ* i + ∆xΒ* i ≥ 0

 ∆b k  ∆b 2 xΒ* i +  yi*,1 + yi*,2 + ... + yi*,k  ∆b1 ≥ 0, ∆b1 ∆b1  

dxΒ* i x = ≥0, db1 * Βi

i= 1, 2, ..., m

i= 1, 2, ..., m

(26)

(27)

Jika


25

dxΒ* i db1

≤ 0 , maka db1 ≤

− xΒ* i

* Βi

dx

(28)

db1

dan secara umum,    − x* dx*   Βi  Βi ∆b1 ≤ min sΒ  * ≤ 0  dxΒi db1   db1 

(29)

dipenuhi yang menyatakan perubahan maksimum b1 , di mana SΒ merupakan indeks variabel basis. Batasan untuk paramer lainnya dapat ditentukan dengan cara yang sama.


BAB II LANDASAN TEORI

Recommend Documents