Kaedah Gomori digunakan untuk mencari penyelesaian integer kepada masalah pengaturcaraan linear.
Biarlah ia dijumpai penyelesaian masalah LP: . Penyelesaian L i akan menjadi integer jika mereka. . (βi) - pecahan penyelesaian optimum bukan integer x i, (d i) ialah bahagian pecahan pembolehubah bukan asas. Nisbah ini menentukan (lihat rajah).

Tujuan perkhidmatan. Kalkulator dalam talian digunakan untuk menyelesaikan masalah pengaturcaraan linear integer menggunakan kaedah cutoff. Semasa penyelesaian, jadual simpleks digunakan. (lihat contoh).

Arahan. Pilih bilangan pembolehubah dan bilangan baris (bilangan kekangan), klik Seterusnya. Penyelesaian yang terhasil disimpan dalam Fail perkataan(lihat contoh penyelesaian menggunakan kaedah Gomori). Selain itu, templat penyelesaian dibuat dalam format Excel.

Bilangan pembolehubah 2 3 4 5 6 7 8 9 10
Bilangan baris (bilangan sekatan) 2 3 4 5 6 7 8 9 10

Pada masa yang sama, sekatan seperti x i ≥ 0 jangan ambil kira.

Jenis algoritma Gomori

1. Algoritma pertama Gomori untuk menyelesaikan masalah integer sepenuhnya.
2. Algoritma kedua Gomori untuk masalah pengaturcaraan linear separa integer.

Algoritma Gomori untuk masalah integer penuh termasuk langkah-langkah berikut:

1. Masalah pengaturcaraan linear diselesaikan tanpa mengambil kira integer.
2. Antara nombor pecahan unsur dengan bahagian pecahan terbesar dipilih dan disusun sekatan tambahan.
3. Ketaksamaan diubah menjadi persamaan dengan memperkenalkan pembolehubah bukan negatif tambahan.
4. Masalah yang terhasil diselesaikan menggunakan kaedah dwi simpleks.

Jika, semasa proses penyelesaian, persamaan dengan sebutan bebas bukan integer b i dan pekali integer a ij muncul dalam jadual simpleks, maka tugasan ini tidak mempunyai penyelesaian optimum integer.

Contoh. Persatuan Penyelidikan dan Pengeluaran Strela terlibat dalam pembuatan komponen untuk perusahaan kompleks industri ketenteraan. Dalam pembuatan produk jenis A dan jenis B, keluli dan logam bukan ferus digunakan. Proses teknologi juga termasuk pemprosesan produk pada mesin pelarik dan pengilangan. Mengikut piawaian teknologi, pengeluaran satu produk jenis A dan satu produk jenis B memerlukan sejumlah bahan mentah dan jumlah jam mesin tertentu untuk diproses pada mesin di bengkel. Data teknologi proses pengeluaran diberikan dalam jadual.
Dalam masa sebulan, bengkel NPO Strela telah sumber yang terhad mengikut bahan mentah dan mengikut masa bekerja di kedai pengeluaran (lihat jadual). Keuntungan daripada penjualan satu produk jenis A ialah 100 rubel, dan dari unit produk jenis B - 250 rubel.

	Bahan mentah		Bekerja di bengkel, jam mesin		Untung daripada jualan, gosok.
	Logam bukan ferus	Keluli	Berpusing berfungsi	Kerja pengilangan
Produk A	10	25	41	90	100
Produk B	30	25	90	50	250
Sumber	4500	6250	14100	18000

Cari pelan pengeluaran optimum untuk NPO Strela (kuantiti jenis produk A dan jenis B - integer) yang memberikan keuntungan terbesar.

Penyelesaian.
ekonomi model matematik tugasan.
x 1 - rancangan pengeluaran untuk produk jenis A, x 2 - rancangan pengeluaran untuk produk jenis B,
x 1, x 2 ialah integer.
Had Sumber
10x 1 + 30x 2 ≤ 4500
25x 1 + 25x 2 ≤ 6250
41x 1 + 90x 2 ≤ 14100
90x 1 + 50x 2 ≤ 18000
Fungsi objektif
100x 1 + 250x 2 → maks

Mari kita selesaikan masalah pengaturcaraan linear terus menggunakan kaedah simpleks. Hasilnya, kami memperoleh pelan optimum berikut:

Asas	B	x 1	x 2	x 3	x 4	x 5	x 6
x 2	1450 / 11	0	1	41 / 330	0	-1 / 33	0
x 4	17500 / 11	0	0	245 / 66	1	-50 / 33	0
x 1	600 / 11	1	0	-3 / 11	0	1 / 11	0
x 6	6500	0	0	55 / 3	0	-20 / 3	1
F(X3)	422500 / 11	0	0	125 / 33	0	50 / 33	0

