materi programasi linear

Programa Linier

“Lebih mudah menambahkan sesuatu pada reputasi yang besar daripada untuk memperoleh reputasi itu sendiri.”-

(Publius Syrus)

Sebagian besar dari persoalan manjemen berkenaan dengan penggunaan sumber secara efesien atau alokasi sumber-sumber terbatas seperti tenaga kerja yang terampil, bahan mentah, dan modal untuk mencapai tujuan yang diinginkan perusahaan (desire objective) yaitu penerimaan hasil penjualan yang harus maksimum, penerimaan devisa hasil ekspor harus meningkat, dan yang lainnya. Dalam keadaan sumber yang terbatas harus dicapai suatu hasil yang optimum. Dengan perkataan lain, bagaimana caranya agar dengan masukan (input) yang serba terbatas dapat diperoleh hasil kerja atau keluaran (output) berupa produksi barang atau jasa yang optimum.

Linier Programming akan memberikan solusi permasalahan tersebut dan mampu memberikan alternatif pengambilan tindakan. Akan tetapi, hanya ada satu yang optimum (maksimum atau minimum). Pengambilan suatu keputusan tindakan berarti memilih alternatif yang terbaik (best alternative).

7.1 Pengertian Programa Linier

Dari kata “programming” memiliki sinonim dengan kata perencanaan dan kata “linier” diartikan sesuatu yang berhubungan dengan garis lurus. Sehingga programa linier dapat diartikan sebagai perencanaan aktivitas-aktivitas yang memiliki fungsi linier untuk memperoleh suatu hasil yang optimum, yaitu suatu hasil yang terbaik diantara seluruh alternatif solusi yang fisibel.

Perencanaan aktivitas dimaksudkan untuk mencari cara yang terbaik dalam mengalokasikan sumber-sumber daya yang sifatnya terbatas untuk melaksanakan aktivitas-aktivitas bersaing tersebut.

Definisi:Suatu fungsi f (x1,x2, ...., xn) dari x1,x2, ...., xn adalah fungsi yang linier jika dan hanya jika untuk sejumlah set konstanta c1,c2, ...., cn berlaku f (x1,x2, ...., xn) = c1x1 + c2x2 + .... + cnxn

1

Sebagai contoh, f (x1,x2) = 2 x1 + x2 adalah fungsi linier dari x1 dan x2, tetapi fungsi f(x1,x2) = 2 x1

2 + x2 bukan fungsi linier dari x1 dan x2 (fungsi kuadrat).

Untuk setiap fungsi linier f (x1,x2, ...., xn) dan setiap bilangan b, ketidaksamaan f (x1,x2, ...., xn) ≤ b dan f (x1,x2, ...., xn) ≥ b dengan f (x1,x2) = 2 x1 + x2 adalah bentuk ketidaksamaan linier, sedangkan f (x1,x2, ...., xn) ≤ b dan f (x1,x2, ...., xn) ≥ b dengan f (x1,x2) = 2 x1

2 + x2 bukanlah ketidaksamaan linier.

Model-model programa linier dapat diterapkan dalam berbagai operasi bisnis dan industri dimana dapat diperoleh hasil yang maskimum dan minimum. Misalnya: penetapan keluaran mesin yang maskimum, tingkat persediaan ideal, campuran produk terbaik, masalah transportasi, masalah penugasan (assigment problem), penganggaran modal (capital budgeting), pemilihan media iklan, dan sebagainya.

7.2 Model Programa Linier

Model programa linier dapat ditunjukkan dari tabel 7.1 berikut ini:

Tabel 7.1 Model Programa Linier

Sumber (i)Penggunaan Sumber/unit (j) Banyaknya Sumber

yang dapat Digunakan1 2 ... n1 a11 a12 ... a1n b1

2 a21 a22 ... a2n b2

... ...

... ...m am1 am2 ... amn bm

Keuntungan/unit c1 c2 ... cn

Tingkat x1 x2 ... xn

Keterangan:

1.(1, 2, ..., m) menyatakan sumber daya yang digunakan terhadap aktivitas2.(1, 2, ..., n) menyatakan aktivitas3.(c1, c2, ..., cn) menyatakan koefesien keuntungan (biaya) per unit dari

penggunaan sumber-sumber daya4.(x1, x2, ..., xn) menyatakan koefisen tingkat aktivitas yang dijadikan variabel

keputusan untuk j = 1,2,..., n5.(b1, b2, ..., bm) menyatakan banyaknya sumber i yang dapat digunakan dalam

pengalokasian dengan i = 1, 2, ..., m.6.Sehingga diperoleh a11 atau aij dimana banyak sumber i yang digunakan

untuk masing-masing unit aktivitas j, dengan i = 1, 2, ..., m dan j = 1, 2, ...., n.

Dari keterangan di atas maka formulasi model matematis dari persoalan pengalokasian sumber-sumber daya terhadap aktivitas untuk mendapatkan solusi pemecahan yang terbaik sebagai berikut:

2

Maksimumkan Z = c1x1+ c2 x2 + .... + cnxn Berdasarkan pembatas:

a11x1 + a12x2 + .... + a1nxn ≤ b1

a11x1 + a12x2 + .... + a1nxn ≤ b1

am1x1 + am2x2 + .... + amnxn ≤ bm

danx1 ≥ 0, x2 ≥ 0, ...., xn ≥ 0

( Yang dicari adalah nilai dari x1, x2, ...., xn)

7.3 Bentuk Standar Model Programa Linier

Model programa linier dapat memiliki pembatas-pembatas yang bertanda ≤, =, dan ≥ serta variabel yang berupa variabel nonnegatif dan tidak terbatas dalam tanda (unrestricted sign).

Dalam menyelesaikan persoalan programa linier dengan

metode simpleks digunakan bentuk standar yaitu bentuk formulasi yang memiliki sifat-sifat sebagai berikut:

1. Seluruh pembatas harus berbentuk persamaan (bertanda =) dengan ruas kanan nonnegatif

2. Seluruh variabel harus merupakan variabel nonnegatif3. Fungsi tujuannya dapat berupa maksimasi atau minimasi

Apabila bentuk formulasinya belum standar maka harus diubah ke dalam bentuk standar dengan cara-cara sebagai berikut:

1. Pembatas (Constraint)

a. Pembatas yang bertanda ≤ atau ≥ dapat dijadikan suatu persamaan (bertanda =) dengan menambahkan atau mengurangi dengan suatu variabel slack pada ruas kiri pembatasnya.

Ilustrasi 1

x1 + 2x2 ≤ 6

Maka kita menambahkan slack S1 ≥ 0 pada ruas kiri sehingga diperoleh persamaan :

x1 + 2x2 + S1 = 6, S1 ≥ 0

3

Jika pembatas di atas menyatakan batas penggunaan suatu sumber, maka S1 akan menyatakan banyaknya sumber yang tidak terpakai.

Ilustrasi 2

3x1 + 2x2 – 3x3 ≥ 5

Karena ruas kiri lebih besar dari ruas kanan maka dikurangkan dengan variabel slack S2 ≥ 0 pada ruas kiri sehingga diperoleh persamaan :

x1 + 2x2 – 3x3 – S2 = 5, S2 ≥ 0

