Kami membagi baris ketiga dengan elemen kunci sama dengan 5, kami mendapatkan baris ketiga dari tabel baru.

Kolom dasar sesuai dengan kolom tunggal.

Perhitungan nilai tabel yang tersisa:

"BP - Paket Dasar":

; ;

"x1": ; ;

"x5": ; .

Nilai baris indeks adalah non-negatif, oleh karena itu kami memperoleh solusi optimal: , ; .

Menjawab: keuntungan maksimum dari penjualan produk manufaktur, sama dengan 160/3 unit, dipastikan dengan pelepasan hanya produk tipe kedua dalam jumlah 80/9 unit.

Tugas nomor 2

Masalah pemrograman nonlinier diberikan. Temukan maksimum dan minimum dari fungsi tujuan menggunakan metode analisis grafik. Susunlah fungsi Lagrange dan tunjukkan bahwa kondisi minimum (maksimum) yang memadai dipenuhi pada titik-titik ekstrem.

Karena digit terakhir cipher adalah 8, maka A=2; B=5.

Karena digit terakhir dari cipher adalah 1, maka Anda harus memilih tugas nomor 1.

Keputusan:

1) Mari kita menggambar area yang didefinisikan oleh sistem pertidaksamaan.

Luas ini adalah segitiga ABC dengan koordinat titik-titik: A(0; 2); B(4; 6) dan C(16/3; 14/3).

Tingkat fungsi tujuan adalah lingkaran yang berpusat di titik (2; 5). Kuadrat jari-jari akan menjadi nilai fungsi tujuan. Kemudian gambar menunjukkan bahwa nilai minimum dari fungsi tujuan tercapai pada titik H, nilai maksimum baik pada titik A atau pada titik C.

Nilai fungsi tujuan di titik A: ;

Nilai fungsi tujuan di titik C: ;

Ini berarti bahwa nilai maksimum fungsi tercapai pada titik A(0; 2) dan sama dengan 13.

Tentukan koordinat titik H.

Untuk melakukan ini, pertimbangkan sistem:

ó

ó

Sebuah garis bersinggungan dengan lingkaran jika persamaan memiliki solusi yang unik. Persamaan kuadrat memiliki solusi unik jika diskriminannya adalah 0.

Kemudian ; ; - nilai minimum fungsi.

2) Susun fungsi Lagrange untuk mencari solusi minimum:

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

ó

Sistem memiliki solusi untuk , mis. kondisi ekstrem yang cukup terpenuhi.

Kami menyusun fungsi Lagrange untuk menemukan solusi maksimum:

Kondisi yang cukup untuk ekstrem:

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

ó ó

Sistem ini juga memiliki solusi, yaitu kondisi ekstrem yang cukup terpenuhi.

Menjawab: minimum dari fungsi tujuan tercapai pada ; ; fungsi tujuan maksimum tercapai jika ; .

Tugas nomor 3

Dua perusahaan dialokasikan dana dalam jumlah d unit. Ketika dialokasikan ke perusahaan pertama selama satu tahun x unit dana yang memberikan pendapatan k 1 x unit, dan ketika dialokasikan ke perusahaan kedua kamu unit dana, itu memberikan pendapatan k 1 kamu unit. Saldo dana pada akhir tahun untuk perusahaan pertama sama dengan nx, dan untuk yang kedua -ku. Bagaimana cara mendistribusikan semua dana dalam waktu 4 tahun agar total pendapatan terbesar? Memecahkan masalah dengan pemrograman dinamis.

i=8, k=1.

J=2200; k 1 = 6; k2=1; n=0.2; m = 0,5.

Keputusan:

Seluruh periode 4 tahun dibagi menjadi 4 tahap yang masing-masing sama dengan satu tahun. Mari kita beri nomor tahapan mulai dari tahun pertama. Misalkan X k dan Y k adalah dana yang dialokasikan masing-masing untuk perusahaan A dan B pada tahap ke-k. Maka jumlah X k + Y k =a k adalah jumlah total dana yang digunakan pada tahap k - itu dan sisa dari tahap sebelumnya k - 1. pada tahap pertama semua dana yang dialokasikan digunakan dan a 1 =2200 unit. pendapatan yang akan diterima pada k - tahap itu, ketika unit X k dan Y k dialokasikan, akan menjadi 6X k + 1Y k . biarkan pendapatan maksimum yang diterima pada tahap terakhir dimulai dari k - tahap itu adalah f k (a k) unit. Mari kita tulis persamaan fungsional Bellman yang menyatakan prinsip optimalitas: berapa pun keadaan awal dan solusi awal, solusi selanjutnya harus optimal terhadap keadaan yang diperoleh sebagai hasil dari keadaan awal:

Untuk setiap tahap, Anda harus memilih nilai X k , dan nilainya y k=ak- Xk. Dengan mengingat hal ini, kita akan menemukan pendapatan pada tahap ke-k:

Persamaan Bellman fungsional akan terlihat seperti:

Pertimbangkan semua tahapan, dimulai dengan yang terakhir.

(karena maksimum fungsi linier dicapai pada akhir segmen pada x 4 = a 4);

Badan Federal untuk Pendidikan

lembaga pendidikan anggaran negara

pendidikan profesional yang lebih tinggi

"Universitas Teknik Negeri Omsk"

PERHITUNGAN DAN PEKERJAAN GRAFIS

dengan disiplin"TEORI KONTROL OPTIMAL »

pada topik"METODE OPTIMASI DAN RISET OPERASI »

opsi 7

Lengkap:

siswa korespondensi

Grup tahun ke-4 ZA-419

Nama: Kuzhelev S. A.

Diperiksa:

Devyaterikova M.V.

Omsk - 2012
^

Tugas 1. Metode grafis untuk memecahkan masalah program linier.

7) 7x 1 + 6x 2 → maks 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

Langkah 1. Membangun area yang valid

Kondisi variabel dan kuadrat non-negatif membatasi rentang nilainya yang dapat diterima ke kuadran pertama. Masing-masing dari empat kendala-ketidaksetaraan model yang tersisa sesuai dengan beberapa setengah bidang. Perpotongan setengah bidang ini dengan kuadran pertama membentuk himpunan solusi yang layak untuk masalah tersebut.

Batasan pertama dari model tersebut adalah . Mengganti tanda di dalamnya dengan tanda =, kita memperoleh persamaan . pada gambar. 1.1 itu mendefinisikan garis (1) yang membagi pesawat menjadi dua setengah bidang, dalam hal ini di atas dan di bawah garis. Untuk memilih mana yang memenuhi pertidaksamaan , kami menggantinya dengan koordinat titik mana pun yang tidak terletak pada garis yang diberikan (misalnya, titik asal X 1 = 0, X 2 = 0). Karena kita memperoleh ekspresi yang benar (20 0 + 6 0 = 0 15), setengah bidang yang memuat titik asal (ditandai dengan panah) memenuhi pertidaksamaan. Jika tidak, setengah bidang lainnya.

Kami melanjutkan dengan cara yang sama dengan kendala yang tersisa dari masalah. Perpotongan semua setengah bidang yang dibangun dengan bentuk kuadran pertama ABCD(lihat gambar 1). Ini adalah ruang lingkup tugas yang valid.

Langkah 2. Membangun garis level Garis level fungsi tujuan adalah himpunan titik-titik di bidang di mana fungsi tujuan mengambil nilai konstan. Himpunan seperti itu diberikan oleh persamaan f ( x) = konstan. Mari kita menempatkan, misalnya, konstan = 0 dan buat garis di level f ( x) = 0 , yaitu dalam kasus kami, langsung 7 x 1 + 6x 2 = 0.

Garis ini melalui titik asal dan tegak lurus terhadap vektor . Vektor ini adalah gradien fungsi tujuan pada (0,0). Gradien suatu fungsi adalah vektor nilai turunan parsial dari suatu fungsi yang diberikan pada titik yang bersangkutan. Dalam kasus masalah LP, turunan parsial dari fungsi tujuan sama dengan koefisien Csaya, j = 1 , ..., n.

Gradien menunjukkan arah pertumbuhan tercepat dari fungsi. Memindahkan garis level fungsi tujuan f ( x) = konstan. tegak lurus terhadap arah gradien, temukan titik terakhir di mana ia berpotongan dengan luas. Dalam kasus kami, ini adalah titik D, yang akan menjadi titik maksimum dari fungsi tujuan (lihat Gambar 2)

Itu terletak di persimpangan garis (2) dan (3) (lihat Gambar. 1) dan menetapkan solusi optimal.

^ Perhatikan bahwa jika Anda ingin mencari nilai minimum dari fungsi tujuan, garis level dipindahkan ke arah yang berlawanan dengan arah gradien.

^ Langkah 3. Menentukan koordinat titik maksimum (minimum) dan nilai optimal dari fungsi tujuan

Untuk menemukan koordinat titik C, perlu untuk menyelesaikan sistem yang terdiri dari persamaan langsung yang sesuai (dalam hal ini, dari persamaan 2 dan 3):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Kami mendapatkan solusi optimal = 1,33.

^ Nilai optimal dari fungsi tujuan f * = f (X*) = 7 * 0 + 6 * 1,33 = 7,8

Keputusan: cari nilai maksimum dan minimum dari fungsi \(f (x, y)\) di bawah batasan berikut $$ f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min \ \ \begin(cases) 2x+3y\geq 6 \\ 3x-2y\leq 18\\ -x+2y\leq 8\\ x,y\geq0\end(cases) $$
Disarankan untuk menggunakan metode grafis untuk memecahkan masalah untuk masalah dengan dua variabel yang ditulis dalam bentuk simetris, serta untuk masalah dengan banyak variabel, asalkan notasi kanoniknya berisi tidak lebih dari dua variabel bebas.