x 1 = 54 6 / 11 , x 2 = 131 9 / 11
F(X) = 250 131 9 / 11 + 100 54 6 / 11 = 38409 1 / 11

Pelan optimum yang terhasil bukan integer, jadi kami gunakan Kaedah Gomori. Bahagian pecahan terbesar adalah dalam persamaan kedua untuk pembolehubah x 4 (10 / 11). Kami membuat sekatan tambahan:
q 2 - q 21 x 1 - q 22 x 2 - q 23 x 3 - q 24 x 4 - q 25 x 5 - q 26 x 6 ≤0
q 2 = b 2 - = 1590 10 / 11 - 1590 = 10 / 11
q 2 1 = a 2 1 - = 0 - 0 = 0
q 2 2 = a 2 2 - = 0 - 0 = 0
q 2 3 = a 2 3 - = 3 47 / 66 - 3 = 47 / 66
q 2 4 = a 2 4 - = 1 - 1 = 0
q 2 5 = a 2 5 - = -1 17 / 33 + 2 = 16 / 33
q 2 6 = a 2 6 - = 0 - 0 = 0

10 / 11 - 47 / 66 x 3 - 16 / 33 x 5 ≤ 0

10 / 11 - 47 / 66 x 3 - 16 / 33 x 5 + x 7 = 0

Kerana ia kaedah dwi simpleks digunakan untuk mencari minimum fungsi objektif, kita membuat penjelmaan F(x) = -F(X).

Asas	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	1450 / 11	0	1	41 / 330	0	-1 / 33	0	0
x 4	17500 / 11	0	0	245 / 66	1	-50 / 33	0	0
x 1	600 / 11	1	0	-3 / 11	0	1 / 11	0	0
x 6	6500	0	0	55 / 3	0	-20 / 3	1	0
x 7	-10 / 11	0	0	-47 / 66	0	-16 / 33	0	1
F(X0)	-422500 / 11	0	0	-125 / 33	0	-50 / 33	0	0

Lelaran pertama Gomori. 1. Menyemak kriteria optimum. Pelan dalam jadual simplex ialah pelan pseudo, jadi kami menentukan baris dan lajur utama.
2. Definisi pembolehubah bebas baharu. Antara nilai negatif pembolehubah asas, kami memilih yang terbesar dalam nilai mutlak. Garis pendahuluan akan menjadi baris kelima, dan pembolehubah x 7 harus diterbitkan daripada asas.
3. Definisi pembolehubah asas baharu. Nilai minimumθ sepadan dengan lajur kelima, i.e. pembolehubah x 5 mesti dimasukkan ke dalam asas. Di persimpangan baris dan lajur utama terdapat elemen penyelesaian (RE) bersamaan dengan (-16 / 33).

Asas	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	131 9 / 11	0	1	41 / 330	0	-1 / 33	0	0
x 4	1590 10 / 11	0	0	3 47 / 66	1	-1 17 / 33	0	0
x 1	54 6 / 11	1	0	-3 / 11	0	1 / 11	0	0
x 6	6500	0	0	18 1 / 3	0	-6 2 / 3	1	0
x 7	-10 / 11	0	0	-47 / 66	0	-16 / 33	0	1
F(X0)	-38409 1 / 11	0	0	-3 26 / 33	0	-1 17 / 33	0	0
θ		-	-	-3 26 / 33: (-47 / 66) = 5 15 / 47	-	-1 17 / 33: (-16 / 33) = 3 1 / 8	-	-

4. Kami mengira semula jadual simpleks menggunakan kaedah Jordano-Gauss.

Asas	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	1055 / 8	0	1	27 / 160	0	0	0	-1 / 16
x 4	6375 / 4	0	0	95 / 16	1	0	0	-25 / 8
x 1	435 / 8	1	0	-13 / 32	0	0	0	3 / 16
x 6	13025 / 2	0	0	225 / 8	0	0	1	-55 / 4
x 5	15 / 8	0	0	47 / 32	0	1	0	-33 / 16
F(X0)	-153625 / 4	0	0	-25 / 16	0	0	0	-25 / 8

Pelan optimum yang terhasil mengandungi nombor pecahan. Menggunakan persamaan pertama dengan pembolehubah x2, yang menerima nilai bukan integer dalam pelan optimum dengan bahagian pecahan terbesar 7/8, kami mencipta kekangan tambahan:
q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 ≤0
q 1 = b 1 - = 131 7 / 8 - 131 = 7 / 8


q 1 3 = a 1 3 - = 27 / 160 - 0 = 27 / 160



