modul i - kantong dunia | everything about our world … · web viewpenyelesaian persoalan...

MODUL PRAKTIKUM

PROGRAM LINEAR

DISUSUN OLEH :

NOORMA YULIA MEGAWATI, S.Si, M. Sc.

LABORATORIUM MATEMATIKA

FAKULTAS SAINS & TEKNOLOGI

UIN SUNAN KALIJAGA

YOGYAKARTA

2011

MODUL I

PENYELESAIAN PROGRAM LINEAR DENGAN METODE GRAFIK

Masalah program linear adalah masalah untuk menentukan titik yang

memaksimumkan atau meminimumkan fungsi objektif linear dan memenuhi kendala linear.

Bentuk umum dari masalah program linear diberikan sebagai berikut,

Meminimumkan/memaksimumkan ,

dengan kendala ;

.

Masalah diatas dapat disederhanakan dengan menggunakan notasi vektor. Misalkan

, maka masalah diatas menjadi

Meminimumkan/ memaksimumkan

Dengan kendala

Masalah program linear dapat diselesaikan dengan bantuan computer, yaitu

menggunakan QSB+, TORA, WinQSB, dan Matlab. Masalah program linear dua variabel

dapat diselesaikan dengan menggunakan metode grafik. Salah satu software yang dapat

digunakan untuk menyelesaikan masalah program linear dengan metode grafik adalah

QSB+ atau WinQSB.

Jika akan menjalankan program WinQSB, klik Start – All Programs - WinQSB .

Didalam WinQSB tersebut terdapat 19 menu utama

Untuk menyelesaikan masalah program linear, maka kita pilih Linear and Integer

Programming. Maka akan muncul

Contoh :

Diketahui masalah program linear

Maksimumkan

Dengan kendala

Untuk menyelesaikan masalah PL diatas dengan menggunakan WinQSB+, pilih menu File -

New problem, maka di layer akan muncul

Dalam layar tersebut berisi tentang :

1. Problem Title : Memberi nama masalah program linear yang akan

diselesaikan

2. Number of Variables : Banyaknya variable dalam masalah program linear yang

akan diselesaiakan

3. Number of Constraints : Banyaknya kendala yang terdapat dalam masalah PL yang

akan diselesaiakan

4. Objective Criterion : Krteria dari fungsi tujuan dalam masalah PL yang akan

diselesaikan, yaitu masalah maksimum atau masalah minimum

5. Default Variable Type : Tipe variable dalam masalah PL

a. Nonnegative continuous : jika variable masalah PL merupakan bilangan real

non negative

b. Nonnegatif Integer : jika variable dalam masalah PL merupakan bilangan

bulat non negative

c. Binary [0,1] : jika variable dalam masalah PL hanya mempunyai

nilai 0 atau 1

d. Unsigned / unrestricted : jika variable dalam masalah PL tidak mempunyai

batasan nilai

6. Data Entry Format

a. Spredsheet Matrix Form : untuk pengisian data adalam bentuk matriks, yaitu

berbentuk

b. normal model Form : untuk pengisian data dalam bentuk norma, yaitu

berbentuk

Untuk masalah diatas, maka dimasukkan entri – entri seperti pada layar berikut

Setelah selesai mengentri pada isian awal, kemudian klik Ok maka akan muncul jendela

batas atas xi

(M menandakan bialangan yang cuku besar atau mendekati tak hingga)batas bawah xi

nilai bi

Kendala 3 masalah PLKendala 1 masalah PLKendala 2 masalah PL

Fungsi tujuan masalah PL

Berdasarkan masalah PL diatas, maka masukkan data tersebut pada jendela diatas, maka

akan diperoleh

Untuk menyelesaikan soal tersebut pilih menu Solve and Analysis – Graphic Method atau

klik ikon , maka akan muncul

Dalam jendela diatas, pilih horizontal axis untuk variable x1 dan veritical axis untuk

variable x2, kemudian klik OK maka akan muncul grafik

Keterangan :

1. Nomor yang dilingkari merupakan nomor persamaan garis yang bersesuaian dengan

kendala.

