BAB I

PENDAHULUAN

A. Latar Belakang

Salah satu pendekatan yang dapat dilakukan untuk menyelesaikan masalah

manajemen sains adalah pemrograman linear. Pemrograman linear merupakan

kelompok teknik analisis kuantitatif yang mengandalkan model matematika atau

model simbolik sebagai wadahnya. Artinya, setiap masalah yang kita hadapi dalam

suatu sistem permasalahan tertentu perlu dirumuskan dulu dalam simbol-simbol

matematika tertentu, jika kita inginkan bantuan pemrograman linear sebagai alat

analisisnya.

Metode grafik merupakan salah satu metode yang dapat digunakan untuk

menyelesaikan masalah pemrograman linear yang melibatkan dua peubah keputusan.

Membahas mengenai masalah meminimumkan fungsi kendala bertanda ≥, fungsi

kendala bertanda = tidak ada penyelesaian layak, tidak ada penyelesaian optimal,

beberapa alternatif optimal, dan wilayah kelayakan yang tidak terikat dapat terjadi

saat menyelesaikan masalah pemrograman linear dengan menggunakan prosedur

penyelesaian grafik. Kasus-kasus ini juga dapat terjadi saat menggunakan metode

simpleks.

Metode simplek untuk linier programming dikembangkan pertama kali oleh

George Dantzing pada tahun 1947, kemudian digunakan juga pada penugasan di

Angkatan Udara Amerika Serikat. Dia mendemonstrasikan bagaimana menggunakan

fungsi tujuan (iso-profit) dalam upaya menemukan solosi diantara beberapa

kemungkinan solosi sebuah persoalan linier programming.

Proses penyelesaiaanya dalam metode simplek, dilakukan secara berulang-

ulang (iterative) sedemikian rupa dengan menggunakan pola tertentu (standart)

sehingga solusi optimal tercapai.

Ciri lain dari metode simplek adalah bahwa setiap solusi yang baru akan

menghasilkan sebuah nilai fungsi tujuan yang lebih besar daripada solosi sebelumnya.

1

B. Rumusan Masalah

Adapun rumusan masalah yang akan dibahas dalam makalah ini adalah sebagai

berikut:

1. Bagaimana cara mencari nilai maksimum dengan menggunakan metode

simpleks?

2. Bagaimana cara menyelesaikan masalah/kendala (syarat) bertanda “=”?

3. Bagaimana cara mencari nilai minimum dengan menggunakan metode

simpleks?

C. Tujuan

Adapun tujuan dari penulisan makalah ini antara lain :

1. Dapat menyelesaikan masalah maksimasi dalam program linear

2. Dapat menyelesaikan masalah / kendala (syarat) bertanda “=” pada program

linear

3. Dapat menyelesaikan masalah minimasi dalam program linear

2

BAB II

PEMBAHASAN

2.1 MENGUBAH SISTEM PERTIDAKSAMAAN MENJADI SISTEM PERSAMAAN

Suatu masalah program linier terdiri dari fungsi tujuan yang berbentuk linier yang berisikan

sejumlah variabel dan suatu sistem pertidaksamaan linier yang merupakan fungsi pembatas

(constraints). Berdasarkan data dari fungsi pembatas ini diusahakan untuk menemukan nilai

optimum (maksimum atau minimum) dari fungsi tujuan.

Perhatikan persoalan program linier berikut :

(1) Fungsi tujuan

(2) Fungsi pembatas

(3) Akan ditentukan nilai x1 dan x2 yang mengakibatkan nilai f mencapai maksimum.

Untuk dapat menyelesaikan persoalan ini dengan cara simpleks, sistem persamaan dari fungsi

pembatas perlu diubah (dikonversikan) menjadi sistem persamaan dengan bantuan substitusi

ata penambahan variabel baru. Kepada setiap pertidaksamaan ditambahkan variabel baru.

Dengan demikian fungsi pembatas:

Dapat dinyatakan menjadi