q 1 7 = a 1 7 - = -1 / 16 + 1 = 15 / 16
Sekatan tambahan mempunyai bentuk:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 ≤ 0
Mari kita ubah ketaksamaan yang terhasil ke dalam persamaan:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 + x 8 = 0
yang pekalinya kami perkenalkan baris tambahan kepada yang optimum jadual simplex.

Asas	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	1055 / 8	0	1	27 / 160	0	0	0	-1 / 16	0
x 4	6375 / 4	0	0	95 / 16	1	0	0	-25 / 8	0
x 1	435 / 8	1	0	-13 / 32	0	0	0	3 / 16	0
x 6	13025 / 2	0	0	225 / 8	0	0	1	-55 / 4	0
x 5	15 / 8	0	0	47 / 32	0	1	0	-33 / 16	0
x 8	-7 / 8	0	0	-27 / 160	0	0	0	-15 / 16	1
F(X0)	-153625 / 4	0	0	-25 / 16	0	0	0	-25 / 8	0

Lelaran kedua Gomroya. 1. Menyemak kriteria optimum. Pelan dalam jadual simplex ialah pelan pseudo, jadi kami menentukan baris dan lajur utama.
2. Definisi pembolehubah bebas baharu. Di antara nilai negatif pembolehubah asas, yang terbesar dalam nilai mutlak ialah pembolehubah x8. Ia harus diperoleh daripada asas.
3. Nilai minimum θ sepadan dengan lajur ketujuh, i.e. pembolehubah x 7 mesti dimasukkan ke dalam asas.

Asas	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	131 7 / 8	0	1	27 / 160	0	0	0	-1 / 16	0
x 4	1593 3 / 4	0	0	5 15 / 16	1	0	0	-3 1 / 8	0
x 1	54 3 / 8	1	0	-13 / 32	0	0	0	3 / 16	0
x 6	6512 1 / 2	0	0	28 1 / 8	0	0	1	-13 3 / 4	0
x 5	1 7 / 8	0	0	1 15 / 32	0	1	0	-2 1 / 16	0
x 8	-7 / 8	0	0	-27 / 160	0	0	0	-15 / 16	1
F(X0)	-38406 1 / 4	0	0	-1 9 / 16	0	0	0	-3 1 / 8	0
θ		-	-	-1 9 / 16: (-27 / 160) = 9 7 / 27	-	-	-	-3 1 / 8: (-15 / 16) = 3 1 / 3	-

4. Lakukan transformasi potongan Gomori Baharu.

Asas	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	1979 / 15	0	1	9 / 50	0	0	0	0	-1 / 15
x 4	4790 / 3	0	0	13 / 2	1	0	0	0	-10 / 3
x 1	271 / 5	1	0	-11 / 25	0	0	0	0	1 / 5
x 6	19576 / 3	0	0	153 / 5	0	0	1	0	-44 / 3
x 5	19 / 5	0	0	46 / 25	0	1	0	0	-11 / 5
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-16 / 15
F(X0)	-115210 / 3	0	0	-1	0	0	0	0	-10 / 3

Pelan optimum mengandungi nombor pecahan. Bahagian pecahan terbesar pembolehubah ialah x 2 (14 / 15). Kami mencipta kekangan tambahan: q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 - q 18 x 8 ≤0
q 1 = b 1 - = 131 14 / 15 - 131 = 14 / 15
q 1 1 = a 1 1 - = 0 - 0 = 0
q 1 2 = a 1 2 - = 1 - 1 = 0
q 1 3 = a 1 3 - = 9 / 50 - 0 = 9 / 50
q 1 4 = a 1 4 - = 0 - 0 = 0
q 1 5 = a 1 5 - = 0 - 0 = 0
q 1 6 = a 1 6 - = 0 - 0 = 0
q 1 7 = a 1 7 - = 0 - 0 = 0
q 1 8 = a 1 8 - = -1 / 15 + 1 = 14 / 15
Sekatan tambahan mempunyai bentuk:
14 / 15 - 9 / 50 x 3 - 14 / 15 x 8 ≤ 0
Mari kita ubah ketaksamaan yang terhasil ke dalam persamaan:
14 / 15 - 9 / 50 x 3 - 14 / 15 x 8 + x 9 = 0
pekali yang akan dimasukkan sebagai garis tambahan ke dalam jadual simplex optimum.

Asas	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	1979 / 15	0	1	9 / 50	0	0	0	0	-1 / 15	0
x 4	4790 / 3	0	0	13 / 2	1	0	0	0	-10 / 3	0
x 1	271 / 5	1	0	-11 / 25	0	0	0	0	1 / 5	0
x 6	19576 / 3	0	0	153 / 5	0	0	1	0	-44 / 3	0
x 5	19 / 5	0	0	46 / 25	0	1	0	0	-11 / 5	0
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-16 / 15	0
x 9	-14 / 15	0	0	-9 / 50	0	0	0	0	-14 / 15	1
F(X0)	-115210 / 3	0	0	-1	0	0	0	0	-10 / 3	0

