Метод на Хомори. Решаване на цялостни проблеми с програмирането

Много проблеми от икономическо естество, проблеми с планирането и дори решаването на въпроси от други сфери на човешката дейност са свързани с променливи, които се отнасят до цели числа. В резултат на анализа и търсенето на оптимални методи за решаване, се появи концепцията за екстремален проблем. Характеристиките му са описаните по-горе, за да отнемат цяло число, а самият проблем се третира в математиката като целочислено програмиране.

Като основна посока на използване на задачи с променливи, които вземат цели стойности, е оптимизацията. Метод, който използва цяло число линейно програмиране, все още се нарича метод на подрязване.

Методът на Homory получи името си от името на математик, който за пръв път разработи през 1957-1958 алгоритъма, който все още се използва широко за решаване на цялостни линейни проблеми при програмирането. Каноничната форма на цялостния програмен проблем дава възможност да се открият напълно предимствата на този метод.

Методът Gomori за линейно програмиране значително усложнява проблема с намирането на оптимални стойности. В крайна сметка числото е основното условие, в допълнение към всички параметри на проблема. Не е необичайно за проблем, когато имаме реалистичен (цялостен) план, ако обективни функции ограниченията на допустимия набор, не достигат максимума в разтвора. Това се дължи на липсата на цялостни решения. Без това условие, като правило, подходящ вектор е под формата на решение.

За да се оправдаят цифрови алгоритми при решаването на проблеми, е необходимо да се наслагват различни допълнителни условия.

Използвайки метода на Gomori, наборът от планови проблеми обикновено се смята за ограничен така наречен политоп на решения. Като се следва това, следва, че наборът от всички интегрални планове за въпросния проблем има крайна стойност.

Също така, за да се гарантира цялостността на дадена функция, се приема, че коефициентите на стойностите са също цели числа. Въпреки тежестта на тези условия, те могат да бъдат изпратени малко.

Методът на Homori, всъщност, включва изграждането на ограничения, които прекъсват решенията, които не са не-цели. В този случай няма изрязване на каквото и да е решение на целочисления план.

Алгоритъм за решаване на проблема включва намирането на подходящи опции simplex метод, като не се вземат предвид цялостните условия. Ако във всички компоненти на оптималния план има решения, свързани с числа, тогава можем да приемем, че целта на цялостното програмиране е постигната. Възможно е да се разкрие нечетливостта на проблема, така че да получим доказателство, че проблемът с цялостното програмиране няма решение.

Вариант е възможен, когато в компонентите на оптималното решение има не-цели числа. В този случай се добавят нови ограничения към всички ограничения на задачата. За ново ограничение са характерни редица свойства. На първо място, той трябва да бъде линеен, той трябва да отреже нецелевия план от намерения оптимален набор. Не трябва да се губи едно цяло число решение, отрязано.

При конструирането на ограничението е необходимо да изберете компонента на оптималния план с най-голямата частична част. Това ограничение ще бъде добавено към вече съществуващата таблица на симплекс.

Намираме решението на получения проблем с обикновени симплекс трансформации. Ние проверяваме решението на проблема за наличието на цялостен оптимален план, ако условието е изпълнено, тогава проблемът е решен. Ако отново резултатът е получен с присъствието на нецелеви решения, тогава въвеждаме допълнително ограничение и ние повторяваме процеса на изчисление.

След като извършихме определен брой повторения, получаваме оптимален план за проблема, поставен преди цялото програмиране, или доказваме неразрешимостта на проблема.