b. Ruas kanan dari suatu persamaan dapat dijadikan bilangan nonnegatif dengan cara mengalikan kedua ruas dengan -1.

Ilustrasi 3

2x1 – 3x2 – 7x3 = -5 maka dikalikan -1 menjadi

-2x1 + 3x2 + 7x3 = 5

c. Arah ketidaksamaan dapat berubah apabila dikalikan dengan -1.

Ilustrasi 4

2x1 – x2 ≤ -5 adalah sama dengan -2x1 + x2 ≥ 5

d. Pembatas dengan ketidaksamaan ruas kirinya berada dalam tanda mutlak dapat diubah menjadi dua ketidaksamaan.

Ilustrasi 5

untuk b ≥ 0, | a1 x1 + a2 x2 | ≤ b adalah sama dengan

a1 x1 + a2 x2 ≤ b dan a1 x1 + a2 x2 ≥ -b

Ilustrasi 6

untuk q ≥ 0, | p1 q1 + p2 q2 | ≥ q adalah sama dengan

p1 q1 + p2 q2 ≥ q dan p1 q1 + p2 q2 ≤ -q

2. Variabel

Suatu variabel yi yang tidak terbatas dalam tanda dapat dinyatakan sebagai variabel nonnegatif dengan menggunakan substitusi:

yi = yi’ – yi” dimana yi’ dan yi” ≥ 0

Subsitusi seperti ini harus dilakukan pada seluru pembatas dan fungsi tujuannya.

3. Fungsi Tujuan

Walaupun model standar programa linier berbentuk maksimasi dan minimasi, kadang-kadang diperlukan perubahan dari satu bentuk ke bentuk

4

yang lainnya. Dalam hal ini, maksimasi dari suatu fungsi tujuan adalah sama dengan minimasi dari negatif fungsi tujuan yang sama.

Ilustrasi 7

Maksimumkan z = 5x1 + 2x2 + 3x3

Secara matematis adalah sama dengan:

Minimumkan (-z) = -5x1 – 2x2 – 3x3

7.4 Metode Pemecahan Programa Linier

Untuk memecahkan persoalan-persoalan model programa linier digunakan metode grafis (dua dimensi) dan metode simpleks, dimana kedua metode tersebut bertujuan untuk mencari solusi dari beberapa alternatif solusi yang dibentuk oleh persamaan-persamaan pembatas (constraint) sehingga diperoleh nilai fungsi tujuan yang optimum.

7.4.1 Metode Grafis

Metode grafis dapat digunakan untuk persoalan programa linier yang memiliki dua variabel keputusan yaitu x1 dan x2 sehingga grafik yang dibuat berdimensi dua. Dengan cara grafis, kita hanya perlu memperhatikan titik ekstrem (titik terjauh) pada ruang solusi atau daerah fisibel.

Ilustrasi 8

Wyndor Glass, Co memproduksi kaca berkualitas tinggi untuk digunakan sebagai jendela dan pintu kaca. Perusahaan ini memiliki tiga buah pabrik (plant) yaitu pabrik 1 yang membuat bingkai aluminium, pabrik 2 membuat bingkai kayu, dan pabrik 3 memproduksi kaca dan merakit produk secara keseluruhan. Perusahaan mendapatkan pesanan berupa dua macam produk baru yang potensial, yaitu pintu kaca setinggi 8 kaki dan bingkai aluminium (produk 1) dan jendela berukuran 4 x 6 kaki dengan bingkai kayu (produk 2).

Karena perusahaan sedang mengalami penurunan pendapatan akibat resesi ekonomi dunia, maka pihak manajemen produksi harus memikirkan kapasitas produksi sehingga mampu menghasilkan dua produk potensial tersebut dengan keuntungan yang besar. Akan tetapi, di pabrik 3 kedua produk tersebut bersaing untuk menggunakan kapasitas produksi yang ada (lihat tabel 4.2). Untuk itu, anda diminta untuk membantu manajer produksi untuk menentukan berapa banyakkah masing-masing produk harus dibuat sehingga diperoleh keuntungan optimal?

Tabel 7.2 Data untuk Wyndor Glass, Co

PabrikKapasitas yang digunakan per unit ukuran produksi per menit

5

Kapasitas yang dapat digunakan

Produk 1 Produk 2

1 1 0 42 0 2 123 3 2 18

Keuntungan $3.000 $5.000Jawaban:

Persoalan di atas termasuk persoalan maksimasi sehingga tujuannya adalah memaksimumkan keuntungan yang diperoleh dari tiap produk dengan menggunakan kapasitas produksi yang terbatas.

Formulasi model matematisnya adalah:

Maksimumkan Z = 3x1+ 5x2

Berdasarkan pembatas:x1 ≤ 4 2x2 ≤ 123x1 + 2x2 ≤ 18danx1 ≥ 0, x2 ≥ 0

Gambar 7.1 ABCDE adalah daerah fisibel untuk (x1, x2)

Dengan adanya pembatas bahwa x1 ≥ 0, dan x2 ≥ 0 maka nilai x1 maupun x2

harus terletak pada sumbu yang positif (Kuadran I) dimana x1 sebagai sumbu horizontal dan x2 sebagai sumber vertikal. Untuk x1 ≤ 4, maka nilai (x1, x2) tidak boleh berada di sebelah kanan garis x1 = 4. Demikian pula halnya untuk 2x2 ≤ 12, maka nilai (x1, x2) tidak boleh berada di atas garis 2x2 = 12 ( atau x2 = 6). Untuk

6

pembatas 3x1 + 2x2 ≤ 18, maka perlu ditentukan nilai dari (x1, x2) yang memenuhi garis 3x1 + 2x2 = 18 ( atau x1 = 6 dan x2 = 9) dan tidak boleh berada disebelah kanan garis. Setelah seluruh pembatas digambarkan dalam grafik, maka kita dapat menentukan solusi optimumnya.

Kemudian langkah terakhir adalah menentukan suatu titik pada daerah fisibel yang memaksimumkan harga Z = 3x1+ 5x2.

a) Nilai Z untuk titik A (0,0) = 3(0) + 5(0) = $0b) Nilai Z untuk titik B (4,0) = 3(4) + 5(0) = $12.000c) Titik C adalah perpotongan antara garis x1 = 4 dan 3x1 + 2x2 = 18 diperoleh

nilai (x1, x2) = 3(4) + 2x2 = 18 sehingga 2x2 = 6 (atau x2 = 3).Maka nilai Z untuk titik C(4,3) = 3(4) + 5(3) = $27.000

d) Titik D adalah perpotongan antara garis 2x2 = 12 dan 3x1 + 2x2 = 18 diperoleh nilai (x1, x2) = 3x1 + 2(6) = 18 sehingga 3x1 = 6 (atau x1 = 2). Maka nilai Z untuk titik C(2,6) = 3(2) + 5(6) = $36.000

e) Nilai Z untuk titik E (0,6) = 3(0) + 5(6) = $30.000