Lelaran ketiga dengan kaedah Gomori. Pembolehubah x 9 harus diterbitkan daripada asas. Nilai minimum θ sepadan dengan lajur kelapan, i.e. pembolehubah x 8 mesti dimasukkan ke dalam asas.

Asas	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	131 14 / 15	0	1	9 / 50	0	0	0	0	-1 / 15	0
x 4	1596 2 / 3	0	0	6 1 / 2	1	0	0	0	-3 1 / 3	0
x 1	54 1 / 5	1	0	-11 / 25	0	0	0	0	1 / 5	0
x 6	6525 1 / 3	0	0	30 3 / 5	0	0	1	0	-14 2 / 3	0
x 5	3 4 / 5	0	0	1 21 / 25	0	1	0	0	-2 1 / 5	0
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-1 1 / 15	0
x 9	-14 / 15	0	0	-9 / 50	0	0	0	0	-14 / 15	1
F(X0)	-38403 1 / 3	0	0	-1	0	0	0	0	-3 1 / 3	0
θ		-	-	-1: (-9 / 50) = 5 5 / 9	-	-	-	-	-3 1 / 3: (-14 / 15) = 3 4 / 7	-

4. Lakukan penukaran.

Asas	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	132	0	1	27 / 140	0	0	0	0	0	-1 / 14
x 4	1600	0	0	50 / 7	1	0	0	0	0	-25 / 7
x 1	54	1	0	-67 / 140	0	0	0	0	0	3 / 14
x 6	6540	0	0	234 / 7	0	0	1	0	0	-110 / 7
x 5	6	0	0	317 / 140	0	1	0	0	0	-33 / 14
x 7	2	0	0	27 / 70	0	0	0	1	0	-8 / 7
x 8	1	0	0	27 / 140	0	0	0	0	1	-15 / 14
F(X0)	-38400	0	0	-5 / 14	0	0	0	0	0	-25 / 7

Penyelesaiannya ternyata integer. Pelan integer optimum boleh ditulis seperti berikut: x 1 = 54, x 2 = 132. F(X) = 38400

Tafsiran ekonomi dan geometri masalah pengaturcaraan integer. Masalah melampau yang pembolehubahnya hanya mengambil nilai integer dipanggil masalah pengaturcaraan integer.

Dalam model matematik masalah integer pengaturcaraan kedua-dua fungsi objektif dan fungsi dalam sistem kekangan boleh linear, tak linear dan bercampur. Marilah kita mengehadkan diri kita kepada kes apabila Fungsi objektif dan sistem kekangan masalah adalah linear.

Contoh 20.

Ia telah memutuskan untuk memasang peralatan tambahan di bengkel perusahaan, yang mana ruang telah diperuntukkan. Sebuah perusahaan boleh membelanjakan 10 ribu rubel untuk pembelian peralatan, dan ia boleh membeli dua jenis peralatan. Satu set peralatan jenis I berharga 1,000 rubel, dan jenis II - 3,000 rubel. Pembelian satu set peralatan jenis I membolehkan anda meningkatkan output pengeluaran setiap syif sebanyak 2 unit, dan satu set peralatan jenis II – sebanyak 4 unit. Mengetahui bahawa memasang satu set peralatan jenis I memerlukan 2 m 2 kawasan, dan peralatan jenis II memerlukan 1 m 2 kawasan, tentukan set peralatan tambahan sedemikian yang memungkinkan untuk memaksimumkan output pengeluaran

Penyelesaian. Mari kita cipta model matematik masalah. Mari kita andaikan bahawa perusahaan akan membeli x 1 set peralatan jenis I dan set peralatan jenis II. Kemudian pembolehubah x 1 dan mesti memenuhi ketaksamaan berikut:

Jika perusahaan membeli jumlah peralatan yang ditentukan, maka jumlah peningkatan dalam output akan menjadi

Mengikut kandungan ekonominya, pembolehubah x 1 dan hanya boleh mengambil nilai integer bukan negatif, i.e.

x 1 , – integer. (73)