Variabel baru ini ditambahkan ke ruas terkecil dari pertidaksamaan.variabel tersebut

dinamakan variabel yang ditambahkan atau variabel slack yaitu variabel dengan nilai non

negatif yang ditambahkan pada ruas terkecil dari pertidaksamaan.

Kadang – kadang variabel slack ini dinyatakan dengan S1, S2, S3 dan seterusnya.

3

Dengan masuknya variabel slack ini maka fungsi tujuan juga harus disusaikan yaitu dengan

menambahkan semua variabel slack ini tetapi dengan koefisien nol. Sehingga fungsi tujuan

menjadi

Setelah konversi ini dilakukan maka persoalan di atas menjadi :

Fungsi tujuan :

Pembatas

non – negatif

Apabila ada pertidaksamaan dalam pembatas yang bertanda “ ” maka variabel slack harus

ditambahkan ke ruas kanan karena ruas kanan yang terkecil. Perhatikan sistem

pertidaksamaan berikut :

Dengan menambahkan variabel slack x4, x5, x6 pada pertidaksamaan yang bersesuaian maka

sistem itu menjadi :

Persamaan terakhir ini diubah menjadi x1 x2 5x3 x6 15 sehingga secara penulisan

lengkap sistem persamaan ini menjadi :

Dalam hal ini x6 disebut variabel slack surplus. Perlu dicatat bahwa semua variabel, baik

variabel aslinya maupun variabel slack bernilai non negatif.

4

2.2 LANGKAH LANGKAH DAN KRITERIA

Untuk menjelaskan langkah langkah dan kriteria dalam penyelesaian masalah program

linier, akan dikemukakan satu masalah :

Sebuah pabrik memproduksi tiga macam barang, tipe A, B dan C yang masing masing

diproses melalui tiga tahap yaitu memotong, melipat dan mengepak. Bagian pemotongan

menyediakan 2705 jam, bagian melipat 2210 jam dan bagian pengepakan 455 jam untuk

periode dan waktu tertentu. Pembuatan 1 unit barang tipe A memerlukan 10,7 jam

memotong, 5,4 jam melipat dan 0,7 jam mengepak. Pembuatan unit 1 unit barang tipe B

memerlukan 5,0 jam memotong, 10,0 jam melipat dan 1,0 jam mengepak. Pembuatan unit 1

unit barang tipe C memerlukan 2,0 jam memotong, 4,0 jam melipat dan 2,0 jam mengepak.

Keungungan penjualan per unit barang tipe A, B dan C berturut turut $10, $15 dan $20.

Kita harus menentukan kombinasi barang tipe A, B dan C dalam produksi agar diperoleh

keuntungan maksimum. Untuk memudahkan penyusunan model matematika persoalan di atas

perlu dibuat tabel data berikut :

BagianTipe Barang Kapasitas per

periode waktuA B C

Memotong 10,7 5,0 2,0 2705

Melipat 5,4 10,0 4,0 2210

Mengepak 0,7 1,0 2,0 445

Keuntungan per unit $ 10 $ 15 $ 20

Misalkan produksi x1 unit untuk model A, sejumlah x2 unit model B dan x3 unit model C.

Berdasarkan data diatas maka model matematika untuk program linier ini ialah :

Maksimumkan

Syarat

5

Dengan menggunakan variabel slack x4, x5, x6 maka setelah ruas kanan dari fungsi objektif

dipindahkan ke ruas kiri, sistem itu berubah menjadi :

....... baris 0

...... baris 1

(1) ...... baris 2

...... baris 3

Dimana semua variabel adalah non negatif.

Sebelum perhitungan dilanjutkan, langkah langkah yang perlu diikuti agar mencapai hasil

akhir ialah :

Langkah 1 : Pilih sejumlah m variabel yang menghasilkan solusi fisibel awal (m

menyatakan benyaknya hubungan linier dalam masalah).

