Cari dengan kaedah grafik minimum fungsi objektif. Cari ekstrem fungsi dengan kaedah grafik

Fungsi objektif- fungsi sebenar atau integer beberapa pembolehubah, tertakluk kepada pengoptimuman (pengoptimuman atau pemaksimum) untuk menyelesaikan beberapa masalah pengoptimuman. Istilah ini digunakan dalam pengaturcaraan matematik, penyelidikan operasi, pengaturcaraan linear, teori keputusan statistik dan bidang matematik yang lain, terutamanya yang bersifat gunaan, walaupun matlamat pengoptimuman mungkin juga merupakan penyelesaian masalah matematik yang betul. Selain daripada Fungsi objektif dalam masalah pengoptimuman, pembolehubah boleh dikekang dalam bentuk sistem kesamaan atau ketaksamaan. AT kes am hujah fungsi objektif boleh ditentukan pada set arbitrary.

Contoh

Fungsi licin dan sistem persamaan

Masalah menyelesaikan sebarang sistem persamaan

( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\mulakan(matriks)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matriks) )\betul.)

boleh dirumuskan sebagai masalah meminimumkan fungsi objektif

S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad(1))

Jika fungsinya lancar, maka masalah pengecilan boleh diselesaikan dengan kaedah kecerunan.

Untuk sebarang fungsi objektif lancar, seseorang boleh menyamakan dengan 0 (\displaystyle 0) terbitan separa berkenaan dengan semua pembolehubah. Fungsi objektif optimum akan menjadi salah satu penyelesaian kepada sistem persamaan tersebut. Dalam kes fungsi (1) (\displaystyle (1)) ini akan menjadi sistem persamaan kaedah petak terkecil(MNK). Mana-mana penyelesaian sistem asal ialah penyelesaian sistem kuasa dua terkecil. Jika sistem asal tidak konsisten, maka sistem LSM, yang sentiasa mempunyai penyelesaian, memungkinkan untuk mendapatkan penyelesaian anggaran sistem asal. Bilangan persamaan sistem LSM bertepatan dengan bilangan yang tidak diketahui, yang kadangkala memudahkan penyelesaian sistem permulaan bersama.

Pengaturcaraan linear

Lain-lain contoh terkenal fungsi objektif ialah fungsi linear yang berlaku dalam masalah pengaturcaraan linear. Tidak seperti fungsi objektif kuadratik, pengoptimuman fungsi linear hanya mungkin jika terdapat sekatan dalam bentuk sistem kesamaan linear atau ketaksamaan.

Pengoptimuman gabungan

Contoh tipikal fungsi objektif gabungan ialah fungsi objektif masalah jurujual perjalanan. Fungsi ini sama dengan panjang kitaran Hamiltonian pada graf. Ia diberikan pada set pilih atur n − 1 (\displaystyle n-1) bucu graf dan ditentukan oleh matriks panjang tepi graf. Penyelesaian yang tepat untuk masalah sedemikian sering datang kepada penghitungan pilihan.

Bab 1. Penyataan masalah utama pengaturcaraan linear

1. Pengaturcaraan linear

Pengaturcaraan linear ialah satu cabang pengaturcaraan matematik yang mengkaji kaedah untuk menyelesaikan masalah ekstrem yang dicirikan oleh pergantungan linear antara pembolehubah dan ujian linear. Masalah sedemikian menemui aplikasi yang meluas dalam pelbagai bidang Aktiviti manusia. Kajian sistematik tentang masalah jenis ini bermula pada 1939–1940. dalam karya L.V. Kantorovich.

Masalah matematik pengaturcaraan linear termasuk kajian pengeluaran tertentu dan situasi ekonomi, yang dalam satu bentuk atau yang lain ditafsirkan sebagai masalah penggunaan optimum sumber terhad.

Julat masalah yang diselesaikan menggunakan kaedah pengaturcaraan linear agak luas. Ini adalah, sebagai contoh:

masalah penggunaan sumber yang optimum dalam perancangan pengeluaran;

masalah campuran (merancang komposisi produk);

masalah mencari gabungan optimum pelbagai jenis produk untuk penyimpanan di gudang (pengurusan inventori atau);

tugas pengangkutan (analisis lokasi perusahaan, pergerakan barang).

Pengaturcaraan linear ialah bahagian pengaturcaraan matematik yang paling maju dan digunakan secara meluas (selain itu, ini termasuk: integer, dinamik, bukan linear, pengaturcaraan parametrik). Ini dijelaskan seperti berikut:

model matematik sebilangan besar masalah ekonomi adalah linear berkenaan dengan pembolehubah yang diperlukan;

jenis masalah ini paling banyak dikaji pada masa ini. Direka untuk dia kaedah khas, dengan bantuan tugas-tugas ini diselesaikan, dan program komputer yang sepadan;

banyak masalah pengaturcaraan linear, sedang diselesaikan, telah menemui aplikasi yang luas;

beberapa masalah yang tidak linear dalam rumusan asal, selepas satu siri sekatan tambahan dan andaian boleh menjadi linear atau boleh dikurangkan kepada bentuk sedemikian yang boleh diselesaikan dengan kaedah pengaturcaraan linear.

Model ekonomi dan matematik bagi sebarang masalah pengaturcaraan linear termasuk: fungsi objektif, yang nilai optimumnya (maksimum atau minimum) mesti ditemui; sekatan dalam bentuk sistem persamaan linear atau ketidaksamaan; keperluan pembolehubah bukan negatif.

AT Pandangan umum model ditulis seperti berikut:

Fungsi objektif

(1.1) di bawah sekatan

(1.2) keperluan bukan negatif

(1.3) di mana x j– pembolehubah (tidak diketahui);

- pekali masalah pengaturcaraan linear.

Masalahnya ialah untuk mencari nilai optimum bagi fungsi (1.1) tertakluk kepada kekangan (1.2) dan (1.3).

Sistem kekangan (1.2) dipanggil kekangan fungsi masalah, dan kekangan (1.3) dipanggil kekangan langsung.

Vektor yang memenuhi kekangan (1.2) dan (1.3) dipanggil penyelesaian yang boleh dilaksanakan (pelan) bagi masalah pengaturcaraan linear. Pelan yang mana fungsi (1.1) mencapai nilai maksimum (minimum) dipanggil optimum.

