Cari maksimum bagi fungsi objektif. Cari ekstrem fungsi dengan kaedah grafik

Cari kaedah grafik maksimum Fungsi objektif

F= 2x 1 + 3x 2 ® maks

Dengan sekatan

Penyelesaian dengan menggunakan Jadual Excel

Mari mula-mula bina pada helaian penyelesaian excel sistem ketidaksamaan.

Pertimbangkan ketidaksamaan pertama.

Mari kita bina garis sempadan daripada dua titik. Nyatakan garis dengan (L1) (atau Baris1). Koordinat X 2 kita mengira mengikut formula:

Untuk membina, pilih plot berselerak

Memilih data untuk garis lurus

Tukar nama baris:

Pilih susun atur carta. Tukar nama paksi koordinat:

Garis lurus (L1) pada carta:

Penyelesaian kepada ketidaksamaan yang ketat boleh didapati menggunakan satu titik ujian yang tidak tergolong dalam garisan (L1). Contohnya, menggunakan titik (0; 0)W(L1).

0+3×0< 18 или 0 < 18 .

Ketaksamaan adalah benar, oleh itu, penyelesaian kepada ketaksamaan (1) akan menjadi separuh satah di mana titik ujian terletak (dalam rajah di bawah garis L1).

Kemudian kita selesaikan ketaksamaan (2) .

Mari kita bina garis sempadan 2 daripada dua titik. Nyatakan garis dengan (L2).

Garis lurus (L2) pada carta:

Penyelesaian ketaksamaan ketat 2 boleh didapati menggunakan satu-satunya titik ujian yang tidak tergolong dalam garisan (L2). Contohnya, menggunakan titik (0; 0)W(L2).

Menggantikan koordinat titik (0; 0), kita memperoleh ketaksamaan

2×0 + 0< 16 или 0 < 16 .

Ketaksamaan adalah benar, oleh itu, penyelesaian kepada ketaksamaan (2) ialah separuh satah di mana titik ujian terletak (dalam rajah di bawah, garis L2).

Kemudian kita selesaikan ketaksamaan (3) .

Mari kita bina garis sempadan daripada dua titik. Nyatakan garis dengan (L3).

Garis lurus (L3) pada carta:

Penyelesaian ketaksamaan ketat 2 boleh didapati menggunakan satu-satunya titik ujian yang tidak tergolong dalam garisan (L3). Contohnya, menggunakan titik (0; 0)W(L3).

Menggantikan koordinat titik (0; 0), kita memperoleh ketaksamaan

Ketaksamaan adalah benar, oleh itu, penyelesaian kepada ketaksamaan (3) ialah separuh satah di mana titik ujian terletak (dalam rajah di bawah, garis L3).

Kemudian kita selesaikan ketaksamaan (4) .

Mari kita bina garis sempadan daripada dua titik. Nyatakan garis dengan (L4).

Tambahkan data ke helaian excel

Garis lurus (L4) pada carta:

Penyelesaian Ketaksamaan Tegas 3 X 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

Menggantikan koordinat titik (0; 0), kita memperoleh ketaksamaan

Ketaksamaan adalah benar, oleh itu, penyelesaian kepada ketaksamaan (4) ialah separuh satah di mana titik ujian terletak (di sebelah kiri garisan L4 dalam rajah).

Dengan menyelesaikan dua ketaksamaan (5) dan (6)

ialah suku pertama yang dibatasi oleh garis koordinat dan .

Sistem ketidaksamaan diselesaikan. Dengan menyelesaikan sistem ketaksamaan (1) - (6) dalam contoh ini ialah poligon cembung di sudut kiri bawah rajah, dibatasi oleh garis L1, L2, L3, L4 dan garis koordinat dan . Anda boleh memastikan bahawa poligon dipilih dengan betul dengan menggantikan titik ujian, contohnya (1; 1) ke dalam setiap ketaksamaan sistem asal. Menggantikan titik (1; 1), kita memperoleh bahawa semua ketaksamaan, termasuk kekangan semula jadi, adalah benar.

Pertimbangkan sekarang fungsi objektif

F= 2x 1 + 3x 2 .

Mari bina garis tahap untuk nilai fungsi F=0 Dan F=12 (nilai berangka dipilih sewenang-wenangnya). Tambahkan data ke helaian excel

Garis tahap pada carta:

Mari kita bina vektor arah (atau kecerunan) (2; 3). Koordinat vektor bertepatan dengan pekali fungsi objektif F.

Mari kita bina pada satah set penyelesaian sistem yang boleh diterima ketaksamaan linear dan mencari secara geometri nilai minimum fungsi sasaran.

Kami membina dalam sistem koordinat x 1 oh 2 baris

Kami mendapati separuh satah ditentukan oleh sistem. Memandangkan ketaksamaan sistem dipenuhi untuk mana-mana titik dari separuh satah yang sepadan, ia memadai untuk menyemaknya untuk mana-mana satu titik. Kami menggunakan titik (0;0). Marilah kita menggantikan koordinatnya ke dalam ketaksamaan pertama sistem. Kerana , maka ketaksamaan mentakrifkan separuh satah yang tidak mengandungi titik (0;0). Begitu juga, kami mentakrifkan separuh satah yang tinggal. Kami mendapati set penyelesaian yang boleh dilaksanakan sebagai bahagian umum daripada separuh satah yang terhasil ialah kawasan berlorek.

Kami membina vektor dan garis tahap sifar berserenjang dengannya.

Dengan menggerakkan garis (5) ke arah vektor, kita melihat bahawa titik maksimum rantau akan berada di titik A persilangan garis (3) dan garis (2). Kami mencari penyelesaian sistem persamaan:

Jadi, kami mendapat titik (13;11) dan.

Dengan menggerakkan garis (5) ke arah vektor, kita melihat bahawa titik minimum rantau akan berada di titik B persimpangan garis (1) dan garis (4). Kami mencari penyelesaian sistem persamaan:

Jadi, kami mendapat mata (6;6) dan.

2. Sebuah syarikat perabot menghasilkan gabungan kabinet dan meja komputer. Pengeluaran mereka dihadkan oleh ketersediaan bahan mentah (papan berkualiti tinggi, kelengkapan) dan masa operasi mesin yang memprosesnya. Setiap kabinet memerlukan 5 m2 papan, untuk meja - 2 m2. Kelengkapan untuk $10 dibelanjakan untuk satu kabinet, dan $8 untuk satu meja. Syarikat boleh menerima daripada pembekalnya sehingga 600 m2 papan setiap bulan dan aksesori untuk $2000. Untuk setiap kabinet, 7 jam kerja mesin diperlukan, untuk meja - 3 jam. Ia adalah mungkin untuk menggunakan hanya 840 jam operasi mesin sebulan.

Berapakah bilangan gabungan kabinet dan meja komputer yang perlu dikeluarkan oleh firma setiap bulan untuk memaksimumkan keuntungan jika satu kabinet membawa masuk $100 dan setiap meja menghasilkan $50?

1. Karang model matematik masalah dan menyelesaikannya menggunakan kaedah simpleks.
2. Membuat model matematik dua tugas dan tuliskan penyelesaiannya berdasarkan penyelesaian yang asal.
3. Tentukan tahap kekurangan sumber yang digunakan dan mewajarkan keuntungan pelan optimum.
4. Terokai kemungkinan untuk meningkatkan lagi output, bergantung pada penggunaan setiap jenis sumber.
5. Menilai kebolehlaksanaan untuk memperkenalkan jenis produk baharu - rak buku, jika 1 m 2 papan dan aksesori untuk $ 5 dibelanjakan untuk pembuatan satu rak, dan 0.25 jam operasi mesin diperlukan dan keuntungan daripada penjualan satu rak ialah $ 20.
1. Mari bina model matematik untuk masalah ini:

Nyatakan dengan x 1 - isipadu pengeluaran kabinet, dan x 2 - isipadu pengeluaran jadual. Mari kita susun sistem kekangan dan fungsi matlamat:

