Tajuk 3 Pengaturcaraan Linear

7/28/2019 Tajuk 3 Pengaturcaraan Linear

1/17

MTE 3104 MATEMATIK KEPUTUSAN

TAJUK 3 PENGATURCARAAN LINEAR

3.1 SINOPSIS

Pengaturcaraan linear ialah satu kaedah matematik yang digunakan

untuk membantu pengurus-pengurus dalam merancang dan membuat

keputusan berdasarkan sumber-sumber yang ada. Dalam topik ini,

anda akan mempelajari bagaimana mendapatkan nilai optimum

penyelesaian bagi sesuatu masalah yang diberi syarat-syarat tertentu.

Terdapat dua kaedah yang biasa digunakan untuk menyelesaikan

masalah pengaturcaraan linear iaitu kaedah bergraf dan kaedah

simpleks.

3.2 HASIL PEMBELAJARAN

1. Menjelaskan erti pengaturcaraan linear

2. Mengenalpasti istilah-istilah penting yang digunakan dalam

pengaturcaraan linear

3. Meringkaskan semua langkah-langkah yang perlu diikuti untuk

menyelesaikan masalah pengaturcaraan linear dengan menggunakankaedah simpleks

3.3 KERANGKA TAJUK

15


2/17


3.4 Pengenalan

Pengaturcaraan linear adalah proses mengambil pelbagai ketaksamaan linear

yang berhubungan dengan beberapa situasi dan mencari nilai "terbaik" yang

boleh diperolehi di bawah syarat-syarat tertentu. Sebagai satu contoh, situasi

yang mengambil kira had, bahan-bahan dan tenaga buruh, dan kemudian

menentukan pengeluaran "terbaik" bagi keuntungan maksimum di bawah syarat-

syarat tertentu.Dalam "kehidupan sebenar", pengaturcaraan linear adalah sebahagian daripada

bidang matematik yang sangat penting dan dipanggil "teknik-teknik

pengoptimuman". Bidang pengajian (atau sekurang-kurangnya keputusan yang

dipohon itu) digunakan setiap hari dalam organisasi dan peruntukan sumber.

Sistem "kehidupan sebenar" ini boleh mempunyai berpuluh-puluh atau beratus-

ratus pemboleh ubah, atau lebih. Dalam algebra, anda menyelesaikan masalah

dengan mudah (atau melukis graf) dengan hanya menggunakan mana-mana

dua pembolehubah linear.

Proses umum untuk membuat graf bagi ketaksamaan ("kekangan") untuk

