management sda s2

1

I PEMROGRAMAN LINIERSejak diperkenalkan di akhir dasawarsa 1960 pemrograman linier merupakan salah satu alat pengambil keputusan yang paling efektif. Keberhasilannya berakar dari keluwesannya dalam menjabarkan di mana kalangan pemakai teknik optimasi ini sukses dalam menggunakan hasil optimasi linier sebagai sebuah alat pengambil keputusan situasi kehidupan nyata di bidang-bidang berikut : militer, industri, pertanian, transportasi, ekonomi, kesehatan, keteknikan bahkan ilmu sosial dan perilaku (Taha,1996). Di samping itu, tersedianya program komputer yang sangat efisien untuk memecahkan masalah-masalah Linier Programing yang sangat luas, merupakan faktor penting dalam penyebaran penggunaan teknik optimasi ini (Lasdon,1998). Pemrograman linier adalah sebuah alat deterministik, yang berarti bahwa semua parameter model diasumsikan diketahui dengan pasti. Tetapi dalam kehidupan nyata jarang seseorang menghadapi masalah di mana terjadi kepastian yang sesungguhnya. Teknik LP mengkompensasikan “kekurangan” ini dengan memberikan analisis pasca optimum yang sistematis untuk memungkinkan pengambil keputusan yang bersangkutan menguji perubahan dalam berbagai parameter dari model tersebut. Pada intinya, teknik tambahan ini memberikan dimensi dinamis (Fauzi, 2002).

2

Pengembangan model matematis dapat dimulai dengan menjawab ketiga pertanyaan berikut ini :Apakah yang diusahakan untuk ditentukan oleh model tersebut? Dengan kata lain, apakah variabel (yang tidak diketahui) dari masalah tersebut?Apakah batasan (kendala) yang harus dikenakan atas variabel untuk memenuhi batasan sistem model tersebut?Apakah tujuan (sasaran) yang harus dicapai untuk menentukan pemecahan optimum (terbaik) dari semua nilai yang layak dari variabel tersebut?Cara yang efektif untuk menjawab pertanyaan-pertanyaan ini adalah memberikan ringkasan untuk masalah yang bersangkutan. Dapat diaplikasikan pada contoh Pabrik Cat berikut

3

Linear Programing dengan Model Dua Variabel dan Pemecahannya

Contoh : Reddy Mikks company memiliki sebuah pabrik yang menghasilkan cat, baik untuk eksterior maupun interior untuk didistribusikan kepada para grosir. Harga jual cat eksterior 3 unit harga, cat interior 2 unit harga. Permintaan cat interior max 1 ton lebih dari cat eksterior, produksi cat interior max 2 ton/hari.

Data : Ton Bahan Mentah per

Ton CatKetersedia

an Maksimum

(Ton)Eksterior Interior

Bahan Mentah A

1 2 6

Bahan Mentah B

2 1 8

4

Pengembangan Model Matematis

1 Variabel : Xe = jumlah ton cat eksterior yang diproduksi setiap hariXi = jumlah ton cat interior yang diproduksi setiap

hari2. Fungsi Tujuan (Objective Function) : Max Z = 3 Xe + 2 Xi3. Batasan (Constraint) :

Xe + 2 Xi ≤ 6 (bahan mentah A)2 Xe + Xi ≤ 8 (bahan mentah B) Xi - Xe ≤ 1 (perbedaan max cat interior &

eksterior) Xi ≤ 2 (max cat interior)

5

1

2

3

4

5

61 2 3 4 50 6

1

2

3

4

5

7

6

8

A

F

B

C

DE

GH K

J

x I

xE

Ruangpemecahan

2xE + xI 8-xE + xI 1

xI 2 xE 0

xI 0

xE + 2xI 6 123456

Penyelesaian secara grafis

6

Membuat persamaan bentuk standard untuk penyelesaian secara simplek

Max : Z = 3 Xe + 2 Xi +0 S1+ 0 S2 + 0 S3 + 0 S4

Dengan batasan : Xe + 2 Xi + S1 = 6 2 Xe + Xi + S2 = 8 - Xe + Xi + S3 = 1 Xi + S4 = 2

Xe, Xi, S1, S2, S3, S4 ≥ 0

7

Penyelesaian dengan cara simplek

Dasar Z Xe Xi S1 S2 S3 S4 Solution

Z 1 -3 -2 0 0 0 0 0 Persamaan Z

S1 0 1 2 1 0 0 0 6 Persamaan S1

S20

2 1 0 1 0 0 8 Persamaan S2

S3 0 -1 1 0 0 1 0 1 Persamaan S3

S4 0 0 1 0 0 0 1 2 Persamaan S4

8


Iterasi I ↓IN

Dasar Z Xe Xi S1 S2 S3 S4 SolutionTitik potong (Ratio)

Z 1 -3 -2 0 0 0 0 0 0/-3= 0

S1 0 1 2 1 0 0 0 6 6/1 = 6

←Out

S2 0 2( titik pivot) 1 0 1 0 0 8 8/2 = 4

(terkecil)

S3 0 -1 1 0 0 1 0 1 - 1 (tidak boleh negatif)

S4 0 0 1 0 0 0 1 2 tidak boleh dibagi 0

9

Dasar Z Xe Xi S1 S2 S3 S4 Solution Ratio

0/2 2/2 1/2 0/2 1/2 0/2 0/2 8/2

Pers.Pivot Xe 0 1 1/2 0 1/2 0 0 4 8/2 =4

10

Operasi Gauss-Jordan berikut menghasilkan tabel baru:1. Persamaan pivot Xe baru = persamaan S2 lama : 22. Persamaan Z baru = persamaan Z lama - (-3) x pers pivot baru3. Persamaan S1 baru= persamaan S1 lama - (1) x pers pivot baru4. Persamaan S3 baru= persamaan S3 lama - (-1) x pers pivot baru5. Persamaan S4 baru= persamaan S4 lama - (0) x pers pivot baru

11

Persamaan Z lama 1 -3 -2 0 0 0 0 0

-(-3) x Pers pivot baru 0 3 3/2 0 3/2 0 0 12

Persamaan Z baru 1 0 -1/2 0 3/2 0 0 12

Persamaan S1 lama 0 1 2 1 0 0 0 6

-1 x Pers pivot baru 0 -1 -1/2 0 -1/2 0 0 -4

Persamaan S1 baru 0 0 3/2 1 -1/2 0 0 2

Persamaan S3 lama 0 -1 1 0 0 1 0 1

-(-1) x Pers pivot baru 0 1 1/2 0 1/2 0 0 4Persamaan S3 baru 0 0 3/2 0 1/2 1 0 5

Operasi Gauss-Jordan

12


Iterasi 2 ↓IN

Dasar Z Xe Xi S1 S2 S3 S4 Solution Ratio

Z 1 0 -1/2 0 3/2 0 0 12

←Out S1 0 0 3/2 1 -1/2 0 0 2 2/3/2=4/3

Xe 0 1 1/2 0 1/2 0 0 4 4/(1/2)=8

S3 0 0 3/2 0 1/2 1 0 5 5/3/2=10/3

S4 0 0 1 0 0 0 1 2 2/1=2

13

Operasi Gauss-Jordan berikut menghasilkan tabel baru:1. Persamaan pivot S1(Xi) baru = persamaan S1 lama : 3/22. Persamaan Z baru = persamaan Z lama - (-1/2) x pers pivot baru3. Persamaan Xe baru= persamaan Xe lama - (1/2) x pers pivot

baru4. Persamaan S3 baru= persamaan S3 lama - (3/2) x pers pivot

baru5. Persamaan S4 baru= persamaan S4 lama - (1) x pers pivot baru

14

Iterasi 3

Dasar Z Xe Xi S1 S2 S3 S4 Solution

Z 1 0 0 1/3 4/3 0 0 12 ⅔

Xi 0 0 1 2/3 -1/3 0 0 4/3

Xe 0 1 0 -1/3 2/3 0 0 10/3

S3 0 0 0 -1 1 1 0 3

S4 0 0 0 - 2/3 1/3 0 1 2/3

Pemecahan ini optimal karena tidak ada kofisien negatif pada persamaan Z, dengan besaran Xi = 4/3, Xe = 10/3 dan Z = 12 ⅔

15

Dalam model Reddy Mikks, semua batasan adalah berjenis . Sifat ini,

bersamaan dengan fakta bahwa sisi kanan dari semua batasan adalah non-

negatif, memberikan kita pemecahan dasar awal yang layak yang terdiri dari

semua variabel slack. Kondisi seperti ini tidak dipenuhi oleh semua model

LP, sehingga menimbulkan kebutuhan untuk merancang sebuah prosedur

perhitungan otomatis untuk memulai iterasi simpleks. Kita melakukan ini

dengan menambahkan variabel buatan (artificial variable) atau variabel

tambahan yang diperlukan untuk memainkan peran variabel slack. Tetapi,

karena variabel buatan seperti itu tidak memiliki makna fisik dalam model

semula (sehingga diberi nama “buatan”),

PEMECAHAN AWAL BUATAN UNTUK METODE SIMPLEKS PRIMAL

16

ketentuan harus dibuat untuk membuatnya menjadi nol di iterasi

optimum. Dengan kata lain, kita menggunakan variabel buatan

untuk memulai pemecahan, dan lalu meninggalkan mereka setelah

misi mereka terpenuhi. Kita mencapai hal ini dengan menggunakan

umpan balik informasi, yang akan membuat variabel ini tidak

menarik dari sudut pandang optimisasi. Satu cara yang logis untuk

mencapai tujuan ini adalah dengan mengenakan penalti pada

variabel buatan dalam fungsi tujuan. Dua metode (yang berkaitan

erat) yang didasari oleh penggunaan penalti tersedia untuk maksud

ini (1) metode M atau metode penalti dan (2) metode dua tahap.

Perincian tentang kedua prosedur ini diberikan berikut ini.

17

Teknik M (Metode Penalti)

Kita menjabarkan metode ini dengan menggunakan contoh numerik berikut ini:

Minimumkan z = 4x1 + x2Dengan batasan3x1 + x2 = 34x1 + 3x2 6x1 + 2x2 4x1, x2 0Bentuk standar dari model ini menjadiMinimumkan z = 4x1 + x23x1 + x2 = 34x1 + 3x2 – x3 = 6x1 + 2x2 + x4 = 4x1, x2, x3, x4 0

18

Persamaan pertama dan kedua tidak memiliki variabel yang memainkan peran sebagai variabel slack. Jadi kita menambahkan dua variabel buatan R1 dan R2 dalam kedua persamaan ini sebagai berikut:

3x1 + x2 + R1 = 34x1 + 3x2 – x3 + R2 = 6Kita dapat mengenakan penalti pada R1 dan R2 dalam

fungsi tujuan dengan memberikan koefisien positif yang sangat besar dalam fungsi tujuan. Anggaplah M > 0 merupakan sebuah konstanta yang sangat besar, jadi LP dengan variabel buatan ini menjadi

19

Minimumkan z = 4x1 + x2 + MR1 + MR2

Dengan batasan3x1 + x2 + R1 = 34x1 + 3x2 – x3 + R2 = 6x1 + 2x2 + x4 = 4

x1, x2, x3,R1, R2, x4 0 Perhatikan alasan di balik penggunaan variabel buatan. Kita memiliki tiga persamaan dan enam variabel yang tidak diketahui. Jadi pemecahan dasar awal harus mencakup 6 – 3 = 3 variabel nol. Jika kita menempatkan x1, x2, dan x3 di tingkat nol, kita dengan segera memperoleh pemecahan R1 = 3, R2 = 6 dan x4 = 4, yang merupakan pemecahan awal yang layak, yang diperlukan.

20

Sekarang, amati bagaimana model “baru” ini secara otomatis memaksa R1

dan R2 untuk menjadi nol. Karena kita melakukan minimasi, dengan

memberikan M dan R1 dan R2 dalam fungsi tujuan, proses optimasi yang

mengusahakan nilai minimum dari z pada akhirnya akan memberikan nilai

nol pada R1 dan R2 dalam pemecahan optimum. Perhatikan bahwa iterasi-

iterasi sebelum iterasi optimum adalah tidak penting bagi kita. Akibatnya,

tidak menjadi masalah apakah iterasi tersebut mencakup variabel buatan di

tingkat positif. Bagaimana teknik M berubah jika kita melakukan maksimasi

dan bukan minimasi? Dengan menggunakan logika yang sama dengan

mengenakan penalti pada variabel buatan, kita harus memberikan koefisien

–M dalam fungsi tujuan (M > 0), sehingga membuatnya tidak menarik untuk

mempertahankan variabel buatan di tingkat positif dalam pemecahan

optimum.

21

Setelah mengembangkan pemecahan awal yang layak, kita harus “mengkondisikan” masalah tersebut sehingga ketika menempatkannya dalam bentuk tabel, kolom sisi kanan akan memberikan pemecahan awal secara langsung. Ini dilakukan dengan menggunakan persamaan batasan untuk mensubstitusi keluar R1 dan R2 dalam fungsi tujuan. Jadi

R1 = 3 - 3x1 - x2 R2 = 6 - 4x1 - 3x2 + x3

22

Fungsi tujuan menjadiz = 4x1 + x2+ M(3 - 3x1 - x2) + M(6 - 4x1 - 3x2 + x3) = (4-7M)x1 + (1- 4)x2 + Mx3 + 9M

dan persamaan z tersebut sekarang terlihat dalam tabel seperti

z = (4-7M)x1 - (1- 4M)x2 – Mx3 + 9MSekarang anda melihat bahwa di pemecahan awal, dengan diketahui x1 = x2 = x3 = 0, nilai z adalah 9M, seperti seharusnya ketika R1 = 3 dan R2 = 6.Urutan tabel yang mengarah pada pemecahan optimum diperlihatkan dalam tabel 1. Amati bahwa ini adalah masalah minimisasi sehingga variabel masuk harus memiliki koefisien yang paling positif dalam persamaan z.

23

Pemecahan optimum dicapai ketika semua variabel nondasar memiliki koefisien z yang nonpositif. (Ingat bahwa M adalah konstanta positif yang sangat besar).

Pemecahan optimum adalah x1 = 2/5, x2 = 9/5, dan z = 17/5. Karena pemecahan ini tidak memiliki variabel buatan di tingkat positif, pemecahan ini layak dalam kaitannya dengan masalah semula sebelum variabel buatan ditambahkan. (Jika masalah ini tidak memiliki pemecahan yang layak, setidaknya satu variabel buatan akan positif dalam pemecahan yang optimum. Kasus ini dibahas dalam bagian berikutnya).

24

Iterasi Dasar x1 x2 x3 R1 R2 x4 Pemecahan

z - 4 + 7M - 1 + 4M - M 0 0 0 9M0(awal)

x1 masukR1 keluar

R1R2R3

341

132

0-10

100

010

001

364

z 0 1 + 5M3

- M 4 - 7M3

0 0 4 + 2M1

x2 masukR2 keluar

x1R2x4

100

1/35/35/3

0-10

1/3- 4/3- 1/3

010

001

123

z 0 0 1/5 8/5 - M -1/5 - M 0 18/52

x3 masukx4 keluar

x1x2x4

100

010

1/5-3/5

1

3/5-4/5

1

-1/53/5-1

001

3/56/51

z 0 0 0 7/5 - M - M -1/5 17/53

(optimum)x1x2x3

100

010

001

2/5-1/5

1

00-1

-1/53/51

2/59/51

Tabel 1

Kolom z telah dihapus untuk memudahkan, karena kolom tidak pernah berubah. Kita akan mengikuti konvensi diseluruh teori ini.

25

Latihan 1 a) Tuliskan persamaan z untuk contoh di atas sebagaimana tampil dalam tabel

ketika masing-masing dari perubahan ini terjadi secara independen.1)Batasan ketiga pada awalnya berjenis .

[Jawab. z + (-4 + 8M) x1 + (-1 + 6 M) x2 – Mx3 – Mx4 = 13M. Gunakan variabel buatan dalam ketiga persamaan.]

2)Batasan kedua pada awalnya berjenis [Jawab. z + (-4 + 3M) x1 + (-1 + M) x2 = 3M. Gunakan variabel

buatan hanya dalam persamaan pertama.]3)Fungsi tujuan adalah memaksimumkan z = 4 x1 + x2

[Jawab. z + (-4 - 7M) x1 + (-1 - 4M) x2 + M x3 = 3M. Gunakan variabel buatan hanya dalam persamaan pertama dan kedua.]

b) Dalam masing-masing kasus di bawah ini, tunjukkan apakah sepenuhnya diperlukan untuk menggunakan variabel buatan untuk memperoleh pemecahan awal. Asumsikan bahwa semua variabel adalah nonnegatif.

(1) Maksimumkan z = x1 + x2 dengan batasan

26

7x1 + 2x2 63x1 + 3x2 = 5[Jawab. Ya, gunakan R1 dalam persamaan pertama dan

variabel slack dalam persamaan kedua.](2) Minimumkan z = x1 + x2 + x3 + x4

Kendala2 x1 + x2+ x3 = 74 x3 + 3x2 + x4 = 8

[Jawab. Tidak, gunakan x3 dan x4; tetapi, pertama-tama substitusikan keduanya keluar dalam fungsi z dengan menggunakan x3 = 7 - 2x1 – x2 dan x4 = 8 - 4 x1 - R2.]

27

Latihan KomputerRancangan metode M didasari oleh persyaratan bahwa

nilai M harus cukup besar. Secara teoritis, M cenderung tak terhingga. Tetapi, dari sudut pandang perhitungan, pilihan M yang spesifik dapat memiliki pengaruh dramatis terhadap hasil, karena kesalahan pembulatan oleh komputer. Untuk mengilustrasikan hal ini, pertimbangkan masalah berikut ini:maksimumkan z = 0,2 x1 + 0,5 x2

dengan batasan3 x1 +2 x2 6x1 + 2 x2 4x1, x2 0

28

Dengan menggunakan prosedur "user-guided" dari SOLVER, terapkan

metode simpleks primal dengan menggunakan M = 10 dan lalu ulangi

metode tersebut dengan menggunakan M = 999.999. M pertama

menghasilkan pemecahan yang tepat z = 0,95, x1 = 1, x2 = 1,5,

sementara M kedua memberikan pemecahan yang tidak tepat z = 1,18,

x1 = 4, x2 = 0 (perhatikan inkonsistensi dalam nilai z yang dihasilkan).

Sekarang, kalikan koefisien dalam fungsi tujuan dengan 100 sehingga

menjadi z = 200 x1 + 500 x2 dan pecahkan masalah ini dengan

menggunakan M = 10 dan M = 999.999 serta amati bahwa nilai kedua

adalah nilai yang menghasilkan pemecahan yang tepat. Latihan ini

memperlihatkan bahwa nilai M harus dipilih secara relatif terhadap

nilai koefisien tujuan.

29

Iterasi Dasar x1 X2 x3 R1 R2 x4 Pemecahan z - 4 + 7M - 1 + 4M - M 0 0 0 9M 0

(awal) x1 masuk R1 keluar

R1 R2 x4

3 4 1

1 3 2

0 -1 0

1 0 0

0 1 0

0 0 1

3 6 4

z 0 1 + 5M 3

- M 4 - 7M 3

0 0 4 + 2M 1

x2 masuk R2 keluar

x1 R2 x4

1 0 0

1/3 5/3 5/3

0 -1 0

1/3 - 4/3 - 1/3

0 1 0

0 0 1

1 2 3

z 0 0 1/5 8/5 - M -1/5 - M 0 18/5 2

x3 masuk x4 keluar

x1 x2 x4

1 0 0

0 1 0

1/5 -3/5

1

3/5 -4/5

1

-1/5 3/5 -1

0 0 1

3/5 6/5 1

z 0 0 0 7/5 - M - M -1/5 17/5 3

(optimum) x1 x2 x3

1 0 0

0 1 0

0 0 1

2/5 -1/5

1

0 0 -1

-1/5 3/5 1

2/5 9/5 1

Tabel dibawah ini hasil operasi iterasi ke 3 untuk mendapatkan besaran yang tertera dapat dijelaskan pada penjabaran berikut

30

Dasar x1 x2 x3 R1 R2 x4 Solution z -4+7M -1+4M -M 0 0 0 9M

R1 3 1 0 1 0 0 3 3/3=1 * R2 4 3 -1 0 1 0 6 6/4=1.5 x4 1 2 0 0 0 1 4 4/1=4

Iterasi ke 0 : X1 masuk R1 keluar

X1=pivot 3/3=1 1/3 0 1/3 0 0 3/3=1

Z lama -4+7M -1+4M -M 0 0 0 9M

(4-7M) x Pivot 4-7M 4/3-7/3M 0 4/3-7/3M 0 0 4-7M +

Z baru 0 1/3+5/3M -M 4/3-7/3M 0 0 4+2M

R2 lama 4 3 -1 0 1 0 6 -4x Pivot -4 -4/3 0 -4/3 0 0 -4 + R2 baru 0 5/3 -1 -4/3 1 0 2

31

Dasar x1 x2 x3 R1 R2 x4 Solution

X4 lama 1 2 0 0 0 1 4 -1x Pivot -1 -1/3 0 -1/3 0 0 -1 + X4 baru 0 5/3 0 -1/3 0 1 3

Iterasi Ke 1 : X2 masuk R2 keluar Z 0 1/3+5/3M -M 4/3-7/3M 0 0 4+2M

X 1 1 1/3 0 1/3 0 0 1 1:1/3=3 R2 0 5/3 -1 -4/3 1 0 2 2:5/3=1.2* X4 0 5/3 0 -1/3 0 1 3 3:5/3=1.8

X2=pivot 0 1 -3/5 -4/5 3/5 0 6/5

Z lama 0 1/3+5/3M -M 4/3-7/3M 0 0 4+2M

-(1/3+5/3M) x pivot 0 -1/3-5/3M 1/5+M 4/15+4/3M -1/5-M 0 -2/5-2M

Z baru 0 0 1/5 8/5-M -1/5-M 0 18/5

32


X 1 lama 1 1/3 0 1/3 0 0 1 -1/3x pivot 0 -1/3 1/5 4/15 -1/5 0 -2/5 + X 1 baru 1 0 1/5 3/5 -1/5 0 3/5

X4 lama 0 5/3 0 -1/3 0 1 3

-5/3x pivot 0 -5/3 1 4/3 -1 0 -2 + X4 baru 0 0 1 1 -1 1 1

Iterasi 2 X3 masuk ; X4 keluar Z 0 0 1/5 8/5-M -1/5-M 0 18/5 X1 1 0 1/5 3/5 -1/5 0 3/5 3/5:1/5=3 X2 0 1 -3/5 -4/5 3/5 0 6/5 X4 0 0 1 1 -1 1 1 1:1=1 *

X3=pivot 0 0 1 1 -1 1 1

Z lama 0 0 1/5 8/5-M -1/5-M 0 18/5 -1/5x pivot 0 0 -1/5 -1/5 1/5 -1/5 -1/5 +

Z baru 0 0 0 7/5-M -M -1/5 17/5

33

Dasar x1 x2 x3 R1 R2 x4 Solution X1 lama 1 0 1/5 3/5 -1/5 0 3/5

-1/5x pivot 0 0 -1/5 -1/5 1/5 -1/5 -1/5 + X1 baru 1 0 0 2/5 0 -1/5 2/5

X2 lama 0 1 -3/5 -4/5 3/5 0 6/5

3/5x pivot 0 0 3/5 3/5 -3/5 3/5 3/5 X2 baru 0 1 -3/5 -4/5 3/5 0 9/5

Iterasi Optimum koefisien pada pers. Z negatif semua dengan besaran Solution Z= 17/5 pada X1= 2/5 dan X2= 9/5

Z 0 0 0 7/5-M -M -1/5 17/5 X1 1 0 0 2/5 0 -1/5 2/5 X2 0 1 -3/5 -4/5 3/5 0 9/5 X3 0 0 1 1 -1 1 1

34

B. Teknik Dua Tahap

Sebagaimana diflustrasikan dalam latihan komputer di atas, satu

kekurangan dari teknik M adalah kemungkinan kesalahan perhitungan

yang dapat dihasilkan dari pemberian nilai yang terlalu besar untuk

konstanta M. Metode dua tahap dirancang untuk mengatasi kesulitan

ini. Walaupun variabel buatan ditambahkan dengan cara yang sama

seperti yang dipergunakan dalam teknik M, penggunaan konstanta M

disingkirkan dengan memecahkan masalah dalam dua tahap (sehingga

dinamakan metode "dua tahap"). Kedua tahap ini digariskan sebagai

berikut:

35

Tahap 1. Tambahkan variabel buatan sebagaimana diperlukan untuk

memperoleh pemecahan awal. Bentuklah fungsi tujuan baru yang

mengusahakan minimisasi jumlah variabel buatan dengan batasan

masalah semula yang dimodifikasi oleh variabel buatan tersebut. Jika

nilai minimum dari fungsi tujuan yang baru itu adalah nol (yang berarti

bahwa semua variabel buatan adalah nol), masalah tersebut memiliki

ruang pemecahan yang layak. Lanjutkan ke tahap II. Jika tidak, jika

nilai minimum itu positif, masalah itu tidak memiliki pemecahan yang

layak. Hentikan.

Tahap II. Gunakan pemecahan dasar optimum dari tahap I sebagai

pemecahan awal untuk masalah semula.

Prosedur ini diilustrasikan dengan menggunakan contoh teknik M

36

Tahap 1. Karena, kita memerlukan variabel buatan R1 dan R2 dalam

persamaan pertama dan kedua, masalah tahap I dapat berbunyi

minimumkan r = R1 + R2 dengan batasan

3x1 + x2 + R1 = 3

4 x1 + 3 x2 – x3 + R2 = 6

x1, x2, x3, R1, R2, x4 0

Karena R1, dan R2, termasuk dalam pemecahan awal, keduanya harus

disubstitusi keluar dalam fungsi tujuan (bandingkan dengan teknik M)

sebagai berikut:

r = R1 + R2

= (3 - 3 x1 – x2) + (6 - 4 x1 - 3 x2 + x3)

= -7 x1 - 4 x2 + x3 + 9

37

Dengan demikian tabel awal menjadi

Tabel optimum diperoleh dalam dua iterasi dan diketahui (periksalah)

Karena minimum r = 0, masalah ini memiliki pemecahan

yang layak; karena itu kita bergerak ke tahap II.

Dasar x1 x2 x3 R1 R2 x4 Pemecahan

r 7 4 -1 0 0 0 9R1

R2

x4

341

132

0-10

100

010

001

364

Dasar x1 x2 x3 R1 R2 x4 Pemecahan

r 0 0 0 -1 -1 0 0x1

x2

x4

100

010

1/5-3/5

1

3/5-4/5

1

-1/53/5-1

001

3/56/51

38

Tahap II. Variabel buatan sekarang telah menjalankan

fungsinya dan harus disingkirkan dalam semua perhitungan

berikutnya. Ini berarti bahwa persamaan dalam tabel optimum di

tahap I dapat ditulis sebagai

x1 + (1/5)x3 = 3/5

x2 – (3/5) (x3) = 6/5

x3 + x4 = 1

39

Persamaan ini tepat setara dengan persamaan dalam bentuk standar

dari masalah semula (sebelum variabel buatan ditambahkan). Jadi

masalah semula tersebut dapat ditulis sebagai

minimumkan z = 4 x1 + x2

dengan batasan

x1 + (1/5)x3 = 3/5

x2 – (3/5) (x3) = 6/5

x3 + x4 = 1

x1, x2, x3, x4 0

40

Kontribusi utama dari perhitungan tahap I adalah memberikan

pemecahan awal yang siap untuk soal semula. Karena soal tersebut

memiliki 3 persamaan dan 4 variabel, dengan menempatkan 4 - 3 =

1 variabel, yaitu x3, sama dengan 0, memperoleh pemecahan dasar

awal yang layak x1 = 3/5, x2 = 6/5, dan x4 = 1.

Untuk memecahkan soal ini, kita perlu mensubstitusi variabel dasar

x1 dan x2 dalam fungsi tujuan seperti yang kita lakukan dalam

teknik M. Ini dicapai dengan menggunakan persamaan batasan

sebagai berikut:

z = 4 x1 + x2

= 4 {3/5- (1/5) x3 } + {6/5 + (3/5) x3}

= -1/5 x3 + 18/5

41

Jadi tabel awal untuk tahap II menjadi

Tabel tersebut tidak optimal, karena x3 harus memasuki pemecahan.

Jika kita melakukan perhitungan simpleks, kita akan memperoleh

pemecahan optimum dalam satu iterasi. Penyingkiran variabel

buatan di akhir tahap I dilakukan hanya ketika semua variabel

tersebut adalah nondasar (seperti yang diilustrasikan dalam contoh

di atas). Tetapi, adalah mungkin bahwa satu variabel buatan atau

lebih tetap dasar tetapi di tingkat nol di akhir tahap I. Dalam kasus

seperti ini, variabel seperti itu haruslah menjadi bagian dari

pemecahan

Dasar x1 x2 x3 x4 Pemecahan

r 0 0 1/5 0 18/5x1

x2

x4

100

010

1/5- 3/5

1

001

3/56/51

42

awal tahap II. Dengan demikian, perhitungan tahap II harus

dimodifikasi untuk mencegah variabel buatan memperoleh nilai

positif selama iterasi dalam tahap II. Peraturan untuk menjamin

bahwa variabel buatan nol tidak akan pernah menjadi positif dalam

tahap II adalah sederhana. Amati bahwa dalam kolom masuk,

koefisien batasan yang berkaitan dengan baris variabel buatan dapat

positif, nol, atau negatif. Jika positif, itu akan secara otomatis

menjadi elemen pivot (karena akan bersesuaian dengan rasio

minimum sebesar nol) dan variabel buatan itu dapat dipastikan akan

meninggalkan pemecahan dasar untuk menjadi variabel nondasar

dalam iterasi berikutnya (penyingkiran yang baik!). Lalu, jika

43

koefisien itu nol, walaupun elemen pivot akan berada tempat lain di

kolom masuk, sifat operasi baris menjamin bahwa baris buatan

tersebut tetap tidak berubah, yang membuat variabel dasar buatan

tersebut berada di tingkat nol sebagaimana diinginkan. Kasus satu-

satunya yang tersisa adalah koefisien negatif. Dalam kasus ini,

elemen pivot pasti berada di tempat lain dalam kolom masuk dan