Kami menyelesaikan masalah menggunakan kaedah simplex. Mari kita tulis dalam bentuk kanonik:

Mari tulis data tugasan dalam bentuk jadual:

Jadual 1

Kerana kini semuanya delta Di atas sifar, maka peningkatan selanjutnya dalam nilai fungsi matlamat f adalah mustahil dan kami telah memperoleh pelan yang optimum.

pengenalan

Peringkat moden pembangunan manusia berbeza kerana abad tenaga digantikan oleh zaman informatika. Terdapat pengenalan intensif teknologi baharu dalam semua bidang Aktiviti manusia. Meningkat masalah sebenar peralihan kepada masyarakat maklumat, yang mana pembangunan pendidikan harus menjadi keutamaan. Struktur ilmu dalam masyarakat juga berubah. Semua nilai yang lebih besar Untuk kehidupan praktikal memperoleh pengetahuan asas yang menyumbang kepada perkembangan kreatif personaliti. Konstruktif pengetahuan yang diperolehi, keupayaan untuk menyusunnya mengikut matlamat juga penting. Berdasarkan pengetahuan, baru sumber maklumat masyarakat. Pembentukan dan pemerolehan pengetahuan baru harus berdasarkan metodologi yang ketat pendekatan sistem, di mana tempat yang berasingan diduduki oleh pendekatan model. Kemungkinan pendekatan pemodelan adalah sangat pelbagai dari segi model formal yang digunakan dan dalam cara melaksanakan kaedah pemodelan. Permodelan fizikal memungkinkan untuk mendapatkan hasil yang boleh dipercayai untuk sistem yang agak mudah.

Pada masa ini, adalah mustahil untuk menamakan kawasan aktiviti manusia di mana, pada satu tahap atau yang lain, kaedah pemodelan tidak akan digunakan. Ini benar terutamanya dalam bidang pengurusan. pelbagai sistem, di mana yang utama adalah proses membuat keputusan berdasarkan maklumat yang diterima.

1. Pernyataan masalah

fungsi objektif minimum

Menyelesaikan masalah mencari minimum fungsi objektif untuk sistem kekangan yang ditentukan oleh poligon keputusan mengikut pilihan No. 16 tugasan. Poligon keputusan ditunjukkan dalam Rajah 1:

Rajah 1 - Poligon penyelesaian masalah

Sistem kekangan dan fungsi objektif masalah dibentangkan di bawah:

Ia adalah perlu untuk menyelesaikan masalah menggunakan kaedah berikut:

Kaedah grafik untuk menyelesaikan masalah LP;

Kaedah algebra untuk menyelesaikan masalah LP;

Kaedah simplex untuk menyelesaikan masalah LP;

Kaedah untuk mencari penyelesaian yang boleh dilaksanakan kepada masalah LP;

Menyelesaikan masalah dwi LP;

Kaedah "cawangan dan sempadan" untuk menyelesaikan masalah LP integer;

Kaedah Gomory untuk menyelesaikan masalah LP integer;

Kaedah Balash untuk menyelesaikan masalah LP Boolean.

Bandingkan keputusan penyelesaian dengan kaedah yang berbeza untuk membuat kesimpulan yang sesuai tentang kerja.

2. Penyelesaian grafik masalah pengaturcaraan linear

Kaedah grafik untuk menyelesaikan masalah pengaturcaraan linear digunakan dalam kes di mana bilangan yang tidak diketahui tidak melebihi tiga. Mudah untuk penyelidikan kualitatif sifat penyelesaian dan digunakan bersama dengan kaedah lain (algebra, cabang dan terikat, dsb.). Idea kaedah adalah berdasarkan penyelesaian grafik sistem ketaksamaan linear.

nasi. 2 Penyelesaian grafik masalah LP

Titik rendah

Persamaan garis lurus yang melalui dua titik A1 dan A2:

AB: (0;1); (3;3)

Matahari: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

dengan sekatan:

Menyelesaikan masalah pengaturcaraan linear dengan kaedah algebra simplex

Aplikasi kaedah algebra untuk menyelesaikan masalah memerlukan generalisasi perwakilan masalah LP. Sistem asal kekangan yang diberikan dalam bentuk ketaksamaan ditukar kepada tatatanda piawai apabila kekangan diberikan dalam bentuk kesamaan. Menukar sistem kekangan kepada pandangan standard merangkumi langkah-langkah berikut:

Ubah ketaksamaan sedemikian rupa sehingga pembolehubah dan ahli bebas berada di sebelah kiri, dan 0 di sebelah kanan, i.e. bahawa bahagian kiri lebih besar daripada atau sama dengan sifar;

Memperkenalkan pembolehubah tambahan, bilangan yang sama dengan bilangan ketaksamaan dalam sistem sekatan;

Memasuki sekatan tambahan pada bukan-negativiti pembolehubah yang ditambah, gantikan tanda-tanda ketaksamaan dengan tanda-tanda kesamaan yang ketat.

Apabila menyelesaikan masalah LP kaedah algebra syarat ditambah: fungsi objektif mesti cenderung kepada minimum. Jika syarat ini tidak dipenuhi, adalah perlu untuk mengubah fungsi objektif dengan sewajarnya (darab dengan -1) dan menyelesaikan masalah pengecilan. Selepas penyelesaian ditemui, gantikan nilai pembolehubah dalam fungsi asal dan hitung nilainya.

Penyelesaian masalah menggunakan kaedah algebra dianggap optimum apabila nilai semua pembolehubah asas adalah bukan negatif, dan pekali pembolehubah bebas dalam persamaan fungsi objektif juga bukan negatif. Jika syarat-syarat ini tidak dipenuhi, adalah perlu untuk mengubah sistem ketaksamaan, menyatakan beberapa pembolehubah dari segi yang lain (menukar pembolehubah bebas dan asas) untuk mencapai sekatan di atas. Nilai semua pembolehubah bebas diandaikan sifar.

Kaedah algebra untuk menyelesaikan masalah pengaturcaraan linear adalah salah satu yang paling banyak kaedah yang berkesan apabila menyelesaikan masalah dimensi kecil secara manual. tidak memerlukan sebilangan besar pengiraan aritmetik. Pelaksanaan mesin kaedah ini lebih rumit daripada, sebagai contoh, untuk kaedah simplex, kerana algoritma untuk menyelesaikan kaedah algebra adalah sedikit sebanyak heuristik dan keberkesanan penyelesaian sebahagian besarnya bergantung kepada pengalaman peribadi.

pembolehubah bebas

lorong St - Tambah. kit

Syarat bukan negatif dipenuhi, oleh itu, kami telah menemui penyelesaian yang optimum.

3. Menyelesaikan masalah pengaturcaraan linear menggunakan jadual simpleks

Penyelesaian: Mari kita bawa masalah kepada bentuk piawai untuk menyelesaikan menggunakan jadual simpleks.

Kami mengurangkan semua persamaan sistem kepada bentuk:

Kami membina jadual simplex:

DALAM bucu atas untuk setiap sel jadual kita masukkan pekali daripada sistem persamaan;

Kami memilih elemen positif maksimum dalam baris F, kecuali untuk ini akan menjadi lajur umum;

Untuk mencari elemen umum, kami membina hubungan untuk semua yang positif. 3/3; 9/1;- nisbah minimum dalam baris x3. Oleh itu - rentetan am dan =3 - elemen umum.

Kami dapati =1/=1/3. Kami membawa masuk sudut bawah sel, di mana elemen umum terletak;

Dalam semua penjuru bawah baris umum yang tidak terisi, kami memasukkan hasil darab nilai di penjuru atas sel dengan;

Pilih sudut atas baris umum;

Di semua sudut bawah lajur umum kami memasukkan hasil darab nilai di sudut atas dengan - dan pilih nilai yang terhasil;

