program linier dan metode simplex

8/12/2019 Program Linier Dan Metode Simplex

1/39


2/39

Program linier adalah suatu model umum yang dapat

digunakan untuk memecahkan masalah-masalah

pengalokasian sumber-sumber yang jumlahnya terbatas

ke beberapa aktifitas dengan menggunakan sumber-sumber secara optimal, yang mencakup perencanaan

kegiatan untuk mencapai suatu hasil yang

mencerminkan tercapainya sasaran tertentu yang baik (

menurut model matematis) dari alternatif-alternatif yangmungkin, dengan menggunakan fungsi linier.

Retraningsih dan Irhamah, 2011


3/39

Terdapat dua macam fungsi Program Linear yangmerupakan model matematis dari persoalan dikehidupan nyata, yaitu:a. Fungsi tujuan (fungsi objektif) :

memuat tujuan yang ingin dicapai dalam suatupermasalahan.

b. Fungsi kendala (fungsi batasan) :memuat batasan-batasan atau kendala-kendalan

yang ada dalam permasalahan tersebut. Sertamenunjukkan besarnya sumber daya yang tersediadan permintaan atas sumber daya tersebut.


4/39

Sumber

Penggunaan Sumber per Unit AktivitasBanyaknya

sumber yangtersedia

Aktifitas

1 2 ... j ... n

1 a 11 a 12 ... a 1j ... a 1n b 1

2 a 21 a 22 ... a 2j ... a 2n b 2

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

i a i1 a i2 ... a ij ... a in b i

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . .

m a m1 a m2 ... a mj ... a mn b m

Kontribusi per unitaktivitas ( z/unit)

c1 c2 ... cj ... cn

Tingkat Aktivitas x 1 x 2 ... x j ... x n

j : jenis kegiatan j=1, 2, ...,n

i : jenis sumberi=1, 2, ...,m x j : tingkat kegiatan

atau variabelkeputusan

b i : jumlah sumber i yang disediakan

a ij :banyaknya sumber i yang diperlukan untukmembuat 1 unit produk jenis j

c j : kontribusi yang diperoleh/dikeluarkan

jika membuat 1 unit produk j


5/39

Fungsi Objektif:Maksimumkan/minimumkan z=c 1x1 + c2x2 +...+ c ixi +... + c nxn

Fungsi Batasan:a 11x1 + a 12x2 +...+ a 1jx j + ... + a 1nx1n b 1 a 21x1 + a 22x2 +...+ a 2jx j + ... + a 2nx1n b 2 ................................................................

a i1x1 + a i2x2 +...+ a ijx j + ... + a inx1n b

i ................................................................a m1 x1 + a m2 x2 +...+ a mjx j +... + a mn xmn b m x1, x2 , ... , x m 0

Ruas kiri dari fungsi batasan menunjukkan jumlah kebutuhan sumberyang diperlukan untuk melakukan seluruh unit aktivitas

Ruas kanan dari fungsi batasan menunjukkan jumlah sumber yang tersedia

Menunjukkan jumlah sumber 1 yang digunakan untuk membuat

seluruh produk 2

Menunjukkan jumlah seluruhsumber yang digunakan untuk

memproduksi produk 1

Menunjukkan jumlah sumber

2 yang digunakan untukmemproduksi seluruh produk

Fungsi obyektif (z) bisa berbentuk maksimumkan atau minimumkan.

Misalnya z berbentuk maksimum pada kasus yang dioptimalkan berupakeuntungan, dan z berbentuk minimum pada kasus yang dioptimalkanberupa biaya

Suatu model program linier disebut model standar bila

fungsi objektifnya berbentuk maksimumkan ,fungsi batasan bertanda , dan variabel

keputusan bertanda 0


6/39

Sebuah perusahaan textil memiliki sebuah pabrik yang akan memproduksi 2 jenis produk, yaitu kain sutera dan kain wol. Untuk memproduksi keduaproduk diperlukan bahan baku benang sutera dan bahan baku benang wol, sertatenaga kerja. Maksimum penyediaan benang sutera adalah 60 kg per hari,benang wol 30 kg per hari dan tenaga kerja 40 jam per hari. Kebutuhan setiapunit produk akan bahan baku dan jam tenaga kerja dapat dilihat dalam tabelberikut:

Jenis bahanbaku dan tebagakerja

Kain sutera Kain wol

Benang sutera 2 kg 3 kgBenang wol - 2kg

Tenaga kerja 2 jam 1 jam

Kedua jenis produk memberikankeuntungan sebesar Rp 40 juta untuk kainsutera dan Rp 30 juta untuk kain wol.Masalahnya adalah bagaimanamenentukan jumlah unit setiap jenisproduk yang akan diproduksi setiap hariagar keuntungan yang diperoleh bisamaksimal.


7/39

Variabel keputusan (x j) :x1=kain suterax2=kain wol

Fungsi obyektif (z) :maksimumkan z= 40x 1 + 30x 2

Fungsi kendala / batasan :2x1 + 3x 2 60 (benang sutera)

2x2 30 (benang wol)2x1 + x2 40 (tenaga kerja)x1 , x2 0


8/39

Naiknya nilai z proporsionaldengan naiknya x k yaitu melalui

ck xk dan naiknya sumberproporsional dengan naiknya x k

yaitu melalui a ik xk .

Nilai dari semua parametermodel (a ij, b i, dan c j) merupakan

konstanta-konstanta yangdiketahui, bukan suatu variabel

atau variabel random

Semua variabel dapat memilikiharga berapapun asalkan real

Kenaikan nilai z akibat kenaikansuatu kegiatan dapat ditambahtanpa mempengaruhi bagian

nilai z yang diperoleh darikegiatan yang lain


9/39

Metode grafis merupakan salah satu metode yangdigunakan untuk menyelesaikan model program linier

Metode grafis hanya bisa digunakan jika persoalan hanya

mempunyai 2 variabel keputusan


10/39

Langkah 1: Menentukan daerah fisibelDaerah fisibel adalah daerah yang memenuhi semua fungsi batasan,

berikut ini adalah cara menentukan daerah visibel:

Membuat suatu sumbu koordinat dengan sumbu x sebagaisumbu untuk variabel x 1 dan sumbu y untuk variabel x 2

Tanda pertidaksamaan pada semua fungsi batasan diubahmenjadi tanda persamaan

Menggambarkan semua fungsi batasan pada sumbukoordinat

Menentukan daerah yang memenuhi semua fungsibatasan


11/39

Langkah 2: Menentukan penyelesaian optimal Ada 2 metode yang bisa digunakan untuk mencari z optimal, yaitu:

1. Cara grafis

Menggambarkangaris z pada

daerah fisibel

Menggeser garis zkearah kanan untukkasus maksimasi dan

kearah kiri untuk

kasus maksimasi

Z optimal terletak pada titikperpotongan daerah fisibelsebelah kiri dengan garis zuntuk kasus minimumkan,

sedangkan untk kasusmaksimumkan terletak

pada titik perpotongandaerah fisibel sebelahkanan dengan garis z


12/39

2. Cara Analitik

Mencari titik ekstrim, yaitu titik-titik yang berada

pada ujung daerah fisibel

Mencari nilai z pada padatitik-titik ekstrim tersebut.

Z optimal adalah nilai zterbesar pada titik ekstrim

untuk kasusmaksimumkan dan zterkecil pada kasus

minimumkan


13/39

Tanda pertidaksamaan pada semua fungsi batasandirubah menjadi tanda persamaan

2x1 + 3x 2 60 menjadi 2x 1 + 3x 2 = 60

2x2 30 menjadi 2x 2 = 302x1 + x2 40 menjadi 2x 1 + x2 = 40

Membuat sumbu koordinatX2

x1

Menggambarkan garis fungsi batasan

40

20

20 30

2x1 + x2 = 40

2x2 = 30

Menentukan daerah yang memenuhi semuafungsi batasan

15

2x1 + 3x 2 = 60

Menentukan penyelesaian optimum dengan caragrafis

Menentukan penyelesaian optimum secara analitis

(15,10)

(0,0)

(0,15)

(20,0)

(7.5,15)

Titik ekstrim Nilai z (juta)

(0,0) 0

(20,0) 800(15,10) 900

(7.5,15) 750

(0,15) 450

z= 40x 1 + 30x 2

Kesimpulan:Perusahaan akan memperoleh keuntunganoptimal sebesar Rp 900 juta apabilamemproduksi 15 unit kain sutera dan 10 unitkain wol.


14/39


15/39

Apabila persoalan mempunyai lebih dari 2 variabel keputusan,dapat diselesaikan dengan metode simpleks. Misalnya terdapatpersoalan program linier sebagaimana berikut.Maksimumkan/minimumkan z=c 1x1 + c2x2 +...+ c ixi +... + c nxn

Sedemikian rupa hingga memiliki fungsi batasanFungsi Batasan:

a 11x 1 + a 12x 2 +...+ a 1jx j + ... + a 1nx 1n b 1a 21x 1 + a 22x 2 +...+ a 2jx j + ... + a 2nx 1n b 2................................................................a i1x 1 + a i2x 2 +...+ a ijx j + ... + a inx 1n b i................................................................a m1x 1 + a m2x 2 +...+ a mjx j +... + a mn x mn b mx 1, x 2 , ... , x m 0


16/39

Program linier tersebut bila dinyatakan dalambentuk matrik dapat ditulis sebagai berikut:

Maksimumkan/minimumkan z = cxBatasan: Ax b x 0


17/39

Fungsi kendala bertanda diubah menjadi persamaandengan menambahkan variabel slack pada ruas kirifungsi kendala

dirubah menjadi

Fungsi batasan awalUntuk mempermudah penyelesaian persoalan programlinier, maka fungsi batasan dirubah dulu menjadi bentuk

sama dengan


18/39

Fungsi kendala bertanda diubah menjadi persamaandengan mengurangkan variabel surplus pada ruas kirifungsi kendala.

dirubah menjadi

Fungsi batasan awal


19/39

Program linier setelah ditambah variabel slack maupundikurangi variabel surplus dalam bentuk matriks

Maksimumkan/minimumkan z = cx

Batasan: Ax b x 0x = [ x1 x2 ... x j xn xn+1 xn+2 ... x n+i ... x n+m ]T b = [ b 1 b 2 ... b j b m ]T Variabel asli Variabel slack dan/atau variablel surplus


20/39

Metode penyelasaian basis visibel merupakan salah satu darimetode simplek.

[A] dipartisi menjadi [ B N ]dimana A matrik berukuran mx(n+m), B matrik berukuran mxm, danN matrik berukuran nxm.

c dipartisi menjadi [ cB cN ]x dipartisi menjadi [ xB xN ]T

Sehingga z = [ cB

cN

]

Fungsi batasan Ax = b berubah menjadi[ B N ] = b


21/39

Metode penyelasaian basis visibel (2)

Fungsi batasan juga dapat dinyatakan sebagai BxB + Nx N= b, sehingga Bx B = b dan Nx N= 0, maka xB =B -1 b dan xN = 0. x B adalah calon variabel basis dan jika xB 0

maka xB adalah variabel non basis, tetapi jika xB 0 makaxB adalah variabel basis, sedangkan xN adalah variabelnon basis. Jika xB variabel basis, maka nilai xB

dimasukkan pada fungsi obyektif sehingga diperoleh nilaiz. Kemudian memilih z optimal sebagai penyelesaianoptimal


22/39

Baris ke BV z xB xN RHS

0 Z 1 0 cBB-1N-cN cBB-1b

1 s.d m xB 0 I B-1N B-1b

Baris ke BV z xN xB RHS

0 Z 1 cBB-1N-cN 0 cBB-1b

1 s.d m xB 0 B-1N I B-1b

Tabel simplek alternatif

Untuk tabel simplek awal dipilih matrik B = I sehingga matrik B -1 adalah matrik I sendiri. Karena B = I, maka x B adalah variabelslack dan c B = 0. x N adalah variabel asli pada fungsi batasan, Nadalah koefisien variabel asli pada fungsi batasan, sehingga B -1N= N = Y dan c N adalah koefisien fungsi tujuan. Dengan demikiantabel simplek akan berubah menjadi:

Baris ke BV z xN xB RHS

0 Z 1 -cN 0 c0

1 s.d m xB 0 Y I b

TABEL SIMPLEK AWAL


23/39

Langkah 1 : Memeriksa apakah tabel sudah optimum.

Apabila fungsi tujuan maksimumkan, tabel optimum jika semuabaris ke nol lebih besar sama dengan nol (z j-c j 0). Dan apabilafungsi tujuan minimumkan, tabel optimum jika semua baris kenol lebih lebih sama dengan nol (z j-c j 0). Bila belum optimummaka dilanjutkan ke langkah 2.

Langkah 2: Memilih variabel yang masuk basis

Apabila fungsi tujuan maksimumkan, maka pilih elemen bariske nol yang merupakan bilangan negatif terbesar. Apabila fungsitujuan minimumkan, maka pilih elemen baris ke nol yangmerupakan bilangan positif terbesar.


24/39

Langkah 3: Mengecek apakah persoalan memiliki daerah fisibel

Dikatakan memiliki daerah fisibel bila pada kolom terpilihpada baris 1 s.d m ada elemen yang lebih besar dari nol. Jikamemenuhi syarat tersebut, maka lanjutkan ke langkah 4

Langkah 4: Memilih variabel yang akan keluar basis

Untuk memilih variabel yang akan keluar basis, ruas kanan (b i)dibagi dengan y ik , dimana y ik > 0. Hasil bagi terkecil adalah yangdipilih. Bila hasil bagi terkecil terletak pada baris ker r makaxn+r keluar basis

Elemen yang terletak pada baris terpilih pada langkah 3 dankolom terpilih pada langkah 4 disebit sebagai pivot


25/39


26/39

Maksimumkan z = 3x 1 + 5x 2Fungsi batasan:

2x1 8

3x2 15

6x1 + 5x 2 30

x1, x2 0

2x1 + X 3 = 8dirubah menjadi 3X 2+ X 4= 15

6x1 + 5x 2 + X 5 = 30

diubah menjadi z - 3x 1 - 5x2 = 0

baris ke BV z x1 x2 x3 x4 x5 RHS

0 z 1 -3 -5 0 0 0 0

1 x3 0 2 0 1 0 0 8

2 x4 0 0 3 0 1 0 15

3 x5 0 6 5 0 0 1 30

Tabel Simplek AwalTabel belum

optimum


27/39

baris ke BV z x1 x2 x3 x4 x5 RHS Rasio Keterangan

0 z 1 -3 -5 0 0 0 0

1 x3 0 2 0 1 0 0 8

2 x4 0 0 3 0 1 0 15

3 x5 0 6 5 0 0 1 30

x2 masuk basis

Persoalanmempunyai

daerah fisibel

5

6

b i /y ik


0 z 1

1 x3 0

2 x2 0

3 x5 0

Tabel simplek iterasi 1

0 1 0 01/3 5

Semua elemenbaris pivot dibagi

dengan nilai

pivotnya

2 0 1 0 0 8-3 0 0 5/3 0 25

6 0 0 -5/3 1 5

B0+5B2

B3-5B2

B1-0B2

Pivot Jadi, x 4 keluar basis


28/39


0 z 1 -3 0 0 5/3 0 25

1 x3 0 2 0 1 0 0 8

2 x2 0 0 1 0 1/3 0 5

3 x5 0 6 0 0 -5/3 1 5

