PENELITIAN OPERASIONAL TAMBANG

PROGRAM LINEAR DAN METODE SIMPLEKS

OLEH :

NAMA : RAKA TUBAGUS INDRA. R

NIM : 1306449

PRODI : TEKNIK PERTAMBANGAN S1

JURUSAN TEKNIK PERTAMBANGAN

FAKULTAS TEKNIK

UNIVERSITAS NEGERI PADANG

PADANG

2016

KATA PENGANTAR

Puji syukur kami panjatkan kehadirat Allah SWT. Yang telah

melimpahkan taufik dan hidaya Nya, sehingga kami dapat menyelesaikan

makalah ini. Tujuan utama dibuatnya makalah ini adalah untuk mamenuhi tugas

pada mata Penelitian Operasional Tambang.

Dalam penulisan makalah ini, kami membahas tentang programlinier dan

metode simpleks dengan rujukan buku bahan ajar program linear karya yetri

ningsih ,M.Pd. tahun 2013.

Mudah-mudahan makalah ini dapat memenuhi syarat. Besar harapan kami

kepada pembaca, sekurangnya dapat memberikan kritik dan saran yang

membangun kearah perbaikan makalah ini, sehingga makalah ini menjadi lebih

sempurna.

Padang, Maret 2016

Penyusun

2

DAFTAR ISI

Kata pengantar.............................................................................................2

Daftar isi.......................................................................................................3

BAB I: PENDAHULUAN...........................................................................4

A. Latar Belakang.................................................................................4

B. Rumusan masalah............................................................................4

C. Tujuan..............................................................................................5

BAB II: PEMBAHASAN............................................................................6

A. Pengertian metode simpleks.............................................................6

B. Penentuan maksimum......................................................................6

C. Penentuan minimum........................................................................18

D. Variabel slack tiruan........................................................................20

E. Merancang program awal.................................................................20

F. Prosedur penentuan struktur persyaratan.........................................23

BAB III: PENUTUP....................................................................................27

A. Kesimpulan......................................................................................27

B. Saran.................................................................................................28

DAFTAR PUSTAKA...................................................................................29

3

BAB I

PENDAHULUAN

A. Latar Belakang

Dalam matematika terdapat metode untuk mengalokasikan sumber daya

yang terbatas untuk mencapai suatu tujuan yang optimal. Metode ini adalah

pemrograman linier. Pemograman linier banyak diterapkan dalam masalah

ekonomi, industri, militer, sosial, dan lain-lain.

Pemrograman linear berkaitan dengan penjelasan suatu kasus dalam dunia

nyata sebagai suatu model matematika yang terdiri dari sebuah fungsi tujuan linier

dengan beberapa kendala linier. Pemrograman linier meliputi perencanaan

aktivitas untuk mendapatkan hasil optimal, yaitu sebuah hasil yang mencapai

tujuan terbaik (menurut model matematika) diantara semua kemungkinan

alternatif yang ada.

Karateristik-karakteristik pada pemrograman linier adalah: fungsi tujuan

(untuk memaksimumkan atau meminimumkan sesuatu), fungsi pembatas yang

membatasi tingkatan pencapaian tujuan, adanya beberapa alternatif tindakan yang

bisa dipilih, fungsi tujuan dan kendala dalam permasalahan diekspresikan dalam

bentuk persamaan atau pertidaksamaan linier.

Metode simpleks adalah suatu metode yang secara sistematis dimulai dari

suatu pemecahan dasar yang dimungkinkan ke pemecahan dasar yang lainnya dan

ini dilakukan tahap demi tahap yang disebut dengan iterasi (dengan jumlah iterasi

yang terbatas) sehingga pada akhirnya akan tercapai suatu pemecahan dasar yang

optimum dan setiap langkah menghasilkan suatu nilai dari fungsi tujuan yang

selalu lebih optimal atau sama dari langkah-langkah sebelumnya.

B. Rumusan Masalah

Adapun rumusan permasalahan yang dibahas didalam makalah ini, sebagai

berikut:

1. Bagaimana menyelesaikan permasalahan program linier dengan

metode simpleks?

4

2. Bagaimana menentukan kerangka dasar perhitungan nilai maksimum

dari tabel simpleks?

3. Bagaimana merancang program awal yang memuat atas variabel

“slack”?

4. Bagaimana siswa memperbaiki program awal dan program-program

berikutnya hingga tercapai program maksimum?

5. Bagaimana menentukan kerangka dasar perhitungan nilai minimum

dari tabel simpleks?

6. Bagaimana merancang program awal yang hanya terdiri atas variabel

“slack tiruan”?

7. Bagaimana siswa memperbaiki program awal dan program-program

berikutnya hingga tercapai program minimum?

C. Tujuan Penulisan

Dalam setiap penulisan makalah pastilah ada tujuan yang ingin dicapai

oleh penulis, adapun tujuan dari penulisan makalah ini:

1. Memenuhi tugas mata kuliah Program Linear.

2. Dapat menyelesaikan permasalahan program linier dengan metode

simpleks.

3. Dapat menentukan kerangka dasar dari tabel simpleks.

4. Dapat merancang program awal yang memuat atas variabel “slack”

atau “slack tiruan”.

5. Dapat memperbaiki program awal dan program-program berikutnya

hingga tercapai program maksimum.

6. Dapat memperbaiki program awal dan program-program berikutnya

hingga tercapai program minimum.

5

BAB II

PEMBAHASAN

A. Pengertian

Metode simpleks merupakan salah satu teknik penyelesaian dalam

program linier yang digunakan sebagai teknik pengambilan keputusan dalam

permasalahan yang berhubungan dengan pengalokasian sumber daya secara

optimal. Metode simpleks digunakan untuk mencari nilai optimal dari program

linier yang melibatkan banyak constraint (pembatas) dan banyak variabel (lebih

dari dua variable). Penemuan metode ini merupakan lompatan besar dalam riset

operasi dan digunakan sebagai prosedur penyelesaian dari setiap program

komputer.

Program Linier merupakan metode matematik dalam mengalokasikan

sumber daya yang langka untuk mencapai tujuan tunggal seperti

memaksimumkan keuntungan atau meminimumkan biaya. LP (linear

programming) banyak diterapkan dalam membantu menyelesaikan masalah

ekonomi, indutri, militer, sosial dan lain-lain.

Dari berbagai metode penyelesaian program linier, metode simpleks

merupakan metode yang paling ampuh dan terkenal. Metode simpleks didasarkan

atas pengertian bahwa solusi optimal dari masalah program linier, jika ada, selalu

dapat ditemukan disalah satu dari “solusi dasar yang berlaku”. Oleh sebab itu

dalam metode simpleks, langkah pertama adalah untuk memperoleh solusi dasar

yang berlaku.

B. Penentuan Maksimum

Suatu masalah dalam pabrik memiliki data sebagai berikut:

Ukuran waktu pemprosesan oleh departemen

DepartemenUkuran Kapasitas per-

periode waktuA B C

Pemotongan 10,7 5,0 2,0 2705

Pelipatan 5,4 10,0 4,0 2210

6

Pengepakan 0,7 1,0 2,0 445

Keuntungan/unit $10 $15 $20

Langkah pertama adalah menentukan model matematika untuk data-data yang

tertera dalam tabel.

Misalnya bahwa diproduksi sejumlah x unit dari produksi A, sejumlah y

unit dari produksi B dan sejumlah z unit dari produksi C.

Fungsi objektif:

Maksimumkan : f=10x + 15y + 20z

Syarat : 10,7x + 5y + 2z ≤ 2705

5,4x + 10y + 2z ≤ 2210

0,7x + 1y + 2z ≤ 445

x ≥ 0, y ≥ 0, z ≥ 0

Dengan penambahan variabel “slack” S1, S2, S3, pertidaksamaan tersebut

dapat diubah menjadi persamaan. Pembuatan produksi imaginer S1, S2, S3,

melibatkan keuntungan nol perunitnya. Sehingga Model matematikanya dapat

ditulis kembali sebagai berikut :

Maksimumkan : fo = 10x + 15y + 20z + 0S1 + 0S2+ 0S3

Syarat : 10,7x + 5y + 2z + 1 S1 + 0 S2 + 0 S3 ≤ 2705

5,4x + 10y + 2z + 0S1 + 1S2 + 0S3 ≤ 2210

0,7x + 1y + 2z + 0S1+ 0S2+ 1S3 ≤ 445

x ≥ 0, y ≥ 0, z ≥ 0 S1 ≥ 0, S2 ≥ 0, S3 ≥ 0

Metode simpleks melangkah dengan mengadakan perbaikan-perbaikan

terhadap solusi dasar yang memenuhi syarat sehingga dicapai suatu solusi

7

optimal. Setiap program yang akan dibuat berikut, diberikan dalam bentuk matrik

atau tabel.

Kerangka dalam simpleks ditampilkan sebagai berikut:

Variabel dalam solusi

Koefisien fungsi

objektif

Besarnya

variabel

10 15 20 0 0 0

X Y Z S1 S2S3

S1 0 270510,7

5 21

0 0

S2 0 2210 5,4 10 4 0 1 0S3 0 445 0,7 1 2 0 0 1

 Net evaluation row 10 15 20 0 0 0

Bilangan di “Net evaluation row”, dibawah setiap kolom dari “badan utama” dan “identitas”

mewakili “opportunity cost” dari tidak memiliki satu unit dari variabel kolom bersangkutan dalam

solusi. Bilangan tersebut mewakili kemampuan peningkatan dalam fungsi obyektif yang dihasilkan

jika memasukan satu unit dari variabel kolom bersangkutan dalam program.

1. Merancang Program Awal

Program pertama dalam metode simpleks adalah program yang hanya

melibatkan variabel slack. Arti dari data-data yang tertera pada tabel

simpleks diatas harus dimengerti sepenuhnya agar dapat menghayati

metode simpleks. Oleh sebab itu marilah kita bahas tabel berikut ini:

Program Keuntungan Kuantitas $10 $15 $20 $0 $0 $0

8

Baris Variabel, menunjukan semua variabel dalam program

Baris objektif, diatas setiap variabel, koefisien obyektif bersangkutan

Kolom objektif menunjukan koefisien obyektif dari variabel dalam program

Identitas setiap solusi dalam metode simpleks harus menunjukan suatu matriks identitas

Kolom ini menunjukan variabel program, variabel lain bernilai nol

Kolom ini menunjukan besarnya variabel dalam program.

Badan utama terdiri atas koeeefisien kerangka atau subtitusi rasio

Perunit x y z S1 S2 S3

S1 0 2705 10,7 5 2 1 0 0S2 0 2210 5,4 10 4 0 1 0S3 0 445 0,7 1 2 0 0 1

Keterangan:

a) Dalam kolom “program” terdaftar variabel-variabel khusus dalam

solusi (produksi yang dihasilkan). Maka dalam program awal kita

produksi S1, S2, dan S3.

b) Dalam kolom “Keuntungan per unit” terdaftar koefisien (dalam

fungsi objektif) dari variabel-variabel yang tercakup dalam program

tersebut. Dapat dipastikan dari fungsi objektif, koefisien dari S1, S2,

dan S3 adalah nol

c) Dalam kolom “Kuantitas” terdaftar besarnya variabel yang tercakup

dalam solusi. Program awal mencakup produksi 2705 unit S1, 2210

unit S2, dan 445 unit S3.

d) Kontribusi keuntungan total yang dihasilkan dari program yang

dimiliki dapat dihitung dengan mengalikan angka-angka dalam

kolom “keuntungan per unit” dan kolom “kuantita” bersangkutan

dan kemudian menjumlahkan hasil perkaliannya. Dalam program

pertama kontribusi keuntungan total adalah : 0(2705) + 0(2210) +

0(445) = 0

e) Bilangan-bilangan dalam bagian utama (bilangan-bilangan dibawah

kolom x, y dan z) dapat dijelaskan memiliki arti fisik. Misalnya,

bilangan 10,7 menunjukan perbandingan pertukaran antara x dan S1,

berarti memproduksi 1 unit x harus mengorbankan 10.7 unit S1 .

Pada kolom dibawah y berarti memproduksi 1 unit y harus

mengorbankan 5 unit S1 , 10 unit S2 ,dan 1 unit S3 .

2. Menguji Keoptimalan Program yang sedang Berlangsung

Program awal memberikan keuntungan nol , karena melibatkan x = 0 , y =

0 , z = 0 , S1= 2705 , S2= 2210 , S3= 445 dengan keuntungan :

9

f0 = 10(0) + 15(0) + 20(0) + 0(2705) + 0(2210) + 0(445) = 0

Perbaikan terhadap program awal dilakukan dengan mengikutsertakan z

dalam program. Dipilih z karena 1 unit z memberikan keuntungan $20,

yang lebih tinggi dari keuntungan yang diberikan oleh 1 unit x atau 1 unit

y.

Pemasukan unit dalam program mengubah fungsi keuntungan menjadi +

1(20) – 2(0) – 4(0) – 2(0) = + 20

Tabel 4.1

Tabel Program 1

Prog

ram

Profit

Perunit

Kuant

itas

$10

x

$15

y

$20

z

$0

S1

$0

S2

$0

S3

S1

S2

S3

0

0

0

2705

2210

445

10.7

5.4

0.7

5

10

1

2

4

2

1

0

0

0

1

0

0

0

1

27052

=1352,5

22104

=552,5

4452

=222,5

Net Evaluation Row 10 15 20 0 0 0

Jika dalam “net evaluation row “masih terdapat bilangan positif, berarti

solusi belum optimal; dan program masih memerlukan perbaikan.

3. Perbaikan Program yang Sedang Berlangsung

3.1 Mengeneli kolom kunci

Tiga bilangan positif (10, 15, 20 ) dalam “baris penilaian” menunjukkan

besarnya keuntungan jika mengikutsertakan 1 unit x, 1 unit y, dan 1 unit z.

Nilai terbesar 20 terletak dibawah kolom z, maka variabel (produk) z

10

Kolom kunci ( variabel masuk )

Bilangan kunci

Baris Kunci ( variabel keluar )

adalah variabel yang pertama-tama harus diikutsertakan. Kolom inin

disebut kolom kunci.

3.2 Mengenal baris kunci dan bilangan kunci

Setelah ditentukan bahwa variabel (produk) z akan diikutsertakan dalam

program untuk menggantikan salah satu dari variabel (produk) S1, S2, atau

S3 ; tibul pertanyaan berapa z dapat diikutsertakan tanpa melanggar

persyaratan-persyaratan yang teleh ditetapkan.

Dari tabel terlihat bahwa memasukkan 1 unit z berarti harus mengeluarkan

2 unit S1, 4 unit S2, dan 2 unit S3. Program yang sedang berlaangsung