Dalam hal ini, tugas dengan dua variabel.

Algoritma untuk memecahkan masalah "interpretasi geometris dari masalah program linier":

1. Mari kita buat domain solusi yang dapat diterima pada bidang xOy.
2. Pilih area solusi non-negatif.

4. Mari kita membangun keluarga fungsi tujuan.
5. Temukan nilai maksimum (minimum) dari fungsi tujuan.

1. Kami membangun domain solusi yang dapat diterima dari masalah \(D\).

Untuk membangun area solusi yang layak:
1) Kami membangun garis batas:
kita ubah pertidaksamaan menjadi persamaan, dan kemudian ke persamaan garis lurus dalam segmen pada sumbu dengan bentuk \(\frac(x)(a)+\frac(y)(b) = 1\), lalu \ (x=a\) adalah segmen yang terpotong pada sumbu Ox, \(y=b\) - pada sumbu Oy $$ \begin(cases) 2x+3y = 6 \\ 3x-2y = 18\\ - x+2y = 8 \end(cases) => \begin(cases) \frac(x)(3)+\frac(y)(2) = 1 \\ \frac(x)(8)-\frac( y)(9) = 1 \\ -\frac (x)(6)+ \frac(y)(4) = 1 \end(cases) $$ Untuk setiap garis, sisihkan segmen pada sumbu dan hubungkan. Kami mendapat garis yang tepat.

2) Kami menemukan setengah bidang yang memenuhi pertidaksamaan yang diberikan:
Untuk pertidaksamaan \(2x+3y\geq 6\) adalah setengah bidang yang terletak di atas garis \(2x+3y = 6\). AC langsung
Untuk pertidaksamaan \(3x-2y\leq 18 => -3x+2y \geq -18\) adalah setengah bidang yang terletak di atas garis \(3x-2y = 18\). CB langsung
Untuk pertidaksamaan \(-x+2y\leq 8\) adalah setengah bidang yang terletak di bawah garis \(-x+2y = 8\). AB langsung

Domain solusi layak didefinisikan sebagai bagian umum dari tiga setengah bidang yang sesuai dengan pertidaksamaan yang diberikan. Luas ini adalah segitiga \(ABC\)

Daerah \(D\) adalah segitiga \(ABC\) lihat gambar.

2. Pilih area solusi non-negatif.

Wilayah solusi non-negatif terletak di kuartal pertama dan merupakan bagian umum dari semua lima setengah bidang, tiga di antaranya adalah wilayah \(D\) yang diperoleh dari pertidaksamaan dan tambahan dua pertidaksamaan \(x \geq 0\ ) - setengah bidang atas (perempat I dan II) dan \(y \geq 0\) - setengah bidang kanan (perempat I dan IV), yang menyatakan kondisi variabel non-negatif \(x; y\). Memperoleh area solusi non-negatif yang diinginkan \(DEBFG\)

3.Temukan koordinat simpul wilayah.
Koordinat keempat simpul sudah diketahui (ini adalah titik potong garis dengan sumbu).
Mari kita tuliskan koordinat ini:
\(D(0;2)\), \(E(0;4)\), \(F(6;0)\), \(G(3;0)\)
Tentukan koordinat titik \(B\), sebagai titik potong garis \(-x+2y = 8\) dan \(3x-2y = 18\). Selesaikan sistem persamaan dan temukan koordinat titik ini $$\begin(cases) -x+2y = 8\\ 3x-2y = 18\end(cases)=> \begin(cases) 2x = 26\\ 3x -2y = 18 \end(cases)=> \begin(cases) x = 13\\ y =10.5\end(cases)$$
Kami mendapatkan koordinat titik \(B(13;10.5)\)

4. Kami membangun keluarga fungsi objektif.
Persamaan \(f(x,y)=(x-4)^2 + (y-3)^2 \panah kanan max,min\) mendefinisikan pada bidang xOy sebuah keluarga lingkaran konsentris yang berpusat pada titik dengan koordinat \ (Q(4 ;3)\), yang masing-masing sesuai dengan nilai tertentu dari parameter \(f\). Seperti yang Anda ketahui, untuk persamaan lingkaran parameternya \(f=R^2\).

Mari kita nyatakan dalam sistem koordinat yang sama sebuah keluarga lingkaran konsentris \(f\) dan keluarga garis. Masalah menentukan titik maksimum (minimum) dari titik \(f\) akan direduksi menjadi menemukan di daerah yang dapat diterima titik yang dilalui lingkaran keluarga \(f=const\), yang bertanggung jawab untuk nilai terbesar (terkecil) dari parameter \(f\).

5. Temukan nilai maksimum (minimum) dari fungsi tujuan.

