Штрафна функція максимуму в лінійному програмуванні

Fìz.-mat. model. ìnf. tehnol. 2021, 33:156-160

Анотація

Задачу лінійного програмування (ЛП-задачу) можна переформулювати як еквівалентну задачу безумовної мінімізації негладкої штрафної функції з досить великим параметром штрафу. У статті представлені два способи вибору цього параметра. Перший застосовується до ЛП-задач із звичайними лінійними нерівностями. Потім використовується відповідна теорема Н.З. Шора про еквівалентність задачі опуклого програмування та задачі безумовної негладкої мінімізації. Другий спосіб ‒ для ЛП-задач особливого типу. Це означає, що всі нерівності мають вигляд, де лінійний вираз в лівій частині менше або дорівнює додатній константі в правій частині. Для цього особливого типу використовується відповідна теорема Б.М. Пшеничного про встановлення штрафного параметра для задачі опуклого програмування. Для ЛП-задач різного розміру спеціального типу показано, що відповідні параметри штрафу можуть бути обчислені за допомогою процедури в GNU Octave на основі програмного забезпечення GLPK.