jika rasio minimum yang dihasilkan kebetulan positif, maka variabel

buatan tersebut akan memiliki nilai positif dalam. iterasi berikutnya

(dapatkah anda melihat mengapa?). Untuk mencegah hal ini terjadi,

semua yang perlu kita lakukan adalah memaksa variabel buatan

tersebut untuk tetap meninggalkan pemecahan,

44

Semata-mata dengan memilih koefisien negatif tersebut sebagai

elemen pivot untuk iterasi. Walau pun kita melanggar peraturan

rasio minimum, kita tidak akan melanggar kelayakan masalah

tersebut (yang adalah inti dari peraturan rasio minimum) karena

variabel buatan tersebut memiliki nilai nol. Jadi, ketika anda

melakukan operasi baris, sisi kanan dari tabel tetap tidak berubah.,

dan karena itu layak. Untuk meringkaskan, peraturan "baru" untuk

tahap II menuntut pemilihan variabel buatan untuk meninggalkan

pemecahan dasar setiap kali koefisien batasan variabel tersebut

dalam kolom masuk memiliki nilai tidak nol (positif atau. negatif).

(Pada kenyataannya, peraturan ini dapat diterapkan untuk setiap

45

variabel dasar nol dalam setiap tabel simpleks tanpa kekuatiran

untuk melanggar kondisi kelayakan). Latihan komputer berikut ini

memberikan ilustrasi tentang peraturan ini dengan menggunakan

Solver.

Latihan komputer

Pertimbangkan Pertanyaan 3-38. Gunakan prosedur "user-guided"

Solver untuk memilih simpleks primal dengan pemecahan awal dua

tahap. Anda akan melihat bahwa tahap II dimulai di iterasi 2 dengan

variabel buatan dasar Rx6 di tingkat nol. Pada iterasi 3, anda akan

melihat bahwa x3 adalah variabel masuk. Secara normal, rasio

46

minimum akan bersesuaian dengan. x2 karena variabel ini memiliki

satu‑satunya koefisien positif di bawah x3. Tetapi, karena koefisien

batasan dari variabel buatan Rx6 adalah tidak nol, metode simpleks

akan menyingkirkan Rx6 dari kelompok variabel dasar untuk

mencegahnya memiliki nilai positif (iterasi 4). Jika anda memaksa

x2 untuk meninggalkan pemecahan, anda akan menemukan bahwa

pemecahan dalam iterasi 4 akan menjadi tidak layak (cobalah!).

Latihan 3-4

(a) Dalam tahap 1, apa yang dinyatakan oleh variabel buatan?

Secara spesifik, mengapa jumlah variabel buatan diminimumkan?

47

Metode Dua TahapMinimumkan z = 4x1 + x2

Dengan batasan3x1 + x2 = 3

4x1 + 3x2 6x1 + 2x2 4

x1, x2 0

minimumkan r = R1 + R2

dengan batasan3x1 + x2 + R1 = 3

4 x1 + 3 x2 – x3 + R2 = 6x1, x2, x3, R1, R2, x4 0

r = R1 + R2

= (3 - 3 x1 – x2) + (6 - 4 x1 - 3 x2 + x3)= -7 x1 - 4 x2 + x3 + 9

48

Iterasi 1 : x1 masuk ; R1keluarDasar x1 x2 x3 R1 R2 x4 Solution

r 7 4 -1 0 0 0 9 9/7=1 2/7R1 3 1 0 1 0 0 3 3/3=1 *

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

x4 1 2 0 0 0 1 4 4/1=4

x1=pivot 1 1/3 0 1/3 0 0 1

r lama 7 4 -1 0 0 0 9

-7x pivot -7 -7/3 0 -7/3 0 0 -7r baru 0 5/3 -1 -7/3 0 0 2

R2lama 4 3 -1 0 1 0 6

-4xpivot -4 -4/3 0 -4/3 0 0 -4R2baru 0 5/3 -1 -4/3 1 0 2

49


x4 lama 1 2 0 0 0 1 4

-1x pivot -1 -1/3 0 1/3 0 0 -1

x4 baru 0 5/3 0 1/3 0 1 3

Iterasi ke 2 : X2 masuk R2 keluar

r 0 5/3 -1 -7/3 0 0 2

x1 1 1/3 0 1/3 0 0 1 1:1/3=3

R2 0 5/3 -1 -4/3 1 0 2 2:5/3=6/5*

x4 0 5/3 0 1/3 0 1 3 3:5/3=9/5

X2=pivot 0 1 -3/5 -4/5 3/5 0 6/5

r lama 0 5/3 -1 -7/3 0 0 2

-5/3xpivot 0 -5/3 1 4/3 -1 0 -2

r baru 0 0 0 -1 -1 0 0

50


x1lama 1 1/3 0 0 0 0 1

-1/3xpivot 0 -1/3 1/5 4/15 -1/5 0 -2/5x1baru 1 0 1/5 4/15 -1/5 0 3/5

x4 lama 0 5/3 0 0 0 1 3

-5/3xpivot 0 -5/3 1 4/3 -1 0 -2x4 baru 0 0 1 4/3 -1 1 1

Tabel optimal koefisien r negatif dan nilai = 0Dasar x1 x2 x3 R1 R2 x4 Solution

r 0 0 0 -1 -1 0 0x1 1 0 1/5 -4/15 -1/5 0 3/5

X2 0 1 -3/5 -4/5 3/5 0 6/5

x4 0 0 1 4/3 -1 1 1

51

Selanjutnya R1, R2 kita abaikan sehingga bentuk yang baru sbb :minimumkan z = 4 x1 + x2

dengan batasanx1 + (1/5)x3 = 3/5x2 – (3/5) (x3) = 6/5

x3 + x4 = 1 x1, x2, x3, x4 0

Dasar x1 x2 x3 x4 Pemecahan

Z 0 0 1/5 0 18/5x1 1 0 1/5 0 3/5 3/5:1/5=3

x2 0 1 - 3/5 0 6/5

x4 0 0 1 1 1 1:1=1*

Iterasi 1 : x3 masuk x4 keluar

52

Dasar x1 x2 x3 x4 Solution

X4= pivot 0 0 1 1 1 1:1=1*

Z lama 0 0 1/5 0 18/5-1/5xpivot 0 0 -1/5 -1/5 -1/5

Z baru 0 0 0 -1/5 17/5

x1 lama 1 0 1/5 0 3/5

-1/5xpivot 0 0 -1/5 -1/5 -1/5x1 baru 1 0 0 -1/5 2/5

x2 lama 0 1 - 3/5 0 6/5

3/5xpivot 0 0 3/5 3/5 3/5x2 baru 0 1 0 3/5 9/5

53

Tabel Optimal karena koefisien Z negatif

Dasar X1 X2 X3 X4 Pemecahan

Zbaru 0 0 0 -1/5 17/5

X1 baru 1 0 0 -1/5 2/5

X2 baru 0 1 0 3/5 9/5

X1 -pivot 0 0 1 1 1

54

Water Quality Management Models

Linear programming solution techniques will be demonstrated using

the simple water quality management example shown in Figure 1. A

stream receives waste from sources located at sites 1 and 2. Without

some waste treatment at these sites, the water quality indicator (such

as dissolved oxygen concentration), q1 mg/l, at sites 2 and 3 will

continue to be below the desired concentration Qi. The problem is to

find the level of waste water treatment (waste removed) at sites 1 and

2 required to achieved the desired concentrations at sites 2 and 3 at a

minimum total cost. This may be a naïve objective for an actual water

quality management problem. Still it serves to illustrate the use of

55

another linear model and some linear programming procedures that

can be used for its solution.

FIGURE 1. Water Quality Management Problem

Waste input = W1

= 200 units/dayWaste removed = W1X1

Waste input = W2


