BAB 2 LANDASAN TEORI
2.1
Sistem dan Model 2.1.1
Pengertian sistem Pengertian sistem dapat diketahui dari definisi yang diambil dari
beberapa pendapat pengarang antara lain : Menurut Romney (2003, p2) sistem adalah suatu set dari dua atau lebih komponen yang berhubungan untuk mencapai tujuan. Menurut Mcleod (2001, p11) sistem adalah sekelompok elemen yang terintegrasi dengan maksud yang sama untuk mencapai suatu tujuan. Menurut Hall (2001, p5) sistem adalah sekelompok dua atau lebih komponen-komponen yang saling berkaitan atau subsistem-subsistem yang bersatu untuk mencapai tujuan yang sama. Menurut Schmidt and Taylor (Law 2000, p3) sistem adalah merupakan suatu kesatuan dari beberapa objek seperti manusia atau mesin yang saling bereaksi untuk mendapatkan suatu tujuan akhir. Menurut Kamus Besar Bahasa Indonesia, sistem adalah seperangkat unsur yang secara teratur saling berkaitan sehingga membentuk suatu totalitas. Dari definisi di atas, maka dapat disimpulkan bahwa sistem adalah kumpulan komponen-komponen dan unsur-unsur yang saling berhubungan untuk mencapai tujuan yang sama.
2.1.2
Pengertian model Mempelajari sistem akan lebih mudah bila kita membangun model dari
sistem tersebut. Maka pengertian model adalah gambaran atau proyeksi dari suatu obyek atau sistem yang sebenarnya. Suatu model dapat dikatakan sempurna bila model tersebut dapat menggambarkan seluruh aspek yang terdapat dalam obyek atau sistem yang sebenarnya dan memiliki sifat atau karakter yang sama.
4
5 Model terdiri dari 2 jenis, yaitu model fisik dan simbolis. Model Fisik
: merupakan gambaran fisik dari suatu benda baik dalam skala yang sama maupun berbeda.
Model Simbolis
: merupakan gambaran dari suatu sistem dalam bentuk simbol-simbol yang memiliki hubungan matematis.
Model matematika dapat diselesaikan dengan 2 cara, yaitu : -
bila model terbilang sederhana, maka dapat diselesaikan dengan cara analitik.
-
Namun bila model matematikanya sangat komplek, dapat diselesaikan dengan cara mensimulasikan model tersebut.
2.2
Model Transportasi Model transportasi merupakan bagian dari program linear. Tujuan dari model
transportasi ini adalah untuk mengoptimalkan jumlah pengiriman ke tujuan dalam sekali pengiriman, sehingga dapat menekan biaya serendah mungkin atau mencapai jumlah laba yang maksimal. Program linear adalah suatu model umum yang jamak dipakai untuk menyelesaikan masalah pengalokasian sumber daya yang terbatas secara optimal, mencangkup perencanaan kegiatan-kegiatan yang akan dilakukan dengan menggunakan anggapan-anggapan hubungan linear, untuk mencapai hasil yang maksimal. Model transportasi merupakan kasus khusus dari masalah
program linear
dengan tujuan untuk mengangkut barang tunggal (1 jenis) dari berbagai asal (origin) ke berbagai tujuan (destination), dengan biaya angkut serendah mungkin. Telah dijelaskan bahwa model transportasi merupakan suatu kasus khusus dalam masalah program linear, namun dapat susut menjadi masalah transportasi jika : 1. Koefisien dari variabel struktural , yaitu amn terbatas pada nilai-nilai 0 atau 1. 2. terdapat adanya kehomogenan antara unit-unit dalam persyaratan. Alokasi produk ini harus diatur sedemikian rupa, karena terdapat perbedaan biaya-biaya alokasi dari satu sumber ke tempat-tempat tujuan yang berbeda-beda, dan dari beberapa sumber ke suatu tempat tujuan juga berbeda-beda.
6 Model transportasi merupakan salah satu kasus khusus dari masalah program linear yang bertujuan untuk mencari biaya angkut serendah mungkin. Model transportasi memiliki ciri-ciri khas seperti yang dimiliki oleh program linear, yaitu : 1. Fungsi obyektif yang linear n f(x) = c1x1 + c2x2 + c3x3 + .... = ∑ cjxj j=1
..................................(1)
2. Struktur persyaratan yang linear Setiap masalah program linear memiliki sekumpulan persyaratan linear. n ∑ j=1
m ∑ i=1
i = 1, 2, ..., m aij xj ≤ bi
..................................(2) j = 1, 2, ..., n
dengan aij merupakan koefisien struktural yang mencerminkan spesifikasi teknik dari masalah yang dibahas, dan ia tampil sebagai koefisien dari variabel struktural dalam persyaratan-persyaratan struktural. Sedangkan bi adalah konstanta yang menggambarkan kapasitas maksimum atau minimum dari fasilitas-fasilitas yang ada maupun sumber-sumber yang tersedia. Bentuk persyaratan struktural yang linear dituliskan secara lengkap sebagai berikut : a11x1 + a12x2 + a13x3 + ... + a1nxn ≤ b1 a21x1 + a22x2 + a23x3 + ... + a2nxn ≤ b2 .......................................................................................... ..........................................................................................
am1x1 + am2x2 + am3x3 + ... + amnxn ≤ bm 3. Persyaratan tidak negatif Variabel struktural, variabel slack, variabel slack buatan dari masalah program linear terbatas pada nilai-nilai tidak negatif, ditulis : Xj
> 0
j = 1, 2, ..., n
Si
> 0
i = 1, 2, ..., m
Ai
> 0
7 Tabel 2.1 Tabel Model Transportasi Kapasitas origin per periode waktu
DESTINATION ORIGIN D1
D2 c11
O1 X11
c12 X12
d1
c23
C2n
Cm3 Xm3
d2
b1 b2
X2n
Cm2 Xm2
Xm1
C1n X1n
X23
Cm1
Om
c13
c22 X22
X21
Dn
X13
c21
O2
Permintaan tujuan per periode waktu
D3
cmn
bm
Xmn d3
dn
Keterangan : Om = Origin (asal) Dn = Destination (tujuan) cmn = biaya pengangkutan 1 unit barang dari asal m ke tujuan n xmn = banyak unit barang yang diangkut dari asal m ke tujuan n dn = permintaan tujuan per periode waktu bm = kapasitas origin per periode waktu Jika m adalah jumlah baris dan n adalah jumlah kolom dalam suatu masalah transportasi, kita dapat menyatakan masalah secara lengkap dengan m+n-1 persamaan. Ini berarti bahwa suatu penyelesaian dasar yang memenuhi persyaratan dari suatu masalah transportasi hanya memiliki m+n-1 komponen-komponen positif.
Pendekatan model transportasi Model transportasi terdiri atas 3 langkah dasar : Langkah 1
: melibatkan penentuan
pengiriman awal, sedemikian rupa sehingga
diperoleh solusi dasar yang memenuhi syarat. Ini berarti bahwa m+n-1 sel atau rute dari matriks transformasi digunakan untuk tujuan pengangkutan. Sel yang digunakan untuk pengangkutan disebut sel yang
8 ditempati, sedang sel lainnya dari matriks transportasi akan disebut sel kosong. Langkah 2
: bertujuan menentukan biaya kesempatan (opportunity cost) yang berkaitan dengan sel kosong. Biaya kesempatan dari sel kosong dapat dihitung untuk setiap sel kosong tersendiri, atau dihitung untuk semua sel kosong secara keseluruhan. Jika biaya kesempatan dari semua sel kosong tidak positif, maka telah diperoleh solusi optimal. Di lain pihak, jika terdapat hanya satu sel saja memiliki biaya kesempatan bernilai positif, solusi pasti belum optimal dan kita harus melangkah ketiga.
Langkah 3
: melibatkan penentuan solusi dasar yang memenuhi syarat, baru dan lebih baik. Sekali solusi dasar yang baru dan memenuhi syarat telah dicapai, kita ulangi langkah 2 dan langkah 3 sampai suatu solusi optimal telah ditentukan.
Sebelum masuk ke dalam penyelesaian model transportasi, sesuai langkah pertama harus ditentukan dahulu solusi awalnya. Ada beberapa cara menentukan solusi awal, yaitu metode pojok barat-laut dan metode inspeksi.
2.2.1
Metode Pojok Barat-Laut Metode ini dikenal juga dengan nama North West Corner Method.
Metode ini ditemukan oleh Charnes dan Cooper, dan kemudian dikembangkan oleh Danzig. Sesuai nama aturan ini, maka penempatan pertama dilakukan di sel paling kiri dan paling atas dari matriks, yaitu sel O1D1. Bandingkan persediaan di O1 dengan kebutuhan di D1, yaitu masing-masing d1 dan b1. Buat x11 = Min (b1, d1). •
Bila b1 > d1, maka x11 = d1. Teruskan ke sel O1D2, yaitu gerakan horizontal dimana x12 = min. (b1 - d1, d2).
•
Bila b1 < d1, maka x11 = b1. Teruskan ke sel O2D1, yaitu gerakan vertikal dimana x21 = min. (d1 - b1, b2).
•
Bila b1 = d1, maka buatlah x11 = d1 dan teruskan ke sel O2D2 (gerakan miring).
9 Teruskan langkah ini menjauhi pojok barat laut menuju pojok tenggara dari tabel, hingga akhirnya semua permintaan terpenuhi. Setelah program awal ini selesai ditentukan, maka perlu diuji persyaratan bahwa m+n-1 sel harus terisi. Bila m+n-1 sama dengan jumlah sel yang terisi, maka solusi tidak merosot. Metode pojok barat-laut ini memperlihatkan bahwa tiap langkah yang dilakukan akan memenuhi satu kendala. Hingga akhirnya berhenti di langkah ke m+n-1, karena pada langkah ini sudah terpenuhi m+n-1 kendala. Metode pojok barat-laut ini belum bisa dibilang optimal, dikarenakan metode ini mengabaikan biaya yang relevan dari tiap-tiap rute.
2.2.2
Metode Inspeksi Dalam menyelesaikan masalah transportasi, diperlukan adanya inspeksi
dan pertimbangan. Untuk masalah transportasi berdimensi kecil, hal ini akan memberi pengurangan terhadap waktu. Alokasi pertama dibuat terhadap sel yang berkaitan dengan biaya pengangkutan terendah. Sel dengan ongkos terendah ini diisi sebanyak mungkin dengan mengingat persyaratan kapasitas origin maupun persyaratan permintaan tempat tujuan. Lalu beralih mengalokasikan ke sel termurah berikutnya dengan memperhatikan kapasitas yang tersisa dan permintaan baris dan kolomnya. Ada kemungkinan terdapat adanya ikatan antara sel-sel termurah. Ikatan tersebut dapat dipatahkan atau dengan memilih sembarang sel untuk diisi. Banyaknya sel yang terisi harus sedemikian hingga diperoleh m+n-1 sel yang terisi. Secara singkat, pendekatan metode transportasi didasarkan atas tiga langkah, yaitu : 1. menentukan program awal untuk mencapai solusi dasar yang memenuhi syarat. 2. menentukan biaya kesempatan dari setiap sel kosong. memperbaiki program yang sedang berjalan untuk memperoleh program yang lebih baik, hingga akhirnya mencapai solusi optimal.
10
Selanjutnya, terdapat beberapa cara penyelesaian masalah dalam model transportasi. Semua cara penyelesaian ini mengarah pada penyelesaian optimal dari masalah-masalah transportasi yang terjadi, yaitu Metode Batu Loncatan, Metode MODI, dan Metode Pendekatan Vogel.
2.2.3
Metode Batu Loncatan Metode ini dikenal juga dengan nama Stepping Stone Method. Metode ini
digunakan untuk menentukan optimal atau tidaknya solusi dasar yang didapat pada langkah pertama. Sebelum mengaplikasikan metode batu loncatan ini, harus ditentukan terlebih dahulu biaya kesempatan atau opportunity cost dari sel yang kosong. Dalam model transportasi melibatkan pengambilan keputusan dengan kepastian, maka suatu solusi optimal tidak akan menimbulkan suatu biaya kesempatan yang positif. Untuk menentukan adanya suatu biaya kesempatan yang bernilai positif dalam suatu program, maka setiap sel kosong (sel yang tidak ikut dalam jalur pengangkutan) harus diselidiki. Metode batu loncatan ini dapat dipergunakan untuk setiap matriks yang berukuran m x n. Dalam metode ini, sebuah loop tertutup dilengkapi dengan tanda (+) dan (-) harus ditentukan untuk setiap sel kosong sebelum menentukan biaya kesempatannya. Setelah loop-loop tersebut ditentukan, barulah ditentukan biaya kesempatannya. Tiap loop tersebut dihitung dengan cara menambah dan mengurangi secara bergantian
biayanya dimulai dari sel kosong yang akan
dicari. Jika ternyata biaya kesempatan dari tiap loop tersebut tidak ada yang bernilai positif, maka program telah optimal. Sebaliknya, jika terdapat satu saja sel kosong yang memiliki biaya kesempatan positif, maka program belum optimal. Sehingga program tersebut masih perlu diperbaiki.
11 Perbaikan program awal diarahkan oleh loop tertutup yang bernilai positif dari sel kosong. Tentukan bilangan dengan tanda negatif (-) yang terkecil dalam sel yang terdapat dalam loop tersebut. Dalam loop tersebut, tambahkan bilangan tersebut ke semua sel yang bertanda positif (+) dan kurangkan semua sel yang bertanda negatif (-) dengan bilangan tersebut. Metode batu loncatan dapat digunakan untuk setiap matriks yang berukuran m x n. Inti dari prosedur batu loncatan dalam penyelesaian masalah transportasi secara singkat yaitu : 1. menyusun solusi dasar yang memenuhi syarat. 2. setelah memperoleh solusi dasar yang memenuhi syarat, lalu dilakukan penentuan biaya kesempatan dari sel-sel yang kosong 3. jika tidak ada satu sel pun memiliki biaya kesempatan yang bernilai positif, maka program sudah optimal. Sebaliknya, jika ada satu saja sel yang memiliki biaya kesempatan yang bernilai postitif, maka program belum optimal. Maka harus dilakukan perbaikan program dengan mengikut sertakan sel kosong yang memiliki biaya kesempatan tertinggi.
2.2.4
Metode MODI Metode MODI disebut juga Modified Distribution Method, sangat mirip
dengan metode batu loncatan, kecuali bahwa ia menyajikan cara yang lebih efisien untuk menghitung tanda-tanda peningkatan dari sel-sel yang kosong. Perbedaan utama antara dua metode ini menyangkut langkah dalam penyelesaian masalah, dimana diperlukan adanya suatu lintasan tertutup. Untuk menghitung penunjuk peningkatan suatu solusi khusus, maka dalam metode batu loncatan perlu digambar suatu lintasan tertutup untuk setiap sel kosong. Ditentukan sel kosong dengan biaya kesempatan tertinggi, kemudian dipilih untuk ikut dalam program perbaikan berikutnya. Dalam metode MODI penunjuk peningkatan dapat dihitung tanpa menggambar lintasan tertutup. Dalam kenyataannya metode MODI memerlukan hanya satu lintasan tertutup. Lintasan ini digambar setelah sel kosong yang memiliki biaya kesempatan tertinggi positif ditemukan. Seperti dalam metode
12 batu loncatan, kegunaan lintasan ini ialah untuk menentukan jumlah unit maksimum yang dapat dipindahkan ke sel kosong dalam program perbaikan berikutnya. Maka, prosedur untuk menghitung biaya kesempatan dari sel kosong dalam MODI tidak tergantung pada lintasan loop tersebut. Biaya kesempatan = implied cost - biaya sebenarnya Cara menentukan implied cost dari sebuah sel kosong tanpa menggambarkan lintasan loop terlebih dahulu, dengan menyusun kerangka utama dari metode MODI, kemudian mengurangkan biaya sebenarnya dari implied cost sel kosong yang telah dihitung. Sesuai itu dapat ditunjukkan bahwa dalam kasus masalah transportasi, kesempatan dari setiap sel terisi (sel berisi variable basis) adalah nol. Dengan perkataan lain, jika variable basis tidak akan diubah, maka pemasukan dan pemindahan 1 unit di sembarang sel terisi tidak akan mengakibatkan perubahan biaya. Sekarang, tentukan sekumpulan bilangan baris (ditempatkan di sebelah paling kanan) dan sekumpulan bilangan kolom (ditempatkan di bawah setiap kolom dari tabel) sedemikian rupa sehingga ongkos pengangkutan per unit dari setiap sel terisi sama dengan jumlah dari bilangan baris dan bilangan kolom. Selanjutnya, kerana jumlah bilangan baris dan bilangan kolom dari sembarang sel terisi sama dengan ongkos dari sel tersebut (suatu variable basis), maka jumlah bilangan baris dan bilangan kolom dari setiap sel kosong memberikan implied cost dari sel kosong tersebut. Maka implied cost dari sembarang sel kosong diberikan oleh
Implied cost
= bilangan baris + bilangan kolom = u m + vn
Maka dengan menentukan bilangan baris dan bilangan kolom secara lengkap, kita dapat menghitung implied cost untuk setiap sel kosong tanpa menggambar lintasan loop.
13 Untuk setiap sel terisi, pilih um (bilangan baris) dan vn (bilangan kolom) sehingga cmn (biaya pengangkutan sebenarnya per unit di sel terisi) sama dengan jumlah dari um dan vn. Misalkan untuk sel terisi yang terletak di baris 1 dan kolom 1, maka c11 = u1 + v1 dan c12 = u1 +v2 dan seterusnya. Proses ini harus dilakukan untuk setiap sel terisi. Tetapi harap disadari bahwa walaupun solusi dasar yang memenuhi syarat dalam suatu model transportasi terdiri atas m+n–1 variabel (dengan perkataan lain, terdapat m+n–1 sel terisi), tentukan m+n nilai untuk memperoleh sekumpulan bilangan baris dan kolom, harus dipilih satu bilangan sembarang yang mewakili suatu baris atau suatu kolom. Sekali suatu bilangan baris atau kolom telah dipilih secara sebarang, bilangan baris dan bilangan kolom lainnya dapat ditentukan oleh hubungan cmn = um + vn. Hubungan ini harus berlaku untuk semua sel isi. Karena sembarang bilangan dapat dipilih untuk mewakili salah satu dari um atau vn, ikuti secara praktis dengan memisahkan u1 = 0.
Tabel 2.2
Metode MODI
Implied Cost
Ongkos Sebenarnya
Tindakan
um + vn
>
cmn
Program yang lebih baik dapat disusun dengan mengikut sertakan sel ini
um + vn
=
cmn
Tak berpengaruh
um + vn
<
cmn
Sel ini jangan diikut sertakan dalam program
Jika implied cost (um + vn) dari suatu sel kosong lebih besar dari ongkos sebenarnya (cmn), maka sel kosong ini dapat diikut sertakan dalam perbaikan program berikutnya. Jika implied cost (um + vn) dari suatu sel kosong kurang dari ongkos sebenarnya (cmn), maka sel kosong ini jangan diikut sertakan. Jika (um + vn) = cmn maka sel kosong ini tidak berpengaruh terhadap perbaikan program.
14 Singkatnya, untuk menilai dan meningkatkan suatu program dimana tujuannya ialah meminimumkan fungsi obyektif, maka aturan yang tertera pada tabel aturan MODI diatas berlaku. Langkah terakhir dalam metode MODI persis sama seperti langkah berkaitan dalam metode batu loncatan. Setelah mengenali sel kosong yang memiliki biaya kesempatan terbesar positif, sel kosong ini harus diikut sertakan dalam program perbaikan dan sebuah lintasan tertutup harus digambar untuk sel ini. Solusi dasar yang baru dan memenuhi syarat diturunkan dari program awal dengan menggeser unit barang sebanyak mungkin kedalam sel kosong tanpa melanggar persyaratan rim.
Implied cost
= u2 + v2
Biaya kesempatan = implied cost - biaya sebenarnya Prosedur Metode MODI (untuk kasus minimum) Langkah 1
Memperoleh solusi dasar yang memenuhi syarat. Metode yang digunakan metode pojok barat-laut atau inspeksi. Harus diperoleh m+n–1 sel terisi. Jika jumlah sel terisi melebihi m+n–1, maka ada salah hitung. Jika jumlah sel terisi kurang dari m+n-1, maka solusi ini mengalami kemerosotan.
Langkah 2.
Menentukan biaya kesempatan dari setiap sel kosong. a. Tentukan bilangan baris dan bilangan kolom secara lengkap. b. Untuk setiap sel terisi berlaku cmn = um + vn ambillah u1 = 0. c. Hitunglah implied cost dari setiap sel kosong. Implied cost = bilangan baris + bilangan kolom. d. Tentukan biaya kesempatan dari setiap sel kosong. Opportunity cost = um + vn - cmn. Jika semua sel kosong memiliki biaya kesempatan tidak positif, maka solusi sudah optimal.
15 Jika masih ada sel kosong yang memiliki biaya kesempatan positif, program masih dapat diperbaiki. Langkah 3.
Merancang peningkatan program Sel kosong yang memiliki biaya kesempatan positif terbesar diikut sertakan dalam program perbaikan. a. Gambarlah suatu loop melalui sel kosong tersebut menuju selsel terisi kemudian kembali lagi ke sel kosongnya. b. Beri tanda (+) pada sel kosong yang akan diisi, kemudian berganti-ganti letakkan tanda (+) dan (-) pada sel-sel terisi yang dilalui loop. c. Banyaknya barang yang harus digeser ditentukan oleh alokasi terendah dari sel yang bertanda (-).
Langkah 4.
Ulangi langkah 2 dan 3 sampai diperoleh program yang optimal.
Prosedur Metode MODI (untuk kasus maksimum) Kecuali untuk satu transformasi, suatu masalah transportasi dengan tujuan menentukan nilai maksimum dari suatu fungsi, dapat diselesaikan dengan algoritma MODI seperti telah dijelaskan. Transformasi dilakukan dengan mengurangkan semua cmn dari cmn tertinggi dari matriks transportasi. Nilai cmn yang telah mengalami transformasi memberikan ongkos relevan, dan masalah menjadi masalah menentukan minimum. Jika suatu solusi optimal telah dicapai untuk masalah transformasi minimum ini, nilai dari fungsi obyektif dapat dihitung dengan memasukan nilai asli dari cmn kedalam rute yang merupakan basis (sel terisi) dalam solusi optimal.
2.2.5
Metode Pendekatan Vogel Metode ini disebut juga Vogel Approximation Metod (VAM). Metode ini
didasarkan atas suatu beda kolom dan suatu beda baris, yang menentukan beda antara dua ongkos. Setiap beda dapat dianggap sebagai penalti karena tidak menggunakan rute termurah. Setelah dilakukan perhitungan penalti sesuai
16 metode pendekatan Vogel, ditentukanlah penalti tertinggi. Baris atau kolom berkaitan dengan penalti tertinggi, akan dijadikan alokasi yang pertama. Alokasi pertama ini ditempatkan pada sel dengan penalti tertinggi pada baris atau kolom yang berkaitan dengan biaya termurah. Alokasi pertama ini menentukan baris atau kolom mana yang akan dihapus dari matriks transportasi, akibat terpenuhinya keperluan dari alokasi pertama tadi. Metode
ini
memiliki
kelemahan
dikarenakan
harus
melakukan
perhitungan-perhitungan yang banyak, sebelum tercapainya solusi dasar yang memenuhi syarat. Akan tetapi, metode pendekatan Vogel dapat menghasilkan biaya pengangkutan yang jauh lebih murah dibanding dengan menggunakan metode pojok barat-laut.
2.2.6
Kemerosotan Suatu penyelesaian dasar yang memenuhi syarat untuk suatu masalah
transportasi terdiri atas m+n-1 variabel basis. Ini berarti bahwa banyaknya sel terisi dalam suatu program transportasi satu kurang dari jumlah baris dan kolom dalam matriks transportasi. Jika jumlah sel terisi kurang dari m+n-1, maka terjadilah kondisi yang dinamakan kemerosotan. Kemerosotan disebut juga Degeneracy. Masalah transportasi ini dapat dikembangkan dengan dua cara. Pertama, masalah mengalami kemerosotan pada waktu program awal disusun melalui salah satu dari metode langkah pertama. Untuk menangani kemerosotan alokasi kemerosotan semacam ini, kita dapat memberi alokasi suatu jumlah barang yang kecil sekali (mendekati 0) terhadap salah satu atau lebih dari sel-sel kosong, sehingga jumlah sel isi menjadi m+n–1. Barang sejumlah kecil ini disebut ε (epsilon), dan sel yang kita beri alokasi ε menjadi sel terisi. Jumlah barang sebanyak ε demikian kecilnya, sehingga pengurangan atau penambahan terhadap suatu jumlah barang tidak mengubah bilangannya. Kedua, masalah transportasi dapat merosot selama tahap penyelesaian. Hal ini terjadi jika keikutsertaan sel kosong yang memiliki biaya kesempatan
17 tertinggi mengakibatkan kekosongan dua sel atau lebih di antara sel-sel yang ikut dalam program. Untuk menangani kasus kemerosotan semacam ini harus ditempatkan ε pada satu atau lebih sel kosong. Telah kita amati bahwa penempatan ε pada sembarang sel kosong, telah memungkinkan kita untuk menentukan suatu kumpulan bilangan baris dan bilangan kolom yang unik. Hal ini benar jika penyusunan program awal dilakukan dengan metode pojok barat-laut. Tetapi jika program awal disusun dengan metode lain, kita dapat menentukan suatu himpunan bilangan baris dan kolom yang unik. Akan kita berikan suatu contoh masalah transportasi untuk memberikan gambaran yang jelas tentang apa yang dimaksudkan. Pilihan terhadap solusi optimal dari masalah transportasi Suatu solusi optimal dari suatu masalah transportasi tidak selalu unik. Terdapatnya lebih dari satu penyelesaian optimal dapat ditentukan dengan menguji biaya kesempatan dari setiap sel kosong dalam program optimal. Jika terdapat sel kosong dengan biaya kesempatan sama dengan nol dalam program optimal, maka program optimal lainnya dengan biaya pengangkutan total yang sama seperti program optimal pertama selalu dapat disusun. Program optimal kedua dapat diperoleh dengan mengikutsertakan sel kosong yang memiliki biaya kesempatan sama dengan nol. Jika telah diperoleh dua program optimal, maka program optimal berikutnya dapat diturunkan sesuai rumus : Program optimal dengan
= dA + (1-d) B
A = matriks program optimal pertama B = matriks program optimal kedua d
= sembarang pecahan lebih kecil dari 1