Langkah 2 : Periksalah fungsi objektif untuk mengetahui apakah ada variabel yang bernilai

nol pada solusi awal (jadi variabel non basis) yang dapat memperbaiki fungsi

objektif jika variabel itu diberi nilai positif. Jika variabel dengan sifat ini

ditemukan, lanjutkan ke langkah ke 3. Apabila tidak ada, pekerjaan dihentikan.

Langkah 3 : Tentukan berapa besar variabel pada langkah 2 dapat diberikan, sementara satu

di antara m variabel dalam solusi awal menjadi nol. Lenyapkanlah variabel

terakhir ini yang mengakibatkan munculnya variabel pada langkah 2 sebagai

penggantinya.

Langkah 4 : Hitunglah nilai dari m variabel ini dan membiarkan variabel sisanya bernilai

nol.

Langkah langkah ini akan digunakan untuk menyelesaikan masalah diatas,

Langkah pertama adalah menentukan solusi fisibel awal dari sistem (1). Terdapat banyak

solusi, tetapi tentu solusi yang lebih sesuai dimulai dengan f 0, x4 2705, x5 2210 dan x6

445, sementara semua variabel lainnya sama dengan nol. Dengan kata lain, dimulai

dengan semua variabel slack diikut sertakan dalam solusi. Solusi ini disebut solusi awal,

sedang f, x4, x5, x6 disebut variabel basis (disingkatn : non basis ), variabel lainnya x1, x2

6

dan x3 disebut variabel non luas x1 , x2 dan x3 disebut variabel non basis (disingkat : non

basis). Jika f diinterpretasikan sebagai keuntungan, maka solusi ini sangat tidak

menguntungkan karena nilainya sama dengan nol. Perhatikan koefisien x1, x2 dan x3pada

baris 0 (baris fungsi obektif ) tiap koefisien negatid ini menunjukkan berapa besar f

bertambah besar jika variabel yang bersangkutan diberi nilai 1.

Interpretasi koesisien - koefisien pada baris nol.tiap koefisien ini menyatakan berapa besar

kenaikan (jika koefisien negatif) atau pengurangan (jika koefisien positif) dapat f akibat

penambahan satu unit variabel non basis.

Langkah kedua adalah menetapkan variabel yang akan masuk kedalam program agar

menaikkan nilai f.

KRITERIA I (Untuk maksimasi).jika ada variabel non basis dengan koefisien negatif pada

abris O, pilihlah variabel yang paling negatif, yaitu variabel yang memberi keuntungan

terbesar, sebutlah variabel xj. Jika semua variabel non baris pada baris O memiliki koefisien

positif atau nol, maka solusi optimal telah tercapai.

Sehubungan dengan kriteria I ini maka terpilih x3 untuk menjadi basis. Tiap unit x3 akan

menambah keuntungan f sebesar 20, yang merupakan keuntungan terbesar dibandingkan

dengan keuntungan yang diberikan oleh variabel lainnya.

Periksalah tiap pembatas. Perhatikan bahwa jika x3 dinaikkan maka setiap variabel

yang sedang berlangsung harus dikurangi untuk tetap mempertahankan stabilitas persamaan

pada kendala. Khususnya, jika x3 dinaikkan sebesar 1 satuan makan untuk menjaga stabilitas

persamaan pada tiap kendala :

(i) x4 harus dikurangi sebesar 2,0 satuan

(ii) x5 harus dikurangi sebesar 4,0 satuan

(iii) x6 harus dikurangi sebesar 2,0 satuan

berapa besar x3 dimasukkan, sehingga variabel basis mencapai batas bahwa ( )?

Perhatikan bahwa pada saat x6 0 maka x3 222,5. Di sini, memasukkan x3 sebagai

basis akan melenyapkan x6 dari basis.

KRITERIA II

a. Tentukan rasio nilai kanan tiap kendala dengan koefisien variabel yang akan masuk x j

(kecualikan rasio dengan pembagi nol atau negatif)

7