membentuk satu kawasan yang disempadani di satah - x, y (dipanggil "rantau

kemungkinan"). Kemudian anda tentukan koordinat sudut rantau kemungkinan

ini (iaitu titik-titik persilangan pelbagai pasangan garisan), dan menguji titik sudut

16

PengaturcaraanLinear

Definisi

Jenis-jenis masalahPengaturcaraan

Linear Kaedah simpleks


3/17


dalam formula (dipanggil "persamaan pengoptimuman") yang mana anda cuba

untuk mendapatkan nilai tertinggi dan terendah.

Contoh:

Cari nilai yang maksima dan minimum z = 3x + 4y tertakluk kepada kekangan

berikut:

Tiga ketaksamaan di atas adalah dipanggil kekangan. Kawasan satah yang

mereka merangkumi kekangan ini akan menjadi rantau kemungkinan (feasibleregion). "z = 3x + 4y" adalah persamaan pengoptimuman. Anda perlu mencari

sudut titik (x, y) bagi rantau kemungkinan yang memberikan nilai z yang terbesar

dan terkecil .

Langkah pertama adalah menukarkan setiap bentuk ketidaksamaan kepada

yang lebih mudah bagi melukis graf seperti di bawah:

Ia adalah mudah untuk melukis graf bagi sistem. Jika anda mengalami masalah

sila rujuk website http://www.purplemath.com/modules/syslneq.htm

17
http://www.purplemath.com/modules/syslneq.htmhttp://www.purplemath.com/modules/syslneq.htm


4/17


Untuk mencari titik sudut - yang tidak jelas dari graf cari titik persilangan bagi

garisan untuk membentuk sistem persamaan linear dan selesaikan.

Untuk sistem persamaan linear, rujuk website

http://www.purplemath.com/modules/syslin1.htm

Maka titik sudut adalah (2,6), (6,4) dan (-1, -3)

Terbukti untuk sistem linear seperti ini, nilai maksimum dan minimum bagi

persamaan pengoptimuman sentiasa berada di sudut rantau kemungkinan. Maka

18

= ( 1/2 ) x + 7

y = 3 x

y = ( 1/2 ) x + 7

y = x 2 y = 3 x

y = x 2

( 1/2 ) x + 7 = 3 x

x + 14 = 6 x14 = 7 x

2 = x

y = 3(2) = 6

( 1/2 ) x + 7 = x 2

x + 14 = 2 x 418 = 3 x

6 = x

y = (6) 2 = 4

3 x = x 22 x = 2 x = 1

y = 3(1) = 3

corner point at (2, 6) corner point at (6, 4) corner pt. at (1, 3
http://www.purplemath.com/modules/syslneq.htmhttp://www.purplemath.com/modules/syslneq.htm


5/17


untuk mendapatkan penyelesaian bagi latihan ini, cuma 3 titik yang perlu di

pertimbangkan ke dalam z = 3x + 4y

(2,6): z = 3 (2) + 4 (6) = 6 + = 30

(6,4): z = 3 (6) + 4 (4) = 18 + 16 = 34

(-1,-3): z = 3 (-1) + 4 (-3) = -3 - 12 = -15

Jadi maksima bagi z = 34 berlaku di (6, 4) dan minimum bagi z = - 15 berlaku di

(-1, -3)

3.5 Definisi

Untuk memahami kepentingan Pengaturcaraan Linear dalam menyelesaikan

masalah kehidupan seharian, istilah-istilah penting perlu di ketahui terlebihdahulu. Sila cari artikel berikut untuk lebih mengetahui tentang istilah dan definisi

yang digunakan dalam Pengaturcaraan Linear:

http://www.netmba.com/operations/lp/

http://www.cs.princtton.edu/courses/archive/spring03/cs/cs226/letures/lp-up.pdf

http://www.uta.edu/faculty/swafford/opma3308/LPchapter.pdf

3.6 Jenis-jenis Masalah Pengaturcaraan Linear

Sebarang vektor x yang memenuhi kekangan masalah pengaturcaraan linear

dinamakan sebagai penyelesaian kemungkinan masalah tersebut. Tiap- tiap

masalah pengaturcaraan linear boleh dikategorikan salah satu daripada yang

berikut:

1. 'Infeasible' atau tiada penyelesaian .

Masalah pengaturcaraan linear adalah 'infeasible' jika penyelesaian

masalah tidak wujud; iaitu, tidak terdapat vektor x yang memenuhikesemua kekangan masalah tersebut.

2. 'Unbounded' atau rantau terbuka .

Masalah pengaturcaraan linear adalah 'unbounded' jika kekangan

tidak menutupi sepenuhnya fungsi kos di mana untuk penyelesaian

19
http://www.netmba.com/operations/lp/http://www.cs.princtton.edu/courses/archive/spring03/cs/cs226/letures/lp-up.pdfhttp://www.uta.edu/faculty/swafford/opma3308/LPchapter.pdfhttp://www.netmba.com/operations/lp/http://www.cs.princtton.edu/courses/archive/spring03/cs/cs226/letures/lp-up.pdfhttp://www.uta.edu/faculty/swafford/opma3308/LPchapter.pdf


6/17


yang diberi, penyelesaian lain boleh diperolehi yang boleh

memperbaiki fungsi kos.

3. Penyelesaian Optima.

Masalah pengaturcaraan linear yang tidak 'infeasible' dan tidak

'unbounded' akan mempunyai penyelesaian yang optima; iaitu

fungsi kos mempunyai nilai fungsi kos yang unik minimum (atau

maksimum). Namun ini tidak bermakna nilai pembolehubah yang

menjana penyelesaian optima adalah unik.

Untuk meluaskan pengetahuan tentang pengaturcaraan linear, penerokaan lanjut

tentang jenis masalah pengaturcaraan linear boleh di buat;

1) Penyelesaian yang banyak (Infinitely many solutions)

http://hotmath.com/hotmath_help/topics/solving-equations.html

2) Rantau yang mungkin (feasible regions)

http://people.hofstra.edu/Stefan_Waner/Real/World/Summary4.html

3) Rantau yang tidak terbuka (unbounded feasible regions)

http://people.richland.edu/james/lecture/m116/systems/linear.html

4) 'Degeneracy

http://www.mpri.Isu.edu/textbook/Chapter4-a.htm#deg

5) Kaedah Simpleks dalam Pengaturcaraan Linear

http://www.markschulze.net/LinearProgramming.pdf

3.6 Kaedah simpleks dalam pengaturcaraan linear