Dipilih titik D (2, 6) karena memberi nilai maksimum terhadap harga Z = 3x1+ 5x2. Sehingga dapat diambil kesimpulan bahwa Wyndor Glass, Co harus memproduksi produk 1 sebanyak 2 unit dan produk 2 sebanyak 6 unit per menit dengan keuntungan yang optimal yaitu $36.000 per menit.

7.4.2 Metode Simpleks

Metode simpleks adalah metode yang paling berhasil dikembangkan untuk memecahkan persoalan programa linier yang memiliki variabel keputusan dan pembatas yang sangat besar. Algoritma simpleks diterangkan dengan menggunakan logika secara aljabar matriks sehingga operasi perhitungan dapat lebih efesien. Untuk lebih memahami mengenai metode simpleks, maka perhatikan kembali model programa linier sebagai berikut:

Maksimumkan atau minimumkan Z = c1x1+ c2 x2 + .... + cnxn Berdasarkan pembatas:

a11x1 + a12x2 + .... + a1nxn = b1

a11x1 + a12x2 + .... + a1nxn = b1

am1x1 + am2x2 + .... + amnxn = bm

xi ≥ 0 (i = 1, 2, ..., n)

Jika didefinisikan:

; ;

7

Maka pembatas dari model tersebut dapat dituliskan dalam bentuk persamaan AX = b dari m persamaan linier dan n variabel, dimana n > m.

Definisi:1. Solusi Basis

Solusi basis untuk AX = b adalah xn+1, xn+2, xn+m dan nilai Z disebut variabel basis (BV) dan variabel-variabel yang dinolkan disebut variabel nonbasis (NBV).

2. Solusi Basis FisibelJika seluruh variabel pada suatu solusi basis berharga nonnegatif, maka solusi itu disebut solusi basis fisibel (BFS).

3. Solusi Fisibel Titik Ekstrim

Adalah solusi fisibel yang tidak terletak pada suatu segmen garis yang menghubungkan dua solusi fisibel lainnya. Jadi titik A(0,0), B(0,6), C(4,3), D(2,6), dan E(4,0) adalah solusi-solusi fisibel titik sudut atau titik ekstrim pada persolan Wyndor Glass, Co.

7.4.3 Algoritma Simpleks

Untuk menyelesaikan persoalan maksimasi programa linier dengan menggunakan metode simpleks, lakukan langkah-langkah berikut:

1. Konversikan formulasi persoalan ke dalam bentuk standar2. Carilah solusi basis fisibel (BFS)3. Jika seluruh NBV mempunyai koefisien nonnegatif (artinya berharga positif atau nol) pada baris fungsi tujuan(baris fungsi z yang biasa disebut baris 0), maka BFS sudah optimal. Jika pada baris 0 masih ada variabel dengan koefisien negatif, pilihlah salah satu variabel yang mempunyai koefisien paling negatif pada baris 0. variabel ini akan masuk sebagai variabel basis sehingga disebut entering variable (EV).

4. Hitung rasio dari pada setiap baris pembatas dimana

EV mempunyai koefesien positif. Variabel basis pada baris pembatas dengan rasio positif terkecil akan berubah menjadi variabel nonbasis yang disebut variabel yang meninggalkan basis atau leaving variabel (LV). 5. Lakukan operasi baris elementer (ERO) untuk membuat koefisien EV pada baris dengan rasio positif terkecil menjadi harga 1 dan 0 pada baris lainnya. 6. Jika ditemukan lebih dari satu baris yang memilki rasio positif terkecil, maka pilihlah salah satu, sebab cara ini tidak mempengaruhi hasil perhitungan akhir.

Ilustrasi 9

8


Berdasarkan pembatas:x1 ≤ 4 2x2 ≤ 123x1 + 2x2 ≤ 18x1, x2 ≥ 0

Jawaban:

Langkah 1: Konversikan ke bentuk standarBaris 0 Z – 3x1+ 5x2 = 0Baris 1 x1 + x3 = 4Baris 2 2x2 + x4 = 12Baris 3 3x1 + 2x2 + x5 = 18

x1, x2 , x3, x4, x5 ≥ 0

Langkah 2: Menentukan Solusi Basis Fisibel (BFS)

Variabel yang dinolkan (variabel nonbasis) = x1 = x2 = 0 diperoleh NBV = { x1, x2} dan Variabel basis (BV) = {Z, x3, x4, x5 }

Iterasi 0

Operasi secara aljabar agar dihasilkan koefisien x1 (EV) pada baris 1 berharga 1 dan pada baris lainnya berharga 0.

Baris 2 : x2 / 2 ; Baris 0 : 5x2 + Z ; Baris 3 : -2x2 + x5

Iterasi 1

9

Baris 3 : x5 / 3 ; Baris 0 : 3x5 + Z ; Baris 1 : -x5 + x3

Iterasi 2

Karena koefesien pada baris 0 telah berharga positif, maka BFS sudah optimal. Diperoleh persamaan Z = 36 – 3/2 x4 – x5 dengan nilai Z = 36 untuk nilai x1

= 2 dan x2 = 6.

Ilustrasi 10

Maksimumkan Z = 60x1+ 30x2 + 20x3

Berdasarkan pembatas:8x1 + 6 x2 + x3 ≤ 484x1 + 2 x2 ≤ 202x1 + 3/2x2 + 3/2x3 ≤ 8 x2 ≤ 5x1, x2, x3 ≥ 0

Jawaban:

Bentuk Standar:Maksimumkan Z = 60x1+ 30x2 + 20x3

10

Berdasarkan pembatas:8x1 + 6 x2 + x3 + x4 = 484x1 + 2 x2 + x5 = 202x1 + 3/2x2 + 3/2x3 + x6 = 8 x2 + x7 = 5x1, x2, x3 ≥ 0

Baris 0 Z – 60x1 - 30 x2 - 20x3 = 0Baris 1 2x1 + 6 x2 + x4 = 48Baris 2 4x1 + 2 x2 + x5 = 20Baris 3 2x1 + 3/2x2 + 3/2x3 + x6 = 8Baris 4 x2 + x7 = 5

Variabel NonBasis (NBV) adalah variabel yang dinolkan agar fungsi tujuan memiliki solusi. NBV = {x1, x2, x3}.

Variabel basis (BV) = {Z, x4, x5, x6, x7}

Iterasi 0

Basic

Variables

Equatio

nZ x1 x2 x3 x4 x5 x6 x7

Solus

iRasio

Z 0 1 -60 -30 -20 0 0 0 0 0 -

x4 1 0 2 6 0 1 0 0 0 48 6

x5 2 0 4 2 0 0 1 0 0 20 5

x6 3 0 2 3/2 3/2 0 0 1 0 8 4

x7 4 0 0 1 0 0 0 1 5 -

Sebab variabel x1 dipilih menjadi entering variable (EV) dan x6 menjadi leaving variable (LV) maka x6 keluar dan digantikan dengan x1 pada iterasi selanjutnya. Demikian seterusnya sehingga diperoleh iterasi mencapai solusi yang fisibel.

Iterasi 1

Basic

Variables

Equatio

nZ x1 x2 X3 x4 x5 x6 x7 Solusi

Z 0 1 0 15 25 0 0 30 0 240

x4 1 0 0 9/2 -3/2 1 0 -1 0 40

x5 2 0 0 -1 -3 0 1 -2 0 4

