Veselo skaitļu programmēšanas vide
Atrisiniet nelielu veselo skaitļu lineāro programmu ar precīzu atzarošanas un ierobežošanas metodi un skatiet katru meklēšanas mezglu. Labākais punkts tiek ziņots kā pierādīti optimāls tikai pēc visa koka izpētes.
Programma nedrīkst pārsniegt 4 000 rakstzīmes un 40 rindas, 8 mainīgos un 8 ierobežojumus, kuros ir vismaz divi mainīgie; mezglu ierobežojums ir no 1 līdz 5 000, un meklēšana apstājas arī pēc 3 000 000 precīzas aritmētikas soļiem. Viss tiek aprēķināts jūsu ierīcē fona procesā, un tam atvēlētas 15 sekundes. Lejupielādei pieejams JSON pārskats un mezglu CSV fails. Pirmajā rindā norādiet maximize vai minimize un mērķfunkciju. Pēc tam katrā rindā ievadiet vienu ierobežojumu. Līdz 4 000 rakstzīmēm. Pirms palaišanas pārskatiet iestatījumus.
Jūsu rezultāts
Veselo skaitļu programmēšanas vide
- Pirmajā rindā uzrakstiet mērķfunkciju, piemēram, maximize 5x + 4y.
- Katrā rindā pievienojiet vienu ierobežojumu, piemēram, x, y >= 0, un, ja vajadzīgs, atsevišķu rindu, piemēram, integer x vai binary z.
- Iestatiet mezglu ierobežojumu un sāciet meklēšanu.
- Skatiet statusu, pašreizējo labāko risinājumu, labāko robežu un atstarpi, pēc tam lejupielādējiet JSON pārskatu vai mezglu CSV failu.
Kas jāzina
Programma nedrīkst pārsniegt 4 000 rakstzīmes un 40 rindas, 8 mainīgos un 8 ierobežojumus, kuros ir vismaz divi mainīgie; mezglu ierobežojums ir no 1 līdz 5 000, un meklēšana apstājas arī pēc 3 000 000 precīzas aritmētikas soļiem. Viss tiek aprēķināts jūsu ierīcē fona procesā, un tam atvēlētas 15 sekundes. Lejupielādei pieejams JSON pārskats un mezglu CSV fails.
Atzarošana un ierobežošana
Katrā mezglā lineāro relaksāciju precīzi atrisina ar simpleksa metodi. Mainīgo ar daļskaitlisku vērtību sadala divos zaros: x <= noapaļojums uz leju vai x >= noapaļojums uz augšu. Mezgli tiek atmesti, ja to relaksācija nav pieļaujama vai nevar uzlabot līdz šim atrasto labāko veselo risinājumu. Metode: Wolsey, Integer Programming, 2. izdevums, 7. nodaļa (2020).
Ko nozīmē pierādīts
Ja katrs mezgls ir atrisināts vai atmests ar precīzu robežu, pašreizējais labākais risinājums ir pierādīti optimāls vai arī pierādīts, ka uzdevums nav pieļaujams. Ja meklēšanu agrāk aptur mezglu ierobežojums vai soļu limits, pašreizējais risinājums ir tikai līdz šim atrastais labākais punkts; pārskatā norādīta labākā robeža un atstarpe starp tiem.
Ievades noteikumi
Pēc noklusējuma mainīgie ir veseli skaitļi. Ja dažus norādāt ar integer x, y, šie mainīgie ir veseli, bet pārējie ir nepārtraukti. Viena mainīgā ierobežojumi kļūst par robežām. Ja relaksācija ir neierobežota, meklēšana tiek apturēta, jo veselā skaitļu programma tad var būt neierobežota vai arī nepieļaujama.