Site 2 3Existing quality 3 2 Desired quality 7 BOD 6

56

Assume that for each unit of waste removed (not discharged into the

stream) at site 1 the quality index at site 2 improves by 0.025 mg/l,

and the quality index at the site 3 improves by 0.0125 mg/l. For each

unit of waste removed at site 2 the quality index at site 3 improves

by 0.025 mg/l. In this example the water quality at site 2 is measured

just upstream of the point of waste water discharge; hence waste

discharged from site 2 affects the quality only at site 3. Denote these

transfer coefficients as aij (the improvement in the quality index at

site j per unit of waste removed at site i), Wi as the amount of waste

to be treated at site i, and Xi as the fraction of waste removed by

treatment at site i. Then the quality improvement at site j due to

WiXi units of waste removed at site i is (aij )(WiXi) mg/l. For all

57

values of Xi between 0 and 1, the quality index at site 2 will equal

the qurrent concentration q2 plus the improvement, (a12 )(W1X1),

due to treatment at site 1. The quality index at site 3 will equal the

qurrent concentration q3 plus the improvement (a13 )( W1X1) +

(a23 )( W2X2) due to treatment at sites 1 and 2.

The cost of treatment Ci(Xi) at each site I will be a function of the

fraction of waste removed Xi. The objective in this example

problem ia to find the values of the removal fractions, Xi and X2,

that minimize the total cost,

Minimize C1 (X1) + C2(X2)………………. 1

58

While meeting the desired quality standards Q j at sites j = 2 and 3:

q2 + a12 W1X1 Q2 …………………………………… 2

q3 + a13 W1X1 + a23 W2X2 Q3 ……………………… 3

To complete the planning model, constraints confining the range of

waste removal fractions to their feasible values are required. For this

example, at least 30 % removal will be required at both sites. This

corresponds to primary treatment of municipal waste waters to prevent

the discharge of suspended and floating solids. An upper limit of 95 %

will reflect the best technology available without resorting to

distilation or pipimg the wastes to another location.

Xi 0.30 i = 1, 2 ……………………………….. 4

Xi 0.95 i = 1, 2 ……………………………….. 5

59

The planning model defined by equations 2 through 5 contains and

possibly a nonlinear objective function.

In many actual planning situations each cost function Ci (Xi)

will be unknown. At best only an approximate estimate may be

available without additional design and cost studies. In this example

each cost function will be assumed to be unknown. The challenge will

be to try to solve the planning problem, that is, find the least-cost

combination of X1 and X2 without requiring an expensive design and

cost study to obtain improved treatment cost data.

The solution of this problem without complete knowledge of

the cost functions in the objective will illustrate how modeling studies

can assist in planning data collection programs. Very often planning

60

exercise are divided into distinct phases, data collection followed by

data analysis. The two phases should be integrated from the

beginning. Model builders must be aware of the data that are

available, or that can be obtained at a reasonable cost. Data collection

programs should be geared to the need for various data

And the accuracy required. There is no advantage to spending money

or time collecting data or improving the accuracy of such efforts if

such data have little influence on the final solution or decision.

Models can be used to assess the sensitivity of possible solutions to

changes in the values of various parameters or assumptions. This use

of models for such sensitifity analyses is often of more value to

planners and decision makers than is their use for identifying possible

solutions.

61

Returning to the water quality management problem, substitution of

the values for each of the known coefficients (qi, aij,Wi and Qi) in

equations 2 to 5 results in the following sets of constraints:

The desired water quality at site 2 : q2 + a12 W1X1 Q2

which yield 3 + (0.025)(200) X1 7

or X1 0.8 …………..6

The desired water quality at site 3 : q3 + a13 W1X1 + a23 W2X2 Q3

which yield 2 + (0.0125)(200) X1 + (0.025)(100) X2 6

or X1 + X2 6 ………. 7

Limits on the fraction of waste removed :

X1 0.3

X2 0.3 ……………………………………………. 8

62

and X1 0.95

X2 0.95 …………………………………………… 9

Graphical Solution and Analysis.

Since this problem involving only two unknown variables, all

combinations of X1 and X2 that satisfy the constraint 2 through 9

can be determined graphically or use simplex solution. ( solution

will be explain in class session )

63

Waste input = W1


Waste input = W2


Site 2 3Existing quality 3 2 Desired quality 7 6

FIGURE 1. Water Quality Management Problem

64

Minimize C1 (X1) + C2(X2)

While meeting the desired quality standards Q j at sites j = 2 and 3:

q2 + a12 W1X1 Q2

q3 + a13 W1X1 + a23 W2X2 Q3

Xi 0.30 i = 1, 2

Xi 0.95 i = 1, 2 …………………………………… 5

4. The desired water quality at site 2 : q2 + a12 W1X1 Q2

which yield 3 + (0.025)(200) X1 7

or X1 0.8 …………..……. 1

65

5. The desired water quality at site 3 : q3 + a13 W1X1 + a23 W2X2 Q3

which yield 2 + (0.0125)(200) X1 + (0.025)(100) X2 6

or X1 + X2 1.6 ……...……. 2

6. Limits on the fraction of waste removed :

X1 0.3………………3

X2 0.3.……………..4

and X1 0.95………..5

X2 0.95.……… 6

66

0 0.2 0.3 0.4 0.6 0.8 0.95 1.0

1.00.95

0.8

0.6

0.4

0.3

0.2

X1 08

X20.95

X1 0.3

X2 0.3

X1 + X2 1.6

Region of feasible solutions

X10.95

X2

X1

67

Min Z = 4 X1 + 6 X2

Constraint :

X1 0.8

X1 + X2 1.6

X1 0.3

X2 0.3

X1 0.95

X2 0.95

X1 + X2 = 1.6 X2 = 0.8

X1 = 0.8

X1 = 0.95 X2 = 0.65

68

Bila Z = 4 X1 + 6 X2

Dan X1, X2 = (0.95, 0.65) Titik paling Extrim minimal.

Maka Z = 4 x 0.95 + 6 x 0.65 = 7.7 (Optimal)

69

Penyelesaian dengan metode ‘M’Persamaan dirubah dalam bentuk standard sbb: Z – 4 X1 - 6 X2 = 0 X1 - X3 = 0.8 X1 + X2 - X4 = 1.6 X2 - X5 = 0.3 X1 + X6 = 0.95 X2 + X7 = 0.95X1 - X3 + R1 = 0.8 ----- R1 = 0.8 – X1 + X3X1 + X2 - X4 + R2 = 1.6 -----R2 = 1.6 – X1 – X2 + X4

Z = 4 X1 + 6 X2 + M ( 0.8 – X1 + X3) + M ( 1.6 – X1 – X2 + X4) = X1(4-M-M) + X2(6-M) + M X3 + M X4 + 2.4 MZ – (4-2M) X1 –( 6 – M )X2 - M X3 – M X4 = 2.4 M

70

Basic X1 X2 X3 X4 X5 X6 X7 R1 R2 Sol

Z -(4-2M) -(6-M) -M -M 0 0 0 0 0 2.4MR1 1 0 -1 0 0 0 0 1 0 0.8 0.8/1=0.8R2 1 1 0 -1 0 0 0 0 1 1.6 1.6/1=1.6X2 0 1 0 0 -1 0 0 0 0 0.3 0.3/0=X1 1 0 0 0 0 1 0 0 0 0.95 0.95/1=0.95X2 0 1 0 0 0 0 1 0 0 0.95 0.95/0=

X1 masuk R1 keluarX1 Pivot 1 0 -1 0 0 0 0 1 0 0.8

Zlama -(4-2M) -(6-M) -M -M 0 0 0 0 0 2.4M

(4-2M)x Pivot 4-2M 0 -4+2M 0 0 0 0 4-2M 0 3.2-1.6M