1.2. Kaedah simplex untuk menyelesaikan masalah pengaturcaraan linear

Kaedah simpleks telah dibangunkan dan pertama kali digunakan untuk menyelesaikan masalah pada tahun 1947 oleh ahli matematik Amerika J. Dantzig.

Masalah pengaturcaraan linear dua dimensi diselesaikan secara grafik. Untuk kes N=3, kita boleh mempertimbangkan ruang tiga dimensi dan fungsi objektif akan mencapai nilai optimumnya pada salah satu bucu polihedron.

Penyelesaian boleh diterima (pelan boleh diterima) bagi masalah LP yang diberikan dalam bentuk piawai ialah set nombor tertib (x1, x2, ..., xn) yang memenuhi kekangan; adalah titik dalam ruang n-dimensi.

Sekumpulan penyelesaian yang boleh dilaksanakan membentuk domain penyelesaian yang boleh diterima (ODS) bagi masalah LP. ODR ialah polihedron cembung (poligon).

Secara umum, apabila N-tidak diketahui terlibat dalam masalah, kita boleh mengatakan bahawa kawasan penyelesaian yang boleh dilaksanakan, yang diberikan oleh sistem syarat had, diwakili oleh polihedron cembung dalam ruang dimensi-n dan nilai optimum fungsi objektif dicapai pada satu atau lebih bucu.

Penyelesaian dipanggil asas jika semua pembolehubah bebas sama dengan sifar.

Penyelesaian rujukan ialah penyelesaian asas bukan negatif. Penyelesaian sokongan boleh menjadi tidak merosot dan merosot. Penyelesaian sokongan dipanggil tidak merosot jika bilangan koordinat bukan sifarnya adalah sama dengan pangkat sistem, jika tidak, ia merosot.

Penyelesaian yang boleh dilaksanakan, di mana fungsi objektif mencapai nilai ekstremnya, dipanggil optimum dan dilambangkan .

Adalah sangat sukar untuk menyelesaikan masalah ini secara grafik apabila bilangan pembolehubah adalah lebih daripada 3. wujud cara universal menyelesaikan masalah pengaturcaraan linear, dipanggil kaedah simpleks.

Kaedah simpleks adalah kaedah universal untuk menyelesaikan masalah LP, yang merupakan proses berulang yang bermula dengan satu penyelesaian dan, untuk mencari pilihan terbaik, bergerak di sepanjang titik sudut kawasan penyelesaian yang boleh dilaksanakan sehingga mencapai nilai optimum. .

Ia boleh digunakan untuk menyelesaikan sebarang masalah pengaturcaraan linear.

Kaedah simplex adalah berdasarkan idea penambahbaikan berturut-turut penyelesaian yang terhasil.

Makna geometri kaedah simpleks terdiri daripada peralihan berturut-turut dari satu bucu polihedron kekangan kepada satu jiran, di mana fungsi objektif mengambil nilai terbaik (atau sekurang-kurangnya bukan yang paling teruk) sehingga ia ditemui. penyelesaian yang optimum- puncak di mana nilai optimum fungsi matlamat dicapai (jika tugas mempunyai optimum terhingga).

Oleh itu, mempunyai sistem kekangan dikurangkan kepada bentuk kanonik(semua kekangan fungsian adalah dalam bentuk kesamaan), cari sebarang penyelesaian asas sistem ini, dengan berhati-hati untuk mencarinya semudah mungkin. Jika penyelesaian asas yang pertama ditemui ternyata boleh dilaksanakan, maka ia diperiksa untuk optimum. Jika ia tidak optimum, maka peralihan dibuat kepada penyelesaian asas yang lain, semestinya boleh diterima. Kaedah simplex menjamin bahawa, dengan penyelesaian baru ini, fungsi objektif, jika ia tidak mencapai optimum, kemudian mendekatinya (atau sekurang-kurangnya tidak bergerak darinya). Dengan penyelesaian asas baharu yang boleh diterima, perkara yang sama dilakukan sehingga penyelesaian didapati yang optimum.

Proses menggunakan kaedah simpleks melibatkan pelaksanaan tiga elemen utamanya:

kaedah untuk menentukan beberapa penyelesaian asas awal yang boleh dilaksanakan kepada masalah;

peraturan peralihan kepada penyelesaian terbaik (lebih tepat, bukan yang paling teruk);

kriteria untuk menyemak optimum penyelesaian yang ditemui.

Kaedah simplex merangkumi beberapa langkah dan boleh dirumuskan sebagai algoritma yang jelas (arahan yang jelas mengenai pelaksanaan operasi berturut-turut). Ini membolehkan anda berjaya memprogram dan melaksanakannya pada komputer. Masalah dengan sebilangan kecil pembolehubah dan kekangan boleh diselesaikan dengan kaedah simpleks secara manual.

6.1 Pengenalan

Pengoptimuman. Bahagian 1

Kaedah pengoptimuman membolehkan anda memilih pilihan reka bentuk terbaik daripada semua pilihan. AT tahun lepas kaedah ini telah diberikan perhatian yang besar, dan sebagai hasilnya dibangunkan keseluruhan baris algoritma yang sangat cekap untuk dicari pilihan terbaik reka bentuk menggunakan komputer. Bab ini menggariskan asas teori pengoptimuman, mempertimbangkan prinsip yang mendasari pembinaan algoritma untuk penyelesaian optimum, menerangkan algoritma yang paling terkenal dan menganalisis kelebihan dan kekurangannya.

6.2 Asas teori pengoptimuman

Istilah "pengoptimuman" dalam literatur merujuk kepada proses atau urutan operasi yang membolehkan anda mendapatkan penyelesaian yang diperhalusi. Walaupun matlamat utama pengoptimuman adalah untuk mencari penyelesaian yang terbaik, atau "optimum", anda biasanya perlu berpuas hati dengan menambah baik penyelesaian yang diketahui daripada menyempurnakan mereka. Oleh itu, pengoptimuman lebih cenderung untuk difahami sebagai mengejar kesempurnaan, yang, mungkin, tidak akan dicapai.

