Täisarvulise optimeerimise tööriist
Lahenda väike täisarvuline lineaarprogramm täpse haru ja piiride meetodiga ning vaata kõiki otsingu sõlmi. Parim punkt märgitakse tõestatult optimaalseks ainult siis, kui kogu otsingupuu on läbi käidud.
Programmide piirangud: 4 000 märki ja 40 rida, 8 muutujat ning 8 vähemalt kahte muutujat sisaldavat piirangut; sõlmede piir on 1 kuni 5 000 ja otsing peatub ka pärast 3 000 000 täpset aritmeetilist sammu. Kõik arvutused tehakse sinu seadmes taustatöölõimes 15 sekundi piiranguga. Allalaaditavad failid: JSON-aruanne ja sõlmede CSV-fail. Esimene rida: maximize või minimize ja sihtfunktsioon. Seejärel üks piirang igal real. Kuni 4 000 märki. Vaadake seaded enne käivitamist üle.
Sinu tulemus
Täisarvulise optimeerimise tööriist
- Kirjuta eesmärk esimesel real, näiteks maximize 5x + 4y.
- Lisa igale reale üks piirang; näiteks piirid x, y >= 0 ja valikulised read nagu integer x või binary z.
- Määra sõlmede piir ja käivita otsing.
- Loe olekut, seni parimat täisarvulist lahendit, parimat piiri ja nende vahet; seejärel laadi alla JSON-aruanne või sõlmede CSV-fail.
Mida tasub teada
Programmide piirangud: 4 000 märki ja 40 rida, 8 muutujat ning 8 vähemalt kahte muutujat sisaldavat piirangut; sõlmede piir on 1 kuni 5 000 ja otsing peatub ka pärast 3 000 000 täpset aritmeetilist sammu. Kõik arvutused tehakse sinu seadmes taustatöölõimes 15 sekundi piiranguga. Allalaaditavad failid: JSON-aruanne ja sõlmede CSV-fail.
Haru ja piiride meetod
Iga sõlm lahendab lineaarse relaksatsiooni täpselt simpleksmeetodiga. Murdarvulise väärtusega täisarvmuutuja jagatakse kaheks haruks: x <= floor ja x >= ceiling. Sõlmed jäetakse välja, kui relaksatsioon on teostamatu või ei saa ületada seni leitud parimat täisarvulist punkti. Meetod: Wolsey, Integer Programming, 2. trükk, 7. peatükk (2020).
Mida tähendab tõestatud
Kui iga sõlm on lahendatud või täpse tõkke abil kärbitud, on seni leitud parim lahend tõestatult optimaalne või on ülesande lahendamatus tõestatud. Kui sõlmede piir või sammude eelarve peatab otsingu varem, on seni leitud parim lahend üksnes parim seni leitud punkt; aruanne näitab parimat tõket ja nende vahet.
Sisestusreeglid
Muutujad on täisarvulised, välja arvatud juhul, kui märgid mõned neist täisarvuliseks, näiteks integer x, y; ülejäänud muutujad on siis pidevad. Ühe muutujaga piirangutest saavad tõkked. Kui lõdvendatud ülesanne on tõkestamata, peatub otsing, sest täisarvprogramm võib olla tõkestamata või lahendamatu.