Oleh itu, kita sampai kepada perkara berikut masalah matematik: cari nilai maksimum fungsi linear(71) apabila syarat (70), (72), dan (73) dipenuhi. Memandangkan tidak diketahui hanya boleh mengambil nilai integer, masalah (70) – (73) ialah masalah pengaturcaraan integer. Oleh kerana bilangan yang tidak diketahui dalam masalah adalah dua, penyelesaian kepada masalah ini boleh didapati menggunakan tafsiran geometrinya. Untuk melakukan ini, pertama sekali, kita akan membina poligon penyelesaian kepada masalah yang terdiri daripada menentukan nilai maksimum fungsi linear (71) apabila keadaan (70) dan (72) dipenuhi (Rajah 11). Koordinat semua titik poligon penyelesaian yang dibina OAEVS memuaskan sistem ketaksamaan linear(70) dan syarat bukan negatif pembolehubah (72). Pada masa yang sama, keadaan (73), iaitu keadaan integriti pembolehubah berpuas hati dengan koordinat hanya 12 mata yang ditandakan dalam Rajah. 11. Untuk mencari titik yang koordinatnya menentukan penyelesaian kepada masalah asal, gantikan poligon OABC poligon OKEMNF, mengandungi semua titik yang sah dengan koordinat integer dan sedemikian rupa sehingga koordinat setiap bucu adalah nombor integer. Ini bermakna jika kita mencari titik maksimum fungsi (71) pada poligon OKEMNF, maka koordinat titik ini akan menentukan rancangan optimum untuk masalah tersebut.

Untuk melakukan ini, kami juga akan membina garis lurus yang melalui poligon penyelesaian OKEMNF(nombor 12 diambil sewenang-wenangnya). Kami menggerakkan garisan yang dibina ke arah vektor sehingga ia melalui titik sepunya terakhir dengan poligon yang diberikan. Koordinat titik ini menentukan pelan optimum, dan nilai fungsi objektif padanya adalah maksimum.

DALAM dalam kes ini titik yang diperlukan ialah E(1; 3), di mana fungsi objektif mengambil nilai maksimum C, oleh itu, koordinat titik E tentukan rancangan optimum untuk masalah (70) – (73). Selaras dengan rancangan ini, perusahaan harus membeli satu set peralatan jenis 1 dan tiga set peralatan jenis II. Ini akan menyediakan perusahaan dengan sekatan sedia ada pada ruang pengeluaran dan dana pembesaran maksimum keluaran pengeluaran bersamaan dengan 14 unit. setiap syif.

Contoh 21.

Untuk melaksanakan kerja boleh digunakan P mekanisme. Prestasi i-mekanisme ke-ketika melaksanakan j – kerja ke adalah sama dengan . Dengan mengandaikan bahawa setiap mekanisme boleh digunakan hanya pada satu kerja dan setiap kerja boleh dilakukan dengan hanya satu mekanisme, tentukan penugasan mekanisme kepada pekerjaan yang memastikan prestasi maksimum. Bina satu model matematik bagi masalah tersebut.

Penyelesaian. Mari kita perkenalkan pembolehubah x ij yang nilainya sama dengan 1 jika, apabila melaksanakan i-th kerja yang digunakan j – mekanisme ke-, dan sama dengan 0 sebaliknya. Kemudian syarat untuk menggunakan setiap mekanisme pada hanya satu kerja dinyatakan oleh kesamaan

(74)

dan syarat untuk melaksanakan kerja hanya dengan satu mekanisme - kesamaan

(75)

Oleh itu, tugasnya adalah untuk menentukan nilai-nilai yang tidak diketahui tersebut , sistem persamaan (74) dan (75) yang memuaskan dan keadaan (76), di mana nilai maksimum fungsi dicapai

Masalah yang dirumuskan ialah masalah pengaturcaraan integer.

Menentukan rancangan optimum untuk masalah pengaturcaraan integer. Mari kita pertimbangkan masalah pengaturcaraan integer di mana kedua-dua fungsi objektif dan fungsi dalam sistem kekangan adalah linear. Dalam hal ini, kami merumuskan masalah pengaturcaraan linear asas di mana pembolehubah hanya boleh mengambil nilai integer. Secara umum, masalah ini boleh ditulis seperti berikut: cari maksimum fungsi

dalam keadaan

(79)

– keseluruhan (81)

Jika kita mencari penyelesaian kepada masalah (78) – (81) kaedah simplex, maka ia mungkin atau mungkin tidak integer (contoh, penyelesaian yang sentiasa integer, ialah masalah pengangkutan). Dalam kes umum, untuk menentukan rancangan optimum untuk masalah (78) – (81) kaedah khas diperlukan. Pada masa ini, terdapat beberapa kaedah sedemikian, yang paling terkenal adalah Kaedah Gomori, yang berdasarkan kaedah simpleks yang diterangkan di atas.

Kaedah Gomori. Mencari penyelesaian kepada masalah pengaturcaraan integer menggunakan kaedah Gomori bermula dengan menentukan pelan optimum masalah (78) – (80) menggunakan kaedah simplex, tanpa mengambil kira integriti pembolehubah. Sebaik sahaja pelan ini ditemui, komponennya disemak. Jika tiada nombor pecahan antara komponen, maka pelan yang ditemui adalah pelan optimum untuk masalah pengaturcaraan integer (78) – (81). Jika dalam rancangan optimum masalah (78) – (80) pembolehubah mengambil nilai pecahan, maka ketaksamaan itu ditambah kepada sistem persamaan (79)

