При любом выборе базиса все планы, удовлетворяющие (18), в том числе все
допустимые планы, можно получить, придавая свободным переменным произвольные
значения и вычисляя значения базисных переменных по их выражениям
через свободные. Планы, которые получаются указанным способом при нулевых
значениях свободных переменных, называются базисными. Симплексной табли-це
2 (уравнениям (25), (26)) соответствует базисный план в
котором
при этом
Базисный
план
будет допустимым тогда и только тогда,
когда значения всех базисных переменных ( т. е. свободные члены
симплексной таблицы) неотрицательны.
Допустимые базисные планы называются опорными. Симплексные таблицы с
неотрицательными свободными членами называются допустимыми.
Предположим, что таблица 2
допустима и, кроме того, все коэффициенты в
строке F неотрицательны (
может
быть и отрицательным). Тогда для любого допустимого плана
будет выполнено неравенство (учесть, что
)
Это означает, что -
наибольшее из значений целевой функции на допустимых планах, т. е. опорный
план
является оптимальным. Если все
коэффициенты
положительны, т. е. среди
них нет не только отрицательных чисел, но и нулей, опорный план
будет единственным оптимальным
планом задачи (17)-(19). Действительно, в этом случае для любого допустимого
плана
среди чисел
а
значит и среди произведений
есть хотя бы одно
положительное, т. е. выполнено строгое неравенство
.
Требование неотрицательности (положительности) элементов строки F (не считая свободного члена) называется условием оптимальности (строгой оптимальности) симплексной таблицы. Доказанное выше утверждение можно сформулировать следующим образом.
Критерий оптимальности. Если симплексная таблица одновременно допустима и удовлетворяет условию оптимальности, соответствующий ей опорный план является оптимальным. При выполнении условия строгой оптимальности таблицы это единственный оптимальный план задачи ЛП.
Рассмотрим на примерах, как можно использовать критерий оптимальности и введенные выше понятия и определения для решения задач ЛП.
Пример
7. Приведем задачу (1)-(3), уже решенную графически в примере 6, к
канонической форме. Выражая балансовые переменные через
получим
Здесь
требования неотрицательности опущены; форма записи уравнений означает, что - базисные,
-
свободные. Справа от уравнений представлена соответствующая симплексная
таблица,
в левом верхнем углу–обозначение этой
таблицы. В
выделены столбец
и
строка
, а также добавлен стол- бец
.В дальнейшем выяснится, для чего это
сделано. В допустимых планах
значения свободных
переменных
неотрицательны и однозначно определяют
значения всех остальных переменных, включая F. При
получаем опорный план
(ему соответствует вершина О(0 ,0),
рис.1) и
Чтобы «улучшить» план
(увеличить значение F),
надо заменить хотя бы одно из нулевых значений
на положительное.
В любом случае F возрастет,
т. к. коэффициенты 7 и 5 (-7 и -5 в таблице Т0) при переменных
положительны. Будем увеличивать только
(выделяем столбец
, оставляя
(почему
не наоборот?). При
С ростом
значения
убывают
(см. положительные элементы в выделенном столбце
) и
обращаются в нуль при
соответственно (см.
столбец
в
прочерк
в строке
соответствует тому, что при
и возрастании
значение
не убывает и остается неотрицательным).
При
все базисные переменные неотрицательны и
соответствующие планы задачи ЛП допустимы; при
первой
из базисных обращается в нуль переменная
(
- минимальное из отношений в столбце
, выделяем строку
); при
планы
задачи становятся недопустимыми. Значению
отвечает
,
, т. е. допустимый
план
и
. (На рис.1 плану
соответствует
вершина
, переходу от
-
движение по ребру ОЕ).
Из уравнения (выделенная строка в
) выразим
(столбец
также выделен) и подставим полученное
выражение в остальные уравнения , т. е. выполним симплексное преобразование
таблицы
. Получим
.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.