2Pemprograman Linear

Pengaturcaraan linear merupakan pendekatan penyelesaian maslah yang telah dibentuk untuk membantu pengurus-pengurus membuat keputusan. Disamping menerangkan definasi matematik yang normal bagi pemprograman linear, mari kita mulakan perbincangan kita dengan mempersembahkan beberapa masalah biasa di mana pemprograman linear telah digunakan:

1. Pengilang mahu membangunkan penjadualan pengeluaran dan polisi inventori yang boleh memenuhi keperluan permintaan jualan bagi tempoh masa hadapan. Secara idealnya penjadualan dan polisi tersebut membolehkan syarikat memenuhi permintaan dan dalam masa yang sama meminimumkan jumlah kos pengeluaran dan inventori.

2. Penganalisis kewangan mesti memilih portfolio pelaburan dari beberapa pilihan pelaburan stok dan bon. Penganalisis mahu membentuk portfolio yang dapat memaksimumkan pulangan ke atas pelaburan.

3. Pengurus pemasaran mahu menentukan bagaimana membahagikan peruntukan pengiklanan yang telah ditetapkan dengan baik dia antara alternatif media pengiklanan seperti radio, television, suratkhabar, dan majalah. Pengurus mahu menentukan campuran media yang memaksimumkan keberkesanan pengiklanan.

4. Syarikat yang mempunyai gudang dibeberapa lokasi disekitar Amerika Syarikat. Diberi satu set permintaan pengguna bagi keluarannya syarikat mahu menentukan gudang manakah yang sepatutnya menghantar berapa banyak keluaran kepada pelanggan yang mana supaya jumlah kos pengangkutan adalah minimum.

Walaupun begitu ini merupakan beberapa penggunaan yang mungkin di mana pemprograman linear telah digunakan dengan jayanya, contoh yang diberikan telah menunjukkan keadaan yang luas bagi jenis masalah yang boleh diselesaikan dengan menggunakan pemprograman linear. Walaupun penggunaan yang berbagai, penyiasatan yang teliti menunjukkan satu kegunaan asas di mana semua masalah ini adalah biasa. Oleh itu, bagi setiap masalah yang diberikan kita terlibat dengan memaksimumkan dan meminimumkan beberapa kuantiti. Di dalam contoh 1, kita dihendaki meminimumkan kos; di dalam contoh 2 kita dihendaki memaksimumkan pulangan ke atas pelaboran; di dalam contoh 3 kita dihendaki memaksimumkan jumlah keberkesanan pengiklanan; dan di dalam contoh 4 kita dihendaki meminimumkan jumlah kos pengangkutan. Di dalam terminologi pemprograman linear, memaksimumkan dan meminimumkan kuantiti adalah dirujukkan sebagai objektif kepada masalah. Oleh itu objektif bagi semua masalah pemprograman linear adalah memaksimumkan atau meminimumkan beberapa kuantiti.

Kegunaan biasa yang kedua kepada masalah pemprograman linear ialah terdapat batasan atau kekangan yang menghadkan darjah untuk objektif dicapai. Di dalam contoh 1, pengilang terbatas oleh kekangan keperluan permintaan keluaran untuk dipenuhi dan dengan kekangan yang menunjukkan kapasiti pengeluaran yang terhad. Masalah penganalisis portfolio kewangan pula dibataskan dengan jumlah dana pelaburan yang ada dan jumlah maksimum

BAB DUA

yang boleh dilaburkan di dalam setiap stok atau bon. Pengurus pemasaran di dalam membuat keputusan pemilihan media adalah dibataskan oleh belanjawan pengiklanan yang telah ditetapkan dan berbagai media yang tersedia. Di dalam masalah pengangkutan meminimumkan kos penjadualan penghantaran dibataskan oleh penawaran keluaran yang ada pada setiap gudang. Semua kekangan-kekangan ini adalah gambaran secara am bagi setiap masalah pemprograman linear.

2.1 Masalah Pemaksimuman yang Mudah.

Sekarang mari kita pertimbangkan masalah yang sedang dianalisis oleh pengurus Par Inc., pengilang kecil dan pembekal peralatan golf. Par telah diyakinkan oleh pengedar di mana terdapat pasaran yang sedia ada bagi kedua-dua beg golf yang berharga sederhana dan tinggi. Kenyataannya, pembekal terlalu yakin kepada pasaran sekiranya Par boleh membuat beg tersebut pada harga yang boleh bersaing, pebekal bersetuju untuk membeli semua apa yang Par boleh keluarkan dalam tempoh tiga bulan yang akan datang.

Selepas membuat penyiasatan bagi setiap langkah yang terlibat di dalam membuat bag golf, Par telah mengenalpasti setiap beg golf yang dikeluarkan adalah perlu melalui operasi berikut:

1. Memotong dan mewarna bahan mentah.2. Menjahit.3. Kemasan (seperti memasukkan pemegang payung, pengagehan kelab dan lain-lain).4. Pemereksaan dan pembungkusan.

Pengarah pengilangan telah menganalisis setiap operasi dan membuat kesimpulan di mana sekiranya syarikat mengeluarkan beg harga sederhana, model standard, setiap beg yang dikeluarkan memerlukan 7/10 jam di dalam jabatan pemotongan dan mewarna, 1/2 jam di dalam jabatan jahitan, 1 jam di dalam jabatan kemasan dan jam di dalam jabatan pemeriksaan dan pembungkusan. Model deluxe yang lebih mahal pula memerlukan 1 jam masa pemotongan dan mewarna, 5/6 jam masa jahitan, 2/3 jam masa kemasan dan 1/4 jam masa pemereksaan dan pembungkusan. Semua maklumat pengeluaran adalah diringkaskan di dalam Jadual 2.1.

JADUAL 2.1 :Operasi Pengeluaran dan Keperluan Pengeluaran Sebuah Beg

MASA PENGELUARAN (jam)Keluaran Pemotongan

dan Mewarna Menjahit Kemasan Pemerkisaan

dan Pembungkusan

Beg standard 7/10 ½ 1 1/10Beg Deluxe 1 5/6 2/3 1/4

Jabatan perakaunan telah menganalisis angka pengeluaran ini, mengenakan semua kos berubah yang sesuai, dan mendapati harga setiap beg menghasilkan sumbangan keuntungan

2

PEMPROGRAMAN LINEAR

dan overhead sebanyak $10 bagi setiap beg standard dan $9 bagi setiap bag deluxe yang dikeluarkan.

Disamping itu, selepas mengkaji unjuran beban kerja jabatan, pengarah perkilangan menganggarkan hanya 630 jam masa pemotongan dan mewarna, 600 jam masa menjahit, 708 jam masa kemasan dan 135 jam masa pemeriksaan dan pembungkusan yang ada untuk pengeluaran beg golf dalam masa tiga bulan berikutnya. Masalah Par ialah untuk menentukan berapa banyak beg standard dan berapa banyak beg deluxe yang patut dikeluarkan untuk memaksimumkan keuntungan. Sekiranya anda ditugaskan membuat penjadualan pengeluaran untuk Par Inc., apakah keputusan yang anda buat? Ia itu, berapa banyak beg standard dan berapa banyak beg deluxe yang patut anda keluarkan untuk tiga bulan akan datang? Tuliskan keputusan anda dibawah. Kemudian anda boleh semak dan lihat bagaimana baiknya yang telah anda buat.

BilanganBeg Standard

Bilangan Beg Deluxe Jumlah Keuntungan

2.2 Fungsi Objektif

Seperti yang telah ditunjukkan terdahulu, setiap masalah pemprograman linear mempunyai objektif yang khusus. Bagi masalah Par objektifnya adalah untuk memaksimumkan keuntungan. Kita boleh tuliskan objektif ini di dalam bentuk yang lebih khusus dengan pengenalan beberapa tetanda yang mudah. Biarkan

x1 = bilangan beg standard yang Par Inc., keluarkan.x2 = bilangan beg deluxe yang Par Inc., keluarkan.

Keuntungan Par datangnya dari dua sumber: (1) keuntungan yang dibuat dengan mengeluarkan x1 beg standard dan (2) keuntungan yang dibuat dengan mengeluarkan x2 beg deluxe. Olek kerana Par memperolehi $10 untuk setiap beg standard yang dikeluarkan, syarikat akan memperolehi $10x1, jika x1 beg standard dikeluarkan. Begitu juga, oleh kerana Par memperolehi $9 untuk setiap keluaran bag deluxe, syarikat akan memperolehi $9x2 jika x2 bag deluxe dikeluarkan. Menandakan jumlah keuntungan sebagai z, kita dapati

Jumlah keuntungan = Z = $10x1 + $9x2

Dari sekarang dan seterusnya kita akan mengandaikan semua keuntungan adalah diukur di dalam ringgit dan jumlah keuntungan akan ditulis tanpa tanda ringgit. Oleh itu

Jumlah keuntungan = Z = 10x1 + 9x2 (2.1)

Penyelesaian untuk masalah Par adalah keputusan yang akan memaksimumkan jumlah keuntungan. Oleh itu, Par Inc., mesti menentukan nilai-nilai bagi angkubah x1 dan x2 yang akan menghasilkan nilai z tertinggi yang mungkin. Di dalam terminologi pemprograman linear kita

3

BAB DUA

rujukkan x1 dan x2 sebagai angkubah keputusan. Oleh kerana, objektif - memaksimumkan jumlah keuntungan - adalah fungsi kepada angkubah keputusan ini, kita rujukkan kepada 10x2

+ 9x2, sebagai fungsi objektif. Oleh itu di dalam terminologi pemprograman linear kita katakan matlamat atau objektif Par adalah untuk memaksimumkan nilai fungsi objektif. Menggunakan max sebagai ringkasan untuk maksimum, objektif boleh ditulis sebagai:

max z = max 10x1 + 9x2 (2.2)

Katakan Par memutuskan untuk membuat 400 beg standard dan 200 beg deluxe. Mengikut persamaan (2.2) keuntungan yang berkaitan adalah

z = 10(400) + 9(200) = 4000 + 1800 = 5800

Apa kata kalau Par memutuskan kombinasi keluaran yang berbeza, katakan mengeluarkan 800 bag standard dan tiada beg deluxe yang dikeluarkan? Dalam kes ini keuntungan Par akan menjadi

z = 10(800) + 9(0) = 8000

Nyatalah kombinasi keluaran yang kemudian ini adalah lebih baik bagi Par, Inc. dalam hal objektif yang dinyatakan untuk memaksimumkan keuntungan. Walau bagaimana pun, adalah tidak mungkin bagi Par, Inc. untuk mengeluarkan 800 beg standard dan tiada beg deluxe. Mari kita lihat pada jumlah masa yang diperlukan untuk setiap empat operasi sekiranya kita mengambilkira kombinasi pengeluaran ini. Menggunakan data di dalam Jadual 2.1, kita dapati pengeluaran bagi 800 beg standard memerlukan 560 jam masa pemotongan dan mewarna, 400 jam masa menjahit, 800 jam masa kemasan dan 80 jam masa pemereksaan dan pebungkusan. Bolehkah Par, Inc. mengeluarkan 800 beg standard? Jawapannya tidak, oleh kerana satu jabatan - jabatan kemasan - tidak mempunyai bilangan masa yang mencukupi. Disebabkan oleh kekangan bilangan masa yang ada, Par, Inc tidak berkebolehan untuk mempertimbangkan 800 beg standard dan tiada beg deluxe sebagai alternatif pengeluaran yang boleh diterima. Kenyataannya, Par, Inc. boleh menimbangkan hanya alternatif pengeluaran yang mempunyai keperluan jumlah masa yang kurang atau sama dengan jumlah maksima jam yang ada bagi setiap empat operasi tersebut.

Di dalam masalah Par, Inc. mana-mana kombinasi tertentu pengeluaran bagi beg standard dan beg deluxe adalah dirujukkan sebagai penyelesaian kepada masalah. Walau bagaimana pun, hanya penyelesaian yang dapat memenuhi semua kekangan sahaja yang dirujukkan sebagai penyelesaian bolehlaksana. Kombinasi tertentu keluaran boleh laksana atau penyelesaian boleh laksana yang menghasilkan keuntungan yang terbesar dirujukkan sebagai kombinasi keluaran yang optimum atau sama dengan penyelesaian optimum. Pada titik ini, walau bagaimanapun, kita tidak ada idea, apakah penyelesaian optimum akan berlaku disebabkan kita tidak membentuk tatacara bagi mengenalpasti penyelesaian boleh laksana. Tatacara untuk menentukan penyelesaian boleh laksana memerlukan kita pertamanya mengenalpasti kekangan bagi masalah.

4

PEMPROGRAMAN LINEAR

2.3 Kekangan

Setiap bag standard dan deluxe yang dikeluarkan melalui empat operasi pengilangan. Oleh itu jumlah masa pengeluaran yang ada adalah terhad bagi setiap operasi, kita boleh jangkakan terdapat empat batasan atau kekangan yang menghadkan jumlah bilangan beg golf yang boleh Par keluarkan. Oleh itu, langkah berikutnya di dalam pendekatan pemprograman linear adalah menentukan dengan jelas semua kekangan yang berkaitan dengan masalah tersebut.

Daripada maklumat pengeluaran (lihat Jadual 2.1) kita tahu setiap bag standard yang Par keluarkan akan menggunakan 7/10 jam masa pemotongan dan mewarna. Oleh itu, jumlah bilangan jam masa pemotongan dan mewarna yang digunakan bagi mengeluarkan x1 bag standard adalah 7/10x1. Dengan lain perkataan, setiap beg deluxe yang dikeluarkan oleh Par menggunakan 1 jam masa pemotongan dan mewarna; oleh itu x1 beg deluxe adalah menggunakan 1x2 jam masa pemotongan dan mewarna. Jumlah masa pemotongan dan mewarna yang diperlukan unuk mengeluarkan x1 beg standard dan x2 beg deluxe diberikan sebagai

Jumlah masa pemotongan dan mewarna = 7/10x1 + 1x2

Oleh kerana pengarah pengilangan telah menyatakan Par hanya mempunyai sebanyak-banyaknya 630 jam masa pemotongan dan mewarna, ia mengikat kombinasi pengeluaran yang dipilih untuk memenuhi keperluan

7/10 x1+ 1x2 630 (2.3)

di mana simbol bermakna lebih kecil daripada atau sama dengan. Perhubungan (2.3) dirujukkan sebagai ketaksamaan dan ditandakan sebagai kenyataan jumlah masa yang digunakan untuk operasi pemotongan dan mewarna bagi mengeluarkan x1 bag standard dan x2

bag deluxe mestilah lebih kecil daripada atau sama dengan jumlah maksimum masa pemotongan dan mewarna yang ada pada Par, Inc. Ketaksamaan (2.3) kemudiannya mewakili kekangan pemotongan dan mewarna bagi Par Inc.

Dari Jadual 2.1 kita juga dapat melihat bagi setiap bag standard yang dikeluarkan memerlukan 1/2 jam masa menjahit dan setiap beg deluxe yang dikeluarkan memerlukan 5/6 jam masa menjahit. Oleh kerana terdapat 600 jam masa menjahit yang ada, berikutnya

1/2 x1 + 5/10 x2 600 (2.4)

Ketaksamaan (2.4) adalah perwakilan matametik bagi kekangan menjahit. Anda tentukan sendiri bagi kekangan kapasiti kemasan adalah

1x1 + 2/3 x2 708 (2.5)

dan kekangan untuk kapasiti pemeriksaan dan pembungkusan adalah

1/10x1 + 1/4x2 135 (2.6)

Kita sekarang telah mengenalpasti perhubungan matametik bagi kekangan-kekangan yang berkaitan dengan empat operasi pengeluaran. Adakah terdapat lain-lain kekangan yang telah kita lupakan? Bolehkah Par mengeluarkan bilangan negatif bagi bag standard dan beg

5

BAB DUA

deluxe? Nyatalah, jawapannya tidak. Oleh itu di dalam usaha untuk menghalang keputusan angkubah x1 dan x2 daripada menpunyai nilai negatif dua kekangan

x1 0 dan x2 0 (2.7)

mesti ditambah. Tanda bermakna lebih besar daripada atau sama dengan. Kekangan ini menentukan penyelesaian bagi masalah kita akan megandungi nilai bukan negatif bagi angkubah keputusan dan dirujukkan sebagai kekangan bukan negatif. Kekangan bukan negatif adalah gambaran am bagi semua masalah pemprograman linear dan akan ditulis di dalam bentuk ringkasnya seperti berikut:

x1, x2 0

2.4 Pernyataan Matematik bagi Masalah Par Inc.

Pernyataan matematik atau formulasi matametik bagi masalah Par, Inc. sekarang telah dilengkapkan. Kita telah berjaya di dalam memindahkan objektif dan kekangan bagi masalah sebenar kepada set perhubungan matematik yang dinyatakan sebagai model matematik. Model matematik yang sempurna bagi Par, Inc. adalah seperti berikut.

max 10 x1 + 9 x2

tertakluk kepada (t.k.)7/10x1 + 1 x2 630 Pemotongan dan mewarna 1/2x1 + 5/6 x2 600 Menjahit 1x1 + 2/3 x2 708 Kemasan 1/10x1 + 1/4 x2 135 Pemeriksaan dan pembungkusan

x1, x2 0

Tugas kita sekarang ialah untuk mencari campuran keluaran (iaitu, kombinasi x1 dan x2) yang dapat memenuhi semua kekangan dan, pada masa yang sama, menghasilkan nilai fungsi objektif yang lebih besar atau sana dengan nilai yang diberi melalui lain-lain penyelesaian boleh laksana. Bila ini telah dilakukan, kita telah memenuhi penyelesaian optimum kepada bagi masalah.

Model matamatik di atas bagi masalah Par, Inc. adalah pemprograman linear. Masalah tersebut mempunyai objektif dan kekangan yang telah kita nyatakan awalnya adalah bahagian yang biasa bagi semua pemprograman linear. Tetapi apakah gambaran khusus bagi model matematik tersebut yang membuatkannya sebagai pemprograman linear? Gambaran khusus yang menjadikan ia pemprograman ialah fungsi objektif dan semua fungsi kekangan (bahagian sebelah kiri bagi kekangan ketaksamaan) adalah fungsi linear angkubah keputusan.

