universiti putra malaysia satu pendekatan geometri bagi masalah

25
UNIVERSITI PUTRA MALAYSIA SATU PENDEKATAN GEOMETRI BAGI MASALAH PENGATURCARAAN LINEAR AZMI BIN JAAFAR FSAS 1997 7

Upload: votuong

Post on 31-Jan-2017

233 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: universiti putra malaysia satu pendekatan geometri bagi masalah

 

UNIVERSITI PUTRA MALAYSIA

SATU PENDEKATAN GEOMETRI BAGI MASALAH PENGATURCARAAN LINEAR

AZMI BIN JAAFAR

FSAS 1997 7

Page 2: universiti putra malaysia satu pendekatan geometri bagi masalah

SATU PENDEKATAN GEOMETRI BAGI

MASALAH PENGATURCARAAN LINEAR

Oieh

AZMI BIN JAAFAR

Dissertasi Yang Dik emukakan Sebagai Memenuhi Syarat Untu k Men dapatkan Ijazah Dok tol' Falsafah

di Fakulti Sains dan Pengajian Alam Sek itar Universiti Putra Malaysia

Mac 1997

Page 3: universiti putra malaysia satu pendekatan geometri bagi masalah

BlIat payllng perrnata Hasnah dan Jaafar,

ternan set i a tersayang

Habshah

dan penyeri kasih kebahagiaan

Nul' Liyana Ahmad Azfar

Nul' Izzati Ahmad Syahrni

dan Nul' Sab r i n a

Page 4: universiti putra malaysia satu pendekatan geometri bagi masalah

PENGHARGAAN

Dengan nama A l lah yang Maha Pemurah dan Maha Pengasih . Segal a pujian

bagi Allah, Tuhan semesta alam dan sel awat d an sal am ke atas j unjungan

besa\' N abi Muhammmad s.a. w . , keluarganya d an para sahabatnya.

Pertama sekali jutaan terima kas ib d i ucapkan kepada P engerusi

lawatankuasa Penyeli aan Professor Madya Dr Hj I smai l b in Mohd atas

segala bimbingan da n bantuan yang tidak ternil a i .

J utaan tel'ima k asih juga d isampaikan kepada ah li-ah l i yang terdiri

dari P I'ofessor Madya Dr Jlj Harun b i n Buclin. Dr Leow Soo Kar and D r

Mansor b i n Monsi kerana clorongan clan mot ivasi yang d iber ikan.

Penghormatan yang seirama jUg8 clitujukan kepacla Skim Latihan

Akademik Bumiputra (SLAB), J abatan Perkhidmatan Awam , Malaysia and

Uni versit i Putra Mal aysia yang mas ing-masing telah rnenyedi ak an

peruntukan kewangan dan cuti be l ajar seh ingga sempurnanya penyeliclikan

ini .

Seterusnya segal a ucapan d an penghormatan d iu njurkan kepada isteri

tersayang dan anak-anak tercinta yang telah mencurahkan sepenuh

pengol'banan, sokongan, kesabaran, dan gal akan. Sekalong a l -Fat i hah

untuk Tell (1909-24/10/1994) dan Bak (1927-30/1111995). Tidak l u p a

sejambak lllawar merah buat Mak Su , Mek clan Ayah sef'ta adi k-beradi k dan

seluruh saudara mar a sebagai hacliah kasih clan keberkatan doa mer'eka.

iii

Page 5: universiti putra malaysia satu pendekatan geometri bagi masalah

KANDUNGAN

PENGHARGAAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

SENARAI JADUAL . . . . . . . .. . . . . . ... . . . . . . . . . . . . . . . . . . . . . . .

SENARAI R AJAH . . . ... . . . . . . . . . . . . . .. . . . . . . . . . . . .. . . . ... .

SENARAI SIMBOL DAN SINGKATAN . . . . . . . . . . . . . . . . . . . . . . . . . .

ABSTR AK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ABSTRACT . . . . . . .. . ..... .... . . . . . . ... . .... . .... . . ...... .

BAB

I

II

PENDAHULUAN . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .

Latarbelakang Kajian . . . . . . . . . . . . . . . . . . . . . . . .

Beberapa Kelemahan Kaedah Simpl eks . . . . . . . . . .

Perkembangan Penyel id ikan . . . . . . . . . . . . . . . . . . .

Kaedah A lternatif . . . . . . . . . . . . . . . . . . . . . . . . . . .

Objektif K ajian . " . . . . . . . . . . . . . . . . . . . . . . . . . .

Penyusunan D i ssertas i . . . . . . . . . . . . . . . . . . . . . . .

