Contoh Metode Simplex (Tutorial dan Cara

Berfungsi)
Dalam artikel berikut, kami akan menjelaskan bagaimana cara kerjanyaMetode Simplexmelalui
berikan contoh sederhana yang sesuai dengan sebuah model dariPemrograman Linierapa
pertimbangkan 3 variabel keputusan.

Metode Simplex adalah algoritma iteratif yang dipublikasikan olehGeorge

Bernard Dantzigpada tahun 1947 di mana dicari untuk mencapai maksimum (atau minimum)
dari sebuah fungsi linier yang terdiri dari sekumpulan variabel yang harus dipenuhi
kondisi yang ditetapkan oleh batasan linier dalam bentuk pertidaksamaan. Dalam hal ini
konteks, tujuan dari artikel ini adalah untuk mendefinisikan secara rinci berbagai pendekatan
untuk penyelesaian model Pemrograman Linier menggunakan Metode
Simplex, selain berdiskusi tentang karakteristik utamanya.
Dengan tujuan tersebut dalam perspektif, mari kita pertimbangkan model optimisasi berikut.
linear

Contoh Metode Simplex (Menggunakan Kamus)

Langkah awal adalah memasukkan yang disebut variabel slack.
Untuk memahami konsep ini, mari kita pertimbangkan pembatasan pertama:

Untuk setiap solusi yang layak , nilai darisisi kiriakan menjadi yang paling

nilai darisisi kanan; o eventualmente existirá una diferencia (holgura) entre

estos 2 valores.
Dengan cara ini kami mendefinisikan comovariable de holgurade dicha restricción, la cual
dapat dinyatakan dengan , di mana . Dengan cara yang sama
Anda dapat mendefinisikan variabel slack (tidak negatif) y untuk
restriksi 2 dan 3, masing-masing. Akhirnya kita bisa menggambarkan fungsi
tujuan menggunakan secara ringkas.
Singkatnya, untuk setiap pemilihan nilai dari variabel tersebut y kita bisa
mendefinisikan nilai untuk variabel , dan menggunakan rumus berikut
 (dikenal umum sebagai kamus menurut terminologi yang digunakan dalam
bukuPemrograman Linierde Vasek Chvátal):
•
•
•
•
Tujuan dari Metode Simpleks adalah untuk mencapai perbaikan berturut-turut untuk nilai dari

fungsi objektif yang terkait dengan pemilihan solusi yang dapat diterima. Ulangi hal tersebut
prosedur tidak numerofinitode kali seharusnya
memungkinkan akhirnya mencapai solusi optimal dari masalah linier yang sedang dipelajari.
Untuk menginisialisasiMetode Simplexkita membutuhkan solusi yang layak. Di kami
contoh ini sederhana dan dapat dicapai hanya dengan menetapkan
variabel en cero. De esta forma se alcanzan los siguientes resultados:

Dalam konteks tujuan yang disebutkan sebelumnya, kita harus mencari solusi.
feasible yang memungkinkan mencapai nilai yang lebih besar untuk. Jika, misalnya,

kami mempertahankan e incrementamos el valor de kami mendapatkan ,

sehingga jika diperoleh (y ). Lebih baik lagi,

ya (menjaga ), diperoleh (y ).

Namun, jika kita mengasumsikan (mengawetkan nilai fungsi

tujuan sekarang es , tapi apa
jelas tidak memenuhi syarat ketidaknegatifan untuk variabel.
Oleh karena itu, pertanyaan yang relevan adalah: seberapa banyak nilai dapat ditingkatkan

de (mempertahankan saat yang sama) dan terus mempertahankan

kelayakan )?.
La kondisi mengimplikasikan
; de bentuk
serupa implikasi y mengandung Jelas dari 3 kuota ini
untuk variabel yang paling ketat adalah , sehingga kami meningkatkan nilai
hingga nilai itu untuk mendapatkan solusi baru:

Yang jelas merupakan perbaikan untuk nilai fungsi objektif di

perbandingan dengan nilai awal .
 Selanjutnya kita harus mencari solusi baru yang layak yang bahkan lebih baik daripada
yang baru saja kami temukan. Untuk itu variabel yang mengubah nilainya
desdeceroa unnúmero positif(12,5), harus mengubah tempatnya dari sebelah
sisi kanan kiri dari sistem persamaan. Dengan cara yang sama,
variable yang mengubah nilai dari angka positif menjadi nol harus dipindahkan
dari sisi kanan ke sisi kiri.
Dengan cara ini dan setelah manipulasi aljabar tertentu, kita dapat menulis ulang en
istilah dari sesuai yang diamati di bawah ini:

Kemudian, dengan tujuan untuk mengekspresikan dan dalam hal , sederhana

kita menggantikan hasil sebelumnya di baris yang sesuai:

•
•
•
•
•
•
Dengan cara ini, sistem persamaan kami (kamus) didefinisikan oleh:
•
•
•
•
Seperti yang kami lakukan di iterasi pertama, kami harus berusaha meningkatkan nilai dari
fungsi tujuan() memilih variabel yang sesuai di sisi kanan,
sementara kami mempertahankan variabel lainnya di sisi kanan
nol. Dalam hal ini dapat diamati bahwa meningkatkan nilai dari
variabel o akan menghasilkan penurunan nilai yang bergerak ke arah
bertentangan dengan tujuan kami untuk memaksimalkan nilai dari fungsi tujuan.
Oleh karena itu, satu-satunya pemilihan variabel di sisi kanan yang
akan meningkatkan nilai dari memilih variabel .
Berapa banyak kita harus meningkatkan nilai ?. Jawaban dapat diperoleh
langsung dari sistem persamaan sebelumnya, mempertimbangkan , la
pembatasan berarti bahwa pembatasan tidak memberlakukan syarat

adicionales y la restricción mengimplikasikan

Oleh karena itu adalah
nilai terbaik yang dapat diadopsi oleh variabel tersebut.
 Solusi baru ini sesuai dengan:

Nilai langkah dari 12,5 hingga 13 setelah satu iterasi Metode Simplex.
Selanjutnya kami memperbarui sistem persamaan di mana variabel yang
mengadopsi nilai-nilai positif akan ditemukan di sisi kiri, sementara
variabel yang sama dengan nol akan berada di sisi kanan. Dengan cara ini kita melanjutkan

variabel di sisi kiri, di mana yang memungkinkan

menggantikan di sisa persamaan:

•
•
•
•
Perlu dicatat bahwa tidak mungkin untuk terus meningkatkan nilai fungsi
tujuan melalui peningkatan variabel di sisi kanan (in
efek, nilai dari menurun). Akibatnya kita berada di hadapan
solusi optimal
masalah: nilai optimal .
Prosedur sebelumnya yang berbasis pada kamus mendukung pemahaman yang lebih baik
konseptual dasar tentang yang menjadi dasar Metode Simplex. Dengan cara
complementaria di bawah ini kami akan menyajikan sebagai perbandingan iterasi
delMétodo Simplexutilizando tablas (otableau) yang biasanya sesuai dengan
bentuk di mana algoritma disajikan dalam kursus sarjana.
Contoh Metode Simplex (Menggunakan Tableau)
Mari kita pertimbangkan kembali masalah kita tentangPemrograman Linier:

A lanjutan kami menggabungkan