Baki sel jadual diisi sebagai hasil daripada elemen terpilih yang sepadan;

Kemudian kami membina jadual baharu di mana penetapan sel bagi elemen lajur dan baris umum diterbalikkan (x2 dan x3);

Di sudut atas baris dan lajur umum bekas, nilai-nilai yang sebelum ini berada di sudut bawah ditulis;

Jumlah nilai sudut atas dan bawah sel ini dalam jadual sebelumnya ditulis di sudut atas sel yang tinggal

4. Menyelesaikan masalah pengaturcaraan linear dengan mencari penyelesaian yang boleh dilaksanakan

Biarkan sistem persamaan algebra linear diberikan:

Kita boleh menganggap bahawa segala-galanya, jika tidak, kita membiak persamaan yang sepadan oleh -1.

Kami memperkenalkan pembolehubah tambahan:

Kami juga memperkenalkan fungsi tambahan

Kami akan meminimumkan sistem di bawah kekangan (2) dan syarat.

PERATURAN UNTUK MENCARI PENYELESAIAN YANG BOLEH DILAKUKAN: Untuk mencari penyelesaian yang boleh dilaksanakan kepada sistem (1), kami meminimumkan bentuk (3) di bawah kekangan (2), kerana yang tidak diketahui percuma kami mengambil xj sebagai yang asas.

Apabila menyelesaikan masalah dengan kaedah simplex, dua kes mungkin timbul:

min f=0, maka semua i mestilah sama dengan sifar. Dan nilai xj yang terhasil ialah penyelesaian yang boleh diterima sistem (1).

min f>0, i.e. sistem asal tidak mempunyai penyelesaian yang boleh dilaksanakan.

Sistem sumber:

Keadaan masalah topik sebelumnya digunakan.

Mari tambah pembolehubah tambahan:

Penyelesaian yang boleh diterima untuk masalah asal ditemui: x1 = 3, x2 = 3, F = -12. Berdasarkan penyelesaian yang boleh dilaksanakan, kami mencari penyelesaian optimum kepada masalah asal menggunakan kaedah simpleks. Untuk melakukan ini, kami akan membina jadual simplex baharu daripada jadual yang diperoleh di atas dengan memadam baris dan baris dengan fungsi sasaran tugas tambahan:

Menganalisis jadual simplex yang dibina, kita melihat bahawa penyelesaian optimum untuk masalah asal telah dijumpai (elemen dalam baris yang sepadan dengan fungsi objektif adalah negatif). Oleh itu, penyelesaian yang boleh dilaksanakan yang ditemui semasa menyelesaikan masalah tambahan bertepatan dengan penyelesaian optimum masalah asal:

6. Masalah dwi pengaturcaraan linear

Sistem kekangan awal dan fungsi objektif masalah ditunjukkan dalam rajah di bawah.

dengan sekatan:

Penyelesaian: Kami membawa sistem sekatan kepada bentuk standard:

Tugas dua untuk yang ini akan kelihatan seperti:

Masalah dwi akan diselesaikan dengan kaedah simpleks.

Mari kita ubah fungsi objektif supaya masalah pengecilan diselesaikan dan tuliskan sistem kekangan dalam bentuk piawai untuk penyelesaian dengan kaedah simpleks.

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

Mari kita bina jadual simpleks awal untuk menyelesaikan masalah dwi LP.

Langkah kedua kaedah simpleks

Jadi, pada langkah ketiga kaedah simpleks, penyelesaian optimum bagi masalah pengecilan didapati dengan keputusan berikut: y2 = -7 /8, y1 = -11/8, Ф = 12. Untuk mencari nilai bagi fungsi objektif masalah dwi, kami menggantikan nilai yang ditemui pembolehubah asas dan bebas ke dalam fungsi pemaksimuman:

Фmaks = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Oleh kerana nilai fungsi objektif masalah langsung dan dua adalah sama, penyelesaian kepada masalah langsung ditemui dan bersamaan dengan 12.

Fmin \u003d Fmax \u003d -12

7. Menyelesaikan masalah pengaturcaraan linear integer menggunakan kaedah “cabang dan sempadan”.

Jom tukar masalah asal dengan cara yang keadaan integer tidak dipenuhi apabila menyelesaikan dengan kaedah konvensional.

Poligon awal penyelesaian kepada masalah pengaturcaraan integer.

Untuk poligon penyelesaian yang diubah, kami membina sistem baru sekatan.

Kami menulis sistem kekangan dalam bentuk kesamaan, untuk menyelesaikan dengan kaedah algebra.

Hasil daripada penyelesaian, pelan tugas optimum ditemui: x1 = 9/4, x2 = 5/2, F = -41/4. Penyelesaian ini tidak memenuhi syarat kamiran yang ditetapkan dalam masalah. Kami membahagikan poligon penyelesaian asal kepada dua kawasan, tidak termasuk rantau 3 daripadanya

Mengubah poligon penyelesaian masalah

Mari kita karang sistem sekatan baharu untuk kawasan terbentuk poligon penyelesaian. Kawasan kiri ialah segi empat (trapezium). Sistem kekangan untuk kawasan kiri poligon penyelesaian dibentangkan di bawah.

Sistem sekatan untuk kawasan kiri

Kawasan kanan mewakili titik C.

Sistem kekangan untuk kawasan keputusan yang betul dibentangkan di bawah.

Sistem kekangan baharu ialah dua masalah subsidiari yang perlu diselesaikan secara bebas antara satu sama lain. Mari kita selesaikan masalah pengaturcaraan integer untuk kawasan kiri poligon penyelesaian.

Hasil daripada penyelesaian, pelan tugas optimum ditemui: x1 = 3, x2 = 3, F = -12. Pelan ini memenuhi syarat pembolehubah integer dalam masalah dan boleh diambil sebagai pelan rujukan optimum untuk masalah pengaturcaraan linear integer asal. Tidak masuk akal untuk menjalankan penyelesaian untuk kawasan penyelesaian yang betul. Rajah di bawah menunjukkan kemajuan penyelesaian masalah pengaturcaraan linear integer dalam bentuk pokok.

Kursus menyelesaikan masalah pengaturcaraan linear integer dengan kaedah Gomory.

Dalam banyak aplikasi praktikal, masalah pengaturcaraan integer sangat menarik, di mana sistem ketaksamaan linear dan bentuk linear diberikan

Ia diperlukan untuk mencari penyelesaian integer bagi sistem (1) yang meminimumkan fungsi objektif F, dan semua pekali adalah integer.

Salah satu kaedah untuk menyelesaikan masalah pengaturcaraan integer telah dicadangkan oleh Gomori. Idea kaedah ini adalah menggunakan kaedah pengaturcaraan linear berterusan, khususnya, kaedah simplex.

1) Dengan menggunakan kaedah simpleks, penyelesaian kepada masalah (1), (2) ditentukan, yang mana keperluan penyelesaian itu adalah integer dikeluarkan; jika penyelesaian ternyata menjadi integer, maka penyelesaian yang dikehendaki untuk masalah integer juga akan ditemui;

2) Jika tidak, jika sesetengah koordinat bukan integer, penyelesaian masalah yang diperolehi diperiksa untuk kemungkinan kewujudan penyelesaian integer (kehadiran titik integer dalam polyhedron yang boleh diterima):

jika dalam mana-mana baris dengan ahli bebas pecahan, semua pekali lain berubah menjadi integer, maka tiada integer, mata dalam polyhedron yang boleh diterima, dan masalah pengaturcaraan integer tidak mempunyai penyelesaian;

Jika tidak, kekangan linear tambahan diperkenalkan, yang memotong daripada polihedron boleh diterima bahagian yang tidak menjanjikan untuk mencari penyelesaian kepada masalah pengaturcaraan integer;

3) Untuk membina kekangan linear tambahan, pilih baris ke-l dengan ahli bebas pecahan dan tuliskan kekangan tambahan