Secara matametik, fungsi di mana setiap angkubah kelihatan di dalam bentuk yang berasingan dan kuasa satu dipanggil fungsi linear. Fungsi objektif (10x1 + 9x2) adalah linear oleh kerana setiap angkubah keputusan terjadi di dalam bentuk yang berasingan dan

mempunyai eksponen 1. Sekiranya fungsi objektif kelihatan sebagai (10x12 + x2) ia tidak lagi

dikenali fungsi linear dan kita tidak lagi mempunyai pemprograman linear. Jumlah masa pengeluaran yang diperlukan di dalam jabatan pemotongan dan mewarna ( 7/10x1 + 1x2) juga merupakan fungsi linear bagi angkubah keputusan untuk sebab yang sama. Begitu juga, fungsi

6

PEMPROGRAMAN LINEAR

bagi bahagian sebelah kiri semua ketaksamaan kekangan (fungsi kekangan) adalah fungsi linear. Oleh itu formulasi matametik bagi masalah Par adalah dirujukkan sebagai pemprograman linear.

2.5 Pendekatan Penyelesaian Secara Geraf

Cara yang mudah untuk menyelesaikan masalah pemprograman linear yang mempunyai hanya dua angkubah keputusan adalah tatacara penyelesaian secara geraf. Walaupun kaedah geraf adalah merumitkan di dalam penyelesaian masalah tiga angkubah, dan tidak boleh digunakan untuk masalah yang besar, keuntungan disebalik mempelajari cara ini amat bernilai sebagai bantuan untuk memahami beberapa konsep yang lebih tinggi yang akan dibincangkan kemudiannya di dalam buku ini. Disamping itu, kaedah geraf memberikan asas 'intuitive' untuk kaedah penyelesaian yang lebih praktikal seperti cara simplek, yang akan dibincangkan di dalam Bab 3.

Sekarang mari kita mulakan tatacara penyelesaian geraf dengan membentuk geraf yang boleh digunakan untuk menerangkan penyelesaian yang mungkin (nilai x1 dan x2) bagi masalah Par, Inc. Geraf (Rajah 2.1) mempunyai nilai x1 bagi paksi mendatar dan nilai x2 bagi paksi menegak. Mana-mana titik di atas geraf boleh dikenalpasti dengan nilai-nilai x1 dan x2, yang

menunjukkan kedudukan titik disepanjang paksi x1 dan x2. Oleh itu setiap titik (x1,x2) berpadanan dengan penyelesaian yang mungkin, setiap titik di atas geraf adalah dipanggil sebagai titik penyelesaian. Titik penyelesaian di mana x1 = 0 dan x2 = 0 dirujukkan sebagai titik origin.

Rajah 2.1Graf Titik Penyelesaian untuk Dua Pembolehubah Masalah Par, Inc.

7

BAB DUA

Langkah berikutnya, ialah untuk menunjukkan di mana kombinasi x1 dan x2 yang mungkin, iaitu, titik penyelesaian, berpadanan dengan penyelesaian boleh laksana bagi pemprograman linear. Oleh itu mana-mana x1 dan x2 mestilah bukan negatif, kita hanya mempertimbangkan titik di mana x1 0 dan x2 0. Ini ditunjukkan di dalam Rajah 2.2 melalui

anak panah yang menunjukkan arah bagi kombinasi keluaran yang akan memenuhi kekangan bukan negatif. Di dalam semua geraf akan datang kita akan andaikan perhubungan bukan negatif akan diikuti dan hanya melukis bahagian geraf yang berkaitan dengan nilai x1 dan x2

yang bukan negatif sahaja.Terdahulunya kita telah melihat ketaksamaan kekangan pemotongan dan sebagai

bentuk

7/10x1 + 1x2 630

Rajah 2.2Kekangan Bukan Negatif

Untuk menunjukkan semua titik penyelesaian yamg dapat memenuhi perhubungan ini, kita mulakan dengan melakarkan garisan yang berpadanan dengan persamaan

7/10x1 + 1x2 = 630

Geraf bagi persamaan ini ditemui dengan mengenalpasti dua titik yang terletak di atas garisan dan kemudiannya dilukiskan garisan melalui titik-titik tersebut. Dengan menetapkan x1= 0 dan selesaikan x2, kita lihat titik tersebut (x1 = 0, x2 = 630) memenuhi persamaan tersebut. Untuk mencari titik kedua yang dapat memenuhi persamaan ini, kita tetapkan x2 = 0 dan

8

PEMPROGRAMAN LINEAR

selesaikan untuk x1. Dengan melakukan sedemikian, kita dapati 7/10 x1+ 1(0) = 630 atau x1 = 900. Oleh itu, titik kedua dapat memenuhi persamaan adalah (x1 = 900, x2 = 0). Diberi dua titik

ini kita sekarang boleh melukis geraf di mana garisan mewakili persamaan

7/10x1 + 1x2 = 630

Garisan ini, di mana dipanggil garisan kekangan pemotongan dan mewarna, ia ditunjukkan di dalam Rajah 2.3. Untuk tujuan pengenalan kita tandakan garisan ini sebagai "P&W" untuk menunjukkan ia mewakili kekangan pemotongan dan mewarna.

Mengingat kembali kekangan ketaksamaan bagi pemotongan dan mewarna yang diwakili oleh

7/10x1 + 1x2 630

Bolehkan anda mengenalpasti semua titik penyelesaian yang dapat memenuhi kekangan ini? Baiklah, oleh kerana kita telah mempunyai garisan di mana 7/10x1 + 1x2 = 630, kita tahu mana-mana titik di atas garisan ini akan memenuhi kekangan ini. Tetapi manakah titik penyelesaian yang memenuhi 7/10x1 + 1x2 630? Pertimbangkan dua titik penyelesaian (x1 = 200, x2 = 200) dan (x1 = 600, x2 = 500). Anda boleh lihat daripada Rajah 2.3 di mana titik penyelesaian yang pertama adalah dibawah garisan kekangan dan titik yang kedua diatas garisan kekangan. Manakah diantara penyelesaian ini memenuhi kekangan pemotongan dan mewarna? Untuk titik (x1 = 200, x2 = 200) kita lihat

7/10x1 + 1x2 = 7/10 (200) + 1 (200) = 340

Oleh kerana 340 jam kurang daripada 630 jam yang ada, maka x1= 200, x2= 200 kombinasi keluaran, atau titik penyelesaian, yang memenuhi kekangan. Bagi x1= 600, x2 = 500 kita dapati

7/10x1 + 1x2 = 7/10 (600) + 1 (500) = 920

Oleh kerana 920 jam adalah lebih besar daripada 630 jam yang ada, titik penyelesaian x1 = 600, x2 = 500 tidak memenuhi keperluan kekangan dan ia tidak boleh diterima sebagai alternatif pengeluaran.

9

BAB DUA

Rajah 2.3Garisan Kekangan Pemotongan dan Mewarna

Adakah anda telah bersedia untuk menentukan titik penyelesaian yang memenuhi kekangan pemotongan dan mewarna? Anda sepatutnya memenuhi di mana-mana titik dibawah garisan kekangan pemotongan dan mewarna akan memenuhi kekangan. Anda mungkin mahu membuktikan untuk anda sendiri dengan memilih titik penyelesaian tambahan di atas atau dibawah garisan kekangan dan semak untuk melihat sekiranya penyelesaian dapat memenuhi kekangan. Anda akan melihat untuk kekangan hanya titik penyelesaian di atas atau dibawah garisan sahaja yang memenuhi kekangan. Didalam Rajah 2.4 kita tunjukkan semua titik dengan melorekkan kawasan geraf berkaitan kepada titik penyelesaian yang memenuhi kekangan pemotongan dan mewarna.

Kemudian mari kita mengenalpasti titik penyelesaian yang dapat memenuhi kekangan menjahit

1/2x1 + 5/6x2 600

Kita mulakan dengan melukis garisan kekangan yang diwakili oleh persamaan

1/2x1 + 5/6x2 600

10

PEMPROGRAMAN LINEAR

Rajah 2.4Kawasan Bolehlaksana Kekangan Pemotongan dan Mewarna

Seperti sebelumnya, membuat garisan pada geraf adalah mudah dengan mencari dua titik di atas garisan dan kemudian menghubungkannya. Oleh itu, pertamanya kita tetapkan x1

sama dengan sifar dan selesaikan untuk mendapatkan x2, yang menghasilkan titik (x1 = 0, x2 =

720). Kemudian kita tetapkan x2 sama dengan sifar dan selesaikan untuk x1, yang memberikan titik kedua (x1 = 1200, x2 = 0). Di dalam Rajah 2.5, kita telah melukis garisan yang telah mewakili kekangan menjahit. Untuk tujuan pengenalan kita tandakan garisan ini sebagai M. Menggunakan pendekatan yang sama dengan kekangan pemotongan dan mewarna, kita sedar hanya titik di atas atau dibawah garisan asalnya yang memenuhi kekangan masa menjahit. Di dalam Rajah 2.5 kawasan yang berlorek mewakili semua kemungkinan kombinasi pengeluaran atau titik penyelesaian boleh laksana bagi operasi menjahit

