Тема 4 базисные решения

Симплекс метод – это метод целенаправленного перебора опорных решений задачи линейного программирования (ЗЛП).

Основания для применения симплекс метода:

1) ОДР ЗЛП – выпуклое множество с конечным числом угловых точек;

2) оптимальное решение ЗЛП – это одна из угловых точек ОДР;

3) угловые точки ОДР – базисные решения (опорные планы) системы ограничений.

Базисные решения – допустимые решения вида , содержащие r базисных и n-r свободных переменных.

Все свободные переменные равны нулю, а базисные переменные равны соответствующим свободным членам в преобразованной (разрешённой относительно базисных переменных) системе ограничений.

Чтобы решения системы уравнений ограничений были допустимыми, должно выполняться

условие неотрицательности свободных членов: