Знаходження допустимого базисного розв’язку (ДБР) задачі лінійного програмування

Розглянемо ЗЛП в канонічній формі:

Визначення. Допустимим базисним розв’язком ЗЛП називається невід’ємний базисний розв’язок системи лiнiйних рiвнянь (1).

Якщо у вихiднiй моделi ЗЛП всi обмеження заданi у виглядi нерiвностей £ при невiд’ємних правих частинах, то при приведеннi математичної моделi до канонiчної форми ми одночасно одержуємо ДБР задачi лiнiйного програмування.

Якщо в вихiднiй моделi ЗЛП є обмеження-нерiвностi вигляду ³ або =, то при перетвореннi математичної моделi до канонiчної форми пошук початкового допустимого базисного розв’язку ускладнюється. В таких випадках до лiвих частин обмежень-рiвнянь канонiчної моделi (1), в яких немає базисних змiнних, добавляють невiд’ємну штучну змiнну, яка вводиться до функцiї мети з коефiцiєнтом –М при розв’язуваннi задачi на максимум (в задачах мiнiмiзацiї – з коефiцiєнтом +М), де М – велике додатнє число.

Зауваження. Якщо в оптимальному розв’язку всі штучні змінні рівні 0, то цей розв’язок є оптимальним розв’язком початкової задачі. Якщо в оптимальному розв’язку присутня штучна змінна, що не дорівнює 0, то система обмежень початкової задачі несумісна і початкова задача не має розв’язку.