Metoda Gomory. Solusi masalah programming integer

Masalah beurat ékonomi, tata komo isu ti spheres séjén masalah kahirupan manusa pakait sareng variabel patali wilangan buleud. Salaku hasil analisis maranéhanana sarta milarian cara anu pangalusna pikeun alamat nu Pamanggih ngeunaan tantangan ekstrim. fitur nyaeta fitur luhur nyokot hiji nilai integer, sarta tugas sorangan dianggap matématika saperti programming integer.

The kagunaan utama masalah sareng variable, hiji integer, nyaeta optimasi nu. Hiji métode anu ngagunakeun hiji integer programming linier, disebut oge metodeu cut-pareum.

Metoda Gomory ieu dingaranan matematika, mimiti tumuwuh di 1957-1958 algoritma anu masih loba dipaké pikeun ngajawab masalah programming linier integer. Bentuk canonical tina masalah programming integer ngamungkinkeun diaksés tur pinuh nyingkab kaunggulan tina metoda ieu.

Metoda Gomori dilarapkeun ka programming linier greatly complicates tugas nyungsi nilai optimal. Saatos integrality mangrupakeun sarat dasar, salajengna sadayana parameter tina masalah. Aya kasus lamun masalah ku ngabogaan valid (integer) rencana, ayana di éta fungsi obyektif tina larangan dina set bisa ditarima, kaputusan datang ka achieving maksimum. Ieu alatan kurangna éta solusi integral. Tanpa kaayaan anu sarua, sakumaha aturan, dina bentuk kaputusan mangrupa vektor luyu.

Menerkeun kana algoritma numeris pikeun ngarengsekeun masalah aya anu peryogi pikeun ngalakonan superimposition tambahan kaayaan béda.

Ngagunakeun metoda Gomory, biasana nganggap loba rencana pikeun disebut masalah solusi polyhedron kawates. Dina dasar ieu, susunan sakabeh rencana integral ngabogaan nilai terhingga keur tugas.

Ogé, keur jaminan fungsi integral nganggap yen nilai tina koefisien oge wilangan buleud. Najan severity kaayaan ieu, anu lemah maranéhna ngatur sababaraha.

Metoda Gomory dasarna ngalibatkeun larangan wangunan, nu motong solusi anu teu nonintegral. Dina hal ieu, euweuh sapotong-off euweuh solusi integer rencana.

Algoritma keur ngarengsekeun masalah ngalibatkeun nyungsi pilihan cocok metoda simpléks, tanpa nyokot kana akun kaayaan integrality. Lamun sakabeh komponen tina rencana optimal ngandung kaputusan patali wilangan buleud, éta bisa dianggap yén tujuan programming integer kahontal. Sugan nu ieu kapanggih insolubility masalah, sangkan mibanda bukti yén masalah programming integer boga solusi.

The variasi, nalika komponén tina larutan optimal ngandung angka non-integer. Dina hal ieu, anu pangwatesan anyar ditambahkeun ka sakabeh konstrain tina masalah. The larangan anyar dicirikeun ku jumlah sipat. Munggaran sadaya, kudu liniér, kudu dipotong kaluar tina set kapanggih tina non-integer rencana optimal. Ngayakeun solusi integer teu matak leungit, motong pareum.

Nalika gedong larangan kudu dipilih komponén hiji rencana optimal ku fraksi pangluhurna. Éta watesan ieu bakal ditambahkeun kana tabel simpléks aya.

Urang neangan solusi ngeunaan masalah hasilna ngagunakeun transformasi simpléks konvensional. Urang pariksa leyuran masalah dina ayana hiji rencana optimal integer, upami kondisi ieu wareg, teras masalah ieu direngsekeun. Mun hasilna dimenangkeun deui ku ayana solusi non-integer, teras urang ngawanohkeun hiji Konstrain tambahan, sarta ngulang prosés itungan.

Sanggeus dilaksanakeun sajumlah iterations, urang ngahontal hiji program optimal dina masalah ngawarah di hareup programming integer, atawa ngabuktikeun insolubility tina masalah.