Nilai fungsi tujuan minimum: Dengan meningkatkan jari-jari lingkaran secara bertahap, kita memperoleh bahwa titik sudut pertama yang dilalui lingkaran adalah titik \(G(3;0)\). Fungsi tujuan pada titik ini akan minimal dan sama dengan \(f(3,0)=(3-4)^2 + (0-3)^2 = 10\)

Nilai maksimum dari fungsi tujuan: Dengan semakin memperbesar jari-jari lingkaran, kita memperoleh bahwa simpul terakhir yang akan dilalui lingkaran adalah titik \(B(13;10.5)\). Fungsi tujuan pada titik ini akan maksimum dan sama dengan \(f(13,10.5)=(13-4)^2 + (10,5-3)^2 = 137,25\)

Anda dapat memverifikasi kebenaran solusi dengan mengganti koordinat simpul yang tersisa ke dalam persamaan fungsi tujuan:
pada titik \(D(0;2)\) nilai fungsi tujuan sama dengan \(f(0,2)=(0-4)^2 + (2-3)^2 = 17\)
pada titik \(E(0;4)\) nilai fungsi tujuan sama dengan \(f(0,4)=(0-4)^2 + (4-3)^2 = 17\)
pada titik \(F(6;0)\) nilai fungsi tujuan adalah \(f(6,4)=(6-4)^2 + (0-3)^2 = 13\)
Mengerti

Menjawab:
nilai minimum fungsi tujuan \(f_(min) = 10\)
nilai maksimum fungsi tujuan \(f_(max) = 137,25\)

fungsi objektif- fungsi nyata atau bilangan bulat dari beberapa variabel, tunduk pada optimasi (minimalisasi atau maksimalisasi) untuk memecahkan beberapa masalah optimasi. Istilah ini digunakan dalam pemrograman matematika, riset operasi, pemrograman linier, teori keputusan statistik dan bidang matematika lainnya, terutama yang bersifat terapan, meskipun tujuan optimasi juga dapat menjadi solusi dari masalah matematika itu sendiri. Selain fungsi tujuan, dalam masalah optimasi, variabel dapat dikenai pembatasan berupa sistem persamaan atau ketidaksamaan. Dalam kasus umum, argumen fungsi tujuan dapat ditentukan pada himpunan arbitrer.

Contoh

Fungsi halus dan sistem persamaan

Masalah penyelesaian sistem persamaan apa pun

( 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\((\begin(matrix)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) )\Baik.)

dapat dirumuskan sebagai masalah meminimalkan fungsi tujuan

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 mulus, maka masalah minimasi dapat diselesaikan dengan metode gradien.

Untuk setiap fungsi tujuan halus, seseorang dapat menyamakan dengan 0 (\displaystyle 0) turunan parsial terhadap semua variabel. Fungsi tujuan yang optimal akan menjadi salah satu solusi untuk sistem persamaan tersebut. Dalam kasus fungsi (1) (\displaystyle (1)) ini akan menjadi sistem persamaan kuadrat terkecil (LSM). Setiap solusi dari sistem asli adalah solusi dari sistem kuadrat terkecil. Jika sistem asli tidak konsisten, maka sistem LSM, yang selalu memiliki solusi, memungkinkan untuk mendapatkan solusi perkiraan dari sistem asli. Jumlah persamaan sistem LSM bertepatan dengan jumlah yang tidak diketahui, yang terkadang memfasilitasi solusi sistem awal gabungan.

Pemrograman linier

Contoh lain yang terkenal dari fungsi tujuan adalah fungsi linier yang terjadi dalam masalah pemrograman linier. Berbeda dengan fungsi tujuan kuadrat, optimasi fungsi linier hanya dimungkinkan jika terdapat pembatasan berupa sistem persamaan atau pertidaksamaan linier.

Optimasi kombinatorial

Contoh khas dari fungsi tujuan kombinatorial adalah fungsi tujuan dari masalah penjual keliling. Fungsi ini sama dengan panjang siklus Hamilton pada grafik. Ini diberikan pada himpunan permutasi n 1 (\displaystyle n-1) dari simpul graf dan ditentukan oleh matriks panjang tepi graf. Solusi yang tepat dari masalah seperti itu sering kali bermuara pada penghitungan opsi.

Bab 1. Pernyataan masalah utama pemrograman linier

1. Pemrograman linier

Pemrograman linier adalah cabang dari pemrograman matematika yang mempelajari metode untuk memecahkan masalah ekstrem yang dicirikan oleh hubungan linier antara variabel dan kriteria linier. Tugas-tugas seperti itu menemukan aplikasi yang luas di berbagai bidang aktivitas manusia. Sebuah studi sistematis masalah jenis ini dimulai pada tahun 1939-1940. dalam karya L.V. Kantorovich.