b. Pilih rasio yang terkecil diantara ketiga rasio pada kendala. Rasio ini sama dengan nilai xj dalam solusi berikutnya. Nilai minimum rasio ini akan menghilangkan variabel xk pada solusi ini. Jadi xj menggantikan xk pada basis.

Perhitungan berdasarkan kriteria II ini disajikan pada tabel berikut ini :

Variabel Basis

Solusi yang sedang Berlangsung

Koefisien x3 Rasio Rasio min Solusi Berikut

fx4

x5

x6

027052210445

-202,04,02,0

1352,5552,5222,5 222,5 x3

Setelah diketahui bahwa x3 akan menghasilkan x6 sebagai basis maka dilanjutkan dengan langkah 4.

Tulis kembali sistem (1) dimana x3 mempunyai koefisien 1 pada baris 3, koefisien 0 pada baris 0, baris 1 dan baris 2. Proses ini disebut proses penggatian basis, atau operasi pivot. Pertama kali bagilah baris 3 dengan 2 yaitu koefisien x3 .

..............baris 0

........baris 1

(2) ....baris 2

...baris 3

Dengan operasi pivot pada 2,0 jadikanlah koefisien x3 sama dengan 1 pada baris 3. Operasi ini mengakibatkan koefisien x3 pada baris lainnya yaitu baris 0, baris 1 dan baris 2. Semuanya menjadi nol. Manipulasi yang dilakukan ialah :

- Baris 0 : Kalikan baris 3 dengan 20 dan tambahkan ke baris 0- Baris 1 : Kalikan baris 3 dengan -2 dan tambahkan ke baris 1- Baris 2 : Kalikan baris 3 dengan -4 dan tambahkan ke baris 2

Hasilnya adalah :

..............baris 0

...............baris 1

(3) ..................baris 28

....baris 3

Sistem (3) memperlihatkan bahwa dengan mengambil x1 = x2 = x6 = 0 diperoleh basis baru seperti pada tabel berikut :

BASIS NILAIfx4

x5

x3

445022601320222,5

Perlihatkan bahwa pada basis baru ini, keuntungan menjadi 4450, yang juga dapat dihitung dari hubungan :

= + x

4450 = 0 + (222,5 x 20 )

Dengan mengulangi langkah 2, kita dapat menetapkan apakah solusi optimal telah dicapai ataukah masih perlu dilakukan iterasi berikutnya.

Kriteria I untuk memeriksa variabel non basis menunjukkan bahwa perbaikan program masih diperlukan. Kita selidiki apakah x1 atau x2 yang akan dimasukkan dalam program sebagai basis baru. Kriteria ini menunjukkan bahwa x2 terpilih sebagai basis yang akan dimasukkan karena x2 memiliki koefisien yang paling negatif yaitu -5 dibanding dengan x1 yang memiliki koefisien -3 yang terdapat pada baris 0 (baris fungsi objektif). Hal ini menandakan bahwa keuntungan yang diberikan oleh x2 lebih besar jika dibandingkan dengan keuntungan yang diberikan oleh x1 , per unitnya. Selanjutnya perhitungan seperti pada langkah 3 dengan menggunakan Kriteria II memberikan :

Variabel Basis

Solusi yang sedang Berlangsung

Koefisien x2 Rasio Rasio min Solusi Berikut

fx4

x5

x3

445022601320222,5

-5480,5

565165445

165 x2 = 165x5 = 0

9

Keuntungan Baru Keuntungan sebelumnya

Nilai variabel yang baru masuk

Keuntungan per unit yang diberikan oleh basis yang masuk

Tabel diatas menunjukkan bahwa x2 akan menggantikan x5 dalam basis. Kita akan menuliskan sistem (3) untuk mengerjakan substitusi. Untuk perhitungan perubahan basis pada langkah 4, pertama sekali bagilah baris 2 dengan poros (pivot) yaitu 8 yang mengakibatkan koefisien x2 menjadi 1, untuk selanjutnya melenyapkan x5 dan memunculkan x2 dalam solusi