Dengan cara yang sama, kita boleh menentukan semua kombinasi pengeluaran boleh laksana bagi setiap kekangan yang tinggal. Hasilnya ditunjukkan di dalam Rajah 2.6 dan 2.7. Untuk latihan, cuba lakarkan kawasan penyelesaian boleh laksana untuk kekangan penyudah (P) dan kekangan pemeriksaan dan bungkusan (P&B) dan lihat jika keputusan anda sama dengan yang ditunjukkan di dalam Rajah 2.6 dan 2.7.

Kita sekarang telah mempunyai empat geraf yang berasingan yang menunjukkan titik penyelesaian boleh laksana bagi setiap empat kekangan. Di dalam masalah pemprograman linear, kita perlu untuk mengenalpasti titik penyelesaian yang dapat memenuhi semua kekangan secara serentak. Untuk mencari titik penyelesaian ini, kita boleh melukis empat kekangan di atas satu geraf dan perhatikan kawasan yang mengandungi titik di mana dapat memenuhi semua kekangan.

11

BAB DUA

Geraf di dalam Rajah 2.4 hingga 2.7 boleh digabungkan di dalam membentuk satu geraf dengan semua empat kekangan. Geraf pencantuman empat kekangan ini ditunjukkan di dalam Rajan 2.8. Kawasan yang berwarna di dalam rajah ini meliputi semua titik penyelesaian yang dapat memenuhi semua kekangan. Oleh kerana penyelesaian dapat memenuhi semua kekangan adalah dikenali sebagai penyelesaian bolehlaksana, kawasan berwarna adalah dipanggil kawasan penyelesaian bolehlaksana, atau ringkasnya kawasan bolehlaksana. Mana-mana titik di atas sempadan bagi kawasan boleh laksana atau diantara kawasan bolehlaksana adalah titik penyelesaian bolehlaksana. Anda mungkin mahu menyemak titik di luar kawasan boleh laksana untuk membuktikan kepada anda di mana titik penyelesaian melanggari satu atau lebih kekangan dan tidak boleh-laksana atau tidak boleh terima.

Rajah 2.5Kawasan Bolehlaksana Kekangan Menjahit

Sekarang kita telah mengenalpasti kawasan boleh laksana, kita bersedia untuk menerima penyelesaian secara geraf dan mencari penyelesaian optima untuk masalah Par, Inc. Ingat semula pengeluaran optima bagi masalah pemprograman linear adalah penyelesaian boleh laksana yang memberikan nilai yang paling berkemungkinan bagi fungsi objektif. Kita pilih secara arbitiari titik penyelesaian boleh laksana (x1,x2) dan kirakan keuntungan berkaitan 10x1+ 9x2. Walau bagaimanapun, kesulitan pendekatan ini adalah terlalu banyak penyelesaian boleh laksana (sebenarnya bilangan tak terhingga), dan ia adalah tidak mungkin untuk menilaikan semua penyelesaian boleh laksana. Oleh itu, tatacara 'trail and error' tidak menjamin penyelesaian optima boleh diperolehi. Apa yang kita lakukan adalah cara yang paling baik untuk menentukan penyelesaian boleh laksana yang mana tujuannya memaksimumkan keuntungan Par, Inc.

12

PEMPROGRAMAN LINEAR

Rajah 2.6Kawasan Bolehlaksana Kekangan Kemasan

Rajah 2.7Kawasan Bolehlaksana Kekangan Pemeriksaan dan Pembungkusan

13

BAB DUA

Rajah 2.8Graf Gabungan Kekangan Menunjukkan Kawasan

Penyelesaian Bolehlaksana Masalah Par, Inc.

Mari kita mulakan langkah pengoptimuman tatacara penyelesaian secara geraf dengan melukiskan kawasan penyelesaian boleh laksana pada geraf yang berasingan. Ini ditunjukkan di dalam Rajah 2.9.

14

PEMPROGRAMAN LINEAR

Rajah 2.9Kawasan Bolehlaksana bagi Masalah Par, Inc.

Daripada memilih penyelesaian bolehlaksana secara abritrari dan mengira keuntungan yang berkaitan, biarkan kita memilih keuntungan secara abritrari, dan mengenalpasti semua titik penyelesaian bolehlaksana (x1,x2) yang menghasilkan keuntungan yang dipilih. Sebagai contohnya, apakah titik penyelesaian bolehlaksana yang memberikan keuntungan sebanyak $1800? Oleh itu, kita perlu mencari nilai x1 dan x2 di dalam kawasan bolehlaksana yang mempunyai fungsi objektif

10x1 + 9x2 = 1800

Pernyataan di atas hanyalah persamaan bagi garisan. Oleh itu semua titik-titik penyelesaian bolehlaksana (x1,x2) menghasilkan keuntungan $1800 mestinya di atas garisan ini. Kita telah pelajari dahulunya di dalam bahagian ini bagaimana melakarkan geraf garisan kekangan. Tatacara bagi membuat geraf bagi keuntungan atau garisan fungsi objektif adalah sama. Biarkan x1 = 0, kita lihat x2 mestilah 200; oleh itu titik penyelesaian (x1 = 0, x2 = 200) adalah di atas garisan. Begitu juga, dengan membiarkan x2 = 0, kita dapati titik penyelesaian (x1

= 180, x2 = 0) juga di atas garisan. Dengan melukis garisan melalui dua titik ini, kita dapat mengenalpasti semua penyelesaian yang mempunyai keuntungan sebanyak $1800. Geraf bagi garisan keuntungan ini ditunjukkan di dalam Rajah 2.10. Daripada geraf ini adalah boleh lihat terdapat bilangan yang tidak terhingga bagi kombinasi keluaran yang memberikan keuntungan sebanyak $1800.

15

BAB DUA

Rajah 2.10Garisan Keuntungan $1800 bagi Masalah Par, Inc.

Oleh kerana objektifnya untuk mencari satu titik penyelesaian bolehlaksana yang dapat memberikan keuntungan yang tinggi, maka kita teruskan dengan memilih nilai keuntungan yang lebih tinggi dan cari titik penyelesaian yang menghasilkan keuntungan yang dinyatakan. Sebagai contoh, apakah titik penyelesaian yang memberikan keuntungan $3600?. Apakah titik penyelesaian yang memberikan keuntungan $5400?. Untuk menjawab soalan ini kita mestilah mencari nilai x1 dan x2 yang terdapat di atas garis dan berikut:-

10x1 + 9x2 = 3600 dan

10x1 + 9x2 = 5400

Menggunakan tatacara sebagaimana sebelumnya untuk melakarkan geraf keuntungan dan garisan kekangan, kita akan lukiskan $3600 dan $5400 garisan keuntungan di atas geraf di dalam Rajah 2.11. Oleh kerana, tidak semua titik penyelesaian di atas garisan keuntungan $5400 terletak di dalam kawasan bolehlaksana, sekurang-kurangnya beberapa titik di atas garisan, dan mungkin di dalam kawasan kombinasi pengeluaran bolehlaksana memberikan keuntungan $5400.

Bolehkah kita mencari penyelesaian bolehlaksana yang menghasilkan keuntungan yang tertinggi? Lihat pada Rajah 2.11 dan lihat apakah pemerhatian am yang boleh anda buat berkenaan dengan garisan keuntungan. Anda semestinya boleh mengenalpasti peraturan berikut (1) garisan keuntungan adalah selari antara satu sama lain, dan (2) garisan keuntungan

16

PEMPROGRAMAN LINEAR

yang lebih tinggi adalah bergerak lebih jauh daripada titik origin. Ini juga boleh dilihat secara algebra. Biarkan z mewakili jumlah keuntungan. Fungsi objektif adalah

z = 10x1 + 9x2

Menyelesaikan untuk x2 di dalam bentuk x1 dan z, kita dapati

9x2 = - 10x1 + zx2 = -10/9x1 + 1/9 z (2.8)

Persamaan (2.8) adalah bentuk cerun-persilangan bagi persamaan linear x1 dan x2. Pengkali bagi x1; -10/9, adalah kecerunan bagi garisan, dan pernyataan 1/9z adalah persilangan x2 [oleh itu, nilai x2 di mana geraf bagi persamaan (2.8) bersilang pada paksi x2]. Menggantikan nilai keuntungan bagi z = 1800; z = 3600, dan z = 5400 ke dalam persamaan (2.8) menghasilkan cerun-persilangan berikut bagi garisan keuntungan yang di tunjukkan di dalam Rajah 2.11.

Rajah 2.11Garisan Keuntungan Terpilih Bagi Masalah par, Inc.

Untuk keuntungan z = 1800x2 = -10/9x1 + 200

Untuk keuntungan Z = 3600

17

BAB DUA

x2 = -10/9x1 + 400

Untuk keuntungan Z = 5400X2 = -10/9x1 + 600

Oleh kerana kecerunan ( -10/9) adalah sama bagi setiap keuntungan, garisan keuntungan adalah selari. Seterusnya, kita lihat persilangan x2 adalah meningkat dengan nilai keuntungan yang besar. Garisan keuntungan yang tertinggi ini semangkin jauh daripada origin.