(82)

dan cari penyelesaian kepada masalah (78) – (80), (82).

Dalam ketaksamaan (82) dan – kuantiti awal yang diubah dan nilainya diambil daripada jadual ringkas terakhir, dan – bahagian pecahan nombor (bahagian pecahan nombor tertentu a ialah nombor bukan negatif terkecil b supaya perbezaan antara A Dan b ada keseluruhan). Jika dalam rancangan optimum masalah (78) – (80) nilai pecahan mengambil beberapa pembolehubah, maka ketaksamaan tambahan (82) ditentukan pecahan terbesar bahagian.

Jika dalam rancangan masalah (78) – (80), (82) yang ditemui pembolehubah mengambil nilai pecahan, maka satu kekangan tambahan ditambah semula dan proses pengiraan diulang. Menjalankan bilangan lelaran yang terhingga, seseorang sama ada memperoleh pelan optimum untuk masalah pengaturcaraan integer (78) – (81) atau menetapkan ketidakbolehpecahannya.

Jika keperluan integriti(81) hanya terpakai kepada beberapa pembolehubah, maka masalah tersebut dipanggil separa integer. Penyelesaian mereka juga didapati dengan menyelesaikan masalah secara berurutan, setiap satunya diperoleh daripada yang sebelumnya dengan memperkenalkan kekangan tambahan. Dalam kes ini, sekatan sedemikian mempunyai bentuk

di mana ditentukan daripada hubungan berikut:

1) untuk , yang boleh mengambil nilai bukan integer,

(84)

2) untuk , yang hanya boleh mengambil nilai integer,

(85)

Daripada perkara di atas, proses menentukan pelan optimum untuk masalah pengaturcaraan integer menggunakan kaedah Gomori termasuk perkara berikut. peringkat utama:

1. Menggunakan kaedah simpleks, cari penyelesaian kepada masalah (78) – (80) tanpa mengambil kira keperluan integriti pembolehubah.

2. Buat kekangan tambahan untuk pembolehubah, yang dalam pelan optimum masalah (78) – (80) mempunyai pecahan maksimum nilai, dan dalam pelan optimum, masalah (78) – (81) hendaklah integer.

3. Menggunakan dwi , cari penyelesaian kepada masalah yang terhasil daripada masalah (78) – (80) akibat penambahan kekangan tambahan.

4. Jika perlu, buat satu lagi kekangan tambahan dan teruskan proses berulang sehingga pelan optimum untuk masalah (78) – (81) diperoleh atau ketidakbolehpecahannya diwujudkan.

Contoh 22.

Gunakan kaedah Gomori untuk mencari nilai maksimum fungsi

memandangkan itu

(87)

– keseluruhan (89)

Penyelesaian. Untuk menentukan rancangan optimum untuk masalah (86) – (89), kita mula-mula mencari rancangan optimum untuk masalah (86) – (88) (Jadual 22).

Jadual 22

		C b	R 0

Seperti yang dapat dilihat dari jadual. 22, pelan optimum ditemui masalah (86) – (88) bukan rancangan optimum untuk masalah (86) – (89), kerana dua komponen dan mempunyai nilai bukan integer. Selain itu, bahagian pecahan nombor ini adalah sama antara satu sama lain. Oleh itu, kekangan tambahan disediakan untuk salah satu pembolehubah ini. Mari kita buat, sebagai contoh, kekangan sedemikian untuk pembolehubah Daripada jadual simpleks terakhir (Jadual 22) kita ada

Oleh itu, kepada sistem kekangan masalah (86) - (89) kita menambah ketaksamaan

atau

Jadual 23

		C b	R 0

Kami kini mencari nilai maksimum fungsi (86) apabila keadaan (87), (88) dan (90) dipenuhi (Jadual 23).

Daripada Jadual 23 dapat dilihat bahawa masalah pengaturcaraan integer asal mempunyai rancangan yang optimum P Dalam pelan ini, nilai fungsi objektif adalah sama dengan . Mari kita berikan tafsiran geometri tentang penyelesaian masalah tersebut. Kawasan penyelesaian yang boleh dilaksanakan untuk masalah (86) – (88) ialah poligon OABCD(Gamb. 12). Daripada Rajah. 12 dapat dilihat bahawa fungsi objektif mengambil nilai maksimumnya pada titik DENGAN(19/2; 7/2), i.e. Apa X =(19/2; 7/2; 0; 0; 34) ialah pelan optimum. Ini jelas jelas daripada Jadual 22. Oleh kerana X= (19/2; 7/2; 0; 0; 34) bukan rancangan optimum untuk masalah (86) – (89) (nombor dan pecahan), maka kekangan tambahan diperkenalkan. Mengecualikan daripadanya dan menggantikan nilai yang sepadan daripada persamaan sistem kekangan (87), kita memperoleh potongan daripada poligon OABCD segi tiga EFC.

