Решение ЗЛП с точки зрения линейной алгебры

Классификация решений ЗЛП

Определение 2.1. Решение ЗЛП, в котором значения всех переменных неотрицательны , называется допустимым.

Определение 2.2. Любая точка ОДР называется планом.

Определение 2.3. Планы, соответствующие угловым точкам ОДР, называются опорными планами.

Опорный план имеет не более m положительных координат. Если положительных координат в опорном плане меньше чем m, то такой план называется вырожденным.

Определение 2.4. Опорный план, при котором целевая функция достигает экстремального значения, называется оптимальным планом и обозначается .

Система уравнений (ограничений), в которой число уравнений равно числу неизвестных (m = n) рассматривается в обычной алгебре, если при этом определитель системы не равен нулю, то система имеет единственное решение, для нахождения которого разработано немало методов. Если же число уравнений меньше числа неизвестных, то система уравнений имеет бесконечное множество решений. Из этого множества решений допустимыми являются лишь те, в которых переменные принимают неотрицательные значения.

Определение 2.5. Базисом называется любой набор m переменных таких, что определитель, составленный из коэффициентов при этих переменных не равен 0. Эти m переменных называются базисными, а все остальные переменные (n - m) называются свободными.

Определение 2.6. Допустимым базисным решением (ДБР) является такое базисное решение, которое одновременно допустимо, то есть то, которое дает неотрицательные значения переменным.

Определение 2.7. ДБР называется невырожденным, если оно содержит ровно m отличных от 0 компонент.

Педагогический комментарий. Данное лекционное занятие закладывает основы для формирования следующих профессиональных умений студентов-экономистов: умение выявлять проблемы экономического характера при анализе конкретных ситуаций, предлагать способы их решения и оценивать ожидаемые результаты; умение разрабатывать и обосновывать варианты эффективных производственно-технологических решений; умение ставить цель и формулировать задачи, связанные с профессиональной деятельностью, умение использовать для их решения методы изученных дисциплин; умение логически мыслить; умение совершенствовать составление оперативно-производственного плана с использованием инструментария математического программирования; умение эффективно управлять экономическими процессами и регулировать использование комплекса имеющихся ресурсов.

ТЕМА 3. Симплексный метод решения задач линейного программирования

План лекции:

1. Суть симплексного метода

2. Критерий оптимальности решения ЗЛП

3. Алгоритм основного симплекс-метода

4. Алгоритм двойственного симплекс-метода

5. Алгоритм смешанного симплекс-метода

6. Особые случаи симплекс-метода

Дата добавления: 2014-01-13