PENGATURCARAAN LINEAR DAN KAEDAH SIMPLEKS

Bebet'apa Konsep A l jabar L i near . . . . . . . . . . . . . .

Vektor dan Matriks . . . . . . . . . . . . . . . . . . . . .

Set Cembung dan Hipersatah . . , . . . .... . . .

Masalah Pengaturcal'aan Linear . . . . . . ... . . . . . .

Pengol ahan Masa lah Pengaturcaraan Li near

Kaedah SimpJeks ............................ .

Penye lesaian Tersaur Asas Awal . . . . . .. . .

iv

Mukasurat

iii

vii

. viii

ix

x

xii

2

3

4

5

6

7

1 0

11

11

12

13

15

16

18

Page 6: universiti putra malaysia satu pendekatan geometri bagi masalah

Pelaksanaan Kaedah Simp\eks ....... .

III PENGUBAHSUAJAN PENENTUAN PENYELESAIAN TERSAUR AWAL 38

IV

Satu Contoh Berangka ........................ 39

Kod Ketaktersauran

Pelaksanaan Kaedah laafar-Mohd ............. .

Keputusan Ber angka

Perbincangan .............................. . .

KAEDAH ELlPSOID KHACHrAN .................. . .

Kaedah Elipsoid ........................... . .

Pelaksanaan Kaedah El ipsoid Kllachian

Keputusan Berangka ........................ . .

Perbincangan ............................... .

Ringkasan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

42

49

53

54

SS

62

76

79

79

V SATU VARIASI ALGORITMA KARMARKAR: ALGORITMA BARNES 80

Kaedah Barnes . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .

Penentuan Q ................................ .

Pelaksanaan Kaedah Bames .................. .

Keputusan Berangka ......................... .

Perbincangan ............................... .

VI SUSUR DAN LANTUN .......................... . .

Garis, Satah dan Hiper-satah ................ .

SUSUl' dan Lantun ........................... .

Penentuan Arah Pergerakan .................. .

Gerakan Lantun ........................ .

Gerakan Susur' ......................... .

Kaedah Susur dan Lantun ................... . .

Gerakan Lantul1

v

81

92

93

101

103

lOS

105

106

108

108

109

114

114

Page 7: universiti putra malaysia satu pendekatan geometri bagi masalah

Gerakan Susur ......................... .

Suatu Contoh Ber'angka ...................... .

Penentuan Penyelesaian Tersallr Awal ....... . .

Beberapa Tahif ...................... . .

Penentuan Penyelesaian Ter'saur Awal

Pelaksanaan Kaedah Susur dan Lantlln ........ .

Algoritma Kaedah Susur-Lantun ......... .

Prosedur Kaedah Suslll'-Lantun .......... .

Keputusan Berangka . . . . . . . . . . .. . . . . . . . . . . . . . .

Perbincangan .............................. . .

Ringkasan .................................. .

VII KEPUTUSAN BERANGKA DAN KESIMPULAN

Keputusan Ujian Berangka ................... .

Perbincangan .............................. ..

Kesimpulan ................................. .

Cadangan bagi Penyelidikan Seterusnya

RUJUKAN .............................................. .

LAMPIRAN ............................................. .

A Set Ujian Masalah Pengaturcar'aan Linear ........... .

B Pseudokod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

C Senarai Aturcara Susur Lantun .................... ..

VITA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

114

115

117

1 17

118

129

129

130

1 49

154

154

ISS

155

158

158

159

161

169

170

17S

186

299

Page 8: universiti putra malaysia satu pendekatan geometri bagi masalah

SENARAI JADUAL

Jadual Mukasurat

Kod Ketaktersaur'an . . . . . . . . . . . . . . . . . . . . . . . . . 41

2 Keputusan bagi Kaedah Simpleks M � . . . . .. . . . . . 51

3 Keputusan bagi Kaedah Simp\eks 3M . . . . . . . .. . .. 52

4 Keputusan bagi Kaedah Elipsoid . . . . . . . . . . . . . 77

5 Keputusan bagi Kaedah Bal'nes . . . . . . . . . . . . . . . 102

6 Keputusan bagi Kaedah PT-SL . . . . . .. . . . . . . . . . . 151

7 Keputusan bagi Kaedah SL . . . . . . . . . . . . . . . . . . . 153

8 Keputusan bagi Keempat-empat Kaedah . . . . . . . . 157

vii

Page 9: universiti putra malaysia satu pendekatan geometri bagi masalah

SENARAI RAJAH

Rajah Mukasurat

Set Cembung dan Tak Cembung ............... . 12