Seperti yang dapat dilihat dari Rajah. 12, kawasan penyelesaian yang boleh dilaksanakan kepada masalah yang terhasil ialah poligon OABEFD. Pada titik itu E(9; 4) poligon ini, fungsi objektif masalah ini mengambil nilai maksimum. Sejak koordinat titik E ialah nombor integer dan tidak diketahui, dan mengambil nilai integer apabila menggantikan nilai dan ke dalam persamaan (87), kemudian ialah rancangan optimum untuk masalah (86) – (89). Ini juga mengikut Jadual 23.

Contoh 23.

Menggunakan kaedah Gomori, cari penyelesaian kepada masalah menentukan nilai maksimum sesuatu fungsi

dalam keadaan

- keseluruhan. (94)

Berikan tafsiran geometri bagi penyelesaian masalah tersebut.

Penyelesaian. Mari kita tulis semula masalah yang dirumuskan seperti berikut: cari nilai maksimum fungsi tersebut

dalam keadaan

(96)

- keseluruhan. (98)

Masalah (95) – (98) adalah sebahagian integer, kerana pembolehubah dan boleh mengambil nilai bukan integer.

Menggunakan kaedah simpleks, kita mencari penyelesaian kepada masalah (95) – (97) (Jadual 24).

Jadual 24

		C b	R 0
		C b	R 0
							–1/3 bukan rancangan untuk masalah (95) – (98), kerana pembolehubah

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.

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 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 kereta jenis A dan B, masing-masing, dengan Z - pencapaian keseluruhan. 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 ^

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 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 pada optimum penyelesaian integer 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, kekal Wang daripada mereka yang diperuntukkan adalah sama dengan 0, dalam simpanan untuk pembelian - 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$ yang 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. Ada cukup sejumlah besar kayu balak 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 2х, + x2 - x4 = 50, , tidak melebihi ini.

Di bawah bahagian pecahan beberapa nombor A bermakna nombor bukan negatif terkecil
supaya perbezaan antara ia dan A Terdapat [ a] - bahagian integer nombor).

Bagi pembolehubah asas yang dipilih dengan bahagian pecahan terbesar cari bahagian pecahan
pembolehubah ini dan bahagian pecahan semua pekali bagi pembolehubah i baris ke- sistem sekatan
(garisan pengeluaran).

Mari kita nyatakan
Dan
keseluruhan bahagian nombor Dan . Nilai bahagian pecahan
Dan
(
) ditakrifkan seperti berikut

Untuk melakukan ini, persamaan ditulis daripada baris penjanaan jadual simpleks, dengan mengandaikan bahawa yang pertama m pembolehubah adalah asas untuk rancangan optimum yang diberikan

atau

Kami menggerakkan semua bahagian integer pekali dalam satu arah, meninggalkan semua bahagian pecahan di arah yang lain:

Kerana
<1, то заменяя в правой части
, kita memperolehi ketidaksamaan yang ketat

Oleh kerana bahagian kiri ketaksamaan mesti mengambil nilai integer, oleh itu, syarat yang diperlukan untuk integerinya hanya boleh ditulis dalam bentuk berikut:

Ketaksamaan ditukar kepada persamaan dengan memperkenalkan pembolehubah bukan negatif tambahan dan dimasukkan ke dalam jadual simpleks optimum.

Kami menyelesaikan masalah menggunakan kaedah dwi simplex. Jika rancangan optimum baharu untuk masalah lanjutan adalah integer, maka masalah itu diselesaikan. Jika penyelesaiannya bukan integer, maka anda perlu mengulang algoritma kaedah Gomori sehingga penyelesaian integer diperolehi.

Contoh. Menggunakan kaedah Gomori, cari penyelesaian kepada masalah pengaturcaraan integer yang terdiri daripada menentukan nilai maksimum fungsi
memandangkan itu

Penyelesaian. Meratakan Ketaksamaan Menggunakan Pembolehubah Bantu X 3 , X 4, kita memperoleh masalah pengaturcaraan linear dalam bentuk kanonik:

Kami menyelesaikan masalah pengaturcaraan linear menggunakan kaedah simplex, menggunakan peralihan langkah demi langkah dari satu asas ke asas yang lain. Kemajuan penyelesaian masalah dan penyelesaian optimum yang terhasil dibentangkan dalam jadual.

	DENGAN B			DENGAN 2 =11