2. Titik sudut yang dilingkari merupakan titik sudut yang memberikan penyelesaian

optimal.

3. Garis merah tebal merupakan garis selidik.

4. Daerah yang berwarna ungu (di layer computer) merupakan daerah fisibel.

5. Titik Putih tebal merupakan titik optimal penyelesaian masalah PL.

6. Untuk mengubah warna atau range dari sumbu koordinat dalam grafiknya dapat

dilakukan dengan memilih menu Option – Change XY Range and Colors, maka

akan muncul jendela

Klik bagian yang akan diganti warnanya. Setelah selesai pilih OK, Selanjutnya Klik

Options – Change XY Variables dan terakhir pilih menu Options – Redraw Graphic

Solution.

Penyelesaian optimal Contoh 1 adalah .

Contoh 2 :

Minimumkan

Dengan kendala

Selesaikan dengan metode grafik!

Penyelesaian :

Masukkan input data diatas, maka akan muncul

Penyelesaian optimal Contoh 2 adalah .

LATIHAN

Selesaikanlah menggunakan metode grafik

1. Maksimumkan

Dengan kendala

2. Minimumkankan

Dengan kendala

3. Farmer Jones bakes two types of cake (chocolate and

vanilla) to supplement his income. Each chocolate cake can be sold for $1, and each

vanilla cake can be sold for 50 ¢. Each chocolate cake requires 20 minutes of baking

time and uses 4 eggs. Each vanilla cake requires 40 minutes of baking time and uses 1

eggs. Eight hours of baking time and 30 eggs are available. Formulate an LP to

maximize Farmer Jones’s revenue. Then graphically solve the LP.

MODUL II

KEJADIAN KHUSUS MASALAH PL DUA VARIABEL.

Ada 3 kejadian khusus dalam masalah program linear 2 variabel, yaitu

1. Masalah PL mempunyai penyelesaian alternative.

2. Masalah PL tidak mempunyai penyelesaian optimal (infeasible solution)

3. Masalah PL mempunyai penyelesaian tak terbatas (Unbounded Solution)

4. Masalah PL dengan variabelnya tidak mempunyai batasan nilai

Contoh 1 : Maksimumkan

Dengan kendala

Penyelesaian :

Masukkan input data diatas, maka akan muncul

Keterangan :

Masalah PL pada contoh 1 mempunyai penyelesaian alternative. Garis selidik berhimpit

dengan persamaan garis kendala pertama. Penyelesaian optimal berada pada garis AB

dengan A (0,6) dan B(4,0) dan nilai maksimum .


Dengan kendala

Penyelesaian :


Dengan kendala

Penyelesaian :

Contoh 4 : Min

s.t.

Penyelesaian :

Kemudian Klik OK dan masukkan data soal, maka diperoleh

Karena hanya variable x2 yang tidak mempunyai batasan nilai, maka untuk tipe variable di

x1 diganti menjadi continuous. Penyelesaian persoalan diperoleh hasil

Penyelesaian optimal contoh 4 adalah dicapai untuk

MODUL III

PENYELESAIAN PROGRAM LINEAR dengan WinQSB

Program WinQSB menyelesaiakan masalah PL dengan metode simpleks. Tabel tiap

iterasi dapat ditampilkan jika jumlah iterasinya sedikit.

Contoh 1: Maks

s.t.

Penyelesaian :

Setelah selesai memasukkan data soal, pilih menu Solve and Analyze dan pilih menu Solve

and display step atau klik ikon . Maka di layar akan muncul

Untuk melihat iterasi selanjutnya pilih menu Simplex Iteration – Next Iteration atau klik

ikon , maka akan muncul

Kemudian untuk melihat iterasi selanjutnya pilih menu Simplex Iteration – Next Iteration,

atau klik ikon , maka akan muncul

Kemudian untuk melihat iterasi selanjutnya pilih menu Simplex Iteration – Next Iteration

sampai muncul jendela yang berisi bahwa The Simplex Method is complete. Dalam

masalah diatas setelah iterasi ketiga, proses iterasi berhenti. Maka dapat ditarik kesimpulan

bahwa dalam masalah PL tersebut yang diselesaiakn dengan menngunakan metode

