Kaedah simplex− ini ialah kaedah penghitungan teratur pelan rujukan (ketertiban dipastikan dengan perubahan monotonik dalam nilai fungsi objektif apabila beralih ke pelan seterusnya). Dalam kes ini, adalah perlu untuk mematuhi prinsip: setiap langkah seterusnya harus bertambah baik atau, dalam kes yang melampau, tidak memburukkan nilai fungsi objektif.
Untuk menyelesaikan ZLP kaedah simplex ia dibawa ke bentuk kanonik, i.e. Dari sekatan - ketidaksamaan - perlu membuat sekatan - kesaksamaan. Untuk melakukan ini, faktor bukan negatif tambahan dimasukkan ke dalam setiap kekangan pembolehubah kunci kira-kira dengan tanda “+” jika tanda ketaksamaan ialah “£”, dan dengan tanda “–” jika tanda ketaksamaan ialah “³”.
Dalam fungsi objektif, pembolehubah tambahan ini disertakan dengan pekali sifar, i.e. kemasukan fungsi objektif tidak akan berubah. Setiap pembolehubah yang tidak tertakluk kepada keadaan bukan negatif boleh diwakili sebagai perbezaan dua pembolehubah bukan negatif: .
Jika kekangan tugas mencerminkan ketersediaan dan penggunaan sumber, maka nilai berangka pembolehubah tambahan dalam pelan tugas, yang ditulis dalam bentuk kanonik, adalah sama dengan jumlah sumber yang tidak digunakan.
Untuk menyelesaikan masalah menggunakan kaedah simplex yang akan kami gunakan jadual ringkas ringkas bagi sistem persamaan linear dan kaedah penyingkiran Jordan yang diubah suai.
1. Membuat pelan rujukan pertama
Tugas tetap sama. Mari kita bawa bentuk piawai sistem ketaksamaan (1) ke dalam bentuk kanonik sistem persamaan dengan memperkenalkan pembolehubah baki tambahan x 3 , x 4 , x 5 ,x 6 .
atau 
Dalam erti kata ekonomi, nilai pembolehubah tambahan x 3 , x 4 , x 5 menentukan baki bahan mentah selepas penjualan produk.
Matriks sistem persamaan yang terhasil mempunyai bentuk:
Ia boleh dilihat bahawa dalam matriks A asas minor bagi urutan ke-4 ialah penentu yang terdiri daripada pekali unit untuk pembolehubah tambahan x 3 , x 4 , x 5 ,x 6, kerana ia berbeza daripada sifar dan bersamaan dengan 1. Ini bermakna vektor lajur untuk pembolehubah ini adalah bebas secara linear, i.e. bentuk asas, dan pembolehubah yang sepadan x 3 , x 4 , x 5 ,x 6 ialah asas(utama). Pembolehubah x 1 , x 2 akan dipanggil percuma(bukan teras).
Jika pembolehubah bebas x 1 dan x 2 menetapkan nilai yang berbeza, maka, menyelesaikan sistem berkenaan dengan pembolehubah asas, kita memperoleh bilangan penyelesaian separa yang tidak terhingga. Jika pembolehubah bebas hanya diberi nilai sifar, maka daripada set penyelesaian tertentu yang tidak terhingga seseorang boleh memilih penyelesaian asas- pelan asas.
Untuk mengetahui sama ada pembolehubah boleh menjadi asas, adalah perlu untuk mengira penentu yang terdiri daripada pekali pembolehubah ini. Jika penentu ini tidak sama dengan sifar, maka pembolehubah ini boleh menjadi asas.
Bilangan penyelesaian asas dan bilangan kumpulan pembolehubah asas yang sepadan boleh tidak lebih daripada , di mana n– jumlah bilangan pembolehubah, r– bilangan pembolehubah asas, r≤ m≤ n.
Untuk tugas kita r = 4; n= 6. Kemudian 
, iaitu 15 kumpulan 4 pembolehubah asas (atau 15 penyelesaian asas) adalah mungkin.
Mari kita selesaikan sistem persamaan bagi pembolehubah asas x 3 , x 4 , x 5 ,x 6:
Dengan mengandaikan bahawa pembolehubah bebas x 1 = 0, x 2 = 0, kita memperoleh nilai pembolehubah asas: x 3 = 312; x 4 = 15; x 5 = 24;x 6 = –10, i.e. penyelesaian asas ialah = (0; 0; 312; 15; 24; –10).
Penyelesaian asas ini ialah tidak boleh diterima, kerana x 6 = –10 ≤ 0, dan mengikut syarat sekatan x 6 ≥ 0. Oleh itu, bukannya pembolehubah x 6 sebagai asas seseorang mesti mengambil pembolehubah lain dari kalangan yang bebas x 1 atau x 2 .
Kami akan menjalankan penyelesaian selanjutnya menggunakan jadual ringkas yang dipendekkan, mengisi baris jadual pertama dengan pekali sistem seperti berikut (Jadual 1):
Jadual 1
F-baris dipanggil indeks. Ia diisi dengan pekali fungsi objektif yang diambil dengan tanda yang bertentangan, kerana persamaan fungsi boleh diwakili dalam bentuk F = 0 – (– 4x 1 – 3x 2).
Dalam ruangan ahli percuma b i terdapat unsur negatif b 4 = –10, i.e. Penyelesaian sistem tidak sah. Untuk mendapatkan penyelesaian yang boleh dilaksanakan (pelan rujukan), elemen b 4 mesti dibuat bukan negatif.
pilih x 6 -rentetan dengan istilah bebas negatif. Baris ini mengandungi unsur negatif. Pilih mana-mana daripadanya, sebagai contoh, “–1” dalam x 1 -lajur, dan x Lajur 1 diambil sebagai lajur resolusi(ia akan menentukan bahawa pembolehubah x 1 akan bergerak daripada bebas kepada asas).
Kami membahagikan ahli percuma b i kepada elemen yang sepadan a ialah lajur resolusi, kami dapat hubungan penilaianΘ i= = (24, 15, 12, 10). Daripada jumlah ini, kami memilih positif terkecil (minΘ i=10), yang akan sepadan talian kebenaran. Rentetan pemboleh mentakrifkan pembolehubah x j, yang pada langkah seterusnya terkeluar dari dasar dan menjadi bebas. sebab tu x 6-baris ialah baris pemboleh, dan elemen “–1” ialah unsur permisif. Mari kita bulatkan. Pembolehubah x 1 dan x 6 ditukar.
Anggaran nisbah Θ i dalam setiap baris ditentukan mengikut peraturan:
1) Θ i= jika b i Dan a ialah mempunyai tanda yang berbeza;
2) Θ i= ∞, jika b i= 0 dan a ialah < 0;
3) Θ i= ∞, jika a ialah = 0;
4) Θ i= 0 jika b i= 0 dan a ialah > 0;
5)Θ i= jika b i Dan a ialah mempunyai tanda yang sama.
Kami melakukan langkah penyingkiran Jordan yang diubah suai (JEME) dengan elemen penyelesaian dan mengarang jadual baharu (Jadual 2) mengikut peraturan berikut:
1) sebagai ganti elemen penyelesaian (RE), nilai ditetapkan iaitu songsangnya, i.e. ;
2) unsur-unsur rentetan pemboleh dibahagikan kepada RE;
3) unsur-unsur lajur resolusi dibahagikan kepada RE dan tanda berubah;
4) elemen yang selebihnya ditemui mengikut peraturan segi empat tepat:
Dari meja 2 adalah jelas bahawa syarat percuma dalam b i-lajur bukan negatif, oleh itu, penyelesaian awal yang boleh dilaksanakan diperolehi - pelan rujukan pertama= (10; 0; 182; 5; 4; 0). Dalam kes ini, nilai fungsi F() = 40. Secara geometri ini sepadan dengan bahagian atas F(10; 0) poligon penyelesaian (Rajah 1).
jadual 2
2. Kami menyemak pelan untuk optimum. Pelan rujukan tidak optimum, kerana dalam F-garis mempunyai pekali negatif “–4”. Kami menambah baik rancangan itu.
3. Mencari pelan rujukan baharu
Kami memilih elemen yang membenarkan mengikut peraturan:
Kami memilih pekali negatif terkecil dalam F-baris “–4”, yang mentakrifkan lajur yang membolehkan – x 6; pembolehubah x 6 ditukar kepada asas;
Mencari hubungan Θ i, di antaranya kami memilih yang positif terkecil, yang sepadan dengan garis resolusi:
min Θ i = min(14, 5, 2, ∞) = 2, oleh itu, x 5-baris – membolehkan, berubah-ubah x 5 ditukar kepada percuma (pembolehubah x 5 dan x 6 ditukar).
Di persimpangan baris dan lajur penyelesaian terdapat elemen penyelesaian "2";
Kami menjalankan langkah SMGI dan membina jadual. 3 mengikut peraturan di atas dan kita mendapat pelan rujukan baru = (12; 0; 156; 3; 0; 2).
Jadual 3
4. Menyemak pelan rujukan baru untuk optimum
Pelan rujukan juga tidak optimum, kerana dalam F-garis mempunyai pekali negatif “–1”. Nilai fungsi F() = 48, yang secara geometri sepadan dengan bahagian atas E(12; 0) poligon penyelesaian (Rajah 1). Kami menambah baik rancangan itu.
5. Mencari pelan rujukan baharu
x Lajur 2 adalah permisif, kerana dalam F-garis, pekali negatif terkecil “–1” adalah dalam x 2-lajur (Δ 2 = –1). Kami dapati Θ terkecil i: min Θ i = min(≈ 9, 6, ∞, 24) = 6, oleh itu, x 4-baris – membenarkan. Elemen resolusi "1/2". Tukar pembolehubah x 2 dan x 4 . Kami menjalankan langkah SMGI dan membina jadual. 4, kita mendapat pelan rujukan baharu = (9; 6; 51; 0; 0; 5).
6. Menyemak pelan rujukan untuk optimum
DALAM F-line, semua pekali adalah bukan negatif, oleh itu, pelan rujukan adalah optimum. Secara geometri sepadan dengan titik D(9;6) (lihat Rajah 1). Pelan optimum memberikan nilai maksimum fungsi objektif 
c.u.
Berikut ialah penyelesaian manual (bukan applet) dua masalah menggunakan kaedah simplex (serupa dengan penyelesaian applet) dengan penjelasan terperinci untuk memahami algoritma untuk menyelesaikan masalah menggunakan kaedah simplex. Masalah pertama mengandungi tanda ketidaksamaan hanya "≤" (masalah dengan asas awal), yang kedua boleh mengandungi tanda "≥", "≤" atau "=" (masalah dengan asas buatan), ia diselesaikan secara berbeza.
Kaedah simplex, menyelesaikan masalah dengan asas awal
1)Kaedah simplex untuk masalah dengan asas awal (semua tanda kekangan ketidaksamaan " ≤ ").
Mari kita tulis masalah dalam berkanun bentuk, i.e. kami menulis semula sekatan ketidaksamaan dalam bentuk kesamaan, sambil menambah penyata imbangan pembolehubah:
Sistem ini adalah sistem dengan asas (asas s 1, s 2, s 3, setiap satu daripadanya dimasukkan ke dalam satu persamaan sahaja sistem dengan pekali 1), x 1 dan x 2 adalah pembolehubah bebas. Masalah yang hendak diselesaikan menggunakan kaedah simpleks mestilah mempunyai dua sifat berikut: - sistem kekangan mestilah sistem persamaan dengan asas; -istilah bebas semua persamaan dalam sistem mestilah bukan negatif.
Sistem yang terhasil ialah sistem dengan asas dan syarat percumanya adalah bukan negatif, jadi kita boleh memohon kaedah simplex. Mari kita cipta jadual simpleks pertama (Lelaran 0) untuk menyelesaikan masalah pada kaedah simplex, iaitu jadual pekali fungsi objektif dan sistem persamaan untuk pembolehubah yang sepadan. Di sini "BP" bermaksud lajur pembolehubah asas, "Penyelesaian" bermaksud lajur sebelah kanan persamaan sistem. Penyelesaiannya tidak optimum, kerana terdapat pekali negatif dalam baris-z.
lelaran kaedah simplex 0
|
Sikap |
|||||||
Untuk menambah baik penyelesaian, mari kita beralih ke lelaran seterusnya kaedah simplex, kita mendapat jadual simpleks berikut. Untuk melakukan ini, anda perlu memilih dayakan lajur, iaitu pembolehubah yang akan dimasukkan ke dalam asas pada lelaran seterusnya kaedah simpleks. Ia dipilih oleh pekali negatif mutlak terbesar dalam baris-z (dalam masalah maksimum) - dalam lelaran awal kaedah simplex ini ialah lajur x 2 (pekali -6).
Kemudian pilih dayakan rentetan, iaitu pembolehubah yang akan meninggalkan asas pada lelaran seterusnya kaedah simpleks. Ia dipilih mengikut nisbah terkecil lajur "Keputusan" kepada elemen positif yang sepadan bagi lajur resolusi (lajur "Nisbah") - dalam lelaran awal ini adalah baris s 3 (pekali 20).
Unsur permisif berada di persimpangan lajur penyelesaian dan baris penyelesaian, selnya diserlahkan dalam warna, ia bersamaan dengan 1. Oleh itu, pada lelaran seterusnya kaedah simpleks, pembolehubah x 2 akan menggantikan s 1 dalam asas. Ambil perhatian bahawa perhubungan tidak dicari dalam rentetan z; sempang “-” diletakkan di sana. Sekiranya terdapat hubungan minimum yang sama, maka mana-mana daripada mereka dipilih. Jika semua pekali dalam lajur resolusi kurang daripada atau sama dengan 0, maka penyelesaian kepada masalah itu adalah tidak terhingga.
Mari lengkapkan jadual berikut "Lelaran 1". Kami akan mendapatkannya daripada jadual "Lelaran 0". Matlamat transformasi selanjutnya adalah untuk menukar lajur resolusi x2 menjadi lajur unit (dengan satu dan bukannya elemen resolusi dan sifar bukannya elemen yang tinggal).
1) Kira baris x 2 jadual “Lelaran 1”. Mula-mula, kami membahagikan semua ahli baris penyelesaian s 3 jadual "Lelaran 0" dengan elemen penyelesaian (ia bersamaan dengan 1 dalam kes ini) jadual ini, kami mendapat baris x 2 dalam jadual "Lelaran 1". . Kerana elemen penyelesaian dalam kes ini adalah sama dengan 1, maka baris s 3 jadual "Lelaran 0" akan bertepatan dengan baris x 2 jadual "Lelaran 1". Baris x 2 daripada jadual Lelaran 1 kami mendapat 0 1 0 0 1 20, baris baki jadual Lelaran 1 akan diperoleh daripada baris ini dan baris jadual Lelaran 0 seperti berikut:
2) Pengiraan baris-z jadual "Lelaran 1". Sebagai ganti -6 dalam baris pertama (z-baris) dalam lajur x2 jadual Lelaran 0, harus ada 0 dalam baris pertama jadual Lelaran 1. Untuk melakukan ini, darabkan semua elemen baris x 2 jadual "Lelaran 1" 0 1 0 0 1 20 dengan 6, kita mendapat 0 6 0 0 6 120 dan tambahkan baris ini dengan baris pertama (z - baris) daripada jadual "Lelaran 0" -4 -6 0 0 0 0, kita dapat -4 0 0 0 6 120. Sifar 0 muncul dalam lajur x 2, matlamat tercapai. Elemen lajur resolusi x 2 diserlahkan dengan warna merah.
3) Pengiraan baris s 1 jadual "Lelaran 1". Sebagai ganti baris 1 dalam s 1 jadual "Lelaran 0" harus ada 0 dalam jadual "Lelaran 1". Untuk melakukan ini, darabkan semua elemen baris x 2 jadual "Lelaran 1" 0 1 0 0 1 20 dengan -1, dapatkan 0 -1 0 0 -1 -20 dan tambahkan baris ini dengan s 1 - baris bagi jadual "Lelaran 0" 2 1 1 0 0 64, kita mendapat baris 2 0 1 0 -1 44. Dalam lajur x 2 kita mendapat 0 yang diperlukan.
4) Kira baris s 2 jadual “Lelaran 1”. Di tempat 3 dalam s 2 baris jadual "Lelaran 0" harus ada 0 dalam jadual "Lelaran 1". Untuk melakukan ini, darabkan semua elemen baris x 2 jadual "Lelaran 1" 0 1 0 0 1 20 dengan -3, kita dapat 0 -3 0 0 -3 -60 dan tambah baris ini dengan s 1 - baris jadual "Lelaran 0" 1 3 0 1 0 72, kita mendapat baris 1 0 0 1 -3 12. Dalam lajur x 2, 0 yang diperlukan diperolehi. Lajur x 2 dalam jadual "Lelaran 1" telah menjadi satu unit, ia mengandungi satu 1 dan selebihnya 0.
Baris jadual "Lelaran 1" diperoleh mengikut peraturan berikut:
Baris baharu = Baris lama – (Pekali lajur resolusi baris lama)*(Baris resolusi baharu).
Sebagai contoh, untuk rentetan z kita ada:
Rentetan z lama (-4 -6 0 0 0 0) -(-6)*Rentetan penyelesaian baharu -(0 -6 0 0 -6 -120) = Rentetan z baharu (-4 0 0 0 6 120).
Untuk jadual berikut, pengiraan semula elemen jadual dilakukan dengan cara yang sama, jadi kami meninggalkannya.
lelaran kaedah simplex 1
|
Sikap |
|||||||
Menyelesaikan lajur x 1, menyelesaikan baris s 2, s 2 meninggalkan asas, x 1 memasuki asas. Dengan cara yang sama, kita memperoleh baki jadual simpleks sehingga kita memperoleh jadual dengan semua pekali positif dalam baris-z. Ini adalah tanda jadual yang optimum.
lelaran kaedah simplex 2
|
Sikap |
|||||||
Menyelesaikan lajur s 3, menyelesaikan baris s 1, s 1 meninggalkan asas, s 3 memasuki asas.
lelaran kaedah simplex 3
|
Sikap |
|||||||
Dalam baris-z, semua pekali adalah bukan negatif, oleh itu, penyelesaian optimum x 1 = 24, x 2 = 16, z max = 192 diperolehi.
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | St. ahli | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | St. ahli | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Tujuan perkhidmatan. Perkhidmatan ini direka untuk menyelesaikan masalah pengaturcaraan linear (LPP) dalam talian menggunakan kaedah simpleks dalam bentuk tatatanda berikut:
- dalam bentuk jadual simplex (kaedah transformasi Jordan); borang rakaman asas;
- kaedah simplex diubah suai; dalam bentuk lajur; dalam bentuk baris.
Arahan. Pilih bilangan pembolehubah dan bilangan baris (bilangan kekangan). Penyelesaian yang terhasil disimpan dalam fail Word dan Excel.
Dalam kes ini, jangan ambil kira sekatan seperti x i ≥ 0. Jika tiada sekatan dalam tugasan untuk beberapa x i, maka ZLP mesti ditukar kepada KZLP, atau menggunakan perkhidmatan ini. Apabila menyelesaikan, penggunaan ditentukan secara automatik M-kaedah(kaedah simplex dengan asas buatan) dan kaedah simpleks dua peringkat.Perkara berikut juga digunakan dengan kalkulator ini:
Kaedah grafik untuk menyelesaikan ZLP
Penyelesaian masalah pengangkutan
Menyelesaikan permainan matriks
Menggunakan perkhidmatan dalam talian, anda boleh menentukan harga permainan matriks (batas bawah dan atas), semak kehadiran titik pelana, cari penyelesaian kepada strategi campuran menggunakan kaedah berikut: minimax, kaedah simplex, grafik (geometrik ) kaedah, kaedah Brown.
Ekstrem bagi fungsi dua pembolehubah
Masalah pengaturcaraan dinamik
Agihkan 5 lot barangan homogen di antara tiga pasaran untuk memperoleh pendapatan maksimum daripada jualannya. Pendapatan daripada jualan dalam setiap pasaran G(X) bergantung pada bilangan kumpulan terjual produk X dan dibentangkan dalam jadual.
| Jumlah produk X (dalam lot) | Pendapatan G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Algoritma kaedah simplex termasuk langkah-langkah berikut:
- Merangka pelan asas pertama. Peralihan kepada bentuk kanonik masalah pengaturcaraan linear dengan memperkenalkan pembolehubah baki tambahan bukan negatif.
- Menyemak pelan untuk optimum. Sekiranya terdapat sekurang-kurangnya satu pekali garis indeks kurang daripada sifar, maka rancangan itu tidak optimum dan perlu diperbaiki.
- Menentukan lajur dan baris terkemuka. Daripada pekali negatif garis indeks, yang terbesar dalam nilai mutlak dipilih. Kemudian unsur-unsur lajur ahli bebas jadual simpleks dibahagikan kepada unsur-unsur tanda yang sama bagi lajur terkemuka.
- Membina pelan rujukan baharu. Peralihan kepada pelan baru dijalankan hasil daripada pengiraan semula jadual simplex menggunakan kaedah Jordan-Gauss.
Jika perlu untuk mencari ekstrem fungsi objektif, maka kita bercakap tentang mencari nilai minimum (F(x) → min, lihat contoh penyelesaian untuk meminimumkan fungsi) dan nilai maksimum ((F(x) ) → maks, lihat contoh penyelesaian untuk memaksimumkan fungsi)
Penyelesaian melampau dicapai pada sempadan kawasan penyelesaian yang boleh dilaksanakan pada salah satu bucu titik sudut poligon, atau pada segmen antara dua titik sudut bersebelahan.
Teorem Asas Pengaturcaraan Linear. Jika fungsi objektif ZLP mencapai nilai yang melampau pada satu titik dalam kawasan penyelesaian yang boleh dilaksanakan, maka ia mengambil nilai ini pada titik sudut. Jika fungsi objektif ZLP mencapai nilai melampau pada lebih daripada satu titik sudut, maka ia mengambil nilai yang sama pada mana-mana gabungan linear cembung titik ini.
Intipati kaedah simpleks. Pergerakan ke titik optimum dilakukan dengan bergerak dari satu titik sudut ke titik yang bersebelahan, yang membawa lebih dekat dan lebih pantas ke X opt. Skim sedemikian untuk menghitung mata, dipanggil kaedah simpleks, dicadangkan oleh R. Danzig.
Titik penjuru dicirikan oleh m pembolehubah asas, jadi peralihan dari satu titik penjuru ke titik jiran boleh dicapai dengan menukar hanya satu pembolehubah asas dalam asas kepada pembolehubah daripada bukan asas.
Pelaksanaan kaedah simplex, disebabkan oleh pelbagai ciri dan rumusan masalah LP, mempunyai pelbagai pengubahsuaian.
Pembinaan jadual simpleks diteruskan sehingga penyelesaian optimum diperolehi. Bagaimanakah anda boleh menggunakan jadual simpleks untuk menentukan bahawa penyelesaian kepada masalah pengaturcaraan linear adalah optimum?
Jika baris terakhir (nilai fungsi objektif) tidak mengandungi unsur negatif, oleh itu, ia akan mencari rancangan yang optimum.
Catatan 1. Jika salah satu pembolehubah asas adalah sama dengan sifar, maka titik ekstrem yang sepadan dengan penyelesaian asas tersebut adalah merosot. Degenerasi berlaku apabila terdapat kekaburan dalam pilihan garis panduan. Anda mungkin tidak menyedari kemerosotan masalah sama sekali jika anda memilih talian lain sebagai panduan. Sekiranya terdapat kekaburan, baris dengan indeks terendah harus dipilih untuk mengelakkan gelung.
Catatan 2. Biarkan pada satu titik ekstrem semua perbezaan ringkas adalah bukan negatif D k ³ 0 (k = 1..n+m), i.e. penyelesaian optimum diperolehi dan wujud A k - vektor bukan asas yang mana D k = 0. Kemudian maksimum dicapai sekurang-kurangnya pada dua titik, i.e. terdapat alternatif optimum. Jika kita memperkenalkan pembolehubah x k ini ke dalam asas, nilai fungsi objektif tidak akan berubah.
Catatan 3. Penyelesaian kepada masalah dwi adalah dalam jadual simpleks terakhir. Komponen m terakhir bagi vektor perbezaan simpleks (dalam lajur pembolehubah keseimbangan) adalah penyelesaian optimum kepada masalah dwi. Nilai fungsi objektif masalah langsung dan dua pada titik optimum bertepatan.
Catatan 4. Apabila menyelesaikan masalah pengecilan, vektor dengan perbezaan simpleks positif terbesar dimasukkan ke dalam asas. Seterusnya, algoritma yang sama digunakan seperti untuk masalah pemaksimuman.
Jika syarat "Adalah perlu bahan mentah jenis III dimakan sepenuhnya" dinyatakan, maka syarat yang sepadan ialah kesamarataan.