Disebabkan oleh garisan keuntungan adalah selari dan garisan keuntungan yang tertinggi lebih jauh daripada origin, kita boleh mendapatkan titik penyelesaian yang menghasilkan peningkatan nilai tertinggi yang bertambah untuk fungsi objektif melalui pergerakan keuntungan berterusan jauh daripada origin secara selari dengan garisan keuntungan yang lain. Walau bagaimanapun, pada sesetengah titik kita akan temui dengan pergerakan yang lebih jauh akan meletakan garisan keuntungan di luar kawasan boleh laksana. Oleh kerana titik diluar kawasan bolehlaksana tidak diterima, titik di dalam kawasan penerimaan di mana berada di atas garisan keuntungan yang tertinggi adalah penyelesaian optimum bagi pemprogramam linear kita.

Anda sekarang sepatutnya berkebolehan untuk mengenalpasti titik penyelesaian optimum bagi masalah Par, Inc. Menggunakan pembaris atau sekeping kertas dan gerakkan garisan keuntungan sejauh mungkin yang boleh. Apakah titik terakhir di dalam kawasan boleh laksana yang boleh anda capai? Titik ini adalah titik optimum, ditunjukkan secara geraf di dalam Rajah 2.12.

Rajah 2.12Penyelesaian Optimum Bagi Masalah Par, Inc.

18

PEMPROGRAMAN LINEAR

Nilai optimum bagi angkubah keputusan adalah nilai x1 dan x2 pada penyelesaian optimum. Bergantung kepada kerumitan masalah dan ketepatan geraf, anda mungkin atau tidak mungkin dapat menentukan nilai x1 dan x2 yang tepat. Merujuk kepada geraf di dalam Rajah 2.12, kesimpulan terbaik yang boleh kita buat ialah kombinasi pengeluaran yang optimum mengandungi lebih kurang 550 beg standard (x1) dan lebih kurang 250 beg deluxe ( x2). Walau bagaimanapun, pemerhatian yang teliti daripada Rajah 2.8 dan 2.12 menunjukkan titik penyelesaian yang optimum adalah dipersilangan garisan kekangan pemotongan dan mewarna dan garisan kekangan penyudah. Oleh itu, titik persilangan yang optimum terletak di atas kedua-dua kekangan pemotongan dan mewarna.

7/10x1 + 1 x2 = 630 (2.9)

dan garisan kemasan:

1x1 + 2/3x2 = 708 (2.10)

Oleh itu nilai bagi keputusan x1 dan x2 mestilah memenuhi serentak kedua-dua persamaan (2.9) dan (2.10). Menggunakan persamaan (2.9) dan menyelesaikan untuk x1

memberikan

7/10 x1 = 630 - 1x2

atau

x1 = 900 - 7/10x2

Menggantikan pernyataan untuk x1 ke dalam persamaan (2.10) dan menyelesaikan

untuk x2 memberikan

1(900 - 7/10 x2 ) + 2/3x2 = 708 900 - 7/10 x2 + 2/3x2 = 708

900 - 30/21x2 - 14/21x2 = 708-16/21 x2 = - 192

x2 = = 252

Menggunakan x2 = 252 di dalam persamaan (2.11) dan menyelesaikan untuk x1

memberikan

x1 = 900 - 10/7 (252) = 900 - 360 = 540

Oleh itu lokasi yang tepat bagi titik penyelesaian yang optimum adalah x1 = 540 dan x2 = 252. Oleh itu kuantiti pengeluaran yang optimum bagi Par, Inc. adalah 540 buah bag standard dan 252 buah beg deluxe yang menghasilkan keuntungan 10(540) + 9(252) = $7668.

Di dalam mana-mana penyelesaian masalah pemprograman linear secara geraf bagi angkubah dua keputusan nilai yang tepat bagi angkubah keputusan pada penyelesaian optimum pertamanya boleh ditentukan melalui penggunaan tatacara geraf untuk mengenalpasti

19

BAB DUA

titik ekstrim yang optimum dan kemudiannya menyelesaikan dua persamaan serentak berkaitan dengan titik ini.

Ringkasan Tatacara Penyelesaian Secara Geraf Bagi Masalah Pemaksimuman

Seperti yang telah anda lihat, tatacara penyelesaian secara geraf merupakan satu kaedah di dalam menyelesaian masalah pemprograman linear yang mempunyai dua-angkubah sebagaimana masalah Par, Inc. Langkah-langkah bagi tatacara penyelesaian secara geraf bagi masalah pemaksimuman digariskan seperti dibawah.

1. Sediakan geraf bagi titik-titik penyelesaian bolehlaksana bagi setiap kekangan. 2. Tentukan kawasan bolehlaksana dengan mengenalpasti titik penyelesaian yang dapat

memenuhi semua kekangan serentak. 3. Lukiskan garisan keuntungan yang menunjukan semua nilai angkubah x1 dan x2 yang

menghasilkan nilai tertentu bagi fungsi objektif. 4. Gerakkan secara selari garisan keuntungan ke arah yang lebih tinggi (biasanya lebih

jauh daripada origin) sehingga pergerakan selanjutnya akan menyebabkan garisan keuntungan keluar daripada kawasan boleh laksana.

5. Titik bolehlaksana terletak di atas garisan keuntungan yang tertinggi merupakan penyelesaian yang optimum.

Angkubah Slak

Sebagai tambahan kepada penyelesaian optimum dan keuntungan terjangka, pihak pengurusan Par, Inc. juga mahu maklumat berkenaan keperluan masa pengeluaran bagi setiap operasi pengeluaran. Kita boleh menentukanm maklumat ini dengan menukarkan nilai optimum x1 dan x2 ke dalam kekangan pemprograman linear kita. Bagi masalah Par, Inc. Keperluan masa pengeluaran adalah seperti berikut:

7/10 (540) + 1 (252) = 630 jam bagi masa pemotongan dan mewarna 1/2 (540) + 5/6 (252) = 480 jam bagi masa menjahit 1 (540) + 2/3 (252) = 708 jam bagi masa kemasan 1/10 (540) + 1/4 (252) = 117 jam bagi masa pemeriksaan dan pembungkusan

Penyelesaian yang lengkap memberitahu pengurusan bahawa pengeluaran 540 buah beg standard dan 252 buah beg deluxe memerluakan semua masa pemotongan dan mewarna yang ada (630 jam) dan semua masa kemasan yang ada (708 jam), sementara 120 jam masa menjahit (600 - 480) dan 18 jam masa pemeriksaan dan pembungkusan (135 - 117) masih terluang. 120 jam masa menjahit yang tidak digunakan dan 18 jam masa pemeriksaan dan pembungkusan yang tidak digunakan adalah dirujukkan sebagai slak bagi dua jabatan tersebut. Di dalam terminologi pemprograman linear, mana-mana yang tidak digunakan atau kapasiti yang terbiar bagi kekangan adalah dirujukkan sebagai slak berkaitan dengan kekangan.

Biasanya angkubah akan ditambah kepada formulasi masalah pemprograman linearmewakili slak, atau kapasiti terbiar. Angkubah tersebutdipanggil angkubah slak, dan oleh kerana itukapasiti yang tidak digunakan tidak memberikan sumbangan kepada keuntungan ia mempunyai koefisien sifar di dalam fungsi objektif. Secara amnya, angkubah slak boleh diterangkan melalui perbezaan diantara bahagian sebelah kiri dengan bahagian sebelah kanan

20

PEMPROGRAMAN LINEAR

bagi kekangan ó. Selepas ditambah angkubah slak kepada pernyataan matematik masalah Par, Inc., model matematik boleh ditunjukkan seperti berikut:

max 10x1 + 9x2 + 0s1 + 0s2 + 0s3 + 0s4

t.k.7/10x1 + 1x2 + 1s1 = 630

1/2x1 + 5/6x2 + 1s2 = 600 1x1 + 2/3x2 + 1s3 = 7081/10x1 + 1/4x2 + 1s4 = 135

x1,x2,s1,s2,s3,s4 0

Apabila pemprograman linear ditulis di dalam bentuk semua kekangan dinyatakan sebagai persamaan, ia dikatakan ditulis di dalam bentuk standard.

Pada penyelesaian optimum, x1 = 540 dan x2 = 252, nilai bagi angkubah slak adalah seperti berikut:

Kekangan Nilai Angkubah SlakPemotongan dan mewarna s1 = 0Menjahit s2 = 120Kemasan s3 = 0Pemeriksaan dan pembungkusan s4 = 18

Bolehkah kita gunakan analisis secara geraf untuk memberikan sedikit maklumat ini? Jawabnya boleh. Dengan mencari titik penyelesaian optimum di atas Rajah 2.8, kita boleh melihat sekatan kekangan pemotongan dan mewarna dan kekangan menjahit, atau terikat, kawasan bolehlaksana terletak pada titik ini. Oleh itu penyelesaian ini memerlukan penggunaan semua masa yang ada bagi dua operasi ini. Dengan lain perkataan, geraf menunjukkan kepada kita jabatan pemotongan dan mewarna dan kemasan mempunyai slak sifar. Dengan lain perkataan, oleh kerana kekangan bagi menjahit dan pemeriksaan dan pembungkusan tidak terikat dengan kawasan bolehlaksana pada penyelesaian optimum, kita boleh jangkakan masa yang tidak digunakan atau slak bagi dua operasi ini.