2 Susur dalam Ruang Dimensi Dua ............. . 106

3 Lantun dalam Ruang Dimensi Dua ........... . . 107

4 Rantau Tersaur OAUVRBSM .................. . . 109

5 Arah eN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 J 6 Rantau Tersaur' : Garis PO ................ . . 116

viii

Page 10: universiti putra malaysia satu pendekatan geometri bagi masalah

SENARAI SIMBOL DAN SlNGKATAN

SL

PL

PTA

PT

it

tt

A

x, c

b

x

f

f

Susur- Dan Lantun

Pengaturcaraan Linear

Penyelesaian Tersaur Asas

Penyelesaian Tersaur

bilangan lelaran

masa yang diambil

Ruang Euklid dirnensi-n

Transposisi

matr iks m x n

vektor dirnensi-n

vektor dirnensi-rn

vektOl' penyelesaian optimum

fungsi matlamat

nilai optimum fungsi matlamat

ix

Page 11: universiti putra malaysia satu pendekatan geometri bagi masalah

Abstrak dissertasi yang dikemukakan kepada Senat Universiti Putra Malaysia bagi memenuhi syarat untuk ijazah Doktor Falsafah.

SATU PENDEKATAN GEOMETRI BAG I

MASALAH PENGATURCARAAN LINEAR

o leh

AZMl BIN JAAFAR

Mac 1997

Pengerusi Prof. Madya Dr Hj Ismail Bin Mohd

Fakulti Sains dan Pengajian Alam Sekitar

Kaedah simpleks adalah kaedah yang paling termasyhur bagi

menyelesaikan masalah pengaturcaraan l i near. Kaedah ini menjelmakan

masalah asal pengaturcaraan linear kepada bentuk kanonikal dengan

bantllan pembolchubah tam bahan, sarna ada pembolehubah lalai, lebihan

atall pembolehubah buatan.

Dengan demikian, timbu l satu pertanyaan. Mengapa tidak

diselesaikan masalah pengaturcaraan linear dalam bentuk asal nya, yakn i

tanpa pembolehu bah tambahan? Pertanyaan iniJah yang memotivasikan

kajian penyelidikan yang dibentangkan dalam dissertasi ini. Pada

mu lanya pengubahsuaian dibuat terhadap pencarian penyeJesaian tersaur

asas awal bagi kaedah sirnpleks tanpa penggunaan pembolehubah buatan

tetapi masih mengekalkan penggunaan pemboJehubah JaJai/lebihan.

Setelah diperoleh penyelesaian tersaur awal tersebut, peng it'aan

diteruskan dengan kaedah simpleks.

Kemudiannya diteruskan dengan ide Sllsur dan lantun dan seterusnya

dikemukakan kaedah susur dan lantun yang meny elesaikan masalah

x

Page 12: universiti putra malaysia satu pendekatan geometri bagi masalah

pengaturcaraan linear seperti sedia tanpa penambc..han sebarang

pembolehubah, sarna ada pcmbolehubah lalaillebihan at au pembolehubah

buatan.

Kaedah Susur clan Lantun pada asasnya terhasil dari ide susur dan

lantun dalarn geometri I'uang c1imensi dua dan tiga. Narnun begitu ianya

dikembangkan untuk kesernua ruang dimensi . Kaedah ini menyusur sisi

rantau tersaur dan melantun menerusi normal kepada fungsi matlamat

untuk mencapai titik optimum. Proses pergerakan susur dan lantun,

sililt berganti, mengikut keadaan tel'tentu akhirnya akan menemui titik

yang optimum yakni penyelesaian optimum bagi masalah pengaturcaraan

linear .

Seperti kaedah pengaturcal'aan I inear yang lain, kaedah ini juga

memet'lukan penyeJesaian tersatlT' awal untuk memulakan pengiraan ke arah

penyelesaian optimum. Penentuan penye lesaian tersaur awal adalah

dengan rnembahagikan salah satu facet rantau tersaur kepada beberapa

grid dengan saiz dan bilangan grid ter'tentu.

Disamping itu. kaedah elipsoicl dan suatu variasi kaedah Karmarkar

juga dilaksanakan bagi rnernbuat perbandingan kaedah yang terbina ini dan

kaedah simpJeks ,

xi

Page 13: universiti putra malaysia satu pendekatan geometri bagi masalah

Abstract of the dissertation submitted to the Senate of Universitl Putra Malaysia i n fulfi l ment of the requi rements for the degree of Doctor of Philosophy.

A GEOMETRICAL APPROACH TO LINEAR PROGRAMMING P ROBLEM

by

AZMI BIN JAAFAR