Masalah matematika program linier mencakup studi produksi tertentu dan situasi ekonomi, yang dalam satu atau lain bentuk ditafsirkan sebagai masalah penggunaan sumber daya yang terbatas secara optimal.

Rentang masalah yang diselesaikan dengan menggunakan metode pemrograman linier cukup luas, antara lain:

masalah penggunaan sumber daya yang optimal dalam perencanaan produksi;

masalah campuran (merencanakan komposisi produk);

masalah menemukan kombinasi optimal dari berbagai jenis produk untuk penyimpanan di gudang (manajemen inventaris atau);

tugas transportasi (analisis lokasi perusahaan, pergerakan barang).

Pemrograman linier adalah bagian yang paling berkembang dan banyak digunakan dari pemrograman matematika (selain itu, ini termasuk: bilangan bulat, dinamis, non-linier, pemrograman parametrik). Hal ini dijelaskan sebagai berikut:

model matematika dari sejumlah besar masalah ekonomi adalah linier terhadap variabel yang diperlukan;

jenis masalah saat ini yang paling dipelajari. Baginya, metode khusus telah dikembangkan dengan bantuan yang memecahkan masalah ini, dan program komputer yang sesuai;

banyak masalah pemrograman linier, yang dipecahkan, telah menemukan aplikasi yang luas;

beberapa masalah yang tidak linier dalam formulasi aslinya, setelah sejumlah batasan dan asumsi tambahan, dapat menjadi linier atau dapat direduksi menjadi bentuk sedemikian rupa sehingga dapat diselesaikan dengan metode pemrograman linier.

Model ekonomi dan matematika dari setiap masalah program linier meliputi: fungsi tujuan, nilai optimal yang (maksimum atau minimum) harus ditemukan; pembatasan berupa sistem persamaan atau pertidaksamaan linier; persyaratan non-negatif variabel.

Secara umum, model ditulis sebagai berikut:

fungsi objektif

(1.1) di bawah batasan

(1.2) persyaratan non-negatif

(1.3) dimana x j– variabel (tidak diketahui);

- koefisien dari masalah program linier.

Masalahnya adalah mencari nilai optimal dari fungsi (1.1) yang tunduk pada kendala (1.2) dan (1.3).

Sistem kendala (1.2) disebut kendala fungsional dari masalah, dan kendala (1.3) disebut kendala langsung.

Sebuah vektor yang memenuhi kendala (1.2) dan (1.3) disebut solusi layak (rencana) dari masalah program linier. Rencana di mana fungsi (1.1) mencapai nilai maksimum (minimum) disebut optimal.

1.2. Metode simpleks untuk menyelesaikan masalah program linier

Metode simpleks dikembangkan dan pertama kali diterapkan untuk memecahkan masalah pada tahun 1947 oleh matematikawan Amerika J. Danzig.

Masalah pemrograman linier dua dimensi diselesaikan secara grafis. Untuk kasus N=3, kita dapat mempertimbangkan ruang tiga dimensi dan fungsi tujuan akan mencapai nilai optimalnya di salah satu simpul polihedron.

Solusi yang dapat diterima (rencana yang dapat diterima) dari masalah LP yang diberikan dalam bentuk standar adalah himpunan bilangan berurutan (x1, x2, ..., xn) yang memenuhi kendala; adalah titik dalam ruang n-dimensi.

Himpunan solusi yang dapat diterima membentuk area solusi yang dapat diterima (SDR) dari masalah LP. ODR adalah polihedron cembung (poligon).

Secara umum, ketika N-tidak diketahui terlibat dalam masalah, kita dapat mengatakan bahwa area solusi layak yang ditentukan oleh sistem kondisi pembatas diwakili oleh polihedron cembung dalam ruang n-dimensi dan nilai optimal tujuan fungsi dicapai pada satu atau lebih simpul.

Suatu solusi disebut dasar jika semua variabel bebas sama dengan nol.

Solusi referensi adalah solusi non-negatif dasar. Solusi dukungan dapat berupa non-degenerasi dan degenerasi. Solusi pendukung disebut non-degenerate jika jumlah koordinat non-nolnya sama dengan peringkat sistem, jika tidak maka akan degenerate.

Solusi yang layak, di mana fungsi tujuan mencapai nilai ekstrimnya, disebut optimal dan dilambangkan .

Sangat sulit untuk menyelesaikan masalah ini secara grafis ketika jumlah variabel lebih dari 3. Ada cara universal untuk menyelesaikan masalah pemrograman linier, yang disebut metode simpleks.

Metode simpleks adalah metode universal untuk menyelesaikan masalah LP, yang merupakan proses iteratif yang dimulai dengan satu solusi dan, dalam mencari opsi terbaik, bergerak sepanjang titik sudut dari area solusi yang layak hingga mencapai nilai optimal. .

Ini dapat digunakan untuk menyelesaikan masalah pemrograman linier apa pun.