Z Baru 0 M-6 M-4 -M 0 0 0 4-2M 0 3.2+0.8M

R2 lama 1 1 0 -1 0 0 0 0 1 1.6

-1x pivot -1 0 1 0 0 0 0 -1 0 -0.8

R2 Baru 0 1 1 0 0 0 0 -1 1 0.8

X2lama=X2baru 0 1 0 0 -1 0 0 0 0 0.3

X1 lama1 0 0 0 0 1 0 0 0 0.95

-1x pivot -1 0 1 0 0 0 0 -1 0 -0.8

X1 baru 0 0 1 0 0 1 0 -1 0 0.15

71


Z 0 M-6 M-4 -M 0 0 0 4-2M 0 3.2+0.8M

X1 1 0 -1 0 0 0 0 1 0 0.8

R2 0 1 1 0 0 0 0 -1 1 0.8 0.8/1=0.8

X2 0 1 0 0 -1 0 0 0 0 0.3

X1 0 0 1 0 0 1 0 -1 0 0.15 0.15/1=0.15

X2 0 1 0 0 0 0 1 0 0 0.95Iterasi II X3 masuk X1 keluarX3=Pivot 0 0 1 0 0 1 0 -1 0 0.15

Z lama 0 M-6 M-4 -M 0 0 0 4-2M 0 3.2+0.8M(4-M)xpivot 0 0 4-M 0 0 4-M 0 M-4 0 0.6-0.15 M

Z baru 0 M-6 0 -M 0 4-M 0 -M 0 0.65M+3.8

X1lama 1 0 -1 0 0 0 0 1 0 0.8

1x pivot 0 0 1 0 0 1 0 -1 0 0.15

X1baru 1 0 0 0 0 1 0 0 0 0.95

R2 lama 0 1 1 0 0 0 0 -1 1 0.8

-1x pivot 0 0 -1 0 0 -1 0 1 0 -0.15

R2 baru 0 1 0 0 0 -1 0 0 1 0.65

72


Z 0 M-6 0 -M 0 4-M 0 -M 0 0.65M+3.8

X1 1 0 0 0 0 1 0 0 0 0.95

R2 0 1 0 0 0 -1 0 0 1 0.65 0.65/1=0.65

X2 0 1 0 0 -1 0 0 0 0 0.3 0.3/1=0.3

X3 0 0 1 0 0 1 0 -1 0 0.15

X2 0 1 0 0 0 0 1 0 0 0.95Iterasi III X2 masuk x2 keluarX2=pivot 0 1 0 0 -1 0 0 0 0 0.3

X1lama=baru 1 0 0 0 0 1 0 0 0 0.95

R2 lama 0 1 0 0 0 -1 0 0 1 0.65

-1x pivot 0 -1 0 0 1 0 0 0 0 -0.3

R2 baru 0 0 0 0 1 -1 0 0 1 0.35

X3lama=baru 0 0 1 0 0 1 0 -1 0 0.15

X2lama 0 1 0 0 0 0 1 0 0 0.95

-1x pivot 0 -1 0 0 1 0 0 0 0 -0.3

X2 baru 0 0 0 0 1 0 1 0 0 0.65

73


Z 0 0 0 -M M-6 4-M 0 -M 0 0.35M+5.6

X1 1 0 0 0 0 1 0 0 0 0.95

R2 0 0 0 0 1 -1 0 0 1 0.35 0.35/1=0.35

X2 0 1 0 0 -1 0 0 0 0 0.3

X3 0 0 1 0 0 1 0 -1 0 0.15

X2 0 0 0 0 1 0 1 0 0 0.65 0.65/1=0.65Iterasi IV X5 masuk R2 keluar

X5=pvt 0 0 0 0 1 -1 0 0 1 0.35

Z lama 0 0 0 -M M-6 4-M 0 -M 0 0.35M+5.6(6-M)x pivot 0 0 0 0 6-M M-6 0 0 6-M -0.35M+2.1

Z baru 0 0 0 -M 0 -2 0 -M 0 7.7

X1 lama=baru 1 0 0 0 0 1 0 0 0 0.95

X2lama 0 1 0 0 -1 0 0 0 0 0.3

1x pivot 0 0 0 0 1 -1 0 0 1 0.35

X2 baru 0 1 0 0 0 -1 0 0 1 0.65

X3lama=baru 0 0 1 0 0 1 0 -1 0 0.15

74

X2 lama 0 0 0 0 1 0 1 0 0 0.65

-1x pivot 0 0 0 0 -1 1 0 0 -1 -0.35

X2 baru 0 0 0 0 0 0 1 0 -1 0.30

Iterasi optimal karena koefisien Z negatif semua


Z 0 0 0 -M 0 -2 0 -M 0 7.7

X1 1 0 0 0 0 1 0 0 0 0.95

X2 0 1 0 0 0 -1 0 0 1 0.65

X3 0 0 1 0 0 1 0 -1 0 0.15

X5 0 0 0 0 1 -1 0 0 1 0.35

X2 0 0 0 0 0 0 1 0 -1 0.30

75

Solve the problem grafically and simplex at class sessionAssume that there are two sites along a stream, i = 1,2, at which waste (BOD) is discharged. See the plan situation at the the problem before. Currently, without any wastewater treatment, the quality (DO), q2 and q3 at each of sites 2 and 3 is less than the minimum desired, Q2 and Q3, respectively. For each unit of waste removed at

site i upstream of site j, the quality improves by Aij.How much treatment is required at sites 1 and 2 that meets the standards at a minimum total cost? Following are the necessary data:C1= 6 per unit of waste treatment at site 1; C2 = 10 per unit of waste treatment at site 2

A12 = 1/20 W1= 100 Q2= 6

A13 = 1/40 W2= 75 Q3= 4

A23 = 1/30 q2= 3 q3= 1

76

Min Z = 6 X1 + 10 X2

A12 = 1/20 W1= 100 Q2= 6

A13 = 1/40 W2= 75 Q3= 4

A23 = 1/30 q2= 3 q3= 1While meeting the desired quality standards Q j at sites j = 2 and 3:

q2 + a12 W1X1 Q2

q3 + a13 W1X1 + a23 W2X2 Q3

The desired water quality at site 2 : q2 + a12 W1X1 Q2

which yield 3 + (0.05)(100) X1 6

or X1 6……………….1

The desired water quality at site 3 : q3 + a13 W1X1 + a23 W2X2 Q3

which yield 1 + (0.025)(100) X1 + (0.033)(75) X2 4

or X1 + X2 .2………….2

77X1( 1.2,0)

X1 0.6

X1 + X2 1.2(0.6,0.6)

1.2

1.0

0.5

X2

0.6

78

Min Z = 6 X1 + 10 X2

Constraint : X1 0.6 X1 + X2 1.2 X2 0

X1 + X2 = 1.2 X1 = 1.2X2 = 0Bila Z = 6 X1 + 10 X2

Dan X1, X2 = (1.2, 0) Titik paling Extrim minimal. Maka Z = 6 x 1.2 + 10 x 0= 7.2 (Optimal)

79

Penyelesaian dengan Solver

Min Z = 6 X1 + 10 X2Constraint :

X1 >= 0.6 X1 + X2 >= 1.2

X2 >= 0

X1 X2 OBJ. Func Constraint1.2 0 7.2

X1 >= 0.6X1+ X2 >= 1.2

80

Structure a linear programming model for estimating the quantities of

each of the two crops that should be produced in order to

maximize total income. Solve the problem graphically and

simplex method, using the following data :

Resources Requirements per unit of Maximum AvailableCrop A Crop B Resources

Water 2 3 60Land 5 2 80

Fertilizer 3 2 60Labor 1 2 40

Unit price 30 25

82

X2

40

30

20

10

0 10 20 30 40 X1

2)

3)

4)

