Cтраница 3
Из предыдущего ясно, что в рамках теоремы 2.4 эти два понятия, а также понятие решения двойственной задачи эквивалентны. [31]
Например, решая некоторую последовательность задач линейного программирования, мы можем со сколь угодно большой точностью найти решение двойственной задачи. Конечно, эти методы требуют уже применения ЭВМ. [32]
Исследование многих задач в условиях неопределенности параметров может проводиться на основе линейных оптимизационных моделей, с последующей оценкой влияния неопределенности через решение двойственной задачи и анализа на чувствительность решения исходной задачи. Выполнение анализа с помощью специальных алгоритмов и одновременно с решением исходной задачи требует значительно меньших усилий специалистов по сравнению с непосредственным решением измененной задачи. [33]
Заметим, что если cs 0 в каждом столбце, то наше полное решение допустимо также по столбцам, и мы имеем решение двойственной задачи. [34]
Из 3.3 известно, что верхняя строка симплексной таблицы содержит с, С ] - ла7 -, и если Cj 0, то я - решение двойственной задачи. Итак, оптимальная таблица содержит оптимальные решения как прямой, так и двойственной задач. Всегда имеется возможность выбора: решать ли прямую задачу или двойственную, использовать прямой или двойственный метод. В приведенном выше примере нецелесообразно было решать двойственную задачу, поскольку тогда понадобилось бы вводить четыре слабые переменные и задача имела бы семь неотрицательных переменных и четыре уравнения. [35]
АЬ является одновременно допустимым, и двойственно допустимым, то оно вместе с отвечающим ему вектором (7.14) определяет оптимальный ( наиболее экономный) раскройный план, а вектор (7.16) представляет решение двойственной задачи. [36]
Теперь можно увидеть, в чем заключается единственное реальное различие между подходом к решению прямой задачи линейного программирования па основе симплексного метода и методом итераций по стратегиям, примененным к решению двойственной задачи. В последнем алгоритме на каждой итерации просматриваются все вершины и одновременно делаются все возможные улучшения. Напротив, в симплексном методе па каждой итерации вводится только одна переменная, после чего проверяется достижение оптимальности. Теорией еще не установлено, можно ли считать метод с многократным введением переменных перед каждой проверкой оптимальности более эффективным с вычислительной точки зрения. [37]
В силу теоремы 1.5 любое базисное решение невырождено, а в силу условий дополнительной нежесткости любое оптимальное решение двойственной задачи должно удовлетворять соответствующей невырожденной системе из N двойственных равенств; следовательно, решение двойственной задачи единственно. [38]
Суть метода состоит в таком последовательном переборе угловых точек допустимого множества Qu двойственной задачи (5.6), при котором значение целевой функции Ь, уу возрастает, то есть в примеаении симплексного метода к решению двойственной задачи. [39]
С - / а ф ( а), другими словами, если а - наибольшее решение уравнения Р ( а) 0, где р ( а) ср ( а) / а - С, то решение двойственной задачи сводится к минимизации - - при ограничительных условиях ( ЗОа) и ( ЗОЬ), и эта задача является в точности той задачей линейного программирования, решение которой дает решение семейства задач о вступительных взносах с f ( i) - g ( i) - а; здесь ф ( а) / ( а) - С в точности равно E Z - - la - G ( i0) - платежу в исходном классе задач правил остановки, которому с помощью разложения на циклы мы поставили в соответствие задачу восстановления. [40]
При решении исходной задачи одновременно может быть получено и решение ее двойственной задачи. Решением двойственной задачи являются теневые цены для ресурсов исходной задачи. [41]
Каждой прямой задаче линейного программирования соответствует другая, симметричная ей двойственная задача. Результаты решения двойственной задачи являются двойственными оценками прямой задачи линейного программирования. Математический смысл оценок широко описан в специальной литературе. [42]
Эта система позволяет при объеме оперативной памяти свыше 64 К эффективно решать задачи, системы ограничений которых включают до 1500 строк. Пакет осуществляет решение прямой и двойственной задачи линейного программирования, выдает информацию о значениях ошибок, позволяет создавать контрольные точки, объединять блоки, вносить изменения и дополнения в систему ограничений и целевую функцию. Разработанные с целью привязки пакета к задачам планирования нефтеперерабатывающих производств Генератор модели и Интерпретатор обеспечивают автоматическое построение модели планирования НПП на основе исходных данных о структуре производства, технологических агрегатов и установок, а также представление результатов решения в виде выходных документов, используемых планово-экономическими службами завода. [43]
Согласно теоремам этого параграфа, при предположениях 1 - 3 двойственная задача не содержит ограничений, за исключением условий мГ О, и h дифференцируема всюду в int D. Таким образом, для решения двойственной задачи вновь подходит метод наискорейшего спуска. [44]
Замечание 4.2. Подчеркнем, что двойственная задача имеет единственное решение, если разрешима основная задача. Однако существование и единственность решения двойственной задачи непосредственно следуют из того факта, что множество KF, Р непусто. Таким образом, возникает предположение, что двойственная задача может иметь решение даже в том случае, когда основная задача неразрешима. [45]