Metode Simpleks Dalam Program Linear Kelompok I 4z11f

Meode Simpleks dalam Program Linear Metode Simpleks adalah metode yang dapat digunakan untuk menyelesaikan persoalan manajerial yang telah diformulasikan terlebih dahulu ke dalam persamaan matematika program linear yang mempunyai Variabel Keputusan mulai dari lebih besar atau sama dengan 2 (dua) sampai multivariabel. Apabila suatu masalah program linear hanya mengandung 2 (dua) kegiatan (atau variable variable keputusan) saja,maka akan dapa diselesaikan dengan metode grafik.Tetapi bila lebih dari dua kegiatan maka digunakan Metode Simplex. Bila variable keputusan yang dikandung tidak terlalu banyak masalah tersebut dapat diselesaikan dengan suatu algoritma yang biasanya sering disebut Metode Simplex table. langkah langkah metode simplex table adalah sebagai berikut :

langkah 1 : Merubah fungsi tujuan dan batasan fungsi tujuan dirubah menjadi fungsi implisit, artinya semua C jXij kita geser kekiri. Misalnya fungsi tujuan pada contoh didepan Z = 3X 1 + 5X2 dirubah menjadi Z – 3X1 -5X2 = 0. Pada bentuk standar , semua batasan mempunyai tanda ≤. Ketidaksamaan ini harus dirubah menjadi kesamaan, dengan cara menambah slack variable. Slack variable ini adalah xn+1 , xn+2 , . . . ,xn+m. Karena tingkat atau hasil kegiatan-kegiatan yang ada diwakili oleh x1 dan x2, maka variabel slack dimulai dari x3 , x4 dan seterusnya sebagai berikut : (1) 2x1 ≤ 8 menjadi 2x1 (2) 3x2 ≤ 15 menjadi (3) 6x1 + 5x2 ≤ 30 menjadi

3x2 6x1

+ x3 = 8 + x4 = 15 + 5x2 + x5 = 30

Berdasarkan perubahan persamaan-persamaan diatas dapat disusun formulasi yang dirubah yaitu sebagai berikut : Fungsi tujuan : maksimumkan

z – 3x1 – 5x2

Batasan-batasan : (1) 2x1 (2)

+ x3 3x2

=8

+ x4

(3) 6x1 + 5x2

= 15 + x5

= 30

Langkah 2 : menyusun persamaan-persamaan dalam tabel. setelah formulasi dirubah kemudian disusun kedalam tabel,dalam bentuk simbol seprti tampak pada tabel 3.1sedang untuk contoh di depan akan terlihat pada tabel 3.2.

Variabel dasar

Z

X1 X2……….Xn Xn+m

Xn+1

Z Xn+1 Xn+2 . . . Xn+m

1 0 0 . . . 0

-C1 -C2……….-Cn a11 a12……….a1n a21 a22……….a2n . . . . . . . . . . . . am1 am2……….amn 1

0 1 0 . .

Xn+2………… 0……………0 0……………0 1……………0 .

NK 0 b1 b2

. bm

. 0

. 0……………

NK adalah nilai kanan persamaan,yaitu nilai dibelakang tanda sama dengan (=). Untuk batasan 1 sebesar 8, batasan 2 sebesar 15, dan batasan 3 sebesar 30. Variabel dasar adalah variabel yang nilainya sama dengan sisi kanan dari persamaan. Pada persamaan 2X1 + X3 = 8,kalau belum ada kegiatan apa-apa, berarti nilai X 1 = 0, dan semua kapasitas masih mengangggur,maka pengangguran ada 8 satuan,atau nilai X3 = 8. Pada tabel tersebut nilai variabel dasar (X 3,X4,X5) pada fungsi tujuan pada tabel ini harus 0, dan nilainya pada batasan-batasan bertanda positif.

Variabel dasar Z X3 X4 X5

Z

X1

1 0 0 0

-3 2

X2

X3

X4

X5

NK

-5 0

0 1

0 0

0

0

3

0

1

0 8 15 30

6

5

0

0

0 0 1

Langkah 3 : memlih kolom kunci Kolom kunci adalah kolom yang menjadi dasar untuk merubah tabel. Pilihan kolom yang mempunyai nilai pada garis fungsi tujuan yang bernilai negatif dengan angka terbesar.

