Egészértékű programozási környezet
Oldjon meg egy kisebb egészértékű lineáris programot egzakt elágazásos és korlátos kereséssel, és tekintse meg a keresés összes csomópontját. A legjobb pontról csak akkor jelenti ki, hogy bizonyítottan optimális, ha a teljes keresési fát bejárta.
A program legfeljebb 4 000 karakteres és 40 soros lehet, és legfeljebb 8 változót, valamint 8 legalább kétváltozós korlátozást tartalmazhat; a csomópontkorlát 1 és 5 000 közé esik, a keresés pedig 3 000 000 egzakt aritmetikai lépés után is leáll. Minden számítás az eszközén, háttérfolyamatban történik, legfeljebb 15 másodpercig. A letölthető fájlok JSON-jelentés és a csomópontok CSV-fájlja. Első sor: írja be, hogy maximize vagy minimize, majd a célfüggvényt. Ezután soronként egy korlátozást adjon meg. Legfeljebb 4 000 karakter. Futtatás előtt tekintsd át a beállításokat.
Az eredményed
Egészértékű programozási környezet
- A célfüggvényt az első sorba írja, például maximize 5x + 4y.
- Minden korlátozást külön sorba írjon; adjon meg például x, y >= 0 típusú korlátokat és igény szerint integer x vagy binary z sorokat.
- Állítsa be a csomópontkorlátot, majd indítsa el a keresést.
- Tekintse meg az állapotot, az aktuális legjobb megoldást, a legjobb korlátot és a rést, majd töltse le a JSON-jelentést vagy a csomópontok CSV-fájlját.
Mire számíthatsz
A program legfeljebb 4 000 karakteres és 40 soros lehet, és legfeljebb 8 változót, valamint 8 legalább kétváltozós korlátozást tartalmazhat; a csomópontkorlát 1 és 5 000 közé esik, a keresés pedig 3 000 000 egzakt aritmetikai lépés után is leáll. Minden számítás az eszközén, háttérfolyamatban történik, legfeljebb 15 másodpercig. A letölthető fájlok JSON-jelentés és a csomópontok CSV-fájlja.
Elágazásos és korlátos keresés
Minden csomópont lineáris relaxációját egzakt módon, a szimplex módszerrel oldja meg. A nem egész értékű egészváltozót két ágra bontja: x <= lefelé kerekített érték és x >= felfelé kerekített érték. A csomópontokat akkor metszi le, ha a relaxációjuk megvalósíthatatlan, vagy nem javíthat a legjobb eddig talált egész megoldáson. Módszer: Wolsey, Integer Programming, 2. kiadás, 7. fejezet (2020).
Mit jelent a bizonyított
Ha minden csomópontot megoldott vagy egzakt korlát alapján levágott, az aktuális legjobb megoldás optimálisnak bizonyított, vagy a feladat megvalósíthatatlansága bizonyított. Ha a csomópontkorlát vagy a lépéskeret előbb állítja le a keresést, az aktuális megoldás csak az eddig talált legjobb pont; a jelentés megadja a legjobb korlátot és a kettő közötti rést.
Bemeneti szabályok
Alapértelmezés szerint minden változó egészértékű. Ha az integer x, y sorban néhány változót felsorol, ezek lesznek egészértékűek, a többi pedig folytonos marad. Az egyváltozós korlátozások korlátokká válnak. Ha a relaxáció korlátlan, a keresés leáll, mert az egészértékű program ekkor korlátlan vagy megvalósíthatatlan lehet.