x1 masuk basisPersoalanmempunyai

daerah fisibel

b i /y ik

pivot Jadi, x 5 keluar basis

4

5/6


0 z 1

1 x3 0

2 x2 0

3 x1 0

Semua elemenbaris pivot dibagi

dengan nilaipivotnya

1 0 0 -5/18 1/6 5/6

0 0 0 5/6 27 B 0+3B30 0 1 5/9 -1/3 6 B1-2B 30 1 0 1/3 0 5 B 2-0B3

Tabel simplek iterasi 2


29/39

Karena pada baris ke nol tidak ada lagi yang bernilai negatif.

Maka tabel sudah optimum, sehingga:

z maksimum = 27 1 / 2, X 1 = 5/6, X 2 = 5

bariske

BV z x1 x2 x3 x4 x5 RHS

0 z 1 0 0 0 5/6 27 1 /21 x3 0 0 0 1 5/9 -1/3 6

1 /3

2 x2 0 0 1 0 1/3 0 5

3 x1 0 1 0 0 -5/18 1/6 5/6


30/39

Metode dua fase digunakan jika fungsi batasan ada yangbertanda lebih besar atau bertanda sama dengan.

Fase satu:Meminimumkan variabel artifisial : Min Y0 = x aFungsi batasan: Ax + x a = b

Apabila persoalan asli memiliki daerah fisibel, maka optimum daripersoalan ini adalah nol, dengan nilai variavel artifisial sama dengan nol.

Fase Dua:Menyelesaikan persoalan program linier dengan penyelesaianbasis fisibel awal x B = B -1b dan x N = 0Maksimumkan/minimumkan z = c BxB + cNxNdengan fungsi batasan : xB +B -1Nx N= B -1b ; x B , xN 0


31/39

Minimumkan z=2x1 + 3x2Fungsi batasan:

2x1+x216

x1+3x220

x1+x2=10

x1,x2 0

2x1+x2+x3=16

x1+3x2-x4+x5=20

x1+x2+x6=10

x1,x2, ..., x 6 0

dirubahmenjadi

Fase satu:Minimumkan Y0 = x

5 + x

6Fungsu batasan : 2x 1+x2+x3=16x1+3x2-x4+x5=20x1+x2+x6=10x1,x2, ..., x 6 0


32/39

baris ke BV Y 0 x1 x2 x3 x4 x5 x6 RHS Rasio Keterangan

0 z 1 0 0 0 0 -1 -1 0 B 0+B2+B31 x3 0 2 1 1 0 0 0 16

2 X5 0 1 3 0 -1 1 0 20

3 x6 0 1 1 0 0 0 1 10


0 z 1 2 4 0 -1 0 0 30 B0+B2+B31 x3 0 2 1 1 0 0 0 16 16

2 X5 0 1 3 0 -1 1 0 20 20/3

3 x6 0 1 1 0 0 0 1 10 10

Tabel simplek awal fase 1

Iterasi 1 pada fase 1


33/39


0 z 1 2/3 0 0 1/3 -4/3 0 10/3 B 0-4B21 x3 0 5/3 0 1 1/3 -1/3 0 28/3 28/5 B 1-B2

2 X2 0 1/3 1 0 -1/3 1/3 0 20/3 20

3 x6 0 2/3 0 0 1/3 -1/3 1 10/3 5 B 3-B2


0 z 1 0 0 0 -1/2 -1 -1 0 B0-2/3 B3 31 x3 0 0 0 1 -1/2 -5/2 1 B1-5/3 B3 3

2 X2 0 0 1 0 -1/2 -1/2 5 B2-1/3 B3 3

3 x1 0 1 0 0 -1/2 3/2 5




34/39

Fase Dua:

Minimumkan z=2x1 + 3x2

Fungsi batasan:

xB +B-1

Nx N= B-1

bxB , xN 0

bariske

BV z x1 x2 x3 x4 RHS Rasio Ket

