Langkah 0. Peringkat persediaan.
Kami mengurangkan masalah LP kepada bentuk khas (15).
Langkah 1. Menyusun jadual simplex, sepadan dengan borang khas:
|
|
|
|||||
|
|
|
|
|
|||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
Ambil perhatian bahawa jadual ini sepadan dengan penyelesaian asas yang boleh diterima 
masalah (15). Nilai fungsi objektif pada penyelesaian ini 
Langkah 2. Semakan keoptimuman
Jika antara elemen baris indeks terdapat jadual simpleks 
tidak ada satu unsur positif pun 
, penyelesaian optimum kepada masalah LP didapati:. Algoritma ditamatkan.
Langkah 3. Semakan ketidakpastian
Jika antara 
ada unsur positif 
, dan dalam lajur yang sepadan 
tiada satu pun unsur positif 
, kemudian fungsi objektif L adalah tidak terhad dari bawah pada set yang boleh diterima. Dalam kes ini, tiada penyelesaian yang optimum. Algoritma ditamatkan.
Langkah 4. Memilih Lajur Utama q
Antara elemen 
pilih unsur positif maksimum 
.Kami mengisytiharkan lajur ini sebagai lajur terkemuka (permisif).
Langkah 5. Pemilihan baris utama hlm
Antara elemen positif lajur 
cari unsur 
, yang mana persamaan itu dipegang
.
Tali hlm Kami isytiharkan ia memimpin (membenarkan). unsur 
Kami isytiharkan sebagai ketua (membenarkan).
Langkah 6. Penukaran Jadual Simplex
Kami mencipta jadual simplex baharu di mana:
a) bukannya pembolehubah asas 
menulis 
, bukannya pembolehubah bukan asas 
menulis 
;
b) unsur utama digantikan dengan nilai songsang 
;
c) semua elemen lajur utama (kecuali 
) darab dengan 
;
d) semua elemen barisan hadapan (kecuali 
) darab dengan 
;
e) baki elemen jadual simpleks diubah mengikut skema "segi empat tepat" berikut.
Hasil darab tiga faktor ditolak daripada unsur:
yang pertama ialah elemen sepadan lajur utama;
yang kedua ialah elemen yang sepadan bagi barisan utama;
yang ketiga ialah timbal balik elemen utama 
.
Unsur yang diubah dan tiga faktor yang sepadan dengannya adalah tepat bucu "segi empat tepat".
Langkah 7 Peralihan kepada lelaran seterusnya dilakukan dengan kembali ke langkah 2.
2.3. Algoritma kaedah simplex untuk masalah maksimum
Algoritma kaedah simpleks untuk masalah maksimum berbeza daripada algoritma untuk masalah minimum hanya dalam tanda garis indeks pekali dalam fungsi objektif 
, iaitu:
Dalam langkah 2:
:
Dalam langkah 3
. Fungsi objektif tidak terhad dari atas pada set yang boleh diterima.
Dalam langkah 4:
.
2.4. Contoh penyelesaian masalah menggunakan kaedah simpleks
Selesaikan masalah yang ditulis dalam borang (15).
Mari buat jadual simplex:
|
|
|
|
|
|
| |||
|
|
|
Oleh kerana pekali garis fungsi objektif adalah bukan negatif, penyelesaian asas awal tidak optimum. Nilai fungsi objektif untuk asas ini L=0.
Pilih lajur utama - ini adalah lajur yang sepadan dengan pembolehubah 
.
Pilih baris utama. Untuk melakukan ini kita dapati 
. Oleh itu, garis pendahuluan sepadan dengan pembolehubah 
.
Kami mengubah jadual simplex dengan memperkenalkan pembolehubah 
ke dalam asas dan mengeluarkan pembolehubah 
daripada asas. Kami mendapat jadual:
|
|
|
|
|
|
|
| ||
|
|
|
Satu lelaran kaedah selesai. Mari kita beralih kepada lelaran baharu. Jadual yang terhasil tidak optimum. Penyelesaian asas yang sepadan dengan jadual mempunyai bentuk . Nilai fungsi objektif atas dasar ini L= -2.
Lajur utama di sini ialah lajur yang sepadan dengan pembolehubah 
. Garisan utama – garisan yang sepadan dengan pembolehubah 
. Selepas menjalankan transformasi, kami memperoleh jadual simpleks:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Satu lagi lelaran selesai. Mari kita beralih kepada lelaran baharu.
Barisan fungsi objektif tidak mengandungi nilai positif, yang bermaksud bahawa penyelesaian asas yang sepadan adalah optimum, dan algoritma ditamatkan.
Kaedah dwi simpleks adalah berdasarkan teori dualiti (lihat penyelesaian masalah dwi) dan digunakan untuk menyelesaikan masalah pengaturcaraan linear, terma bebas yang b i boleh mengambil sebarang nilai, dan sistem sekatan ditentukan oleh ketaksamaan makna "≤", “≥” atau kesamaan “=”.Tujuan perkhidmatan. Kalkulator dalam talian digunakan untuk menyelesaikan masalah pengaturcaraan linear P-kaedah dalam borang rakaman berikut: borang rakaman asas kaedah simpleks, dalam bentuk jadual simpleks, dalam kaedah simpleks diubah suai.
Arahan untuk menyelesaikan masalah kaedah dwi simpleks. Pilih bilangan pembolehubah dan bilangan baris (bilangan kekangan), klik Seterusnya. Penyelesaian yang terhasil disimpan dalam fail Word (lihat contoh penyelesaian menggunakan kaedah dwi simplex).
Pada masa yang sama, sekatan seperti x i ≥ 0 jangan ambil kira.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 |
Dalam kaedah P, pelan optimum diperoleh dengan bergerak di sepanjang pseudoplan. Pseudoplane- pelan di mana keadaan optimum dipenuhi, dan antara nilai pembolehubah asas x i terdapat nombor negatif. Algoritma untuk kaedah dwi simpleks merangkumi langkah-langkah berikut:
- Merangka pelan pseudo. Sistem kekangan masalah asal membawa kepada sistem ketidaksamaan dengan makna "≤".
- Menyemak pelan untuk optimum. Sekiranya keadaan optimum tidak dipenuhi dalam pelan rujukan yang dihasilkan, maka masalah diselesaikan menggunakan kaedah simpleks.
- Memilih baris dan lajur terkemuka. Antara nilai negatif pembolehubah asas, yang terbesar dalam nilai mutlak dipilih. Baris yang sepadan dengan nilai ini adalah yang terkemuka.
- Pengiraan pelan rujukan baharu. Pelan baru diperoleh dengan mengira semula jadual simpleks menggunakan kaedah Jordan-Gauss. Seterusnya, teruskan ke peringkat 2.
Contoh. Syarikat perlu mengeluarkan unit A1, unit A2, dan unit A3 mengikut pelan pengeluaran. Setiap jenis produk boleh dihasilkan pada dua mesin.
Bagaimana untuk mengagihkan kerja mesin supaya jumlah masa yang dibelanjakan untuk melaksanakan rancangan adalah minimum? Matriks kos dan sumber masa setiap mesin diberikan. Tulis model operasi yang sedang dikaji dalam bentuk yang membenarkan penggunaan kaedah-P.
Adalah diketahui bahawa kandungan n nutrien A, B dan C dalam diet harus sekurang-kurangnya m1, m2, m3 unit, masing-masing. Tiga jenis makanan mengandungi nutrien ini. Kandungan unit nutrien dalam satu kilogram setiap jenis produk ditunjukkan dalam jadual. tentukan diet harian yang menyediakan jumlah nutrien yang diperlukan pada kos yang minimum.
Tugasan: Selesaikan masalah menggunakan algoritma kaedah dwi simpleks.
Mari kita kurangkan sistem sekatan kepada sistem ketaksamaan makna ≤ dengan mendarab garis yang sepadan dengan (-1).
Mari kita tentukan nilai minimum bagi fungsi objektif F(X) = 4x 1 + 2x 2 + x 3 di bawah keadaan kekangan berikut.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Untuk membina pelan rujukan pertama, kami mengurangkan sistem ketaksamaan kepada sistem persamaan dengan memperkenalkan pembolehubah tambahan (peralihan kepada bentuk kanonik).
Dalam ketaksamaan makna pertama (≤), kami memperkenalkan pembolehubah asas x 4 . Dalam ketaksamaan makna kedua (≤), kami memperkenalkan pembolehubah asas x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
Matriks pekali A = a(ij) sistem persamaan ini mempunyai bentuk:
| A= |
|
x 4, x 5,
Dengan mengandaikan bahawa pembolehubah bebas adalah sama dengan sifar, kami memperoleh reka bentuk rujukan pertama:
X1 = (0,0,0,-10,8)
| Asas | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
Lelaran #1
Pelan 0 dalam jadual simpleks ialah pelan pseudo, jadi kami menentukan baris dan lajur utama.
Garis pendahuluan akan menjadi baris pertama, dan pembolehubah x 4 harus diterbitkan daripada asas.
3. Definisi pembolehubah asas baharu. Nilai minimum θ sepadan dengan lajur ke-2, i.e. pembolehubah x 2 mesti dimasukkan ke dalam asas.
| Asas | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
| θ | 0 | -4: (-1) = 4 | -2: (-1) = 2 | - | - | - |
4. Pengiraan semula jadual simpleks. Kami menjalankan transformasi jadual simpleks menggunakan kaedah Jordano-Gauss.
| Asas | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
Mari kita bentangkan pengiraan setiap elemen dalam bentuk jadual:
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| -10: -1 | -1: -1 | -1: -1 | 0: -1 | 1: -1 | 0: -1 |
| 8-(-10 1):-1 | 2-(-1 1):-1 | 1-(-1 1):-1 | -1-(0 1):-1 | 0-(1 1):-1 | 1-(0 1):-1 |
| 0-(-10 -2):-1 | -4-(-1 -2):-1 | -2-(-1 -2):-1 | -1-(0 -2):-1 | 0-(1 -2):-1 | 0-(0 -2):-1 |
Lelaran #2
1. Menyemak kriteria optimum.
Pelan 1 dalam jadual simpleks ialah pelan pseudo, jadi kami menentukan baris dan lajur utama.
2. Definisi pembolehubah bebas baharu.
Antara nilai negatif pembolehubah asas, kami memilih yang terbesar dalam nilai mutlak.
Baris kedua akan mendahului, dan pembolehubah x 5 harus diterbitkan daripada asas.
3. Definisi pembolehubah asas baharu. Nilai minimum θ sepadan dengan lajur ketiga, i.e. pembolehubah x 3 mesti dimasukkan ke dalam asas.
Di persimpangan baris dan lajur utama terdapat elemen penyelesaian (RE) bersamaan dengan (-1).
| Asas | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
| θ | 0 | - | - | -1: (-1) = 1 | - | - |
4. Pengiraan semula jadual simpleks. Kami melakukan transformasi.
| Asas | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| 10-(-2 0):-1 | 1-(1 0):-1 | 1-(0 0):-1 | 0-(-1 0):-1 | -1-(1 0):-1 | 0-(1 0):-1 |
| -2: -1 | 1: -1 | 0: -1 | -1: -1 | 1: -1 | 1: -1 |
| 20-(-2 -1):-1 | -2-(1 -1):-1 | 0-(0 -1):-1 | -1-(-1 -1):-1 | -2-(1 -1):-1 | 0-(1 -1):-1 |
Dalam lajur asas, semua elemen adalah positif. Mari kita beralih kepada algoritma utama kaedah simpleks.
Lelaran #3
1. Menyemak kriteria optimum.
Tiada nilai positif di antara nilai rentetan indeks. Oleh itu, jadual ini menentukan rancangan optimum untuk masalah tersebut.
| Asas | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
Pelan optimum boleh ditulis seperti berikut: x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22
Salah satu kaedah untuk menyelesaikan masalah pengoptimuman ( biasanya dikaitkan dengan mencari minimum atau maksimum) pengaturcaraan linear dipanggil . Kaedah simplex termasuk keseluruhan kumpulan algoritma dan kaedah untuk menyelesaikan masalah pengaturcaraan linear. Salah satu kaedah ini, yang melibatkan merekod data sumber dan mengira semula dalam jadual khas, dipanggil kaedah simplex jadual.
Mari kita pertimbangkan algoritma kaedah simplex jadual menggunakan contoh penyelesaian tugas pengeluaran, yang bermuara kepada mencari pelan pengeluaran yang memastikan keuntungan maksimum.
Masukkan data untuk masalah kaedah simpleks
Syarikat itu mengeluarkan 4 jenis produk, memprosesnya pada 3 mesin.
Piawaian masa (min./keping) untuk memproses produk pada mesin ditentukan oleh matriks A:
Dana masa operasi mesin (min.) dinyatakan dalam matriks B:
Keuntungan daripada penjualan setiap unit produk (RUB/keping) diberikan oleh matriks C:
Tujuan tugas pengeluaran
Buat rancangan pengeluaran yang akan memaksimumkan keuntungan perusahaan.
Menyelesaikan masalah menggunakan kaedah simplex jadual
(1) Mari kita nyatakan dengan X1, X2, X3, X4 bilangan produk yang dirancang bagi setiap jenis. Kemudian rancangan yang diingini: ( X1, X2, X3, X4)
(2) Mari kita tuliskan kekangan rancangan dalam bentuk sistem persamaan:
(3) Maka sasaran keuntungan ialah:
Maksudnya, keuntungan daripada memenuhi rancangan pengeluaran hendaklah maksimum.
(4) Untuk menyelesaikan masalah ekstrem bersyarat yang terhasil, kami menggantikan sistem ketaksamaan dengan sistem persamaan linear dengan memasukkan pembolehubah bukan negatif tambahan ke dalamnya ( X5, X6, X7).
(5) Mari kita terima perkara berikut pelan rujukan:
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Mari masukkan data ke dalam jadual simplex:
Dalam baris terakhir kita masukkan pekali fungsi objektif dan nilainya sendiri dengan tanda bertentangan;
(7) Pilih dalam baris terakhir terhebat (modulo) nombor negatif.
Jom kira b = N / Item_of_the_selected_column
Antara nilai terkira b yang kami pilih paling kurang.
Persilangan lajur dan baris yang dipilih akan memberikan kita elemen penyelesaian. Kami menukar asas kepada pembolehubah yang sepadan dengan elemen penyelesaian ( X5 hingga X1).
- Elemen penyelesaian itu sendiri bertukar kepada 1.
- Untuk elemen garis peleraian – a ij (*) = a ij / RE ( iaitu, kami membahagikan setiap elemen dengan nilai elemen penyelesaian dan mendapatkan data baharu).
- Untuk elemen lajur resolusi, ia hanya ditetapkan semula kepada sifar.
- Kami mengira semula baki elemen jadual menggunakan peraturan segi empat tepat.
a ij (*) = a ij – (A * B / RE)
Seperti yang anda lihat, kami mengambil sel semasa yang dikira semula dan sel dengan elemen penyelesaian. Mereka membentuk sudut bertentangan segi empat tepat. Seterusnya, kami mendarabkan nilai dari sel-sel 2 sudut lain pada segi empat tepat ini. Kerja ini ( A * B) bahagikan dengan unsur penyelesaian ( RE). Dan tolak daripada sel semasa yang dikira semula ( a ij) apa yang berlaku. Kami mendapat nilai baharu - a ij (*).
(9) Semak baris terakhir sekali lagi ( c) pada kehadiran nombor negatif. Jika mereka tidak ada, pelan optimum telah ditemui; kita beralih ke peringkat terakhir untuk menyelesaikan masalah. Jika ada, pelan itu belum optimum, dan jadual simpleks perlu dikira semula sekali lagi.
Oleh kerana kita sekali lagi mempunyai nombor negatif dalam baris terakhir, kita memulakan lelaran pengiraan baharu.
(10) Oleh kerana tiada unsur negatif dalam baris terakhir, ini bermakna kami telah menemui pelan pengeluaran yang optimum! Iaitu: kami akan menghasilkan produk yang telah berpindah ke lajur "Asas" - X1 dan X2. Kami mengetahui keuntungan daripada pengeluaran setiap unit keluaran ( matriks C). Ia kekal untuk mendarabkan volum pengeluaran produk 1 dan 2 yang dijumpai dengan keuntungan setiap 1 keping, kita mendapat yang terakhir ( maksimum! ) keuntungan untuk rancangan pengeluaran tertentu.
JAWAPAN:
X1 = 32 pcs., X2 = 20 pcs., X3 = 0 pcs., X4 = 0 pcs.
P = 48 * 32 + 33 * 20 = 2,196 gosok.
Galyautdinov R.R.
© Menyalin bahan dibenarkan hanya jika hiperpautan terus ke
. Algoritma kaedah simplex
Contoh 5.1. Selesaikan masalah pengaturcaraan linear berikut menggunakan kaedah simpleks:
Penyelesaian:
saya lelaran:
x3, x4, x5, x6 x1,x2. Mari kita nyatakan pembolehubah asas dari segi pembolehubah percuma:
Mari kita kurangkan fungsi objektif kepada bentuk berikut:
Berdasarkan masalah yang diperoleh, kami akan membentuk jadual simpleks awal:
Jadual 5.3
Jadual simplex asal
Hubungan Evaluatif |
||||
Menurut definisi penyelesaian asas, pembolehubah bebas adalah sama dengan sifar, dan nilai pembolehubah asas adalah sama dengan nilai sepadan nombor bebas, iaitu:
Peringkat 3: menyemak keserasian sistem sekatan PAP.
Pada lelaran ini (dalam Jadual 5.3), tanda ketidakkonsistenan sistem kekangan (tanda 1) tidak dikenal pasti (iaitu tidak ada garis dengan nombor bebas negatif (kecuali untuk garis fungsi objektif) yang tidak akan menjadi sekurang-kurangnya satu elemen negatif (iaitu pekali negatif untuk pembolehubah bebas)).
Pada lelaran ini (dalam Jadual 5.3), tanda ketakterbatasan fungsi objektif (tanda 2) tidak dikenal pasti (iaitu, tiada lajur dengan unsur negatif dalam baris fungsi objektif (kecuali lajur nombor bebas). ) di mana tidak akan ada sekurang-kurangnya satu unsur positif) .
Oleh kerana penyelesaian asas yang ditemui tidak mengandungi komponen negatif, ia boleh diterima.
Peringkat 6: semakan optimum.
Penyelesaian asas yang ditemui tidak optimum, kerana mengikut kriteria optimum (tanda 4) seharusnya tidak ada unsur negatif dalam baris fungsi objektif (nombor bebas baris ini tidak diambil kira apabila mempertimbangkan kriteria ini). Oleh itu, mengikut algoritma kaedah simplex, kita beralih ke peringkat 8.
Oleh kerana penyelesaian asas yang ditemui boleh diterima, kami akan mencari lajur penyelesaian mengikut skema berikut: kami menentukan lajur dengan unsur negatif dalam baris fungsi objektif (kecuali lajur nombor bebas). Menurut Jadual 5.3, terdapat dua lajur tersebut: lajur “ x1"dan lajur" x2" Daripada lajur sedemikian, lajur yang mengandungi elemen terkecil dalam baris fungsi sasaran dipilih. Dia akan menjadi yang permisif. Kolum " x2" mengandungi unsur terkecil (–3) berbanding lajur " x1
Untuk menentukan garis penyelesaian, kita dapati nisbah anggaran positif nombor bebas kepada unsur lajur penyelesaian; garisan yang sepadan dengan nisbah penilaian positif terkecil diterima sebagai diselesaikan.
Jadual 5.4
Jadual simplex asal
Dalam Jadual 5.4, hubungan penilaian positif terkecil sepadan dengan garis " x5", oleh itu, ia akan menjadi permisif.
Elemen yang terletak di persimpangan lajur pemboleh dan baris pemboleh diterima sebagai pemboleh. Dalam contoh kami, ini ialah elemen yang terletak di persimpangan garis " x5"dan lajur" x2».
Elemen penyelesaian menunjukkan satu asas dan satu pembolehubah bebas yang mesti ditukar dalam jadual simpleks untuk beralih kepada penyelesaian asas "diperbaiki" baharu. Dalam kes ini, ini adalah pembolehubah x5 Dan x2, dalam jadual simplex baharu (Jadual 5.5) kami menukarnya.
9.1. Transformasi unsur penyelesaian.
Elemen resolusi Jadual 5.4 ditukar seperti berikut:
Kami memasukkan hasil yang terhasil ke dalam sel yang serupa dalam Jadual 5.5.
9.2. Penukaran rentetan resolusi.
Kami membahagikan elemen baris penyelesaian jadual 5.4 dengan elemen penyelesaian jadual simpleks ini, hasilnya sesuai dengan sel yang serupa dalam jadual simpleks baharu (jadual 5.5). Transformasi elemen rentetan resolusi diberikan dalam Jadual 5.5.
9.3. Penukaran lajur resolusi.
Kami membahagikan elemen lajur resolusi Jadual 5.4 dengan elemen resolusi jadual ringkas ini, dan hasilnya diambil dengan tanda yang bertentangan. Keputusan yang diperolehi dimuatkan ke dalam sel yang serupa pada jadual simpleks baharu (Jadual 5.5). Transformasi unsur-unsur lajur resolusi diberikan dalam Jadual 5.5.
9.4. Transformasi unsur-unsur baki jadual simpleks.
Transformasi unsur-unsur baki jadual simpleks (iaitu, elemen yang tidak terletak dalam baris penyelesaian dan lajur penyelesaian) dijalankan mengikut peraturan "segi empat tepat".
Sebagai contoh, pertimbangkan untuk menukar elemen yang terletak di persimpangan garis " x3" dan lajur "", kami akan menyatakannya secara bersyarat " x3" Dalam Jadual 5.4, kita secara mental melukis segi empat tepat, satu bucunya terletak di dalam sel yang nilainya kita ubah (iaitu dalam sel " x3"), dan satu lagi (bucu pepenjuru) berada dalam sel dengan elemen penyelesaian. Dua bucu yang lain (pada pepenjuru kedua) ditentukan secara unik. Kemudian nilai berubah sel " x3" akan sama dengan nilai sebelumnya sel ini tolak pecahan, dalam penyebutnya ialah elemen penyelesaian (daripada Jadual 5.4), dan dalam pengangka ialah hasil darab dua bucu lain yang tidak digunakan, iaitu:
« x3»: .
Nilai sel lain ditukar sama:
« x3 x1»: ;
« x4»: 
;
« x4 x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
Hasil daripada transformasi ini, satu jadual simpleks baharu telah diperolehi (Jadual 5.5).
II lelaran:
Peringkat 1: merangka jadual simpleks.
Jadual 5.5
Jadual simplexII lelaran
Dianggarkan perhubungan |
||||
| ||||
|
|
Peringkat 2: penentuan penyelesaian asas.
Hasil daripada penjelmaan simpleks, penyelesaian asas baru diperolehi (Jadual 5.5):
Seperti yang anda lihat, dengan penyelesaian asas ini nilai fungsi objektif = 15, yang lebih besar daripada penyelesaian asas sebelumnya.
Ketidakkonsistenan sistem sekatan mengikut ciri 1 dalam Jadual 5.5 belum dikenal pasti.
Peringkat 4: menyemak sempadan fungsi objektif.
Ketakterbatasan fungsi objektif mengikut kriteria 2 dalam Jadual 5.5 tidak didedahkan.
Peringkat 5: menyemak kebolehterimaan penyelesaian asas yang ditemui.
Penyelesaian asas yang ditemui mengikut kriteria 4 tidak optimum, kerana garis fungsi objektif jadual simpleks (Jadual 5.5) mengandungi unsur negatif: –2 (nombor bebas baris ini tidak diambil kira apabila mempertimbangkan ini ciri). Oleh itu, kita beralih ke peringkat 8.
Peringkat 8: penentuan elemen penyelesaian.
8.1. Definisi lajur resolusi.
Penyelesaian asas yang ditemui boleh diterima; kami menentukan lajur dengan unsur negatif dalam baris fungsi objektif (kecuali lajur nombor bebas). Menurut Jadual 5.5, terdapat hanya satu lajur sedemikian: “ x1" Oleh itu, kami menerimanya seperti yang dibenarkan.
8.2. Definisi rentetan dayakan.
Mengikut nilai yang diperolehi hubungan penilaian positif dalam Jadual 5.6, minimum ialah hubungan yang sepadan dengan garis " x3" Oleh itu, kami menerimanya seperti yang dibenarkan.
Jadual 5.6
Jadual simplexII lelaran
Dianggarkan perhubungan |
||||
3/1=3 – min |
||||
Peringkat 9: penjelmaan jadual simpleks.
Transformasi jadual simplex (Jadual 5.6) dilakukan dengan cara yang sama seperti dalam lelaran sebelumnya. Keputusan penjelmaan unsur jadual simpleks diberikan dalam Jadual 5.7.
III lelaran
Berdasarkan hasil transformasi simpleks lelaran sebelumnya, kami menyusun jadual simpleks baharu:
Jadual 5.7
Jadual simplexIII lelaran
Dianggarkan perhubungan |
||||
| ||||
|
|
Peringkat 2: penentuan penyelesaian asas.
Hasil daripada penjelmaan simpleks, penyelesaian asas baru diperolehi (Jadual 5.7):
Peringkat 3: menyemak keserasian sistem sekatan.
Ketidakkonsistenan sistem sekatan mengikut ciri 1 dalam Jadual 5.7 belum dikenal pasti.
Peringkat 4: menyemak sempadan fungsi objektif.
Ketakterbatasan fungsi objektif mengikut kriteria 2 dalam Jadual 5.7 tidak didedahkan.
Peringkat 5: menyemak kebolehterimaan penyelesaian asas yang ditemui.
Penyelesaian asas yang ditemui mengikut kriteria 3 boleh diterima, kerana ia tidak mengandungi komponen negatif.
Peringkat 6: menyemak optimum penyelesaian asas yang ditemui.
Penyelesaian asas yang ditemui mengikut kriteria 4 tidak optimum, kerana garis fungsi objektif jadual simpleks (Jadual 5.7) mengandungi unsur negatif: –3 (nombor bebas baris ini tidak diambil kira apabila mempertimbangkan ini ciri). Oleh itu, kita beralih ke peringkat 8.
Peringkat 8: penentuan elemen penyelesaian.
8.1. Definisi lajur resolusi.
Penyelesaian asas yang ditemui boleh diterima; kami menentukan lajur dengan unsur negatif dalam baris fungsi objektif (kecuali lajur nombor bebas). Menurut Jadual 5.7, terdapat hanya satu lajur sedemikian: “ x5" Oleh itu, kami menerimanya seperti yang dibenarkan.
8.2. Definisi rentetan dayakan.
Menurut nilai yang diperolehi hubungan penilaian positif dalam Jadual 5.8, minimum ialah hubungan yang sepadan dengan garis " x4" Oleh itu, kami menerimanya seperti yang dibenarkan.
Jadual 5.8
Jadual simplexIII lelaran
Dianggarkan perhubungan |
||||
5/5=1 – min |
||||
Peringkat 9: penjelmaan jadual simpleks.
Transformasi jadual simpleks (Jadual 5.8) dilakukan dengan cara yang sama seperti dalam lelaran sebelumnya. Keputusan penjelmaan unsur jadual simpleks diberikan dalam Jadual 5.9.
IV lelaran
Peringkat 1: pembinaan jadual simpleks baharu.
Berdasarkan hasil transformasi simpleks lelaran sebelumnya, kami menyusun jadual simpleks baharu:
Jadual 5.9
Jadual simplexIV lelaran
Dianggarkan perhubungan |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
Peringkat 2: penentuan penyelesaian asas.
Hasil daripada penjelmaan simpleks, penyelesaian asas baharu telah diperoleh; mengikut Jadual 5.9, penyelesaiannya adalah seperti berikut:
Peringkat 3: menyemak keserasian sistem sekatan.
Ketidakkonsistenan sistem sekatan mengikut ciri 1 dalam Jadual 5.9 belum dikenal pasti.
Peringkat 4: menyemak sempadan fungsi objektif.
Ketakterbatasan fungsi objektif mengikut kriteria 2 dalam Jadual 5.9 tidak didedahkan.
Peringkat 5: menyemak kebolehterimaan penyelesaian asas yang ditemui.
Penyelesaian asas yang ditemui mengikut kriteria 3 boleh diterima, kerana ia tidak mengandungi komponen negatif.
Peringkat 6: menyemak optimum penyelesaian asas yang ditemui.
Penyelesaian asas yang ditemui mengikut ciri 4 adalah optimum, kerana tiada unsur negatif dalam baris fungsi objektif jadual simpleks (Jadual 5.9) (nombor bebas baris ini tidak diambil kira apabila mempertimbangkan ciri ini) .
Peringkat 7: menyemak alternatif penyelesaian.
Penyelesaian yang ditemui adalah unik, kerana tiada unsur sifar dalam baris fungsi objektif (Jadual 5.9) (nombor bebas baris ini tidak diambil kira apabila mempertimbangkan ciri ini).
Jawapan: nilai optimum fungsi objektif masalah yang sedang dipertimbangkan =24, yang dicapai pada.
Contoh 5.2. Selesaikan masalah pengaturcaraan linear di atas dengan syarat fungsi objektif diminimumkan:
Penyelesaian:
saya lelaran:
Peringkat 1: pembentukan jadual simpleks awal.
Masalah pengaturcaraan linear asal diberikan dalam bentuk piawai. Marilah kita membawanya ke bentuk kanonik dengan memperkenalkan pembolehubah bukan negatif tambahan ke dalam setiap kekangan ketidaksamaan, i.e.
Dalam sistem persamaan yang terhasil, kami mengambil pembolehubah (asas) yang dibenarkan x3, x4, x5, x6, maka pembolehubah bebas ialah x1,x2. Mari kita nyatakan pembolehubah asas dari segi pembolehubah percuma.
Mari kita pertimbangkan kaedah simplex untuk menyelesaikan masalah pengaturcaraan linear (LP). Ia adalah berdasarkan peralihan daripada satu pelan rujukan kepada yang lain, di mana nilai fungsi objektif meningkat.
Algoritma kaedah simplex adalah seperti berikut:
- Kami mengubah masalah asal kepada bentuk kanonik dengan memperkenalkan pembolehubah tambahan. Untuk ketaksamaan dalam bentuk ≤, pembolehubah tambahan diperkenalkan dengan tanda (+), tetapi jika dalam bentuk ≥, maka dengan tanda (-). Pembolehubah tambahan dimasukkan ke dalam fungsi objektif dengan tanda sepadan dengan pekali sama dengan 0 , kerana fungsi sasaran tidak seharusnya mengubah makna ekonominya.
- Vektor ditulis P i daripada pekali pembolehubah dan lajur sebutan bebas. Tindakan ini menentukan bilangan vektor unit. Peraturannya ialah perlu ada vektor unit sebanyak mana terdapat ketaksamaan dalam sistem kekangan.
- Selepas ini, data sumber dimasukkan ke dalam jadual simplex. Vektor unit dimasukkan ke dalam asas, dan dengan mengecualikannya daripada asas, penyelesaian optimum ditemui. Pekali fungsi objektif ditulis dengan tanda bertentangan.
- Tanda optimum untuk masalah LP ialah penyelesaian adalah optimum jika dalam f– dalam baris semua pekali adalah positif. Peraturan untuk mencari lajur yang membolehkan - dilihat f– rentetan dan antara unsur negatifnya yang terkecil dipilih. vektor P i kandungannya menjadi permisif. Peraturan untuk memilih elemen penyelesaian - nisbah unsur positif lajur penyelesaian kepada unsur vektor disusun P 0 dan nombor yang memberikan nisbah terkecil menjadi elemen penyelesaian yang mana jadual simpleks akan dikira semula. Baris yang mengandungi elemen ini dipanggil baris membolehkan. Sekiranya tiada unsur positif dalam lajur resolusi, maka masalah itu tiada penyelesaian. Selepas menentukan elemen penyelesaian, mereka meneruskan pengiraan semula jadual simpleks baharu.
- Peraturan untuk mengisi jadual simpleks baharu. Unit diletakkan di tempat elemen penyelesaian, dan elemen lain diandaikan sama 0 . Vektor penyelesaian ditambahkan pada asas, dari mana vektor sifar yang sepadan dikecualikan, dan vektor asas yang selebihnya ditulis tanpa perubahan. Unsur-unsur garis resolusi dibahagikan dengan elemen resolusi, dan unsur-unsur yang selebihnya dikira semula mengikut peraturan segi empat tepat.
- Ini dilakukan sehingga f– semua elemen rentetan tidak akan menjadi positif.
Mari kita pertimbangkan untuk menyelesaikan masalah menggunakan algoritma yang dibincangkan di atas.
Diberi:
Kami membawa masalah kepada bentuk kanonik:
Kami menyusun vektor:
Isikan jadual simplex:
:
Mari kita mengira semula elemen pertama vektor P 0, yang mana kita membuat segi empat tepat nombor: dan kita mendapat: 
.
Kami melakukan pengiraan yang serupa untuk semua elemen lain jadual simpleks:
Dalam rancangan yang diterima f– garis mengandungi satu unsur negatif – (-5/3), vektor P 1. Ia mengandungi dalam lajurnya satu elemen positif, yang akan menjadi elemen pemboleh. Mari kita mengira semula jadual mengenai elemen ini:
Tiada unsur negatif dalam f– garis bermaksud dijumpai rancangan yang optimum:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).
- Ashmanov S. A. Pengaturcaraan Linear, M: Nauka, 1998,
- Ventzel E.S. Penyelidikan Operasi, M: Radio Soviet, 2001,
- Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Pengaturcaraan matematik, M: Sekolah Tinggi, 1986.
Penyelesaian Pengaturcaraan Linear Tersuai
Anda boleh memesan sebarang tugasan dalam disiplin ini di laman web kami. Anda boleh melampirkan fail dan menentukan tarikh akhir di