Langkah 4 : memilih baris kunci Baris kunci adalah baris yang merupakan dasar untuk mengubah tabel. Untuk itu terlebih dahulu carilah indeks tiap baris dengan cara membagi nilai nilai pada kolom NK dengan nilai yang sebaris dengan kolom kunci. index

¿

Nilai kolom NK Nilai kolom kunci

Langkah 5 : Merubah nilai-nilai baris kunci Nilai baris kunci dirubah dengan cara membaginya dengan angka kunci.

Langkah 6 : merubah nilai –nilai selain pada baris kunci Nilai-nilai baris yang lain ,selain pada baris kunci dapat dirubah dengan rumus sebagai berikut : Baris baru = baris lama – (koefisien pada kolom kunci) x nilai baru baris kunci.

Langkah 7 : melanjutkan perbaikan-perbaikan atau perubahan-perubahan Ulangilah langkah-langkah 3 sampai dengan langkah 6 untuk mempebaiki tabeltabel yang telah dirubah/ diperbaiki nilainya. Perubahan baru berhenti setelah pada pertama (fungsi tujuan) tidak ada yang bernilai negatif.

ESENSI METODE SIMPLEKS Metode simpleks adalah suatu prosedur aljabar, tetapi konsep yang mendasarinya adalah geometris. Pemahaman atas konsep geometris akan memberikan penjelesan mengenai bagaimana metode simpleks beroperasi dan apa yang membuat metode ini sangat efisien.

