Chapter 3 : The Simplex Method & Sensitivity Analysis

Simplex Method

Dalam LP model (yang ada objective dengan constraints) mestilah memenuhi 2 syarat ni:

1.All the constraints (with the exception of the nonnegativity of the variables)  are equations with the nonnegative right-hand side .
2.all the variables are nonnegative.

Lepas kita bina model LP ni, kita akan selesaikan bagaimana nak cari persilangan max/min dengan 3 cara:

1.Simplex Method biasa
2.Big M
3.2- phase

Kita akan go through satu-satu eh ketiga-tiga kaedah ni..

1.Simplex Method biasa.

Rule: kalu jumpa kurang atau sama dengan, kene +s
         kalu jumpa lebih atau sama dengan ,kene -s+a
dan   kalu jumpa sama dengan, kene +a(artificial variable)

Contoh 

1st step kene buat ialah tgok pada objective. Objective adalah MIN.. so bila min, rule dia +M pada z dan cari most +ve pada row z kat teblau nanti. Mesti blur kan.. meh nak tnjuk jalan..

nampak tak..Cekti cakap +M pada z..kita akan tambah dua M sebab pada constraint 1 dan 2 ada artificial variable/a...kalu ada artificial variable pada constraint 3, kene tulis Ma3 lah.. pastu tulis sama dengan kat belakang tu...faham?

Pastu...kene carik basic variable(bv) pulak sebab kita nak letak bv pada teblau nanti..cne nak carik bv ni, kene compare antara 3 contraint ni, tgk pada s dengan a yang positive..so itulah yang jadi bv..

ni adalah teblau kita...

teblau yang pertama ....tengok pada row z...ada -4,-1,1,-1,-M,-M tapi solution 0..M ni sebenarnya adalah nombor yang sangat besar okeh..mungkin 300 mungkin 4000.. tak logik lah = 0 kan.. so kita kene hilangkan -M ni..

tengok teblau yang kedua pulak..

ingat tak tadi Cekti cakap pilih most +ve pada z row kat teblau? so ini lah sebabnya..sepanjang column X1 ada 3,4,1 kan..kita kene pilih antara nombor ni untuk kita jadikan 1..cne nak pilih?  kene kira ratio test dengan cara bahagikan solution(3,6,4) dengan element pada X1(3,4,1)...3/3=1,6/4=3/2,4/1=4...antara 3ratio test ni, pilih yang positif min iaitu 1..jadi element pada 1 ialah 3..jadi pilihlah 3..

Ingat ! lepas dah jadikan element 3 dengan 1, kene tukar bv dengan X1 ,bukan lagi a1..seterusnya lah kene buat ERO samapai sume column sama dengan 0..

Last sekali kene keluarkan bv dengan solution yang hujung sekali tu...nak dapat z pulak, ganti je dengan nilai yang dah kita dapat tadi....ok..