di mana dan adalah, masing-masing, bahagian pecahan pekali dan bebas

ahli. Marilah kita memperkenalkan pembolehubah tambahan ke dalam kekangan (3):

Mari kita tentukan pekali dan termasuk dalam kekangan (4):

di mana dan ialah integer bawah terdekat untuk dan, masing-masing.

Gomory membuktikan bahawa bilangan terhingga langkah sedemikian membawa kepada masalah pengaturcaraan linear yang penyelesaiannya adalah integer dan, oleh itu, yang dikehendaki.

Penyelesaian: Kami mengurangkan sistem kekangan linear dan fungsi matlamat kepada bentuk kanonik:

Mari kita tentukan penyelesaian optimum sistem kekangan linear, membuang keadaan integer buat sementara waktu. Kami menggunakan kaedah simplex untuk ini. Jadual di bawah secara berurutan membentangkan penyelesaian awal masalah, dan transformasi jadual asal diberikan untuk mendapatkan penyelesaian optimum kepada masalah:

Menyelesaikan masalah Boolean LP dengan kaedah Balash.

Karang varian anda sendiri untuk masalah pengaturcaraan linear integer dengan pembolehubah Boolean, dengan mengambil kira peraturan berikut: masalah menggunakan sekurang-kurangnya 5 pembolehubah, sekurang-kurangnya 4 kekangan, pekali kekangan dan fungsi objektif dipilih secara sewenang-wenangnya, tetapi dalam keadaan sedemikian. cara sistem kekangan itu serasi. Tugasnya adalah untuk menyelesaikan ZCLP dengan pembolehubah Boolean menggunakan algoritma Balash dan menentukan pengurangan kerumitan pengiraan berhubung dengan menyelesaikan masalah dengan carian menyeluruh.

Pelaksanaan sekatan

nilai F

Kekangan penapis:

Penentuan Pengurangan Pengiraan

Penyelesaian masalah dengan kaedah carian menyeluruh ialah 6*25=192 ungkapan yang dikira. Penyelesaian masalah dengan kaedah Balash ialah 3*6+(25-3)=47 ungkapan yang dikira. Jumlah pengurangan dalam kerumitan pengiraan berhubung dengan penyelesaian masalah dengan kaedah carian menyeluruh ialah.

Kesimpulan

Proses mereka bentuk sistem maklumat yang melaksanakan teknologi maklumat baharu sentiasa diperbaiki. Sistem yang semakin kompleks menjadi tumpuan perhatian jurutera sistem, yang menjadikannya sukar untuk menggunakan model fizikal dan meningkatkan kepentingan model matematik dan simulasi komputer sistem. Pemodelan mesin telah menjadi alat yang berkesan untuk penyelidikan dan reka bentuk sistem yang kompleks. Perkaitan model matematik sentiasa meningkat kerana fleksibilitinya, kecukupan kepada proses sebenar, kos pelaksanaan yang rendah berdasarkan PC moden. Semakin banyak peluang diberikan kepada pengguna, iaitu pakar dalam sistem pemodelan melalui teknologi komputer. Penggunaan pemodelan amat berkesan pada peringkat awal mereka bentuk sistem automatik, apabila kos keputusan yang salah adalah paling ketara.

Alat pengkomputeran moden telah memungkinkan untuk meningkatkan kerumitan model yang digunakan dalam kajian sistem dengan ketara, ia telah menjadi mungkin untuk membina model gabungan, analisis dan simulasi yang mengambil kira keseluruhan pelbagai faktor yang berlaku dalam sistem sebenar, iaitu penggunaan model yang lebih sesuai dengan fenomena yang dikaji.

kesusasteraan:

1. Lyashchenko I.N. Pengaturcaraan linear dan bukan linear / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. Shor. - K .: "Sekolah Tinggi", 1975, 372 hlm.

2. Garis panduan untuk pelaksanaan projek kursus dalam disiplin "Matematik Gunaan" untuk pelajar khusus "Sistem Komputer dan Rangkaian" bentuk pendidikan sepenuh masa dan separuh masa / Disusun oleh: I.A. Balakireva, A.V. Skatkov - Sevastopol: SevNTU Publishing House , 2003. - 15 p.

3. Garis panduan untuk kajian disiplin "Matematik Gunaan", bahagian "Kaedah carian global dan pengecilan satu dimensi" / Comp. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: SevGTU Publishing House, 2000. - 31s.

4. Garis panduan untuk mengkaji disiplin "Matematik Gunaan" untuk pelajar khusus "Sistem Komputer dan Rangkaian" Bahagian "Menyelesaikan Masalah Pengaturcaraan Linear Integer" bentuk pendidikan sepenuh masa dan surat-menyurat / Disusun oleh: I.A. Balakireva, A.V. Skatkov - Sevastopol : SevNTU Publishing House, 2000. - 13 p.

5. Akulich I.L. Pengaturcaraan matematik dalam contoh dan tugasan:

6. Proc. elaun ekonomi pelajar. pakar. universiti.-M.: Lebih tinggi. sekolah, 1986.- 319s., sakit.

7. Andronov S.A. Kaedah reka bentuk optimum: Teks kuliah / SPbGUAP. SPb., 2001. 169 hlm: sakit.

Dokumen Serupa

Algoritma untuk menyelesaikan masalah pengaturcaraan linear dengan kaedah simpleks. Pembinaan model matematik masalah pengaturcaraan linear. Menyelesaikan masalah pengaturcaraan linear dalam Excel. Mencari keuntungan dan pelan pengeluaran yang optimum.

kertas penggal, ditambah 03/21/2012

Penyelesaian masalah grafik. Melukis model matematik. Menentukan nilai maksimum fungsi objektif. Penyelesaian dengan kaedah simpleks dengan asas buatan bagi masalah pengaturcaraan linear kanonik. Memeriksa optimum penyelesaian.

ujian, ditambah 04/05/2016

Asas teori pengaturcaraan linear. Masalah pengaturcaraan linear, kaedah penyelesaian. Analisis penyelesaian optimum. Penyelesaian masalah pengaturcaraan linear indeks tunggal. Penyataan masalah dan kemasukan data. Pembinaan model dan langkah penyelesaian.

kertas penggal, ditambah 12/09/2008

Pembinaan model matematik. Pemilihan, justifikasi dan penerangan kaedah untuk menyelesaikan masalah langsung pengaturcaraan linear dengan kaedah simplex, menggunakan jadual simplex. Perumusan dan penyelesaian masalah dwi. Analisis model untuk kepekaan.

kertas penggal, ditambah 31/10/2014

Membina model matematik untuk memaksimumkan keuntungan perusahaan, penyelesaian grafik kepada masalah tersebut. Penyelesaian masalah menggunakan alat tambah SOLVER. Analisis perubahan dalam rizab sumber. Penentuan had perubahan dalam pekali fungsi objektif.

kertas penggal, ditambah 17/12/2014

Pengaturcaraan matematik. Pengaturcaraan linear. Masalah pengaturcaraan linear. Kaedah grafik untuk menyelesaikan masalah pengaturcaraan linear. Rumusan ekonomi masalah pengaturcaraan linear. Pembinaan model matematik.

kertas penggal, ditambah 10/13/2008

Menyelesaikan masalah pengaturcaraan linear dengan kaedah grafik, pengesahannya dalam MS Excel. Analisis struktur dalaman penyelesaian masalah dalam program. Pengoptimuman pelan pengeluaran. Penyelesaian masalah dengan kaedah simpleks. Sistem beratur berbilang saluran.

ujian, ditambah 05/02/2012

Menyelesaikan masalah pengaturcaraan linear dengan kaedah simplex: menetapkan masalah, membina model ekonomi dan matematik. Penyelesaian masalah pengangkutan dengan kaedah potensi: pembinaan pelan rujukan awal, penentuan nilai optimumnya.

ujian, ditambah 04/11/2012

