Algoritma simpleks dan titik ekstrim
Untuk pertanyaan ini, tangan pendek saya adalah LP = program linier, BFS = solusi dasar yang layak, SEF = bentuk persamaan standar.
Karena algoritma Simplex melakukan iterasi dari titik ekstrim ke titik ekstrim (sesuai dengan fakta bahwa Simplex melakukan iterasi dari BFS ke BFS ketika LP berada dalam SEF), bagaimana algoritma Simplex bekerja secara geometris ketika daerah yang layak adalah polihedron yang tidak dapat direalisasikan di SEF (misalnya setengah spasi)? Misalkan kita memiliki LP dimana wilayah yang layak tidak memiliki titik ekstrim. Kemudian kita dapat menulis LP 'setara' yang ada di SEF dan menjalankan algoritma Simplex di atasnya. Tetapi ada poin ekstrim untuk polihedron baru ini, sedangkan untuk yang asli tidak ada, dengan asumsi. Awalnya saya berpikir bahwa titik ekstrim dari satu LP secara biologis berhubungan dengan titik ekstrim dari LP lainnya, tetapi ternyata tidak demikian.
Jadi kapan tepatnya titik ekstrim dari LP versi SEF sesuai secara biologis dengan titik ekstrim dari aslinya? Dan selanjutnya, ketika bijection seperti itu tidak berlaku, bagaimana kita bisa menafsirkan secara geometris apa yang dilakukan algoritma Simplex dalam hal LP asli?
Jawaban
algoritma Simplex mengulangi dari titik ekstrim ke titik ekstrim
Secara teknis, tidak. Algoritma simpleks melakukan iterasi dari basis ke basis . Kebetulan solusi dasar yang layak sesuai dengan poin ekstrim. (misalnya, simpleks ganda melakukan iterasi melalui solusi dasar yang layak ganda, yang bukan merupakan titik ekstrem dari wilayah layak-primal).
Pertimbangkan LP dalam bentuk standar, yang menulis \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}Wilayah layak LP itu selalu berupa polihedral. Jika tidak memiliki titik ekstrem, maka kolom tersebut kosong (dan tidak ada solusi dasar yang layak), atau sub-spasi affine dari$\mathbb{R}^{n}$. Sekarang, kasus terakhir tidak dapat terjadi, karena tidak ada sub-spasi affine yang dapat menjadi bagian dari$\mathbb{R}_{+}^{n}$.
Sekarang, kembali ke (apa yang saya pikirkan) pertanyaan awal Anda: diberi polihedron asli dan representasi SEF untuknya, apakah representasi itu memiliki titik ekstrim, dan apakah mereka sesuai dengan titik ekstrim dari polihderon asli? Jawabannya adalah: ya, SEF akan memiliki titik ekstrem, dan tidak, mungkin tidak selalu sesuai dengan titik ekstrem polihedron asli Anda.
Berikut ini contoh sederhananya: take $\mathcal{P} = \{x \in \mathbb{R}\}$, yang merupakan polihedron 1 dimensi. Formulasinya memiliki satu variabel bebas dan tidak ada batasan.
Untuk membangun representasi SEF, ganti $x$ oleh $x^{+} - x^{-}$ dengan $x^{\pm} \geq 0$. Sekarang,$(0, 0)$ adalah titik ekstrim dari SEF itu, yang berhubungan dengan $x=0$, yang bukan merupakan titik ekstrem $\mathcal{P}$.
Tidak yakin saya sepenuhnya memahami pertanyaan Anda, tetapi saya rasa kebingungan Anda berasal dari asumsi bahwa solusi dasar adalah "titik ekstrim". Sebuah solusi dasar (tidak harus primal atau dual feasible) hanyalah perpotongan dari sejumlah batasan baris (beberapa di antaranya mungkin berupa batas). Ada kemungkinan bahwa masalah tidak memiliki solusi primal atau ganda yang layak sebagai akibatnya tidak layak atau tidak terbatas. Algoritme simpleks buku teks terkadang mengabaikan fakta bahwa beberapa bentuk pendekatan fase 1 diperlukan untuk membuat BFS agar benar-benar memulai algoritme. Ada kemungkinan bahwa fase primer 1 menemukan masalah primal tidak layak dan mungkin juga fase ganda 1 menemukan masalah tidak terbatas.
Pembaruan: Jawaban oleh mtanneau mungkin mengatakan semua yang bisa dikatakan, untuk satu kendala dengan variabel bebas yang sama berlaku. Saya hanya ingin menambahkan bahwa implementasi simpleks bekerja dengan variabel bebas secara langsung dan tidak mengubahnya menjadi dua variabel yang dibatasi oleh 0. Tetapi hal yang sama berlaku, algoritme berulang di atas solusi dasar dan konvensi dibuat bahwa variabel bebas non-dasar mengambil nilainya 0. Perhatikan juga bahwa untuk polihedra berbatas, solusi dasar sesuai dengan titik ekstrim.