11

LV

EV

x1 3 0 1 3/4 3/4 0 0 1/2 0 4

x7 4 0 0 1 0 0 0 0 1 5

Baris 3 = x1/2 ; Baris 0 = 60x1 + Z; Baris 1 = - 2x1 + x4 ; Baris 2 = - 4x1 + x5;

Karena harga Z telah positif maka iterasi dihentikan sebab BFS sudah optimal.

BFS-nya adalah : Z = 240; x4 = 40; x5 = 4; x1 = 4; x7 = 5

Ilustrasi 11:

Minimumkan Z = 2x1 – 3x2

Berdasarkan pembatas:x1 + x2 ≤ 4x1 – 2x2 ≤ 6dan x1, x2 ≥ 0

Jawaban:

CARA I

Bentuk Standar:Minimumkan Z = 2x1 – 3x2

Berdasarkan pembatas:x1 + x2 + x3 = 4x1 – 2x2 + x4 = 6dan x1, x2 ≥ 0

Baris 0 Z – 2x1 + 3x2 = 0Baris 1 x1 + x2 + x3 = 4Baris 2 x1 - 2x2 + x4 = 6

Variabel NonBasis (NBV) adalah variabel yang dinolkan agar fungsi tujuan memiliki solusi. NBV = {x1, x2}.

Variabel basis (BV) = {Z, x3, x4}

Iterasi 0

Basic

Variables

Equatio

nZ x1 x2 x3 x4

Solus

iRasio

Z 0 1 -2 3 0 0 0 -

12

EV

LV

x3 1 0 1 1 1 0 4 4

x4 2 0 1 -2 0 1 6 -3

Karena persoalan minimasi maka pilih variabel x2 menjadi entering variable (EV) sebab memiliki nilai positif paling besar.

x3 menjadi leaving variable (LV) maka x3 keluar dan digantikan dengan x1 pada iterasi selanjutnya. Demikian seterusnya sehingga diperoleh iterasi mencapai solusi yang fisibel.

Iterasi 1

Basic

Variables

Equatio

nZ x1 x2 x3 x4 Solusi

Z 0 1 -5 0 -3 0 -12

x2 1 0 1 1 1 0 4

x4 2 0 3 0 2 1 14

Variabel x2 telah bernilai 1 pada baris utama, maka baris 0 dan baris 2 yang harus dinolkan.Baris 0 = -3x2 + Z; Baris 2 = 2x2 + x4

Diperoleh nilai fungsi tujuan telah berharga negatif, maka BFS sudah optimal.

BFS-nya adalah : Z = -12; x2 = 4; x4 = 14

CARA II

Bentuk Standar:Minimumkan Z = 2x1 – 3x2 sama denganMaksimumkan (-Z) = -2x1 + 3x2

Berdasarkan pembatas:x1 + x2 + x3 = 4x1 – 2x2 + x4 = 6dan x1, x2 ≥ 0

Baris 0 -Z + 2x1 - 3x2 = 0Baris 1 x1 + x2 + x3 = 4Baris 2 x1 - 2x2 + x4 = 6

Variabel NonBasis (NBV) adalah variabel yang dinolkan agar fungsi tujuan memiliki solusi. NBV = {x1, x2}. Variabel basis (BV) = {Z, x3, x4}

Iterasi 0

13

EV

Basic

Variables

Equatio

nZ x1 x2 x3 x4

Solus

iRasio

Z 0 -1 2 -3 0 0 0 -

x3 1 0 1 1 1 0 4 4

x4 2 0 1 -2 0 1 6 -3

Karena persoalan maksimasi maka pilih variabel x2 menjadi entering variable (EV) sebab memiliki nilai negatif paling kecil.x3 menjadi leaving variable (LV) maka x3 keluar dan digantikan dengan x1 pada iterasi selanjutnya. Demikian seterusnya sehingga diperoleh iterasi mencapai solusi yang fisibel.

Iterasi 1

Basic

Variables

Equatio


Z 0 -1 5 0 3 0 12

x2 1 0 1 1 1 0 4

x4 2 0 3 0 2 1 14

Variabel x2 telah bernilai 1 pada baris utama, maka baris 0 dan baris 2 yang harus dinolkan.Baris 0 = 3x2 + Z; Baris 2 = 2x2 + x4

Diperoleh nilai variabel pada fungsi tujuan telah berharga positif, maka BFS sudah optimal.

BFS-nya adalah : -Z = 12 (atau Z = -12); x2 = 4; x4 = 14

Ilustrasi 12:

PT Unilever bermaksud memproduksi 2 jenis sabun, yaitu sabun bubuk dan sabun batang. Untuk itu dubutuhkan 2 macam zat kimia, yakni A dan B. Jumlah zat kimia yang tersedia adalah A = 200 kg dan B = 360 kg. Untuk membuat 1 kg sabun bubuk diperlukan 2 kg A dan 6 kg B.Untuk membuat 1 kg sabun batang diperlukan 5 kg A dan 3 kg B.Bila keuntungan yang diperoleh setiap membuat 1 kg sabun bubuk = $3 dan 1 kg sabun batang = $2.

a. Formulasikan persoalan di atas dalam model matematisnyab. Berapa kg jumlah sabun bubuk dan sabun batang yang sebaiknya

dibuat

Jawaban:

14

LV

Tabulasikan persoalan di atas menjadi:

Zat Kimia Sabun Bubuk (x1) Sabun Batang (x2) KapasitasA 2 5 200B 6 3 360

Profit ($) 3 2

a. Formulasi Model Matematis

Maksimumkan Z = 3x1 + 2x2

Berdasarkan pembatas:2x1 + 5x2 ≤ 2006x1 + 3x2 ≤ 360dan x1, x2 ≥ 0

Bentuk Standar:Maksimumkan Z = 3x1+ 2x2

Berdasarkan pembatas:2x1 + 5x2 + x3 = 2006x1 + 3x2 + x4 = 360dan x1, x2 ≥ 0

Baris 0 Z – 3x1 - 2x2 = 0Baris 1 2x1 + 5x2 + x3 = 200Baris 2 6x1 + 3x2 + x4 = 360

Variabel NonBasis (NBV) adalah variabel yang dinolkan agar fungsi tujuan memiliki solusi. NBV = {x1, x2}.

Variabel basis (BV) = {Z, x3, x4}

Iterasi 0

Basic

Variables

Equatio

nZ x1 x2 x3 x4

Solus

iRasio

Z 0 1 -3 -2 0 0 0 -

x3 1 0 2 5 1 0 200 100

x4 2 0 6 3 0 1 360 60

Iterasi 1

15

EV

EV

LV

Basic

Variables

Equatio

nZ x1 x2 x3 x4

Solus

iRasio

Z 0 1 0 -1/2 0 1/2 180 -

x3 1 0 0 4 1 -1/3 80 20

x1 2 0 1 1/2 0 1/6 60 120

Iterasi 2

Basic

Variables

Equatio


Z 0 1 0 0 1/811/2

4190

x2 1 0 0 1 1/4 -1/12 20

x1 2 0 1 0 -1/8 5/24 50


BFS-nya adalah : Z = 190; x2 = 20; x1 = 50

