Gomory әдісі. бүтін бағдарламалау проблемаларды шешу

бүтін сандарға байланысты айнымалы байланысты адамның өмірі проблемаларын басқа да салалардағы экономикалық, жоспарлау және тіпті мәселелер Салмағы мәселелері. олардың талдау және төтенше қатерлерге ұғымын шешу үшін ең жақсы жолдарын іздеу нәтижесінде. Оның ерекшеліктері жоғарыда ерекшелігі бүтін мәнді қабылдайды, ал міндеті өзі бүтін бағдарламалау ретінде математика қарастырылады.

айнымалы, бүтін сан бар проблемаларды негізгі пайдалану, оңтайландыру болып табылады. бүтін пайдаланады әдісі сызықтық бағдарламалау, сондай-ақ, кесімді әдісін деп аталатын.

Бірінші 1957-1958 алгоритмдер әзірленген математик, әлі күнге дейін кеңінен бүтін сызықтық бағдарламалау проблемаларды шешу үшін пайдаланылады кейін Gomory әдісі аталды. бүтін бағдарламалау мәселенің канондық формасы қолжетімді мүмкіндік береді және толық осы әдістің артықшылықтары туралы ақпаратты ашып көрсетуі.

Gomori әдісі айтарлықтай оңтайлы мәндерін табу міндетін қиындатады сызықтық бағдарламалау қолданылады. бүтіндігі іргелі талап кейін, мәселенің барлық параметрлерді одан әрі. жарамды (бүтін) жоспарлары бар проблемалық, болуы жағдайлар бар объективті функциясын рұқсат етілген жиынтығы бойынша шектеулерді, шешім ең қол жеткізу үшін келеді. Бұл оның жетіспеушілігі ажырамас шешімдер байланысты. сол жағдайларда болмаса, әдетте, шешім түрінде тиісті векторы.

проблемаларды шешу үшін сандық алгоритмдерді ақтау үшін түрлі жағдайларда қосымша жаза жүзеге асыруға қажеттілік бар.

Gomory әдісін пайдалану, әдетте, шектеулі полиэдра ерітінділердің деп аталатын проблема көптеген жоспарларын қарастыру. Осы негізде, барлық ажырамас жоспарын тапсырмасына арналған ақырғы мәні бар.

Сондай-ақ, кепілдік ажырамас функциясы үшін коэффициенттер мәндері, сондай-ақ бүтін сандар болып табылады деп санаймыз. Осы жағдайлардың ауырлығына қарамастан, әлсіз, олар бірнеше басқару.

Gomory тәсілі мәні нецелым болып табылмайтын шешімдерді кесіп құрылыс шектеулер, қамтиды. Бұл жағдайда, ешбір қиылған жоқ бүтін шешімдер жоспары бар.

мәселені шешу үшін алгоритм лайықты нұсқаларын іздестіруді көздейді , Симплекс әдісін ескере тұтастығын шарттарын алмағанда. оңтайлы жоспарының барлық компоненттері бүтін сандарға байланысты шешімдер бар болса, онда ол бүтін бағдарламалау мақсаты қол деп болжауға болады. Мүмкін, бұл мәселенің табылған шешілмеген болып табылады, сондықтан біз бүтін бағдарламалау проблема шешім жоқ дәлелі бар.

оңтайлы шешу компоненттері емес бүтін санын қамтиды нұсқа. Бұл жағдайда, жаңа шектеу мәселесіне барлық шектеулерді қосылады. жаңа шектеулер қасиеттерін бірқатар сипатталады. Біріншіден, ол сызықтық болуы тиіс, емес бүтін оңтайлы жоспарын табылған жинағынан кесіп тиіс. Бірде-бүтін шешім кесіп, жоғалған тиіс емес.

құрылыс кезінде шектеулер жоғары үлесі оңтайлы жоспарын компонентін таңдау керек. Бұл шектеу қолданыстағы Симплекс кестеге қосылады табылады.

Біз дәстүрлі Симплекс өзгерісті пайдаланып нәтижесінде мәселенің шешімін табуға. шарт орындалды, егер біз, содан кейін проблема шешілді, бүтін оңтайлы жоспарын болуымен мәселенің шешімін тексеріңіз. нәтижесі емес бүтін шешімдерінің қатысуымен қайтадан алынды болса, онда біз қосымша шектеу енгізу, және есептеу процесті қайталаңыз.

Итерация соңғы саны жүзеге асырылатын отырып, біз бүтін бағдарламалау алдында қойылған проблеманың оңтайлы бағдарламаны жету, немесе мәселені шешілмеген дәлелдейді.