simpleks akan terdapat 3 iterasi. Dari table iterasi terakhir, terlihat bahwa solusi

optimumnya adalah yang dicapai untuk . Atau untuk melihat hanya hasil akhirnya pilih

menu Solve and Analyze atau klik ikon .

Contoh 2 : Min

s.t.

Penyelesaian :

Kemudian diselesaiakn dengan menggunakan metode Simpleks yang memberikan iterasi

sebagai berikut

Diperoleh bahwa terdapat 3 iterasi. Dari table akhir, terlihat bahwa solusi optimumnya

adalah yang dicapai untuk .

Tambahan untuk variable yang tidak mempunyai batasan nilai

Latihan :

Selesaikan dengan menggunakan WinQSB

1. Max

s.t.

2. Min

s.t.

3. Max

s.t.

MODUL IV

PENYELESAIAN PROGRAM LINEAR dengan TORA

Program TORA dibuat oleh Hamdy Taha pada tahun 1989. Untuk menjalankan

program Tora, pilih menu TORA.exe. Tampilan pertama di layar setelah memilih menu

TORA.exe adalah

Kemudian tekan sembarang tombol keybord, maka di layer akan muncul 7 menu utama,

yaitu

Keterangan :

Menu 1 : menjalankan aplikasi untuk masalah program linear.

Menu 2 : menjalankan aplikasi untuk masalah model transportasi

Menu 3 : menjalankan aplikasi untuk masalah model jaringan

Menu 4 : menjalankan aplikasi untuk masalah program bilangan bulat

Menu 5 : menjalankan aplikasi untuk masalah analisa antrian.

Menu 6 : menjalankan aplikasi untuk masalah histogram

Menu 7 : menjalankan aplikasi untuk masalah model inventory.

Pilih menu Linear programming, maka di layer akan muncul

Keterangan :

1. Read an existing data file : Untuk membaca masalah PL yang telah disimpan

di drive komputer

2. Enter new problem : Untuk memasukkan input masalah PL baru.

Pilih menu Enter new data, maka

Keterangan :

1. Problem Title : Judul masalah PL yang akan dimasukkan datanya

2. Nbr of Variables : Jumlah variabel ada dalam masalah PL

3. Nbr of Constrains :Jumlah kendala ada dalam masalah PL

4. User – defined Vars Names (y/n) : Ketik y jika kita ingin mendefinisikan

sendiri nama variable jika tidak ketik n

5. Nonzero lower Bounds (y/n) : Ketik y jika terdapat batas bawah yang tidak

nol jika tidak tidak ada ketik n

6. Finite Upper Bounds (y/n) : Ketik y jika terdapat batas atas yang berhingga,

tetapi jika tidak ada ketik n

7. Unrestricted Variables (y/n) : Ketik y jika terdapat variabel yang tidak

mempunyai batasan nilai.

Contoh 1: Maks

s.t.

Penyelesaian :╒═════════════════════════════♦Enter new problem♦══════════════════════════════╕

│INS ← → BS DEL:Edit cell, ESC:Goto preceding cell, ↑↓:Go Up/Dn, ◄═╝:Exit cell │

├──────────────────────────────────────────────────────────────────────────────┤

│Problem Title : contoh1 │

│Nbr of Variables : 3 ← Indexed VARIABLES names: x1 to x3 │

│Nbr of Constraints : 3 │

│User-defined Vars Names (y/n)? : n │

│Nonzero Lower Bounds (y/n)? : n │

│Finite Upper Bounds (y/n)? : n │

│Unrestricted Variables (y/n)? : n │

├──────────────────────────────────────────────────────────────────────────────┤

│ max/min x1 x2 x3 │

│Obj. Function: max 3 2 1 │

├──────────────────────────────── ────────-----------──────────────────────────┤

Setelah fungsi tujuan dimasukkan kemudian tekan Enter dan masukkan kendala pertama.

x1 x2 x3 < = > RHS

Constraint 1: 1 2 -2 <= 20

Tekan Enter kemudian masukkan kendala kedua.

x1 x2 x3 < = > RHS

Constraint 2: -1 3 5 <= 30