∆ j =Z j -DENGAN j

	DENGAN B			DENGAN 2 =11
∆ j =Z j -DENGAN j

Dalam rancangan optimum yang ditemui, nilai pembolehubah X 2 adalah sama dengan nombor pecahan. Kami mencari bahagian pecahannya dan bahagian pecahan semua unsur garis yang mengandungi pembolehubah X 2, iaitu:

Sekarang kita menyusun ketaksamaan Gomori untuk nilai yang ditemui bahagian pecahan:

.

X 5, kami mengalihkan sebutan bebas persamaan ke sebelah kanan dan mendapat kekangan baharu:

.

Kami menambah baris yang mengandungi kekangan baharu dan lajur yang mengandungi pembolehubah baharu pada jadual simpleks, dan terus menyelesaikan masalah menggunakan kaedah dwi simpleks, kerana pseudoplan kini ditulis dalam jadual.

∆ j =Z j –DENGAN j

	DENGAN B			DENGAN 2 =11
∆ j =Z j –DENGAN j

Penyelesaian optimum yang terhasil kepada masalah lanjutan mengandungi nilai bukan integer pembolehubah X 1, jadi kita dapati untuk baris ini bahagian pecahan semua nombor bukan integer, iaitu:

dan ketidaksamaan Gomory baharu mempunyai bentuk:

Kami menyamakan ketidaksamaan Gomori menggunakan pembolehubah tambahan baharu X 6, kami mengalihkan sebutan bebas persamaan ke sebelah kanan dan mendapat kekangan baharu:
.

Kami menambahkannya kepada masalah yang sedang diselesaikan, menyelaraskannya menggunakan pembolehubah tambahan dan menyelesaikan masalah lanjutan

	DENGAN B			DENGAN 2 =11
∆ j =Z j –DENGAN j

	DENGAN B			DENGAN 2 =11
∆ j =Z j –DENGAN j

Oleh itu, penyelesaian optimum kepada masalah pengaturcaraan integer telah ditemui: Z maks=11 pada
.

Nota :

Jika, semasa proses penyelesaian, persamaan dengan komponen bukan integer muncul dalam jadual simpleks dan pekali integer dalam baris yang sepadan bagi sistem sekatan
, maka masalah ini tidak mempunyai penyelesaian integer.

Kaedah ini berdasarkan kaedah simplex, yang digunakan untuk mencari penyelesaian optimum tanpa mengambil kira keadaan integer. Jika pelan yang terhasil mengandungi sekurang-kurangnya satu komponen pecahan, maka kekangan tambahan dikenakan dan pengiraan sekali lagi terus menggunakan kaedah simpleks.

Proses ini berterusan sehingga semua komponen pelan adalah integer, atau ditunjukkan bahawa masalah tidak mempunyai penyelesaian integer.

Biarkan X* = (x1, x2, …, xm, …, xn) ialah pelan optimum yang ditemui menggunakan kaedah simplex, di mana asasnya ialah vektor A1, A2,…, Am. Biarkan xi ialah nombor pecahan (nombor dalam lajur B dalam baris ke-i). Maka ada kemungkinan bahawa dalam baris ke-i:

1. semua xij adalah integer, ini bermakna masalah tidak mempunyai penyelesaian integer

2. beberapa xij adalah pecahan

Biarkan [xi] dan [xij] ialah bahagian integer bagi nombor xi dan хij, dan (xi) dan (хij) ialah bahagian pecahan.

Mari kita nyatakan qi = (хi) dan qij = (хij) dan susun perbezaannya.

(qi1Х1+ qi1Х2+…+ qi1Хn)- qi ≥0

Mari kita ubah ketaksamaan kepada persamaan dengan mendarabkannya dengan (-1) dan menambah pembolehubah baharu Xn+1 dan menambah baris baharu pada jadual simpleks (dan oleh itu lajur). Kami selanjutnya menyelesaikan menggunakan kaedah dwi simpleks; jika pelan yang ditemui bukan integer, maka kami mengulangi proses menambah pembolehubah, baris dan lajur baharu pada jadual simpleks.

Jika pelan optimum mempunyai beberapa komponen bukan integer, maka kami membuat kekangan tambahan untuk qi maksimum.

Anda juga boleh mendapatkan maklumat yang anda minati dalam enjin carian saintifik Otvety.Online. Gunakan borang carian:

Lebih lanjut mengenai topik 47 Kaedah Gomori: idea utama dan penerangan ringkas tentang algoritma. Perasaan ekonomi untuk memperkenalkan sekatan tambahan:

1. 25. Kaedah pengurusan ekonomi, tujuan yang dimaksudkan. Jenis dan kandungan utama kaedah pengaruh ekonomi. Penerangan ringkas dan ciri-ciri aplikasi kaedah ekonomi