Memandangkan beberapa sistem sewenang-wenangnya, diterangkan oleh persamaan m dengan n tidak diketahui, terdapat tiga jenis masalah utama. Jika m=n , masalah itu dipanggil algebra. Masalah sedemikian biasanya mempunyai satu penyelesaian. Jika m>n, maka masalah itu ditakrifkan semula dan, sebagai peraturan, tidak mempunyai penyelesaian. Akhirnya, untuk m

Sebelum meneruskan perbincangan isu pengoptimuman, kami memperkenalkan beberapa definisi.

Parameter reka bentuk

Istilah ini merujuk kepada bebas parameter berubah-ubah, yang mentakrifkan secara lengkap dan jelas masalah reka bentuk yang sedang diselesaikan. Parameter reka bentuk adalah kuantiti yang tidak diketahui, nilainya dikira semasa proses pengoptimuman. Sebarang kuantiti asas atau derivatif yang berfungsi untuk menerangkan secara kuantitatif sistem boleh berfungsi sebagai parameter reka bentuk. Jadi, ia boleh menjadi nilai panjang, jisim, masa, suhu yang tidak diketahui. Bilangan parameter reka bentuk mencirikan tahap kerumitan masalah reka bentuk ini. Biasanya bilangan parameter reka bentuk dilambangkan dengan n, dan parameter reka bentuk itu sendiri dengan x dengan indeks yang sepadan. Oleh itu, n parameter reka bentuk masalah ini akan ditandakan dengan

X1, x2, x3,...,xn.

Fungsi objektif

Ini ialah ungkapan yang nilainya ingin dimaksimumkan atau diminimumkan oleh jurutera. Fungsi objektif membolehkan anda membandingkan secara kuantitatif dua penyelesaian alternatif. Dari sudut pandangan matematik, fungsi objektif menerangkan beberapa (n + 1) - permukaan dimensi. Nilainya ditentukan oleh parameter reka bentuk

M=M(x 1 , x 2 ,...,x n).

Contoh fungsi objektif, yang sering ditemui dalam amalan kejuruteraan, ialah kos, berat, kekuatan, dimensi, kecekapan. Jika terdapat hanya satu parameter reka bentuk, maka fungsi objektif boleh diwakili oleh lengkung pada satah (Rajah 6.1). Jika terdapat dua parameter reka bentuk, maka fungsi sasaran akan diwakili oleh permukaan dalam ruang tiga dimensi (Rajah 6.2). Dengan tiga atau lebih parameter reka bentuk, permukaan yang ditentukan oleh fungsi objektif dipanggil hypersurfaces dan tidak boleh digambarkan.

zheniya cara konvensional. Sifat topologi permukaan fungsi objektif memainkan peranan penting dalam proses pengoptimuman, kerana pilihan algoritma yang paling cekap bergantung kepada mereka.

Fungsi objektif dalam beberapa kes boleh mengambil bentuk yang paling tidak dijangka. Sebagai contoh, tidak selalu mungkin untuk menyatakannya

Rajah 1. Fungsi objektif satu dimensi.

Rajah 6.2.Fungsi objektif dua dimensi.

tertutup bentuk matematik, dalam kes lain ia mungkin

menjadi fungsi licin sekeping. Fungsi objektif kadangkala memerlukan jadual data teknikal (contohnya, jadual keadaan wap) atau mungkin perlu untuk menjalankan eksperimen. Dalam sesetengah kes, parameter reka bentuk hanya mengambil nilai integer. Contohnya ialah bilangan gigi dalam gear atau bilangan bolt dalam bebibir. Kadangkala parameter reka bentuk hanya mempunyai dua nilai - ya atau tidak. Parameter kualitatif, seperti kepuasan pelanggan, kebolehpercayaan, estetika, sukar untuk diambil kira dalam proses pengoptimuman, kerana ia hampir mustahil untuk diukur. Walau bagaimanapun, dalam apa jua bentuk fungsi objektif dibentangkan, ia mestilah fungsi nilai tunggal bagi parameter reka bentuk.

Dalam beberapa masalah pengoptimuman, pengenalan lebih daripada satu fungsi objektif diperlukan. Kadang-kadang salah satu daripada mereka mungkin tidak serasi dengan yang lain. Contohnya ialah reka bentuk pesawat, apabila ia diperlukan untuk memberikan kekuatan maksimum, berat minimum dan kos minimum pada masa yang sama. Dalam kes sedemikian, pereka bentuk mesti memperkenalkan sistem keutamaan dan menetapkan beberapa pengganda tanpa dimensi kepada setiap fungsi objektif. Akibatnya, "fungsi kompromi" muncul, yang membolehkan satu fungsi objektif komposit digunakan dalam proses pengoptimuman.

Mencari minimum dan maksimum

Sesetengah algoritma pengoptimuman disesuaikan untuk mencari maksimum, yang lain untuk mencari minimum. Walau bagaimanapun, tanpa mengira jenis masalah ekstrem yang sedang diselesaikan, seseorang boleh menggunakan algoritma yang sama, kerana masalah pengecilan boleh dengan mudah diubah menjadi masalah pencarian maksimum dengan membalikkan tanda fungsi objektif. Teknik ini digambarkan dalam Rajah 6.3.

Ruang reka bentuk

Ini ialah nama kawasan yang ditakrifkan oleh semua n parameter reka bentuk. Ruang reka bentuk tidak sebesar yang kelihatan, kerana ia biasanya terhad kepada beberapa

keadaan yang berkaitan dengan entiti fizikal tugasan. Kekangan boleh menjadi sangat kuat sehingga tugas itu tidak mempunyai apa-apa

Rajah 6.3 Menukar tanda fungsi objektif kepada sebaliknya

Tugas maksimum menjadi tugas minimum.

penyelesaian yang memuaskan. Kekangan dibahagikan kepada dua kumpulan: kekangan - kesamaan dan kekangan - ketidaksamaan.

Kekangan - kesaksamaan

Kekangan - kesamaan - adalah pergantungan antara parameter reka bentuk yang mesti diambil kira semasa mencari penyelesaian. Ia mencerminkan undang-undang alam semula jadi, ekonomi, hak, cita rasa yang lazim dan ketersediaan bahan yang diperlukan. Bilangan sekatan - kesamaan boleh menjadi apa-apa. Mereka kelihatan seperti