20
http://hotmath.com/hotmath_help/topics/solving-equations.htmlhttp://people.hofstra.edu/Stefan_Waner/Real/World/Summary4.htmlhttp://people.richland.edu/james/lecture/m116/systems/linear.htmlhttp://www.mpri.isu.edu/textbook/Chapter4-a.htm#eghttp://www.markschulze.net/LinearProgramming.pdfhttp://hotmath.com/hotmath_help/topics/solving-equations.htmlhttp://people.hofstra.edu/Stefan_Waner/Real/World/Summary4.htmlhttp://people.richland.edu/james/lecture/m116/systems/linear.htmlhttp://www.mpri.isu.edu/textbook/Chapter4-a.htm#eghttp://www.markschulze.net/LinearProgramming.pdf


7/17


Dalam kaedah graf, nilai optimum biasanya terletak di atas sisi/sempadan

dan kadang-kadang pada bucu kawasan rantau. Mencari nilai maksimum

dan nilai minimum dalam satu masalah pengaturcaraan linear dapat

diperolehi dengan menggunakan kaedah graf apabila ia terdiri daripada

dua pemboleh ubah.Namun agak sukar mencari nilai maksimum dan nilai

minimum apabila masalah pengaturcaraan linear melibatkan lebih tiga

atau lebih pembolehubah. Oleh itu satu kaedah diperolehi untuk

menyelesaikan masalah ini yang dinamakan Kaedah Simpleks.

Kaedah Simpleks : Algoritma pengaturcaraan linear yang dapat

menyelesaikan masalah lebih daripada dua pembolehubah.Kaedah simpleks bermula daripada titik penjuru kawasan tersaur dan

bergerak secara sistematik dari satu titik penjuru ke satu titik penjuru

sehingga nilai optima diperolehi.

Kita akan mempertimbangkan hanya masalah yang melibatkan kekangan

jenis bagi mencari nilai optimum.

Titik asas dipanggil initial basic feasible solution.

Dalam kaedah simpleks pembolehubah slack diperkenalkan yangmerupakan pembolehubah asas.

Pembolehubah Slack

Slack : apabila nilai optima pemboleh ubah akhir diganti ke dalam

kekangan yang kurang atau sama, didapati nilainya kurang daripada nilai

di sebelah kanan.

Slack akan menunjukkan perbezaan nilai di sebelah kiri ketaksamaan dan

di sebelah kanan ketaksamaan.

Contoh :-

21


8/17


x1 + 2x 2 < 32(i)

3x 1 + 4x 2 < 84(ii)

Katakan diperolehi nilai akhir x 1 = 20 dan x 2 = 5

Apabila diganti dalam ketaksamaan (i) didapati nilai di sebelah kiri adalah 30 iaitu

kurang daripada nilai di sebelah kanan.

Perbezaan antara nilai kiri dan kanan adalah sebanyak 2. Nilai ini dipanggil slack

Langkah-langkah dalam Kaedah Simpleks

Tambah pembolehubah slack pada pengaturcaraan linear.

Letakkan pemalar untuk setiap persamaan dalam jadual.

Pilih lajur untuk menentukan lajur pemimpin/pangsi atau pivot column.

Pilih baris untuk menentukan baris pemimpin/pangsi atau pivot row.

Tentukan elemen pemimpin/pangsi atau pivot element

Jalankan operasi baris untuk menukar kemasukan (entry) ke

pemimpin/pangsi (pivot).

Contoh:-

Maksimumkan P = x + 0.8 y

Sabjek kepada

x + y 1000

2 x + y 1500

3 x + 2y 2 400

x, y > 0

Penyelesaian:

1. Tambah pembolehubah slak kepada persamaan Pengaturcaraan Linear

Pembolehubah slack adalah s 1, s 2 dan s 3

22


9/17


Maksimumkan : P - x - 0.8 y = 0

Sabjek kepada

x + y + s 1 = 1000

2 x + y + s 2 = 1500

3 x + 2y + s 3 = 2 400

Menentukan PIVOT PERTAMA

2. Letakkan pemalar persamaan dalam jadual seperti di bawah.

P x y s 1 s 2 s 3 RHS

1 -1 -0.8 0 0 0 0 Baris objektif

0 1 1 1 0 0 10000 2 1 0 1 0 1500

0 3 2 0 0 1 2400

3. Memilih lajur pivot

Lihat kepada baris objektif yang mempunyai kemasukan (entry)negatif.

Jika ada lebih dari satu nombor negatif, pilih kemasukan nombor

negatif paling besar.

Lajur pivot yang dipilih ialah x ( -1) lebih besar daripada y (-0.8)