0 z 1 -2 -3 0 -1/2 0 B0+3B

2+2B

3

1 x3 0 0 0 1 -1/2 1

2 X2 0 0 1 0 -1/2 5

3 x1 0 1 0 0 5

Tabel awal fase II


35/39

Karena semua elemen pada baris ke no tidak ada yangbernilai negatif, maka tabel sudah optimum. Jadizminimum = 25 ketika x 1 =5 dan x 2 =5 = 25

baris ke BV z x1 x2 x3 x4 RHS Rasio Ket

0 z 1 0 0 0 -1/2 25 B 0+3B2+2B3

1 x3 0 0 0 1 -1/2 12 x2 0 0 1 0 -1/2 5

3 x1 0 1 0 0 5


36/39

Metode big M digunakan jika fungsi batasan ada yang bertanda >atau =. Misal terdapat suatu persoalan program linier, dimanafungsi batasan satu dan emapt bertanda , maka model matematisnya adalah sebagai

berikut.

Atau

Maksimumkan z=c 1x1 + c2x2 + c3x3 + c4x4 Mx 8-Mx9

Minimumkan z=c 1x1 + c2x2 + c3x3 + c4x4 + Mx 8+Mx 9


37/39

Dengan fungsi batasana 11x 1 + a 12x 2 +a 13x 3+ a 14x 4 +x 5 =b 1a 21x 1 + a 22x 2 + a 23x 2 + a 24x 4+x 8 = b 2a 31x 1 + a 32x 2 + a 33x 2 + a 34x 4-x 6 +x 9 = b 3a 41x 1 + a 42x 2 + a 43x 2 + a 44x 4+x 8 = b 4

x 1, x 2 , ... , x 9 0

Untuk menyelesaikan persoalan diatas, langkah-langkah yangdilakukan sama seperti menyelesaikan persoalan program liniermenggunakan simplek tabel. Jika persoalan fisibel, maka nilai zoptimum tidak memuat bilangan M


38/39

Pada setiap kali dilakukan iterasi, tabel simplek mempunyaimakna bahwa tabel simplek yang sekarang adalah tabel simpleksebelumnya yang dikalikan dengan matriks B -1, dimana B adalahmatrik dari koefisien variabel basis pada fungsi batasan, oleh karenaitu matrik I pada tabel awal menjadi B -1 pada tabel-tabel berikutnya,

maka elemen dibawah variabel slack pada baris 1 s.d m adalahelemen dari matriks B -1.

1

Fungsi tujuan pada persoalan program linier adalahmengoptimumkan z = c BxB + cNxN , dimana zoptimum=c BB -1b.

Apabila z diturunkan terhadap b, maka z/ b =c BB -1= w i dimana w i adalah elemen baris ke nol dibawah variabel slack . z/b i mempunyaimakna bahwa jika sumber i bertambah sebanyak satu satuan, makanilai z berubah sebesar wi

2


39/39

Nilai variabel basis xB

=B-1

b, jika variabel xB diturunkan

terhadap b, maka x B /b =B -1. x B /b mempunyai makna bahwa jikasember i bertambah satu satuan, maka variabel basis x B bertambahsebesar B i-1, dimana B i-1 adalan elemen dibawah variabel slack ke ipada baris 1 s.d m.

3

Jika variabel basis tidak memuat variabel slack, berarti semuafungsi batasan bertanda sama dengan, oleh karena itu jumlah sumber

yang dibutuhkan sama dengan jumlah sumber yang tersedia, sehinggatidak ada bahan yang tersedia, atau dengan kata lain sumber tersebutadalah sumber yang langka

4

Jika variabel basis memuat variabel slack, maka fungsibatasan yang memuat variabel slack bertanda lebih kecil, artinya

jumlah kebutuhan akan sumber lebih kecil daripada jumlah sumber yang tersedia, sehingga sumber tersebut masih berlebih, dengan katalain sumber tersebut dikatakan sebagai sumber melimpah

5

program linier dan metode simplex

Documents