Линейное программирование. Некоторые примеры экономических задач, приводящих к модели линейного программирования. Геометрическая интерпретация и графическое решение задачи ЛП, страница 9

     При любом выборе базиса все планы, удовлетворяющие (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 плану   соответствует вершина  , переходу от   - движение по ребру ОЕ).

     Из уравнения   (выделенная строка  в   ) выразим 

(столбец   также выделен) и подставим полученное выражение в остальные уравнения , т. е. выполним симплексное преобразование таблицы  . Получим                                 

                              

                                                      .