Artikel

4.3: Pengurangan Dengan Kaedah Simplex - Matematik


Objektif Pembelajaran

Pada bahagian ini, anda akan belajar menyelesaikan masalah pengurangan pengaturcaraan linear menggunakan kaedah simplex.

  1. Kenal pasti dan atur program linear dalam bentuk peminimuman standard
  2. Rumuskan masalah ganda dalam bentuk pemaksimum standard
  3. Gunakan kaedah simplex untuk menyelesaikan masalah pemaksaan ganda
  4. Kenal pasti penyelesaian optimum untuk masalah pengurangan asal dari jadual sederhana simplex.

Pada bahagian ini, kita akan menyelesaikan masalah pengurangan pengaturcaraan linear standard menggunakan kaedah simplex. Sekali lagi, kami mengingatkan pembaca bahawa dalam masalah pengurangan standard semua kekangan adalah dalam bentuk (ax + by ≥ c ).

Prosedur untuk menyelesaikan masalah ini dikembangkan oleh Dr. John Von Neuman. Ia melibatkan menyelesaikan masalah berkaitan yang disebut masalah berganda. Untuk setiap masalah pengurangan terdapat masalah ganda. Penyelesaian masalah ganda digunakan untuk mencari penyelesaian masalah asal. Masalah ganda adalah masalah pemaksimalan, yang telah kita selesaikan di bahagian terakhir. Kami terlebih dahulu menyelesaikan masalah ganda dengan kaedah simplex.

Dari jadual sederhana simplex, kami kemudian mengeluarkan penyelesaian untuk masalah pengurangan asal.

Sebelum kita melangkah lebih jauh, bagaimanapun, kita pertama kali belajar mengubah masalah pengurangan menjadi masalah pemaksimalan yang sesuai yang disebutnya berganda.

Contoh ( PageIndex {1} )

Tukarkan masalah peminimalan berikut menjadi ganda.

[ mulakan {array} {ll}
textbf {Minimalkan} & mathrm {Z} = 12 mathrm {x} _ {1} +16 mathrm {x} _ {2}
textbf {Tertakluk kepada:} & mathrm {x} _ {1} +2 mathrm {x} _ {2} geq 40
& mathrm {x} _ {1} + mathrm {x} _2 geq 30
& mathrm {x} _ {1} geq 0; mathrm {x} _ {2} geq 0
end {array} bukan nombor ]

Penyelesaian

Untuk mencapai matlamat kami, kami terlebih dahulu menyatakan masalah kami sebagai matriks berikut.

[ mulakan {array} {cc | c}
1 & 2 & 40 \
1 & 1 & 30 \
hline 12 & 16 & 0
end {array} bukan nombor ]

Perhatikan bahawa jadual ini kelihatan seperti jadual sederhana simplex tanpa pemboleh ubah kendur. Seterusnya, kami menulis matriks yang lajurnya adalah baris matriks ini, dan barisnya adalah lajur. Matriks seperti itu disebut a menukar dari matriks asal. Kita mendapatkan:

[ mulakan {array} {cc | c}
1 & 1 & 12 \
2 & 1 & 16 \
hline 40 & 30 & 0
end {array} bukan nombor ]

Masalah pemaksimalan berikut yang berkaitan dengan matriks di atas disebut dualnya.

[ mulakan {array} {ll}
textbf {Maksimumkan} & mathrm {Z} = 40 mathrm {y} _ {1} +30 mathrm {y} _ {2}
textbf {Tertakluk kepada:} & mathrm {y} _ {1} + mathrm {y} _ {2} leq 12
& 2 mathrm {y} _1 + mathrm {y} _2 leq 16
& mathrm {y} _ {1} geq 0; mathrm {y} _ {2} geq 0
end {array} bukan nombor ]

Perhatikan bahawa kami telah memilih pemboleh ubah sebagai y, bukannya x, untuk membezakan dua masalah tersebut.

Contoh ( PageIndex {2} )

Selesaikan secara grafik masalah peminimuman dan masalah pemaksimalan ganda.

Penyelesaian

Masalah pengurangan kami adalah seperti berikut.

[ mulakan {array} {ll}
textbf {Minimalkan} & mathrm {Z} = 12 mathrm {x} _1 + 16 mathrm {x} _2
textbf {Tertakluk kepada:} & mathrm {x} _ {1} +2 mathrm {x} _ {2} geq 40
& mathrm {x} _ {1} + mathrm {x} _ {2} geq 30
& mathrm {x} _ {1} geq 0; mathrm {x} _ {2} geq 0
end {array} bukan nombor ]

Kami sekarang menggambarkan ketidaksamaan:

Kami telah memetakan grafik, membayang kawasan kesesuaian, dan melabel titik sudut. Titik sudut (20, 10) memberikan nilai terendah untuk fungsi objektif dan nilai itu adalah 400.

Sekarang ganda adalah:

[ mulakan {array} {ll}
textbf {Maksimumkan} & mathrm {Z} = 40 mathrm {y} _1 + 30 mathrm {y} _ {2}
textbf {Tertakluk kepada:} & mathrm {y} _ {1} + mathrm {y} _ {2} leq 12
& 2 mathrm {y} _1 + mathrm {y} 2 leq 16
& mathrm {y} _ {1} geq 0; mathrm {y} _ {2} geq 0
end {array} bukan nombor ]

Kami merangka ketaksamaan:

Sekali lagi, kami telah memetakan grafik, mengorek wilayah kelayakan, dan melabel titik sudut. Titik sudut (4, 8) memberikan nilai tertinggi untuk fungsi objektif, dengan nilai 400.