C 1 (x 1 , x 2 ,...,x n)=0,

C 2 (x 1 , x 2 ,...,x n)=0,

..................

C j (x 1 , x 2 ,...,x n)=0.

Jika mana-mana perhubungan ini boleh diselesaikan berkenaan dengan salah satu parameter reka bentuk, maka ini membolehkan anda mengecualikan parameter ini daripada proses pengoptimuman. Ini mengurangkan bilangan dimensi ruang reka bentuk dan memudahkan penyelesaian masalah.

Kekangan - ketidaksamaan

Ini adalah jenis kekangan istimewa yang dinyatakan oleh ketidaksamaan. Dalam kes umum, boleh terdapat sebarang nombor, dan kesemuanya mempunyai bentuk

z 1 r 1 (x 1 , x 2 ,...,x n) Z 1

z 2 r 2 (x 1 , x 2 ,...,x n) Z 2

.......................

z k r k (x 1 , x 2 ,...,x n) Z k

Perlu diingatkan bahawa selalunya, disebabkan oleh batasan, nilai optimum fungsi objektif tidak dicapai di mana permukaannya mempunyai kecerunan sifar. Selalunya penyelesaian terbaik adalah di salah satu sempadan domain reka bentuk.

optimum tempatan

Ini adalah nama titik dalam ruang reka bentuk di mana fungsi objektif mempunyai nilai terbesar berbanding dengan nilainya di semua titik lain di kawasan kejiranan terdekatnya.

Rajah 6.4 Fungsi objektif arbitrari boleh mempunyai beberapa

optima tempatan.

Pada rajah. Rajah 6.4 menunjukkan fungsi objektif satu dimensi yang mempunyai dua optima setempat. Selalunya ruang reka bentuk mengandungi banyak optima tempatan dan penjagaan mesti diambil untuk tidak tersilap yang pertama sebagai penyelesaian optimum kepada masalah tersebut.

Global Optimum

Optimum global ialah penyelesaian optimum untuk keseluruhan ruang reka bentuk. Ia lebih baik daripada semua penyelesaian lain yang sepadan dengan optima tempatan, dan inilah yang dicari oleh pereka bentuk. Kes beberapa optima global yang sama terletak di bahagian yang berbeza ruang reka bentuk. Cara masalah pengoptimuman ditimbulkan paling baik digambarkan oleh contoh.

Contoh 6.1

Biarkan ia dikehendaki untuk mereka bentuk bekas segi empat tepat dengan isipadu 1 m , direka untuk mengangkut gentian yang tidak dibungkus. Adalah wajar bahawa pengeluaran kontena sedemikian harus dibelanjakan sebanyak mungkin kurang bahan(dengan mengandaikan ketebalan dinding yang berterusan, ini bermakna bahawa luas permukaan harus minimum), kerana ia akan menjadi lebih murah. Untuk memudahkan pengambilan bekas dengan forklift, lebarnya mestilah sekurang-kurangnya 1.5 m.

Mari kita rumuskan masalah ini dalam bentuk yang sesuai untuk menggunakan algoritma pengoptimuman.

Parameter reka bentuk: x 1 , x 2 , x 3 .

Fungsi objektif (yang perlu diminimumkan) ialah luas permukaan sisi bekas:

A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2.

Kekangan - kesaksamaan:

Kelantangan \u003d x 1 x 2 x 3 \u003d 1m3.

Kekangan - ketidaksamaan:

Masalah pengaturcaraan linear

Pengaturcaraan Linear (LP) ialah salah satu bahagian pengaturcaraan matematik - satu disiplin yang mengkaji masalah ekstrem (pengoptimuman) dan membangunkan kaedah untuk menyelesaikannya.

Masalah pengoptimuman- ia masalah matematik, yang terdiri daripada mencari nilai optimum (iaitu, maksimum atau minimum) bagi fungsi objektif, dan nilai-nilai pembolehubah mestilah tergolong dalam kawasan tertentu nilai yang dibenarkan(ODZ).

Secara amnya, perumusan masalah ekstrem pengaturcaraan matematik terdiri daripada menentukan nilai terbesar atau terkecil fungsi, dipanggil Fungsi objektif, di bawah syarat (sekatan), di mana dan – fungsi yang telah ditetapkan, dan diberikan pemalar. Pada masa yang sama, sekatan dalam bentuk kesamaan dan ketidaksamaan menentukan set (rantau) penyelesaian yang boleh dilaksanakan (ODS), dan dipanggil parameter reka bentuk.

Bergantung kepada jenis fungsi dan masalah pengaturcaraan matematik dibahagikan kepada beberapa kelas (linear, tak linear, cembung, integer, stokastik, pengaturcaraan dinamik, dll.).

AT Pandangan umum Masalah LP ada pandangan seterusnya:

, (5.1)

, , (5.2)

, , (5.3)

di mana , , diberi pemalar.

Fungsi (5.1) dipanggil fungsi objektif; sistem (5.2), (5.3) - oleh sistem kekangan; syarat (5.4) ialah keadaan bukan negatif parameter reka bentuk.

Set parameter reka bentuk yang memenuhi kekangan (5.2), (5.3) dan (5.4) dipanggil penyelesaian yang boleh diterima atau rancangan.

Penyelesaian yang optimum atau rancangan yang optimum Masalah LP dipanggil penyelesaian yang boleh dilaksanakan, di mana fungsi objektif (5.1) mengambil nilai optimum (maksimum atau minimum).

Tugas standard LP dipanggil masalah mencari nilai maksimum (minimum) bagi fungsi objektif (5.1) di bawah keadaan (5.2) dan (5.4), di mana , , i.e. mereka. sekatan hanya dalam bentuk ketaksamaan (5.2) dan semua parameter reka bentuk memenuhi syarat bukan negatif, dan tiada syarat dalam bentuk kesamaan:

,

, , (5.5)

.

Tugas kanonik (utama). LP dipanggil masalah mencari nilai maksimum (minimum) bagi fungsi objektif (5.1) di bawah keadaan (5.3) dan (5.4), di mana , , i.e. mereka. sekatan hanya dalam bentuk kesamaan (5.3) dan semua parameter reka bentuk memenuhi syarat bukan negatif, dan tiada syarat dalam bentuk ketaksamaan:

,

.

Masalah LP kanonik juga boleh ditulis dalam bentuk matriks dan vektor.

Bentuk matriks masalah LP kanonik mempunyai bentuk berikut:

Bentuk vektor masalah LP kanonik.

KERJA KAWALAN MENGENAI DISIPLIN:

"KAEDAH PENYELESAIAN OPTIMAL"

Pilihan nombor 8

1. Menyelesaikan masalah pengaturcaraan linear menggunakan kaedah grafik. Cari maksimum dan minimum bagi fungsi  di bawah kekangan yang diberikan:

,

.

Keputusan

Adalah perlu untuk mencari nilai minimum fungsi objektif dan maksimum, di bawah sistem sekatan:

9x1 +3x2 ≥30, (1)

X 1 + x 2 ≤4, (2)

x 1 + x 2 ≤8, (3)

Mari kita bina domain penyelesaian yang boleh diterima, i.e. menyelesaikan secara grafik sistem ketaksamaan. Untuk melakukan ini, kami membina setiap garis lurus dan mentakrifkan separuh satah yang diberikan oleh ketaksamaan (separuh satah ditandakan dengan perdana).

Persilangan separuh satah akan menjadi kawasan, koordinat titik-titik yang memenuhi keadaan ketaksamaan sistem kekangan masalah. Mari kita nyatakan sempadan kawasan poligon penyelesaian.

Mari kita bina garis lurus yang sepadan dengan nilai fungsi F = 0: F = 2x 1 +3x 2 = 0. Vektor kecerunan yang terdiri daripada pekali fungsi objektif menunjukkan arah pengecilan F(X). Permulaan vektor ialah titik (0; 0), penghujungnya ialah titik (2; 3). Mari kita gerakkan baris ini secara selari. Oleh kerana kami berminat dengan penyelesaian minimum, oleh itu, kami menggerakkan garis lurus sehingga sentuhan pertama kawasan yang ditetapkan. Pada graf, garis ini ditunjukkan oleh garis putus-putus.

Lurus
memotong rantau pada titik C. Oleh kerana titik C diperoleh hasil daripada persilangan garis (4) dan (1), maka koordinatnya memenuhi persamaan garis ini:
.

Setelah menyelesaikan sistem persamaan, kita dapat: x 1 = 3.3333, x 2 = 0.

Di manakah kita boleh mencari nilai minimum bagi fungsi objektif: .

Pertimbangkan fungsi objektif masalah.

Mari kita bina garis lurus yang sepadan dengan nilai fungsi F = 0: F = 2x 1 +3x 2 = 0. Vektor kecerunan yang terdiri daripada pekali fungsi objektif menunjukkan arah pemaksimuman F(X). Permulaan vektor ialah titik (0; 0), penghujungnya ialah titik (2; 3). Mari kita gerakkan baris ini secara selari. Oleh kerana kami berminat dengan penyelesaian maksimum, kami menggerakkan garis lurus sehingga sentuhan terakhir kawasan yang ditetapkan. Pada graf, garis ini ditunjukkan oleh garis putus-putus.

Lurus
memotong rantau pada titik B. Oleh kerana titik B diperoleh hasil daripada persilangan garis (2) dan (3), maka koordinatnya memenuhi persamaan garis ini:

.

Di manakah kita boleh mencari nilai maksimum fungsi objektif: .

Jawapan:
dan
.

2 . Selesaikan masalah pengaturcaraan linear menggunakan kaedah simpleks:

.

Keputusan

Mari kita selesaikan masalah langsung pengaturcaraan linear dengan kaedah simpleks, menggunakan jadual simpleks.

Mari kita tentukan nilai minimum bagi fungsi objektif
di bawah syarat-sekatan berikut:
.

Untuk membina pelan rujukan pertama, kami mengurangkan sistem ketaksamaan kepada sistem persamaan dengan memperkenalkan pembolehubah tambahan.

Dalam ketaksamaan makna pertama (≥), kami memperkenalkan pembolehubah asas x 3 dengan tanda tolak. Dalam ketaksamaan makna ke-2 (≤), kami memperkenalkan pembolehubah asas x 4 . Dalam ketaksamaan makna ke-3 (≤), kami memperkenalkan pembolehubah asas x 5 .

Mari perkenalkan pembolehubah buatan : dalam kesamaan pertama kami memperkenalkan pembolehubah x 6 ;

Untuk menetapkan tugas untuk minimum, kami menulis fungsi objektif seperti berikut: .

Untuk penggunaan pembolehubah buatan yang dimasukkan ke dalam fungsi objektif, penalti yang dipanggil M dikenakan, nombor positif yang sangat besar, yang biasanya tidak dinyatakan.

Asas yang terhasil dipanggil buatan, dan kaedah penyelesaian dipanggil kaedah asas buatan.

Selain itu, pembolehubah buatan tidak berkaitan dengan kandungan tugas, tetapi ia membolehkan anda membina titik permulaan, dan proses pengoptimuman memaksa pembolehubah ini mengambil nilai sifar dan memastikan kebolehterimaan penyelesaian optimum.

Daripada persamaan kita menyatakan pembolehubah buatan: x 6 \u003d 4-x 1 -x 2 +x 3, yang kita gantikan ke dalam fungsi objektif: atau.

Matriks Pekali
sistem persamaan ini mempunyai bentuk:
.

Mari kita selesaikan sistem persamaan berkenaan dengan pembolehubah asas: x 6 , x 4 , x 5.

Dengan mengandaikan bahawa pembolehubah bebas ialah 0, kita mendapat garis dasar pertama:

X1 = (0,0,0,2,10,4)

Penyelesaian asas dipanggil boleh diterima jika ia bukan negatif.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Garis dasar semasa tidak optimum kerana terdapat pekali positif dalam baris indeks. Kami akan memilih lajur yang sepadan dengan pembolehubah x 2 sebagai yang terkemuka, kerana ini adalah pekali terbesar. Kira nilai D i dan pilih yang terkecil: min(4: 1 , 2: 2 , 10: 2) = 1.