Sebagai komen terakhir bagi analisis secara geraf masalah Par, Inc. kita mengingatkan anda kembali kepada kekangan kapasiti menjahit seperti ditunjukkan di dalam Rajah 2.8. Perhatikan, terutamanya, kekangan ini tidak memberi kesan keatas kawasan bolehlaksana. Iaitu, kawasan bolehlaksana adalah sama samada kekangan menjahit terlibat atau tidak. Ini memberitahu kita bahawa masa menjahit adalah mencukupi untuk menyesuaikan mana-mana paras pengeluaran yang boleh dicapai oleh tiga jabatan lain. Oleh kerana kekangan menjahit tidak memberikan kesan ke atas kawasan bolehlaksana dan tidak memberi kesan ke atas penyelesaian optimum, ia di panggil kekangan lebih-pada. Kekangan lebih-pada boleh digugurkan daripada masalah tanpa memberi kesan keatas penyelesaian optimum.

2.6 Titik Ekstrim dan Penyelesaian Optimum

Katakan keuntungan bagi bag standard Par dikurangkan dari $10 kepada $5 sebeg sementara keuntungan bagi beg deluxe dan semua kekangan tidak berubah. Model pemprograman linear

21

BAB DUA

yang lengkap bagi masalah baru ini adalah sama dengan model di dalam Bahagian 2.4 kecuali fungi objektifnya bertukar menjadi:

max z = 5x1 + 5x2

Bagaimanakah perubahan di dalam fungsi objektif memberi kesan ke atas penyelesaian optimum terhadap masalah Par, Inc. kita?. Rajah 2.13 menunjukkan secara geraf penyelesaian bagi masalah Par, Inc. dengan pembaharuan fungsi objektif. Perhatikan, oleh kerana kekangan-kekangan tidak berubah, kawasan bolehlaksana juga tidak berubah. Walau bagaimanapun, garisan keuntungan akan berubah mengikut fungsi objektif yang baru.

Dengan menggerakkan garisan keuntungan selari jauh daripada origin, kita dapati penyelesaian optimum ditunjukkan di dalam Rajah 2.13. Nilai bagi angkubah-angkubah keputusan pada titik ini adalah x1 = 300 dan x2 = 420. Dengan mengurangkan keuntungan bagi bag standard akan menyebabkan perubahan di dalam penyelesaian optimum. Kenyataannya, seperti yang anda jangkakan, kita mengurangkan pengeluaran bag standard yang memberikan keuntungan yang rendah dan meningkatkan pengeluaran bagi beg deluxe yang mempunyai keuntungan yang tinggi.

Apakah yang anda lakukan terhadap lokasi penyelesaian optimum di dalam dua masalah pemprograman linear yang telah kita selesaikan setakat ini? Lihat dengan teliti pada penyelesaian secara geraf di dalam Rajah 2.12 dan 2.13. Perhatian penting yang mesti anda buat ialah penyelesaian optimum mesti pada satu daripada titik ekstrim atau sudut kawasan bolehlaksana. Di dalam teminalogi pemprograman linear sudut ini dikenali sebagai titik ekstrim bagi kawasan bolehlaksana. Oleh itu, masalah Par, Inc. mempunyai lima sudut atau lima titik ekstrim kawasan bolehlaksana (Lihat Rajah 2.14). Kita sekarang boleh menyatakan pemerhatian kita berkenaan lokasi penyelesaian bolehlaksana sebagai berikut 1:

t 1 Kita akan melihat di Bahagian 2.8 dimana terdapat 3 keadaan khas (ketakbole laksanaan dan ketakterbatasan) didalam pemprograman linear yang tidak terdapat penyelesaian optimum. Oleh itu pernyataan diatas tidak boleh digunakan bagi keadaan ini.

22

PEMPROGRAMAN LINEAR

Rajah 2.13Penyelesaian Optimum Bagi Masalah par, Inc.

Dengan Fungsi Objektif 5x1 + 9x2

Penyelesaian optimum bagi LP boleh ditemui pada titik ekstrim kawasan bolehlaksana sesuatu masalah

23

BAB DUA

Rajah 2.14Lima Titik Ekstrim Penyelesaian Bolehlaksana

Bagi Masalah Par, Inc.

Pernyataan ini bermakna sekiranya anda mencari penyelesaian optimum bagi masalah pemprograman linear, anda tidak perlu menilai semua titik penyelesaian boehlaksana. Kenyataannya, anda hanya perlu menimbangkan penyelesaian bolehlaksana yang terjadi pada titik ekstrim kawasan bolehlaksana. Oleh itu di dalam masalah Par, Inc. daripada mengira dan membandingkan keuntungan bagi semua penyelesaian bolehlaksana, kita boleh mencari penyelesaian optimum dengan menilai penyelesaian lima titik ekstrim dan memilih salah satu daripadanya yang memberikan keuntungan yang tertinggi. Sebenarnya tatacara penyelesaian secara geraf tidak lebih daripada jalan yang mudah untuk menentukan titik ekstrim yang optimum bagi masalah dua-angkubah. linear selalunya terbentuk pada titik ekstrim, pilih beberapa fungsi objektif yang berbeza bagi masalah Par, Inc. dan lakarkan geraf untuk mencari penyelesaian optimum bagi setiap keadaan. Anda akan dapat melihat sekiranyanya anda menggerakkan garisan keuntungan jauh daripada origin, titik penyelesaian bolehlaksana yang terakhir - penyelesaian optimum - selalunya salah satu daripada titik ekstrim ini.

Berbilang Penyelesaian Optimum

Apakah akan terjadi sekiranya garisan keuntungan yang tertinggi terletak di atas satu daripada garisan kekangan yang menjadi sempadan kepada kawasan bolehlaksana? Keadaan ini ditunjukkan bagi fungsi objektif 6.3x1 + 9x2 di dalam Rajah 2.15. Adakah penyelesaian optimum

24

PEMPROGRAMAN LINEAR

masih terbentuk pada titik ekstrim (1), titik ekstrim (2), dan dimana-mana titik di atas garisan segmen yang menyambungkan dua titik-titik ini. Ini merupakan kes khas bagi berbilang penyelesaian optimum atau berbilang optimum. Seperti yang dapat anda lihat, apabila berbilang optimum berlaku maka terjadilah bilangan infiniti penyelesaian optimum terbentuk di atas segmen garisan yang menyambungkan dua titik ekstrim. Masalah pemprograman linear mempunyai berbilang optimum merupakan keadaan yang baik bagi pengurus yang cuba untuk melaksanakan penyelesaian. Ini bermakna terdapat banyak kombinasi angkubah-angkubah yang optimum dan pengurus boleh memilih penyelesaian tertentu yang lebih bersesuaian.

Rajah 2.15Masalah Par, Inc. dengan Fungsi Objektoif

6.3x1 + 9x2 (Penyelesaian Berbilang Optimum)

2.7 Masalah Peminimuman Mudah

Masalah Par, Ins. Melibattkan pemaksimuman, banyak masalah pemprograman linear lebih natural diformulasi sebagai masalah peminimuman. Sebagai contoh, pertimbangkan kes sebuah kilang yang mempunyai kontrak untuk menjual beberapa unit keluaran kepada beberapa pembeli. Pengilang tidak menghirukan berapa banyak yang hendak dikeluarkan; masalahnya ialah meminimumkan jumlah kos pengeluaran tertakluk kepada kekangan untuk memenuhi permintaan. Sebagai ilustrasi bagaimanakah masalah peminimuman boleh dibentuk, mari kita timbangkan masalah yang dihadapi oleh Photo Chemical, Inc.

25

BAB DUA

Photo Chemical mengeluarkan dua jenis cecair mencuci gambar. Kedua-dua keluaran tersebut melibatkan kos Photo Chemical $1 setiap gelen untuk dikeluarkan. Berdasarkan kepada analisis paras inventori semasa dan pesanan bagi bulan hadapan, pengurusan Photo Chemical telah mengenalpasti sekurang-kurangnya 30 gelen bagi keluaran 1 dan sekurang-kurangnya 20 gelen bagi keluaran 2 mesti dikeluarkan dalam masa dua minggu berikutnya. Pengurusan juga menyatakan inventori yang ada sekarang merupakan bahan mentah yang mudah rosak diperlukan di dalam pengeluaran kedua-dua cecair dan mesti digunakan di dalam masa dua minggu. Inventori semasa bagi bahan mentah mudah rosak ialah 80 paun. Oleh kerana lebih banyak bahan mentah ini boleh dipesan sekiranya perlu, mana-mana inventori semasa jika tidak digunakan dalam masa dua minggu akan musnah. Oleh itu keperluan pengurusan sekurang-kurangnya 80 paun akan digunakan dalam masa 2 minggu akan datang. Selanjutnya, diketahui keluaran 1 memerlukan 1 paun bahan mentah mudah rosak setiap gelen dan keluaran 2 memerlukan 2 paun bahan mentah segelen. Oleh kerana objektif Photo Chemical ialah untuk mengekalkan kos pengeluaran pada paras yang paling minimum, pengurusan firma sekarang melihat perancangan kos pengeluaran yang minimum menggunakan 80 paun bahan mentah mudah rosak tersebut dan menghasilkan sekurang-kurangnya 30 gelen keluaran 1 dan sekurang-kurangnya 20 gelen keluaran 2. Apakah penyelesaian kos yang minimum?.

