Model pengaturcaraan linear integer. Kaedah Gomori untuk menyelesaikan masalah pengaturcaraan integer. Contoh penyelesaian masalah ekonomi

Dalam pengertian sebahagian besar tugas ekonomi yang berkaitan dengan tugas pengaturcaraan linear, komponen penyelesaian mesti dinyatakan dalam integer, i.e. menjadi integer. Ini termasuk, sebagai contoh, masalah di mana pembolehubah bermaksud bilangan unit produk yang tidak boleh dibahagikan, bilangan mesin semasa memuatkan peralatan, bilangan kapal semasa mengedar di sepanjang talian, bilangan turbin dalam sistem kuasa, bilangan komputer di kompleks pengurusan dan lain-lain lagi.

Masalah linear pengaturcaraan integer dirumuskan seperti berikut: cari penyelesaian sedemikian (rancangan) saya, di mana fungsi linear

mengambil maksimum atau nilai minimum di bawah sekatan

(8.2)

(8.3)

- nombor bulat. (8.4)

Perlu diingatkan bahawa klasik masalah pengangkutan dan beberapa tugas jenis pengangkutan lain disediakan "secara automatik". penyelesaian masalah dalam integer (jika, sudah tentu, parameter keadaan adalah integer). Walau bagaimanapun, dalam kes umum, keadaan integer (8.4) ditambah kepada tugas biasa pengaturcaraan linear, dengan ketara merumitkan penyelesaiannya.

Beberapa kaedah digunakan untuk menyelesaikan masalah pengaturcaraan integer linear. Yang paling mudah ialah kaedah biasa pengaturcaraan linear. Jika komponen penyelesaian optimum bukan integer, ia dibundarkan kepada integer terdekat. Kaedah ini digunakan apabila satu unit populasi membentuk sebahagian kecil daripada jumlah keseluruhan populasi. Jika tidak, pembundaran boleh membawa kepada penyelesaian integer yang jauh daripada optimum, jadi kaedah yang dibangunkan khas digunakan.

Kaedah pengoptimuman integer boleh dibahagikan kepada tiga kumpulan utama: a) kaedah pemangkasan; b) kaedah gabungan; c) kaedah anggaran. Mari kita lihat lebih dekat kaedah pemotongan.

Kaedah keratan. Kaedah Gomori

Intipati kaedah pemangkasan ialah masalah diselesaikan terlebih dahulu tanpa keadaan integer™. Jika pelan yang terhasil adalah integer, masalah itu diselesaikan. Jika tidak, kekangan baharu ditambahkan pada kekangan tugas dengan sifat berikut:

ia mestilah linear;
hendaklah memotong pelan bukan integer optimum yang ditemui;
tidak boleh memotong sebarang pelan integer.

Kekangan tambahan dengan sifat ini dipanggil pemotongan yang betul.

Menambah setiap satu secara geometri kekangan linear sepadan dengan melukis garis lurus (hyperplane) yang memotong sebahagian daripadanya daripada poligon penyelesaian (polyhedron) bersama-sama dengan titik optimum dengan koordinat bukan integer, tetapi tidak menjejaskan mana-mana titik integer polyhedron ini. Akibatnya, polihedron larutan baharu mengandungi semua titik integer yang terkandung

dalam polyhedron asal penyelesaian, dan dengan itu penyelesaian optimum yang diperolehi dengan polyhedron ini akan menjadi integer (Rajah 8.1).

Salah satu algoritma untuk menyelesaikan masalah pengaturcaraan integer linear (8.1)-(8.4), yang dicadangkan oleh R. Gomori, adalah berdasarkan kaedah simplex dan menggunakan kaedah yang agak mudah untuk membina cutoff yang betul.

Biarkan masalah pengaturcaraan linear (8.1)-(8.3) mempunyai optimum akhir, dan pada langkah terakhir penyelesaiannya kaedah simplex persamaan berikut diperoleh menyatakan pembolehubah utama melalui pembolehubah bukan utama penyelesaian optimum:

(8.5)

jadi penyelesaian optimum kepada masalah (8.1)-(8.3) ialah i, di mana, sebagai contoh, β; – komponen bukan integer. Dalam kes ini, dapat dibuktikan bahawa ketidaksamaan yang terbentuk oleh saya- kepada persamaan sistem (8.5), mempunyai semua sifat potongan biasa.

Untuk menyelesaikan masalah pengaturcaraan linear integer (8.1)-(8.4) menggunakan kaedah Gomori, algoritma berikut digunakan.