Pernyataan masalah pengaturcaraan tak linear. Penentuan titik pegun dan jenisnya. Pembinaan garis aras, graf tiga dimensi bagi fungsi objektif dan sekatan. Penyelesaian masalah secara grafik dan analitik. Manual pengguna dan skema algoritma.

kertas penggal, ditambah 17/12/2012

Analisis penyelesaian masalah pengaturcaraan linear. Kaedah simpleks menggunakan jadual simpleks. Pemodelan dan penyelesaian masalah LP pada komputer. Tafsiran ekonomi tentang penyelesaian optimum masalah. Rumusan matematik masalah pengangkutan.

TOPIK: PENGATURCARAAN LINEAR

TUGASAN 2.A. Menyelesaikan masalah pengaturcaraan linear dengan kaedah grafik

Perhatian!

Ini adalah VERSI PENGENALAN kerja No. 2073, harga asal ialah 200 rubel. Direka dalam Microsoft Word.

Bayaran. Kenalan.

Pilihan 7. Cari nilai maksimum dan minimumfungsi linearФ \u003d 2x 1 - 2 x 2dengan sekatan: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1.2.

Penyelesaian:

Menggantikan tanda-tanda ketaksamaan bersyarat dengan tanda-tanda kesamaan, kita memperoleh sistem persamaan x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Kami membina garis lurus mengikut persamaan ini, kemudian, mengikut tanda-tanda ketaksamaan, kami memilih separuh satah dan mendapatkan bahagian biasa mereka - kawasan penyelesaian ODE yang boleh diterima - MNPQ segiempat.

Nilai minimum fungsi

tsii - pada titik M (2; 2)

Ф min = 2 2 - 2 2 = 0.

Nilai maksimum dicapai pada titik N (10; 0),

Ф maks \u003d 2 10 - 2 0 \u003d 20.

Pilihan 8. Cari nilai maksimum dan minimum

fungsi linear Ф \u003d x 1 + x 2

dengan sekatan: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1.2.

Penyelesaian:

Menggantikan tanda-tanda ketaksamaan bersyarat dengan tanda-tanda kesamaan, kita memperoleh sistem persamaan x1 - 4 x2 = 4;

3 x1 - x2 = 0;

Kami membina garis lurus mengikut persamaan ini, kemudian, mengikut tanda-tanda ketaksamaan, kami memilih separuh satah dan mendapatkan bahagian sepunya - kawasan penyelesaian yang boleh diterima ODE - poligon MNPQ yang tidak terhad.

Nilai minimum fungsi

tions - pada garis lurus NP, sebagai contoh

pada titik Р(4; 0)

Ф min = 4 + 0 = 4.

ODE tidak terhad dari atas, oleh itu, Ф max = + ∞.

Pilihan 10. Cari nilai maksimum dan minimum

fungsi linear Ф \u003d 2 x 1 - 3 x 2

dengan sekatan: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1.2.

Menggantikan secara bersyarat tanda-tanda ketaksamaan dengan tanda-tanda kesamaan, kita memperoleh sistem persamaan

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Kami membina vektor Г(2; -3) dan lukis melalui asalan garisan aras- lurus.

Kami menggerakkan garis aras ke arah, manakala nilai F meningkat. Pada titik S(7; 0), fungsi objektif mencapai maksimum Ф max =2·7–3·0= = 14. Kami menggerakkan garis aras ke arah, manakala nilai Ф berkurangan. Nilai minimum fungsi adalah pada titik N(0; 5)

Ф min = 2 0 – 3 5 = –15.

TUGASAN 2.B. Menyelesaikan masalah pengaturcaraan linear

kaedah simpleks analitik

Pilihan 7. Minimumkan fungsi objektif Ф \u003d x 1 - x 2 + x 3 + x 4 + x 5 - x 6

di bawah sekatan: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 - 4 x 3 + 2 x 6 \u003d 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Penyelesaian:

Bilangan yang tidak diketahui n=6, bilangan persamaan m=3. Oleh itu, r = n-m = 3 yang tidak diketahui boleh diambil sebagai percuma. Mari pilih x 1 , x 3 dan x 6 .

Kami menyatakan pembolehubah asas x 2 , x 4 dan x 5 dalam sebutan yang bebas dan membawa sistem kepada asas unit

x 2 \u003d 2 - 3 x 1 + 4 x 3 - 2 x 6

x 4 \u003d 9 - x 1 - 6 x 6 (*)

x 5 \u003d 6 - x 1 - 2 x 3 - 2 x 6

Fungsi objektif akan kelihatan seperti:

Ф \u003d x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 - x 1 - 6 x 6 +6 - x 1 - 2 x 3 - 2 x 6 - x 6 =

13 + 2 x 1 - 5 x 3 - 7 x 6

Mari letakkan x 1 \u003d x 3 \u003d x 6 \u003d 0, manakala pembolehubah asas akan mengambil nilai x 2 \u003d 2; x 4 \u003d 9; x 5 \u003d 6, iaitu, penyelesaian pertama yang boleh dilaksanakan (0; 2; 0; 9; 6; 0), fungsi objektif Ф 1 \u003d 13.

Pembolehubah x 3 dan x 6 termasuk dalam fungsi objektif dengan pekali negatif, oleh itu, dengan peningkatan dalam nilainya, nilai Ф akan berkurangan. Ambil, sebagai contoh, x 6 . Daripada persamaan pertama sistem (*) dapat dilihat bahawa peningkatan dalam nilai x 6 adalah mungkin sehingga x 6 \u003d 1 (selagi x 2 ³ 0). Dalam kes ini, x 1 dan x 3 mengekalkan nilai sama dengan sifar. Sekarang, sebagai pembolehubah asas, kita ambil x 4, x 5, x 6, sebagai percuma - x 1, x 2, x 3. Mari kita nyatakan pembolehubah asas baharu dari segi pembolehubah percuma baharu. Dapatkan

x 6 \u003d 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3

x 4 \u003d 3 + 8 x 1 + 3 x 2 - 12 x 3

x 5 \u003d 4 + 2 x 1 + x 2 - 6 x 3

Ф \u003d 6 + 25/2 x 1 + 7/2 x 2 - 19 x 3

Berikan nilai sifar kepada pembolehubah bebas, iaitu, x 1 \u003d x 2 \u003d x 3 \u003d 0, manakala x 6 \u003d 1, x 4 \u003d 3, x 5 \u003d 4, iaitu, yang ketiga penyelesaian yang sah (0; 0; 0; 3; 4; 1). Dalam kes ini, Ф 3 \u003d 6.

Pembolehubah x 3 termasuk dalam fungsi objektif dengan pekali negatif, oleh itu, peningkatan dalam x 3 berbanding sifar akan membawa kepada penurunan dalam F. Daripada persamaan ke-2 dapat dilihat bahawa x 3 boleh meningkat sehingga 1/ 4, daripada persamaan ke-3 - sehingga 2/3 . Persamaan kedua adalah lebih kritikal. Kami menterjemahkan pembolehubah x 3 kepada bilangan yang asas, x 4 kepada bilangan yang percuma.

Sekarang kita ambil x 1 , x 2 dan x 4 sebagai pembolehubah bebas baharu. Mari kita ungkapkan pembolehubah asas baharu x 3 , x 5 , x 6 dalam sebutannya. Jom dapatkan sistem

x 3 \u003d 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 \u003d 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Fungsi objektif akan mengambil bentuk

Ф \u003d 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Pembolehubah x 1 dan x 2 dimasukkan ke dalam fungsi objektif dengan pekali negatif, oleh itu, dengan peningkatan dalam nilainya, nilai Ф akan berkurangan. Ambil, sebagai contoh, x 2 . Daripada persamaan ke-2 sistem, dapat dilihat bahawa peningkatan dalam nilai x 2 adalah mungkin sehingga x 2 \u003d 5 (selagi x 5 ³ 0). Dalam kes ini, x 1 dan x 4 mengekalkan nilai sifar, nilai pembolehubah lain adalah sama dengan x 3 = 3/2; x 5 \u003d 0, x 6 \u003d 3/2, iaitu penyelesaian sah keempat (0; 5; 3/2; 0; 0; 3/2). Dalam kes ini, Ф 4 \u003d 5/4.

