Cтраница 2
И в прямом и в двойственном симплекс-методах с каждой итерацией связана пара векторов it, % ( в методах с обратными матрицами и тот и другой просто-напросто вычисляются) таких, что значения функционалов прямой и двойственной задач на них совпадают, или, что то же самое, - векторы х, % удовлетворяют условиям дополняющей нежесткости. В прямом симплекс-методе вектор х есть базисное допустимое решение прямой задачи, а ограничения двойственной задачи в точках % на всех итерациях, кроме последней, не выполняются. В двойственном симплекс-методе все наоборот-вектор %, составленный из первых т координат очередного базисного решения задачи (5.18), указывает в допустимую вершину двойственной к (5.17) задачи, а х на всех итерациях, кроме последней, хотя и подчиняется уравнениям прямой задачи, имеет отрицательные компоненты, и поэтому недопустим. [16]
Вид каждой из них строго определен другой. Каждая пара таких ограничений прямой и двойственной задачи называется взаимно сопряженной. [17]
Матрица коэффициентов функций ограничений двойственной задачи получается путем транспонирования соответствующей матрицы прямой задачи. Число ограничений двойственной задачи равно числу переменных прямой задачи, а число переменных двойственной задачи - числу ограничений прямой. Знаки неравенств в ограничениях двойственной задачи изменяются на обратные по сравнению с прямой задачей. Указанные особенности позволяют формализовать процесс построения двойственной задачи при заданной прямой и наоборот. [18]
Если в прямом методе не нашлось номера /, а в двойственном - номера /, то задача решена. Если в прямом методе минимум (2.16) ищется по пустому множеству номеров, то минимизируемая форма не ограничена снизу на множестве допустимых решений, а система ограничений двойственной задачи несовместна. В двойственном методе, наоборот, пустота множества, по которому ищется минимум (2.17), означает несовместность системы ограничений задачи на минимум и неограниченность сверху максимизируемой функции в двойственной задаче. [19]
Первое ограничение двойственной задачи выполняется как строгое неравенство. Это означает, что двойственная оценка сырья, используемого на производство одного изделия вида А, выше цены этого изделия и, следовательно, выпускать изделия вида А невыгодно. Его производство и не предусмотрено оптимальным планом прямой задачи. Второе и третье ограничения двойственной задачи выполняются как строгие равенства. Это означает, что двойственные оценки сырья, используемого для производства единицы соответственно изделий В и С, равны в точности их ценам. Поэтому выпускать эти два вида продукции по двойственным оценкам экономически целесообразно. Их производство и предусмотрено оптимальным планом прямой задачи. [20]