Tekan Enter kemudian masukkan kendala ketiga.

x1 x2 x3 < = > RHS

Constraint 3: -1 -6 4 >= 15

Seteleah data lengkap tekan tombol F8, maka di lyar akan muncul

Do you wish to save this (new or modified) set of data (y/n)?

Ketik y jika ingin menyimpan data tersebut dalam drive computer . Contoh untuk

menyimpan data PL : c:\contoh1. Di dalam file contoh 1 tersimpan data sebagai berikut╒══════════════════════════════════════════════════════════════════════════════╕

│contoh1 Size: 3 constrs x 3 vars │

├──────────────────────────────────────────────────────────────────────────────┤

│ │

│ │

│ x1 x2 x3 RHS │

│─────────────────────────────────────────────────────────── │

│max 3 2 1 │

│─────────────────────────────────────────────────────────── │

│Constraint 1: 1 2 -2 <= 20 │

│Constraint 2: -1 3 5 <= 30 │

│Constraint 3: -1 -6 4 >= 15 │

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

Jika data tidak disimpan ketik n, kemudian tekan Enter, maka di layar akan terlihat ╒═════ SOLVE/MODIFY ════╕

│ Solve Problem │

│ Modify data ╒══════ PROCEDURE ══════╕

│ View data │Automated procedure │

│ Print data │User-guided procedure │

└───────────────────└───────────────────────┘

│ Use ↑ or ↓ then ◄│ Use ↑ or ↓ then ◄═╝ │

└───────────────────└───────────────────────┘

Pada menu solve problem terdapat 2 pilihan menu, yaitu Automated procedure dan User –

guided procedure. Jika dipilih menu Automated procedure, maka di layar akan muncul╒══════════════ OPTIMUM ══════════════╕

│View solution/sensitivity summary │

│Print solution/sensitivity summary │

│Obtain alternative optimum │

│View optimum tableau │

│Print optimum tableau │

│View original data │

│Print original data │

└─────────────────────────────────────┘

│ Use ↑ or ↓ then ◄═╝ │

└─────────────────────────────────────┘

Jika dipilih menu view optimum tableau, maka di layar akan muncul ╒══════════════════════════════════════════════════════════════════════════════╕

│contoh1 max (phase_2) (Final)Iteration No: 4 │

├──────────────────────────────────────────────────────────────────────────────┤

│ Basic x1 x2 x3 Sx4 sx5 sx6 Rx7 │

│─────────────────────────────────────────────────────────────────────────── │

│ z 0.00 133.00 0.00 16.00 0.00 13.00 -16.00 │

│─────────────────────────────────────────────────────────────────────────── │

│ 1) sx5 0.00 -22.00 0.00 -3.00 1.00 -2.00 3.00 │

│ 2) x1 1.00 42.00 0.00 5.00 0.00 4.00 -5.00 │

│ 3) x3 0.00 9.00 1.00 1.00 0.00 1.00 -1.00 │

│─────────────────────────────────────────────────────────────────────────── │

│+/-=(x+ - x-) s/S=slack/Surplus R=artif '=upper bd =inv(B) │

└───────────────────── <PgUp/PgDn>Scroll <F6>Optimum Menu ────────────────────┘

Dalam menu View solution / sensitivity summary terdapat 2 bagian table, yaitu Optimum

Solution Summary dan Sensitivity Analysis.╒══════════════════════════════════════════════════════════════════════════════╕

│contoh1 max Final Iteration No: 4 │

├──────────────────────────────────────────────────────────────────────────────┤

│ *** OPTIMUM SOLUTION SUMMARY *** │

│Obj value = 150.0000 │

│───────────────────────────────────────────────────────────────────────────── │

│ Variable Value Obj Coeff Obj Val Contrib │

│───────────────────────────────────────────────────────────────────────────── │

│ x1 45.0000 3.0000 135.0000 │

│ x2 0.0000 2.0000 0.0000 │

│ x3 15.0000 1.0000 15.0000 │

│ More to come... Press PgDn/PgUp to scroll │

╒══════════════════════════════════════════════════════════════════════════════╕


├──────────────────────────────────────────────────────────────────────────────┤