Mal'ch 1997

Chai rman : Assoc. Prof. Dr Hj Ismai l Bin Mohd

Faculty : Science and Envirornental Studies

Simplex method is the well known method for solving linear

programming pl'oblems. This. method transforms the original linear

programming problems to a parti cu lar canoni cal form with the aids of

additional var iables, either s lacks , sur'plus or al,tificial var i ab les .

A questi on then ar i ses. Why not solve a li near programming

prob lem in its original form? This question gives the motivation to

the research study which is presented in this dissertation . First of

al l , a modification is done in determi ning the in itial feasible

solution for simplex method, wit hout the use of arti ficial variables

but sti l l make fu l l use of the s lacks and su rplus variab les. After the

in it ial feasible solution is obtained, the computation continues with

the usuaJ simpJex method.

The study conti nues with the idea of bounce and explore, and the

method called bounce and expl ore meth od for solving the linear

xi i

Page 14: universiti putra malaysia satu pendekatan geometri bagi masalah

programming problems in its original form without the aids of any

additional variables (slacks, surplus or artificial varibales).

Bounce and Explore method comes with the detel'mination of an

initial feasible solution for starting the computation to the optimum

solution. This is done by dividing one of the facets of the feasible

region into several number of grids with suitable size.

Ellipsoid Method and a variant of Karmarkar's Algorithm are also

implemented for comparisons wi th the proposed method here and the

simplex method.

xiii

Page 15: universiti putra malaysia satu pendekatan geometri bagi masalah

BAB I

PENDAHULUAN

Pengaturcaraan bermatematik adalah aspek yang paling berkembang

dalam penyelidikan operasi. Perkembangan komputer digital juga

menyumbang kepada bertambahnya minat kepada pengaturcaraan

bermatematik. Istilah pengaturcaraan bel'matematik meliputi pelbagai

bidang seperti pengaturcaraan linear, pengaturcaraan taklinear,

pengatul'caraan integer dan lain-lain jenis masalah pengaturcaraan.

Pengaturcal'aan bermatematik adalah mengenai masalah mengoptimumkan

fungsi matlamat dengan batasan atau kekangan tertentu dalam bentuk

kesamaan dan ketaksamaan. Bahagian yang memenuhi semua kekangan

membentuk rantau tersaur. Jika fungsi matlamat dan sernua kekangan

adalah linear, maka masalah itu dikenali sebagai pengaturcaraan linear

(selepas ini akan dirujuk sebagai pL). Jika fungsi matlamat atau salah

satu kekangan adalah tak linear, ianya dikenali sebagai pengaturcaraan

tak linear. Rantau tersaur PL yang terbentuk ialah satu politop

cernbung dan penyelesaiannya adalah pada titik bucu politop tersebut.

Dalam dissertasi ini, hanya dipel'katakan ten tang rant au tersaur dalam

bentuk politop cembung sahaja. Dengan lain perkataan, perbincangan

tertumpu kepada masalah pengoptimurnan pada politop cembung sahaja.

Penekanan khusus dissertasi ini adalah kaedah penyelesaian masalah

pengaturcaraan linea!'. Dalam bahagian lain dalam bab ini,

diperkenalkan latarbelakang 'nasalah yang bel�kaitan dengan rnasalah PL.

Page 16: universiti putra malaysia satu pendekatan geometri bagi masalah

2

Disamping itu dipersembahkan juga objektif dan matlamat kajian ini yang

meliputi penilaian dan pencapaian kaedah tersedia pilihan dan kaedah

yang ingin diu tarakan.

inL

Akhir seka l i di hidangkan penyusunan dissertasi

Latarbelakang Kajian

Istilah "pengaturcaraan" dalam PL ber'maksud perancangan dan ianya

tidak berkaitan langsu ng dengan istilah "pengaturcaraan komputer"

sebagaimana ianya lebih popular' sekarang. Perkataan aturcara atau

program adalah kef'ana G. B. Dantzig, pengasas PL, pad a masa itu sedang

berkhidmat dalam Pel'ang Dunia ke-I1 dan sedang menyediakan perancangan

untuk program lat ihan , penempatan dan penyediaan Iogistik bagi tentera.

Istilah pengaturcal'aan linear telah diilhamkan oleh pakar ekonomi dan

matematikawan T.C. Koopmans pada tahun 1948 pada masa be l iau dan

Dantzig bel'siar-siar di tepi panteJi Santa Monica, Californ i a (Bazaraa,

et a!. 1990). Pada masa itu, pengatul'car'aan komputer tidak begitu

meluas lagi seperti had ini.