Oleh itu, barisan ke-2 mendahului.

Elemen penyelesaian adalah sama dengan (2) dan terletak di persimpangan lajur hadapan dan baris hadapan.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Kami membentuk bahagian seterusnya jadual simplex. Daripada pembolehubah x 4, pembolehubah x 2 akan memasuki pelan 1.

Garisan yang sepadan dengan pembolehubah x 2 dalam pelan 1 diperoleh dengan membahagikan semua elemen garisan x 4 pelan 0 dengan elemen pemboleh RE=2. Sebagai ganti elemen penyelesaian, kita mendapat 1. Dalam baki sel lajur x 2, kita menulis sifar.

Oleh itu, dalam pelan baharu 1 baris x 2 dan lajur x 2 diisi. Semua elemen lain pelan baharu 1, termasuk elemen baris indeks, ditentukan oleh peraturan segi empat tepat.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1 / 2 +1 1 / 2 M

Garis dasar semasa tidak optimum kerana terdapat pekali positif dalam baris indeks. Kami akan memilih lajur yang sepadan dengan pembolehubah x 1 sebagai yang terkemuka, kerana ini adalah pekali terbesar. Kira nilai D i mengikut baris sebagai hasil bahagi: dan daripada mereka kami memilih yang terkecil: min (3: 1 1 / 2, -, 8: 2) = 2.

Oleh itu, barisan pertama mendahului.

Elemen penyelesaian adalah sama dengan (1 1 / 2) dan terletak di persimpangan lajur hadapan dan baris hadapan.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 M

Kami membentuk bahagian seterusnya jadual simplex. Daripada pembolehubah x 6 , pembolehubah x 1 akan dimasukkan dalam pelan 2.

Kami mendapat jadual simplex baharu:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Tiada nilai baris indeks adalah positif. Oleh itu, jadual ini menentukan pelan tugas yang optimum.

Versi akhir jadual simplex:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Oleh kerana tiada pembolehubah buatan dalam penyelesaian optimum (ia sama dengan sifar), maka keputusan ini ianya sah.

Pelan optimum boleh ditulis seperti berikut: x 1 \u003d 2, x 2 \u003d 2:.

Jawab:
,
.

3. Syarikat "Tiga lelaki gemuk" terlibat dalam penghantaran daging dalam tin dari tiga gudang yang terletak di bahagian yang berlainan di bandar ke tiga kedai. Stok makanan dalam tin yang terdapat di gudang, serta jumlah pesanan dari kedai dan kadar penghantaran (bersyarat unit kewangan) dibentangkan dalam jadual pengangkutan.

Cari pelan pengangkutan yang menyediakan kos tunai paling sedikit (lakukan pelan pengangkutan asal menggunakan kaedah "sudut barat laut").

Keputusan

Marilah kita semak syarat yang diperlukan dan mencukupi untuk kebolehlarutan masalah:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Syarat baki dipenuhi. Stok keperluan yang sama. Oleh itu, model masalah pengangkutan ditutup.

Mari masukkan data awal dalam jadual pengedaran.

Keperluan

Menggunakan kaedah sudut barat laut, kami akan membina pelan asas pertama masalah pengangkutan.

Pelan itu mula diisi dari sudut kiri atas.

Elemen yang diingini ialah 4. Untuk elemen ini, stoknya ialah 300, keperluannya ialah 250. Oleh kerana minimum ialah 250, kita tolak: .

			300 - 250 = 50
250 - 250 = 0

Elemen yang diingini ialah 2. Untuk elemen ini, stoknya ialah 50, keperluannya ialah 400. Oleh kerana minimum ialah 50, kami menolaknya: .

			50 - 50 = 0
	400 - 50 = 350

Elemen yang diingini ialah 5. Untuk elemen ini, stoknya ialah 300, keperluannya ialah 350. Oleh kerana minimum ialah 300, kami menolaknya:

			300 - 300 = 0
	350 - 300 = 50

Elemen yang diingini ialah 3. Untuk elemen ini, stok ialah 200, keperluannya ialah 50. Oleh kerana minimum ialah 50, kami menolaknya:

			200 - 50 = 150
	50 - 50 = 0

Elemen yang diingini ialah 6. Untuk elemen ini, stoknya ialah 150, keperluannya ialah 150. Oleh kerana minimum ialah 150, kami menolaknya:

			150 - 150 = 0
		150 - 150 = 0

Keperluan

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

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 selesaikan menggunakan kaedah simpleks.
• 2. Susun model matematik bagi masalah dwi, ​​tulis 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 semua delta adalah lebih besar daripada sifar, maka peningkatan lagi dalam nilai fungsi matlamat f adalah mustahil dan kami telah memperoleh pelan yang optimum.

Jika terdapat hanya dua pembolehubah dalam masalah pengaturcaraan linear, maka ia boleh diselesaikan secara grafik.

Pertimbangkan masalah pengaturcaraan linear dengan dua pembolehubah dan:
(1.1) ;
(1.2)
Di sini , adalah nombor sewenang-wenangnya. Tugas boleh kedua-duanya untuk mencari maksimum (maks) dan untuk mencari minimum (min). Dalam sistem sekatan, kedua-dua tanda dan tanda boleh hadir.

Pembinaan domain penyelesaian yang boleh dilaksanakan

Kaedah grafik untuk menyelesaikan masalah (1) adalah seperti berikut.
Mula-mula, kita lukis paksi koordinat dan pilih skala. Setiap ketaksamaan sistem kekangan (1.2) mentakrifkan separuh satah yang dibatasi oleh garis yang sepadan.

Jadi ketidaksamaan pertama
(1.2.1)
mentakrifkan separuh satah yang dibatasi oleh garis. Di satu sisi baris ini, dan di sisi lain. Pada garisan paling lurus. Untuk mengetahui dari mana ketaksamaan sisi (1.2.1) berpuas hati, kami memilih titik sewenang-wenangnya tidak berbaring di atas garis lurus. Seterusnya, kita menggantikan koordinat titik ini dalam (1.2.1). Jika ketaksamaan berlaku, maka separuh satah mengandungi titik yang dipilih. Jika ketaksamaan tidak berpuas hati, maka separuh satah terletak di sisi lain (tidak mengandungi titik yang dipilih). Kami menaungi separuh satah yang mana ketaksamaan (1.2.1) dipenuhi.

