Gomory метод. Решението на целочислени програмни проблеми

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

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

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

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

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

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

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

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

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

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

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

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

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