Dan tzig memb ina kaedah si rnpleks pada tahun 1947 (Dantzig, 1963).

Tetapi penu lisan pertamanya diterbitkan pada tahun 1949. Semenjak itu

pengaturcaraan linear terus menjadi perhatian ramai penyelidik yang

bukan sahaja menyumbang kaedah baru tetapi juga pembaik an kcpada

kaedah tersedia termasuklah pengembangan dari segi teorinya. Terdapat

banyak penyelidikan telah dibuat untuk memperbaiki kaedah simpleks dad

segi keefisiensian pengir'aan nya (Solow, 1984 ). Terdapat juga banyak

percubaan untuk merekabentuk kaedah a ltematif (Osborne , 1990;

Z i -Luan , 1987; Khachian, 1979; Karrnal'kar, 1984). Kriteria yang umurn

bagi semua kaedah ter'sebut adalah rnasalah PL diubah bentuk kepada

Page 17: universiti putra malaysia satu pendekatan geometri bagi masalah

3

bent uk kanonikal tertentu sebelurn diselesaikan dengan penambahan

pembolehubah lalai, lebihan dan buatan. Ini memotivasikan untuk

mencari kaedah alternatif yang rnenyelesaikan masalah PL dalam bentuk

yang asal yakni dengan pembolehubah yang asal tanpa pembolehubah

tam bah an sepel"ti yang tel'sebut di atas.

PL digunakan dengan meiuas sebagai alat yang efektif untuk

menyelesaikan masalah dunia nyata dan dianggarkan jutaan dolal' Amedka

dalam kos masa komputel' di Amel'ika Syal'ikat sahaja digunakan untuk

menyelesaikan masalah PL (Wu, 1981). Sebagaimana yang dinyatakan di

awal bab ini l agi , kegunaan asal PL adalah o)eh pasukan tentera.

Setelah itu. PL telah dikembangkan kegunaannya dalam perindustrian dan

perdagangan. sepel'ti dalam pelbagai fasa industri petroleum

(penerokaan, pengeluaran , penapisan , pengedaran dan pengawalan

pencemaran), industri pemproses makanan, kewangan, perakaunan,

pentadbiran (seperti pentadbiran bandaraya) , pendidikan ( seperti

pengagihan mudd ke sekolah-sekolah), politik (perancangan dan

pengagihan sumber kewangan dan sumber manusia dalam kempen politik)

(Wu, 1981). Sernua yang dinyatakan di atas adalah sebahagian dad

senarai lengkap penggunaan PL. Untuk senarai yang lebih terperinci dan

komprehensif sila rujuk Gass (1977).

Beberapa Kelemahan Kaedah Simpleks

Tidak dinafikan kaedah sirnpleks merupakan kaedah yang baik untuk

menyelesaikan masa)ah pengaturcaraan linear. Namun begitu, terdapat

beberapa kelemahan yang masih boleh diperbaiki. Umpamanya ialah

kemungkinan berlakunya masalah kemerosotan(degenaracy) iaitu salah satu

pembolehubah asas adalah sifar. Kemerosotan biasanya akan

Page 18: universiti putra malaysia satu pendekatan geometri bagi masalah

4

mengakiba tkan suatu fenomena yang dinarnakan kitaran (cycLing) yakni

pengiraan akan berputar dari satu asas ke satu as as yang lain tetapi

sebenarnya ianya adalah titik yang ekstremum yang sarna. Ini

menyebabkan kaedah s impleks tidak dapat memberhentikan pengiraan dalarn

bilangan yang terhingga.

Satu lagi yang mer'upakan kelemahan juga kepada k aedah simpleks ini

ialah kel uar masuknya vektar as as di dalam tabla simpleks. Kadangkala

bedaku vektor asas yang tel ah dikel uarkan pad a lelaran sebelumnya,

dimasukkan kembali sebagai vektar asas bagi l e l aran yang ber-ikutnya.

Ini menambahkan masa dan bi langan lelaran untuk mencapai ke titik

optimum.

Pembolehubah tambahan juga, boleh lah dikatakan sebagai satu

kelemahan kaedah simpleks ini. Bi la bertarnbahnya pembolehubah maka

pengir'aan terpaksa dijalankan dalarn r'uang dimensi y ang lebih tinggi

dad r'uang dimensi asal masalah pengaturcar'aan yang berkenaan. I n i

kadangnya menyulitkan lagi masalah tersebut. Dad perkernbangan ini ,

maka dicadangkan kaedah a l tern atif yang dinamakan kaedah susur dan

l antun yang mengelak d ad pengunaan sebarang pernbolehubah tambahan sarna

