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