memproduksi 2705 unit S1, 2210 unit S2, dan 445 unit S3. Bagilah bilangan

dalam kolom “kuantitas” dengan bilangan “bukan negatif” bersangkutan

dari kolom kunci, kemudian bandingkan hasil bagi yang terkecil menjadi

“barisan kunci”.

Perhitungan untuk menentukan barisan kunci adalah:

Barisan S1 : 2705

2 = 1352,5 unit

Barisan S2 : 2210

4 = 552,5 unit

Barisan S3 :445

2 = 222,5 unit

Barisan S3 merupakan barisan kunci

Setelah kolom kunci dan barisan kunci ditemukan, selanjutnya

menentukan bilangan kunci. Bilangan yang terletak pada perpotongan

kolom kunci dan barisan kunci disebut “bilangan kunci”. Dalam contoh

diatas, bilangan kunci adalah 2.

3.3 Menurunkan Tabel

Penentuan kolom kunci dan barisan kunci menunjukkan bahwa variabel

(produk) z akan menggantikan variabel (produk) S3 dan tidak lebih dari

11

Bilanganberkaitan rasiotertentudalambariskuncibersangkutanX

X

222,5 unit z dapat diproduksi tanpa melenggar kapasitas. Tugas kita

selanjutnya adalah menentukan penurunan S1 dan S2 karena 222,5 unit z

dimasukkan dalam perbaikan program. Kapasitas yang tersisa untuk S1

adalah 2705 – ( 222,5 x 2 ) = 2260 dan untuk S2 adalah 2210 – ( 222,5 x

4 ) = 1320 unit.

Program kedua melibatkan x = 0, y = 0, z = 222,5 , S1 = 2260, S2 = 1320,

dan S3 = 0, sehingga program II akan memiliki tabel baru yang

ditransformasikan dari tabel program I. Transformasi dari tabel lama ke

tabel baru mengikuti aturan-aturan yang telah ditetapkan.

Aturan : Bagilah semua bilangan dalam baris kunci dengan

bilangan kunci

Maka, barisan ketiga dalam tabel (barisan z) diturunkan dari barisan

ketiga dari tabel 4.1 (barisan S3) dengan membagi setiap bilangan dengan

2. Barisan baru dari z (tabel program II) adalah:

222,5 0,35 0,5 1 0 0 0,5

3.5 Transformasi Bukan Baris Kunci

Aturan :

Dimana : rasio tertentu = bilanganbaris lama dalam kolom kunci

bilangankunci

Berdasarkan aturan tersebut , maka barisan S1 baru dalam tabel program II

diturunkan sebagai berikut :

Rasio tertentu = 22 = 1

12

Bil.barisbaru = bil.barislama –

Bil. berkaitan

dalam baris kunci

Rasio tertentu

bersangkutan

Bilangan baris lama – = Bil.

Baris baru

2705 - ( 445 x 1 ) = 2260

10,7 - ( 0,7 x 1 ) = 10

5 - ( 1 x 1 ) = 4

2 - ( 2 x 1 ) = 0

1 - ( 0 x 1 ) = 1

0 - ( 0 x 1 ) = 0

0 - ( 1 x 1 ) = -1

Sesuai perhitungan di atas, baris baru S2 dapat diturunkan sebagai

berikut:

Rasio tertentu = 4/2 = 2

Bilangan berkaitan rasio tertentu

Bil.baris lama - x = Bil. baris baru

dalam baris kunci bersangkutan

2210 - ( 445 x 2 ) = 1320

5,4 - ( 0,7 x 2 ) = 4

10 - ( 1 x 2 ) = 8

4 - ( 2 x 2 ) = 0

0 - ( 0 x 2 ) = 0

1 - ( 0 x 2 ) = 1

0 - ( 1 x 2 ) = -2

Dari hasil perhitungan transformasi baris kunci dan transformasi baris

bukan kunci, diperoleh tabel program 11,secara lengkap dapat dilihat

pada tabel 4.2

13

Tabel 4.2

Tabel Program II

Program 11 melibatkan produksi dari S1 = 2260, S2 =1320 , dan Z = 222,5 Unit.

Variabel S3 , X dan Y tidak ada dalam program.Keuntungan total dari program 11

adalah : 2260 (0) + 1320 (0) + 222,5 (0) = $ 4450

4. Perbaikan Program II

Dalam program II, baris penilaian masih mempunyai dua bilangan

positif, maka program ini belum optimal dan masih memerlukan

perbaikan.Penurunan program III dari program II menggunakan langkah-

langkah seperti yang telah dilakukan pada trans- formasi dari program 1

ke program II.

Perhitungan pada tabel 11 menunjukkan bahwa baris S2 merupakan baris

kunci dan variabel (produk) y harus masuk dalam program,karena

memberikan keuntungan tertinggi.Jadi kolom y menjadi kolom kunci

dengan bilangan kunci = 8.

14

Pro

gra

m

Profit

perunit

Kuan

titas

$ 10

X