│Obj value = 150.0000 │

│───────────────────────────────────────────────────────────────────────────── │

│Constraint RHS Slack(-)/Surplus(+) │

│───────────────────────────────────────────────────────────────────────────── │

│1 (<) 20.0000 5.0000- │

│2 (<) 30.0000 0.0000- │

│3 (>) 15.0000 0.0000+ │


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


Contoh 2 : Min

s.t.

Penyelesaian :

Pada contoh 2 diatas merupakan variabel unrestricted sehingga dalam memasukkan input

data diberi nilai u.╒═════════════════════════════♦Enter new problem♦══════════════════════════════╕

│INS ← → BS DEL:Edit cell, ESC:Goto preceding cell, ↑↓:Go Up/Dn, ◄═╝:Exit cell │

├──────────────────────────────────────────────────────────────────────────────┤

│Problem Title : contoh2 │

│Nbr of Variables : 2 ← Indexed VARIABLES names: x1 to x2 │

│Nbr of Constraints : 2 │

│User-defined Vars Names (y/n)? : n │

│Nonzero Lower Bounds (y/n)? : n │

│Finite Upper Bounds (y/n)? : n │

│Unrestricted Variables (y/n)? : y │

├──────────────────────────────────────────────────────────────────────────────┤

Masukkan input data contoh 2. Hasil dari view data akan terlihat╒══════════════════════════════════════════════════════════════════════════════╕

│contoh2 Size: 2 constrs x 2 vars │

├──────────────────────────────────────────────────────────────────────────────┤

│ x1 x2 RHS │

│───────────────────────────────────────────────────---------------------------│

│min -2 1 │

│───────────────────────────────────────────────────---------------------------│

│Constraint 1: 1 1 <= 4 │

│Constraint 2: 1 -1 <= 6 │

│───────────────────────────────────────────────────---------------------------│

│Unrest. Vars: u │

|------------------------------------------------------------------------------|

Keterangan :

u : unrestricted

Diperoleh solusi optimum╒══════════════════════════════════════════════════════════════════════════════╕

│contoh2 min Final Iteration No: 3 │

├──────────────────────────────────────────────────────────────────────────────┤


│Obj value = -11.0000 │

│───────────────────────────────────────────────────────────────────────────── │


│───────────────────────────────────────────────────────────────────────────── │

│ x1 5.0000 -2.0000 -10.0000 │

│ x2 -1.0000 1.0000 -1.0000 │

│ │



MODUL V

KEJADIAN KHUSUS PADA MASALAH PL

Ada 3 kejadian khusus dalam masalah program linear dengan penyelesaian menggunakan

table simpleks, yaitu

1. Masalah PL mempunyai penyelesaian alternative.

Jika dalam table optimal terdapat variabel non basis dengan bernilai nol maka ada

dua kemungkinan, yaitu penyelesaian tunggal atau ada penyelesaian alternatif.

2. Masalah PL tidak mempunyai penyelesaian optimal (infeasible solution)

Model PL dikatakan infeasible jika terdapat variabel semu bernilai positif dalam

table optimal.

3. Masalah PL mempunyai penyelesaian tak terbatas (Unbounded Solution)

Model PL dikatakan unbounded solution jika pada suatu ietrasi semua elemen

kolom kunci dalam table simpleks tidak ada yang positif (negative atau nol).

4. Masalah PL Degenerate

Model PL dikatakan degeneracy jika ada paling sedikit satu variabel basis dalam

penyelesaian optimal bernilai nol. Penyelesaiannya disebut degenerate.

Contoh 1 :

Maksimukan

Dengan kendala

Penyelesaian :

Iterasi 1

Iterasi 2

Next Iteration masalah diatas, memunculkan jendela

Contoh 2 :

Maksimumkan

Dengan kendala

Penyelesaian :

Iterasi 1

Iterasi 2

Penyelesaian masalah diatas, akan memunculkan jendela

Contoh 3 :

Maksimumkan

Dengan kendala

Penyelesaian :

Dengan menggunakan WinQSB akan diperoleh penyelesaian :

