Симплекс-метод решения задачи линейного программирования
Приведем прежде всего постановку задачи линейного программирования. Под задачей линейного программирования (задачей ЛП) будем понимать следующую задачу.
Даны система т линейных ограничений с п неизвестными (система может содержать как уравнения, так и (или) неравенства того или иного знака),
условие неотрицательности неизвестных
(2)
и целевая линейная функция, зависящая от n неизвестных,
(3)
где - вектор неизвестных.
Требуется найти такой план системы линейных ограничений (1), при котором целевая функция (3) примет наибольшее или наименьшее значение, то есть найти оптимальный план задачи.
При решении задачи ЛП возможны следующие случаи.
. Существует оптимальный план (единственный или бесконечное множество оптимальных планов).
. Оптимального плана не существует, так как планы в задаче есть, но на непустом множестве планов целевая функция не ограничена (сверху - в задаче максимизации или снизу - в задаче минимизации).
. Оптимального плана не существует, так как в задаче вообще нет ни одного плана.
Будем рассматривать три формы задачи линейного программирования, а именно:
) общая задача;
) основная задача;
) каноническая задача.
Задачу ЛП будем называть общей задачей, если система линейных ограничений (1) содержит хотя бы одно неравенств, основной задачей, если все ограничения системы (1) являются уравнениями.
Задачу ЛП будем называть канонической задачей, если она является частным случаем основной задачи в том смысле, что система линейных уравнений - каноническая, а целевая функция выражена только через свободные неизвестные.
Система линейных уравнений называется канонической системой, если она удовлетворяет двум условиям:
) в каждом уравнении содержится неизвестное с коэффициентов равным единице, отсутствующее во всех остальных уравнениях и называемое базисным неизвестным;
) свободные члены всех уравнений неотрицательны.
Теорема. (Основная теорема симплекс-метода). Каноническая задача всегда имеет и причем единственное решение, то есть оптимальный план.
Неизвестные, не являющиеся базисными, называются свободными неизвестными. При т = 2, п = 4, если предполагать базисными неизвестные х3 и х4, каноническую задачу можно записать в виде
Если в канонической системе положить все свободные неизвестные равными нулю, то базисные неизвестные будут равны неотрицательным свободным членам уравнений. Полученный таким способом план называется базисным планом канонической задачи. При х1 = x2 = 0 из системы (4) получим, что х3 = b1 ³ 0, х4 = b2 ³ 0, и базисный план задачи (4) - (6) будет иметь вид
Xbas=(0, 0, b1, b2),
причем, как видно из выражения (6), значение целевой функции для этого плана f(Xbas) = C0.
Из трех форм задачи ЛП главная роль отводится канонической, так как алгоритм симплекс-метода непосредственно применяется к канонической задаче, а общая и основная задачи в конечном счете сводятся к канонической.
Симплекс-метод решения канонической задачи линейного программирования называют еще методом последовательного улучшения базисного плана. Любую каноническую задачу можно поместить в так называемую симплексную таблицу. Рассмотрим, как заполняется симплексная таблица задачи (4)-(6). В эту таблицу записывается расширенная матрица канонической системы (4), слева выписываются названия базисных неизвестных, содержащихся в соответствующих уравнениях. Последняя строка симплексной таблицы называется индексной строкой и заполняется коэффициентами целевой функции (6) по следующему правилу: свободный член С0 вносится со своим знаком, коэффициенты при неизвестных - с противоположными знаками.