$ 15

Y

$ 20

Z

$ 0

S1

$ 0

S2

$ 0

S3

S1 0 2260 10 4 0 1 0 -1 2260/4 = 565

S2 0 1320 4 8 0 0 1 -2 1320/8 =165

Z 20 222,5 0,35 0,5 1 0 0 0,5 222,5 = 445

Net Evaluation Row 3,0 5,0 0 0 0 -10

Produk akan keluar Produk akan masuk

Baris y dalam tabel program 111 menjadi :

165 0,5 1 0 0 0,125 -0,25

Untuk baris S1 baru dalam tabel program 111 diturunkan sebagai berikut:

Rasio tertentu = 4/8 = 0,5

Bilangan berkaitan rasiao tertentu

Billangan baris lama X = bilangan baru

Dalam baris kunci bersangakutan

2260 - ( 1320 x 0,5 ) = 1600

10 - ( 4 x 0,5 ) = 8

4 - ( 8 x 0,5 ) = 0

0 - ( 0 x 0’5 ) = 0

1 - ( 0 x 0’5 ) = 1

0 - ( 1 x 0’5 ) = -0,5

-1 - ( -2 x 0’5 ) = 0

Perhitungan untuk garis z pada program ke llldapat diturun kan sebagai berikut ;

Rasio tertentu =0,5/8 = 0,0065

Bilangan berkaitan rasio tertentu

Bilangan baris lama x = Bil. Baris baru

Dalam baris kunci bersangkutan

222,5 -( 1320 x 0’0625) = 140

0,35 -(4 x 0,0625) = 0,1

0,5 -(8 x 0,0625) = 0

1 -(0 x 0,0625) = 1

15

0 -(0 x 0,0625) = 0

0 -(1 x 0,0625) = -0;0625

0,5 -(-2 x 0,0625) = 0,0625

Dari hasil perhitungan di atas diperoleh tabel program ke lll yang secara lengkap

dapat di lihat pada tabel 4.3.

Tabel 4.3

Tabel Program III

Pro

g

ram

Profit

perunit

Kuan

titas

$10

x

$15

y

$20

Z

$0

S1

$0

S2

$0

S3

S1 0 1600 8 0 0 1 -0,5 0 1600/8=200

y 15 165 0,5 1 0 0 0,125 -0,25 165/0,5=330

z 20 140 0,1 0 1 0 -0,062 0,625 140/0,1 =1400

Net evolution row 0,5 0 0 0 -0,062 -8,75

Produk akan keluar produk akan masuk

Program ke tiga memproduksi s1 = 1600, y =165 , dan z =140 unit .

Keuntungan total yang dihasilkan dari program ke tiga adalah ;

1600 (0) + 165 (15) + (20) = $ 5275

5. Perbaikan Program lll

16

Dalam program ke lll, baris penilaian mempunyai satu bilangan pasitif

yaitu didalam kolom x . berarti program ini belum optimal dan masih

memerlukan perbaikan . penurunan tabel program lV dari tabel program

lll menggunakan langkah -langkah seperti yang telah di lakukan pada

tranformasi dari program ll ke program III .

Perhitungan pada tabel program menunjukan bahwa baris S1 merupakan

baris kunci dan variabel (produk) x menjadi kolom kunci = 8

Baris x dalam tabel program 1V menjadi ;

200 1 0 0 0,125 -0,0625 0

Untuk baris y baru dalam tabel program 1V diturun kan sebagai berikut ;

Rasio tertentu = 0,5/8 = 0,0625

Bil. baris lama – [(bilangan berkaitandalambaris kunci )×( rasio tertentu

bersangkutan)]=¿ Bil. baris baru

165 − (1600 ×0,0625 )=65

0,5 −(8 × 0,0625 )=0

1 −(0 × 0,0625 )=1

0 −(0 × 0,0625 )=0

0 −(1 ×0,0625 )=¿-0,062

0,125 −(−0,5 × 0,0625 )=156

-0,25 − (0× 0,0625 )=¿ -0,25

Perhitungan untuk baris z pada tabel program IV dapat diturunkan sebagai

berikut :

Rasio tertentu ¿0,18

=0,0125

17

Bil. Baris lama −[(bilangan berkaitandalambaris kunci )×( rasio tertentu

bersangkutan)]=¿ Bil. baris baru

140 − (1600 ×0,0125 )=120

0,1 − (8 × 0,0125 )=0

0 − (0 × 0,0125 )=0

1 − (0 × 0,0125 )=1

0 − (1 ×0,0125 )=¿-0,012

-0,062 − (−0,5 × 0,0125 )=¿-0,056

0,625 − (0 × 0,0125 )=¿-0,625

Dari hasil perhitungan di atas diperoleh tabel program IV yang secara

lengkap dapat dilihat pada tabel 4.4.

Tabel 4.4.

Tabel program IV

Program IV melibatkan produksi x = 200, y = 65, dan z = 120 unit,

dengan keuntungan total sebesar :

18

Pro

gram

Profit

perunit