Sehingga PT Unilever harus membuat 20 kg sabun batang dan 50 kg sabun bubuk untuk mendapatkan keuntungan optimal sebesar $190.

7.4.4 Metode Big M (Metode Penalty)

Pada persoalan yang sebelumnya, pembatas hanya terdiri dari tanda (). Sekarang timbul pertanyaan, bagaimana jika pembatasnya tidak hanya tanda (), tetapi juga tanda (=), dan ().

a) Untuk pembatas (=), maka daerah fisibelnya hanya berupa segmen garis sehingga tidak ada variabel slack yang dapat digunakan sebagai basis awal sebagai solusi fisibel basis awalnya.

Ilustrasi 133x1 + 2x2 = 18

maka daerah fisibelnya hanya berupa segmen garis yang menghubungkan titik (0,6) dan titik (0,9).

b) Untuk pembatas (), maka tidak dapat diperoleh solusi fisibelnya, sebab ruas kanannya berharga negatif.

16

LV

Ilustrasi 143x1 + 2x2 18 sama saja dengan -3x1 – 2x2 -18

Dengan menambahkan variabel slack menjadi -3x1 – 2x2 + x3 -18. Jika Variabel yang dinolkan (variabel nonbasis) = x1 = x2 = 0 diperoleh NBV = { x1, x2} maka x3 = -18 sehingga tidak dapat dijadikan Variabel basis (BV). Untuk itu diperlukan variabel palsu (dummy) yang disebut variabel artifisial, sehingga variabel basis awal tetap ada.

Ilustrasi 15


Berdasarkan pembatas:x1 ≤ 4 2x2 ≤ 123x1 + 2x2 = 18x1, x2 ≥ 0

Jawaban:

Untuk persoalan maksimasi, maka penalty yang diberikan bertanda (-) dan jika persoalan minimasi, maka penalty yang diberikan bertanda (+).

Maksimumkan Z = 3x1+ 5x2 - M

Berdasarkan pembatas: x1 + x3 = 4 2x2 + x4 = 12

3x1 + 2x2 + = 18

Diperoleh nilai = 18 – 3x1 – 2x2 maka masukkan nilai tersebut ke dalam persamaan Z:

Z = 3x1+ 5x2 – M(18 - 3x1 – 2x2 ) = 3x1+ 5x2 – 18M + 3Mx1 + 2Mx2

Z = (3M + 3) x1 + (2M + 5) x2 – 18M sehingga Z - (3M + 3)x1 - (2M + 5) x2 + 18M

Langkah 1: Konversikan ke bentuk standarnya

Baris 0 Z - (3M + 3)x1 - (2M + 5) x2 + 18M = 0Baris 1 x1 + x3 = 4Baris 2 2x2 + x4 = 12Baris 3 3x1 + 2x2 + = 18

x1, x2 , x3, x4, ≥ 0

17

Langkah 2: Menentukan Solusi Basis Fisibel (BFS)

Variabel yang dinolkan (variabel nonbasis) = x1 = x2 = 0 diperoleh NBV = { x1, x2} dan Variabel basis (BV) = {Z, x3, x4, }

Iterasi 0

Basic

Variables

Equatio

nZ x1 x2 x3 x4 Solusi Rasio

Z 0 1 (-3M – 3) (-2M – 5) 0 0 0 0 -18M

x3 1 0 1 0 1 0 0 4 4/1=4

x4 2 0 0 2 0 1 0 12 12/0

3 0 3 2 0 0 1 18 18/3=6

Baris 1 = (3M + 3)x3 + ZBaris 3 = - 3x3 +

Iterasi 1

Basic

Variables

Equatio


Z 0 1 0 (-2M – 5) (3M + 3 ) 0 0 (-6M + 12)

x1 1 0 1 0 1 0 0 4 4/0

x4 2 0 0 2 0 1 0 12 12/2=6

3 0 0 2 -3 0 1 6 6/2=3

Baris 3 = /2 Baris 0 = (2M + 5) + ZBaris 2 = -2 + x4

Iterasi 2

Basic

Variables

Equatio


Z 0 1 0 0 9/2 0 (M+5/2) 27

x1 1 0 1 0 1 0 0 4 4/1=4

18

EV

EV

EV

x4 2 0 0 0 3 1 -1 6 6/3=2

x2 3 0 0 1 -3/2 0 1/2 3 3/(-3/2)

Baris 2 = x4/3 Baris 0 = 9/2 x4 + ZBaris 1 = - x4 + x1 Baris 3 = 3/2 x4 +

Iterasi 3

Basic

Variables

Equatio


Z 0 1 0 0 0 9/6 M + 1 36

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

x3 2 0 0 0 1 1/3 -1/3 2

x2 3 0 0 1 0 3/6 0 6

Karena koefesien pada baris 0 telah berharga positif, maka BFS sudah optimal. Diperoleh persamaan Z = 36 – 9/6 x4 + (M + 1) dengan nilai Z = 36 untuk nilai x1 = 2 dan x2 = 6.

Ilustrasi 13

Minimumkan Z = 3x1+ 5x2

Berdasarkan pembatas:x1 4 2x2 = 123x1 + 2x2 18x1, x2 ≥ 0

Jawaban:

Minimumkan Z = 3x1 + 5x2 + M + MBerdasarkan pembatas: x1 + x3 = 4

2x2 + = 12 3x1 + 2x2 – x5 + = 18

Perhatikan: Soal Minimasi maka Tanda M (+)

Subsitusi Nilai = 12 – 2x2

= 18 – 3x1 – 2x2 + x5

Sehingga diperoleh Persamaan Z:

Z = 3x1+ 5x2 + M(12 – 2x2) + M(18 – 3x1 – 2x2 + x5)

19

Z = 3x1+ 5x2 + 12M – 2Mx2 +18M – 3Mx1 – 2Mx2 + Mx5

Z = (-3M + 3) x1 + (-4M + 5) x2 + Mx5 + 30M sehingga Z – (-3M + 3) x1 – (-4M + 5) x2 – Mx5 = 30M

Langkah 1: Konversikan ke bentuk standarnya

Baris 0 Z - (-3M + 3)x1 - (-4M + 5) x2 – Mx5 = 30MBaris 1 x1 + x3 = 4Baris 2 2x2 + = 12Baris 3 3x1 + 2x2 – x5 + = 18

x1, x2 , x3, , x5, ≥ 0Langkah 2: Menentukan Solusi Basis Fisibel (BFS)

Variabel yang dinolkan (variabel nonbasis) = x1 = x2 = x5 = 0 agar nilai Z mempunyai solusi sehingga diperoleh NBV = { x1, x2, x5}.Variabel basis (BV) = {Z, x3, , }

Iterasi 0

Basic

Variables

Equa

tionZ x1 x2 x3 x5 Solusi Rasio

Z 0 1 (3M – 3) (4M – 5) 0 0 -M 0 30M -

x3 1 0 1 0 1 0 0 0 4 -

2 0 0 2 0 1 0 0 12 6

3 0 3 2 0 0 -1 1 18 9

Baris 2 = x2 /2 ;Baris 0 = - (4M – 5)x2 + Z;Baris 3 = - 2 x2 +

Iterasi 1

Basic

Variables

Equa

tionZ x1 x2 x3 x5 Solusi Rasio

Z 0 1 (3M – 3) 0 0 (-2M + 5/2) -M 0 6M + 30 -

x3 1 0 1 0 1 0 0 0 4 4

x2 2 0 0 1 0 1/2 0 0 6 -

20

EV

LV

LV

EV

3 0 3 0 0 -1 -1 1 6 2

Baris 2 = x2 /2 ;Baris 0 = - (4M – 5)x2 + Z;Baris 3 = - 2 x2 +

Iterasi 2

Basic

Variables

Equa

tionZ x1 x2 x3 x5 Solusi

Z 0 1 0 0 0 (-M + 3/2) -1 (-M + 1) 36

x3 1 0 0 0 1 1/3 1/3 -1/3 2

x2 2 0 0 1 0 1/2 0 0 6

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

Baris 3 = x1/3; Baris 0 = -(3M – 3)x1 + Z; Baris 1 = - x1 + x3

Karena harga Z telah negatif maka iterasi dihentikan sebab BFS sudah optimal.BFS-nya adalah : Z = 36; x3 = 2; x2 = 6; x1 = 2

7.4.5 Metode Dua Fasa

Dengan digunakannya konstanta M yang merupakan bilangan positif yang sangat besar sebagai penalty, maka dapat saja terjadi kesalahan perhitungan disebabkan koefesien fungsi tujuan relatif sangat kecil dibandingkan dengan harga M, sehingga koefesien tersebut dapat saja dianggap nol apabila perhitungan dilakukan dengan komputer (software). Sebagai contoh, apabila M = 1000, maka koefesien x1 dan x2 pada fungsi tujuan menjadi (3000 – 3).

Kesulitan tersebut dapat diminimalisir dengan menggunakan metode dua fase, dimana konstanta M dihilangkan dengan cara menyelesaikan persoalan dalam dua fase, yaitu:

FASE I :

Fase ini digunakan untuk menguji apakah persoalan yang dihadapi memiliki solusi fisibel atau tidak. Pada fase ini, fungsi tujuan semula diganti dengan meminimumkan jumlah variabel artifisialnya.

Jika nilai minimum fungsi tujuan baru berharga 0, artinya variabel artifisialnya berharga 0 sehingga persoalan memiliki solusi fisibel.

Tetapi, jika nilai fungsi tujuan baru berharga positif, maka persoalan tidak memiliki solusi fisibel. STOP!

FASE II:

21

Gunakan solusi basis optimum dari fase 1 sebagai solusi awal bagi persoalan semula. Dalam hal ini, ubahlah bentuk fungsi tujuan fase 1 dengan mengembalikannya pada fungsi tujuan persoalan semula. Pemecahan persoalan dilakukan dengan cara seperti biasa.

Ilustrasi 14:


Berdasarkan pembatas:x1 ≤ 4 2x2 ≤ 123x1 + 2x2 = 18x1, x2 ≥ 0x1, x2 ≥ 0

Jawaban:Maksimumkan Z = 3x1+ 5x2 - MBerdasarkan pembatas: x1 + x3 = 4

2x2 + x4 = 12 3x1 + 2x2 + = 18

Diperoleh nilai = 18 – 3x1 – 2x2

Fase I

Minimumkan r = atau r = 18 – 3x1 – 2x2

Berdasarkan pembatas:x1 + x3 = 4 2x2 + x4 = 123x1 + 2x2 + = 18

x1, x2, x3, x4, ≥ 0

Baris 0 r + 3x1 + 2x2 = 18Baris 1 x1 + x3 = 4Baris 2 2x2 + x4 = 12Baris 3 3x1 + 2x2 + = 18

x1, x2 , x3, x4, ≥ 0

Variabel yang dinolkan (variabel nonbasis) = x1 = x2 = 0 diperoleh NBV = { x1, x2} dan Variabel basis (BV) = {r, x3, x4, }

22

Iterasi 0

Basic

Variables

Equatio

nr x1 x2 x3 x4 Solusi Rasio

r 0 1 3 2 0 0 0 18

x3 1 0 1 0 1 0 0 4 4

x4 2 0 0 1 0 1 0 12 -

3 0 3 2 0 0 1 18 6

Baris 0 = -3x3 + r Baris 3 = - 3x3 +

Iterasi 1

Basic

Variables

Equatio

nR x1 x2 x3 x4 Solusi Rasio

r 0 1 0 2 -3 0 0 6

X1 1 0 1 0 1 0 0 4 -

x4 2 0 0 2 0 1 0 12 6

3 0 0 2 -3 0 1 6 3

Baris 3 = /2Baris 0 = -2 + rBaris 2 = -2 + x4

Iterasi 2

Basic

Variables

Equatio

nr x1 x2 x3 x4 Solusi

r 0 1 0 0 0 0 -1 0

x1 1 0 1 0 1 0 0 4

x4 2 0 0 0 3 1 -1 6

x2 3 0 0 1 -3/2 0 1/2 3

Karena koefesien pada baris 0 telah berharga negatif (persoalan minimum), maka BFS sudah optimal. Diperoleh nilai x1 + x3 = 4, 3x3 + x4 = 6, dan x2 – 3/2x3 = 3, dimana nilai tidak diikutsertakan lagi pada fase II.

23

EV

EV

LV

LV

Fase II

Dari tabel optimum pada fase I diperoleh persamaan berikut:x1 + x3 = 4 dimana x1 = 4 – x3 3x3 + x4 = 6 x2 – 3/2x3 = 3 dimana x2 = 3 + 3/2x3

Substusikan persaman di atas ke dalam persamaan Z (model persoalan semula), diperoleh:

Maksimumkan Z = 3(4 – x3) + 5(3 + 3/2x3) atau Z = 12 – 3x3 + 15 + 15/2 x3

Z = 9/2 x3 + 27

Berdasarkan pembatas:x1 + x3 = 4 3x3 + x4 = 6 x2 – 3/2x3 = 3

Baris 0 Z – x3 = 27Baris 1 x1 + x3 = 4Baris 2 3x3 + x4 = 6Baris 3 x2 – 3/2x3 = 3

Variabel Nonbasis (NBV) = {x3} (dinolkan agar nilai Z mempunyai solusi) sehinggaVariabel basisnya (BV) = {Z, x1, x4, x2}

Iterasi 0

Basic

Variables

Equatio


Z 0 1 0 0 -9/2 0 27 -

x1 1 0 1 0 1 0 4 4

x4 2 0 0 0 3 1 6 2

x2 3 0 0 1 -3/2 0 3 -2

Baris 2 = x3/3 ; Baris 0 = 9/2x3 + Z; Baris 1 = - x3 + x1; Baris 3 = 3/2 x3 + x2

Iterasi 1

Basic

Variables

Equatio


Z 0 1 0 0 0 3/2 36

24

EV

LV

x1 1 0 1 0 0 -1/3 2

x3 2 0 0 0 1 1/3 2

x2 3 0 0 1 0 1/2 6

Karena koefesien pada baris 0 telah berharga positif (persoalan maksimum), maka BFS sudah optimal. Diperoleh nilai x1 = 2, dan x2 = 6 dengan Z = 36.