4. Memilih baris pivot

Baris yang dipilih mesti mempunyai nisbah minimum pada lajur

sebelah kanan. Jika dua baris mempunyai nilai minimum nisbah yang sama, lajur

sebelah kanan akan mempunyai nilai sifar selepas proses

pivoting. Situasai ini dipanggil degenerasi.

Untuk mencari nisbah minimum dikalangan kekangan

23


10/17


x + y + s 1 = 1000 ( kekangan 1)

x + y + s 1 = 1000 x = 1000

2 x + y + s 2 = 1500 ( kekangan 2)

2 x + y + s 2 = 1500 x = 750 3 x + 2y + s 3 = 2 400 ( kekangan 3)

3 x + 2y + s 3 = 2 400 x = 800

Pilih kekangan kedua sebagai baris pivot kerana in mempunyai

nisbah pemalar RHS pada kekangan dibahagi dengan pemalar

pada lajur pivot pertama adalah paling minimum.

5. Menentukan elemen pivot

- persilangan antara baris pivot dan lajur pivot.


1 -1 -0.8 0 0 0 0

0 1 1 1 0 0 1000

0 2 1 0 1 0 1500

0 3 2 0 0 1 2400

24

lajur pivot

baris pivot

elemen pivot


11/17


6. Jalankan operasi baris untuk menukar kemasukan (entry) ke pemimpin

(pivot).

Bahagikan baris pivot dengan elemen pivot untuk mendapat hasil seperti di

bawah.


1 -1 -0.8 0 0 0 0 baris objektif

0 1 1 1 0 0 1000

0 1 0.5 0 0.5 0 750 baris pivot

0 3 2 0 0 1 2400

Tambahkan baris pivot dengan baris objektif untuk membentuk elemen 0 pada

lajur pivot untuk mendapat baris objektif seperti di bawah..

P x y s 1 s 2 s 3RHS

Bo 1 0 -0.3 0 0.5 0 750

B1 0 1 1 1 0 0 1000

B2 0 1 0.5 0 0.5 0 750

B3 0 3 2 0 0 1 2400

Kekangan 1 (baris 1) tolak baris pivot (B2) bagi membentuk elemen 0 pada lajur

pivot untuk mendapat baris 1 seperti di bawah.


1 0 -0.3 0 0.5 0 750

0 0 0.5 1 0.5 0 250

0 1 0.5 0 0.5 0 750

0 3 2 0 0 1 2400

25


12/17


Baris ke 3 tolak tiga kali baris pivot bagi membentuk elemen 0 pada lajur pivot.


Bo 1 0 -0.3 0 0.5 0 750

B1 0 0 0.5 1 0.5 0 250

B2 0 1 0.5 0 0.5 0 750

B3 0 0 0.5 0 -1.5 1 150

Fungsi objektif (P) adalah RM750

Nilai ini sepadan kepada (750, 0) dalam penyelesaian graf.

Bagaimanapun nilai ini bukan penyelesaian maksimum sebab baris

objektif masih bernilai negatif.

Penyelesaian maksimum akan meningkat untuk proses pivoting

seterusnya.

7. Teruskan operasi kerana baris objektif masih mengandungi nilai negatif

(mencari elemen pivot kedua)

Lakukan proses seperti langkah 3, langkah 4 dan langkah 5 untuk mencari

baris pivot, lajur pivot dan elemen pivot..

lajur pivot


Bo 1 0 -0.3 0 0.5 0 750

B1 0 0 0.5 1 0.5 0 250

B2 0 1 0.5 0 0.5 0 750

B3 0 0 0.5 0 -1.5 1 150 baris pivotelemen pivot

26


13/17


Bahagikan baris 3 dengan 0.5 atau darab dengan 2.

lajur pivot


Bo 1 0 -0.3 0 0.5 0 750

B1 0 0 0.5 1 0.5 0 250

B2 0 1 0.5 0 0.5 0 750

B3 0 0 1 0 -3 2 300 baris pivotelemen pivot

Darab baris 3 dengan 0.3 dan kemudian tambah dengan baris objektif (B o)

lajur pivot


Bo 1 0 0 0 -0.4 0.6 840

B1 0 0 0.5 1 0.5 0 250

B2 0 1 0.5 0 0.5 0 750


Baris 1 tolak dengan (0.5 x baris 3) untuk mendapat baris 1 seperti di bawah.

lajur pivot


Bo 1 0 0 0 -0.4 0.6 840

B1 0 0 0 1 1 -1 100