Kami melakukan perkara yang sama untuk baki ketaksamaan sistem (1.2). Jadi kita mendapat separuh satah berlorek. Titik domain penyelesaian yang boleh diterima memenuhi semua ketaksamaan (1.2). Oleh itu, secara grafik, kawasan penyelesaian boleh dilaksanakan (ODD) ialah persilangan semua satah separuh yang dibina. Kami menaungi ODR. Ia adalah poligon cembung yang mukanya tergolong dalam garisan yang dibina. Juga, ODR boleh menjadi angka cembung tanpa had, segmen, sinar atau garis lurus.

Kes juga mungkin timbul bahawa separuh pesawat tidak mengandungi perkara biasa. Kemudian domain penyelesaian yang boleh diterima ialah set kosong. Masalah ini tiada penyelesaian.

Anda boleh memudahkan kaedah. Anda tidak boleh menaungi setiap separuh satah, tetapi mula-mula bina semua garisan
(2)
Seterusnya, pilih titik arbitrari yang bukan milik mana-mana garisan ini. Gantikan koordinat titik ini ke dalam sistem ketaksamaan (1.2). Jika semua ketaksamaan dipenuhi, maka luas penyelesaian yang boleh dilaksanakan dihadkan oleh garisan yang dibina dan termasuk titik yang dipilih. Kami menaungi kawasan penyelesaian yang boleh diterima di sepanjang sempadan garisan supaya ia termasuk titik yang dipilih.

Jika sekurang-kurangnya satu ketaksamaan tidak berpuas hati, maka pilih titik lain. Dan seterusnya, sehingga satu titik ditemui, koordinatnya memenuhi sistem (1.2).

Mencari ekstrem bagi fungsi objektif

Jadi, kami mempunyai kawasan berlorek bagi penyelesaian yang boleh dilaksanakan (ODD). Ia dibatasi oleh garis putus yang terdiri daripada ruas dan sinar kepunyaan garisan yang dibina (2). ODR sentiasa set cembung. Boleh jadi macam set terhad, dan tidak terhad di sepanjang beberapa arah.

Sekarang kita boleh mencari ekstrem bagi fungsi objektif
(1.1) .

Untuk melakukan ini, pilih sebarang nombor dan bina garis lurus
(3) .
Untuk kemudahan pembentangan selanjutnya, kami menganggap bahawa garis lurus ini melalui ODS. Pada garis lurus ini, fungsi objektif adalah malar dan sama dengan . garis lurus sedemikian dipanggil garis aras fungsi. Garisan ini membahagikan satah kepada dua satah separuh. Pada satu setengah pesawat
.
Di separuh lagi pesawat
.
Iaitu, pada satu sisi garis lurus (3), fungsi objektif meningkat. Dan semakin jauh kita mengalihkan titik dari garisan (3), semakin besar nilainya. Di sisi lain garis lurus (3), fungsi objektif berkurangan. Dan semakin jauh kita mengalihkan titik dari garis (3) ke sisi lain, semakin kecil nilainya. Jika kita melukis garisan selari dengan garisan (3), maka garisan baharu juga akan menjadi garis tahap fungsi objektif, tetapi dengan nilai yang berbeza .

Oleh itu, untuk mencari nilai maksimum fungsi objektif, adalah perlu untuk melukis garis lurus selari dengan garis lurus (3), sejauh mungkin daripadanya ke arah peningkatan nilai , dan melalui sekurang-kurangnya satu titik ODT. Untuk mencari nilai minimum fungsi objektif, adalah perlu untuk melukis garis lurus selari dengan garis lurus (3) dan sejauh mungkin daripadanya ke arah penurunan nilai , dan melalui sekurang-kurangnya satu titik daripada ODT.

Jika ODE tidak terhad, maka kes mungkin timbul apabila garis lurus tersebut tidak boleh dilukis. Iaitu, tidak kira bagaimana kita mengeluarkan garis lurus dari garis aras (3) ke arah meningkat (menurun), garis lurus akan sentiasa melalui ODR. Dalam kes ini, ia boleh sewenang-wenangnya besar (kecil). Oleh itu, tiada nilai maksimum (minimum). Masalahnya tiada penyelesaian.

Pertimbangkan kes apabila garis melampau selari dengan garis arbitrari dalam bentuk (3) melalui satu bucu poligon ODD. Daripada graf, kami menentukan koordinat puncak ini. Kemudian nilai maksimum (minimum) fungsi objektif ditentukan oleh formula:
.
Penyelesaian kepada masalah tersebut ialah
.

Mungkin juga terdapat kes apabila garis lurus selari dengan salah satu muka ODS. Kemudian garisan itu melalui dua bucu poligon ODD. Kami menentukan koordinat bucu ini. Untuk menentukan nilai maksimum (minimum) bagi fungsi objektif, anda boleh menggunakan koordinat mana-mana bucu ini:
.
Masalah itu mempunyai banyak penyelesaian yang tidak terhingga. Penyelesaiannya ialah sebarang titik yang terletak pada segmen antara titik dan , termasuk titik itu sendiri dan .

Contoh penyelesaian masalah pengaturcaraan linear dengan kaedah grafik

Tugas

Syarikat itu mengeluarkan pakaian dua model A dan B. Tiga jenis fabrik digunakan. Untuk pembuatan satu model pakaian A, 2 m kain jenis pertama, 1 m kain jenis kedua, 2 m kain jenis ketiga diperlukan. Untuk pembuatan satu pakaian model B, 3 m kain jenis pertama, 1 m kain jenis kedua, 2 m kain jenis ketiga diperlukan. Stok fabrik jenis pertama ialah 21 m, jenis kedua - 10 m, jenis ketiga - 16 m. Pelepasan satu produk jenis A membawa pendapatan sebanyak 400 den. unit, satu produk jenis B - 300 den. unit

Sediakan pelan pengeluaran yang menyediakan syarikat dengan pendapatan terbesar. Selesaikan masalah secara grafik.

Keputusan

