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

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

  • Petro Stetsyuk Інститут кібернетики імені В.М. Глушкова НАН України, Проспект Академіка Глушкова, 40, 03187, Київ
  • Andreas Fischer Інститут обчислювальної математики технічного університету Дрездена, 01062, Дрезден, Німеччина
  • Olha Khomiak Інститут кібернетики імені В.М. Глушкова НАН України, Проспект Академіка Глушкова, 40, 03187, Київ
Ключові слова: метод штрафних функцій, функція максимуму, задача лінійного програмування, GNU Octave

Анотація

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

Опубліковано
2021-09-06