..............baris 0

....................baris 1

(4) ..................baris 2

....baris 3

Kemudian, Jadikanlah koefisien x2 lainnya (pada baris 0,baris 1, dan baris 3) semuanya nol, sebagai berikut :

- Baris 0 : Kalikan baris 2 dengan 5 dan tambahkan ke baris 0- Baris 1 : Kalikan baris 2 dengan -4 dan tambahkan ke baris 1- Baris 2 : Kalikan baris 2 dengan -0,5 dan tambahkan ke baris 4

Hasilnya ialah :

......baris 0

.............baris 1

(4) .........baris 2

......baris 3

Sistem (5) ini memberi hasil seperti pada tabel :

BASIS NILAIfx4

x2

x3

52751600165140

Hasil iterasi kedua ini (jadi solusi ketiga) selanjutnya digunakan untuk menyelidiki apakah solusi optimal telah dicapai. Periksalah baris 0 (baris fungsi tujuan). Basis pada iterasi kedua ini adalah f,x4,x2,dan x3. Perhatikan bahwa koefisien x1 pada baris 0 adalah – 0,5 (negatif) yang menunjukkan bahwa solusi ini belum optimal, sehingga variabel x1 perlu dimasukkan kedalam program sebagai basis karena akan meningkatkan keuntungan. Periksalah rasio minimum nilai kanan dengan setiap koefisien x1 pada baris 1,2 dan 3.

10

Hasilnya ditunjukkan oleh tabel berikut :

Variabel Basis

Solusi yang sedang Berlangsung

Koefisien x2 Rasio Rasio min Solusi Berikut

fx4

x2

x3

52751600165140

-0,580,50,1

2003301400

200 x1 = 200x4 = 0

Ternyata rasio minimum adalah 200 sehingga x1 akan menggantikan X4 dalam basis. Jadikanlah koefisien x1 pada baris 1 bernilai 1 dengan membagi baris tersebut dengan 8 dan menghasilkan :

......baris 0

.......baris 1

(6) .........baris 2

......baris 3

Lanjutkan dengan mengubah semua koefisien x1 pada baris-baris lainnya (baris 0,2,3) menjadi nol dengan jalan :

- Baris 0 : Kalikan baris 1 dengan 0,5 dan tambahkan ke baris 0- Baris 2 : Kalikan baris 1 dengan -0,5 dan tambahkan ke baris 2- Baris 3 : Kalikan baris 1 dengan -0,1 dan tambahkan ke baris 3

Hasilnya :

......baris 0

.............baris 1

(7) .............baris 2

......baris 3

Program ini menghasilkan :

BASIS NILAI

11

fx1

x2

x3

537520065120

Program yang dinyatakan oleh sistem (7) menunjukkan bahwa pada baris fungsi tujuan (baris 0), tidak ditemui lagi adanya koefisien negatif, yang menandakan bahwa program ini telah mencapai optimal. Perusahaan yang bersangkutan memperoleh keuntungan maksimum sebesar $ 5375 dengan memproduksi barang tipe A sebanyak 200 unit, barang tipe B sebanyak 65 unit dan barang tipe C sebanyak 120 unit

Ringkasan :

Penyelesaian suatu persoalan program linier dilakukan melalui langkah-langkah :

Langkah 1 Pilih basis awal (variabel slack dipilih sebagai basis)

Langkah 2 Gunakan kriteria I untuk memeriksa optimalitas fungsi tujuan. Jika solusi yang sedang berlangsung belum optimal, lanjutkan ke langkah 3. Apabila telah mencapai optimal, pekerjaan dihentikan

Langkah 3 Gunakan kriteria II untuk menentukan jumlah unit variabel yang akan masuk sebagai basis dan menetapkan variabel yang keluar dari program

Langkah 4 Melakukan perubahan basis

Catatan :

Pada contoh diatas, disamping variabel x1, x2,....., x6 terdapat juga variabel f sehingga seharusnya setiap kendala dituliskan sehingga berisikan variabel f. Namun karena koefisiennya adalah nol maka variabel ini tidak dituliskan. Misalnya kendal pertama yaitu

Lengkapnya adalah :

Oleh karena koefisien f pada semua kendala selalu nol dan pada setiap transformasi yang dilakukan tidak akan mempengaruhi f pada fungsi tujuan, maka dalam prakteknya variabel f ini tidak ditulis, namun harus dipikirkan adanya variabel f ini pada setiap kendala.

Perlu diperhatikan bahwa pada setiap solusi, variabel f ini selalu termasuk sebagai basis, namun demikian dalam pembicaraan tentang variabel basis, f ini sebagai salah satu basis sering tidak disebut, tetapi harus dipikirkan adanya karena justru pada setiap solusi, nilai f inilah yang diperlukan

12

Contoh:

Diberikan masalah sebagai berikut:

Maksimumkan

Syarat

Setelah dimasukkan variabel slack, maka sistem ini berubah menjadi:

baris 0

baris 1

baris 2

baris 3

Langkah pertama. Pilih solusi awal : sedang

Langkah kedua. Pada langkah kedua ini, akan ditentukan variabel yang akan masuk ke dalam

program sebagai basis. Dengan menggunakan kriteria I, periksalah baris 0,

yaitu baris fungsi objektif dan terpilih x2 karena memiliki koefisien paling

negatif.

Langkah ketiga. Dengan menggunakan kriteria II, akan di tetapkan variabel yang akan

digantikan oleh x2.

Hitunglah rasio nilai kanan dengan koefisien x2 yang bersesuaian pada setiap baris kendala.

13

Basis Solusi yang berlangsung Koefisien Rasio Min Solusi berikut

F 0 -12 -

100 2 50 50 = 50, = 0

80 -2 -

300 5 60

Tabel ini menunjukkan bahwa masuk ke dalam basis sebesar 50 unit dan akan menghilangkan dan basis.

Langkah keempat. Ubahlah koefisien menjadi 1 pada baris 1 dengan membagi baris itu dengan 2. Setelah hal ini dilakukan maka bersama-sama dengan baris-baris lainnya sistem menjadi:

baris 0

baris 1

baris 2

baris 3

Lanjutkan dengan perubahan sistem persamaa dengan cara mengubah semua koefisien x2 pada baris-

baris 0, 2 dan 3 semuanya nol.

Baris 0 : Kalikan baris 1 dengan 12 dan tambahkan ke baris 0.

Baris 2 : Kalikan baris 1 dengan 2 dan tambahkan ke baris 2.

Baris 3 : Kalikan baris 1 dengan -5 dan tambahkan ke baris 3.

Hasilnya adalah:

baris 0

baris 1

14

baris 2

baris 3

Sistem ini menunjukkan solusi:

Basis Nilai

f 600

50

180

50

Oleh karena pada sistem persamaan terakhir masih terdapat koefisien negatif pada baris fungsi tujuan maka kriteria I mengisyaratkan bahwa perbaikan program masih perlu dilanjutkan.

Variabel yang akan dimasukkan adalah .

Kriteria II digunakan untuk menetapkan variabel yang akan keluar dari basis dan berapa unit akan

dimasukkan.

Basis Solusi yang berlangsung Koefisien Rasio Min Solusi berikut

F 600 -2 -

50 100

180 6 30 30 =30, = 0

50

akan menggantikan dalam basis.

Kemudian bagilah baris 2 dengan 6 sehingga koefisien menjadi 1 dan tuliskan kembali sistem persamaannya.

baris 0

15

baris 1

baris 2

baris 3

Jadikan semua koefisien variabel pada baris-baris 0, 1 dan 3 menjadi nol yaitu:

Baris 0 : Kalikan baris 2 dengan 2 dan tambahkan ke baris 0.