Untuk melihat penyelesaian alternative yang lain klik menu Results – Optain Alternate

Optimal, maka akan diperoleh penyelesaian

Dengan menggunakan TORA, maka diperoleh╒══════════════════════════════════════════════════════════════════════════════╕


├──────────────────────────────────────────────────────────────────────────────┤


│Obj value = 12.000 ==> (Alternative solution detected at x4 ) │

│───────────────────────────────────────────────────────────────────────────── │


│───────────────────────────────────────────────────────────────────────────── │

│ x1 2.1818 3.0000 6.5455 │

│ x2 2.7273 2.0000 5.4545 │

│ │


Maslah ini mempunyai penyelesaian alternative untuk yang merupakan variabel slack .

Tekan F6 kemudian pilih menu Obtain alternative optimum, kemudian isi Variable nbr : 4

. Tekan Eneter, kemudian pilih menu View solution / optimum summary, maka akan di

layar akan muncul╒══════════════════════════════════════════════════════════════════════════════╕


├──────────────────────────────────────────────────────────────────────────────┤


│ │

│Obj value = 12.000 ==> (Alternative solution detected at x1 ) │

│───────────────────────────────────────────────────────────────────────────── │


│───────────────────────────────────────────────────────────────────────────── │

│ x1 0.0000 3.0000 0.0000 │

│ x2 6.0000 2.0000 12.0000 │

│ │


Penyelesaian optimal contoh 3 adalah atau dengan .

BAB VI

APLIKASI PROGRAM LINEAR

A company produces A, B, and C and can sell these products in unlimited quantities at the

following unit prices : a , $10; B, $56; C, $100. Producing 1 unit of A requires 1 hour of

labor. Producing 1 unit of B requires 2 hour of labor plus 2 units of A. Producing 1 unit of

C requires 3 hour of labor plus 1 unit of B. Any A that is used to produce B cannot be sold.

Similarly, any B that is used to produce C cannot sold. A total of 40 hours of labor are

available. Formulate an LP to maximize the company’s revenue.

Penyelesaian :

Misalkan :

: banyaknya produk A yang dihasilkan

: banyaknya produk B yang dihasilkan

: banyaknya produk C yang dihasilkan dan dijual

: banyaknya produk A yang dijual

: banyaknya produk B yang dijual.

1. Fungsi tujuan : memaksimumkan keuntungan

Keuntungan = hasil penjualan produk A + hasil penjualan produk B + hasil penjualan

produk C

=

=

2. Kendala :

a. Waktu yang disediakan adalah 40 jam

Total waktu produksi = waktu produksi produk A + waktu produksi produk B +

waktu produksi produk C

=

Maka

b. Produksi

Maka

Maka

c. Non negative

Akibatnya, masalah PL untuk soal diatas adalah

Maksimumkan

Dengan kendala

Dengan menggunakan TORA, input datanya menjadi ╒══════════════════════════════════════════════════════════════════════════════╕

│masalah1 Size: 3 constrs x 5 vars │

├──────────────────────────────────────────────────────────────────────────────┤

│ x1 x2 x3 x4 x5 RHS │

│─────────────────────────────────────────────────────────────────────────── │

│max 0 0 100 10 56 │

│─────────────────────────────────────────────────────────────────────────── │

│Constraint 1: 1 2 3 0 0 <= 40 │

│Constraint 2: 1 -2 0 -1 0 = 0 │

│Constraint 3: 0 1 -1 0 -1 = 0 │

│─────────────────────────────────────────────────────────────────────────── │

Dan solusi optimumnya adalah╒══════════════════════════════════════════════════════════════════════════════╕

│masalah1 max Final Iteration No: 4 │

├──────────────────────────────────────────────────────────────────────────────┤


│ │

│Obj value = 571.4286 │

│───────────────────────────────────────────────────────────────────────────── │


│───────────────────────────────────────────────────────────────────────────── │

│ x1 11.4286 0.0000 0.0000 │

│ x2 5.7143 0.0000 0.0000 │

│ x3 5.7143 100.0000 571.4286 │

│ x4 0.0000 10.0000 0.0000 │

│ x5 0.0000 56.0000 0.0000 │