Kuan

titas

$10

x

$15

y

$20

z

$0

S1

$0

S2

$0

S3

x

y

z

10

15

20

200

65

120

1

0

0

0

1

0

0

0

1

0,125

-0,062

-0,012

-0,062

156

-0,056

0

-0,25

0,625

16008

=200

1650,5

=330

1400,1

=140

Net Evaluation Row 0 0 0 0 -0,625 -8,75

200 (10) + 65 (15) + 120 (20) = $ 5375

Program IV ini telah optimal, karena pada baris penilaian dalam tabel IV

tersebut tidak mempunyai bilangan positif lagi.

6. Program Optimal

Bars penilaian (net evaluation row) mempunyai bilangan-bilangan yang

bernilai nol atau negatif. Kenyataan ini menunjukkan bahwa program

optimal teah diproleh.

C. Penemtuan Minimum

Kasus mencari nilai minimum akan dijelaskan dengan sebuah masalah

serupa dengan masalah diet yang sangat terkenal. Marilah kita merumuskan

masalah dimana seseorang memerlukaan sejumlah tertentu dari masing-masing

vitamin setiap harinya.

Vtamin A dan B terdapat dalam dua makanan yang berbeda M1 dan M2.

Jumlah vitamin disetiap makanan dan vitamin yang diperlukan setiap harinya

dapat dilihat pada tabel berikut.

Tabel Persiapan Penyusunan Model Matematika

Vitamin

Makanan

Keperluan

SehariM1 M2

A 2 4 40

B 3 2 50

Harga

Makanan/Unit3 2.5

Dalam menunjukkan bahwa 1 M1 mengandung 2 unit vitamin A dan 3

unit vitamin B, serta 1 unit M2 mengandung 4 unit vitamin A dan 2 unit vitamin B.

Keperluan sehari akan vitamin A paling sedikit 40 unit dan vitamin B sejumlah

540 unit. Tujuan kita adalah menentukan jumlah optimal dari makanan M1 dan

M2 sehingga keperluan vitamin seharinya dipenuhi dengan biaya serendah

mungkin.

19

Misalkan bahwa untuk memenuhi tujuan ini dibeli x makanan M1 dan

sejumlah y dari makanan M2. Secara aljabar masalah inni dapat ditulis sebagi

berikut:

Minimumkan: f = 3x + 2.5y

Syarat : 2x + 4y ≥ 40

3x + 2y ≥ 50

x ≥ 0 , y ≥ 0

Metode simpleks II menangani persyaratan “lebih besar atau sama”

dengan suatu nilai. Untuk merubah pertidaksamaan menjadi persamaan

memerlukan “pengurangan” dengan variabel “slack”. Misalkan sejumlah x dan y

dari vitamin A dan B diperlukan seharinya,maka model matematikanya dapat

ditulis kembali sebagai berikut:

Minimumkan: f = 3x + 2.5y + 0S1 + 0S2

Syarat : 2x + 4y - S1 = 40

3x + 2y – S2 = 50

x ≥ 0 , y ≥ 0 , S1 ≥ 0 , S2 ≥ 0

D. Variabel Slact Tiruan (Artificial)

Jika variabel kerangka (struktual) x dan y dimisalkan nol seperti pada

program awal metode simpleks, maka diperoleh nilai-nilai negatif dari S1 dan S2

yang tidak memenuhi persyaratan. Untuk tidak melanggar persyarataan-

persyaratan yang telah ditetapkan dalam program-program metode simpleks maka

diciptakan variabel slack tiruan.

Model matematika dilengkapi dengan variabel slack tiruan A1 dan A2

sampai An, sehingga jika x dan y bernilai nol, persamaan-persamaan persyaratan

masih memiliki variabel slack yang bernilai positif. Maka model matematika

secara lengkap ditulis:

Minimumkan: f = 3x + 2.5y + 0S1 + 0S2 + MA1 + MA2

20

Syarat : 2x + 4y - S1 + A1 = 40

3x + 2y – S2 + A2 = 50

x ≥ 0 , y ≥ 0 , S1 ≥ 0 , S2 ≥ 0 , A1 ≥ 0 , A2 ≥ 0

Perlu diperhatikan bahwa variabel “slack” S memiliki koefisien biaya

sebesar nol, sedangkan variabel “slack tiruan” A memiliki koefisien biaya M yang

tak terhingga besarnya. Dengan mengaitkan nilai M yang tak terhingga besarnya

pada koefisien slack tiruan A, kita yakin bahwa variabel ini tidak akan pernah

masuk dalam penyelesaian optimal.

E. Merancang Program Awal

Dalam metode simpleks, program awl hanya melibatkan S1 dan S2,

sedangkan x dan y sebagai variabel kerangka benilai nol. Untuk suatu masalah

berdimensi dua, ini berarti menyatakan vektor persyaratan P0 dalam vektor basis

10 dan 01 .

Dalam contoh yang ditampikan diatas, vektor persyaratan P0 = 4050 dapat

