Основная задача линейного программирования
Таким образом, имеем общую задачу линейного программирования — найти неотрицательные, чтобы они удовлетворяли системе уравнений (5) и обращали в минимум. Имеется ряд переменных. Требуется найти такие их неотрицательные значения, которые удовлетворяли бы системе линейных уравнений: Рассмотрим задачу линейного программирования с ограничениями-неравенствами, которые имеют вид. Допустимым решением… Читать ещё >
Основная задача линейного программирования (реферат, курсовая, диплом, контрольная)
Основная задача линейного программирования (ОЗЛП) ставится следующим образом:
Имеется ряд переменных. Требуется найти такие их неотрицательные значения, которые удовлетворяли бы системе линейных уравнений:
(1).
и, кроме того, обращали бы в минимум линейную целевую функцию (ЦФ).
(2).
Очевидно, случай, когда ЦФ нужно обратить не в минимум, а в максимум, легко сводится к предыдущему, если изменить знак функции и рассмотреть вместо нее функцию.
(3).
Допустимым решением ОЗЛП называют любую совокупность переменных, удовлетворяющую уравнениям (1).
Оптимальным решением называют то из допустимых решений, при котором ЦФ обращается в минимум.
На практике ограничения в задаче линейного программирования часто заданы не уравнениями, а неравенствами. В этом случае можно перейти к основной задаче линейного программирования.
Рассмотрим задачу линейного программирования с ограничениями-неравенствами, которые имеют вид.
и являются линейно-независимыми. Последнее означает, никакое из них нельзя представить в виде линейной комбинации других. Требуется найти, которые удовлетворяют неравенствам и обращают в минимум.
Введём уравнения:
(5).
Где — добавочные переменные, которые также, как и являются неотрицательными.
Таким образом, имеем общую задачу линейного программирования — найти неотрицательные, чтобы они удовлетворяли системе уравнений (5) и обращали в минимум.