ada pernbo lehubah lalai, lebihan apatah lagi pembolehubah buatan.

Sebelum dibentangkan kaeclah a l tematif ber'kenaan, dipersembahkan

dahu l u perkembangan kaeclah penyel esaian pengaturcaraan linear.

Perkernbangan Penyelidikan

Penyel idikan d a l am bidang pengaturcaraan linear ban yak tertumpu

kepada pengubahsuaian, pernbaikan dan keefisienan kaedah tersedia

Page 19: universiti putra malaysia satu pendekatan geometri bagi masalah

terutama kaedah simpleks (Klee dan Minty, 1972; Ogryczak, 1987; Shamir,

1987). Manakala kaedah e l ipsoid pula mendapat ulasan yang kurang

memberangsangkan untuk menandingi kaedah simpleks dan kaedah terbaru

ia itu a l gori tma Karmarkar's. Me Cal l menyatakan a l gor i t m a Khaehian i t u

bukanlah sautu penemuan yang dapat menandingi kaedah s impleks (Me Cal l ,

1980) malah Dantzig sendiri mernbuat pengujian dan mendapati kaedah

elipsoid memerlukan 50 juta tahun untuk menyelesaikan masa l ah yang

boleh diselesaikan o leh kaedah s i mpleks dalam j angkamasa 30 m init

( Dantzig, 1979). Rosen dan Frawl ey yang juga membuat penguj ian ke atas

k aedah e l i psoid bagi menyelesaikan slstem ketaksamaan bagi masalah

mudah juga mendapati i anya t i dak efis ien ( Rosen dan Fraw l ey, 1979 ).

A l gori tma oleh N. Karmarkar inl banyak mendapat perhat ian para

penye l id ik yang t e l ah membuat pengubahsua i an dan pembaikannya ( Tom l i n ,

1987; B l air , 1986; Gonzaga, 1991; Roos dan V i al , 1992; Y e dan Koj ima,

1987; Renegar, 1988; Gay, 1987; Goldfarb dan Xiao , 1991; Sharmo dan

Bagehi, 1990; Adler et aI., 1989). Penyel i d i kan untuk membi n a kaedah

baru t idak begitu menar i k mi nat pal'a penyel idi k . Penerbi ta n yang

mel ibatkan pembentukan kaedah baru antaranya i a l ah (Osborne, 1987,

1990) dan (Zi -Luan, 1987a, 1987b). Dengan demikian di terangkan dal a m

bahagian berikut kaedah a l ternat if yang dieadangkan dalam d issertasi

ini.

Kaedah AIternatif

Kaedah a lternat if yang di bentangkan dalam Bab VI ada l ah m erupakan

kaedah baru secara kesel uruhannya. Kaedah ini berdasarkan kepada

konsep susur dan lantu n . Susur membawa maksud menyusuri p i nggir rantau

t ersaur dari suatu t i t i k bucu ke t i t i k bueu yang lebi h balk nilai

fungsi mat l amatnya. Manakala l antun ada l ah pergerakan menerusi

Page 20: universiti putra malaysia satu pendekatan geometri bagi masalah

6

pedalarnan rantau tersaur dad satu titik ke satu titik tersaur yang

lain, Dengan gabungan kedua-dua pergerakan ini bersilih ganti mengikut

keperluan, titik optimum dapat dicari dad satu titik tersaur awal

yang diketahui . Konsep susur dan lantun juga dilaksanakan dalam

penggelintaran facet bagi menentukan titik tersaur awal bagi memulakan

kaedah yang dinamakan Kaeclah SlIsur' dan Lantlln ini. Pembentangan

mendalam dan terperinci dengan ujian pelaksanaan terdapat dalam Bab VI.

Berikutnya diberikan tujuan dan objektif kajian bagi dissertas i jni.

Objektif Kajian

Objektif utarna penyelidikan ini ialah untuk mencad kaedah

aiternatif bagi menyeiesaikan masalah PL. Penekanan khusus untuk

menyelesaikan masalah PL dalam bentuk asal, iaitu tanpa pernbolehubah

tarnbahan, sarna ada pernbolehubah ialai, lebihan ataupun pembolehubah

buatan,

Objektif penyelidikan ini adalah

i. Untuk mengimplementasikan kaedah tersedia, terutarna kaedah

termasyhur Kaedah Simpleks Dantzig, kaedah yang menimbulkan

kontl'oversi, Kaeclah Elipsoid Khachian dan algoritma Karmarkar yang

menjanjikan seribu har apan.

ii. Untuk rn e rn b i na kaedah baru bagi menyelesaikan masalah PL dalam