Ilustrasi 15:


Berdasarkan pembatas:x1 4 2x2 = 123x1 + 2x2 18x1, x2 ≥ 0

Jawaban:

Minimumkan Z = 3x1+ 5x2 + M + M

Berdasarkan pembatas: x1 + x3 = 4 2x2 + = 12

3x1 + 2x2 – x5 + = 18

Subsitusi Nilai = 12 – 2x2

= 18 – 3x1 – 2x2 + x5

Fase I

Minimumkan r = + r = 12 – 2x2 + 18 – 3x1 – 2x2 + x5

r = 30 – 3x1 – 4x2 + x5

Berdasarkan pembatas: x1 + x3 = 4 2x2 + = 12

3x1 + 2x2 – x5 + = 18Bentuk standar

Baris 0 r + 3x1 + 4x2 + x5 = 30Baris 1 x1 + x3 = 4Baris 2 2x2 + = 12Baris 3 3x1 + 2x2 – x5 + = 18

x1, x2 , x3, , x5,

≥ 0

25

Variabel yang dinolkan (variabel nonbasis) = x1 = x2 = x5 = 0 agar nilai Z mempunyai solusi sehingga diperoleh NBV = { x1, x2, x5}.

Variabel basis (BV) = {r, x3, , }

Iterasi 0

Basic

Variables

Equa

tionr x1 x2 x3 x5 Solusi Rasio

r 0 1 3 4 0 0 1 0 30 -

x3 1 0 1 0 1 0 0 0 4 -

2 0 0 2 0 1 0 0 12 6

3 0 3 2 0 0 -1 1 18 9

Baris 2 = x2 /2 ;Baris 0 = -4x2 + Z;Baris 3 = - 2 x2 +

Iterasi 1

Basic

Variables

Equa


r 0 1 3 0 0 -2 -1 0 6 -

x3 1 0 1 0 1 0 0 0 4 4

x2 2 0 0 1 0 1/2 0 0 6 6

3 0 3 0 0 -1 -1 1 6 2

Baris 3 = x1 /3 ;Baris 0 = -3x1 + Z; Baris 1 = - x3 + x1

Iterasi 2

Basic

Variables

Equa

tionr x1 x2 x3 x5 Solusi

r 0 1 0 0 0 -1 0 -1 0

x3 1 0 0 0 1 1/3 1/3 -1/3 2

x2 2 0 0 1 0 1/2 0 0 6

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

26

EV

LV

LV

EV

Persoalan memiliki solusi fisibel.

Fase II

Dari tabel optimum pada fase I diperoleh persamaan berikut: x3 + 1/3x5 = 2

x2 = 6x1 - 1/3x5 = 2 dimana x1 = 2 + 1/3x5


Minimumkan Z = 3(2 + 1/3x5) + 5(6) atau Z = 6 + x5 + 30

Z = x5 + 36Berdasarkan pembatas:

x3 + 1/3x5 = 2 x2 = 6

x1 - 1/3x5 = 2

Baris 0 Z - x5 = 36Baris 1 x3 + 1/3x5 = 2Baris 2 x2 = 6Baris 3 x1 – 1/3x3 = 2

Variabel Nonbasis (NBV) = {x5} (dinolkan agar nilai Z mempunyai solusi) sehinggaVariabel basisnya (BV) = {Z, x3, x2, x1}

Iterasi 0

Basic

Variables

Equatio

nZ x1 x2 x3 X5 Solusi

Z 0 1 0 0 -1 0 36

x3 1 0 0 0 1 1/3 2

x2 2 0 0 1 0 0 6

x1 3 0 1 0 0 -1/3 2


BFS-nya adalah : Z = 36; x3 = 2; x2 = 6; x1 = 2

Ilustrasi 16:

Suatu Perusahaan memproduksi minuman jeruk yang merupakan kombinasi dari air soda manis dan air jeruk manis.

Setiap liter air jeruk mengandung 0,25 liter gula dan 3 mililiter Vitamin C.

27

Setiap liter air soda mengandung 0,5 liter gula dan 1 mililiter Vitamin C.Biaya produksi 1 liter air jeruk = Rp 3000Biaya produksi 1 liter air soda = Rp 2000

Bagian pemasaran menentukan bahwa setiap 10 liter minuman jeruk harus mengandung sedikitnya 20 mililiter Vitamin C dan paling banyak 4 liter gula. Tentukan produksi dengan biaya minimum!

Jawaban:

a. Formulasi Model Matematis:

Asumsi : x1 = air jeruk x2 = air soda

Source(liter)

Kapasitas yang digunakan Kapasitas digunakanAir Jeruk Air Soda

Vitamin C 0,003 0,001 0,02Gula 0,25 0,5 4

Keuntungan Per unit (ribuan)

3 2

Fungsi Tujuan :


Berdasarkan pembatas:0,003x1 + 0,001x2 0,02 (x1000) = 3x1 + x2 20 (1)0,25 x1 + 0,5 x2 ≤ 4 (x 4) = x1 + 2x2 ≤ 16 (2)

x1 + x2 = 10 (3)dan x1, x2 0

Jawaban:

Bentuk Standar:Minimumkan Z = 3x1+ 5x2 + M + M

Berdasarkan pembatas:3x1 + x2 – x3 + = 20 x1 + 2x2 + x4 = 16 x1 + x2 + = 10

x1, x2, x3, x4, , 0

FASE I

Minimumkan r = + r = (20 – 3x1 – x2 + x3) + (10 – x1 – x2)

28

r = 30 – 4x1 – 2x2 + x3

Berdasarkan pembatas:3x1 + x2 – x3 + = 20 x1 + 2x2 + x4 = 16 x1 + x2 + = 10

x1, x2, x3, x4, , 0

Baris 0 r + 4x1 + 2x2 – x3 = 30Baris 1 3x1 + x2 – x3 + = 20 Baris 2 x1 + 2x2 + x4 = 16Baris 3 x1 + x2 + = 10

Iterasi 0

Basic

Variables

Equa

tionr x1 x2 X3 x4 Solusi Rasio

r 0 1 4 2 -1 0 0 0 30

x3 1 0 3 1 -1 1 0 0 20 20/3

2 0 1 2 0 0 1 0 16 16/1

3 0 1 1 0 0 0 1 10 10/1

Baris 1 = x1/3Baris 0 = -4x1+ ZBaris 2 = -x1 + Baris 3 = - x2 +

Iterasi 1

Basic

Variables

Equa


r 0 1 0 2/3 1/3 -4/3 0 0 10/3

x1 1 0 1 1/3 -1/3 1/3 0 0 20/3 20

2 0 0 5/3 1/3 -1/3 1 0 28/3 28/5

3 0 0 2/3 1/3 -1/3 0 1 10/3 20

Baris 2 = x2 * 3/5; Baris 0 = -2/3x2 + Z; Baris 1 = -1/3x2 + x1; Baris 3 = (-2/3)x2 +

29

EV

LV

LV

EV

Iterasi 2

Basic

Variables

Equa


r 0 1 0 0 1/5 -6/5 -2/5 0 -2/5 -

