Hanyar Homori. Ana warware matsalolin shirye-shiryen mahallin

Matsayin matsaloli na yanayin tattalin arziki, matsalolin shiryawa da ma warware tambayoyin daga wasu wurare na rayuwar ɗan adam yana haɗuwa da masu amfani da suke magana zuwa lambobi. A sakamakon binciken su da kuma neman hanyoyin mafi kyau na bayani, manufar matsalar matsala ta bayyana. Ayyukansa sune siffar da ke sama don ɗaukar lamba mai mahimmanci, kuma matsala kanta ana bi da ita a lissafin ilmin lissafi azaman tsarin mahaɗan.

Babban jagorancin yin amfani da ɗawainiya tare da masu canji da ke ɗaukar lambobin lamba shine ingantawa. A Hanyar cewa yana amfani da wani lamba mikakke shirye-shirye, kuma ake kira da yanke-kashe hanya.

Hanyar Homori ta sami suna da sunan mathematician, wanda ya fara kirkira a 1957-1958 algorithm, wanda har yanzu ana amfani dashi don magance matsalolin shirye-shiryen linzamin kwamfuta na tsakiya. Hanyoyin maganganu na matsala masu mahimmanci suna sa ya fahimci amfanin wannan hanya.

Hanyar Gomori don tsara shirye-shiryen linzami yana ƙaddamar da matsala na gano dabi'un mafi kyau. Hakika, mahaɗin shine ainihin yanayin, ban da duk sigogi na matsalar. Akwai lokuta idan matsalar ta hanyar da ciwon inganci (lamba) da tsare-tsaren, gaban a haƙiƙa aiki na hani a kan m sa, da yanke shawara zo don cimma iyakar. Wannan shi ne saboda rashin mafitacin magunguna. Ba tare da wannan yanayin ba, a matsayin mai mulki, na'urar dacewa ta kasance a cikin hanyar warwarewa.

Don tabbatar da algorithms na lamba a magance matsalolin, ya zama wajibi don superimpose wasu ƙarin yanayi.

Amfani da tsarin Gomori, an saita tsarin ƙaddamar da matsaloli a matsayin abin da ake kira polytope na mafita. Tsayawa daga wannan ya biyo baya cewa tsarin duk shirye-shiryen haɗin kai don matsala a cikin tambaya yana da darajar ƙimar.

Har ila yau, don tabbatar da yawancin aiki, an ɗauka cewa halayen maɗaukaki maɗaura ne. Duk da tsananin irin waɗannan yanayi, za a iya aika su a bit.

Hanyar Homori, a gaskiya ma, ta ƙunshi gina ƙuntatawa da yanke yanke shawara waɗanda ba su da kowa ba. A wannan yanayin, babu wani bayani da zai iya warware duk wani bayani ga tsarin mai lamba.

A algorithm domin warware matsalar shafi gano dace zabin simplex Hanyar, ba tare da shan la'akari da yanayin integrality. Idan a duk bangarori na shirin mafi kyau duka akwai mafita dangane da mahaɗin lamba, to, zamu iya ɗauka cewa an cimma burin shirya shirye-shiryen mahaɗi. Yana yiwuwa yiwuwar rashin matsala ga matsalar za a bayyana, don haka muna samun tabbacin cewa matsala ta tsarin lamarin ba shi da wani bayani.

Ana iya bambanta lokacin da akwai lambobi marasa lamba a cikin ɓangarorin da aka samu mafi kyau. A wannan yanayin, sababbin ƙuntatawa an ƙãra wa dukan matsalolin aikin. Wani sabon ƙayyadaddun yana nuna wurin kasancewar yawan kaddarorin. Da farko, dole ne ya zama haɗin linzamin kwamfuta, dole ne ya yanke shirin ba tare da maƙala daga saiti mafi kyau ba. Babu wani bayani mai mahimmanci guda ɗaya da ya kamata a rasa, yanke.

Lokacin da kake gina ƙuntatawa, ya kamata ka zabi ɓangaren shirin mafi kyau tare da ɓangare mafi girma. Wannan ƙuntatawa ce da za a kara da shi a cikin tebur na simplex wanda yake kasancewa.

Mun sami maganin matsalar da aka samo ta ta amfani da canji na sauƙaƙe na simplex. Muna bincika maganin matsalar don kasancewar tsarin mai kyau mafi kyau, idan yanayin ya gamsu, to, an warware matsalar. Idan kuma an samu sakamako tare da kasancewar mafita ba tare da maƙala ba, to, za mu gabatar da ƙarin ƙuntatawa, kuma mun sake aiwatar da lissafi.

Bayan da muka gudanar da adadi mai yawa, mun sami shirin mafi kyau ga matsalar da aka gabatar kafin tsarin shirye-shirye, ko tabbatar da rashin daidaituwa na matsalar.