1. Menggunakan kaedah simpleks, selesaikan masalah (8.1)-(8.3) tanpa mengambil kira keadaan integer. Jika semua komponen pelan optimum adalah integer, maka ia adalah optimum untuk masalah pengaturcaraan integer (8.1)-(8.4). Jika masalah pertama (8.1)-(8.3) tidak dapat diselesaikan (iaitu, ia tidak mempunyai optimum akhir atau keadaannya bercanggah), maka masalah kedua (8.1)-(8.4) juga tidak boleh diselesaikan.
2. Jika di antara komponen penyelesaian optimum terdapat bukan integer, maka pilih komponen yang paling besar. keseluruhan bahagian dan mengikut persamaan sistem yang sepadan (8.5) membentuk potongan yang betul (8.6).
3. Dengan memperkenalkan pembolehubah integer bukan negatif tambahan, ubah ketaksamaan (8.6) kepada persamaan setara dan masukkannya ke dalam sistem sekatan (8.2).
4. Selesaikan masalah lanjutan yang terhasil menggunakan kaedah simpleks. Jika pelan optimum yang ditemui ialah integer, maka masalah pengaturcaraan integer (8.1)–(8.4) diselesaikan. Jika tidak, kembali ke langkah 2 algoritma.

Jika masalah itu boleh diselesaikan dalam integer, maka selepas beberapa langkah terhingga (lelaran) pelan integer optimum akan ditemui.

1 Dalam ketaksamaan (8.6) terdapat simbol ( ), bermaksud bahagian pecahan nombor. Bahagian integer nombor a ialah integer terbesar [dalam] tidak melebihi a, bahagian pecahan suatu nombor– nombor (a), sama dengan perbezaan antara nombor ini dan bahagian integernya, i.e. (a) = a-[b].

Contohnya, untuk (nota, tepat -3, bukan -2) dan

Jika dalam proses menyelesaikan persamaan muncul (menyatakan pembolehubah utama dari segi bukan asas) dengan sebutan bebas bukan integer dan pekali baki integer, maka persamaan yang sepadan tidak mempunyai penyelesaian dalam integer. Dalam kes ini dan tugasan ini tidak mempunyai penyelesaian optimum integer.

8.1. Untuk membeli peralatan menyusun bijirin, petani memperuntukkan 34 den. unit Peralatan mesti diletakkan di kawasan tidak melebihi 60 meter persegi. m. Petani boleh memesan dua jenis peralatan: mesin kurang berkuasa seperti A bernilai 3 den. unit yang memerlukan kawasan pengeluaran 3 persegi. m (termasuk pas), dan produktiviti setiap syif 2 tan bijirin, dan mesin yang lebih berkuasa seperti DALAM bernilai 4 den. unit menduduki kawasan seluas 5 persegi. m, dan produktiviti setiap syif 3 tan bijirin berkualiti tinggi.

Ia dikehendaki merangka pelan pemerolehan peralatan optimum yang memastikan maksimum pencapaian keseluruhan dengan syarat petani boleh membeli tidak lebih daripada 8 mesin jenis tersebut DALAM.

Penyelesaian. Mari kita nyatakan dengan bilangan mesin, masing-masing, jenis A Dan DALAM, melalui Z – produktiviti keseluruhan. Kemudian model matematik masalah akan mengambil bentuk

(!!!8.8)

dengan sekatan:

(8.2)

- nombor bulat. (8.4)

Marilah kita membawa masalah kepada bentuk kanonik dengan memperkenalkan pembolehubah bukan negatif tambahan. Kami mendapat sistem sekatan:

(8.5)

Kami menyelesaikan masalah menggunakan kaedah simplex. Untuk kejelasan, kami menggambarkan penyelesaian secara grafik (Rajah 8.2).

Dalam Rajah. 8.2 OKLM– kawasan penyelesaian yang boleh dilaksanakan untuk masalah (8.D)–(8.3"), dihadkan oleh garis lurus (1), (2), (3) dan paksi koordinat; L(2/3; 8) – titik penyelesaian optimum, tetapi bukan integer kepada masalah (8.1")–(8.3"); (4) – garis lurus memotong penyelesaian bukan integer ini; OKNM– kawasan penyelesaian yang boleh dilaksanakan bagi masalah lanjutan (8.1")–(8.3"), (8.6"); N( 2; 7) – titik penyelesaian integer optimum.

Langkah I. Pembolehubah asas Pembolehubah bukan asas

Penyelesaian asas yang pertama ialah menganggap

saya. Nilai fungsi linear yang sepadan

Kami menukar kepada pembolehubah utama pembolehubah yang termasuk dalam ungkapan fungsi linear dengan pekali positif terbesar. Kami mencari nilai maksimum yang mungkin bagi pembolehubah yang "membolehkan"

menerima sistem sekatan berdasarkan syarat hubungan sepadan minimum:

mereka. persamaan penyelesaian (disorotkan) ialah persamaan ketiga. Pada X. 2 = 8 dalam persamaan ini X- = 0, dan pembolehubah pergi ke bukan asas X 5.

Langkah II. Pembolehubah Utama X 2, X 3, X 4.

Pembolehubah kecil.g, xy

Selepas transformasi kita dapat

Tukar kepada pembolehubah utama dan dalam yang bukan utama x4.

Langkah III. Pembolehubah utama x, X 2, X 3.

Pembolehubah bukan utama x4, x5.

Selepas transformasi kita dapat

Penyelesaian asas X., optimum untuk masalah (8.1")–(8.3") (), kerana dalam ungkapan fungsi linear

tiada pembolehubah bukan teras dengan pekali positif.

Namun, penyelesaiannya X 3 tidak memenuhi keadaan integer (8.4") Menggunakan persamaan pertama dengan pembolehubah x menerima nilai bukan integer dalam penyelesaian optimum (2/3), kami mencipta kekangan tambahan (8.6):

Sila ambil perhatian bahawa, mengikut (8.5) dan (8.6), kami mengambil bahagian pecahan ahli percuma dengan tanda yang sama, yang dia ada dalam persamaan, dan bahagian pecahan pekali bagi pembolehubah kecil x 4 dan x- – dengan tanda berlawanan.

Sejak bahagian pecahan ,

, kami menulis ketidaksamaan terakhir

(8.6")

Dengan memperkenalkan pembolehubah integer tambahan x6 ≥ 0, kita memperoleh persamaan bersamaan dengan ketaksamaan (8.6")

(8.7")

Persamaan (8.7") mesti dimasukkan dalam sistem kekangan (8.5") masalah kanonik asal, dan kemudian ulangi proses menyelesaikan masalah menggunakan kaedah simpleks berhubung dengan masalah lanjutan. Dalam kes ini, untuk mengurangkan bilangan langkah (lelaran), disyorkan untuk memperkenalkan persamaan tambahan (8.7") ke dalam sistem yang diperoleh pada langkah terakhir menyelesaikan masalah (tanpa keadaan integer).

Langkah IV. Pembolehubah Utama x v X 2, x3, χβ.

Pembolehubah bukan utama x4, x5.

Penyelesaian asas tidak dibenarkan

saya. (Perhatikan bahawa selepas memasukkan persamaan tambahan yang sepadan dengan potongan yang betul dalam sistem kekangan, penyelesaian asas yang tidak sah akan sentiasa diperolehi.)

Untuk mendapatkan penyelesaian asas yang boleh diterima, adalah perlu untuk menukar kepada pembolehubah utama, yang disertakan dengan pekali positif dalam persamaan di mana istilah bebas adalah negatif, i.e. x, atau x. (pada peringkat ini kita tidak menganggap fungsi linear). Kami menterjemah ke dalam yang asas, sebagai contoh, pembolehubah x5.

Langkah V. Pembolehubah utama ialah x, x2, x3, x5.

Pembolehubah bukan utama x4, x6.

Kami mendapat selepas transformasi

Oleh kerana tiada pembolehubah utama dengan pekali positif dalam ungkapan fungsi linear, maka X 5 adalah penyelesaian yang optimum.

Jadi, Zmax = 25 pada optimum penyelesaian integer X* = X 5 = (2; 7; 19; 0; 1; 0), i.e. prestasi maksimum 25 tan bijirin berkualiti tinggi setiap syif boleh diperolehi dengan membeli 2 mesin jenis L dan 7 mesin jenis DALAM Pada masa yang sama, kawasan yang tidak dihuni di premis itu ialah 19 meter persegi. m, baki dana yang diperuntukkan adalah sifar, rizab untuk pembelian ialah 1 mesin jenis DALAM(komponen keenam tidak mempunyai makna yang bermakna).

Komen. Untuk tafsiran geometri pada Ox, satah x2 (lihat Rajah 8.2) potongan (8.6"), pembolehubah yang termasuk di dalamnya adalah perlu X 4 dan X- ungkapkan melalui pembolehubah x dan x2. Kami memperoleh (lihat persamaan ke-2 dan ke-3 sistem sekatan (8.5"))

(lihat baris keratan (4) dalam Rajah 8.2).
8.2. Ada cukup sejumlah besar kayu balak sepanjang 3 m. Balak hendaklah dipotong kepada dua jenis bahan kerja: 1.2 dan 0.9 m panjang, dan sekurang-kurangnya 50 dan 81 keping setiap jenis bahan kerja perlu diperolehi. masing-masing. Setiap log boleh dipotong menjadi kepingan yang ditentukan dalam beberapa cara: 1) menjadi 2 keping tetapi 1.2 m; 2) untuk 1 keping 1.2 m dan 2 keping 0.9 m setiap satu; 3) untuk 3 keping 0.9 m setiap satu. Cari bilangan balak yang dipotong mengikut setiap kaedah supaya kepingan apa-apa jenis diperolehi daripada bilangan balak yang terkecil.

Penyelesaian. Mari kita nyatakan dengan X() x2, x3 bilangan kayu balak yang digergaji masing-masing menggunakan 1, 2 dan 3 kaedah. Daripada ini anda boleh mendapatkan 2xj +x2 kosong 1.2 m setiap satu dan 2x x +3x2 kosong 0.9 m setiap satu. Mari kita nyatakan jumlah bilangan log Z. Kemudian model matematik masalah akan mengambil bentuk

dengan sekatan:

Dengan memperkenalkan pembolehubah tambahan

kita mengurangkan sistem ketaksamaan kepada sistem persamaan yang setara:

(8.5")

Menyelesaikan yang diterima masalah kanonik(tanpa keadaan integer) menggunakan kaedah simpleks, pada langkah terakhir, ketiga, penyelesaian kita akan menemui ungkapan berikut bagi pembolehubah utama dan fungsi linear dari segi pembolehubah bukan asas (kami mengesyorkan agar pelajar mendapatkannya pada mereka punya).

Langkah III. Pembolehubah Utama x v X 2.

Pembolehubah bukan teras X di X A , X 5.

iaitu dengan penyelesaian yang optimum

Ternyata dua komponen penyelesaian optimum tidak memenuhi syarat integer (8.4"), dan komponen mempunyai bahagian integer terbesar X 2. Selaras dengan ∏. 2 algoritma untuk menyelesaikan masalah pengaturcaraan integer (lihat ms 166) menggunakan persamaan kedua yang mengandungi pembolehubah ini X 2, kami membuat kekangan tambahan (8.6):

Mari cari bahagian pecahan

dan tulis ketaksamaan terakhir dalam borang

(8.6")

Dengan memperkenalkan pembolehubah tambahan yang kita dapat

persamaan bersamaan dengan ketaksamaan (8.6"):

(8.7")

Mari kita nyatakan daripada (8.7") pembolehubah tambahan x6 dan masukkan persamaan yang terhasil ke dalam sistem kekangan yang kita ada pada langkah terakhir, III, untuk menyelesaikan masalah (8.1") - (8.3") (tanpa keadaan integer ).

Langkah IV. Pembolehubah Utama X{, X di X 6.

Pembolehubah bukan teras X 3, x4, X 5.

Menyelesaikan masalah lanjutan ini menggunakan kaedah simpleks (kami menjemput pelajar untuk melakukannya sendiri), kami memperoleh perkara berikut.

Langkah V. Pembolehubah utama x); X 2, x3.

Pembolehubah bukan utama x4, x5, xb.

iaitu dengan penyelesaian yang optimum

Penyelesaian optimum yang terhasil kepada masalah lanjutan (8.1")–(8.3"), (8.6") sekali lagi tidak memenuhi keadaan integer (8.4"). Mengikut persamaan pertama dengan pembolehubah Xj menerima nilai bukan integer dalam optimum

penyelesaian (), kami meninggalkan had tambahan kedua

bacaan (8.6):

yang kita ingatkan

Menggunakan pembolehubah tambahan

Kami mengurangkan ketaksamaan ini kepada persamaan yang setara, yang kami sertakan dalam sistem kekangan yang diperoleh pada langkah terakhir, V, untuk menyelesaikan masalah lanjutan (8.G")–(8.3"), (8.6") menggunakan kaedah simplex.

Langkah VI. Pembolehubah Utama x v X 2, X di X T

Pembolehubah bukan teras X 4, X-, x 6.

Meninggalkan penyelesaian masalah selanjutnya menggunakan kaedah simpleks (kami mencadangkan pelajar melakukan ini sendiri), pada langkah terakhir, VII, yang kami perolehi.

Langkah VII. Pembolehubah Utama x v X t x3, X G

Pembolehubah bukan teras x v X 6, X T

Oleh kerana tiada pembolehubah bukan asas dengan pekali negatif dalam ungkapan fungsi linear, maka X 7 – penyelesaian integer optimum kepada masalah asal.

Perlu diingatkan bahawa dalam ungkapan yang terhasil bagi fungsi linear Z tidak ada pembolehubah kecil X D) dan X 6. Ini bermakna, secara amnya, terdapat set penyelesaian optimum yang tidak terhingga (mana-mana, tidak semestinya integer), yang mana Z" = Zmjn = 46. Penyelesaian ini diperoleh untuk nilai pembolehubah bukan utama X 7 (termasuk dalam ungkapan untuk Z), sama dengan sifar(iaitu apabila X 7 = 0), dan pada mana-mana nilai pembolehubah bukan asas x5 dan X 6 (tidak termasuk dalam ungkapan untuk Z), yang sistem sekatan "membenarkan" untuk diterima: 0<лг5 X 5 ≤ 1 dan 0< x(i ≤ 1. Tetapi disebabkan keadaan integer, pembolehubah X- Dan X(> hanya boleh mengambil nilai 0 atau 1. Oleh itu masalah akan mempunyai empat penyelesaian optimum integer apabila X. dan *6 dalam sebarang kombinasi mengambil nilai 0 atau 1, dan X 7 = 0. Menggantikan nilai ini ke dalam sistem sekatan pada langkah VII, kami dapati penyelesaian optimum ini:

Kehadiran penyelesaian integer optimum alternatif memungkinkan untuk memilih salah satu daripada mereka, berpandukan kriteria tambahan yang tidak diambil kira dalam model matematik masalah. Sebagai contoh, dari keadaan masalah ini ia mengikuti bahawa menggergaji balak tidak menghasilkan sisa hanya menggunakan kaedah ke-3, oleh itu, apabila memilih salah satu daripada empat penyelesaian optimum, adalah wajar untuk memberi keutamaan kepada penyelesaian itu. X^ 3 di mana bilangan maksimum log ( X 2 = 41) digergaji tanpa sisa.

Jadi, Zmin=46 untuk penyelesaian integer optimum (5; 41; 0), (6; 39; 1), (7; 36; 3), (6; 38; 2). Apabila merekodkan penyelesaian optimum, kami hanya meninggalkan tiga komponen pertama, menyatakan bilangan log yang dipotong mengikut kaedah 1, 2 dan 3, masing-masing, dan mengecualikan empat komponen terakhir, yang tidak mempunyai makna semantik.

Kelemahan kaedah Gomori adalah keperluan untuk nilai integer untuk semua pembolehubah - kedua-dua asas (menyatakan, sebagai contoh, dalam masalah menggunakan sumber unit pengeluaran) dan tambahan (menyatakan jumlah sumber yang tidak digunakan, yang boleh menjadi pecahan).

Anda dapat melihat bahawa penyelesaian kepada masalah adalah lebih pendek.

Intipati kaedah pemangkasan ialah masalah diselesaikan terlebih dahulu tanpa keadaan integer. Jika pelan yang terhasil adalah integer, masalah itu diselesaikan. Jika tidak, kekangan baharu ditambahkan pada kekangan tugas dengan sifat berikut:

Ia harus linear;

Harus memotong pelan bukan integer optimum yang ditemui;

Tidak boleh memotong sebarang pelan integer.

Kekangan tambahan yang mempunyai sifat ini dipanggil pemotongan yang betul.

Secara geometri, penambahan setiap kekangan linear sepadan dengan melukis garis lurus (hyperplane) yang memotong sebahagian daripadanya daripada poligon penyelesaian (polyhedron) bersama-sama dengan titik optimum dengan koordinat bukan integer, tetapi tidak menjejaskan mana-mana integer. titik polihedron ini. Akibatnya, polihedron larutan baharu mengandungi semua titik integer yang terkandung dalam polihedron larutan asal dan, dengan itu, penyelesaian optimum yang diperoleh dengan polihedron ini ialah integer (Rajah 8.1).

menekan pembolehubah utama *1, *2, pembolehubah baharu Xm+1, Xm+2, ..., Xm+1, penyelesaian

Xt melalui neo-x„optimum

(8.5)

komponen bukan integer. Dalam kes ini boleh dibuktikan bahawa ketidaksamaan

(P, ) - (a," m+\)xm+1 ■ -~(at )Xn ^ 0, (* )

dibentuk oleh persamaan /th sistem (8.5), mempunyai semua sifat cutoff biasa.

Untuk menyelesaikan masalah pengaturcaraan linear integer (8.1)-(8.4) menggunakan kaedah Gomori, algoritma berikut digunakan:

1. Menggunakan kaedah simpleks, selesaikan masalah (8.1)-(8.3) tanpa mengambil kira keadaan integer. Jika semua komponen pelan optimum adalah integer, maka ia adalah optimum untuk masalah pengaturcaraan integer (8.1)-(8.4). Jika masalah pertama (8.1) -

(8.3) tidak boleh diselesaikan (iaitu, ia tidak mempunyai optimum akhir atau keadaannya bercanggah), maka masalah kedua (8.1)-(8.4) juga tidak boleh diselesaikan.

2. Jika antara komponen penyelesaian optimum terdapat bukan integer, kemudian pilih komponen dengan bahagian integer terbesar dan, menggunakan persamaan sistem yang sepadan (8.5), bentuk potongan yang betul (8.6).

3. Dengan memperkenalkan pembolehubah integer bukan negatif tambahan, ubah ketaksamaan (8.6) kepada persamaan setara

(P() - |a/ t+1 )*t+1- ■-(a|"l )xn + xn+1 > (®*^)

dan memasukkannya ke dalam sistem sekatan (8.2).

4. Selesaikan masalah lanjutan yang terhasil menggunakan kaedah simpleks. Jika pelan optimum yang ditemui ialah integer,

maka masalah pengaturcaraan integer (8.1)-(8.4) diselesaikan. Jika tidak, kembali ke langkah 2 algoritma.

Jika masalah itu boleh diselesaikan dalam integer, maka selepas beberapa langkah terhingga (lelaran) pelan integer optimum akan ditemui.

Jika dalam proses menyelesaikan persamaan muncul (menyatakan pembolehubah utama dari segi bukan asas) dengan sebutan bebas bukan integer dan pekali baki integer, maka persamaan yang sepadan tidak mempunyai penyelesaian dalam integer. Dalam kes ini, masalah ini tidak mempunyai penyelesaian optimum integer.

^8.1. Untuk membeli peralatan menyusun bijirin, petani memperuntukkan 34 den. unit Peralatan mesti diletakkan di kawasan tidak melebihi 60 meter persegi. m. Petani boleh memesan dua jenis peralatan: mesin jenis A yang kurang berkuasa berharga 3 den. unit yang memerlukan kawasan pengeluaran 3 persegi. m (termasuk pas) dan menyediakan produktiviti 2 tan bijirin setiap syif, dan mesin jenis B yang lebih berkuasa berharga 4 den. unit menduduki kawasan seluas 5 persegi. m dan menyediakan produktiviti 3 tan bijirin berkualiti tinggi setiap syif.

Adalah perlu untuk merangka pelan optimum untuk membeli peralatan yang memastikan produktiviti keseluruhan maksimum, dengan syarat petani boleh membeli tidak lebih daripada 8 mesin jenis B.

Penyelesaian. Mari kita nyatakan dengan x\, x2 bilangan mesin jenis A dan B, masing-masing, dan dengan Z jumlah produktiviti. Kemudian model matematik masalah akan mengambil bentuk:

Dalam Rajah. 8.2 OKM - kawasan penyelesaian yang boleh dilaksanakan untuk masalah (8.1") - (8.3"), dihadkan oleh garis lurus (1), (2), (3) dan paksi koordinat; />(2/3; 8) - titik penyelesaian optimum, tetapi bukan integer kepada masalah (8.1") - (8.3"); (4) - garis lurus memotong penyelesaian bukan integer ini; 0№М - kawasan penyelesaian yang boleh dilaksanakan bagi masalah lanjutan (8.1’) - (8.3’), (8.61); M2; 7) - titik penyelesaian integer optimum.

Langkah I. Pembolehubah utama x3, x4, *5; pembolehubah bukan asas X\, X2.

x3	= 60 -	Zh! - 5x2,
x4	= 34 -	Zx) - 4x2,
x5	= 8	- *2>
	Z = 2x)	+ Zx2.

Penyelesaian asas pertama X\ = (0; 0; 60; 34; 8) boleh diterima. Nilai fungsi linear sepadan = 0.

Kami menterjemah ke dalam pembolehubah utama pembolehubah XI, yang termasuk dalam ungkapan fungsi linear dengan pekali positif terbesar. Kami mencari nilai maksimum yang mungkin bagi pembolehubah xi, yang sistem sekatan "membenarkan" untuk diterima, dari keadaan minimum hubungan yang sepadan:

Хг = 1ШП|т;т;Т| = 8,

mereka. persamaan penyelesaian (disorotkan) ialah persamaan ketiga. Apabila *2 = 8 dalam persamaan ini X5 = 0, dan pembolehubah X5 menjadi bukan asas.

Langkah II. Pembolehubah utama x2, x3, x*; pembolehubah bukan utama Xx X5.

{

(8.6)

Dengan memperkenalkan pembolehubah integer tambahan x6 > O, kita memperoleh persamaan bersamaan dengan ketaksamaan (8.6")

~1*5 + Xb = °" ^8"7 ^

Langkah IV. Pembolehubah asas X), *2, xs> *b‘> pembolehubah bukan asas *1, *2-

X1 = z - 3*4 +

x3 = 18 + x4 +___ x5,

x6 - + ^x4 + z"x5-

Penyelesaian asas X4 = (y; 8; 18; 0; 0; -y) tidak boleh diterima. (Perhatikan bahawa selepas memasukkan persamaan tambahan yang sepadan dengan potongan yang betul dalam sistem kekangan, penyelesaian asas yang tidak sah akan sentiasa diperolehi.)

Untuk mendapatkan penyelesaian asas yang boleh diterima, adalah perlu untuk menukar kepada pembolehubah utama, yang disertakan dengan pekali positif dalam persamaan di mana istilah bebas adalah negatif, i.e. *1 atau x$ (pada peringkat ini kami tidak menganggap fungsi linear). Kami menterjemah ke dalam yang asas, sebagai contoh, pembolehubah X5.

Langkah V. Pembolehubah utama X\, X2, X3, X5; pembolehubah bukan asas R], X £

Selepas transformasi kita dapat:

LG| = 2 - x4 + 2x6,

*2 = 7 + 2х* ~ 2Х("

x3 = 19 + -x4 + -x6,

*5 = 1 - 2х* + 2Х6’

2 = 25-|x4--|x6.

^5 =(2; 7; 19; 0; 1;0);^ = 25.

Oleh kerana tiada pembolehubah utama dengan pekali positif dalam ungkapan fungsi linear, X5 ialah penyelesaian optimum.

Jadi, 2maks = 25 untuk penyelesaian integer optimum X* - X$ =(2; 7; 19; 0; 1; 0), i.e. produktiviti maksimum 25 tan bijirin berkualiti tinggi setiap syif boleh diperolehi dengan membeli 2 mesin jenis A dan 7 mesin jenis B\ manakala kawasan yang tidak dihuni premis adalah 19 meter persegi. m, baki dana yang diperuntukkan adalah sama dengan 0, dalam rizab untuk pembelian terdapat 1 mesin jenis B (komponen keenam tidak mempunyai makna yang bermakna).

Komen. Untuk tafsiran geometri pada satah Ox\Xr (lihat Rajah 8.2) potongan (8.6"), adalah perlu untuk menyatakan pembolehubah x4 dan x$ termasuk di dalamnya melalui pembolehubah XI dan x2. Kami memperoleh (lihat Persamaan ke-2 dan ke-3 sistem kekangan (8.5")):

y - y (34 - 3x, - 4x2) - y (8 - x2) £ 0 atau x, + 2x2 £ 16.

(lihat baris keratan (4) dalam Rajah 8.2)>

^8.2. Terdapat bilangan balak yang agak besar sepanjang 3 m. Balak hendaklah dipotong kepada dua jenis kosong: 1.2 m panjang dan 0.9 m panjang, dan sekurang-kurangnya 50 keping setiap jenis perlu diperolehi. dan 81 pcs. masing-masing. Setiap log boleh dipotong ke dalam tempat kosong yang ditentukan dalam beberapa cara: 1) menjadi 2 kosong 1.2 m setiap satu; 2) untuk 1 keping 1.2 m setiap satu dan 2 keping 0.9 m setiap satu; 3) untuk 3 keping 0.9 m setiap satu. Cari bilangan kayu balak,

digergaji oleh setiap kaedah, supaya apa-apa jenis bahan kerja boleh diperolehi daripada bilangan kayu yang paling kecil.

Penyelesaian. Mari kita nyatakan dengan х\, хі, хм, bilangan log yang dipotong mengikut kaedah 1, 2 dan 3. Daripada mereka anda boleh mendapatkan 2хі + *2 kosong 1.2 m setiap satu dan 2l\ + 3x2 kosong 0.9 m setiap satu Biarkan kami menandakan jumlah bilangan log sebagai I. Kemudian model matematik masalah akan mengambil bentuk:

I 2x, + x2 - x4 = 50,+ (?у), di mana [y] - keseluruhan bahagian dan (y) = U ~ [y] ~ pecahan.

[h] Kami mendapati penyelesaian asas yang boleh diterima, mempertimbangkan baris baru permisif, iaitu. saya = P + 1.

a) Jika semua pekali uc> 0, maka masalah tidak mempunyai penyelesaian (iaitu masalah integer diselesaikan).
b) Jika tidak, cari indeks Kepada seperti itu

(kriteria kemasukan untuk asas baru). Perhatikan bahawa pilihan elemen penyelesaian diDan* tidak mengubah tanda kriteria Aj.

[4] Jika dalam meja baru terdapat sekurang-kurangnya satu x 3 s dan ulangi prosedur ini seberapa banyak yang perlu.

[~5~| Jika penyelesaian optimum yang terhasil adalah integer, maka masalah itu diselesaikan. Jika tidak, anda perlu kembali ke titik.

Contoh 4.6.1. Selesaikan masalah integer menggunakan kaedah Gomori

Penyelesaian. Selepas menambah pembolehubah tambahan, kami mempunyai masalah pengaturcaraan linear berikut dalam bentuk standard:

dengan matriks

Jadual 1


	X4

Kepada= 1 T

Dengan menggunakan kaedah putaran, isikan jadual berikut. Elemen peleraian - 6*.

jadual 2		X 2



	„ _ 1 DANZ ~_3_

k" = 2 T

Elemen peleraian - 1/2*.

X masuk^0). Oleh itu, atur cara (xi = 11/3, X 2 = 5) akan memberikan maksimum fungsi ekonomi z, sama dengan 1370/3 = 45b|, t.s. z= z maks = 456§. "

Sejak ini program yang optimum bukan integer, kami menggunakan algoritma Gomori untuk mencari program optimum integer. Sebagai rentetan atas dasar yang kita bentuk garisan tambahan Daripada bahagian pecahan semua elemen, pilih baris kedua (indeks 7’ = 1). Mari kita isi jadual 3", menambah pada jadual 3 baris tambahan (4.14) dengan bahagian pecahan untuk pembolehubah tambahan Ж5 dan lajur tambahan. Kami mendapat

k" = 4 T

Selepas menambah baris baharu, jadual simpleks 3" tidak lagi sepadan dengan penyelesaian asas yang boleh diterima untuk masalah yang diterangkan. Kami menemui penyelesaian asas yang boleh diterima, dengan mengambil kira baris baharu itu sedang diselesaikan, iaitu /" = 5.

Kami mencari lajur penyelesaian, i.e. indeks kepada" seperti itu

(kriteria untuk memasuki asas baru). Elemen peleraian - (-2/3*). Ambil perhatian bahawa pilihan elemen penyelesaian sedemikian tidak mengubah tanda kriteria Aj.

Mari kita isi jadual simpleks 4.

Jadual 4		X2

	X2

Nilai semua kriteria ^ 0, ( X masuk^0). Oleh itu, atur cara (xi = 3, x 2 = 6, x±= 1) memberikan maksimum fungsi ekonomi r sama dengan 450, t.s. z = zma^= 450. Atur cara optimum ini ialah integer. ?

Contoh 4.6.2. Selesaikan masalah integer menggunakan kaedah Gomori

Penyelesaian. Terdapat masalah pengaturcaraan linear dengan matriks

Mari kita isi jadual simplex dengan atur cara awal.

Jadual 1

Kepada= 1 T

Dengan menggunakan kaedah putaran, isikan jadual berikut. Elemen peleraian - 1*.

jadual 2				X2

Unsur permisif - 5*.

Jadual 3

Nilai semua kriteria ^ 0, ( X masuk^0). Akibatnya, program (xi = 12/5, 24 = 1/5, 25 = 28/5) memberikan minimum fungsi ekonomi r sama dengan -11/5 = -2.2, i.e. z =

~min = -2.2.

Memandangkan atur cara optimum ini bukan satu integer, kami menggunakan algoritma Gomori untuk mencari program optimum integer. Sebagai rentetan yang berdasarkannya kami membentuk rentetan tambahan daripada bahagian pecahan unsur ss, kami memilih, sebagai contoh, baris ketiga (indeks r = 5) dengan bahagian pecahan maksimum. Mari kita isi jadual 3" dengan menambah baris tambahan (4.14) pada jadual 3 dengan bahagian pecahan baris ketiga untuk pembolehubah tambahan xq (baris ini membolehkan anda memotong bahagian kawasan program yang mengandungi titik dengan koordinat bukan berangka) dan lajur tambahan. Kita mendapatkan

Jadual 3"





		G - -DAN

k" = 3 T

Selepas menambah baris baharu, jadual simpleks 3" tidak lagi sepadan dengan penyelesaian asas yang boleh diterima untuk masalah yang diterangkan. Kami mendapati penyelesaian asas yang boleh diterima, memandangkan baris baharu itu sedang diselesaikan, i.e. saya" = 6.

Kami mencari lajur penyelesaian, i.e. indeks kepada" seperti itu

(kriteria untuk memasuki asas baru). Elemen peleraian - (-3/5*). Ambil perhatian bahawa pilihan elemen penyelesaian sedemikian tidak mengubah tanda kriteria Aj.

Mari kita isi jadual simpleks 4.

Jadual 4

Nilai semua kriteria ^ 0, ( X masuk^0). Oleh itu program (x = 2, X2 = 0, xs = 1, X 4 = 0, f 5 = 5) akan memberikan minimum fungsi ekonomi z 9 sama dengan (-2), t.s. z =-min = - 2. Aturcara optimum ini ialah integer. ?

Masalah 4.6.1. Selesaikan masalah integer menggunakan kaedah Gomori