Sekarang kita ambil x 1 , x 4 dan x 5 sebagai pembolehubah bebas baharu. Mari kita ungkapkan pembolehubah asas baharu x 2 , x 3 , x 6 dalam sebutannya. Jom dapatkan sistem

x 2 \u003d 5 - 4 x 1 + x 4 - 2 x 5

x 3 \u003d 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Fungsi objektif akan mengambil bentuk

F \u003d - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

Pekali untuk kedua-dua pembolehubah dalam ungkapan untuk Ф adalah positif, oleh itu, penurunan selanjutnya dalam nilai Ф adalah mustahil.

Iaitu, nilai minimum Ф min = - 5, penyelesaian terakhir yang boleh dilaksanakan (0; 5; 3/2; 0; 0; 3/2) adalah optimum.

Pilihan 8. Maksimumkan fungsi objektif Ф = 4 x 5 + 2 x 6

dengan sekatan: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 \u003d 30;

x 3 + x 5 - 2 x 6 \u003d 6;

2 x 4 + 3 x 5 - 2 x 6 \u003d 18;

Penyelesaian:

Bilangan persamaan ialah 4, bilangan yang tidak diketahui ialah 6. Oleh itu, r = n - m = 6 - 4 = 2 pembolehubah boleh dipilih sebagai bebas, 4 pembolehubah sebagai asas. Kami memilih x 5 dan x 6 sebagai yang percuma, x 1, x 2, x 3, x 4 sebagai yang asas. Kami menyatakan pembolehubah asas dalam sebutan yang bebas dan mengurangkan sistem persamaan kepada asas unit

x 1 \u003d 12 - x 5 - x 6;

x 2 \u003d 30 - 5 x 5 + x 6;

x 3 \u003d 6 - x 5 + 2 x 6;

x 4 \u003d 9 - 3/2 x 5 + x 6;

Kami menulis fungsi objektif dalam bentuk Ф = 4 x 5 + 2 x 6 . Kami memberikan nilai sifar kepada pembolehubah bebas x 5 = x 6 = 0. Dalam kes ini, pembolehubah asas akan mengambil nilai x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 , iaitu, kita akan mendapat penyelesaian pertama yang boleh dilaksanakan (12, 30 , 6, 9, 0,) dan Ф 1 = 0.

Kedua-dua pembolehubah bebas memasuki fungsi sasaran dengan pekali positif, iaitu, peningkatan selanjutnya dalam F adalah mungkin. Mari kita terjemahkan, sebagai contoh, x 6 ke dalam bilangan yang asas. Persamaan (1) menunjukkan bahawa x 1 = 0 pada x 5 = 12, dalam (2) ÷ (4) x 6 masuk dengan pekali positif. Mari kita beralih kepada asas baharu: pembolehubah asas - x 6, x 2, x 3, x 4, percuma - x 1, x 5. Mari kita nyatakan pembolehubah asas baharu melalui percuma baharu

x 6 \u003d 12 - x 1 - x 5;

x 2 \u003d 42 - x 1 - 6 x 5;

x 3 \u003d 30 - 2 x 1 - 3 x 5;

x 4 \u003d 21 - x 1 - 5/2 x 5;

Fungsi objektif akan mengambil bentuk Ф = 24 - 2 x 1 + 2 x 5 ;

Kami memberikan nilai sifar kepada pembolehubah bebas x 1 = x 5 = 0. Dalam kes ini, pembolehubah asas akan mengambil nilai x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 , iaitu, kita akan memperoleh penyelesaian kedua yang boleh dilaksanakan (0, 42 , 30, 21, 0, 12) dan Ф 2 = 24.

Fungsi sasaran x 5 masuk dengan pekali positif, iaitu, peningkatan selanjutnya dalam F adalah mungkin. Mari kita beralih kepada asas baru: pembolehubah asas - x 6, x 5, x 3, x 4, yang percuma - x 1 , x 2. Mari kita nyatakan pembolehubah asas baharu melalui percuma baharu

x 6 \u003d 5 - 5/6 x 1 + 1/6 x 2;

x 5 \u003d 7 - 1/6 x 1 - 1/6 x 2;

x 3 \u003d 9 - 3/2 x 1 + 1/2 x 2;

x 4 \u003d 7/2 - 7/12 x 1 + 5/12 x 5;

Fungsi objektif akan mengambil bentuk Ф = 38 - 7/2 x 1 - 1/3 x 2;

Berikan nilai sifar x 1 = x 2 = 0 kepada pembolehubah bebas. Dalam kes ini, pembolehubah asas akan mengambil nilai x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7/ 2, iaitu, kita akan mendapat penyelesaian ketiga yang boleh dilaksanakan X 3 = (0, 0, 9, 7/2, 7, 5) dan Ф 3 = 38.

Kedua-dua pembolehubah memasuki fungsi sasaran dengan pekali negatif, iaitu, peningkatan selanjutnya dalam Ф adalah mustahil.

Oleh itu, penyelesaian terakhir yang boleh dilaksanakan adalah optimum, iaitu, Х opt = (0, 0, 9, 7/2, 7, 5) dan Ф max = 38.

Pilihan 10. Maksimumkan fungsi objektif Ф \u003d x 2 + x 3

di bawah sekatan: x 1 - x 2 + x 3 \u003d 1,

x 2 - 2 x 3 + x 4 \u003d 2.

Penyelesaian:

Sistem persamaan - kekangan adalah konsisten, kerana kedudukan matriks sistem persamaan dan matriks lanjutan adalah sama dan sama dengan 2. Oleh itu, dua pembolehubah boleh diambil sebagai bebas, dua pembolehubah lain - asas - boleh dinyatakan secara linear dalam sebutan dua yang bebas.

Mari kita ambil x 2 dan x 3 sebagai pembolehubah bebas. Kemudian pembolehubah x 1 dan x 2 akan menjadi pembolehubah asas, yang akan kita nyatakan dalam sebutan bebas

x 1 \u003d 1 + x 2 - x 3; (*)

x 4 \u003d 2 - x 2 + 2 x 3;

Fungsi sasaran telah pun dinyatakan dalam sebutan x 2 dan x 3 , iaitu, Ф = x 2 + x 3 .

Pada x 2 \u003d 0 dan x 3 \u003d 0, pembolehubah asas akan sama dengan x 1 \u003d 1, x 4 \u003d 2.

Kami mempunyai penyelesaian pertama yang boleh dilaksanakan X 1 = (1, 0, 0, 2), manakala Ф 1 = 0.

Peningkatan dalam Ф adalah mungkin dengan peningkatan, sebagai contoh, dalam nilai x 3, yang termasuk dalam ungkapan untuk Ф dengan pekali positif (x 2 kekal sama dengan sifar). Dalam persamaan pertama sistem (*), dapat dilihat bahawa x 3 boleh dinaikkan kepada 1 (daripada keadaan x 1 ³0), iaitu, persamaan ini mengenakan sekatan untuk meningkatkan nilai x 3. Persamaan pertama sistem (*) sedang menyelesaikan. Berdasarkan persamaan ini, kita beralih kepada asas baru, menukar x 1 dan x 3 tempat. Sekarang pembolehubah asas ialah x 3 dan x 4, percuma - x 1 dan x 2. Kami kini menyatakan x 3 dan x 4 dalam sebutan x 1 dan x 2.

Kami mendapat: x 3 \u003d 1 - x 1 + x 2; (**)

x 4 \u003d 4 - 2 x 1 + x 2;

Ф \u003d x 2 + 1 - x 1 + x 2 \u003d 1 - x 1 + 2 x 2

