- •Глава I. Линейное программирование.
- •Примеры задач линейного программирования.
- •Различные формы задачи лп
- •Определение 3. Каноническая задача лп называется симплексной, если:
- •Связь между различными типами задачи лп.
- •Вначале сведём общую задачу к однородной. В соответствии с определением 1 п.1.3 для этого достаточно каждое ограничение вида равенства:
- •1.5. Графический метод решения задачи лп.
- •1.6. Выпуклые множества на плоскости и в пространстве.
- •1.7. Геометрическая интерпретация однородной задачи линейного программирования.
- •1.8. Симплекс-метод решения задачи линейного программирования.
- •1.8.1. Пример решения задачи линейного программирования симплекс-методом.
- •Алгоритм симплекс-метода.
- •1.9. Геометрическая интерпретация симплекс-метода.
- •1.10. Основные теоремы.
- •1.11. Методы получения 1-го опорного решения.
- •1.12. Пара симметричных двойственных задач.
- •1.13. Правила перехода к двойственной задаче.
- •1.14. Теоремы двойственности.
- •1.15. Экономический смысл двойственных оценок. Методы нахождения двойственных оценок.
- •1.16. Условие устойчивости двойственных оценок.
- •Глава II. Транспортная задача
- •2.1. Замкнутая модель транспортной задачи.
- •2.2. Другие модели транспортной задачи.
- •Глава III. Игровые методы и модели.
- •3.1. Понятие об игровых моделях.
- •3.2. Постановка игровых задач.
- •3.3. Методы и модели решения игровых задач. Принцип минимакса.
- •3.4. Решения игр в смешанных стратегиях.
- •3.5. Геометрический метод.
- •3.6. Метод линейного программирования.
- •3.7. Игровые модели в условиях коммерческого риска.
- •3.8. Игровые модели в условиях коммерческой неопределенности.
- •Контрольные вопросы.
Различные формы задачи лп
Помимо общей задачи ЛП, выделяют однородную, каноническую и симплексную формы задачи ЛП.
Определение 1. Задача ЛП называется однородной, если все ограничения имеют вид неравенства.
Частными случаями однородной задачи являются задача о ресурсах (или производственная):
(1)
и задача об издержках:
(2)
В первом случае требуется найти максимум функции F («прибыли») при ограниченных «ресурсах» , во втором – минимум издержек F при заданных «нормах потребления» , Более подробно, эти типы задачи ЛП будут рассмотрены в следующих параграфах.
Определение 2. Задача ЛП называется канонической, если все нетривиальные ограничения имеют вид равенства и на все переменные наложены тривиальные ограничения.
Поскольку, переменную можно заменить на новую переменную , удовлетворяющую условию то, без ограничения общности, можно считать, что все переменные канонической задачи ЛП неотрицательны.
Таким образом, каноническая задача ЛП может быть записана в виде:
(3)
или в координатной форме:
(4)
Определение 3. Каноническая задача лп называется симплексной, если:
система линейных ограничений имеет разрешенный вид, то есть матрица системы содержит единичную матрицу ;
столбец свободных членов неотрицателен:
целевая функция F зависит только от свободных переменных.
Разъясним смысл некоторых терминов, встречающихся в этом определении. Во-первых, напомним, что матрица размера тт называется единичной (и обозначается Е=Е ), если:
Например, единичными называются матрицы:
Во-вторых, говорят, что система линейных уравнений (4) имеет разрешенный вид, если ее матрица содержит, возможно после перестановки столбцов, единичную подматрицу Е размера т т. Столбцы единичной подматрицы имеют вид:
и называются базисными.
Определение 4. Переменные, соответствующие базисным столбцам, называются также базисными, а остальные переменные – свободными.
Если исходная матрица системы (4) содержит т линейно независимых строк (или столбцов), то есть ее ранг равен т, то, как известно, с помощью метода Гаусса система может быть приведена к равносильной системе, имеющей разрешенный вид. При этом в качестве базисных могут быть выбраны любые т линейно независимых столбцов исходной системы.
Напомним, что метод Гаусса состоит в приведении матрицы системы к ступенчатому виду с помощью элементарных преобразований, к которым относятся:
перестановка строк;
умножение строки на число ;
замена одной из строк ее суммой с другой строкой, умноженой на некоторое произвольное число .
Как правило, базисными будем считать последние т столбцов матрицы системы.
Замечание: Далее слова «матрица системы А содержит единичную подматрицу» будут означать, что матрица системы А после перестановки столбцов содержит единичную подматрицу Е размера т т, где т – число строк матрицы А.
Определение 5. Решение системы (4) называется базисным, если все свободные переменные равны нулю.
Определение 6. Допустимое базисное решение называется опорным решением.
Напомним, что вектор называется допустимым решением, если он удовлетворяет как нетривиальным ограничениям, в данном случае системе уравнений (4), так и тривиальным:
Таким образом решение системы (4) оказывается допустимым, если все его компоненты неотрицательны.
В дальнейшем будет показано, что оптимальное решение канонической задачи ЛП является опорным.