Metode simpleks didasarkan pada gagasan peningkatan berturut-turut dari solusi yang dihasilkan.

Arti geometris dari metode simpleks adalah berpindah secara berurutan dari satu simpul polihedron kendala ke simpul tetangga, di mana fungsi tujuan mengambil nilai terbaik (atau setidaknya bukan yang terburuk) sampai solusi optimal ditemukan - simpul di mana nilai optimal tercapai fungsi tujuan (jika masalah memiliki optimal terbatas).

Jadi, memiliki sistem kendala yang direduksi menjadi bentuk kanonik (semua kendala fungsional dalam bentuk persamaan), seseorang menemukan solusi dasar dari sistem ini, hanya dengan berhati-hati untuk menemukannya sesederhana mungkin. Jika solusi dasar yang pertama kali ditemukan ternyata layak, maka diperiksa optimalitasnya. Jika tidak optimal, maka transisi dibuat ke solusi dasar lain yang tentu dapat diterima. Metode simpleks menjamin bahwa, dengan solusi baru ini, fungsi tujuan, jika tidak mencapai optimum, maka mendekatinya (atau setidaknya tidak menjauhinya). Dengan solusi dasar baru yang dapat diterima, hal yang sama dilakukan sampai ditemukan solusi yang optimal.

Proses penerapan metode simpleks melibatkan penerapan tiga elemen utamanya:

metode untuk menentukan beberapa solusi dasar yang layak awal untuk masalah tersebut;

aturan transisi ke solusi terbaik (lebih tepatnya, bukan yang terburuk);

kriteria untuk memeriksa optimalitas solusi yang ditemukan.

Metode simpleks mencakup sejumlah langkah dan dapat dirumuskan sebagai algoritma yang jelas (instruksi yang jelas untuk melakukan operasi sekuensial). Ini memungkinkan Anda untuk berhasil memprogram dan mengimplementasikannya di komputer. Masalah dengan sejumlah kecil variabel dan kendala dapat diselesaikan dengan metode simpleks secara manual.

6.1 Pendahuluan

Optimasi. Bagian 1

Metode pengoptimalan memungkinkan Anda memilih opsi desain terbaik dari semua opsi yang memungkinkan. Dalam beberapa tahun terakhir, banyak perhatian telah diberikan pada metode ini, dan sebagai hasilnya, sejumlah algoritma yang sangat efisien telah dikembangkan yang memungkinkan untuk menemukan opsi desain yang optimal menggunakan komputer digital. Bab ini menguraikan dasar-dasar teori optimasi, mempertimbangkan prinsip-prinsip yang mendasari konstruksi algoritma untuk solusi optimal, menjelaskan algoritma yang paling terkenal, dan menganalisis kelebihan dan kekurangannya.

6.2 Dasar-dasar teori optimasi

Istilah "optimasi" dalam literatur mengacu pada proses atau urutan operasi yang memungkinkan Anda untuk mendapatkan solusi yang disempurnakan. Meskipun tujuan akhir dari optimasi adalah untuk menemukan solusi terbaik, atau "optimal", seseorang biasanya harus puas dengan meningkatkan solusi yang diketahui daripada menyempurnakannya. Oleh karena itu, optimasi lebih mungkin dipahami sebagai mengejar kesempurnaan, yang mungkin tidak akan tercapai.

Mempertimbangkan beberapa sistem arbitrer yang dijelaskan oleh m persamaan dengan n yang tidak diketahui, kita dapat membedakan tiga jenis masalah utama. Jika m=n , masalahnya disebut aljabar. Masalah seperti itu biasanya memiliki satu solusi. Jika m>n, maka masalahnya didefinisikan ulang dan, sebagai aturan, tidak memiliki solusi. Akhirnya, untuk m

Sebelum melanjutkan ke pembahasan masalah optimasi, kami memperkenalkan sejumlah definisi.

Parameter desain

Istilah ini menunjukkan parameter variabel independen yang secara lengkap dan jelas mendefinisikan masalah desain yang sedang dipecahkan. Parameter desain adalah jumlah yang tidak diketahui, yang nilainya dihitung selama proses optimasi. Setiap kuantitas dasar atau turunan yang berfungsi untuk menggambarkan sistem secara kuantitatif dapat berfungsi sebagai parameter desain. Jadi, dapat diketahui nilai panjang, massa, waktu, suhu. Jumlah parameter desain mencirikan tingkat kompleksitas masalah desain ini. Biasanya jumlah parameter desain dilambangkan dengan n, dan parameter desain itu sendiri dengan x dengan indeks yang sesuai. Dengan demikian, n parameter desain dari masalah ini akan dilambangkan dengan

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

fungsi objektif