Untuk menjawab soalan ini, mari kita cuba untuk menulis masalah tersebut sebagai masalah pemprograman linear. Mengikut tatacara sebagaimana dilakukan di dalam masalah Par Inc., pertamanya kita menentukan angkubah-angkubah keputusan dan fungsi objektif bagi masalah.

Biarkan

x1 = bilangan gelen keluaran 1 dikeluarkanx2 = bilangan gelen keluaran 2 dikeluarkan

Oleh kerana kos pengeluaran bagi Photo Chemical Inc. adalah $1 bagi setiap gelen keluaran 1 dan $1 bagi setiap gelen keluaran 2 yang dikeluarkan, fungsi objektif yang mewakili jumlah kos ialah

1x1 + 1 x2

menggunakan tetanda z sebagai nilai fungsi objektif, objektif kos yang minimum boleh ditulis sebagai

min z = 1 x1 + 1 x2

Kemudian timbangkan kekangan yang dikenakan ke atas masalah Photo Chemical Inc. Bagi kekangan bahan mentah mudah rosak, keluaran 1 menggunakan 1 paun bahan mentah dan keluaran 2 menggunakan 2 paun bahan mentah. Jumlah bilangan paun bahan mentah yang diperlukan untuk menghasilkan x1 unit keluaran 1 dan x2 unit keluaran x2 ialah

1 x1 + 2 x2

Oleh kerana kekangan yang digunakan sekurang-kurangnya 80 paun bahan mentah mudah rosak, kekangan bahan mentah menjadi

26

PEMPROGRAMAN LINEAR

1 x1 + 2 x2 80

Dengan kekangan mengeluarkan sekurang-kurannya 30 gelen keluaran 1 (x1 30) dan sekurang-kurangnya 20 gelen keluaran 2 (x2 20) dan kekangan bukan negatif (x1,x2 0), kita mempunyai formulasi pemprograman linear yang berikut bagi masalah Photo Chemical

min 1 x1 + 1 x2 t.k.

1 x1 + 2 x2 80 Bahan mentah1 x1 30 Keluaran 1 1 x2 20 Keluaran 2 x1,x2 0

Oleh kerana model pemprograman linear hanya mempunyai dua angkubah keputusan, penyelesaian secara geraf boleh digunakan untuk mencari kuantiti pengeluaran yang optimum. Kaedah geraf bagi masalah ini, adalah sama sebagaimana masalah Par, Inc., memerlukan kita membuat geraf bagi semua kekangan dalam usaha untuk mencari titik penyelesaian bolehlaksana. Perhatikan di sini, masalah Photo Chemical mempunyai kekangan lebih besar daripada atau sama dengan akan menyebabkan titik bolehlaksana dibahagian atas garisan-garisan kekangan . Garisan kekangan dan kawasan boleh laksana ditunjukkan di dalam Rajah 2.16.

Dalam usaha untuk menentukan nilai kos yang minimum (1x1 + 1x2), pertamanya kita melukis garisan kos yang berpadanan dengan nilai z = 1x1 + 1x2. Sebagai contoh, kita cuba mulakan dengan melukis garisan 1x1 + 1x2 = 80. Rajah 2.17 menunjukkan geraf bagi garisan tersebut. Dengan jelas, terdapat banyak titik-titik di dalam kawasan bolehlaksana yang menghasilkan nilai kos ini (sebagai contoh x1 = x2 = 40).

27

BAB DUA

Untuk mencari nilai bagi x1 dan x2 yang memberikan kos yang minimum, kita gerakkan garisan kos ke arah yang lebih rendah kekiri sehingga, kita gerakkan lagi, ia akan keluar daripada kawasan bolehlaksana. Perhatikan disini, garisan 1x1 + 1x2 = 55 bersilang di kawasan bolehlaksana pada titik (x1= 30, x2 =25). Oleh itu penyelesaian optimum bagi masalah ini ialah x1 = 30 dan x2 =25 dengan nilai fungsi objektif adalah 55. Juga di dalam Rajah 2.17 kita boleh melihat kekangan bahan mentah dan kekangan minimum x1 adalah terikat dan seperti juga masalah pemaksimuman masalah Par, penyelesaian optimum terbentuk pada titik ekstrim bagi kawasan boleh laksana.

28

Rajah 2.16

Set Penyelesaian BolehlaksanaBagi Masalah Photo Chemical, Inc.Rajah 2.17

Penyelesaian GrafikBagi Masalah Photo Chemical, Inc.

PEMPROGRAMAN LINEAR

Ringkasan Tatacara penyelesaian secara Geraf Bagi Masalah Peminimuman

Langkah-langkah di dalam tatacara penyelesaian secara geraf bagi masalah peminimuman digariskan seperti dibawah:

1. Sediakan geraf bagi titik penyelesaian bolehlaksana bagi setiap kekangan.2. Kenalpasti kawasan penyelesaian bolehlaksana dengan mengenalpasti titik

penyelesaian yang memenuhi semua kekangan serentak.3. Lukiskan garisan kos yang menunjukkan semua nilai angkubah x1 dan x2 yang

memberikan nilai tertentu fungsi objektif.4. Gerakan secara selari garisan kos ke arah kos yang rendah (biasanya kearah origin)

sehingga pergerakan selanjutnya akan membuatkan garisan kos keluar sepenuhnya daripada kawasan bolehlaksana.

5. Titik ekstrim bolehlaksana menyentuh sehabis rendah yang mungkin garisan kos merupakan penyelesaian yang optimum.

Angkubah Lebihan

Analisis yang lengkap penyelesaian optimum bagi masalah Photo Chemical menunjukkan jumlah 1x1 + 1x2 = 1(30) + 2(25) = 80 paun bahan mentah digunakan sepenuhnya di dalam proses pengeluaran. Sementara itu, keluaran 1 adalah di paras penerimaan minimum pengeluaran 30 unit, sementara pengeluaran keluaran 2 adalah melebehi 5 unit daripada paras minimum 20 unit. Pengeluaran lebihan bagi keluaran 2 dikenali sebagai lebihan. Di dalam teminologi pemprograman linear, mana-mana lebihan kuantiti berpadanan dengan kekangan adalah dirujukkan kepada lebihan bagi kekangan yang berkenaan.

Ingat kembali dengan kekangan angkubah slak ditambah kepada formulasi untuk menerangkan perbezaan diantara bahagian sebelah kiri dan sebelah kanan kekangan. Bagi kekangan angkubah lebihan boleh ditolak daripada bahagian sebelah kiri untuk menjadikan kekangan dalam bentuk persamaan. Seperti juga angkubah slak, angkubah lebihan akan memberikan pengkali sifar dalam fungsi objektif kerana ia tidak memberi kesan kepada nilainya. Selepas memasukkan angkubah lebihan, model matematik bagi masalah Photo Chemical boleh ditulis sebagai:

min 1 x1 + 1 x2 + 0 s1 + 0 s2 + 0 s3

t.k. 1 x1 + 2 x2 - 1 s1 = 80

1 x1 - 1 s2 = 30 1 x2 - 1 s3 = 20 x1,x2,s1,s2,s3 0

Semua kekangan-kekangan sekarang di dalam bentuk persamaan. Oleh itu, ia merupakan bentuk standard dalam mewakili masalah Photo Chemical. Pada penyelesaian optimum (x1 = 30 dan x2 = 25) nilai bagi angkubah lebihan adalah seperti berikut:

Kekangan Nilai Angkubah lebihanBahan mentah s1 = 0Keluaran 1 s2 = 0

29

BAB DUA

Keluaran 2 s3 = 5

Rujuk kepada Rajah 2.16 dan 2.17 dan perhatikan bagaimana penyelesaian secara geraf menunjukkan kekangan bahan mentah dan kekangan keluaran 1 adalah terikat pada penyelesaian optimum. Lebihan 5 unit adalah berkaitan dengan kekangan keluaran 2 yang tidak terikat.

Perhatikan di dalam masalah pemaksimuman Par, Inc. semua kekangan adalah dalam bentuk dan di dalam masalah Photo Chemical, Inc. pula kekangan adalah dalam bentuk Walaupun corak kekangan ini mungkin terjadi di dalam masalah pemprograman linear yang lain, kami mengingati anda, jangan menjangka masalah pemaksimumam hanya mempunyai masalah kekangan dan masalah peminimuman hanya mempynyai kekangan . Sebenarnya, masalah pemprograman linear samada pemaksimuman atau peminimumam mungkin sesetengahnyan mempunyai kekangan , sesetengahnya kekangan , dan sesetengahnya mempunyai kekangan persamaan (=). Kekangan persamaan bermakna penyelesaian optimum mesti memenuhi keadaan kekangan setepatnya sebagaimana ditentukan oleh garisan kekangan.

Sebagai contoh pemprograman linear dengan tiga bentuk kekangan yang mungkin diberikan sebagaimana dibawah (masalah 20 pada akhir bab akan menyoal anda untuk menyelesaikan masalah ini menggunakan geraf).