│ │


Diperoleh bahwa nilai optimum dengan .

Latihan Soal

1. A company makes two types of sofas, regular and long, at two locations, one in

Hickory and one in Lenoir. The plant in Hickory has a daily operating budget of

$45,000 and can produce at most 300 sofas daily in any combination. It costs $150 to

make a regular sofa and $200 to make a long sofa at the Hickory plant. The Lenoir

plant has a daily operating budget of $36,000, can produce at most 250 sofas daily in

any combination and makes a regular sofa for $135 and a long sofa for $180. The

company wants to limit production to a maximum of 250 regular sofas and 350 long

sofas each day. If the company makes a profit of $50 on each regular sofa and $70 on

each long sofa, how many of each type should be made at each plant in order to

maximize profit? What is the maximum profit?

BAB VII

ANALISA SENSITIVITAS GRAFIK

Anlisa sensitivitas grafik yang dibahas adalah Perubahan Nilai Koefisien Fungsi Sasaran

dan Perubahan Nilai RHS.

Contoh :

Maksimumkan

Dengan kendala

Penyelesaian :

Dengan menggunakan TORA, diperoleh╒══════════════════════════════════════════════════════════════════════════════╕


├──────────────────────────────────────────────────────────────────────────────┤


│Obj value = 300.0000 │

│───────────────────────────────────────────────────────────────────────────── │


│───────────────────────────────────────────────────────────────────────────── │

│ x1 5.0000 12.0000 60.0000 │

│ x2 30.0000 8.0000 240.0000 │

│ │


│ │


╒══════════════════════════════════════════════════════════════════════════════╕


├──────────────────────────────────────────────────────────────────────────────┤


│Obj value = 300.0000 │

│───────────────────────────────────────────────────────────────────────────── │

│Constraint RHS Slack(-)/Surplus(+) │

│───────────────────────────────────────────────────────────────────────────── │

│1 (<) 150.0000 65.0000- │

│2 (<) 100.0000 0.0000- │

│3 (<) 80.0000 0.0000- │

│ │


│ │


╒══════════════════════════════════════════════════════════════════════════════╕


├──────────────────────────────────────────────────────────────────────────────┤

│ ***** SENSITIVITY ANALYSIS ***** │

│Obj value = 300.0000 │

│Obj Coeffs -- Single Changes: │

│───────────────────────────────────────────────────────────────────────────── │

│ Variable Current Coeff Min Coeff Max Coeff Reduced Cost │

│───────────────────────────────────────────────────────────────────────────── │

│ x1 12.0000 5.3333 16.0000 0.0000 │

│ x2 8.0000 6.0000 18.0000 0.0000 │

│ │


│ │


╒══════════════════════════════════════════════════════════════════════════════╕


├──────────────────────────────────────────────────────────────────────────────┤

│ ***** SENSITIVITY ANALYSIS ***** │

│Obj value = 300.0000 │

│Righthand Side -- Single Changes: │

│───────────────────────────────────────────────────────────────────────────── │

│Constraint Current RHS Min RHS Max RHS Dual Price │

│───────────────────────────────────────────────────────────────────────────── │

│1 (<) 150.0000 85.0000 infinity 0.0000 │

│2 (<) 100.0000 40.0000 120.0000 1.0000 │

│3 (<) 80.0000 66.6667 127.2727 2.5000 │

│ │


│ │


Dari table Sensitivity Analysis yang pertama terlihat bahwa untuk variabel berada diantara

dan variabel berada di antara . Sedangkan untuk table Sensitivity Analysis jika terjadi

perubahan RHS, maka untuk , nilai yang diperbolehkan adalah .

Dengan menggunkan WinQSB diperoleh

Dari tabel hasil optimal diatas terlihat bahwa perunahan nilai fungsi sasaran untuk variabel

berada diantara dan untuk variabel berada di antara . Sedangkan jika terjadi perubahan

RHS, maka untuk , nilai yang diperbolehkan adalah .

Bandingkan hasil diatas dengan hitung manual di bawah ini.

A. Perubahan Nilai Fungsi Sasaran

Fungsi tujuan masalah pemograman linear dengan dua variabel dapat ditulis

