Počítání tolerancí pro úlohy vícekriteriálního lineárního programování

Abstrakt

Uvažujeme úlohy vícekriteriálního lineárního programování, kde koeficienty účelových funkcí podléhají určitému stupni nejistoty. Buď x* eficientní řešení dané úlohy.

Ukážeme jak spočítat individuální tolerance pro jednotlivé koeficienty tak, že všechny tyto koeficienty se mohou libovolně perturbovat v rámci svých tolerancí a přitom x* zůstane eficientní. Je-li x* nedegenerované řešení, pak algoritmus běží v polynomiálním čase.

Tato metoda je použitelná také pro úlohy intervalového vícekriteriálního lineárního programování pro testování nutné eficience x*, tj. zda x* je eficientní pro všechny realizace intervalových hodnot.

Klíčová slova

• Computing
• tolerances
• multiobjective
• linear
• programming