SI-4SI-4101101 Sistem Rekayasa Sistem Rekayasa

Metode Simplex Dua FaseMetode Simplex Dua Fase

1717 September September 20120122

Minggu-4 Minggu-4

• Untuk persamaan pembatas yang mempunyai pembatas lebih besar sama Untuk persamaan pembatas yang mempunyai pembatas lebih besar sama dengan (≥) , variabel surplus ditambahkan kedalam persamaan. Variabel dengan (≥) , variabel surplus ditambahkan kedalam persamaan. Variabel ini tidak dapat diberikan untuk set variabel basic xini tidak dapat diberikan untuk set variabel basic xBB , sebab hal ini , sebab hal ini melanggar aturan bahwa variabel basic harus bernilai positif, xmelanggar aturan bahwa variabel basic harus bernilai positif, xBB ≥ 0. ≥ 0.

• Metode simplex dua fase mudah untuk dimengerti karena metode ini Metode simplex dua fase mudah untuk dimengerti karena metode ini menghindari kebutuhan untuk melakukan perhitungan dengan memilih menghindari kebutuhan untuk melakukan perhitungan dengan memilih basis awal.basis awal.

• Misalkan masalah pemograman linier sebagai berikutMisalkan masalah pemograman linier sebagai berikut

Minimumkan z = 3xMinimumkan z = 3x11 + 4x + 4x22 + 5x + 5x33

xx11 + x + x22 + x + x33 ≤ 5 ≤ 5

2x2x22 + x + x33 ≥ 2 ≥ 2

xx11 + 3x + 3x22 = 4 = 4

xx11 , x , x22 , x , x33 ≥ 0 ≥ 0

Tambahkan variabel slack dan surplus pada persamaan pembatas pertama Tambahkan variabel slack dan surplus pada persamaan pembatas pertama dan kedua.dan kedua.

Format pemograman linier standar untuk pers. diatas menjadiFormat pemograman linier standar untuk pers. diatas menjadi

Minimumkan z = 3xMinimumkan z = 3x11 + 4x + 4x22 + 5x + 5x33

xx11 + x + x22 + x + x33 + x + x4 4 = 5 = 5

2x2x22 + x + x33 - x - x55 = 2 = 2

xx11 + 3x + 3x22 = 4 = 4

xx11 , x , x22 , x , x33 , x , x44 , x , x55 ≥ 0 ≥ 0

Karena tujuannya adalah untuk memberikan basis awal tanpa menampilkan Karena tujuannya adalah untuk memberikan basis awal tanpa menampilkan perhitungan, xperhitungan, x11 , x , x22 , dan x , dan x33 diberikan untuk x diberikan untuk xNN

00. Variabel kendali x. Variabel kendali x44 dan x dan x55 diberikan untuk xdiberikan untuk xBB

00. Terdapat , tiga persamaan pembatas, m = 3 , basis x. Terdapat , tiga persamaan pembatas, m = 3 , basis xBB00

harus terdiri dari tiga variabel untuk memenuhi persyaratan bahwaharus terdiri dari tiga variabel untuk memenuhi persyaratan bahwa

xxBB00 = A = ABB

-1-1 [b – A [b – ANN x xNN00]]

Secara jelas, variabel xSecara jelas, variabel x11 , x , x22 , atau x , atau x33 harus diberikan pada x harus diberikan pada xBB00. Sayangnya . Sayangnya

penempatan salah satu dari variabel ini dalam xpenempatan salah satu dari variabel ini dalam xBB memerlukan memerlukan perhitungan. Sebagai tambahan, kemungkinan bahwa pemberian ini tidak perhitungan. Sebagai tambahan, kemungkinan bahwa pemberian ini tidak akan memberikan solusi fisibel, x ≥ 0.akan memberikan solusi fisibel, x ≥ 0.

• Jika ini terjadi, variabel lain diberikan untuk xJika ini terjadi, variabel lain diberikan untuk xBB00 dan perhitungan akan dan perhitungan akan