x1 1 0 1 0 -2/5 2/5 -1/5 0 24/5 -12

x2 2 0 0 1 1/5 -1/5 3/5 0 28/5 28

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

Iterasi 3

Basic

Variables

Equa

tionr x1 x2 x3 x5 Solusi

r 0 1 0 0 0 -1 -1 0 -6

x1 1 0 1 0 0 0 1 0 16

x3 2 0 0 1 1 -1 3 0 28

3 0 0 0 0 0 -1 1 -6

Baris 2 = x3 * 5; Baris 0 = -1/5x3 + Z;Baris 1 = 2/5x3 + x1; Baris 3 = (-1/5)x3 +

Persoalan memiliki solusi fisibel.

Fase II

Dari tabel optimum pada fase I diperoleh persamaan berikut:x1 + x5 = 16 dimana x1 = 16 – x5

x2 + x3 + 3x5 = 28 dimana x2 = 28 – x3 – 3x5 -x5 = -6


Minimumkan Z = 3(16 – x5) + 2(28 – x3 – x5) atau Z = 48 – 3x5 + 56 – 2x3 – 2x5

Z = -2x3 – 5x5 + 104

Berdasarkan pembatas:

30

EV

LV

EV

LV

x1 + x5 = 16 x2 + x3 + 3x5 = 28 -x5 = -6

Baris 0 Z + 2x3 + 5x5 = 104Baris 1 x1 + x5 = 16 Baris 2 x2 + x3 + 3x5 = 28Baris 3 -x5 = -6 Variabel Nonbasis (NBV) = {x3, x5} (dinolkan agar nilai Z mempunyai solusi) sehinggaVariabel basisnya (BV) = {Z, x1, x2}

Iterasi 0

Basic

Variables

Equatio


Z 0 1 0 0 2 5 104

x1 1 0 1 0 0 1 16 16

x2 2 0 0 1 1 3 28 28/3

Baris 2 = x5 /3

Baris 0 = -5 x5 + Z

Baris 1 = - x5 + x1

Iterasi 1

Basic

Variables

Equatio


Z 0 1 0 -5/3 1/3 0 171/3 -

x1 1 0 1 -1/3 -1/3 0 20/3 -20

x5 2 0 0 1/3 1/3 1 28/3 28

Baris 2 = x3 * 3; Baris 0 = -1/3 x3 + Z; Baris 1 = 1/3x3 + x1

Iterasi 2

Basic Equatio Z x1 x2 x3 x5 Solusi Rasio

31

EV

LV

EV

LV

EV

Variables n

Z 0 1 0 -2 0 0 143/3

x1 1 0 1 0 0 1 16

x5 2 0 0 1 1 3 28

Karena harga Z telah negatif maka iterasi dihentikan sebab BFS sudah optimal.

BFS-nya adalah : Z = 143/3; x1 = 16; x5 = 28

Soal Latihan

1. Sebuah perusahaan elektronik memproduksi tape recorder dan amplifier yang prosesnya dilakukan di dua stasiun kerja, yaitu perkaritan dan pengetesan. Setiap unit tape recorder memerlukan 2 jam peraktan dan 2 jam pengetesan, sedangkan satu unit amplifier memerlukan 4 jam perakitan dan 3 jam pengetesan.

2. Waktu yang tersedia di departemen perakitan adalah 72 jam/minggu, sedangkan di departemen pengetesan adalah 48 jam/minggu. Kontribusi profit dari tape recorder adalah 25.000/unit dan setiap unit amplifier adalah 50.000/unit. Bagaimana formulasi persoalan di atas agar dapat ditentukan strategi produksi terbaik untuk memberikan kontribusi profit maksimum?

3. Kurina One Auto Corp memproduksi dua jenis mobil, yaitu mobil sedan dan truk. Untuk dapat meraih konsumen berpenghasilan tinggi, perusahaan ini memutuskan untuk melakukan promosi dalam sua macam acara TV, yaitu pada acara hiburan dan acara olahraga. Promosi pada acara hiburan akan disaksikan oleh 7 juta pemirsa wanita dan 2 juta pemirsa pria. Promosi pada acara olahraga akan disaksikan oleh 2 juta pemirsa wanita dan 12 juta pemirsa pria. Biaya promosi pada acara hiburan adalah 5 juta/menit, sedangkan pada acara olahraga biayanya adalah 10 juta/menit.

4. Jika perusahaan menginginkan promosinya disaksikan sedikitnya 18 juta pemirsa wanita dan sedikitnya 24 juta pemirsa pria, bagaimanakah strategi promosi itu sebaiknya dirancang?

32

LV

5. Perusahan pipa PT Sekar Jaya bergerak dalam bidang produksi pipa-pipa plastik dengan ukuran panjang standar 200 inci. Suatu ketika perusahaan ini mendapat pesanan berupa pipa-pipa berukuran panjang yang tidak standar, yaitu 50, 70, 90 inci dengan jumlah masing-masing pesanan adalah sebagai berikut:

Pesanan Panjang Pipa Kebutuhan Barang (batang)1 50 1502 70 2003 90 300

Yang menjadi persoalan disini adalah menetapkan kombinasi potongan yang harus dilakukan sehingga seluruh jenis pesanan dapat terpenuhi, tetapi dengan meninggalkan sisa yang tak terpakai sekecil-kecilnya (minimum)?

6. Persamaan matematis suatu programa linier sebagai berikut:Dengan pembatas:

2x1 = 183x2 15

6x1 + 5x2 ≥ 30x1, x2 ≥ 0

7. Bahan A dan B dapat diolah menjadi 3 buah produk tipe I, tipe II, tipe III, menurut spesifikasi sebagai berikut:

Bahan Tipe I Tipe IITipe III Bahan

TersediaBahan A ¼ kg/ unit I ½ kg/unit II ¾ kg/ unit III 200 kgBahan B ¾ kg/ unit I ½ kg/ unit II ¼ kg/ unit III 400 kgPerolehan per unit

Rp. 10/unit Rp.14/ unit Rp. 20/unit

Berapa komposisi x1, x2 dan x3 agar persoalan tersebut maksimal!8. Ibu bermaksud membuat 3 jenis kue, yaitu kue brownies, coklat, dan chocochip. Untuk itu dibutuhkan 3 macam bahan, yaitu gula, tepung terigu, dan telur. Jumlah bahan yang tersedia adalah gula = 60 ons dan telur = 40 butir serta tepung terigu = 80 ons.Untuk membuat 1 toples chocochip diperlukan 3 ons gula, 2 butir telur, dan 1 ons terigu.Untuk membuat 1 kotak coklat diperlukan 4 ons gula, 1 butir telur, dan 3 ons terigu.Untuk membuat 1 kotak brownies diperlukan 2 ons gula, 2 butir telur, dan 2 ons terigu.Bila keuntungan yang diperoleh setiap membuat 1 toples chocochip adalah 42 dan 1 kotak coklat adalah $4 serta 1 kotak brownies adalah $3.

33

a. Formulasikan persoalan di atas dalam model matematisnyab. Berapa jumlah kue-kue yang sebaiknya dibuat agar keuntungannya

optimal.

34

materi programasi linear

Documents