variabel de holgura(no
negatif yang secara definisi memiliki koefisien nol (nol) dalam fungsi
tujuan. Dengan cara ini kita mendapatkan bentuk standar(*):
(*) Untuk kepentingan kami, kami akan menganggap bahwa bentuk standar dari sebuah model
Pemrograman Linier diberikan oleh , menjadi
format ini yang lebih kami sukai untuk mengembangkan iterasi
delMétodo Simplex di artikel terkait lainnya di situs kami.
konsekuensi pemilihan format tersebut adalah murni konvensional.
Mengambil contoh kami, tabel awal didefinisikan oleh:

Variabel slack mendefinisikan sebuahSolusi Dasar yang Layak Awal,

con (variabel non-dasar awalnya sesuai dengan
variabel asli dari model, yaitu yang menurut definisi mengadopsi sebuah

nilai sama dengan nol.

Bagaimana cara memeriksa bahwa tabel awal mewakili solusi dasar
solusi optimal untuk masalah tersebut?
Kriteria Optimalitas: Jika dalam suatu iterasi Metode Simplex tersedia
sebuah solusi dasar yang layak dan tambahan semua biaya yang dikurangi adalah lebih besar
atau sama dengan nol, berhenti karena solusi dasar yang layak saat ini adalah optimal.
Dalam contoh yang diajukan meskipun kita dihadapkan pada solusi dasar
faktorial biaya yang dikurangi dari variabel non-dasar adalah negatif, oleh karena itu tidak

kriteria optimalitas terpenuhi, yaitu, nilai tersebut masih bisa diperbaiki

dari fungsi tujuan.
Dalam hal ini kami akan secara sembarangan mempertimbangkan sebagai variabel yang masuk ke

basis, meskipun tidak ada kepastian bahwa pemilihan variabel non-dasar dengan
biaya yang lebih rendah lebih negatif berkontribusi secara negatif padaKecepatan dari

Konvergensi Metode Simplex.

Variabel yang menjadi dasar untuk memberikan tempat kepada diperoleh dari kriteria kelayakan:
Kriteria Kelayakan: Untuk memutuskan variabel dasar mana yang keluar dari basis, perlu
menghitung nilai maksimum yang dapat diambil oleh variabel non dasar yang masuk ke basis
yang menjamin kelayakan solusi dasar baru. Untuk itu, dianggap sebuah
perbandingan antara nilai solusi dasar yang layak saat ini dan yang
koefisien lebih besar dari nol di kolom variabel yang masuk. Jika semua
hasil bagi adalah negatifMasalah tidak terbatasi oleh karena itu tidak ada
solusi optimal.
Dalam contoh ini, kriteria kelayakan untuk iterasi ini adalah:

Kuantitas terkecil dicapai pada baris pertama (batasan) yang menentukan

variabel yang harus meninggalkan basis, dalam hal ini, variabel Kemudian diperbarui
tabel melakukan operasi baris dengan mempertimbangkan penyebut dari yang minimum
kuotien komposit. Tujuannya adalah untuk mencapai di kolom variabel lo
yang saat ini kami miliki di kolom variabel .
Misalnya, kita dapat membagi baris 1 dengan 2 sehingga mendapatkan 1 di posisi
tentang baris pivot. Kemudian pada baris baru 1 ini kita bisa mengalikannya dengan -4 dan menjumlahkannya ke

la fila 2. También se puede alcanzar un cero para la variable di baris 3

mengalikan baris baru 1 dengan -3 dan menjumlahkannya dengan baris 3. Akhirnya untuk mencapai
nol dalam biaya yang dikurangi dari dikalikan dengan 5 baris baru 1 dan dijumlahkan ke
baris 4.

Dengan cara ini, tabel Metode Simplex setelah satu iterasi akan menjadi
bentuk berikut:

La solusi dasar layak aktual berkorespondensi

a: dengan nilai dalam fungsi
tujuan Dapat dilihat bahwa hasil tersebut konsisten dengan pendekatan
dediccionarios digunakan awalnya.
Jelas tidak memenuhi kriteria optimalitas karena variabel tidak
dasar memiliki biaya yang sangat rendah. Oleh karena itu masuk ke dalam basis dan oleh karena itu
kita harus menghitung kembali kriteria kelayakan untuk menentukan variabel
yang harus ditinggalkan oleh dasar:

Elpivoteahora sekarang berada di baris 3 dan akibatnya variabel

dasar harus meninggalkan dasar. Perhatikan bahwa tidak dipertimbangkan untuk perhitungan dari

kriteria kelayakan koefisien variabel correspondiente a la fila 2 del

tabel sebelumnya (yang nilainya nol dan oleh karena itu hasil bagi tidak terdefinisi).

Kami memperbarui tabel Metode Simplex dengan hasil sebagai berikut

resultados:

Nilai yang diadopsi oleh variabel dasar yang sesuai dengan yang baru ini
iterasi adalah yang juga mewakili
solusi optimal dari model Pemrograman Linier (dengan memenuhi
dari kriteria optimalitas). Kemudian nilai optimalnya sesuai dengan .
Penting: Ada alat komputer dan aplikasi yang memungkinkan
menyelesaikan masalah Program Linear secara online menggunakan Metode
Simplex. Berikut adalah cuplikan dari hasil yang dicapai untuk
kami contoh menggunakan la aplikasi tersedia
en[Link]
 Metode Simplex (Kesimpulan)
Contoh yang telah kami kembangkan dalam artikel ini bertujuan untuk mempersembahkan secara

sederhana dan didaktis dasar-dasar utama yang terkait dengan Metode Simplex. Sebaiknya
menekankan bahwa telah diperlukan untuk penerapan algoritma membawa model
asal-usul ke bentuk standarnya yang seperti yang dibahas sebelumnya dapat memiliki
representasi yang berbeda sesuai dengan bibliografi yang dikonsultasikan.
Dalam konteks ini, setiap masalah Pemrograman Linear dalam bentuk standarnya
memenuhi sifat-sifat berikut yang ditetapkan diTeorema Fundamental
dari Pemrograman Linear:
Jika masalah tidak memiliki solusi optimal maka itu adalahtidak terbatasotak terlaksana.
2. Jika memiliki solusi yang layak, memiliki sebuahsolusi dasar yang layak.
3. Jika masalah memiliki solusi optimal, maka memiliki solusi dasar yang layak optimal.
Perlu dicatat bahwa tidak selalu tersedia solusi dasar yang layak dalam
variabel asli dari model (setelah membawa masalah ke bentuk standarnya).
Meskipun ada berbagai strategi algoritmik untuk menghadapi kesulitan ini, ada
mengusulkan kepada pembaca untuk meninjau tutorial yang telah kami kembangkan tentang ini

masalah, khususnya terkait denganMetode Simpleks 2 Fase, Metode dari

la M BesaryMetode Simplex Dual.
Selain itu, dengan tujuan untuk merangkum beberapa ide utama dari
algoritma kami telah menyiapkan sebuah infografis yang kami sebut10 Hal yang
Anda perlu mengetahui tentang Metode Simplex.
Akhirnya kami ingin mengingatkan pengguna kami bahwa di BlogManajemen
OperasiSejauh ini, lebih dari 80 publikasi terkait dapat ditemukan
laPemrograman Linier dan yangInvestigasi Operasi. Dengan cara
favoritkan pencarian cepat masuk ke menuCara Memulai. Akhirnya
Kami akan menghargai jika Anda dapat membagikan dan menyebarkan materi ini sebanyak mungkin.

dianggap berguna dan mengevaluasi tutorial ini menggunakanbintangdi akhir ini

publikasi.