memaksimumkan / meminimumkan . Perubahan atau akan merubah gradient . Secara

grafik perubahan ini mungkin menyebabkan perubahan penyelesaian optimal berada pada

titik sudut yang berbeda dalam penyelesaian fisibel. Penyelesaian tidak berubah jika

berada dalam range optimalitas.

Perhatikan grafik berikut

Titik B merupakan perpotongan garis dan . Dari persamaan pertama diperoleh atau . Dari

persamaan kedua diperoleh atau . Diperoleh dua pertidaksamaan atau . Untuk artinya

grdaien garis fungsi tujuan bukan garis horizontal, artinya garis fungsi tujuan bukan garis

vertical.

Nilai dan yang memenuhi pertidaksamaan diatas menjamin bahwa penyelesaian optimum

tetap berada di titik sudut B (yang berubah nilai ). Perubahan koefisien fungsi tujuan yang

dimaksud adalah perubahan nilai saja atau saja.

tetap

Dari , diperoleh . Jika nilai diubah dalam range maka penyelesaian optimalnya

tetap di B (5,30).

Contoh : Tentukan penyelesaian optimum masalah 1 pada bagian I jika fungsi

tujuannya .

Penyelesaian : Solusi optimum di B (5,30) dengan nilai .

tetap

Dari, diperoleh . Jika nilai diubah dalam range maka penyelesaian optimalnya

tetap di B (5,30).

Contoh : Tentukan penyelesaian optimum masalah 1 pada bagian I jika fungsi

tujuannya .

Penyelesaian : Solusi optimum di B (5,30) dengan nilai .

B. Perubahan Nilai RHS

Dalam model PL biasanya RHS menyatakan batasan sumber. Jika nilai batas ini

diubah maka nilai -nya akan berubah (berkurang atau bertambah).

Titik B merupakan perpotongan dua garis yang bersesuaian dengan dan . Jika nilai

berubah (bertambah atau berkurang ) di sekitar 100 maka PO B akan berubah di sepanjang

garis AD. Titik dan berguna untuk menentukan range fisibilitas untuk . Nilai bersesuaian

dengan adalah . Nilai bersesuaian dengan adalah . Jadi, range fisibilitas untuk adalah .

Titik optimal B tetap merupakan perpotongan garis kendala ke – 2 dan ke – 3 jika

perubahan nilai sebesar , .

Didefinisikan (worth per unit or raw material )

Nilai pada A = 12 x 0 + 8 x =

Nilai pada D = 12 x + 8 x =

Diperoleh satuan harga / unit . Di dalam TORA dikenal sebahai dual price. Akibatnya,

perubahan 1 unit dalam range akan merubah (mengurangi atau menambah) sebesar

satuan harga.

Latihan soal

The Shader Electronics Company produces two products : (1) the Shader Walkman,

a portable CD/DVD player, and (2) the Shader Watch – TV, a wristwatch – size internet –

connected color television. The production process for each product is similar in that both

require a certain number of hours of electronic work and a certain number of labor – hours

in the assembly department. Each Walkman takes 4 hours of electronic work and 2 hours in

the assembly shop. Each Waych – TV requires 3 hours in electronics and 1 hour in

assembly. During the current production period, 240 hours of electronic time are available,

and 100 hours of assembly department time are available. Each Walkman sold yields a

profit of $7;each Watch – TV produced may be sold for a $5 profit.

Shader’s problem is to determine the best possible combination of

a. For what values of the price of Walkman would the current basis remain optimal?

b. For what values of the price of Watch - TV radio would the current basis remain

optimal?

c. If electronic time only 250 hours are available, would the current basis remain

optimal?

d. If assembly time 80 hours are available, would the current basis remain optimal?

e. Find the dual price of each constraint?

DAFTAR PUSTAKA

Wu, Nesa dan Richard Coppins, 1981, Linear Programming and Extensions. McGraww –

Hill, Inc., New York.

Winston, W.L., 2004, Operation Research Application and Algorithms, Ruxbury Press.

modul i - kantong dunia | everything about our world … · web viewpenyelesaian persoalan...

Documents