Ini adalah ekspresi yang nilainya ingin dimaksimalkan atau diminimalkan oleh insinyur. Fungsi tujuan memungkinkan Anda untuk membandingkan dua solusi alternatif secara kuantitatif. Dari sudut pandang matematika, fungsi tujuan menggambarkan beberapa (n + 1) - permukaan dimensi. Nilainya ditentukan oleh parameter desain

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

Contoh fungsi tujuan, yang sering dijumpai dalam praktik rekayasa, adalah biaya, berat, kekuatan, dimensi, efisiensi. Jika hanya ada satu parameter desain, maka fungsi tujuan dapat direpresentasikan dengan kurva pada bidang (Gbr. 6.1). Jika ada dua parameter desain, maka fungsi target akan diwakili oleh permukaan dalam ruang tiga dimensi (Gbr. 6.2). Dengan tiga atau lebih parameter desain, permukaan yang ditentukan oleh fungsi tujuan disebut hypersurfaces dan tidak dapat digambarkan.

zheniya berarti konvensional. Sifat topologi permukaan fungsi tujuan memainkan peran penting dalam proses optimasi, karena pilihan algoritma yang paling efisien tergantung pada mereka.

Fungsi tujuan dalam beberapa kasus dapat mengambil bentuk yang paling tidak terduga. Misalnya, tidak selalu mungkin untuk mengungkapkannya dalam

Gambar 1. Fungsi tujuan satu dimensi.

Gbr.6.2.Fungsi tujuan dua dimensi.

bentuk matematika tertutup, dalam kasus lain dapat

menjadi fungsi halus sepotong-sepotong. Fungsi tujuan terkadang memerlukan tabel data teknis (misalnya, tabel keadaan uap) atau mungkin diperlukan untuk melakukan eksperimen. Dalam beberapa kasus, parameter desain hanya mengambil nilai integer. Contohnya adalah jumlah gigi pada roda gigi atau jumlah baut pada flensa. Terkadang parameter desain hanya memiliki dua nilai - ya atau tidak. Parameter kualitatif, seperti kepuasan pelanggan, keandalan, estetika, sulit untuk diperhitungkan dalam proses pengoptimalan, karena hampir tidak mungkin untuk diukur. Namun, dalam bentuk apa pun fungsi tujuan disajikan, itu harus menjadi fungsi bernilai tunggal dari parameter desain.

Dalam sejumlah masalah optimasi, pengenalan lebih dari satu fungsi tujuan diperlukan. Terkadang salah satu dari mereka mungkin tidak cocok dengan yang lain. Contohnya adalah desain pesawat, ketika diperlukan untuk memberikan kekuatan maksimum, berat minimum dan biaya minimum pada saat yang bersamaan. Dalam kasus seperti itu, perancang harus memperkenalkan sistem prioritas dan menetapkan pengali tak berdimensi untuk setiap fungsi tujuan. Akibatnya, "fungsi kompromi" muncul, yang memungkinkan satu fungsi tujuan gabungan untuk digunakan dalam proses optimasi.

Mencari minimum dan maksimum

Beberapa algoritma optimasi diadaptasi untuk menemukan maksimum, yang lain untuk menemukan minimum. Namun, terlepas dari jenis masalah ekstrem yang dipecahkan, seseorang dapat menggunakan algoritma yang sama, karena masalah minimasi dapat dengan mudah diubah menjadi masalah maksimum dengan mengubah tanda fungsi tujuan menjadi kebalikannya. Teknik ini diilustrasikan pada Gambar 6.3.

Ruang desain

Ini adalah nama area yang ditentukan oleh semua n parameter desain. Ruang desain tidak sebesar yang terlihat, karena biasanya terbatas pada beberapa ruangan

kondisi yang terkait dengan esensi fisik masalah. Kendala bisa begitu kuat sehingga tugas tidak akan ada

Gbr.6.3 Mengubah tanda fungsi tujuan menjadi kebalikannya

Tugas maksimum menjadi tugas minimum.

solusi yang memuaskan. Kendala dibagi menjadi dua kelompok: kendala - persamaan dan kendala - ketidaksetaraan.

Kendala - kesetaraan

Kendala - persamaan - adalah ketergantungan antara parameter desain yang harus diperhitungkan ketika menemukan solusi. Mereka mencerminkan hukum alam, ekonomi, hak, selera yang berlaku dan ketersediaan bahan yang diperlukan. Jumlah batasan - persamaan bisa berapa saja. Mereka terlihat 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 salah satu dari hubungan ini dapat diselesaikan sehubungan dengan salah satu parameter desain, maka ini memungkinkan Anda untuk mengecualikan parameter ini dari proses pengoptimalan. Ini mengurangi jumlah dimensi ruang desain dan menyederhanakan solusi masalah.

Kendala - ketidaksetaraan

