.jpg)
BAB I
PENDAHULUAN
1.1 Pendahuluan Riset Operasi
Sejak revolusi industri, dunia usaha mengalami perubahan dalam hal ukuran (besarnya) dan kompleksitas
organisasi-organisasi perusahaan. Bagian yang mengalami perubahan yang cukup menyolok adalah
perkembangan dalam pembagian kerja dan segmentasi tanggung jawab manajemen dalam organisasiorganisasi
tersebut. Disisi lain, organisasi-organisasi (perusahaan) pada saat ini harus beroperasi di dalam
situasi dan kondisi lingkungan bisnis yang dinamis dan selalu bergejolak, serta siap untuk berubah-ubah.
Perubahan-perubahan tersebut terjadi sebagai akibat dari kemajuan teknologi yang begitu pesat ditambah
dengan dampak dari beberapa faktor-faktor lingkungan lainnya seperti keadaan ekonomi, politik, sosial dan
sebagainya. Perkembangan Kemajuan teknologi tersebut telah menghasilkan dunia komputerisasi. Buah-buah
pembangunan telah melahirkan para pimpinan dan pengambilan keputusan, para peneliti, perencana dan
pendidik untuk memikirkan serta memcahkan/menganalisis permasalahan, mengambil langkah-langkah dan
strategi yang tepat serta target yang sesuai secara sistematis dalam rangka mencapai tujuan yang telah
ditentukan, yakni hasil yang memuaskan. Hasil yang memuaskan tersebut adalah hasil yang optimal yang berarti
dampak positipnya maksimum dan dampak negatipnya minimum.
Pola berpikir, pola analisis dan pemecahan masalah, pola pengambilan langkah-langkah, serta pola
penyusunan strategi dan target secara sistematis tersebut, disebut sebagai pola pendekatan ilmiah.
Arti riset operasi (operations research) telah banyak didefinisikan oleh beberapa ahli.
· Morse dan Kimball mendefinisikan riset operasi sebagai metode ilmiah (scientific method) yang
memungkinkan para manajer mengambil keputusan mengenai kegiatan yang mereka tangani dengan
dasar kuantitatif. Definisi ini kurang tegas karena tidak tercermin perbedaan antara riset operasi dengan
disiplin ilmu yang lain.
· Churchman, Arkoff dan Arnoff pada tahun 1950-an mengemukakan pengertian riset operasi sebagai
aplikasi metode-metode, teknik-teknik dan peralatan-peralatan ilmiah dalam menghadapi masalahmasalah
ysng timbul di dalam operasi perusahaan dengan tujuan ditemukannya pemecahan yang
optimum masalah-masalah tersebut.
· Miller dan M.K. Starr mengartikan riset operasi sebagai peralatan manajemen yang menyatukan ilmu
pengetahuan, matematika, dan logika dalam kerangka pemecahan masalah-masalah yang dihadapi
sehari-hari, sehingga akhirnya permasalahan tersebut dapat dipecahkan secara optimal.
Dari ketiga definisi tersebut dapat disimpulkan bahwa riset operasi berkenaan dengan pengambilan keputusan
yang optimal dalam, dan penyusunan model dari sistem-sistem baik yang diterministik maupun probabilistik yang
berasal dari kehidupan nyata. Atau dunia pengelolaan atau dunia usaha yang memakai pendekatan ilmiah atau
pendekatan sistematis disebut riset operasi (Operations Resech).
Tim-tim riset operasi dalam lingkungan dunia bisnis ini menandai kemajuan teknik-teknik riset operasi.
Sebagai contoh utama adalah metode simpleks untuk pemecahan masalah-masalah linear programming, yang
dikembangkan oleh George Dantzig dalam tahun 1947. Disamping itu banyak peralatan-peralatan riset operasi
standar, seperti linear programming, dynamic programming, teori antrian dan teori pengendalian persediaan
telah dikembangkan sebelum akhir tahun 1950-an.
Dalam hal ini termasuk menentukan pilihan dari alternatif-alternatif yang ada secara umum meliputi langkahlangkah
:
1. Identifikasi masalah
Identifikasi masalah terdiri dari :
Penentuan dan perumusan tujuan yang jelas dari persoalan dalam sistem model yang dihadapi.
Identifikasi perubah yang dipakai sebagai kriteria untuk pengambilan keputusan yang dapat dikendalikan
maupun yang tidak dapat dikendalikan. Kumpulkan data tentang kendala-kendala yang menjadi syarat
ikatan terhadap perubah-perubah dalam fungsi tujuan sistem model yang dipelajari.
2. Penyusunan model
Penyusunan model terdiri dari :
Memilih model yang cocok dan sesuai dengan permasalahannya. Merumuskan segala macam faktor yang
terkait di dalam model yang bersangkutan secara simbolik ke dalam rumusan model matematika.
Menentukan perubah-perubah beserta kaitan-kaitannya satu sama lainnya. Tetapkan fungsi tujuan beserta
kendala-kendalanya dengan nilai-nilai dan perameter yang jelas.
3. Analisa model.
Analisa model terdiri dari tiga hal penting, yaitu :
· Melakukan anlisis terhadap model yang telah disusun dan dipilih.
· Memilih hasil-hasil analisis yang terbaik (optimal).
· Melakukan uji kepekaan dan anlisis postoptimal terhadap hasil-hasil terhadap analisis model.
4. Pengesahan model.
Analisis pengesahan model menyangkut penilaian terhadap model tersebut dengan cara mencocokannya
dengan keadaan dan data yang nyata, juga dalam rangka menguji dan mengesahkan asumsi-asumsi yang
membentuk model tersebut secara struktural (yaitu perubahnya, hubungan-hubungan fungisionalnya, dan
lain-lain).
5. Implementasi hasil.
Hasil-hasil yang diperoleh berupa nilai-nilai yang akan dipakai dalam kriteria pengambilan keputusan
merupakan hasil-hasil analisis yang kiranya dapat dipakai dalam perumusan keputusan yang kiranya dapat
dipakai dalam perumusan strategi-strategi, target-target, langkah-langkah kebijakan guna disajikan kepada
pengambilan keputusan dalam bentuk alternatif-alternatif pilihan.
BAB II
PROGRAM LINIER
2.1 Pendahuluan
Pengertian Program Linier:
Secara Umum :
Linear programming (program linier) merupakan salah satu teknik penyelesaian riset operasi dalam hal ini
adalah khusus menyelesaikan masalah-masalah optimasi (memaksimalkan atau meminimumkan) tetapi hanya
terbatas pada masalah-masalah yang dapat diubah menjadi fungsi linier. Demikian pula kendala-kendala yang
ada juga berbentuk linier.
Secara khusus;
Persoalan program linier adalah suatu persoalan untuk menentukan besarnya masing-masing nilai variabel
(variable pengambilan keputusan) sedemikian rupa sehingga nilai funsi tujuan atau objektif (objective function)
yang linier menjadi optimum (maksimum atau minimum) dengan memperhatikan pembatasan-pembatasan
(kendala-kendala) yang ada yaitu pembatasan ini harus dinyatakan dengan ketidaksamaan yang linier (linear
inequalities).
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 positip, manfaat-manfaat, atau dampak negatip, kerugian-kerugian, resiko-resiko, biayabiaya,
jarak, waktu yang ingin diminimumkan.
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
baku/model matematika sebagai berikut :
Menentukan nilai dari X1, X2, X3, ....., Xn sedemikian rupa sehingga :
Z = C1 X1 + C2 X2 + .... +Cj Xj +....+Cn Xn = Cj Xj (Optimal[maksimum/minimum])
j=1
Yang kemudian disebut sebagai Fungsi Tujuan (Objective Function)
dengan pembatasan (Funsi Kendala/Syarat Ikatan) :
a11 X1 + a12 X2 +.....+a1n Xn £ atau ³ b1 ,
a21 X1 + a22 X2 +.....+a2n Xn £ atau ³ b2,
· · · ·
· · · ·
· · · ·
am1 X1 + am2 X2 +....+ amn Xn £ atau ³ bm,
n
atau aij Xj £ atau ³ bi untuk i = 1,2,3, … , m.
j=1
dan X1 ³ 0, X2 ³ 0,...,Xn ³ 0 atau Xj ³ 0, dimana j = 1, 2, 3,...., n (syarat non-negatif).
Keterangan :
Ada n macam barang yang akan diproduksi masing-masing sebanyak X1, X2, ...,Xn unit.
Xj = Variabel pengambilan keputusan atau kegiatan yang ingin dicari (misalnya banyaknya produksi barang
yang ke-j, dimana j = 1, 2, ...,n ).
Cj = Parameter yang dijadikan kriteria optimasi atau koefisien variabel pengambilan keputusan dalam fungsi
tujuan (misalnya harga per satuan barang ke-j).
bi = Sumber daya yang terbatas, yang membatasi kegiatan atau usaha yang bersangkutan disebut juga
konstanta atau “nilai sebelah kanan (nsk)” dari kendala ke-i (misalnya banyaknya bahan mentah ke-i, i=
1, 2, .., m). Ada m macam bahan mentah, yang masing-masing tersedia b1, b2,...., bm.
aij = Koefisien teknologi variabel pengambilan keputusan (kegiatan yang bersangkutan) dalam kendala ke-i
(misalnya banyaknya bahan mentah ke-i yang digunakan untuk memproduksi 1 satuan barang ke-j).
Contoh Soal:
1. Sebagai contoh dalam memformulasikan permasalahan, berikut ini akan dibahas perusahaan Krisna Furniture
yang akan membuat meja dan kursi. Keuntungan yang diperoleh dari satu unit meja adalah $7,- sedang
keuntungan yang diperoleh dari satu unit kursi adalah $5,-. Namun untuk meraih keuntungan tersebut Krisna
Furniture menghadapi kendala keterbatasan jam kerja. Untuk pembuatan 1 unit meja dia memerlukan 4 jam
kerja. Untuk pembuatan 1 unit kursi dia membutuhkan 3 jam kerja. Untuk pengecatan 1 unit meja dibutuhkan 2
jam kerja, dan untuk pengecatan 1 unit kursi dibutuhkan 1 jam kerja. Jumlah jam kerja yang tersedia untuk
pembuatan meja dan kursi adalah 240 jam per minggu sedang jumlah jam kerja untuk pengecatan adalah 100
jam per minggu. Berapa jumlah meja dan kursi yang sebaiknya diproduksi agar keuntungan perusahaan
maksimum?
2. Suatu perusahaan akan memproduksi 2 macam barang yang jumlahnya tidak boleh lebih dari 18 unit.
Keuntungan dari kedua produk tersebut masing-masing adalah Rp. 750,- dan Rp. 425,- per unit. Dari survey
terlihat bahwa produk I harus dibuat sekurang-kurangnya 5 unit sedangkan produk II sekurang-kurangnya 3
unit. Mengingat bahan baku yang ada maka kedua produk tersebut dapat dibuat paling sedikit 10 unit. Tentukan
banyaknya produk yang harus dibuat untuk mendapatkan keuntungan yang maksimum ?
3. Sebuah pabrik obat menyediakan 2 jenis campuran A dan B. Bahan-bahan dasar yang terkandung dalam tiap kg
campuran A dan B adalah sebagai berikut:
Bahan Dasar
Bahan-1 Bahan-2
Campuran A 0,4 kg 0,6 kg
Campuran B 0,8 kg 0,2 kg
Dari campuran A dan B hendak dibuat campuran C. Campuran C ini sekurang-kurangnya mengandung bahan-1
sebanyak 4 kg dan bahan-2 sebanyak 3 kg. Harga tiap kg campuran A adalah Rp. 20.000,00 dan tiap kg
campuran B adalah Rp.10.000,00. Berapakah campuran A dan B harus dibeli supaya biaya total pembuatan
campuran C semurah-murahnya dan berapa biaya yang harus dikeluarkan ?
Pemecahan:
1. Misalkan akan diproduksi meja sebanyak X1 unit dan akan diproduksi kursi sebanyak X2 unit.
a. Fungsi Tujuan : Memaksimalkan Z = $7 X1 + $5 X2
b. Fungsi Kendala:
Waktu pembuatan : 4 X1 + 3 X2 £ 240 jam/minggu
Waktu pengecatan : 2 X1 + X2 £ 100 jam/minggu
c. Syarat non negative : X1 ³ 0, X2 ³ 0
2. Misalkan akan diproduksi produk I sejumlah X unit dan akan diproduksi produk II sejumlah Y unit.
a. Fungsi tujuan : Memaksimalkan Z = Rp. 750 X + Rp. 425 Y
b. Fungsi Kendala :
X + Y £ 18 unit
X ³ 5 unit
Y ³ 3 unit
X + Y ³ 10 unit
c. Syarat Non Negatif : X ³ 0, Y ³ 0
Kamis, 14 Mei 2009
Pengertian RO
Riset operasi, atau disebut riset operasional di Eropa, adalah cabang interdisiplin dari matematika terapan dan sains formal yang menggunakan model-model—seperti model matematika, statistika, dan algoritma—untuk mendapatkan nilai optimal atau nyaris optimal pada sebuah masalah yang kompleks. Riset operasi biasanya digunakan untuk mencari nilai maksimal (profit, performa lini perakitan, hasil panen, bandwith dll) atau nilai minimal (kerugian, risiko, biaya, dll) dari sebuah fungsi objektif. Riset operasi bertujuan membantu manajemen mendapatkan tujuannya melalui proses ilmiah.
Minggu, 12 April 2009
metode simplex
http://e-learning.unram.ac.id/riset/pdf-doc/modul/Dokumen/Simplex.pdf
II. PROGRAM LINIER: METODE SIMPLEX
Persoalan program linier tidak selalu sederhana karena melibatkan banyak
constraint (pembatas) dan banyak variabel sehingga tidak mungkin
diselesaikan dengan metode grafik. Oleh karena itu serangkaian prosedur
matematik (aljabar linier) diperlukan untuk mencari solusi dari persoalan
yang rumit tersebut. Prosedur yang paling luas digunakan adalah Metode
Simplex. Penemuan metode ini merupakan lompatan besar dalam Riset Operasi
dan ia digunakan sebagai prosedur penyelesaian dari setiap program
komputer.
Bentuk Aljabar Metode Simplex
Dengan menggunakan contoh pada kasus perusahaan TAS terdahulu maka model
linier persoalan tersebut dapat dinyatakan sebagai berikut:
Max. Z = 3X1 + 2X2
Subject to
2X1 + 2X2 <= 800
2X1 + 3.3X2 <= 1000
1X1 + 0.5X2 <= 300
2X1 + 1.5X2 <= 650
Dengan menyertakan variabel Slack atau surplus maka model tersebut dibuat
menjadi bentuk standar berikut:
Max. Z = 3X1 + 2X2 + 0S1 + 0S2 + 0S3 + 0S4
Subject to constraint:
2X1 + 2X2 + 1S1 = 800 ... (1)
2X1 + 3.3X2 + 1S2 = 1000 ... (2)
1X1 + 0.5X2 + 1S3 = 300 ... (3)
2X1 + 1.5X2 + 1S4 = 650 ... (4)
X1,X2,S1,S2,S3,S4 ≥ 0
Properti Aljabar Metode Simplex
Keempat fungsi pembatas tersebut merupakan suatu persamaan sistem dengan
enam variabel. Jika suatu sistem persamaan memiliki veriabel yang lebih
banyak dibanding dengan jumlah persamaannya maka solusi dari persamaan
sistem tersebut adalah infinity. Metode simplex dengan demikian merupakan
prosedur aljabar untuk mendapatkan solusi terbaik bagi suatu sistem
persamaan. Dalam proses mencari solusi terbaik (best solution), solusi yang
tidak memenuhi persyaratan non negatif akan dieliminasi.
Mendapatkan Solusi dasar
Oleh karena jumlah variabel dalam persamaan sistem lebih besar dibanding
jumlah persamaaannya –-dalam hal ini ada enam variabel untuk empat
persamaan-- maka metode simplex memberikan nilai nol untuk dua variabel,
dan mencari solusi terbaik bagi empat variabel lainnya dalam sistem
persamaan tersebut. Misalkan X2 = 0 dan S1 = 0 sehingga persamaan sistem
tersebut menjadi:
2X1 = 800 ... (5)
2X1 + 1S2 = 1000 ... (6)
1X1 + 1S3 = 300 ... (7)
2X1 + 1S4 = 650 ... (8)
Dengan menetapkan nilai nol untuk variabel X2 dan S1 maka persamaan sistem
tersebut direduksi menjadi empat persamaan dengan empat variabel
(X1,S2,S3,S4).
Dari persamaan (5) diperoleh
2
2X1 = 800
sehingga X1 = 800/2 = 400.
Dari persamaan (6) masukkan nilai x1 = 400 untuk mendapatkan nilai S2 yaitu
2X1 + 1S2 = 1000
sehingga S2 = 1000 – (2*400) = 200
Dari persamaan (7) diperoleh
1X1 + 1S3 = 300
sehingga S3 = 300 – 400 = -100
Dari persamaan (8) diperoleh
2X1 + 1S4 = 650
sehingga diperoleh S4 = 650 – (2*400) = -150
Dengan demikian diperoleh solusi dari persamaan sistem dengan enam variabel
dan empat persamaan, yaitu:
X1 = 400
X2 = 0
S1 = 0
S2 = 200
S3 = -100
S4 = -150
Solusi diatas disebut Solusi dasar (Basic Solution).
Prosedur umum untuk mendapatkan basic solution adalah dengan membangun
bentuk persamaan standar untuk n variabel (termasuk variabel keputusan,
slack dan surplus) dan m persamaan pembatas dimana n lebih besar dari m.
Solusi Dasar
Untuk mendapatkan solusi dasar, tetapkan n-m variabel mana saja sebagai
variabel non basic dan beri nilai nol dan temukan solusi dari m
persamaan pembatas untuk m variabel lainnya.
Solusi fisibel dasar (Basic Feasible Solution)
Solusi dasar mungkin saja fisibel atau infisibel. Sebuah solusi dasar
fisibel akan memenuhi persyaratan tidak negatif. Solusi dasar yang
diperoleh diatas dengan menetapkan X2 dan S1 sebagai variabel bukan basis
dan bernilai sama dengan nol telah mendapatkan solusi untuk nilai
X1,S2,S3,S4 bukan sebagai solusi dasar fisibel karena nilai S3 = -100 dan
S4 = -150. Oleh karena itu pemilihan variabel bukan basis perlu diubah.
Jadi jika variabel yang dipilih sebagai variabel bukan basis adalah X1 dan
X2 dan bernilai nol maka solusi basis yang diperoleh adalah fisibel, yaitu:
S1 = 800
S2 = 1000
S3 = 300
S4 = 650
dengan variabel bukan basis X1 = 0 dan X2 = 0.
3
Daerah fisibel beserta titik-titik ekstrim dari persoalan perusahaan TAS
tersebut disajikan pada gambar berikut:
Pemeriksaan&Pengepakan
0 X1
X2
5
4
3
2
Pemotongan
Penjahitan
Penyelesaian
〇1 〇
〇
〇
〇
300
400
300 400 500
600
325
433
Prosedur penyelesaian program linear dengan Metode Simplex
1. Formulasikan persoalan menjadi model linear
2. Transformasikan model tersebut kedalam bentuk standar dengan
menambahan variabel slack atau mengurangi dengan variable surplus
3. Buatlah tableau form
Menyusun Tabel Simplex Awal (Initial Simplex Tableau)
Setelah melakukan konversi program linier kedalam tabel simplex maka tahap
pertama adalah membangun tabel simplex awal (initial simplex tableau). Pada
tahap ini termasuk pemberian notasi bagi semua koefisien yaitu:
cj = koefisien fungsi tujuan untuk variabel j
bi = koefisien sisi kanan (RHS) untuk constraint ke i
aij = koefisien yang berasosiasi dengan variabel j pada constraint i
Koefisien-koefisien ini merupakan bagian yang menyususn tabel simplex
seperti berikut:
C1 C2 ... Cn bi
a11 a12 ...a1n
a21 a22 ...a2n
. . ... .
. . ... .
. . ... .
am1 am2 ...amn
b1
b2
.
.
.
.
bm
Jadi tabel simplex awal untuk persoalan perusahaan TAS adalah
4
3 2 0 0 0 0
2 2 1 0 0 0 800
2 2.3 0 1 0 0 1000
1 0.5 0 0 1 0 300
2 1.5 0 0 0 1 650
Baris pertama tabel simplex awal tersebut menunjukkan koefisien dari
masing-masing variabel pada fungsi tujuan, sedangkan koefisien di bawahnya
dan di sebelah kiri garis vertikal merupakan koefisien dari masing-masing
variabel pada setiap constraint. Elemen di sebelah kanan garis vertikal
menunjukkan nilai dari sisi kanan dari constraint. Demi kemudahan, setiap
kategori koefisien diperlakukan sebagai suatu grup yang terdiri dari:
Baris C = baris dari koefisien fungsi tujuan
Kolom B = kolom dari nilai sisi kanan masing-masing constraint
Matrik A = marupakan matrik m x n dari koefisien masing-masing
variabel pada setiap constraint.
Baris C
Matrix
A
Kolom
B
Guna lebih memudahkan dalam mengingat masing-masing koefisien maka di
bagian paling atas tabel simplex dituliskan simbol masing-masing variabel
menjadi:
X1 X2 S1 S2 S3 S4
3 2 0 0 0 0
2 2 1 0 0 0 800
2 2.3 0 1 0 0 1000
1 0.5 0 0 1 0 300
2 1.5 0 0 0 1 650
Dari tabel simplex awal dapat diketahui dengan mudah solusi fisibel dasar
awal (initial basic feasible solution) karena untuk setiap kolom dari
variabel basis terdapat koefisien yang bernilai satu demikian juga untuk
setiap barisnya. Nilai dari variabel basis dengan demikian dinyatakan oleh
nilai sisi kanan yang berada pada kolom bi. Misalkan nilai S2 adalah 1000
X1 X2 S1 S2 S3 S4
3 2 0 0 0 0 bi
2 2 1 0 0 0 800
2 2.3 0 1 0 0 1000
1 0.5 0 0 1 0 300
2 1.5 0 0 0 1 650
Perbaikan Solusi
Guna meningkatkan solusi maka metode simplex harus menghasilkan solusi
fisibel dasar (basic feasible solution) yang baru (ekstreme point) yang
memberikan perbaikan pada nilai fungsi tujuan. Hal ini dilakukan dengan
mengganti salah satu variabel basis dengan variabel bukan basis, artinya
Nilai S2
Kolom Baris yang berasosiasi dengan variable S2 yang berasosiasi dengan variable S2
5
menetapkan variabel yang semula adalah bukan basis untuk menggantikan satu
variabel yang semula variabel basis. Metode simplex memberikan cara dan
prosedur untuk proses penggantian variabel ini.
Untuk lebih memudahkan proses maka ditambahkan dua kolom pada bagian kiri
tabel simplex awal, satu kolom diberi label Basis dan kolom lainnya diberi
label Cb. Pada kolom basis ditulis nama variabel basis sedangkan pada kolom
Cb ditulis nilai koefisien dari variabel basic tersebut seperti terdapat
pada fungsi tujuan.
Untuk kasus perusahaan TAS maka Tabel Simplex menjadi
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi S1 0 2 2 1 0 0 0 800
S2 0 2 2.3 0 1 0 0 1000
S3 0 1 0.5 0 0 1 0 300
S4 0 2 1.5 0 0 0 1 650
Untuk mengetahui apakah perbaikan solusi masih dapat dilakukan, maka
ditambahkan dua baris lagi pada bagian bawah tabel simplex ini. Baris yang
satu diberi label Zj yang menunjukkan perubahan pada nilai fungsi tujuan
jika satu unit variabel matrik A pada kolom j dimasukkan menjadi variabel
basis. Baris yang kedua diberi label Cj-Zj yang menyatakan pengaruh neto
dari pemasukan satu unit variabel tersebut pada nilai fungsi tujuan. Baris
ini disebut baris evaluasi netto (net evaluation row).
Berikut disajikan bagaimana elemen baris Zj disusun bila satu unit variabel
X1 menjadi variabel dasar sedangkan variabel X2 tetap sebagai bukan
variabel dasar yang bernilai nol. Dari persamaan pembatas (constraint)
pertama diketahui:
2X1 + 2X2 + 1S1 = 800
Variabel dasar saat ini adalah S1, dan jika X1 yang merupakan bukan
variabel dasar nilainya ditingkatkan satu unit dari 0 menjadi 1 maka nilai
S1 harus dikurangi 2 unit agar tetap memenuhi pembatas pertama tersebut.
Dari pembatas kedua dan seterusnya maka variabel S2 juga harus dikurangi 2
unit, variabel S3 berkurang 1 unit dan variabel S4 berkurang 2 unit.
Setelah dilakukan analisis untuk semua persamaan pembatas maka dapat
dikatakan koefisien pada kolom X1 menunjukkan jumlah unit dari variabel
dasar harus dikurangkan dengan masuknya variabel X1 menjadi variabel dasar
bernilai 1 untuk tetap menjaga terpenuhinya semua pembatas. Hal yang sama
dapat dilakukan untuk bukan variabel dasar lainnya seperti X2. Dengan
menetapkan X1 sebagai bukan variabel dasar benilai 0 maka untuk satu unit
penambahan nilai X2 dari 0 menjadi 1 maka variabel S1 harus dikurangi 2
unit, S2 berkurang 2.3 unit, S3 berkurang 0.5 unit dan S4 berkurang 1.5
unit supaya tetap memenuhi semua fungsi pembatas secara simultan.
Karena kolom Cb merupakan koefisien dari variabel dasar pada fungsi tujuan
maka untuk menghitung perubahan nilai fungsi tujuan (Zj) apabila nilai
variabel dasar Xj meningkat dari nol menjadi 1 adalah:
Z1 = 0(2)+ 0(2) + 0(1) + 0(2) = 0
Z2 = 0(2)+ 0(2.3)+ 0(0.5)+ 0(1.5) = 0
Z3 = 0(1)+ 0(0) + 0(0) + 0(0) = 0
Z4 = 0(0)+ 0(1) + 0(0) + 0(0) = 0
Z5 = 0(0)+ 0(0) + 0(1) + 0(0) = 0
Z6 = 0(0)+ 0(0) + 0(1) + 0(1) = 0
6
Karena nilai koefisien C1, C2, C3, C4, C5, C6 pada fungsi tujuan masingmasing
bernilai 3, 2, 0, 0, 0, 0 maka C1-Z1 = 3-0 = 3; C2-Z2 = 2-0 = 2 dan
seterusnya. Sampai dengan tahap ini maka tabel simplex menjadi:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi S1 0 2 2 1 0 0 0 800
S2 0 2 2.3 0 1 0 0 1000
S3 0 1 0.5 0 0 1 0 300
S4 0 2 1.5 0 0 0 1 650
Zj 0 0 0 0 0 0 0
Cj-Zj 3 2 0 0 0 0
Pada tabel tersebut juga diperoleh nilai Zj = 0 dengan cetak tebal pada
kolom terakhir yang merupakan perkalian antara kolom bi dengan koefisien
variabel basis-nya [0(800)+ 0(1000)+ 0(300)+ 0(650)] = 0
Dari baris evaluasi neto diketahui setiap produksi satu unit X1 (tas model
ransel) memberikan tambahan keuntungan Rp. 3 (dlm puluhan ribu) dan Rp. 2
(juga dlm puluhan ribu) untuk satu unit X2 pada nilai fungsi tujuan. Guna
memaksimumkan nilai fungsi tujuan maka variabel X1 dimasukan sebagai
variabel basic karena memiliki nilai positif terbesar dan menggantikan
salah satu variabel basic yang ada. Untuk menemukan variabel basic yang
harus diganti maka dicari variabel yang berasosiasi dengan constraint yang
paling membatasi nilai X1 (most restrictive). Dari contraint 1 diperoleh
nilai maksimum X1 adalah 400 karena untuk setiap tas model ransel
memerlukan 2 jam pengerjaan karena waktu yang tersedia adalah 800. Pada
constraint kedua X1 bernilai 500, constraint ketiga dan keempat
menghasilkan X1 masing-masing bernilai 300 dan 325. Dari analisis tersebut
terlihat bahwa constraint tiga paling membatasi sehingga nilai X1 tidak
boleh melebihi 300. Oleh karena itu variabel basic yang berasosiasi dengan
constraint ini yaitu variabel S3 menjadi variabel non basic.
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi bi/ai1
S1 0 2 2 1 0 0 0 800 (800/2=400)
S2 0 2 2.3 0 1 0 0 1000 (1000/2=500)
S3 0 1 0.5 0 0 1 0 300 (300/1=300)
S4 0 2 1.5 0 0 0 1 650 (650/2=325)
Zj 0 0 0 0 0 0 0
Cj-Zj 3 2 0 0 0 0
Untuk memperbaiki solusi awal X1=0, X2=0, S1=800, S2=1000, S3=300, dan
S4=650 yang menghasilkan keutungan pada nilai fungsi tujuan = 0 maka X1
ditingkatkan nilainya menjadi 300 sehingga keuntungan menjadi 3(300) = 900.
Dengan memproduksi 300 unit tas model ransel maka semua waktu kerja yang
tersedia pada bagian penyelesaian habis digunakan dan menyebabkan nilai S3
menjadi nol, sehingga X1 sekarang menjadi variabel basic menggantikan
variabel S3 yang sekarang menjadi non basic.
Elemen matrik yang merupakan perpotongan antara kolom X1 dengan baris S3
disebut elemen pivot (tanda kotak), sedangkan baris dan kolom yang
berasosiasi dengan elemen pivot disebut baris pivot dan kolom pivot.
Penyusunan Tabel Simplex berikutnya
7
Untuk menemukan basic solution yang baru maka perlu dilakukan perubahan
pada tabel simplex yang terakhir. Masuknya variabel X1 sebagai variabel
basic harus tetap menjaga pola seperti pola variabel S3 yang digantikannya
yang sekarang menjadi non basic. Matrik kolom X1 tetap dipertahankan
seperti pola seperti matrik unity S3 yaitu:
0
0
1
0
Prosedur transformasi tabel simplex sehingga tetap merupakan sistem
persamaan constraint yang ekuivalen adalah dengan mengikuti langkah Operasi
Baris Elementer (elementary row operation).
Operasi Baris Elementer
1. Kalikan setiap baris (persamaan) dengan bilangan bukan nol
2. Gantikan setiap baris (persamaan)dengan hasil penambahan atau
pengurangan berganda dari baris lainnya
Operasi baris elementer ini tidak merubah solusi dari sistem persamaan
simultan tetapi operasi ini akan merubah koefisien dari variabel dan nilai
sisi kanan constraint. Tujuan dari oprasi baris ini adalah untuk
mentransformasikan sistem persamaan constraint menjadi bentuk yang mudah
untuk mengidentifikasi solusi basic yang baru.
Kolom X1 pada tabel simplex menjadi:
a11 = 0
a21 = 0
a31 = 1
a41 = 0
Secara kebetulan elemen matrik a31 sudah bernilai 1 seperti tampak pada
persamaan constraint baris 3 berikut:
1X1 + 0.5X2 + 0S1 + 0S2 + 1S3 + 0S4 = 300
sehingga tidak diperlukan operasi baris elementer. Baris tersebut sekarang
menjadi baris pivot yang baru pada tabel simplex yang diperbaiki.
Untuk membuat elemen a11 = 0 maka operasi baris elementer yang dilakukan
adalah dengan mengalikan baris pivot tersebut dengan 2 sehingga menjadi:
2(1X1 + 0.5X2 + 0S1 + 0S2 + 1S3 + 0S4) = 2(300)
atau 2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4 = 600
Berikutnya adalah mengurangkan baris pertama dengan persamaan diatas
menjadi
(2X1 + 2X2 + 1S1)- (2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4) = 800 – 600
atau 0X1 + 1X2 + 1S1 – 0S2 -2S3 -0S4 = 200
Untuk membuat elemen a21 = 0 maka operasi yang harus dilakukan adalah
mengalikan baris pivot tersebut dengan 2 sehingga menjadi:
8
2(1X1 + 0.5X2 + 0S1 + 0S2 + 1S3 + 0S4) = 2(300)
atau 2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4 = 600
kemudian lakukan pengurangan terhadap persamaan baris kedua sehingga
(2X1 + 3.3X2 + 1S2) – (2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4) = 1000-600
atau 0X1 + 2.3X2 – 0S1 + 1S2 – 2S3 – 0S4 = 400
Untuk menghasilkan elemen a41 = 0 maka baris pivot juga kalikan 2 menjadi
2(1X1 + 0.5X2 + 0S1 + 0S2 + 1S3 + 0S4) = 2(300)
atau 2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4 = 600
kemudian lakukan pengurangan terhadap persamaan baris keempat sehingga
(2X1 + 1.5X2 + 1S4) – (2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4) = 650-600
atau 0X1 + 0.5X2 – 0S1 - 1S2 – 2S3 + 1S4 = 50
Karena pola matrik kolom X1 sudah ditransformasikan menjadi unity maka
bagian tabel simplex yang baru adalah sebagai berikut:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi
S1 0 0 1 1 0 -2 0 200
S2 0 0 2.3 0 1 -2 0 400
X1 3 1 0.5 0 0 1 0 300
S4 0 0 0.5 0 0 -2 1 50
Berikutnya adalah menghitung perubahan nilai Zj dan Cj-Zj untuk masingmasing
kolom termasuk nilai Zj pad kolom bi. Setelah menghitung nilai-nilai
tersebut dengan cara yang sama seperti pada tabel simplex awal maka
diperoleh tabel simplex iterasi pertama berikut:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi
S1 0 0 1 1 0 -2 0 200
S2 0 0 2.3 0 1 -2 0 400
X1 3 1 0.5 0 0 1 0 300
S4 0 0 0.5 0 0 -2 1 50
Zj 3 1.5 0 0 3 0 900
Cj-Zj 0 0.5 0 0 -3 0
Proses selanjutnya adalah terus mengusahakan perbaikan nilai fungsi tujuan
dengan memasukan variabel non basic menjadi variabel basic yang baru dengan
mengikuti prosedur seperti pada iterasi pertama. Dari evaluasi baris neto
diketahui variabel X2 memiliki nilai positif terbesar (0.5) sehingga ia
menjadi variabel basic yang baru, kolom X2 sekarang adalah sebagao kolom
pivot. Untuk menemukan baris pivot maka dicari nilai terkecil dari X2
dengan menghitung nilai Bi/ai2 (most restrictive X2). Hasilnya disajian
pada tabel berikut:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 Bi bi/ai2
9
S1 0 0 1 1 0 -2 0 200 (200/1=200)
S2 0 0 2.3 0 1 -2 0 400 (400/2.3=174)
X1 3 1 0.5 0 0 1 0 300 (300/0.5=600)
S4 0 0 0.5 0 0 -2 1 50 (50/0.5=100)
Zj 3 1.5 0 0 3 0 900
Cj-Zj 0 0.5 0 0 -3 0
Dari tabel tersebut diketahui constraint 4 paling restriktif sehingga
variabel S4 menjadi non basic karena bernilai nol karena semua jam kerja
yang ada pada bagaian ini digunakan untuk menghasilkan 100 unit X2 (tas
model klasik).
Operasi baris elementer harus dilakukan untuk membuat elemen metrik kolom
X2 menjadi unity dengan mempertahankan pola seperti S4, yaitu:
a12 = 0
a22 = 0
a32 = 0
a42 = 1
Untuk menjadikan elemen matrik a42 = 1 maka baris pivot harus dikalikan 2
menjadi 2(0X1 + 0.5X2 + 0S1 + 0S2 – 2S3 + 1S4) = 2(50)
atau 0X1 + 1X2 + 0S1 + 0S2 – 4S3 + 2S4 = 100
Persamaan tersebut sekarang menjadi baris pivot yang baru.
Untuk mendapatkan elemen matrik a12 = 0 maka operasi baris elementer
dilakukan dengan hanya mengurangkan baris pivot dari persamaan baris
pertama (variabel basic S1) karena koefisien X2 yang ada pada baris pertama
dengan yang ada pada baris pivot, yaitu sama-sama 1. Baris pertama yang
baru dengan demikian menjadi:
(0X1+1X2+1S1+0S2–2S3+0S4)-(0X1+1X2+0S1+0S2–4S3+2S4) = 200-100
atau 0X1 – 0X2 + 1S1 + 0S2 + 2S3 – 2S4 = 100
Untuk mendapatkan elemen matrik a22 = 0 maka operasi baris elementer
dilakukan dengan mengalikan baris pivot dengan 2.3 dan mengurangkan
hasilnya dari persamaan baris 2 (variabel basic S2), yaitu:
2.3(0X1 + 1X2 + 0S1 + 0S2 – 4S3 + 2S4) = 2.3(100)
atau 0X1 + 2.3X2 + 0S1 + 0S2 – 9.2S3 + 4.6S4 = 230
Setelah operasi pengurangan maka diperoleh hasil sebagai berikut:
(0X1+2.3X2+0S1+1S2-2S3+0S4)-(0X1+2.3X2+0S1+0S2–9.2S3+4.6S4) = 400-230
atau 0X1 + 0X2 + 0S1 + 1S2 + 7.2S3 -4.6S4 = 170
Untuk mendapatkan elemen matrik a32 = 0 maka operasi baris elementer
dilakukan dengan mengalikan baris pivot dengan 0.5 dan mengurangkan
hasilnya dari persamaan baris 3 (variabel basic X1), yaitu:
0.5(0X1 + 1X2 + 0S1 + 0S2 – 4S3 + 2S4) = 0.5(100)
atau 0X1 + 0.5X2 + 0S1 + 0S2 –2S3 + 1S4 = 50
Setelah operasi pengurangan maka diperoleh hasil sebagai berikut:
(1X1+0.5X2+0S1+0S2+1S3+0S4)-(0X1+0.5X2+0S1+0S2–2S3+1S4) = 300-50
atau 1X1 + 0X2 + 0S1 + 0S2 + 3S3 -1S4 = 250
10
Setelah mendapatkan semua persamaan constraint maka bagian tabel simplex
yang baru adalah
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 Bi
S1 0 0 0 1 0 2 -2 100
S2 0 0 0 0 1 7.2 -4.6 170
X1 3 1 0 0 0 3 -1 250
X2 2 0 1 0 0 -4 2 100
Berikutnya adalah menghitung perubahan nilai Zj dan Cj-Zj untuk masingmasing
kolom termasuk nilai Zj pad kolom bi. Setelah menghitung nilai-nilai
tersebut dengan cara yang sama seperti pada iterasi pertama maka diperoleh
tabel simplex iterasi kedua berikut:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 Bi
S1 0 0 0 1 0 2 -2 100
S2 0 0 0 0 1 7.2 -4.6 170
X1 3 1 0 0 0 3 -1 250
X2 2 0 1 0 0 -4 2 100
Zj 3 2 0 0 1 1 950
Cj-Zj 0 0 0 0 -1 -1
Interpretasi Solusi Optimal
Dari baris evaluasi neto tidak lagi ditemukan nilai positif yang berarti
solusi yang diperoleh sudah maksimum, yaitu X1 = 250, X2 = 100 dan nilai
fungsi tujuan Zj = 950 ( dalam puluhan ribu rupiah)
Dari tabel tersebut diketahui S1 = 100 dan S2 = 170 yang berarti waktu
kerja pada bagian pemotongan masih tersisa (slack) 100 jam sedangkan sisa
waktu pada bagian penjahitan adalah 170 jam. Pada bagian lainnya
(penyelesaian, pemeriksaan & pengepakan) seluruh waktu kerja sudah habis
digunakan.
Merujuk kembali pada gambar terdahulu diketahui bahwa solusi optimal
bergerak mulai dari titik ekstem 1 dengan solusi awal X1=0, X2=0, S1=800,
S2=1000, S3=300, S4=650 dan menghasilkan nilai fungsi tujuan nol. Pada
iterasi pertama variabel X1 memasuki basis dan mengakibatkan variabel S3
menjadi non basic variabel. Solusi basic kedua berada pada titik ekstem 2
yaitu X1=300, X2=0, S1=200, S2=400, S3=0, dan S4=50 serta menghasilkan
nilai 900 pada fungsi tujuan. Pada iterasi selanjutnya X2 memasuki basis
mendorong S4 untuk keluar. Hal ini menyebabkan solusi bergerak kearah sumbu
X2 menuju titik ekstem 3. Pada titik ini solusi yang didapat sudah optimum
yaitu X1=250, X2=100, S1=100, S2=170, S3=0 dan S4=0 sedangkan nilai fungsi
tujuan maksimum yaitu 950.
Ringkasan Prosedur Metode Simplex
1. Formulasikan persoalan kedalam model linear
2. Tambahkan variabel Slack pada masing-masing constraint (pembatas)
untuk memperoleh bentuk standar. Model ini digunakan untuk
11
identifikasi solusi feasible awal dari pembatas bertanda lebih kecil
atau sama dengan.
3. Buat tabel simplex awal (initial simplex tableau)
4. Pilih variabel non basic yang memiliki nilai positif terbesar pada
baris evaluasi neto menjadi variabel basic. Variabel ini menjadi
kolom pivot, yaitu kolom yang berasosiasi dengan variabel basic yang
masuk.
5. Pilih baris pivot yang memiliki ratio bi/aij terkecil dimana aij ≥ 0,
dimana j adalah kolom pivot. Hal ini sekaligus menunjukkan variabel
yang meninggalkan basis menjadi non basis.
6. Lakukan operasi baris elementer jika diperlukan untuk
mentransformasikan kolom dari variabel yang memasuki basis menjadi
kolom unitary yang bernilai 1 pada baris pivotnya.
a. Kalikan atau bagi setiap elemen baris pivot dengan pivot elemen
b. Hasilkan nilai 0 pada elemen kolom lainnya dengan cara
mengurangkan baris pivot dari baris-baris constraint lainnya
7. Lakukan pengujian tingkat optimaliti. Jika Cj-Zj ≤ 0 untuk semua
kolom maka solusi optimal sudah diperoleh, jika tidak maka ulangi
prosedur 4 kembali.
II. PROGRAM LINIER: METODE SIMPLEX
Persoalan program linier tidak selalu sederhana karena melibatkan banyak
constraint (pembatas) dan banyak variabel sehingga tidak mungkin
diselesaikan dengan metode grafik. Oleh karena itu serangkaian prosedur
matematik (aljabar linier) diperlukan untuk mencari solusi dari persoalan
yang rumit tersebut. Prosedur yang paling luas digunakan adalah Metode
Simplex. Penemuan metode ini merupakan lompatan besar dalam Riset Operasi
dan ia digunakan sebagai prosedur penyelesaian dari setiap program
komputer.
Bentuk Aljabar Metode Simplex
Dengan menggunakan contoh pada kasus perusahaan TAS terdahulu maka model
linier persoalan tersebut dapat dinyatakan sebagai berikut:
Max. Z = 3X1 + 2X2
Subject to
2X1 + 2X2 <= 800
2X1 + 3.3X2 <= 1000
1X1 + 0.5X2 <= 300
2X1 + 1.5X2 <= 650
Dengan menyertakan variabel Slack atau surplus maka model tersebut dibuat
menjadi bentuk standar berikut:
Max. Z = 3X1 + 2X2 + 0S1 + 0S2 + 0S3 + 0S4
Subject to constraint:
2X1 + 2X2 + 1S1 = 800 ... (1)
2X1 + 3.3X2 + 1S2 = 1000 ... (2)
1X1 + 0.5X2 + 1S3 = 300 ... (3)
2X1 + 1.5X2 + 1S4 = 650 ... (4)
X1,X2,S1,S2,S3,S4 ≥ 0
Properti Aljabar Metode Simplex
Keempat fungsi pembatas tersebut merupakan suatu persamaan sistem dengan
enam variabel. Jika suatu sistem persamaan memiliki veriabel yang lebih
banyak dibanding dengan jumlah persamaannya maka solusi dari persamaan
sistem tersebut adalah infinity. Metode simplex dengan demikian merupakan
prosedur aljabar untuk mendapatkan solusi terbaik bagi suatu sistem
persamaan. Dalam proses mencari solusi terbaik (best solution), solusi yang
tidak memenuhi persyaratan non negatif akan dieliminasi.
Mendapatkan Solusi dasar
Oleh karena jumlah variabel dalam persamaan sistem lebih besar dibanding
jumlah persamaaannya –-dalam hal ini ada enam variabel untuk empat
persamaan-- maka metode simplex memberikan nilai nol untuk dua variabel,
dan mencari solusi terbaik bagi empat variabel lainnya dalam sistem
persamaan tersebut. Misalkan X2 = 0 dan S1 = 0 sehingga persamaan sistem
tersebut menjadi:
2X1 = 800 ... (5)
2X1 + 1S2 = 1000 ... (6)
1X1 + 1S3 = 300 ... (7)
2X1 + 1S4 = 650 ... (8)
Dengan menetapkan nilai nol untuk variabel X2 dan S1 maka persamaan sistem
tersebut direduksi menjadi empat persamaan dengan empat variabel
(X1,S2,S3,S4).
Dari persamaan (5) diperoleh
2
2X1 = 800
sehingga X1 = 800/2 = 400.
Dari persamaan (6) masukkan nilai x1 = 400 untuk mendapatkan nilai S2 yaitu
2X1 + 1S2 = 1000
sehingga S2 = 1000 – (2*400) = 200
Dari persamaan (7) diperoleh
1X1 + 1S3 = 300
sehingga S3 = 300 – 400 = -100
Dari persamaan (8) diperoleh
2X1 + 1S4 = 650
sehingga diperoleh S4 = 650 – (2*400) = -150
Dengan demikian diperoleh solusi dari persamaan sistem dengan enam variabel
dan empat persamaan, yaitu:
X1 = 400
X2 = 0
S1 = 0
S2 = 200
S3 = -100
S4 = -150
Solusi diatas disebut Solusi dasar (Basic Solution).
Prosedur umum untuk mendapatkan basic solution adalah dengan membangun
bentuk persamaan standar untuk n variabel (termasuk variabel keputusan,
slack dan surplus) dan m persamaan pembatas dimana n lebih besar dari m.
Solusi Dasar
Untuk mendapatkan solusi dasar, tetapkan n-m variabel mana saja sebagai
variabel non basic dan beri nilai nol dan temukan solusi dari m
persamaan pembatas untuk m variabel lainnya.
Solusi fisibel dasar (Basic Feasible Solution)
Solusi dasar mungkin saja fisibel atau infisibel. Sebuah solusi dasar
fisibel akan memenuhi persyaratan tidak negatif. Solusi dasar yang
diperoleh diatas dengan menetapkan X2 dan S1 sebagai variabel bukan basis
dan bernilai sama dengan nol telah mendapatkan solusi untuk nilai
X1,S2,S3,S4 bukan sebagai solusi dasar fisibel karena nilai S3 = -100 dan
S4 = -150. Oleh karena itu pemilihan variabel bukan basis perlu diubah.
Jadi jika variabel yang dipilih sebagai variabel bukan basis adalah X1 dan
X2 dan bernilai nol maka solusi basis yang diperoleh adalah fisibel, yaitu:
S1 = 800
S2 = 1000
S3 = 300
S4 = 650
dengan variabel bukan basis X1 = 0 dan X2 = 0.
3
Daerah fisibel beserta titik-titik ekstrim dari persoalan perusahaan TAS
tersebut disajikan pada gambar berikut:
Pemeriksaan&Pengepakan
0 X1
X2
5
4
3
2
Pemotongan
Penjahitan
Penyelesaian
〇1 〇
〇
〇
〇
300
400
300 400 500
600
325
433
Prosedur penyelesaian program linear dengan Metode Simplex
1. Formulasikan persoalan menjadi model linear
2. Transformasikan model tersebut kedalam bentuk standar dengan
menambahan variabel slack atau mengurangi dengan variable surplus
3. Buatlah tableau form
Menyusun Tabel Simplex Awal (Initial Simplex Tableau)
Setelah melakukan konversi program linier kedalam tabel simplex maka tahap
pertama adalah membangun tabel simplex awal (initial simplex tableau). Pada
tahap ini termasuk pemberian notasi bagi semua koefisien yaitu:
cj = koefisien fungsi tujuan untuk variabel j
bi = koefisien sisi kanan (RHS) untuk constraint ke i
aij = koefisien yang berasosiasi dengan variabel j pada constraint i
Koefisien-koefisien ini merupakan bagian yang menyususn tabel simplex
seperti berikut:
C1 C2 ... Cn bi
a11 a12 ...a1n
a21 a22 ...a2n
. . ... .
. . ... .
. . ... .
am1 am2 ...amn
b1
b2
.
.
.
.
bm
Jadi tabel simplex awal untuk persoalan perusahaan TAS adalah
4
3 2 0 0 0 0
2 2 1 0 0 0 800
2 2.3 0 1 0 0 1000
1 0.5 0 0 1 0 300
2 1.5 0 0 0 1 650
Baris pertama tabel simplex awal tersebut menunjukkan koefisien dari
masing-masing variabel pada fungsi tujuan, sedangkan koefisien di bawahnya
dan di sebelah kiri garis vertikal merupakan koefisien dari masing-masing
variabel pada setiap constraint. Elemen di sebelah kanan garis vertikal
menunjukkan nilai dari sisi kanan dari constraint. Demi kemudahan, setiap
kategori koefisien diperlakukan sebagai suatu grup yang terdiri dari:
Baris C = baris dari koefisien fungsi tujuan
Kolom B = kolom dari nilai sisi kanan masing-masing constraint
Matrik A = marupakan matrik m x n dari koefisien masing-masing
variabel pada setiap constraint.
Baris C
Matrix
A
Kolom
B
Guna lebih memudahkan dalam mengingat masing-masing koefisien maka di
bagian paling atas tabel simplex dituliskan simbol masing-masing variabel
menjadi:
X1 X2 S1 S2 S3 S4
3 2 0 0 0 0
2 2 1 0 0 0 800
2 2.3 0 1 0 0 1000
1 0.5 0 0 1 0 300
2 1.5 0 0 0 1 650
Dari tabel simplex awal dapat diketahui dengan mudah solusi fisibel dasar
awal (initial basic feasible solution) karena untuk setiap kolom dari
variabel basis terdapat koefisien yang bernilai satu demikian juga untuk
setiap barisnya. Nilai dari variabel basis dengan demikian dinyatakan oleh
nilai sisi kanan yang berada pada kolom bi. Misalkan nilai S2 adalah 1000
X1 X2 S1 S2 S3 S4
3 2 0 0 0 0 bi
2 2 1 0 0 0 800
2 2.3 0 1 0 0 1000
1 0.5 0 0 1 0 300
2 1.5 0 0 0 1 650
Perbaikan Solusi
Guna meningkatkan solusi maka metode simplex harus menghasilkan solusi
fisibel dasar (basic feasible solution) yang baru (ekstreme point) yang
memberikan perbaikan pada nilai fungsi tujuan. Hal ini dilakukan dengan
mengganti salah satu variabel basis dengan variabel bukan basis, artinya
Nilai S2
Kolom Baris yang berasosiasi dengan variable S2 yang berasosiasi dengan variable S2
5
menetapkan variabel yang semula adalah bukan basis untuk menggantikan satu
variabel yang semula variabel basis. Metode simplex memberikan cara dan
prosedur untuk proses penggantian variabel ini.
Untuk lebih memudahkan proses maka ditambahkan dua kolom pada bagian kiri
tabel simplex awal, satu kolom diberi label Basis dan kolom lainnya diberi
label Cb. Pada kolom basis ditulis nama variabel basis sedangkan pada kolom
Cb ditulis nilai koefisien dari variabel basic tersebut seperti terdapat
pada fungsi tujuan.
Untuk kasus perusahaan TAS maka Tabel Simplex menjadi
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi S1 0 2 2 1 0 0 0 800
S2 0 2 2.3 0 1 0 0 1000
S3 0 1 0.5 0 0 1 0 300
S4 0 2 1.5 0 0 0 1 650
Untuk mengetahui apakah perbaikan solusi masih dapat dilakukan, maka
ditambahkan dua baris lagi pada bagian bawah tabel simplex ini. Baris yang
satu diberi label Zj yang menunjukkan perubahan pada nilai fungsi tujuan
jika satu unit variabel matrik A pada kolom j dimasukkan menjadi variabel
basis. Baris yang kedua diberi label Cj-Zj yang menyatakan pengaruh neto
dari pemasukan satu unit variabel tersebut pada nilai fungsi tujuan. Baris
ini disebut baris evaluasi netto (net evaluation row).
Berikut disajikan bagaimana elemen baris Zj disusun bila satu unit variabel
X1 menjadi variabel dasar sedangkan variabel X2 tetap sebagai bukan
variabel dasar yang bernilai nol. Dari persamaan pembatas (constraint)
pertama diketahui:
2X1 + 2X2 + 1S1 = 800
Variabel dasar saat ini adalah S1, dan jika X1 yang merupakan bukan
variabel dasar nilainya ditingkatkan satu unit dari 0 menjadi 1 maka nilai
S1 harus dikurangi 2 unit agar tetap memenuhi pembatas pertama tersebut.
Dari pembatas kedua dan seterusnya maka variabel S2 juga harus dikurangi 2
unit, variabel S3 berkurang 1 unit dan variabel S4 berkurang 2 unit.
Setelah dilakukan analisis untuk semua persamaan pembatas maka dapat
dikatakan koefisien pada kolom X1 menunjukkan jumlah unit dari variabel
dasar harus dikurangkan dengan masuknya variabel X1 menjadi variabel dasar
bernilai 1 untuk tetap menjaga terpenuhinya semua pembatas. Hal yang sama
dapat dilakukan untuk bukan variabel dasar lainnya seperti X2. Dengan
menetapkan X1 sebagai bukan variabel dasar benilai 0 maka untuk satu unit
penambahan nilai X2 dari 0 menjadi 1 maka variabel S1 harus dikurangi 2
unit, S2 berkurang 2.3 unit, S3 berkurang 0.5 unit dan S4 berkurang 1.5
unit supaya tetap memenuhi semua fungsi pembatas secara simultan.
Karena kolom Cb merupakan koefisien dari variabel dasar pada fungsi tujuan
maka untuk menghitung perubahan nilai fungsi tujuan (Zj) apabila nilai
variabel dasar Xj meningkat dari nol menjadi 1 adalah:
Z1 = 0(2)+ 0(2) + 0(1) + 0(2) = 0
Z2 = 0(2)+ 0(2.3)+ 0(0.5)+ 0(1.5) = 0
Z3 = 0(1)+ 0(0) + 0(0) + 0(0) = 0
Z4 = 0(0)+ 0(1) + 0(0) + 0(0) = 0
Z5 = 0(0)+ 0(0) + 0(1) + 0(0) = 0
Z6 = 0(0)+ 0(0) + 0(1) + 0(1) = 0
6
Karena nilai koefisien C1, C2, C3, C4, C5, C6 pada fungsi tujuan masingmasing
bernilai 3, 2, 0, 0, 0, 0 maka C1-Z1 = 3-0 = 3; C2-Z2 = 2-0 = 2 dan
seterusnya. Sampai dengan tahap ini maka tabel simplex menjadi:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi S1 0 2 2 1 0 0 0 800
S2 0 2 2.3 0 1 0 0 1000
S3 0 1 0.5 0 0 1 0 300
S4 0 2 1.5 0 0 0 1 650
Zj 0 0 0 0 0 0 0
Cj-Zj 3 2 0 0 0 0
Pada tabel tersebut juga diperoleh nilai Zj = 0 dengan cetak tebal pada
kolom terakhir yang merupakan perkalian antara kolom bi dengan koefisien
variabel basis-nya [0(800)+ 0(1000)+ 0(300)+ 0(650)] = 0
Dari baris evaluasi neto diketahui setiap produksi satu unit X1 (tas model
ransel) memberikan tambahan keuntungan Rp. 3 (dlm puluhan ribu) dan Rp. 2
(juga dlm puluhan ribu) untuk satu unit X2 pada nilai fungsi tujuan. Guna
memaksimumkan nilai fungsi tujuan maka variabel X1 dimasukan sebagai
variabel basic karena memiliki nilai positif terbesar dan menggantikan
salah satu variabel basic yang ada. Untuk menemukan variabel basic yang
harus diganti maka dicari variabel yang berasosiasi dengan constraint yang
paling membatasi nilai X1 (most restrictive). Dari contraint 1 diperoleh
nilai maksimum X1 adalah 400 karena untuk setiap tas model ransel
memerlukan 2 jam pengerjaan karena waktu yang tersedia adalah 800. Pada
constraint kedua X1 bernilai 500, constraint ketiga dan keempat
menghasilkan X1 masing-masing bernilai 300 dan 325. Dari analisis tersebut
terlihat bahwa constraint tiga paling membatasi sehingga nilai X1 tidak
boleh melebihi 300. Oleh karena itu variabel basic yang berasosiasi dengan
constraint ini yaitu variabel S3 menjadi variabel non basic.
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi bi/ai1
S1 0 2 2 1 0 0 0 800 (800/2=400)
S2 0 2 2.3 0 1 0 0 1000 (1000/2=500)
S3 0 1 0.5 0 0 1 0 300 (300/1=300)
S4 0 2 1.5 0 0 0 1 650 (650/2=325)
Zj 0 0 0 0 0 0 0
Cj-Zj 3 2 0 0 0 0
Untuk memperbaiki solusi awal X1=0, X2=0, S1=800, S2=1000, S3=300, dan
S4=650 yang menghasilkan keutungan pada nilai fungsi tujuan = 0 maka X1
ditingkatkan nilainya menjadi 300 sehingga keuntungan menjadi 3(300) = 900.
Dengan memproduksi 300 unit tas model ransel maka semua waktu kerja yang
tersedia pada bagian penyelesaian habis digunakan dan menyebabkan nilai S3
menjadi nol, sehingga X1 sekarang menjadi variabel basic menggantikan
variabel S3 yang sekarang menjadi non basic.
Elemen matrik yang merupakan perpotongan antara kolom X1 dengan baris S3
disebut elemen pivot (tanda kotak), sedangkan baris dan kolom yang
berasosiasi dengan elemen pivot disebut baris pivot dan kolom pivot.
Penyusunan Tabel Simplex berikutnya
7
Untuk menemukan basic solution yang baru maka perlu dilakukan perubahan
pada tabel simplex yang terakhir. Masuknya variabel X1 sebagai variabel
basic harus tetap menjaga pola seperti pola variabel S3 yang digantikannya
yang sekarang menjadi non basic. Matrik kolom X1 tetap dipertahankan
seperti pola seperti matrik unity S3 yaitu:
0
0
1
0
Prosedur transformasi tabel simplex sehingga tetap merupakan sistem
persamaan constraint yang ekuivalen adalah dengan mengikuti langkah Operasi
Baris Elementer (elementary row operation).
Operasi Baris Elementer
1. Kalikan setiap baris (persamaan) dengan bilangan bukan nol
2. Gantikan setiap baris (persamaan)dengan hasil penambahan atau
pengurangan berganda dari baris lainnya
Operasi baris elementer ini tidak merubah solusi dari sistem persamaan
simultan tetapi operasi ini akan merubah koefisien dari variabel dan nilai
sisi kanan constraint. Tujuan dari oprasi baris ini adalah untuk
mentransformasikan sistem persamaan constraint menjadi bentuk yang mudah
untuk mengidentifikasi solusi basic yang baru.
Kolom X1 pada tabel simplex menjadi:
a11 = 0
a21 = 0
a31 = 1
a41 = 0
Secara kebetulan elemen matrik a31 sudah bernilai 1 seperti tampak pada
persamaan constraint baris 3 berikut:
1X1 + 0.5X2 + 0S1 + 0S2 + 1S3 + 0S4 = 300
sehingga tidak diperlukan operasi baris elementer. Baris tersebut sekarang
menjadi baris pivot yang baru pada tabel simplex yang diperbaiki.
Untuk membuat elemen a11 = 0 maka operasi baris elementer yang dilakukan
adalah dengan mengalikan baris pivot tersebut dengan 2 sehingga menjadi:
2(1X1 + 0.5X2 + 0S1 + 0S2 + 1S3 + 0S4) = 2(300)
atau 2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4 = 600
Berikutnya adalah mengurangkan baris pertama dengan persamaan diatas
menjadi
(2X1 + 2X2 + 1S1)- (2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4) = 800 – 600
atau 0X1 + 1X2 + 1S1 – 0S2 -2S3 -0S4 = 200
Untuk membuat elemen a21 = 0 maka operasi yang harus dilakukan adalah
mengalikan baris pivot tersebut dengan 2 sehingga menjadi:
8
2(1X1 + 0.5X2 + 0S1 + 0S2 + 1S3 + 0S4) = 2(300)
atau 2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4 = 600
kemudian lakukan pengurangan terhadap persamaan baris kedua sehingga
(2X1 + 3.3X2 + 1S2) – (2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4) = 1000-600
atau 0X1 + 2.3X2 – 0S1 + 1S2 – 2S3 – 0S4 = 400
Untuk menghasilkan elemen a41 = 0 maka baris pivot juga kalikan 2 menjadi
2(1X1 + 0.5X2 + 0S1 + 0S2 + 1S3 + 0S4) = 2(300)
atau 2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4 = 600
kemudian lakukan pengurangan terhadap persamaan baris keempat sehingga
(2X1 + 1.5X2 + 1S4) – (2X1 + 1X2 + 0S1 + 0S2 + 2S3 + 0S4) = 650-600
atau 0X1 + 0.5X2 – 0S1 - 1S2 – 2S3 + 1S4 = 50
Karena pola matrik kolom X1 sudah ditransformasikan menjadi unity maka
bagian tabel simplex yang baru adalah sebagai berikut:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi
S1 0 0 1 1 0 -2 0 200
S2 0 0 2.3 0 1 -2 0 400
X1 3 1 0.5 0 0 1 0 300
S4 0 0 0.5 0 0 -2 1 50
Berikutnya adalah menghitung perubahan nilai Zj dan Cj-Zj untuk masingmasing
kolom termasuk nilai Zj pad kolom bi. Setelah menghitung nilai-nilai
tersebut dengan cara yang sama seperti pada tabel simplex awal maka
diperoleh tabel simplex iterasi pertama berikut:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 bi
S1 0 0 1 1 0 -2 0 200
S2 0 0 2.3 0 1 -2 0 400
X1 3 1 0.5 0 0 1 0 300
S4 0 0 0.5 0 0 -2 1 50
Zj 3 1.5 0 0 3 0 900
Cj-Zj 0 0.5 0 0 -3 0
Proses selanjutnya adalah terus mengusahakan perbaikan nilai fungsi tujuan
dengan memasukan variabel non basic menjadi variabel basic yang baru dengan
mengikuti prosedur seperti pada iterasi pertama. Dari evaluasi baris neto
diketahui variabel X2 memiliki nilai positif terbesar (0.5) sehingga ia
menjadi variabel basic yang baru, kolom X2 sekarang adalah sebagao kolom
pivot. Untuk menemukan baris pivot maka dicari nilai terkecil dari X2
dengan menghitung nilai Bi/ai2 (most restrictive X2). Hasilnya disajian
pada tabel berikut:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 Bi bi/ai2
9
S1 0 0 1 1 0 -2 0 200 (200/1=200)
S2 0 0 2.3 0 1 -2 0 400 (400/2.3=174)
X1 3 1 0.5 0 0 1 0 300 (300/0.5=600)
S4 0 0 0.5 0 0 -2 1 50 (50/0.5=100)
Zj 3 1.5 0 0 3 0 900
Cj-Zj 0 0.5 0 0 -3 0
Dari tabel tersebut diketahui constraint 4 paling restriktif sehingga
variabel S4 menjadi non basic karena bernilai nol karena semua jam kerja
yang ada pada bagaian ini digunakan untuk menghasilkan 100 unit X2 (tas
model klasik).
Operasi baris elementer harus dilakukan untuk membuat elemen metrik kolom
X2 menjadi unity dengan mempertahankan pola seperti S4, yaitu:
a12 = 0
a22 = 0
a32 = 0
a42 = 1
Untuk menjadikan elemen matrik a42 = 1 maka baris pivot harus dikalikan 2
menjadi 2(0X1 + 0.5X2 + 0S1 + 0S2 – 2S3 + 1S4) = 2(50)
atau 0X1 + 1X2 + 0S1 + 0S2 – 4S3 + 2S4 = 100
Persamaan tersebut sekarang menjadi baris pivot yang baru.
Untuk mendapatkan elemen matrik a12 = 0 maka operasi baris elementer
dilakukan dengan hanya mengurangkan baris pivot dari persamaan baris
pertama (variabel basic S1) karena koefisien X2 yang ada pada baris pertama
dengan yang ada pada baris pivot, yaitu sama-sama 1. Baris pertama yang
baru dengan demikian menjadi:
(0X1+1X2+1S1+0S2–2S3+0S4)-(0X1+1X2+0S1+0S2–4S3+2S4) = 200-100
atau 0X1 – 0X2 + 1S1 + 0S2 + 2S3 – 2S4 = 100
Untuk mendapatkan elemen matrik a22 = 0 maka operasi baris elementer
dilakukan dengan mengalikan baris pivot dengan 2.3 dan mengurangkan
hasilnya dari persamaan baris 2 (variabel basic S2), yaitu:
2.3(0X1 + 1X2 + 0S1 + 0S2 – 4S3 + 2S4) = 2.3(100)
atau 0X1 + 2.3X2 + 0S1 + 0S2 – 9.2S3 + 4.6S4 = 230
Setelah operasi pengurangan maka diperoleh hasil sebagai berikut:
(0X1+2.3X2+0S1+1S2-2S3+0S4)-(0X1+2.3X2+0S1+0S2–9.2S3+4.6S4) = 400-230
atau 0X1 + 0X2 + 0S1 + 1S2 + 7.2S3 -4.6S4 = 170
Untuk mendapatkan elemen matrik a32 = 0 maka operasi baris elementer
dilakukan dengan mengalikan baris pivot dengan 0.5 dan mengurangkan
hasilnya dari persamaan baris 3 (variabel basic X1), yaitu:
0.5(0X1 + 1X2 + 0S1 + 0S2 – 4S3 + 2S4) = 0.5(100)
atau 0X1 + 0.5X2 + 0S1 + 0S2 –2S3 + 1S4 = 50
Setelah operasi pengurangan maka diperoleh hasil sebagai berikut:
(1X1+0.5X2+0S1+0S2+1S3+0S4)-(0X1+0.5X2+0S1+0S2–2S3+1S4) = 300-50
atau 1X1 + 0X2 + 0S1 + 0S2 + 3S3 -1S4 = 250
10
Setelah mendapatkan semua persamaan constraint maka bagian tabel simplex
yang baru adalah
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 Bi
S1 0 0 0 1 0 2 -2 100
S2 0 0 0 0 1 7.2 -4.6 170
X1 3 1 0 0 0 3 -1 250
X2 2 0 1 0 0 -4 2 100
Berikutnya adalah menghitung perubahan nilai Zj dan Cj-Zj untuk masingmasing
kolom termasuk nilai Zj pad kolom bi. Setelah menghitung nilai-nilai
tersebut dengan cara yang sama seperti pada iterasi pertama maka diperoleh
tabel simplex iterasi kedua berikut:
X1 X2 S1 S2 S3 S4
Basis Cb 3 2 0 0 0 0 Bi
S1 0 0 0 1 0 2 -2 100
S2 0 0 0 0 1 7.2 -4.6 170
X1 3 1 0 0 0 3 -1 250
X2 2 0 1 0 0 -4 2 100
Zj 3 2 0 0 1 1 950
Cj-Zj 0 0 0 0 -1 -1
Interpretasi Solusi Optimal
Dari baris evaluasi neto tidak lagi ditemukan nilai positif yang berarti
solusi yang diperoleh sudah maksimum, yaitu X1 = 250, X2 = 100 dan nilai
fungsi tujuan Zj = 950 ( dalam puluhan ribu rupiah)
Dari tabel tersebut diketahui S1 = 100 dan S2 = 170 yang berarti waktu
kerja pada bagian pemotongan masih tersisa (slack) 100 jam sedangkan sisa
waktu pada bagian penjahitan adalah 170 jam. Pada bagian lainnya
(penyelesaian, pemeriksaan & pengepakan) seluruh waktu kerja sudah habis
digunakan.
Merujuk kembali pada gambar terdahulu diketahui bahwa solusi optimal
bergerak mulai dari titik ekstem 1 dengan solusi awal X1=0, X2=0, S1=800,
S2=1000, S3=300, S4=650 dan menghasilkan nilai fungsi tujuan nol. Pada
iterasi pertama variabel X1 memasuki basis dan mengakibatkan variabel S3
menjadi non basic variabel. Solusi basic kedua berada pada titik ekstem 2
yaitu X1=300, X2=0, S1=200, S2=400, S3=0, dan S4=50 serta menghasilkan
nilai 900 pada fungsi tujuan. Pada iterasi selanjutnya X2 memasuki basis
mendorong S4 untuk keluar. Hal ini menyebabkan solusi bergerak kearah sumbu
X2 menuju titik ekstem 3. Pada titik ini solusi yang didapat sudah optimum
yaitu X1=250, X2=100, S1=100, S2=170, S3=0 dan S4=0 sedangkan nilai fungsi
tujuan maksimum yaitu 950.
Ringkasan Prosedur Metode Simplex
1. Formulasikan persoalan kedalam model linear
2. Tambahkan variabel Slack pada masing-masing constraint (pembatas)
untuk memperoleh bentuk standar. Model ini digunakan untuk
11
identifikasi solusi feasible awal dari pembatas bertanda lebih kecil
atau sama dengan.
3. Buat tabel simplex awal (initial simplex tableau)
4. Pilih variabel non basic yang memiliki nilai positif terbesar pada
baris evaluasi neto menjadi variabel basic. Variabel ini menjadi
kolom pivot, yaitu kolom yang berasosiasi dengan variabel basic yang
masuk.
5. Pilih baris pivot yang memiliki ratio bi/aij terkecil dimana aij ≥ 0,
dimana j adalah kolom pivot. Hal ini sekaligus menunjukkan variabel
yang meninggalkan basis menjadi non basis.
6. Lakukan operasi baris elementer jika diperlukan untuk
mentransformasikan kolom dari variabel yang memasuki basis menjadi
kolom unitary yang bernilai 1 pada baris pivotnya.
a. Kalikan atau bagi setiap elemen baris pivot dengan pivot elemen
b. Hasilkan nilai 0 pada elemen kolom lainnya dengan cara
mengurangkan baris pivot dari baris-baris constraint lainnya
7. Lakukan pengujian tingkat optimaliti. Jika Cj-Zj ≤ 0 untuk semua
kolom maka solusi optimal sudah diperoleh, jika tidak maka ulangi
prosedur 4 kembali.
Selasa, 10 Februari 2009
Langganan:
Postingan (Atom)