Dengan menyamakan pembolehubah bebas kepada sifar, kami memperoleh penyelesaian asas kedua yang boleh diterima X 2 = (0; 0; 1; 4), di mana Ф 2 =1.

Peningkatan dalam F adalah mungkin dengan peningkatan dalam x 2. Peningkatan dalam x 2, berdasarkan sistem persamaan terakhir (**), tidak terhad. Oleh itu, Ф akan mengambil semua nilai positif yang besar, iaitu, Ф max = + ¥.

Jadi, fungsi objektif Ф tidak dibatasi dari atas, jadi tidak ada penyelesaian yang optimum.

TUGASAN 2.D. Tulis dua masalah kepada yang diberikan.

tugas asal.

Pilihan 7. Maksimumkan fungsi objektif Ф = 2× x 1 - x 4

dengan sekatan: x 1 + x 2 \u003d 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Penyelesaian:

Kami membawa sistem kekangan kepada satu, sebagai contoh, bentuk kanonik dengan memasukkan pembolehubah tambahan ke dalam persamaan ke-2 dan ke-3

x 1 + x 2 = 20,

x 2 + 2 × x 4 - x 5 \u003d 5,

- x 1 + x 2 + x 3 + x 6 \u003d 8.

Kami mendapat masalah asimetri jenis ke-2. Masalah dwi akan kelihatan seperti:

Minimumkan fungsi objektif F = 20 × y 1 + 5 × y 2 + 8 × y 3

untuk y 1 — y 3 ≥ 2,

y1 + y2 + y3 ≥ 0,

y 3 ≥ 0,

2× y2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Pilihan 8. Maksimumkan fungsi objektif Ф \u003d x 2 - x 4 - 3× x 5

dengan sekatan: x 1 + 2× x 2 - x 4 + x 5 \u003d 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (i = 1, 6)

Penyelesaian:

Kami mempunyai masalah pemaksimuman asal dengan sistem kekangan dalam bentuk persamaan, iaitu, sepasang masalah dwi mempunyai bentuk asimetri jenis ke-2, model matematik yang dalam bentuk matriks mempunyai bentuk:

Masalah awal: Masalah dua:

F = C × X maks F = B T × Ymin

di A × X \u003d B pada AT × Y ≥ C T

Dalam masalah asal, baris matriks pekali bagi pembolehubah dalam fungsi objektif mempunyai bentuk С = (0; 1; 0; -1; -3; 0),

matriks lajur bagi sebutan bebas dan matriks pekali bagi pembolehubah dalam sistem kekangan mempunyai bentuk

B \u003d 2, A \u003d 0 - 4 1 2 -1 0

Cari matriks transpos bagi pekali, baris matriks pekali bagi pembolehubah dalam fungsi objektif, dan lajur matriks bagi ahli bebas

0 1 0 0 V T \u003d (1; 2; 5)

A T = -1 2 0 C T = -1

Masalah dwi boleh ditulis dalam bentuk berikut:

cari nilai minimum bagi fungsi objektif F = y 1 + 2 × y 2 + 5 × y 3

di bawah sekatan y 1 ≥ 0,

2× y 1-4 × y 2 + 3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Pilihan 10. Minimumkan fungsi Ф = x 1 + x 2 + x 3

terhad: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Penyelesaian:

Kami mempunyai masalah pengecilan asal dengan sistem kekangan dalam bentuk ketaksamaan, iaitu, sepasang masalah dwi mempunyai bentuk simetri jenis ke-3, model matematik yang dalam bentuk matriks mempunyai bentuk:

Masalah asal Masalah berganda

F = C × X min F \u003d B T × Ymax

di A × X ≥ B di A T × Y ≤ C T

X ≥ 0 Y ≥ 0

Dalam masalah asal, baris matriks pekali bagi pembolehubah dalam fungsi objektif, lajur matriks sebutan bebas, dan matriks pekali bagi pembolehubah dalam sistem kekangan mempunyai bentuk

C \u003d (1; 1; 1), B \u003d 3, A \u003d 6 4 5

Mari kita cari matriks bagi masalah dwi

B T = (2; 3; 4) C T = 3 A T = 9 4 2

Masalah dwi dirumuskan sebagai:

Maksimumkan fungsi objektif F = 2y 1 + 3y 2 + 4y 3

di bawah sekatan 3 × y 1 + 6 × y 2 + 8 × y 3 ≤ 1,

9× y 1 + 4 × y 2 + 2 × y 3 ≤ 1,

7× y 1 + 5 × y 2 + 4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

TUGASAN 2.C. Menyelesaikan masalah pengaturcaraan linear menggunakan jadual simpleks.

Pilihan 7. Maksimumkan fungsi objektif Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

di bawah sekatan: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Penyelesaian:

Kami mengurangkan sistem kekangan kepada bentuk kanonik

2 x 1 + 3 x 2 - x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

Kami mempunyai sistem 3 persamaan dengan 7 tidak diketahui. Kami memilih x 1 , z 1 , z 3 sebagai pembolehubah asas 3, x 2 , x 3 , x 4 , z 2 sebagai pembolehubah percuma, kami menyatakan pembolehubah asas melaluinya.

Daripada (2) kita ada x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Gantikan dalam (1) dan (3), kita dapat

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 \u003d 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 \u003d 2.

Susun jadual simpleks

I lelaran Jadual 1

asas AC	Kebebasan. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z1	2	0	7	-11		1	2	0	1/ 4	1/8
z3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 \u003d (1; 0; 0; 0; 2; 0; 4) F 1 \u003d 2.