Ini adalah jenis kendala khusus yang diekspresikan oleh ketidaksetaraan. Dalam kasus umum, jumlahnya bisa berapa saja, dan semuanya memiliki 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 dicatat bahwa sangat sering, karena keterbatasan, nilai optimal dari fungsi tujuan tidak tercapai di mana permukaannya memiliki gradien nol. Seringkali solusi terbaik ada di salah satu batas domain desain.

Optimal lokal

Ini adalah nama titik dalam ruang desain di mana fungsi tujuan memiliki nilai terbesar dibandingkan dengan nilainya di semua titik lain di lingkungan terdekatnya.

Gbr.6.4 Sebuah fungsi tujuan arbitrer dapat memiliki beberapa

optimal lokal.

pada gambar. Gambar 6.4 menunjukkan fungsi tujuan satu dimensi yang memiliki dua local optima. Seringkali ruang desain mengandung banyak local optima dan harus berhati-hati agar tidak salah memilih solusi optimal untuk masalah tersebut.

Optimal Global

Optimal global adalah solusi optimal untuk seluruh ruang desain. Ini lebih baik daripada semua solusi lain yang terkait dengan local optima, dan inilah yang dicari oleh perancang. Kasus beberapa optima global yang sama yang terletak di berbagai bagian ruang desain dimungkinkan. Bagaimana masalah optimasi diajukan paling baik diilustrasikan dengan sebuah contoh.

Contoh 6.1

Biarkan diperlukan untuk merancang wadah persegi panjang dengan volume 1 m , yang dirancang untuk mengangkut serat yang tidak dikemas. Diinginkan bahwa bahan sesedikit mungkin dihabiskan untuk pembuatan wadah tersebut (dengan asumsi ketebalan dinding konstan, ini berarti luas permukaan harus minimal), karena akan lebih murah. Agar nyaman membawa wadah dengan forklift, lebarnya harus minimal 1,5 m.

Mari kita merumuskan masalah ini dalam bentuk yang nyaman untuk menerapkan algoritma optimasi.

Parameter desain: x 1 , x 2 , x 3 .

Fungsi objektif (yang perlu diminimalkan) adalah luas permukaan samping wadah:

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

Batasan - kesetaraan:

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

Batasan - ketidaksetaraan:

Masalah pemrograman linier

Pemrograman Linier (LP) adalah salah satu bagian dari pemrograman matematika - disiplin yang mempelajari masalah ekstrem (optimasi) dan mengembangkan metode untuk menyelesaikannya.

Masalah pengoptimalan adalah masalah matematika yang terdiri dalam menemukan nilai optimal (yaitu, maksimum atau minimum) dari fungsi tujuan, dan nilai-nilai variabel harus termasuk dalam area nilai yang dapat diterima (ODV) tertentu.

Secara umum, rumusan masalah ekstrem pemrograman matematika terdiri dari penentuan nilai terbesar atau terkecil dari fungsi , yang disebut fungsi objektif, di bawah kondisi (pembatasan) , di mana dan diberikan fungsi, dan diberikan konstanta. Pada saat yang sama, pembatasan berupa persamaan dan pertidaksamaan menentukan himpunan (wilayah) solusi layak (ODS), dan disebut parameter desain.

Tergantung pada jenis fungsi dan masalah pemrograman matematika dibagi menjadi beberapa kelas (linear, non-linear, cembung, integer, stokastik, pemrograman dinamis, dll).

PADA pandangan umum Masalah LP memiliki bentuk berikut:

, (5.1)

, , (5.2)

, , (5.3)

dimana , , diberikan konstanta.

Fungsi (5.1) disebut fungsi tujuan; sistem (5.2), (5.3) - oleh sistem kendala; kondisi (5.4) adalah kondisi non-negatif dari parameter desain.

Himpunan parameter desain yang memenuhi batasan (5.2), (5.3) dan (5.4) disebut solusi yang dapat diterima atau rencana.

Solusi optimal atau rencana optimal Masalah LP disebut solusi layak, di mana fungsi tujuan (5.1) mengambil nilai optimal (maksimum atau minimum).

tugas standar LP disebut masalah menemukan nilai maksimum (minimum) dari fungsi tujuan (5.1) pada kondisi (5.2) dan (5.4), dimana , , yaitu. itu. pembatasan hanya berupa pertidaksamaan (5.2) dan semua parameter desain memenuhi syarat non-negatif, dan tidak ada syarat berupa persamaan:

,

, , (5.5)

.

Tugas kanonik (utama) LP disebut masalah menemukan nilai maksimum (minimum) dari fungsi tujuan (5.1) pada kondisi (5.3) dan (5.4), dimana , , yaitu. itu. pembatasan hanya dalam bentuk persamaan (5.3) dan semua parameter desain memenuhi kondisi non-negatif, dan tidak ada kondisi dalam bentuk ketidaksetaraan:

,

.

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

Bentuk matriks dari masalah LP kanonik memiliki bentuk sebagai berikut:

Bentuk vektor dari masalah LP kanonik.