dinyatakan dengan vektor-vektor basis 10 dan 01 .

Untuk memudahkan penyusunan program awal dari metode simpleks II,

maka dengan menggunakan variabel slack A1 dan A2, model matematika perlu

dituliskan kembali selengkapnya.

Minimumkan: f = 3x + 2.5y + 0S1 + 0S2 + MA1 + MA2

Syarat : 2x + 4y - 1.S1 + 0.S2 + 1. A1 + 0.A2 = 40

3x + 2y + 0.S1 – 1.S2 + 0. A1 + 1.A2 = 50

x ≥ 0 , y ≥ 0 , S1 ≥ 0 , S2 ≥ 0 , A1 ≥ 0 , A2 ≥ 0

Program awal dengan memilih x, y, S1, S2 bernilai nol. Dari persamaan

diatas, mudah dipahami bahwa ini berkaitan dengan nilai-nilai A1 = 40 dan A2 =

50. Oleh sebab itu tabel yang digunakan untuk perhitungan simpleks II pada

program awal dapat dilihat pada tabel dibawah ini.

21

Tabel Program I

ProgramBiaya/

Unit

Kuan

titas

3

X

2,5

Y

0

S1

0

S2

M

A1

M

A2

A1 M 40 2 4 -1 0 1 0 40/4=10

A2 M 50 3 2 0 -1 0 1 50/2=25

Baris Penilaian: 3-5 M 52 -6 M M M 0 0

Variabel keluar Variabel masuk

Program awal ini melibatkan biaya 90 M yang jelas besar sekali, sehingga

program harus diperbaiki.

1. Perhitungan dari baris penilaian.

2. mengenali kolom kunci

3. mengenali bariskunci dan bilangan kunci

4. Transformasi dari baris kunci dan baris bukan kunci untuk memperoleh

program yang diperbaiki

Adapun perbedaan yang perlu diperhatikan dalam simpleks II, bahwa

dalam kasus mencari minimum, nilai “negatif terbesar” dalam baris penilaian

menentukan kolom kunci dan bukan positif terbesar seperti dalam kasus mencari

nilai minimum.

Dalam kasus mencari nilai minimum, jika bilangan dari baris penilaian

dibawah suatu kolom variabel adalah negatif, maka jelas bahwa keikutsertaan

variabel ini dalam baris baru akan menurunkan nilai dari fungsi objektifnya.

Penghitungan dari baris penilaian sudah dijelaskan dalam kegiatan belajar

1. Memasukan satu unit y akan menurunkan biaya total dengan 2,5M – 6M yang

diperoleh dari [+1(2,5) – 4M – 2M]

Nilai 2,5M – 6M jelas lebih negatif dari pada 3 – 5M, maka y adalah variabel

yang harus masuk dengan mengeluarkan variabel A1. Hasil perbaikan tabel

program I dapat dilihat pada tabel 5.3

22

Tabel 5.3

Tabel program II

Pro gram

Biaya per unit

Kuan titas

3 2,5 0 0 M MX Y S1 S2 A1 A2

Y 2,5 100,5

1 -0,25 0 0,25 0100,5

=20

A2

M 30

2

0 0,5 -1 -0,5 1302

=13

Baris penilaian:74−2M 0

58−1

2M M

−58

+ 32

M 0

Tabel program II jelas belum optimal karena masih memiliki nilai negatif

dalam baris penilaian. Perbaikan program akan melibatkan pergantian variabel A2

oleh x. Dalam transformasi baris lama ke baris baru dalam program yang telah

diperbaiki kita berpedoman kepada aturan – aturan yang telah berlaku, yaitu:

1. Baris kunci dibagi dengan bilangan kunci menghasilkan baris baru.

2. Bil. baris lama – (bilang berkaitan dalam baris kunci x rasio

tertentu bersangkutan) ¿ Bilangan baris baru

3. Rasio tertentu = bilanganbaris lama dalam kolom kunci

bilangankunci

Tabel 5.4

Tabel program III

Pro

gram

Biaya

perunit

Kua

n

titas

3 2,5 0 0 M M

0 1 S1 S2 A1 A2

Y 2,552 0 1

−38

14

38

−14

X 3 15 1 014

−12

−14

12

23

Variabel Keluar Variabel Masuk

Baris penilaian 0 0316

78

M− 316

M−78

Tabel program III sudah merupakan program optimal, karena baris penilaian

tidak memiliki nilai negatif lagi.

Program optimal ini berkaitan dengan pembelian 15 unit makan M1 dan 52

unit makanan M2 seharinya, dengan biaya 51,25 dollar sen.

F. Prosedur Penentuan Struktur Persyaratan

Karakteristik dari masalah program linier dapat dicakup dalam 3 jenis yang

berbeda.

1. persyaratan yang dalam bentuk aslinya dinyatakan oleh pertidaksamaan

dari jenis “kurang dari atau sama dengan”, jenis ≤.

2. persyaratan yang dalam bentuk aslinya dinyatakan oleh pertidaksamaan

dari jenis “lebih besar atau sama dengan”, jenis ≥.

3. persyaratan yang dalam bentuk aslinya merupakan campuran dari

persamaan dan pertidaksamaan.

Penyusunan kembali model matematika diperlukan untuk siap dan dapat

digunakan dalam perancangan program awal dari metode simpleks.

Kasus 1:

Jenis ( ≤. ) “lebih kecil dari atau sama dengan”

Setiap pertidaksamaan “kurang dari atau sama dengan” diubah menjadi

persamaan dengan menambah “variable slack” yang tidak negatif dan

memiliki koefesien 0 dalam fungsi objektif.

Contoh:

Maksimumkan: f = 10x + 15y

Syarat : 4x + 60y ≤. 60

24

3x + 4y ≤. 80

X ≥ 0, y ≥ 0

Persamaan yang diperlukan untuk table simpleks adalah:

4x + 6y + 1S1 + 0S2 = 60

3x + 4y + 0S1 + 1S2 = 80

Fungsi Objektif:

f = 10x + 15y + 0S1 + 0S2

kasus 2:

Jenis ( ≥ ) “lebih besar atau sama dengan”

Setiap pertidaksamaan dari jenis “lebih besar atau sama dengan” diubah

menjadi persamaan dengan mula-mula mengurangi dengan variabel slack

yang tidak negative dan memiliki koefesien onkos 0, kemudian

menambahkan dengan variabel slack tiruan yang tidak negative dan

memiliki koefesien onlos M yang bernilai tak hingga.

Contoh:

Minimunkan: f = 300x + 180y

Syarat : 8x + 5y ≥ 80

4x + 2y ≥ 70

x ≥ 0, y ≥ 0

Persamaan-persamaan yang diperlukan untuk tabel simpleks adalah:

8x + 5y +1S1 + 0S2 + 1A1 + 0A2 = 80

4x + 2y +0S1 + 1S2 + 0A1 + 1A2 = 70

Fungsi Objektif:

25

f: 300x + 180y +0S1 + 0S2 + MA1 + MA2

Kasus 3:

Kasus campuran

Masalah yang digolongkan kedala kasus 3 adalah masalah yang memiliki

persamaan disamping pertidaksamaan. Persamaan ditangani dengan

melengkapinya dengan menambahkan variabel slack tiruan yang tidak

negative.

Contoh:

Minimumkan: f = 7x + 15y

Syarat : 2x + 4y ≥ 20

5x + 8y = 30

x ≥ 0 , y ≥ 0

Persamaan-persamaan yang diperlukan untuk tabel simpleks adalah:

2x + 4y +1S1 + 1A1 + 0A2 = 20

5x + 8y +0S1 + 0A1 + 1A2 = 30

Fungsi Objektif:

f: 7x + 15y +0S1 + MA1 + MA2

26

BAB III

PENUTUP

A. Kesimpulan

Langkah-langkah yang dapat di tempuh dalam menentukan solusi

optimal permasahan program linear dengan metode simpleks adalah :

1. Menentukan medel matematika untuk data-data yang terdapat pada

permasalahan program linier

2. Menambahkan dan melakukan pengurangan dengan variabel ”slack”

(S1,S2,S3), sehingga model matematika dapat diubah menjadi

persamaan linear

3. Membuat kerangka tabel simpleks, merancang program awal, menguji

ke optimalan yang sedang berlangsung

4. Supaya tidak melanggar syarat yang telah ditetapkan, maka di

tambahkan variabel “slack tiruan” (A1,A2,A3)

5. Melakukan perbaikan-perbaikan terhadap program yang berlangsung

sampai diperoleh program optimal.

Langkah- langakah yang dilakukan dalam perbaikan program tersebut

adalah:

a. Menetukan kolom kunci, yaitu kolom yang memiliki nilai “negatif

terbesar” pada baris penilaian.

b. Menentukan baris kunci yaitu baris yang mempunyai bilangan

hasil bagi terkecil (bilangan pada kolom kuantitas dibagi dengan

bilangan negatif pada kolom kunci)

c. Menentukanbilangan kunci, yaitu bialangan yang terdapat pada

persilangan antar kolom kunci dan baris kunci

d. Menurunkan tabel dari tabel program awal ketabel program berikut

nya hasil perbaikan dengan cara:

Melakukan transpormasi baris kunci, yaitu membagi semua

bilangan dalam baris kunci dan bilangan kunci

Melakukan transpormasi bukan baris kunci, dengan rumus

“bilangan baris baru”

27

Program sudah optimal jika baris penilaian tidak memiliki

bilangan nol atau negatif.

B. Kritik dan Saran

Kami sebagai penyusun menyadari bahwa masih terdapat kekurangan

di dalam makalah kami, maka dari itu kritik dan saran yang membangun

dari pembaca sangat kami harapkan.

28

DAFTAR PUSTAKA

Ningsih,Yetri.2013.Bahan Ajar Program Linier.Lubuklinggau

https://www.academia.edu/3449276/

Program_Linear_dengan_Metode_Simplex

29