Baris 1 : Kalikan baris 2 dengan dan tambahkan ke baris 1.

Baris 3 : Kalikan baris 2 dengan dan tambahkan ke baris 3.

Sistem persamaan menjadi:

baris 0

baris 1

baris 2

baris 3

Sistem ini menunjukkan solusi:

Basis Nilai

f 660

35

30

5

16

Pemeriksaan terhadap koefisien-koefisien pada baris 0 (baris fungsi tujuan) menunjukkan bahwa tidak ada lagi yang bernilai negatif sehingga solusi yang diperoleh telah mencapai optimal. Program ini menghasilkan:

=35, =30, =5 dan f(maks)= 660

Pada dasarnya penyelesaian yang dilakukan pada pembicaraan di atas tidak lain dari pada melakukan transformasi elementer baris terhadap matriks lengkap dan koefisien-koefisien dari sistem persamaan linier yang dibentuk oleh masalah program linier yang bersangkutan. Elemen matriks yang dijadikan sebagai pivot (poros) berkaitan dengan variabel mana yang akan dimasukkan dan variabel mana yang akan dikeluarkan dari basis. Kriteria I mementukan variabe yang akan masuk sedang kriteria II menetapkan variabel mana yang akan keluar. Dengan demikian pengerjaan mencari solusi optimal dapat dilakukan dengan hanya menggunakan matriks lengkap dari koefisien sisitem persamaaannya. Pada contoh berikut ini, penyelesaian program linier di atas dilakukan dengan menggunakan matriks koefisien.

Matriks lengkap sistem persamaan di atas adalah:

Rasio

Perhatiakan bahwa kolom-kolom f, , dan membentuk matriks identitas segitiga sehingga

solusi awal diberikan oleh matriks identitas ini yaitu f=0, =100, =80 dan =300 sedang variabel lainnya semua nol.

Kriteria I dan II menunjukkan bahwa elemen 2 (yang dilingkari) merupakan elemen pivot. Dengan demikian matriks itu ditulis kembali sehingga elemen pivot menjadi 1, kemudian dilakukan transformasi elemen baris.

17

Rasio

Matriks ini menunjukkan hasil f= 600, =50, =180, =50.

Pada baris pertama masih terdapat bilangan negatif, sehingga perbaikan selanjutnya perlu dilakukan.

Karena koefisien negatif ini terdapat pada kolom maka dimasukkan dalam basis. Sedang rasio

nilai kana dengan koefisien-koefisien pada kendala menunjukkan nilai minimum rasio ini terdapat pada baris ketiga maka transformasi baris elementer yang dilakukan adalah poros 6 (perpotongan kolom dengan baris ketiga, pada matriks di atas, poros ini dilingkari). Prosesnya terdapat perhitungan sebagai berikut ini:

18

Hasilnya adalah f = 660, =35, =30, dan =5

Penyelidikan selanjutnya terhadap baris pertama dari matriks memperlihatkan bahwa solusi ini telah mencapai optimal.

BAB III

PENUTUP

3.1 Kesimpulan

1. Penyelesaian masalah PL(Program Linier) yang melibatkan lebih dari dua variabel

membutuhkan metode solusi yang lebih umum menjadi nyata.

19

2. Metode umum itu dikenal dengan nama Algoritma Simplex yang dirancang untuk

menyelesaikan seluruh masalah PL, baik yang melibatkan dua variabel atau lebih

dua variabel.

3. Metode ini menyelesaikan masalah PL melalui perhitungan-ulang (iteration) di mana

langkah- langkah perhitungan yang sama diulang berkali-kali sebelum solusi

optimum dicapai.

DAFTAR PUSTAKA

Gauss, S. L. 1975. Liniear Programming, Methods and Application. Mc-Graw-Hill Book

Co., New York

Supranto, J. 1983. Linier Programming. Lembaga Penerbit FE-UI : Jakarta

Susanta, B. 1994. Program Linier. Erlangga: Yogyakarta

20