Pembaca mungkin menyedari bahawa Contoh ( PageIndex {2} ) di atas adalah sama dengan Contoh 3.1.1, di bahagian 3.1. Masalahnya juga sama seperti Contoh 4.1.1 di bahagian 4.1, di mana kita menyelesaikannya dengan kaedah simplex.

Kami memerhatikan bahawa nilai minimum masalah pengurangan adalah sama dengan nilai maksimum masalah pemaksimalan; dalam Contoh ( PageIndex {2} ) minimum dan maksimum kedua-duanya adalah 400. Ini bukan kebetulan. Kami menyatakan prinsip dualitas.

Prinsip Duality

Prinsip Duality

Fungsi objektif masalah pengurangan minimum dapat dicapai jika dan hanya jika fungsi objektif ganda mencapai maksimum. Dan apabila mereka melakukannya, mereka sama.

Matlamat kami seterusnya adalah untuk mendapatkan penyelesaian untuk masalah pengurangan dari dua yang sesuai. Untuk melakukan ini, kami menyelesaikan kaedah dual dengan kaedah simplex.

Contoh ( PageIndex {3} )

Cari jalan keluar untuk masalah pengurangan dalam Contoh ( PageIndex {1} ) dengan menyelesaikan duanya menggunakan kaedah simplex. Kami menulis semula masalah kami.

[ mulakan {array} {ll}
textbf {Minimalkan} & mathrm {Z} = 12 mathrm {x} _ {1} +16 mathrm {x} _ {2}
textbf {Tertakluk kepada:} & mathrm {x} _ {1} +2 mathrm {x} _ {2} geq 40
& mathrm {x} _ {1} + mathrm {x} _ {2} geq 30
& mathrm {x} _ {1} geq 0; mathrm {x} _ {2} geq 0
end {array} bukan nombor ]

Penyelesaian

[ mulakan {array} {ll}
textbf {Maksimumkan} & mathrm {Z} = 40 mathrm {y} _ {1} +30 mathrm {y} _ {2}
textbf {Tertakluk kepada:} & mathrm {y} _ {1} + mathrm {y} _ {2} leq 12
& 2 mathrm {y} _ {1} + mathrm {y} _ {2} leq 16
& mathrm {y} _ {1} geq 0; mathrm {y} _ {2} geq 0
end {array} bukan nombor ]

Ingatlah bahawa kita menyelesaikan masalah di atas dengan kaedah simplex dalam Contoh 4.1.1, bahagian 4.1. Oleh itu, kami hanya menunjukkan jadual sederhana dan akhir sederhana.

Tableau simplex awal adalah

[ mulakan {array} {ccccc | c}
mathrm {y} _1 & mathrm {y} _2 & mathrm {x} _ {1} & mathrm {x} _ {2} & mathrm {Z} & mathrm {C}
1 & 1 & 1 & 0 & 0 & 12 \
2 & 1 & 0 & 1 & 0 & 16 \
hline-40 & -30 & 0 & 0 & 1 & 0
end {array} bukan nombor ]

Perhatikan perubahan penting. Di sini pemboleh ubah utama kami adalah ( mathrm {y} _1 ) dan ( mathrm {y} _2 ) dan pemboleh ubah slack adalah ( mathrm {x} _1 dan mathrm {x} _2 ).

Jadual akhir simplex berbunyi seperti berikut:

[ mulakan {array} {ccccc | c}
mathrm {y} _1 & mathrm {y} _2 & mathrm {x} _ {1} & mathrm {x} _ {2} & mathrm {Z} &
0 & 1 & 2 & -1 & 0 & 8 \
1 & 0 & -1 & 1 & 0 & 4 \
hline 0 & 0 & 20 & 10 & 1 & 400
end {array} bukan nombor ]

Melihat lebih dekat jadual ini menunjukkan bahawa nilai ( mathrm {x} _1 ) dan ( mathrm {x} _2 ) bersama dengan nilai minimum untuk masalah pengurangan dapat diperoleh dari baris terakhir final tableau. Kami telah menonjolkan nilai-nilai ini dengan anak panah.

[ mulakan {array} {ccccc | c}
mathrm {y} _1 & mathrm {y} _2 & mathrm {x} _ {1} & mathrm {x} _ {2} & mathrm {Z} &
0 & 1 & 2 & -1 & 0 & 8 \
1 & 0 & -1 & 1 & 0 & 4 \
hline 0 & 0 & 20 & 10 & 1 & 400
& & uparrow & uparrow & & uparrow
end {array} bukan nombor ]

Kami menyatakan semula penyelesaiannya seperti berikut:

Masalah pengurangan minimum mempunyai nilai minimum 400 pada sudut sudut (20, 10)

Kami sekarang meringkaskan perbincangan kami.

Pengurangan dengan Kaedah Simplex

  1. Selesaikan masalahnya.
  2. Tulis matriks yang barisnya mewakili setiap kekangan dengan fungsi objektif sebagai baris bawahnya.
  3. Tulis peralihan matriks ini dengan menukar baris dan lajur.
  4. Sekarang tulis masalah ganda yang berkaitan dengan transpose.
  5. Selesaikan masalah ganda dengan kaedah simplex yang dipelajari di bahagian 4.1.
  6. Penyelesaian optimum dijumpai di baris bawah matriks akhir dalam lajur yang sesuai dengan pemboleh ubah kendur, dan nilai minimum fungsi objektif adalah sama dengan nilai maksimum ganda.


Tonton videonya: Penjumlahan dan Pengurangan Bilangan Pecahan (Oktober 2021).