min 2 x1 + 2 x2 t.k.

1 x1 + 3 x2 123 x1 + 1 x2 131 x1 - 1 x2 = 3

x1 ,x2 0

Bentuk standard di dalam menyelesaikan masalah ini ialah

min 2 x1 + 2 x2 + 0 s1 + 0 s2

t.k.1 x1 + 3 x2 + 1 s1 = 123 x1 + 1 x2 - 1 s2 = 131 x1 - 1 x2 = 3

x1, x2, s1, s2 0

Formulasi ini memerlukan angkubah slak bagi kekangan dan angkubah lebihan bagi kekangan . Walau bagaimanapun, angkubah slak atau lebihan tidak diperlukan bagi kekangan ke tiga, kerana ia telah sedia di dalam bentuk persamaan.

Kaedah penyelesaian secara geraf merupakan jalan mudah untuk mencari penyelesaian titik ekstrim yang optimum bagi masalah pemprograman linear dua angkubah. Apabila menyelesaikan masalah pemprograman linear secara geraf adalah tidak penting untuk menulis masalah dalam bentuk standard. Walau bagaimanapun, kita mesti berkebolehan untuk mengira nilai angkubah slak dan lebihan dan memahami maksudnya. Di dalam Bab 3 kita akan perkenalkan tatacara penyelesaian secara aljabar, kaedah simplek, di mana boleh digunakan untuk mencari penyelesaian titik ekstrim yang optimum bagi masalah pemprograman linear yang mempunyai beberapa ribu angkubah keputusan. Langkah matematik bagi kaedah simplek

30

PEMPROGRAMAN LINEAR

melibatkan penyelesaian serentak persamaan yang mewakili kekangan bagi pemprograman linear. Oleh itu dalam menyediakan pemprograman linear untuk penyelesaian kaedah simplek kita mesti mempunyai satu persamaan linear bagi setiap kekangan di dalam masalah; oleh itu masalah tersebut mestilah di dalam bentuk standard.

Sebagai peringatan terakhir, penting untuk dinyatakan bahawa bentuk standard masalah pemprograman linear adalah bersamaan dengan formulasi masalah yang asal. Iaitu, penyelesaian optimum terhadap sebarang masalah pemprograman linear adalah sama sebagaimana penyelesaian optimum terhadap bentuk standard bagi masalah. Bentuk standard tidak akan mengubah masalah asas, ianya hanya mengubah bagaimana kita menulis kekangan bagi masalah.

2.8 Ketidakboleh laksanaan dan Ketidakberbatasan

Di dalam bahagian ini kita bincangkan dua keadaan khas yang boleh terjadi apabila kita menyelesaikan masalah pengatrucaraan linear.

Ketidakboleh laksanaan

Ketidakboleh laksanaan terjadi apabila tiada penyelesaian kepada masalah pemprograman linear yang dapat memenuhi semua kekangan, termasuk keadaan bukan negatif x1, x2 0. Secara geraf, ketidakboleh laksanaan bermaksud kawasan bolehlaksana tidak terbentuk; oleh itu, tidak terdapat titik yang dapat memenuhi semua kekangan dan keadaan bukan negatif serentak. Untuk menggambarkan keadaan ini, mari kita lihat kembali masalah yang dihadapi oleh Par Inc.

Katakan pehak pengurusan telah menetapkan sekurang-kurangnya 500 buah beg standard dan 360 buah beg deluxe mesti dikeluarkan. Geraf bagi kawasan penyelesaian kita sekarang perlu dibentuk berdasarkan kepada keperluan ini (Lihat Rajah 2.18). Kawasan berlorek dibahagian bawah kiri graf menunjukkan titik-titik yang dapat memenuhi kekangan jabatan ke atas masa yang ada. Kawasan berwarna bahagian atas kanan menunjukkan titik yang memenuhi keperluan minimum pengeluaran 500 bag standard dan 360 buah beg deluxe. Tetapi tidak terdapat satu titik yang dapat memenuhi kedua-dua set kekangan tersebut. Oleh itu kita lihat sekiranya pehak pengurusan mengkehendaki keperluan pengeluaran yang minimum, maka tidak terdapat penyelesaian boleh laksana bagi model pemprograman linear.

31

BAB DUA

Rajah 2.18Kawasan Tidak Bolehlaksana Bagi Masalah par, Inc. dengan Keperluan

Pengeluaran 500 Bag Standard dan 360 Beg Deluxe

Bagaimana kita mentafsirkan ketidak bolehlaksanaan di dalam bentuk masalah sekarang? Pertamanya kita perlu memberitahu pengurusan pada paras sumber-sumber yang ada (seperti masa pemotongan dan mewarna, masa menjahit, masa Kemasan dan masa pemereksaan dan pembungkusan) adalah tidak mungkin untuk membuat 500 buah beg standard dan 360 buah beg deluxe. Selanjutnya, kita boleh memberitahu pengurusan setepatnya berapa banyakkah setiap sumber mesti ditambah di dalam usaha untuk mengeluarkan 500 beg standard dan 360 buah beg deluxe. Jumlah sumber minimum yang berikut mestilah ada:

Operasi Keperluan minimum (Jam)

Sumber yang ada (Jam)

Pemotongan dan mewarna 7/10(500) + 1(360) = 710 630Menjahit 1/2(500) + 5/6(360) = 550 600Kemasan 1 (500) + 2/3(360) = 740 708Pemeriksaan danpembungkusan 1/10(500) + 1/4(360) = 140 135

Oleh itu kita memerlukan tambahan 80 jam lagi masa pemotongan dan mewarna, 32 jam lagi masa Kemasan, 5 jam lagi masa pemeriksaan dan pembungkusan di dalam usaha untuk memenuhi keperluan pengeluaran pehak pengurusan.

32

PEMPROGRAMAN LINEAR

Sekiranya, selepas melihat laporan kita, pihak pengurusan masih mahu mengeluarkan 500 beg standard dam 360 beg deluxe, ia bagaimana pun mesti memberikan tambahan sumber. Ini bermakna terpaksa mengupah buroh tambahan untuk berkerja dijabatan pemotongan dan mewarna, memindahkan buroh daripada mana-mana bahagian kilang sebagai pekerja sementara di dalam jabatan Kemasan, ataupun mengambil buroh jahitan untuk menolong di dalam pemeriksaan dan pembungkusan. Sebagaimana yang dapat anda lihat, terdapat banyak kemungkinan untuk bertindak ke atas aksi pengurusan, untuk mengatasi masalah tidak ada penyelesaian boleh laksana. Perkara yang penting untuk kita pertimbangkan ialah analisis pemprograman linear boleh menolong kita untuk menentukan samada perancangan pengurusan boleh dilaksanakan atau tidak. Dengan menganalisis masalah menggunakan pemprograman linear, kita boleh menentukan keadaan ketidak bolehlaksanaan dan memerlukan tindakan pembetulan.

Ketidakterbatasan

Penyelesaian masalah pemprograman linear adalah ketidakterbatasan jika nilai bagi penyelesaian boleh dibuat terlalu banyak tanpa melanggar mana-mana kekangan. Keadaan ini dikenali sebagai 'utopia pengurusan'. Sekiranya keadaan ini terjadi di dalam masalah memaksimumkan keuntungan, adalah benar bagi pengurus mencapai keuntungan yang tidak terhad.

Di dalam model pemprograman linear bagi masalah dunia sebenar, berlakunya penyelesaian ketidakterbatasan bermakna masalah tersebut tidak dirumuskan dengan sempurna. Sebagai contohnya, kita tahu bahawa tidak mungkin untuk meningkatkan keuntungan yang tidak terhingga. Oleh itu kita mesti membuat kesimpulan sekiranya keputusan dalam masalah memaksimumkan keuntungan adalah penyelesaian ketidakterbatasan, model matematik nyatalah tidak tepat dibentuk dalam masalah dunia sebenar. Biasanya apa yang terjadi ialah kekangan dikeluarkan daripada formulasi masalah.

Secara geraf, sekiranya masalah pemprograman linear terdapat penyelesaian ketakterbatasan, kawasan bolehlaksana bertambah sehingga infiniti dalam arah yang sama. Sebagai ilustrasi, perhatikan contoh numerik mudah ini:-

max 2 x1 + 1 x2

t.k.1 x1 2

1 x2 5 x1,x2 0

Dalam Rajah 2.19 kita telah lakarkan kawasan bolehlaksana berkaitan dengan masalah ini. Perhatikan kita hanya boleh menunjukkan sebahagian daripada kawasan bolehlaksana, sementara kawasan bolehlaksana berkembang selanjutnya dalam arah menurut paksi x1. Melihat kepada garisan keuntungan dalam Rajah 2.18, kita lihat penyelesaian bagi masalah ini boleh dibuat seberapa besar yang kita kehendaki. Oleh itu, walau apa pun penyelesaian yang kita ambil, sentiasa terdapat beberapa penyelesaian bolehlaksana dengan nilai yang lebih besar. Oleh itu kita katakan penyelesaian kepada pemprograman linear ini ialah ketidakterbatasan.

33

BAB DUA

Rajah 2.19Contoh Masalah Ketakterbatasan

34