1)10.91, 12.73

83

Perpotongan pers 1 & 2 merupakan paling maximal

2X1+3 X2 = 60------ X2 =(60-2 X1)/3

5 X1+2 X2 = 80------- X1=(80-2/3(60-2 X1))/5

X1=10.91--- X2=12.73

Bentuk standard :

Z - 30 X1 - 25 X2 = 0

2 X1 + 3 X2 + S1 = 60

5 X1 + 2 X2 + S2 = 80

3 X1 + 2 X2 + S3 = 60

X1 + 2 X2 + S4 = 40

84

Basic Z X1 X2 S1 S2 S3 S4 Sol

Z 1 -30 -25 0 0 0 0 0S1 0 2 3 1 0 0 0 60 60/2=30S2 0 5 2 0 1 0 0 80 80/5=16 *S3 0 3 2 0 0 1 0 60 60/3=20S4 0 1 2 0 0 0 1 40 40/1=40

Iterasi 1 : X1 masuk S2 keluar

X1=pivot 0 1 2/5 0 1/5 0 0 16 X1=pivot

Z lama 1 -30 -25 0 0 0 0 030xpivot 0 30 12 0 6 0 0 480 30xpivotZ baru 1 0 -13 0 6 0 0 480 Z baru

S1lama 0 2 3 1 0 0 0 60-2xpivot 0 -2 -4/5 0 -2/5 0 0 -32 -2xpivotS1baru 0 0 11/5 1 -2/5 0 0 28 S1baru

S3lama 0 3 2 0 0 1 0 60 S3lama-3xpivot 0 -3 -6/5 0 -3/5 0 0 -48 -3xpivotS3baru 0 0 4/5 0 -3/5 1 0 12 S3baru

S4lama 0 1 2 0 0 0 1 40 S4lama-1xpivot 0 -1 -2/5 0 -1/5 0 0 -16 -1xpivotS4baru 0 0 8/5 0 -1/5 0 1 24 S4baru

85


Z 1 0 -13 0 6 0 0 480

S1 0 0 11/5 1 -2/5 0 0 28 28:11/5=12.73

X1 0 1 2/5 0 1/5 0 0 16 16:2/5= 40

S3 0 0 4/5 0 -3/5 1 0 12 12:4/5=15

S4 0 0 8/5 0 -1/5 0 1 24 24:8/5=15

Iterasi 2 : X2 masuk S1 keluarX2 = pivot 0 0 1 5/11 -2/11 0 0 140/11

Z lama 1 0 -13 0 6 0 0 480

-(-13)x pivot 0 0 13 65/11 -26/11 0 0 165.4

Z baru 1 0 0 65/11 40/11 0 0 645.4

X1 lama 0 1 2/5 0 1/5 0 0 16

-2/5x pivot 0 0 -2/5 -2/11 4/55 0 0 -56/11

X1 baru 0 1 0 -2/11 15/55 0 0 120/11

S3 lama 0 0 4/5 0 -3/5 1 0 12

-4/5x pivot 0 0 -4/5 -4/11 8/55 0 0 -112/11

S3 baru 0 0 0 -4/11 25/55 1 0 20/11

S4 lama 0 0 8/5 0 -1/5 0 1 24

-8/5x pivot 0 0 -8/5 -8/11 16/55 0 0 -224/11

S4 baru 0 0 0 -8/11 5/55 0 1 40/11

86

Tabel Optimal koefisien Z positif untuk maximize dengan nilai 645.4


Z 1 0 0 65/11 40/11 0 0 645.4X2 0 0 1 5/11 -2/11 0 0 140/11X1 0 1 0 -2/11 15/55 0 0 120/11

S3 0 0 0 -4/11 25/55 1 0 20/11S4 0 0 0 -8/11 5/55 0 1 40/11

Exercise on Irrigation Planning and Operation.

In Algeria there are two distinct cropping intensities, depending on

the availability of water. Consider a single crop that can be grown

under intensive rotation or extensive rotation on a total of A hectare.

Assume that the annual water requirements for the intensive rotation

policy are 16,000 m3 per hectare, and for extensive rotation policy

87

they are 4000 m3 per hectare. The annual net production returns are

4000 and 2000 dinars respectively. If the total water available is

320,000 m3, show that as the available land area A increases, the

rotation policy that maximizes total net income changes from one

that is totally intensive to one that is increasingly extensive.

Would the same conclusions hold if instead of fixed net incomes of

4000 and 2000 dinars per hectare of intensive and extensive rotation,

the net income depended on the quantity of crop produced?

Assuming that intensive rotation produces twice the crop yield of

extensive rotation, and that the net income per unit of crop yield Y is

defined by simple linear function 5-0.05 Y, develop and solve a

linear programming model to determine the optimal rotation policies

if A equals 20, 50,80.

88

a. Max : Z = 4000 X1 + 2000 X2

Constraints : 16000 X1 + 4000 X2 320000

X1 + X2 20

Solving Graficaly :

16000 X1 + 4000 X2 = 320000

X1 + X2 = 20

89X1

X2

80

20

( 20 ,0)

Optimum Point : (20,0)

90

1) X1 + X2 = 20 X1 = 20 – 80+4X1 X1 = 20 ;X2 = 02) X1 + X2 = 50 X1 = 50 - 80+4X1 X1 = 10 ; X2 = 403) X1 + X2 = 80 X1 = 80 - 80+4X1 X1 = 0 ; X2 = 80

Using Solver Solution

Exercise Solution 16 a

Max : Z = 4000 X1 + 2000 X2 Constraints : 16000 X1 + 4000 X2 <= 320000

X1 + X2<= 20Intensif Extensif Objective Function Constrain

tArea (X1) Area (X2) Z

20 0 80000 X1 + X2 <= 20 20 Area (Ha)16000 X1 + 4000 X2 <= 320000 320000 Water(M3)

91

Using Solver Solution

Exercise Solution 16 a


X1 + X2<= 50

92


X1 + X2<= 5010 40 120000

X1 + X2 <= 50 50 Area (Ha)16000 X1 + 4000 X2 <= 320000 320000 Water(M3)


X1 + X2<= 80

0 80 160000 X1 + X2 <= 80 80 Area (Ha)

16000 X1 + 4000 X2 <= 320000 320000 Water(M3)

93

Exercise Solution 16 b

Max : Z=X1(5-0.05 T1) T1+ X2 (5-0.05 T2 )T2Constraint : T1 = 2xT2

1) X1 + X2 <= 20

2) X1 + X2 <= 50

3) X1 + X2 <= 80

X1>=5

X2>=5

Intensive Extensive Obj. Function Constraints

T1 T2 Z

54 27 2356 54 Yield (T1,T2)

15 5 20 20 Area( X1 + X2)16000 4000 260000 320000 Water(M3)

94

75 37 5625 75 Yield (T1,T2)

10 40 50 50 Area( X1 + X2)16000 4000 320000 320000 Water(M3)

87.5 43.75 7656.25 87.5 Yield (T1,T2)5 60 65 80 Area( X1 + X2)

16000 4000 320000 320000 Water(M3)

95

Penjelasan Kuliah Ke 17Selesaikan semua contoh soal dan latihan pada kuliah 13-16 dengan menggunakan program Solver.

Soal 13Minimumkan z = 4x1 + x2Dengan batasan3x1 + x2 = 34x1 + 3x2 >=6x1 + 2x2 <= 4x1, x2 >= 0

x1 x2 Z Batasan0.4 1.8 3.40

3 37 64 4

96

Soal 13Minimumkan z = 4x1 + x2Dengan batasan3x1 + x2 = 34x1 + 3x2 >=6x1 + 2x2 <= 4x1, x2 >= 0

x1 x2 Z Batasan0.4 1.8 3.40

3 3

7 64 4

management sda s2

Documents