Penyelesaian Contoh Masalah Berikut ini adalah garis besar proses metode simpleks (dari sudut pandang geometris) dalam menyelesaikan permasalahan Wyndor Glass Co. Pada setiap langkah, kesimpulan dinyatakan terlebih dahulu dan kemudian alas an disampaikan dalam tanda kurung. Inisialisasi: Pilih (0,0) sebagai solusi F awal yang akan di uji.( Hal ini merupakan kesepakatan dalam memilih karena memang tidak diperlukan perhitungan untuk mengidentifikasisolusi F ini) Uji Optimalitas: Kesimpulan yang diambil adalah (0,0) bukan solusi yang optimal. (solusi F yang berseberangan merupakan solusi yang lebih baik). Itersi 1: Bergerak ke solusi F berseberangan yang lebih baik, yaitu (0,6), dengan mengikuti tiga langkah berikut: 1. Perhatikan dua tepi dari daerah solusi layak yang berasal dari titk (0,0), pilih untuk bergerak di sepanjang tepi yang menyebabkan nilai pada sumbu x 2 semakin membesar. (Dengan fungsi tujuan Z = 3x + 5x , menaikkan nilai x akan 1

2

2

meningkatkan nilai Z dengan lebih cepat bila dibandingkan dengan menaikkan nilai x1.

2. Berhenti pada kendala batas baru yang pertama: 2x 1 = 12 [bergerak lebih jauh sesuai dengan arah yang telah dipilih pada langkah pertama akan meninggalkan daerah solusi yang layak; misalnya bergerak ke kendala batas baru yang kedua akan melampaui batas solusi dan mencapai titik (0,9), yang merupakan solusi tak layak titik sudut.] 3. Selesaikan pada perpotongan batas kendala yang baru: (0,6). (Persamaan untuk batasan kendala ini, x1 = 0 dan 2x2 = 12, akan segera menghasilkan solusinya) Uji Optimalisasi: Kesimpulan yang diambil adalah (0,6) bukan merupakan solusi yang optimal.(Solusi Fyang berseberangan adalah lebih baik.) Iterasi 2: Bergerak ke solusi yang lebih baik, yaitu ke solusi F yang berseberangan. Penyelesaian tersebut adalah (2,6), dengan mengikuti tiga langkah berikut. 1. Dengan mempertimbangkan dua sisi dari daerah solusi layak berasal dari titik (0,6), pilih untuk bergerak di sepanjang sisi yang bergerak kea rah kanan. (Bergerak di sepanjang garis sisi ini akan meningkatkan nilai Z, sedangkan bila mundur akan bergerak turun sepanjang sumbu x 2 menurunkan nilai Z.) 2. Berhenti pada batasan kendala pertama yang ditemui selama bergerak di sepanjang sisi tersebu, 3x1 + 2x2 = 12 (bergerak lebih jauh ke arah yang dipilih pada langkah 1 akan meninggalkan daerah solusi yang layak). 3. Selesaikan pada perpotongan batasan kendala yang baru: (2,6). (Persamaan untuk batasan kendala ini, 3x1 + 2x2 = 18 dan 2x2 = 12.)

Uji Optimalitas: Kesimpulan yang diambil adalah (2,6) merupakan solusi yang optimal sehingga proses bias dihentikan.( Tidak ada solusi F berseberangan yang lebih baik.) Urutan pengujian solusi F di tunjukkan pada Gambar 4.2. Setiap angka yang diberi lingkaran menunjukkan nomor iterasi. Sekarang, mari kita amati konsep enam solusi kunci pada metode simpleks yang menjadi dasar pemikiran langkah-langkah diatas. Konsep Solusi Utama Konsep solusi pertama didasarkan pada relasi antara solusi yang optimal dan solusi F. Kosep solusi 1: Metode simpleks terfokus semata-mat pada solusi F. Untuk setiap persoalan yang sedikitnya memiliki satu solusi yang optimal, penyelesaiannya hanya memerlukan solusi F yang terbaik.

Oleh karena jumlah solusi layak pada umumnya tidak terbatas, pengurangan jumlah solusi yang harus diuji menjadi jumlah yang terbatas (hanya tiga solusi dalam Gambar 4.2) merupakan bentuk penyederhanaan yang luar biasa. Konsep solusi 2: Metode simpleks merupakan sebuah algoritma iterative (sebuah prosedur solusi sistematis yang melakukan perulangan pada serangkaian langkahlangkah, disebut iterasi, sampai hasil yang diinginkan diperoleh) dengan struktur sebagai berikut. Inisialisasi:

Tahap persiapan untuk memulai iterasi, termasuk menemukan nilai awal solusi F.

Pengujian Optimalisasi: Jika tidak

jika ya

apakah solusi F saat ini optimal? selesai Melakukan iterasi untuk menemukan solusi F yang lebih baik

Iterasi:

Konsep solusi 3: Bila memungkinkan, inisialisasi dalam metode simpleks menggunakan asal (origin) (semua variable keputusan sama dengan nol) sebagai solusi F awal. Memilih titik mula pada umumnya dimungkinkan ketika semua variable keputusan memiliki batasan nonnegative, karena perpotongan pada kendala-kendala ini menghasilkan titik mula sebagai solusi titik sudut. Solusi (titik ini) selanjutnya disebut solusi F,. Konsep solusi 4: Dengan adanya sebuah solusi F, perhitungan untuk mengmpulkan informasi tentang solusi F yang berseberangan akan lebih cepat dilakukan bila dibandingkan jika harus mencari informasi tentang solusi F yang lain. Dengan demikian, setiap kali metode simpleks melakukan iterasi untuk bergerak dari solusi F saat ini ke solusi F yang lebih baik. Kosep solusi 5: Setelah solusi F saat ini diidentifikasi, metode simpleks menguji setiap sisi daerah solusi layak yang berasal dari solusi F saat ini. Konsep solusi 6: Konsep solusi 5 menguraikan bagaimana metode simpleks menguji setiap sisi daerah solusi layak yang berasal dari solusi F saat ini. Pengujian sisi ini mempercepat identifikasi laju perbaikan terhadap Z yang akan diperoleh jika pergerakan dilakukan sepanjang sisi menuju titik solusi F yang

berseberangan pada ujung lain dari sisi ini. Laju perbaikan yang positif terhadap nilai Z menunjukkan bahwa solusi F yang berseberangan memilki penyelesaian yang lebih baik daripada solusi F saat ini. Adapun laju perbaikan yang negative terhadap nilai Z menunjukkan bahwa solusi F yang berseberangan lebih buruk daripada solusi F saat ini. Dengan demikan, uji optimalitas terdiri dari pengujian sederhana terhadap sisi yang memberikan laju perbaikan terhadap nilai Z yang positif. Jika tidak ditemukan maka solusi F saat ini merupakan solusi yang optimal.

4.2 SIFAT-SIFAT ALJABAR METODE SIMPLEKS Inisialisasi Pemilihan x1 dan x2 sebagai variable nonbasis (variable diberi nilai nol) untuk solusi BF awal didasarkan pada konsep solusi 3 di bagian 4.1. Pilihan ini menghilangkan pekerjaan yang diperlukan untuk menyelesaikan variabel-variabel basis (x 1,x2,x3) dari sistem persamaan berikut ini. Interpretasi geometris dan aljabar dari proses metode simpleks menyelesaikan persoalan Wyndor Glass Co Urutan Inisialisasi

Interpretasi Geometris Pilih (0,0) sebagai solusi F awal

Uji optimalitas

Belum optimal, karena bergerak sepanjang salah satu dari dua sisi yang dibentuk dari (0,0) dapat meningkatkan Z

Iterasi 1 Langkah 1

Langkah 2

Langkah 3

Bergerak ke atas searah dengan sumbu x2

Interpretasi secara aljabar Pilih x1 dan x2 sbg variable nonobasis (=0) Untuk solusi BF awal: (0, 4, 12, 18) Belum optimal, karena meningkatkan salah satu dari dua variable nonbasis (x1 dan x2) akan meningkatkan Z

Meningkatkan x2 dgn mengatur nilai variable yg lain untuk memenuhi sistem persamaan Berhenti ketika menemui batas Berhenti ketika variable basis yg kendala baru yg pertama (2x2 = pertama (x3, x4 atau x5) mencapai nilai 12) dicapai nol (x4) Temukan titik perpotongan Dengan x4 sbg variable basis saat ini antara pasangan batas kendala dan x4 sbg variable nonbasis, yg baru: (0,6) merupakan solusi selesaikan sistem persamaan yg ada: F yg baru (0, 6, 4, 0, 6) merupakan solusi BF yg baru

Pengujian optimalitas

Iterasi 2 Langkah 1

Langkah 2

Uji optimalitas

x1

Bergerak di sepanjang sisi ini ke kanan

Meningkatkan x1, dgn mengatur nilai variable yg lain untuk memenuhi sistem persamaan Berhenti ketika variable basis yg pertama (x2, x3, atau x5) mencapai titik nol (x5) Dengan x1 sekarang sbg variable basis dan x5 sbg variable nonbasis, selesaikan sisitem persamaan: (2, 6, 2, 0, 0) merupakan solusi BF yg baru (2, 6, 0, 0) merupakan penyelesaian yg optimal karena dengan menaikkan salah satu dari variable nonbasis (x4 atau x5) akan menurunkan nilai Z

x3

+ 2 x2

(2) (3)

Belum optimal, karena meningkatkan satu variable nonbasis (x1) akan meningkatkan Z

Berhenti ketika batasan kendala baru yg pertama (3x1 + 2x2 = 18) dicapai Temukan titik perpotongan pasangan batasan kendala yg baru: (2,6) merupakan solusi F yg baru (2,6) merupakan jawaban yg optimal, karena bergerak ke sisi yg berasal dari titik (2,6) akan menurunkan nilai Z

Langkah 3

(1)

Belum optimal, karena bergerak sepanjang sisi dari (0,6) ke kanan akan meningkatkan Z

3 x1

+

2 x2

=4 +

x4 +

x1 = 0 dan x2 sehingga = 12

x5

x3 = 4

= 18

x4 = 12 X5 = 18

Jadi, solusi BF awal adalah (0, 0, 4, 12, 18). Uji Optimalitas Fungsi tujuan adalah: Z = 3 x1 + 5 x2 Sehingga Z = 0 untuk solusi BF awal. Oleh karena tidak satu pun dari variable basis (x3, x4, x5) mempunyai suatu koefisien bukan nol (nonzero) di dalam fungsi tujuan ini, koefisien pada setiap variable nonbasis (x 1, x2) menunjukkan laju perbaikan pada nilai Z jika variable tersebut ditingkatkan nilainya dari nol (sementara nilai variable basis disesuaikan agar terus memenuhi sistem persamaan). Laju perbaikan ini (3 dan 5) adalah positif. Oleh karena itu, berdasarkan pada konsep solusi 6, disimpulkan bahwa (0, 0, 4, 12, 18) tidak optimal.

Untuk masing-masing solusi BF yang di uji setelah masing-masing iterasi, setidaknya satu variable basis memiliki koefisien bukan nol dalam fungsi tujuan. Oleh karena itu, uji optimalitas kemudian menggunakan Pers. (0) untuk menuliskan kembali fungsi tujuan dalam bentuk variable nonbasisnya saja seperti yang akan dibahas berikut.

Menentukan Arah Pergerakan (Langkah 1 Iterasi) Penambahan satu variable nonbasis dari nol sama saja dengan mengeluarkan tepi dari solusi F saat ini. Berdasarkan kosep solusi 4 dan 5 di bagian 4.1, pilihan atas variable nonbasis yang akan diaugmentasi adalah seperti berikut: Z = 3x1 + 5x2 Menambah x1? Laju perubahan Z = 3 Menambah x2 ? Laju perbaikan Z = 5 5 > 3 sehingga x2 adalah variable yang akan ditambahkan. Seperti di tunjukkan, kita menyebut x2 sebagai variable basis yang masuk untuk iterasi 1. Menentukan Saat Berhenti (Langkah 2 Iterasi) Peningkatan x2 juga meningkatkan nilai Z sehingga kita perlu melangkah sejauh mungkin tanpa meninggalkan daerah layk. Syarat untuk memenuhi kendala fungsional dalam bentuk tambahan di bawah ini memilki ari bahwa peningkatan x 2 (dengan tetap mempertahankan nilai variable nonbasis x 1 = 0) akan mengubah nilai beberapa variable basis seperti diperlihatkan di sebelah kanan. x1 (1)

x1

+ 2 x2

(2) (3)

3 x1

+

2 x2

x3

= 0 sehingga =4

+

x4 +

x3

= 12 x5

= 18

=4

x4

x = 12 −¿ 2 2

x4

= 18 −¿

2

x1

METODE SIMPLEKS DALAM BENTUK TABULAR Bentuk tabular metode simpleks hanya mencatat informasi penting, yaitu :

1. Koefisien variabel 2. Konstanta pada ruas kanan persamaan 3. Variabel basis yang muncul di setiap persamaan. Kita tak perlu lagi menulis symbol-simbol untuk variable-variabel dalam masingmasing persamaan. Akan tetapi, yang lebih penting lagi adalah kenyataan bahwa kita bisa menyorot angka-angka yang terlibat dalam perhitungan aritmetika dan mencatatnya secara ringkas. Pada table 4.3 membandingkan system persamaan awal untuk permasalahan Wyndor Glass co. dalam bentuk aljabar (di sebelah kiri) dan dalam bentuk tabular (di sebelah kanan), sementara table di sebelah kanan disebut tableau simpleks. Variabel basis untuk masing-masing persamaan ditunjukkan dengan huruf yang ditebalkan di sebelah kiri dan juga di kolom pertama tableau simpleks sebelah kanan. [Walaupun hanya variable-variabel xj yang berifat basis atau nonbasis, Z turut berperan sebagai variabel basis untuk persamaan (0).] Semua variabel yang tidak dicantumkan dalam kolom variabel basis (x1,x2) secara otomatis merupakan variabel nonbasis. Setelah kita tetapkan x 1= 0, x2= 0, kolom ruas kanan menyediakan solusi yang dihasilkan untuk variabel-variabel basis, sehingga solusi BF awal adalah (x1,x2,x3,x4,x5) = (0, 0, 4, 12, 18) yang menghasilkan Z=0. Bentuk tabular metode simpleks menggunakan tableau simpleks untuk menampilkan secara padat system persamaan yang menghasilkan solusi BF saat ini. Untuk solusi, masing-masing variabel dalam kolom paling kiri menyamakan angka yang sesuai dalam kolom paling kanan (dan variabel yang tidak dicantumkan dianggap bernilai nol). Saat uji optimalitas atau sebuah iterasi dilakukan, angkaangka yang relevan adalah angka-angka yang tertera pada ruas kolom kanan Z. istilah baris merujuk pada barisan angka yang terletak di sebelah kanan kolom Z (meliputi angka-angka pada ruas kanan), di mana baris I sama dengan persamaan i. Table 4.3 Sistem persamaan awal untuk permasalahan Wyndor Glass Co.

Ringkasan untuk Metode Simpleks (dan Iterasi 1 untuk Masalah Contoh) Inisialisasi. Masukkan variabel slack. Pilih variabel keputusan yang akan dijadikan variable-variabel nonbasis awal (samakan dengan nol) dan pilih variabel slack yang akan dijadikan variabel basis awal.

Untuk contoh masalah: Pemiihan tersebut akan menghasilkan table simpleks awal yang ditunjukkan pada kolom (b) Tabel 4.3, sehingga solusi BF awal adalah (0,0,4,12,18). Uji Optimals. Solusi BF saat ini akan optimal jika dan hanya jika setiap koefisien dalam baris nol adalah nonnegative (≥0). Jika memang demikian, berhenti: jika tidak, lakukan iterasi untuk mendapatkan solusi BF berikutnya, yang melibatkan perubahan satu variabel nonbasis menjadi satu variabel basis (langkah 1) dan sebaliknya langkah 2 dan kemudian menyelesaikannya untuk mendapatkan solusi baru (langkah 3). Iterasi. Langkah 1: Tentukan variabel basis yang masuk dengan memilih variabel (secara otomatis variabel nonbasis) dengan koefisien negative yang memiliki nilai absolute terbesar (yaitu koefisien yang “paling negatif”) dalam persamaan (0). Letakkan sebuah kotak di sekeliling kolom di bawah koefisien ini. Kolom itu disebut kolom sumbu (pivot coloumn). Untuk Contoh Masalah: Koefisien yang paling negatif adalah -5 untuk x 2 (5 > 3) sehingga x2 berubah menjadi variabel basis. (Perubahan ini ditunjukkan dalam Tabel 4.4 dalam kotak yang mengelilingi kolom x 2 di bawah -5). Langkah 2: Tentukan variabel minimum.

basis yang keluar dengan menerapkan uji rasio

TABEL 4.4 Penerapan uji rasio minimum untuk menentukan variabel bebas yang keluar pertama kali untuk permasalahan Wyndor Glass Co.

Langkah 3: Selesaikan dan carilah BF baru dengan menggunakan operasi baris dasar (mengalikan atau membagi sebuah baris dengan konstanta bukan nol; menambahkan atau mengurangkan hasil perkalian sebuah baris terhadap baris lainnya) untuk membentuk tabel simpleks yang baru dalam bentuk yang tepat dari eliminasi Gaussian di bawah yang saat ini. Kemudian ke uji optimals. Operasi baris dasar khusus yang perlu dilakukan dicantumkan di bawah ini. Iterasi 2 Untuk Contoh Masalah dan Solusi Optimal yang Dihasilkan Iterasi kedua dimulai dari tabel kedua Tabel 4.6 untuk menemukan solusi BF berikutnya. Dengan mengikuti petunjuk untuk langkah 1 dan 2, kita dapati bahwa x 5 merupakan variabel basis yang keluar, seperti diperlihatkan pada Tabel 4.7.

Untuk langkah 3, kita mulai dengan membagi baris sumbu (baris 3) dalam Tabel 4.7 dengan angka sumbu (3). Selanjutnya kita tambahkan pada baris 0 hasil perkalian baris 3 yang baru dengan 3. Kemudian, kita kurangkan baris 1 dengan baris 3 yang baru. Dengan begitu, sekarang kita memiliki serangkaian tableau seperti diperlihatkan pada Tabel 4.8. oleh karena itu, solusi BF yang baru adalah (2,6,2,0,0) dengan Z = 36. Beranjak ke uji optimalitas, kita dapati bahwa solusi ini optimal karena tak satu pun koefisien dalam baris 0 yang bernilai negatif, sehingga algoritma ini selesai. Akibatnya, solusi optimal untuk Wyndor Glass Co. (sebelum variabel slack dikenali) adalah x1 = 2, x2 = 6. TABEL 4.5 Tableau simpleks untuk masalah Wyndor Glass Co., setelah baris sumbu pertama dibagi dengan angka sumbu pertama. TABEL 4.6 Kedua tableau simpleks pertama untuk masalah Wyndor Glass Co.

TABEL 4.7 Langkah 1 dan 2 Iterasi 2 untuk masalah Wyndor Glass Co.

TABEL 4.8 Rangkaian utuh tableau simpleks untuk masalah Wyndor Glass Co.

PEMUTUSAN PERTALIAN DALAM METODE SIMPLEKS Pertalian pada variabel basis yang Masuk Langkah 1 pada masing-masing iterasi menjadikan variabel nonbasis yang memiliki koefisien negatif dengan nilai absolut terbesar dalam persamaan (0)0 sebagai variabel basis yang masuk. Maka sekarang anggaplah terdapat dua atau lebih variabel nonbasis yang terkait karena memiliki koefisien negative terbesar (dalam artian absolut). Contohnya, hal ini akan terjadi dalam iterasi pertama untuk permasalahn Wyndor Glass Co. jika fungsi tujuannya diubah menjadi Z = 3x 1 + 3x2 sehingga persamaan (0) awal menjadi Z - 3x 1 - 3x2 = 0. Kemudian muncul pertanyaan bagaimana seharusnya memutuskan pertalian tersebut ?

Jawabannya adalah memilih salah satu yang mungkin dilakukan secara sembarang (arbiter).

4.6 Kendala Persamaan Kendala persamaan apa pun ai 1 x 1 +a i2 x 2+ …+a¿ x n=bi sebenarnya ekuivalen dengan sepasang kendala pertidaksamaan: ai 1 x 1 +a i2 x 2+ …+a¿ x n ≤b i ai 1 x 1 +a i2 x 2+…+a¿ x n ≥b i ' Contoh: Maksimumkan

Z =3 x 1 +5 x 2

.

Penyelesaian:  

Fungsi tujuan Z =3 x 1 +5 x 2 diubah menjadi

Z −3 x 1−5 x 2=0 .

Fungsi kendala diubah menjadi variabel slack. Variabel slack adalah variabel tambahan yang mewakili atau kapasitas yang merupakan batas. Sistem persamaan untuk bentuk tambahan permasalahan menjadi x ≤8 x x3 i 2 1 menjadi 2 1 + ii

3

x 2 ≤ 15

iii

6

x 1+5 x 2 ≤ 30

menjadi menjadi

3 6



Fungsi tujuan: maksimumkan Z = 3



Fungsi kendala: x ≤8 (i) 2 1

x2

x 1+5 x 2 x1

+5

x2

=8

+

x4

= 15

+

x5

= 30

(ii)

3

x 2 ≤ 15

(iii)

6

x 1+5 x 2 ≤ 30

Untuk (i) 2

x1 ≤ 8 x1 ≤ 4

jadi



x 1=4

Untuk (ii) 3

x 2 ≤ 15 x2 ≤ 5

jadi



x 2=5

Untuk (iii) 6

x 1+5 x 2 ≤ 30

misalkan 6 x 1 ≤ 30

x 2=0 x1 ≤ 5

jadi koordinat (5,0)

misalkan

x 1=0

5 x2 ≤30

x2 ≤ 6

jadi koordinat (6,0)



x1 ≥ 0



x2 ≥ 0

x1

Persamaan 2 x 1 ≤8 3

x 2 ≤ 15

6

x 1+5 x 2

x2

x 1=4 x 2=5 (5,0)

x1 ≥ 0

(6,0)

(0,0)

x1 ≥ 0

(0,0)

Ruas Kanan Negatif Untuk menyelesaikan kendala persamaan dengan ruas kanan negatif, (yaitu mengalikan kedua sisi dengan -1) juga bisa digunakan untuk sembarang kendala pertidaksamaan dengan ruas kanan negatif. Perkalian kedua sisi sebuah pertidaksamaan dengan -1 juga membalikkan arah pertidaksamaan; yaitu, ≤ berubah menjadi

≥ , atau sebaliknya.

Kendala Fungsional dalam Bentuk

≥

Akan ditunjukkan bagaimana metode simpleks menyelesaikan masalah ini dengan cara menyelesaikan masalah artifisial yang ada secara langsung. Namun, pertama-tama kita harus mendeskripsikan bagaimana cara menangani kendala ketiga. Pendekatan kita memerlukan adanya variabel surplus

x5

(didefinisikan

x 5=6 x 1+5 x 2−30

) dan sebuah variabel artifisial

x6

, seperti

diperlihatkan di bawah ini. 6

Di sini

x 1+5 x 2 ≤ 30 → 6 x 1+5 x 2−x 5=30

(

x5 ≥ 0 ¿

→ 6 x 1+5 x 2−x 5 + x 6=30

(

x 5 ≥ 0, x 6 ≥ 0 ¿

x5

disebut variabel surplus karena ia mengurangkan ruas kanan pada ruas

kiri untuk mengubah kendala pertidaksamaan menjadi kendala persamaan yang ekuivalen.

Minimalisasi Sebuah cara tepat untuk meminimalkan Z dengan metode simpleks adalah dengan menukar peran koefisien positif dan negatif dalam baris nol untuk uji optimalis maupun lanhgkah 1 iterasi. n

Meminimalkan

Z =∑ c j x j j =1

ekuivalen dengan n

(−c j ) x j ; memaksimalkan Z =∑ j =1 sehingga, kedua perumusan tersebut menghasilkan solusi optimal yang sama. Kedua rumusan tersebut ekuivalen karena semakin kecil nilai Z maka semakin besar nilai –Z. akan dilakukan perubahan berikut dalam perumusan: Minimalkan

Z =3 x 1 +5 x 2

→ maksimalkan - Z =−3 x 1−5 x 2