diulang lagi. Metode ini tidak dapat diterima untuk model yang terdiri dari diulang lagi. Metode ini tidak dapat diterima untuk model yang terdiri dari jumlah variabel yang besar. Kita akam menyelidiki contoh ini secara detail jumlah variabel yang besar. Kita akam menyelidiki contoh ini secara detail dan menunjukkan bagaimana variabel artificial dapat digunakan untuk dan menunjukkan bagaimana variabel artificial dapat digunakan untuk membuat suatu solusi fisibel basimembuat suatu solusi fisibel basiss awal. Variabel kon awal. Variabel konttrol xrol x11, x, x22, dan x, dan x33 akan akan diberikan untuk xdiberikan untuk xNN..

• Masing2 persamaan pembatas akan diselidiki secara bebas. Karena xMasing2 persamaan pembatas akan diselidiki secara bebas. Karena x11, x, x22, , dan xdan x33 adalah anggota dari x adalah anggota dari xNN

00 dan sama dengan nol, variabel kontrol x dan sama dengan nol, variabel kontrol x44 dari xdari x11 + x + x22 + x + x33 + x + x44 = 5 sama dengan, x = 5 sama dengan, x44 = 5. = 5.

• Karena xKarena x44 adalah positif dan berkaitan dengan unit harga x adalah positif dan berkaitan dengan unit harga x44 adalah sama adalah sama dengan nol, xdengan nol, x44 adalah sebuah pilihan yang dapat dilakukan untuk basis adalah sebuah pilihan yang dapat dilakukan untuk basis awal. Jadi, xawal. Jadi, x44 dapat diberikan untuk x dapat diberikan untuk xBB

00..

• Untuk 2xUntuk 2x22 + x + x33 – x – x55 = 2, substitusi nol untuk x = 2, substitusi nol untuk x11, x, x22, dan x, dan x33 akan akan memberikan xmemberikan x55 = -2 . Variabel surplus x = -2 . Variabel surplus x55 melanggar aturan yang melanggar aturan yang disyaratkan bahwa variabel basidisyaratkan bahwa variabel basiss adalah positif. adalah positif.

• Persamaan xPersamaan x11 + 3x + 3x22 = 4 memberikan tipe permasalahan yang berbeda. = 4 memberikan tipe permasalahan yang berbeda. Karena xKarena x11 dan x dan x22 diasumsikan anggota x diasumsikan anggota xNN

00 dan sama dengan nol, dan sama dengan nol, persamaan pembatas tidak dapat dipenuhi, (0) + 3 (0) ≠ 4. persamaan pembatas tidak dapat dipenuhi, (0) + 3 (0) ≠ 4.

• Pendekatan dengan metode simplex dua fase membuat pemberian awal Pendekatan dengan metode simplex dua fase membuat pemberian awal variabel kendali untuk xvariabel kendali untuk xBB

00 menjadi lebih mudah. Metode ini menggunakan menjadi lebih mudah. Metode ini menggunakan variabel kendali baru yang disebut variabel buatan/variabel kendali baru yang disebut variabel buatan/artificialartificial. Sebagai ilustrasi, . Sebagai ilustrasi, berikan xberikan x11, x, x22, dan x, dan x33 untuk x untuk xNN

00 dan x dan x44, variabel slack dari x, variabel slack dari x11 + x + x22 + x + x33 + x + x44 = = 5 diberikan untuk x5 diberikan untuk xBB

00..

• Tambahkan variabel xTambahkan variabel x66 pada 2x pada 2x22 + x + x33 – x – x55 = 2 menjadi 2x = 2 menjadi 2x22 + x + x33 – x – x55 + x + x66 = 2. = 2. Variabel kontrol xVariabel kontrol x55 diberikan untuk x diberikan untuk xNN

00. Jadi, nilai variabel artificial adalah x. Jadi, nilai variabel artificial adalah x66 = = 2. Variabel x2. Variabel x66 diberikan untuk x diberikan untuk xBB

00..

• Untuk xUntuk x11 + 3x + 3x22 = 4 , variabel artificial x = 4 , variabel artificial x77 diberikan, sehingga x diberikan, sehingga x11 + 3x + 3x22 + x + x77 = 4 = 4 . Karena x. Karena x11 dan x dan x22 adalah variabel nonbasi adalah variabel nonbasiss, x, x77 harus berupa variabel harus berupa variabel artificial, sehingga nilai variabel artificial adalah xartificial, sehingga nilai variabel artificial adalah x77 = 4. Karena x = 4. Karena x77 adalah adalah positif, diberikan untuk xpositif, diberikan untuk xBB

00. Sehingga vektor basi. Sehingga vektor basiss dan nonbasi dan nonbasiss awal adalah awal adalah xxBB

0’0’ = [x = [x44 x x66 x x77] = [5 2 4]] = [5 2 4] xxNN

0’0’ = [x = [x11 x x22 x x33 x x55] = [0 0 0 0]] = [0 0 0 0]

• Vektor diatas memenuhi persyaratan bahwa xVektor diatas memenuhi persyaratan bahwa xBB00 ≥ 0 dan x ≥ 0 dan xNN

00 = 0 . Persamaan = 0 . Persamaan set pembatas menjadiset pembatas menjadi

xx11 + x + x22 + x + x33 + x + x44 = 5 = 5 2x2x22 + x + x33 - x - x55 + x + x66 = 2 = 2 xx11 + 3x + 3x22 + x + x77 = 4 = 4

• Metode simplex dua fase secara sistematis menghilangkan variabel buatan Metode simplex dua fase secara sistematis menghilangkan variabel buatan dari basis dan memberikannya pada nonbasis dan secara bersamaan dari basis dan memberikannya pada nonbasis dan secara bersamaan menentukan solusi kandidat yang terdiri dari variabel dari formulasi asal. menentukan solusi kandidat yang terdiri dari variabel dari formulasi asal. Untuk mendapatkan solusi optimum dari model matematik asal dicapai Untuk mendapatkan solusi optimum dari model matematik asal dicapai dengan menetapkan fungsi objektif kedua terhadap model.dengan menetapkan fungsi objektif kedua terhadap model.

• Tujuan fungsi objektif kedua adalah untuk menghilangkan variabel buatan Tujuan fungsi objektif kedua adalah untuk menghilangkan variabel buatan dari model dan didalam prosesnya menentukan solusi kandidat yang dari model dan didalam prosesnya menentukan solusi kandidat yang memenuhi persyaratan untuk solusi fisibel basik dengan menggunakan memenuhi persyaratan untuk solusi fisibel basik dengan menggunakan aturan metode simplex.aturan metode simplex.

• Fungsi objektif kedua ditentukan sama dengan penjumlahan variabel Fungsi objektif kedua ditentukan sama dengan penjumlahan variabel buatan:buatan:

w = sum xw = sum xii

dari contoh persamaan sebelumnya dapat ditentukan:dari contoh persamaan sebelumnya dapat ditentukan:

w = xw = x66 + x + x77

w = 6 – xw = 6 – x11 – 5x – 5x22 – x – x33 + x + x55

(w – 6) = – x(w – 6) = – x11 – 5x – 5x22 – x – x33 + x + x55

• Karena semua variabel buatan adalah anggota awal xKarena semua variabel buatan adalah anggota awal xBB dan dengan definisi dan dengan definisi bernilai positif, nilai w harus selalu positif. Tujuannya disini adalah untuk bernilai positif, nilai w harus selalu positif. Tujuannya disini adalah untuk meminimumkan w sampai berkurang menjadi nol. Jika w = 0, semua variabel meminimumkan w sampai berkurang menjadi nol. Jika w = 0, semua variabel buatan akan sama dengan nol. Jika semua variabel buatan anggota dari xbuatan akan sama dengan nol. Jika semua variabel buatan anggota dari xNN , , model adalah sebuah fungsi dari variabel kendali dengan formulasi asal.model adalah sebuah fungsi dari variabel kendali dengan formulasi asal.

• Sehingga kalau disusun kembali model matematik diatas menjadi:Sehingga kalau disusun kembali model matematik diatas menjadi:

Minimumkan (w – 6) = -xMinimumkan (w – 6) = -x11 – 5x – 5x22 – x – x33 + x + x55

Minimumkan z = 3xMinimumkan z = 3x11 + 4x + 4x22 + 5x + 5x33

xx11 + x + x22 + x + x33 + x + x44 = 5 = 5

2x2x22 + x + x33 - x - x55 + x + x66 = 2 = 2

xx11 + 3x + 3x22 +x +x77 = 4 = 4

xx11 , x , x22 , x , x33 , x , x44 , x , x55 , x , x66 , x , x77 ≥ 0 ≥ 0

• Basis awal xBasis awal xBB00 untuk model mtematik linier dua fase bisa ditulis sbb: untuk model mtematik linier dua fase bisa ditulis sbb:

Minimumkan (w – wMinimumkan (w – w00) = b) = bII’’ x xNN

00

Minimumkan (z – 0) = cMinimumkan (z – 0) = cII’’ x xNN

00

AANN00 x xNN

00 + I x + I xBB00 = b = b00

dimana ddimana dII = b = bII ditentukan sebagai unit harga fungsi objektif buatan. ditentukan sebagai unit harga fungsi objektif buatan.

• Tabel simpleks untuk model ini adalahTabel simpleks untuk model ini adalah

xxBB00 A ANN

00 I b b/a I b b/a

- c- cII’’ 0 (z – 0) - 0 (z – 0) -

- d- dII’’ 0 (w – w 0 (w – w00) -) -

• Metode simpleks dua fase menggunakan aturan yang sama seperti metode Metode simpleks dua fase menggunakan aturan yang sama seperti metode simpleks sebelumnya untuk meminimumkan model matematik linier. simpleks sebelumnya untuk meminimumkan model matematik linier. Dalam metode ini, persyaratan dua fungsi objektif harus dipenuhi.Dalam metode ini, persyaratan dua fungsi objektif harus dipenuhi.

Fase pertamaFase pertama, tujuannya adalah meminimumkan nilai numerik w , tujuannya adalah meminimumkan nilai numerik w

menjadi nol. Koefisien harga dmenjadi nol. Koefisien harga dII dari fungsi w digunakan sebagai indikator dari fungsi w digunakan sebagai indikator selama tahap ini. Jika w = 0, semua variabel buatan sudah dihilangkan dari selama tahap ini. Jika w = 0, semua variabel buatan sudah dihilangkan dari basis dan model adalah dalam bentuk variabel kendali asal. Fase dua basis dan model adalah dalam bentuk variabel kendali asal. Fase dua dimulai.dimulai.

Fase keduaFase kedua, tujuannya meminimumkan fungsi z, dimana koefisien c, tujuannya meminimumkan fungsi z, dimana koefisien c II digunakan sebagai indikator. Selama fase kedua, variabel buatan tidak digunakan sebagai indikator. Selama fase kedua, variabel buatan tidak pernah ditinjau sebagai masukan yang mungkin untuk basis. Sekali pernah ditinjau sebagai masukan yang mungkin untuk basis. Sekali dihilangkan, tidak pernah masuk kembali ke basis.dihilangkan, tidak pernah masuk kembali ke basis.

• Contoh: Contoh:

(a) Gunakan metode simplex dua fase untuk model matematik berikut ini:(a) Gunakan metode simplex dua fase untuk model matematik berikut ini:

Minimmkan z = xMinimmkan z = x22

3x3x11 + 4x + 4x2 2 ≥ 9≥ 9

5x5x11 + 2x + 2x22 ≤ 8 ≤ 8

3x3x11 - x - x22 ≤ 0 ≤ 0

xx11 ≥ 0 , x ≥ 0 , x22 ≥ 0 ≥ 0

(b) Telusuri lintasan untuk solusi optimum pada gambar(b) Telusuri lintasan untuk solusi optimum pada gambar

SolusiSolusi

(a) Variable slack dan surplus diberikan kedalam model untuk menghilangkan (a) Variable slack dan surplus diberikan kedalam model untuk menghilangkan pembatas tidak sama dengan. Model menjadipembatas tidak sama dengan. Model menjadi

Minimumkan z = xMinimumkan z = x22

3x3x11 + 4x + 4x22 - x - x33 = 9 = 9

5x5x11 + 2x + 2x22 + x + x44 = 8 = 8

3x3x11 - x - x22 + x + x55 = 0 = 0

xx11 ≥ 0 , x ≥ 0 , x22 ≥ 0 ≥ 0

Selanjutnya solusi fisibel basic ditentukan dengan memberikan variabel Selanjutnya solusi fisibel basic ditentukan dengan memberikan variabel buatan pada persamaan pembatas pertama:buatan pada persamaan pembatas pertama:

3x3x11 + 4x + 4x22 - x - x33 + x + x66 = 9 = 9

Fungsi objektif buatan ditentukan dalam bentuk xFungsi objektif buatan ditentukan dalam bentuk xNN supaya bisa menjadi supaya bisa menjadi basisbasis

w = xw = x66

w = 9 – 3xw = 9 – 3x11 – 4x – 4x22 + x + x33

Model matematik bisa ditulis sebagai model matematik linier dua fase:Model matematik bisa ditulis sebagai model matematik linier dua fase:

Minimumkan (w – 9) = -3xMinimumkan (w – 9) = -3x11 + -4x + -4x22 + x + x33

Minimumkan (z – 0) = xMinimumkan (z – 0) = x22

3x3x11 + 4x + 4x22 - x - x33 + x + x66 = 9 = 9

5x5x11 + 2x + 2x22 + x + x44 = 8 = 8

3x3x11 - x - x22 + x + x55 = 0 = 0

Vektor basis dan nonbasis awal dapat ditulis:Vektor basis dan nonbasis awal dapat ditulis:

xxBB0’0’ = [x = [x44 x x55 x x66]]

xxNN0’0’ = [x = [x11 x x22 x x33]]

Tabel simpleks untuk model ini adalahTabel simpleks untuk model ini adalah

Solusi awalSolusi awal

xxBB x x11 x x22 x x33 x x44 x x55 x x66 b b/a b b/a

xx66 3 4 -1 0 0 1 9 9/4 = 2,25 3 4 -1 0 0 1 9 9/4 = 2,25

xx44 5 2 0 1 0 0 8 8/2 = 4 5 2 0 1 0 0 8 8/2 = 4

xx55 3 -1 0 0 1 0 0 3 -1 0 0 1 0 0

ccII 0 1 0 0 0 0 (z – 0) 0 1 0 0 0 0 (z – 0)

ddII -3 -4 1 0 0 0 (w – 9) -3 -4 1 0 0 0 (w – 9)

Aturan metode simpleks diterapkan pada baris indikator w sampaiAturan metode simpleks diterapkan pada baris indikator w sampai

variabel buatan, xvariabel buatan, x66 dihilangkan dari basis x dihilangkan dari basis xBB. .

ATURAN 1 Karena tidak semua baris indikator dATURAN 1 Karena tidak semua baris indikator d II positif, solusi awal adalah positif, solusi awal adalah

tidak minimumtidak minimum

ATURAN 2 Variabel kendali xATURAN 2 Variabel kendali x22 masuk basis karena d masuk basis karena d22 = -4 adalah nilai = -4 adalah nilai

negatif terkecil dari vektor indikator dnegatif terkecil dari vektor indikator dII . Sebuah panah menunjukkan bahwa . Sebuah panah menunjukkan bahwa

xx22 masuk basis. masuk basis.

ATURAN 3 Variabel buatan xATURAN 3 Variabel buatan x66 meninggalkan basis karena b/a = 2,25 adalah meninggalkan basis karena b/a = 2,25 adalah

nilai positif terkecil dari vektor b/a. Sebuah panah menunjukkan bahwa b/a nilai positif terkecil dari vektor b/a. Sebuah panah menunjukkan bahwa b/a

meninggalkan basis. Catatan bahwa xmeninggalkan basis. Catatan bahwa x55 tidak ditinjau sebab koefisien “a” tidak ditinjau sebab koefisien “a”

adalah negatif, a = -1.adalah negatif, a = -1.

Iterasi 1Iterasi 1 Eliminasi berurutan digunakan untuk menentukan solusi kandidat Eliminasi berurutan digunakan untuk menentukan solusi kandidat

selanjutnya, xselanjutnya, xBB1’1’ = [x = [x22 x x44 x x55]. Sebuah lingkaran digambar melingkari ]. Sebuah lingkaran digambar melingkari

elemen pivot dari matriks A . Hasil eliminasi berurutab diberikan sbb:elemen pivot dari matriks A . Hasil eliminasi berurutab diberikan sbb:

xxBB x x11 x x22 x x33 x x44 x x55 x x66 b b/a b b/a

xx22 0.75 1 -0.25 0 0 0.25 2.25 2.25/0.75 = 3 0.75 1 -0.25 0 0 0.25 2.25 2.25/0.75 = 3

xx44 3.5 0 0.5 1 0 -0.50 3.50 3.5/3.5 = 1 3.5 0 0.5 1 0 -0.50 3.50 3.5/3.5 = 1

xx55 3.75 0 -0.25 0 1 0.25 2.25 2.25/3.75 = 0.6 3.75 0 -0.25 0 1 0.25 2.25 2.25/3.75 = 0.6

ccII -0.75 0 0.25 0 0 0 (z – 2.25) -0.75 0 0.25 0 0 0 (z – 2.25)

ddII 0.00 0 0.0 0 0 1 (w – 0.0) 0.00 0 0.0 0 0 1 (w – 0.0)

Karena variabel buatan tidak lama menjadi anggota basis, indikator barisKarena variabel buatan tidak lama menjadi anggota basis, indikator baris

z digunakan sebagai indikatorz digunakan sebagai indikator

ATURAN 1 Karena tidak semua nilai cATURAN 1 Karena tidak semua nilai cII positif, solusi kandidat tidak optimum. positif, solusi kandidat tidak optimum.

ATURAN 2 Variabel kendali xATURAN 2 Variabel kendali x11 akan diberikan pada basis karena c akan diberikan pada basis karena c11 = -0.75 = -0.75

adalah satu-satunya indikator negatif dari cadalah satu-satunya indikator negatif dari c II . .

ATURAN 3 Variabel kendali xATURAN 3 Variabel kendali x55 dihilangkan dari basis karena b/a = 0.6 adalah dihilangkan dari basis karena b/a = 0.6 adalah

nilai positif terkecil dari vektor b/a. nilai positif terkecil dari vektor b/a.

Iterasi 2Iterasi 2 Karena w = 0, baris indikator kedua w dan kolom untuk variabel Karena w = 0, baris indikator kedua w dan kolom untuk variabel

buatan xbuatan x66 , dihilangkan dari tinjauan selanjutnya. Eliminasi berurutan , dihilangkan dari tinjauan selanjutnya. Eliminasi berurutan

dilakukan, sehingga solusi kandidat baru diberikan pada tabel simpleks sbb:dilakukan, sehingga solusi kandidat baru diberikan pada tabel simpleks sbb:

xxBB x x11 x x22 x x33 x x44 x x55 b b

xx22 0.00 1 -0.20 0 -0.20 1.80 0.00 1 -0.20 0 -0.20 1.80

xx44 0.00 0 0.73 1 -0.93 1.40 0.00 0 0.73 1 -0.93 1.40

xx11 1.00 0 -0.07 0 0.27 0.60 1.00 0 -0.07 0 0.27 0.60

ccII 0.00 0 0.20 0 0.20 (z – 1.8) 0.00 0 0.20 0 0.20 (z – 1.8)

ATUTAN 1 Karena semua cATUTAN 1 Karena semua cII adalah positif, solusi optimum sudah didapat. adalah positif, solusi optimum sudah didapat.

Lokasi optimum adalah xLokasi optimum adalah x11* = 0.60 x* = 0.60 x22* = 1.80 x* = 1.80 x44* = 1.40* = 1.40

Nilai optimum minimum dari z adalah z* = 1.80Nilai optimum minimum dari z adalah z* = 1.80

(b) Lintasan menuju solusi optimum ditunjukkan pada gambar.(b) Lintasan menuju solusi optimum ditunjukkan pada gambar.

Solusi awal, x0

Lintasan

x1

x2

1 2

1

2

3

4

Lintasan

Iterasi 1, x1

Iterasi 2 dan akhir, x2

5x1 + 2x2 = 8

3x1 - x2 = 0

3x1 + 4x2 = 9

x1*

x2* z2*= 1.8

Pada gambar solusi awal adalah (0,0). Setelah satu iterasi, menjadi (0,2.25).Pada gambar solusi awal adalah (0,0). Setelah satu iterasi, menjadi (0,2.25).

Iterasi selanjutnya didapat solusi optimum (0.6 , 1.8)Iterasi selanjutnya didapat solusi optimum (0.6 , 1.8)

Tugas 3Tugas 3

• Soal 1Soal 1

Minimumkan z = 4xMinimumkan z = 4x11 + 5x + 5x22

xx11 + x + x22 ≥ 1 ≥ 1

2x2x11 + 4x + 4x22 ≥ 3 ≥ 3

3x3x11 + 7x + 7x22 ≤ 6 ≤ 6

xx11 ≥ 0 , x ≥ 0 , x22 ≥ 0 ≥ 0

a) Selesaikan soal diatas dengan metode simpleks dua fasea) Selesaikan soal diatas dengan metode simpleks dua fase

b) Selesaikan secara grafis.b) Selesaikan secara grafis.

c) Telusuri jalur untuk solusi optimum.c) Telusuri jalur untuk solusi optimum.

• Soal 2Soal 2

Maksimumkan z = 2xMaksimumkan z = 2x11 + 3x + 3x22 – 2x – 2x33

xx11 + 3x + 3x22 + x + x33 ≥ 3 ≥ 3

6x6x11 - x - x22 - x - x33 ≤ 6 ≤ 6

2x2x11 - 3x - 3x22 + 2x + 2x33 ≤ 12 ≤ 12

xx11 + 6x + 6x22 - 4x - 4x33 ≤ 5 ≤ 5

xx11 ≥ 0, x ≥ 0, x22 ≥ 0, x ≥ 0, x33 ≥ 0 ≥ 0

• Soal 3Soal 3

Maksimumkan z = 3xMaksimumkan z = 3x11 + 2x + 2x22 + 3x + 3x33

xx11 + x + x22 + 2x + 2x33 ≥ 1 ≥ 1

2x2x11 ≤ 4 ≤ 4

xx33 ≥ 2 ≥ 2

xx11 ≥ 0, x ≥ 0, x22 ≥ 0, x ≥ 0, x33 ≥ 0 ≥ 0

• Soal 4 (hal 300 Ossenbruggen)Soal 4 (hal 300 Ossenbruggen)• Campuran suatu agregat mengandung minimum 30 % pasir dan tidak lebih Campuran suatu agregat mengandung minimum 30 % pasir dan tidak lebih

dari 60 % kerikil dan 10 % lanau. Tiga lokasi sumber agregat disediakan dari 60 % kerikil dan 10 % lanau. Tiga lokasi sumber agregat disediakan dengan data dibawah.dengan data dibawah.

______________________________________________________

Galian 1 2 3Galian 1 2 3

----------------------------------------------------------------------------

% pasir 5 30 100% pasir 5 30 100

% kerikil 60 70 --% kerikil 60 70 --

% lanau 35 -- --% lanau 35 -- --

biaya/ydbiaya/yd3 3 $2 $10 $8$2 $10 $8

______________________________________________________

a) Formulasikan bentuk model biaya minimumnya. Tentukan variabel a) Formulasikan bentuk model biaya minimumnya. Tentukan variabel

kendalinya.kendalinya.

b) Tulis dalam bentuk standar pemograman linier.b) Tulis dalam bentuk standar pemograman linier.

c) Selesaikan dengan metode simpleks dua fase.c) Selesaikan dengan metode simpleks dua fase.