Много задачи от икономически характер, проблемипланирането и дори решаването на проблеми от други сфери на човешката дейност е свързано с променливи, свързани с цяло число. В резултат на техния анализ и търсене на оптимални решения се появи концепцията за екстремален проблем. Неговите характеристики са горната черта, за да се вземат целочислени стойности, а самият проблем се разглежда в математиката като цяло числово програмиране.
Като основна употребазадачи с променливи, които приемат целочислени стойности, е оптимизация. Методът, използващ цялостно линейно програмиране, също се нарича метод на изрязване.
Методът Гомори получи името си по имематематиката, първата разработваща алгоритъм през 1957-1958 г., която все още се използва широко за решаване на цели линейни програми. Каноничната форма на задачата за цялостно програмиране дава възможност напълно и ясно да се разкрият предимствата на този метод.
Gomory метод за линейнипрограмирането значително усложнява задачата за намиране на оптималните стойности. В края на краищата, интегралността е основното условие, в допълнение към всички параметри на проблема. Често има случаи, когато дадена задача, имаща допустими (целочислени) планове, не достига максимум, когато целевите функции имат ограничения върху допустим набор. Това се дължи на липсата на точно цели решения. Без това условие, като правило, подходящ вектор се намира под формата на разтвор.
За да се обосноват числени алгоритми при решаването на проблеми, е необходимо да се наложат различни допълнителни условия.
Използвайки метода на Гомори, обикновено се броят многопланове за проблем, ограничен от т.нар. На тази основа следва, че множеството от всички целочислени планове за въпросната задача има крайна стойност.
Също така, за да се гарантира целостта на функцията, се приема, че коефициентите на стойностите са също цели числа. Въпреки тежестта на такива състояния, те могат да се разхлабят малко.
Методът Gomory всъщност включва изграждането на ограничения, които отрязват решения, които не са нецели. В същото време не се прекъсва решение на цялостен план.
Алгоритм решения задачи включает в себя намиране на подходящи варианти по метода симплекс, без да се вземат предвид условията на интегритет. Ако всички компоненти на оптималния план съдържат решения, свързани с числа, тогава можем да приемем, че целта на целочисленото програмиране е постигната. Възможно е да се разкрие неразрешимостта на проблема, така че получаваме доказателство, че целият програмен проблем няма решение.
Възможно е в компонентитеоптималните решения са нецелочислени числа. В този случай към всички ограничения на задачата се добавя ново ограничение. Наличието на редица свойства е характерно за новото ограничение. На първо място, тя трябва да бъде линейна, тя трябва да отсече нецелочислен план от намерения оптимален набор. Не трябва да се губи нито едно цяло цяло число, нито да се изрязва.
При конструирането на ограничение трябва да се избере компонентата на оптималния план с най-голямата дробна част. Това ограничение ще бъде добавено към вече съществуващата симплекс таблица.
Ние намираме решение на проблема, получен чрез използванеобикновени симплексни преобразувания. Проверяваме решението на проблема за наличието на целочислен оптимален план, ако условието е изпълнено, тогава проблемът се решава. Ако резултатът отново се получи с наличието на неинтегрални решения, ще въведем допълнително ограничение и ще повторим процеса на изчисление.
Извършвайки ограничен брой итерации, постигаме оптималния план на задачата, зададен преди цялостното програмиране, или доказваме неразрешимостта на проблема.