B2 0 1 0.5 0 0.5 0 750


27


14/17


Baris ke 2 tolak dengan (0.5 x baris 3) untuk mendapat baris ke 2

lajur pivot


Bo 1 0 0 0 -0.4 0.6 840

B1 0 0 0 1 1 -1 100

B2 0 1 0 0 2 -1 600



Nilai ini sepadan kepada (600, 300) dalam penyelesaian graf.Bagaimanapun nilai ini bukan penyelesaian maksimum sebab baris

objektif masih bernilai negatif.

Penyelesaian maksimum akan meningkat untuk proses pivoting

seterusnya.

8. Teruskan operasi kerana baris objektif masih mengandungi nilai negatif

(mencari elemen pivot ketiga)

Lakukan proses seperti langkah 3, langkah 4 dan langkah 5 untuk mencari

baris pivot, lajur pivot dan elemen pivot..

lajur pivot

P x y s 1 s 2 s 3 RHSBo 1 0 0 0 -0.4 0.6 840

B1 0 0 0 1 1 -1 100 baris pivot

B2 0 1 0 0 2 -1 600

B3 0 0 1 0 -3 2 300elemen pivot

28


15/17


Darab baris satu dengan 0.4 dan tambah hasilnya dengan baris objektif

untuk mendapat baris objektif seperti di bawah.. lajur pivot


Bo 1 0 0 0 0 0.2 880 baris objektif

B1 0 0 0 1 1 -1 100 baris pivot

B2 0 1 0 0 2 -1 600

B3 0 0 1 0 -3 2 300elemen pivot

Baris kedua tolak dengan 2 darab baris 1 untuk mendapat baris ke 2

seperti jadual di bawah. lajur pivot


Bo 1 0 0 0 0 0.2 880

B1 0 0 0 1 1 -1 100 baris pivot

B2 0 1 0 -2 0 1 400

B3 0 0 1 0 -3 2 300elemen pivot

Baris ketiga tambah dengan 3 darab baris 1 untuk mendapat baris ke 3

seperti jadual di bawah. lajur pivot


Bo 1 0 0 0 0 0.2 880

B1 0 0 0 1 1 -1 100 baris pivot

B2 0 1 0 -2 0 1 400

B3 0 0 1 3 0 -1 600

elemen pivot


Nilai ini sepadan kepada (400, 600) dalam penyelesaian graf.

29


16/17


Nilai ini adalah penyelesaian maksimum sebab baris objektif tidak

mempunyai nilai negatif.

Latihan

1. Gunakan algoritma simpleks untuk menyelesaikan masalah pengeluaranminuman dengan menggunakan lajur y sebagai lajur pivot yang pertama.

Maksimumkan I = x + 0.8y

Subjek kepada x + y 1000

2x + y 1500

3x + 2y

24002. Gunakan kaedah simpleks untuk menyelesaikan masalah pengaturcaraan

linear berikut:-.

Maximise : z = 4x 1 + 3x 2

Subject : x 1 + x 2 40

2x 1 + x 2 50

x1 , x 2 0

3. Fortesques di London adalah Pembekal Peringkat penyelia yangmembuat dan menjual dua jenis kopi kisar iaitu campuran biasa dan

campuran khas . Setiap adunan dihasilkan dengan menggunakan tiga

jenis kacang iaitu Arabica, Blue Mountain dan Costa Rica. Campuran

biasa adalah 1 bahagian Arabica; 3 bahagian Blue Mountain dan 3

bahagian Costa Rica manakala gabungan khas 2 bahagian Arabica, 2

bahagian Blue Mountain dan 1 bahagian Costa Rica. Pengimport kopi

mampu untuk membekalkan Fortesques sehingga kepada 120kg Arabica,

180kg Blue Mountain dan 150kg Costa Rica setiap minggu. Keuntungan

yang dibuat pada campuran biasa 25sen sekilogram dan campuran khas

50sen sekilogram. Campuran Fortesques mempunyai kepercayaan yang

tinggi kedai itu boleh menjual semua kopi yang dihasilkan.

(i) Bentukkan masalah pengaturcaraan linear dari mana keuntungan

30


17/17


mingguan maksimum boleh dikira.

(ii) Selesaikan masalah pengaturcaraan linear anda dari (i) menggunakan

kaedah simpleks. Tafsirkan penyelesaian yang anda perolehi.

Layari Internet

1. http : //math.uww.edu/~mcfarlat/s-prob.htm

31

Tajuk 3 Pengaturcaraan Linear

Documents

Transcript of Tajuk 3 Pengaturcaraan Linear