bentuk asal dengan pembolehubah yang asal yang dinamakan kaedah

Susur dan Lantun.

i i i . Untuk membuat slIatu perbandingan antal'a kaedah tersedia dan

Page 21: universiti putra malaysia satu pendekatan geometri bagi masalah

7

yang bal'U dibentuk dengan mengambi I masa untuk setiap kaedah mencapai

penyelesaian optimum.

Adalah diharapkan bahawa penyelidikan ini dan penemuannya berguna

bukan sahaja kepada penyeJidik daJam bidang ini tetapi juga semua

pengguna yang ingin mencari penyelesaian masalah PL dalam bidang

masing-masing seperti ekonomi, sains sosial, industri dan sebagainya.

Konsep matematik di belakang kaedah yang dikemukakan di sini

adalah mudah maka dengan itu ianya boleh dilaksanakan pad a sebarang

komputer digital.

Penyusunan Dissertasi

Dissertasi dimulakan dengan pendahuluan dalam Bab 1. la

memberikan gambaran umurn pengaturcaraan linear sebagai kes khusus

kepada istilah urnurn pengaturcal'aan matematik atau pengaturcaraan

taklinear. la juga memberikan latarbelakang dan sejarah serta

penggunaan pengaturcaraan linear dalam m asalah dunia nyata. Dalam Bab

11 suatu sorotan berkaitan masalah PL dihuraikan dan pelaksanaan kaedah

yang termasyhur Kaedah Simpleks diterangkan dengan terperinci. Ini

termasuk penjanaan penyelesaian tersaur awal iaitu Fasa I dan Kaedah

Big-M. Bab III adalah diperuntukkan untuk membentangkan idea perluasan

matriks bagi penjanaan penyelesaian tersaur as as awal, Kaedah

Jaafar-Mohd (Kaedah JM)

sirnpleks dengan Kaedah M.

dan perbandingan dengan kaedah tersedia

Bab IV rnenerangkan kaedah yang narnpaknya menimbulkan banyak

kontroversi iaitu keadah Elipsoid yang diketengahkan aleh L.G.

Page 22: universiti putra malaysia satu pendekatan geometri bagi masalah

8

Khachian , seorang matematikawan Rusia . Pengirnplirnentasian secara

praktikal dilaksanakan untuk m en injau keberkesanan kaedah dengan suatu

set uj ian masal ah PL d i Lampit-an A. Oalarn Bab V diberikan khusus untuk

kaedah yang dipercayai dapat menyaingi kaedah s imp leks iaitu Algodtma

Karmarkar. Bab ini m enerangkan pelaksanaan satu algori tma ubahsuaian

yang d igunakan pada masalah PL bentuk baku.

seperti mana Bab IV d ijalankan untuk kaedah ini.

Uj i an yang sama

Bab VI menjelaskan dengan mend a l am tentang kaedah yang baru d ib i na

yang d i kenali sebagai Kaedah Susur dan Lantun (selepas ini d ir'ujuk

sebagai Kaedah SU. Kaedah ini diasaskan kepada mencari penyelesaian

kepada masalah PL dalam keadaan sedia ada, yakni dalam bentuk asal

tanpa pembolehubah tambahan. Penentuan satu penyelesaian tersaur awal

bagi kaedah SL memulakan pengil-aan juga d iterangkan dengan terperinc i .

Semua prosedUl-, fungsi dan algoritma dalam Bab II, III, IV, V dan VI,

dibentangkan dengan rnenggunakan pseudokod seperti di Lamp iran B .

Pemahaman pernbentangan pr'oseclur-pl- oseclur aturcara dalam pelaksanaan

semua kaedah d31am dissertasi ini akan menjadi lebih mudah seandainya

Lampiran B dir'ujuk terlebih dahulu.

Suatu perband ingan semua kaedah yang telah diterangkan dalam Bab

II, IV, V dan VI dihidangkan dalam bentuk jadual dalam Bab VII. Set

ujian masalah PL di Lampiran A digunakan untuk tujuan inL Lampiran A

ter'diri dad pada 17 masalah PL yang dikernbangkan dad ruang dimensi

asal kepada masalah dalam ruang yang lebih tinggi . Masalah 1-14 adalah

asalnya masalah cialam l'uang climensi dua (20), masalah ke-15 adalah

dalam ruang dimensi tiga(30), masalah ke-1 6 daJam ruang dimensi empat

( 4 /) ) dan masalah ke-·17 adalah masalah dalam ruang dimensi lima (50).

Page 23: universiti putra malaysia satu pendekatan geometri bagi masalah

9

