Analiz Ustoychivosti Zadach I Algoritmov Tselochislennogo Programmirovaniya

Iskhodnaya informatsiya znachitel'nogo chisla prakticheskikh zadach, matematicheskimi modelyami kotorykh yavlyayutsya zadachi tselochislennogo programmirovaniya (TsP), nosit priblizhennyy kharakter. V svyazi s etim aktual'nym yavlyaetsya analiz ukazannykh zadach i metodov ikh resheniya pri malykh izmeneniyakh nachal'nykh parametrov zadachi. V monografii razvivaetsya novyy podkhod k issledovaniyu ustoychivosti zadach TsP, osnovannyy na metode regulyarnykh razbieniy relaksatsionnykh mnozhestv. Pod ustoychivost'yu zadachi TsP otnositel'no regulyarnogo razbieniya ponimaetsya ne bolee chem polinomial'nyy po otnosheniyu k razmernosti prostranstva rost moshchnosti regulyarnogo razbieniya relaksatsionnogo mnozhestva zadachi pri dostatochno malykh "dopustimykh" izmeneniyakh etogo mnozhestva. V rabote provedeno issledovanie ustoychivosti zadachi TsP v obshchey postanovke, a takzhe ee chastnykh sluchaev otnositel'no ryada regulyarnykh razbieniy. Polucheny kolichestvennye kharakteristiki ustoychivosti dlya spetsial'nykh zadach tselochislennogo lineynogo programmirovaniya. Issledovana ustoychivost' nekotorykh algoritmov TsP pri izmenenii relaksatsionnykh mnozhestv rassmatrivaemykh zadach. Razrabotany algoritmy dlya zadachi TsP s interval'nymi iskhodnymi dannymi.