II lelaran Jadual 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 \u003d (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 \u003d 4.

III lelaran Jadual 3

x 1	1	1	— 6	0	0		-1	— 1	1/2
x4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7	11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7	13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7	45/14

X 3 \u003d (1; 0; 6/7; 10/7; 0; 0; 0) Ф 3 \u003d 52/7.

Lelaran IV Jadual 4

z1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X 4 \u003d (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 \u003d 149/14.

Tiada nombor negatif dalam baris indeks jadual terakhir, iaitu, dalam ungkapan untuk fungsi objektif, semua Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Jawapan: Ф maks = 149/14,

penyelesaian optimum (0; 0; 25/14; 37/14; 1/2; 0; 0)

Pilihan 8. Minimumkan fungsi objektif Ф = 5 x 1 - x 3

di bawah sekatan: x 1 + x 2 + 2 x 3 - x 4 \u003d 3,

x 2 + 2 x 4 \u003d 1,

Penyelesaian:

Bilangan pembolehubah ialah 4, pangkat matriks ialah 2, oleh itu bilangan pembolehubah bebas ialah r \u003d 4 - 2 \u003d 2, bilangan pembolehubah asas juga 2. Kami mengambil x 3, x 4 sebagai pembolehubah bebas, kami akan menyatakan pembolehubah asas x 1, x 2 dalam sebutan percuma dan kami membawa sistem kepada asas unit:

x 2 \u003d 1 - 2 x 4,

x 1 \u003d 3 - x 2 - 2 x 3 + x 4 \u003d 3 - 1 + 2 x 4 - 2 x 3 + x 4 \u003d 2 - 2 x 3 + 3 x 4

Ф \u003d 5 x 1 - x 3 \u003d 5 (2 - 2 x 3 + 3 x 4) - x 3 \u003d 10 - 10 x 3 + 15 x 4 - x 3 \u003d 10 - 11 x 3 + 15 x 4

Kami menulis sistem persamaan dan fungsi objektif dalam bentuk yang sesuai untuk jadual simpleks, iaitu, x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

Ф + 11 x 3 - 15 x 4 \u003d 10

Jom buat meja

I lelaran Jadual 1

asas AC	Kebebasan. AC
x1	2	1	0		— 3	1/2
x2	1	0	1	0	2
F	10	0	0	11	— 15	— 11/2

X 1 \u003d (2; 1; 0; 0) F 1 \u003d 10.

II lelaran Jadual 2

x3	1	1/2	0	1	-3/2	3/4
x2	1	0	1	0		1/2
F	— 1	— 11/2	0	0	3/2	— 3/4

X 2 \u003d (0; 1; 1; 0) F 2 \u003d -1.

III lelaran Jadual 3

x3	7/4	1/2	3/4	1	0
x4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X 3 \u003d (0; 0; 7/4; 1/2) F 3 \u003d -7/4.

Tiada nombor positif dalam baris indeks jadual terakhir, iaitu, dalam ungkapan untuk fungsi objektif, semua Г i > 0. Kami mempunyai kes I, oleh itu, penyelesaian asas terakhir adalah optimum.

Jawapan: Ф min = -7/4, penyelesaian optimum (0; 0; 7/4; 1/2)

********************

Pilihan 10. Minimumkan fungsi objektif Ф \u003d x 1 + x 2,

dengan sekatan: x 1 -2 x 3 + x 4 \u003d 2,

x 2 - x 3 + 2 x 4 \u003d 1,

Penyelesaian:

Bilangan pembolehubah ialah 5, kedudukan matriks ialah 3, oleh itu bilangan pembolehubah bebas ialah r \u003d 6-3 \u003d 2. Kami mengambil x 3 dan x 4 sebagai pembolehubah bebas, x 1, x 2, x 5 sebagai asas. Semua persamaan sistem telah dikurangkan kepada asas tunggal (pembolehubah asas dinyatakan dalam sebutan yang bebas), tetapi ia ditulis dalam bentuk yang tidak sesuai untuk menggunakan jadual simpleks. Kami menulis sistem persamaan dalam bentuk

x 1 - 2 x 3 + x 4 \u003d 2

x 2 - x 3 +2 x 4 \u003d 1

x 5 + x 3 - x 4 . = 5

Kami menyatakan fungsi objektif dari segi pembolehubah bebas dan menulisnya dalam bentuk Ф - 3 x 3 +3 x 4 = 3

Jom buat meja

I lelaran Jadual 1

asas AC	Kebebasan. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X 1 \u003d (2; 3; 0; 0; 5) F 1 \u003d 3.

jadual 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X 2 \u003d (3/2; 0; 0; 1/2; 11/2) F 2 \u003d 3/2.

Tiada nombor positif dalam baris indeks jadual terakhir, iaitu, dalam ungkapan untuk fungsi objektif, semua Гi > 0. Kami mempunyai kes 1, oleh itu, penyelesaian asas terakhir adalah optimum.

Jawapan: Ф min = 3/2, penyelesaian optimum ialah (3/2; 0; 0; 1/2; 11/2).

Kami membahagikan baris ketiga dengan elemen utama sama dengan 5, kami mendapat baris ketiga jadual baharu.

Lajur asas sepadan dengan lajur tunggal.

Pengiraan nilai jadual yang tinggal:

"BP - Pelan Asas":

; ;

"x1": ; ;

"x5": ; .

Nilai baris indeks adalah bukan negatif, oleh itu kami memperoleh penyelesaian optimum: , ; .

Jawapan: keuntungan maksimum daripada penjualan produk perkilangan, bersamaan dengan 160/3 unit, dipastikan dengan keluaran hanya produk jenis kedua dalam jumlah 80/9 unit.

Tugas nombor 2

Masalah pengaturcaraan tak linear diberikan. Cari maksimum dan minimum fungsi objektif menggunakan kaedah analisis graf. Susun fungsi Lagrange dan tunjukkan pada titik ekstrem syarat yang mencukupi minimum (maksimum).

Kerana digit terakhir sifir ialah 8, maka A=2; B=5.

Kerana digit terakhir sifir ialah 1, maka anda harus memilih tugasan nombor 1.

Penyelesaian:

1) Mari kita lukiskan kawasan yang ditakrifkan oleh sistem ketaksamaan.

Kawasan ini ialah segi tiga ABC dengan koordinat bucu: A(0; 2); B(4; 6) dan C(16/3; 14/3).

Tahap fungsi objektif ialah bulatan berpusat pada titik (2; 5). Kuasa dua jejari akan menjadi nilai fungsi objektif. Kemudian rajah menunjukkan bahawa nilai minimum fungsi objektif dicapai pada titik H, nilai maksimum sama ada pada titik A atau pada titik C.

Nilai fungsi objektif pada titik A: ;

Nilai fungsi objektif pada titik C: ;

Ini bermakna nilai maksimum fungsi dicapai pada titik A(0; 2) dan bersamaan dengan 13.

Mari cari koordinat titik H.

Untuk melakukan ini, pertimbangkan sistem:

Garis adalah tangen kepada bulatan jika persamaan mempunyai penyelesaian yang unik. Persamaan kuadratik mempunyai penyelesaian yang unik jika diskriminasi ialah 0.

Kemudian ; ; - nilai minimum fungsi.

2) Susun fungsi Lagrange untuk mencari penyelesaian minimum:

Pada x 1 =2.5; x 2 =4.5 kita mendapatkan:

Sistem ini mempunyai penyelesaian untuk , i.e. syarat ekstrem yang mencukupi dipenuhi.

Kami mengarang fungsi Lagrange untuk mencari penyelesaian maksimum:

Keadaan yang mencukupi untuk ekstrem:

Pada x 1 =0; x 2 =2 kita mendapatkan:

ó ó

Sistem ini juga mempunyai penyelesaian, i.e. syarat ekstrem yang mencukupi dipenuhi.

Jawapan: minimum fungsi objektif dicapai pada ; ; fungsi objektif maksimum dicapai apabila ; .

Tugas nombor 3

Dua perusahaan diperuntukkan dana dalam jumlah tersebut d unit. Apabila diperuntukkan kepada perusahaan pertama selama setahun x unit dana ia menyediakan pendapatan k 1 x unit, dan apabila diperuntukkan kepada perusahaan kedua y unit dana, ia memberikan pendapatan k 1 y unit. Baki dana pada akhir tahun untuk perusahaan pertama adalah sama dengan nx, dan untuk yang kedua saya. Bagaimana untuk mengagihkan semua dana dalam tempoh 4 tahun supaya jumlah pendapatan adalah yang terbesar? Selesaikan masalah dengan pengaturcaraan dinamik.

i=8, k=1.

A=2200; k 1 =6; k2=1; n=0.2; m=0.5.

Penyelesaian:

Keseluruhan tempoh 4 tahun dibahagikan kepada 4 peringkat, setiap satu sama dengan satu tahun. Mari kita nombor peringkat bermula dari tahun pertama. Biarkan X k dan Y k ialah dana yang diperuntukkan masing-masing kepada perusahaan A dan B pada peringkat ke-k. Kemudian jumlah X k + Y k =a k ialah jumlah keseluruhan dana yang digunakan pada peringkat k - itu dan baki daripada peringkat sebelumnya k - 1. pada peringkat pertama semua dana yang diperuntukkan digunakan dan 1 = 2200 unit. pendapatan yang akan diterima pada peringkat k - itu, apabila unit X k dan Y k diperuntukkan, akan menjadi 6X k + 1Y k . biarkan pendapatan maksimum yang diterima pada peringkat terakhir bermula dari k - peringkat itu ialah f k (a k) unit. Mari kita tulis persamaan Bellman berfungsi yang menyatakan prinsip optimum: apa pun keadaan awal dan penyelesaian awal penyelesaian berikutnya mestilah optimum berkenaan dengan keadaan yang terhasil daripada keadaan awal:

Untuk setiap peringkat, anda perlu memilih nilai X k , dan nilainya Y k=ak- Xk. Dengan ini, kita akan mencari pendapatan pada peringkat ke-k:

Persamaan Bellman berfungsi akan kelihatan seperti:

Pertimbangkan semua peringkat, bermula dengan yang terakhir.

(memandangkan maksimum fungsi linear dicapai pada penghujung segmen pada x 4 = a 4);