Bab VII juga memberikan ringkasan keseluruhan dan kesimpulan

penyel id ikan. fa juga mempersembahkan beberapa cadangan untuk

penyel id ik beri kutnya.

Semua aturcara d itu l is dengan menggllnakan bahasa pengaturcaraan

® ® Borland ' s Turbo Pascal 6 . 0 da lam komputer peribadi Hewlett Packard

Vectra 486/33VL d i Un ivers it i Pertanian Ma l aysia, 43400 UPM SERDANG,

Selangor , Malays ia . Masa yang d i ambi l adalah menggunakan prosedur

"gettime" yang memang tersed ia dalam bentllk "unit" dalam pengomp i l

Turbo Pascal 6 . 0 i nL

Page 24: universiti putra malaysia satu pendekatan geometri bagi masalah

BAB II

PENGATURCARAAN LINEAR DAN KAEOAH SIMPLEKS

Pengaturcaraan linear adalah suatu masalah yang b iasanya

diungkapkan sebagai peminimuman atau pemaksimuman suatu fungsi linear

eli at as satu set polihedral . Khusus untuk penu l i san dalam tesis i n i ,

k:1rni akan rnenurnpukan kepada rnasalah pernaksimurnan sahaja. la adalah

suatu teknik maternatik yang memilih aturcara yakni senarai t indakan

yang terbaik daripada satu set alternatif yang tersaur .

Penga tu I'caraan linear adalah aspek yang pal ing penti ng dalam

pengaturcaraan matemat ik . Salah satu sebabnya ia lah kerana ban yak

masalah dunia nyata, seperti masalah dalarn b idang perakaunan,

pentadbir'an, pendidikan, politik, pengiklanan, pemasaran, kewangan,

pengurusan, pengeluaran dan penjadualan boleh d isesuaikan dan

diselesaikan dcngan teknik pengaturcaraan linear ( Wu , 1981; Gass,

1977). Sebab yang lain adalah ker'ana PL mudah untuk d ise lesaikan jika

d ibandingkan dcngan masalah pengaturcaraan tak linear.

Oalam bab ini, kita akan l1lenerangkan matemat i k permulaan yak n i

aljabar lineal' yang dipcl'lukan untuk Jebih mudah mernahami konsep PL dan

kaedah simpleks yang digunakan untuk menye lesaikan PL tad i . Bab ini

juga mempel'sembahkan penjanaan penye l esa ian tersau r as as (PTA) awal

bagi membo l ehkan pe l aksanaan kaeclah sirnpleks. D i sampi ng penerangan

ten tang kaedah rasa clan Kaeclah M, yang biasa d igunakan da lam

penjanaan PTA awa l , kita akan mempelKcllalkan dan menel'angkan dengan

Page 25: universiti putra malaysia satu pendekatan geometri bagi masalah

11

terperinci suatu kaedah penjanaan yang menggunakan matriks kekangan

terperluas. Di akhir bab i n i , keputusan berangka akan d iberikan sebagai

perbandingan dan sebagai bukt i keberkesanan kaedah yang d icadangkan.

Sebelum i tu perlu d iJelaskan beberapa konsep a ljabar l inear untuk

memudahkan perb i ncangan da\am bahagian-bahagian ber i kutnya.

Beberapa Konsep Aljabar Linear

A l jabar l inear d igunakan untuk menerangkan konsep PL kerana i anya

memudahkan pel'bi ncangan dan pemahaman pembacaan bab i n l khususnya dan

tesis ini umumnya. A ljabar l i near adal ah juga a lat yang penting bagi

perkembangan kaedah s impleks yang termasyhur i tu . Bahagian kec i l yang

berikut dipenmtukkan bagi menjelaskan perkara tertentu dari a ljabar

l inear yang diper l ukan u ntuk pemahaman yang leb ih berkesan. Konsep

a ljabar l i near yang d ib incangkan termasuk vektor dan matr iks , set

cembung dan h ipersatah akan d i ter'angkan menerusi wadah berupa bahagian

keci l seperti ber ikllt .

Vektor dan Matr iks

T Vektor d i wak i lkan o l eh x = (x , . . . , x ) dan matriks d i wak i l kan 1 n

oleh A = (a ) IJ mxn

ditakr ifkan sebaga i

T a b = <a,b>

Has i l darab dalaman antara vektor a dan b

= a b + a b + . . . + a b 1 1 2 2 n n

n Lab .

J '" 1 J J

Perbincangan menda lam tentang perkara i n i boleh d irujuk sebarang buku

pengena\an aljabar l inear atall bab-bab permu laan buku pengenalan PL.