Biarkan pembolehubah dan nyatakan bilangan pakaian yang dihasilkan bagi model A dan B, masing-masing. Kemudian jumlah tisu yang digunakan daripada jenis pertama ialah:
(m)
Jumlah fabrik yang digunakan bagi jenis kedua ialah:
(m)
Jumlah fabrik yang digunakan bagi jenis ketiga ialah:
(m)
Oleh kerana bilangan pakaian yang dihasilkan tidak boleh negatif, maka
dan .
Pendapatan daripada pakaian yang dihasilkan ialah:
(den. unit)

Kemudian model ekonomi-matematik masalah mempunyai bentuk:

Kami menyelesaikannya secara grafik.
Lukiskan paksi koordinat dan .

Kami membina garis lurus.
Pada .
Pada .
Kami melukis garis lurus melalui titik (0; 7) dan (10.5; 0).

Kami membina garis lurus.
Pada .
Pada .
Kami melukis garis lurus melalui titik (0; 10) dan (10; 0).

Kami membina garis lurus.
Pada .
Pada .
Kami melukis garis lurus melalui titik (0; 8) dan (8; 0).

Kami lorekkan kawasan itu supaya titik (2; 2) jatuh ke bahagian yang berlorek. Kami mendapat OABC segiempat.

(P1.1) .
Pada .
Pada .
Kami melukis garis lurus melalui titik (0; 4) dan (3; 0).

Selanjutnya, kami perhatikan bahawa oleh kerana pekali untuk dan bagi fungsi objektif adalah positif (400 dan 300), maka ia meningkat dengan peningkatan dan . Kami melukis garis lurus selari dengan garis lurus (A1.1), sejauh mungkin daripadanya ke arah peningkatan, dan melalui sekurang-kurangnya satu titik OABC segiempat. Garis lurus sedemikian melalui titik C. Daripada pembinaan, kita menentukan koordinatnya.
.

Penyelesaian masalah: ;

Jawab

.
Iaitu, untuk mendapatkan pendapatan terbesar, perlu membuat 8 pakaian model A. Pendapatan dalam kes ini ialah 3200 den. unit

Contoh 2

Tugas

Menyelesaikan masalah pengaturcaraan linear menggunakan kaedah grafik.

Keputusan

Kami menyelesaikannya secara grafik.
Lukiskan paksi koordinat dan .

Kami membina garis lurus.
Pada .
Pada .
Kami melukis garis lurus melalui titik (0; 6) dan (6; 0).

Kami membina garis lurus.
Dari sini.
Pada .
Pada .
Kami melukis garis lurus melalui titik (3; 0) dan (7; 2).

Kami membina garis lurus.
Kami membina garis lurus (paksi absis).

Domain penyelesaian boleh diterima (DDR) dihadkan oleh garis lurus yang dibina. Untuk mengetahui dari sisi mana, kita perhatikan bahawa titik itu adalah milik ODT, kerana ia memenuhi sistem ketaksamaan:

Kami lorekkan kawasan di sepanjang sempadan garisan yang dibina supaya titik (4; 1) jatuh ke bahagian yang berlorek. Kita mendapatkan segi tiga ABC.

Kami membina garis aras sewenang-wenangnya bagi fungsi objektif, sebagai contoh,
.
Pada .
Pada .
Kami melukis garis aras lurus melalui titik (0; 6) dan (4; 0).
Oleh kerana fungsi objektif bertambah dengan peningkatan dan , kita lukis garis lurus, garis selari aras dan sejauh mungkin daripadanya ke arah peningkatan , dan melalui sekurang-kurangnya satu titik segi tiga ABC. Garis lurus sedemikian melalui titik C. Daripada pembinaan, kita menentukan koordinatnya.
.

Penyelesaian masalah: ;

Jawab

Contoh tiada penyelesaian

Tugas

Selesaikan secara grafik masalah pengaturcaraan linear. Cari nilai maksimum dan minimum bagi fungsi objektif.

Keputusan

Kami menyelesaikan masalah secara grafik.
Lukiskan paksi koordinat dan .

Kami membina garis lurus.
Pada .
Pada .
Kami melukis garis lurus melalui titik (0; 8) dan (2.667; 0).

Kami membina garis lurus.
Pada .
Pada .
Kami melukis garis lurus melalui titik (0; 3) dan (6; 0).

Kami membina garis lurus.
Pada .
Pada .
Kami melukis garis lurus melalui titik (3; 0) dan (6; 3).

Garis dan ialah paksi koordinat.

Domain penyelesaian boleh diterima (SDR) dihadkan oleh garis lurus dan paksi koordinat yang dibina. Untuk mengetahui dari sisi mana, kita perhatikan bahawa titik itu adalah milik ODT, kerana ia memenuhi sistem ketaksamaan:

Kami lorekkan kawasan itu supaya titik (3; 3) jatuh ke bahagian yang berlorek. Kami mendapat kawasan tanpa had yang dibatasi oleh garis putus ABCDE.

Kami membina garis aras sewenang-wenangnya bagi fungsi objektif, sebagai contoh,
(P3.1) .
Pada .
Pada .
Kami melukis garis lurus melalui titik (0; 7) dan (7; 0).
Oleh kerana pekali pada dan adalah positif, maka meningkat dengan peningkatan dan .

Untuk mencari maksimum, anda perlu melukis garis selari, sejauh mungkin ke arah peningkatan, dan melalui sekurang-kurangnya satu titik rantau ABCDE. Walau bagaimanapun, oleh kerana kawasan itu tidak bersempadan dari sisi nilai yang besar dan , maka garis lurus sedemikian tidak boleh dilukis. Walau apa pun garis lurus yang kita lukis, akan sentiasa ada mata di rantau yang lebih jauh ke arah peningkatan dan . Oleh itu, tidak ada maksimum. anda boleh membuat ia sebesar yang anda mahu.

Kami sedang mencari yang minimum. Kami melukis garis lurus selari dengan garis lurus (A3.1) dan sejauh mungkin daripadanya ke arah menurun , dan melalui sekurang-kurangnya satu titik rantau ABCDE. Garis lurus sedemikian melalui titik C. Daripada pembinaan, kita menentukan koordinatnya.
.
Nilai minimum fungsi sasaran:

Jawab

Tiada nilai maksimum.
Nilai minimum
.