Двойственность в линейном программировании

Этому способу в некотором смысле соответствует метод двойственных оценок, развитый в рамках теории двойственности линейного программирования [63]. Метод двойственных оценок может применяться в том случае, когда наряду с задачами оптимального управления и планирования работы предприятия решаются задачи оптимального планирования отрасли. [c.59]

Согласно теоремам двойственности линейного программирования [56], существование решения прямой задачи (17) влечет существование двойственной задачи [c.203]

ПРИНЦИП ДВОЙСТВЕННОСТИ и ЗАДАЧАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ [c.460]

Следует еш,е отметить, что двойственная задача имеет определенный физический смысл, соответствующий постановке исходной задачи. Подробнее об этом сказано ниже при рассмотрении конкретного примера применения линейного программирования для планирования химического производства. [c.470]

Величина Ui — F,- характеризует изменение min Kj при малых колебаниях / , дает оценку значимости г-му наблюдению. Малые колебания в г, как следует из теории линейного программирования, не меняют решений двойственной задачи. Это позволяет из (4) и аналогичного соотношения для max Kj [c.88]

V.2.3. Двойственность в линейном программировании [c.191]

С каждой задачей линейного программирования связана другая задача, называемая двойственной эта последняя такова, что решения этих задач являются в некотором смысле равносильными. Первоначальная задача называется исходной, или прямой. [c.191]

Прямая и двойственная задачи линейного программирования интересны как теоретически, так и практически. В табл. V.2, где показаны эти двойственные отношения, параметры Лх,. .., я, являются двойственными переменными. Важно отметить, что существует прямое отношение между я и исходным ограничением i с правой частью bi, а также между переменной / в исходной задаче и ограничением / в двойственной (с правой частью ). В табл. V.3 указаны эти отношения. Величина Ai в табл. V.3 обозначает -ю строку матрицы А. [c.191]

Относительно анализа устойчивости задач линейного программирования существенна интерпретация двойственных переменных. Можно показать, что последние являются показателями изменяемости оптимального решения в зависимости от изменения правой части в записи задачи линейного программирования. [c.197]

В тех случаях, когда задачи АСУ решаются с использованием дисковой операционной системы ДОС ЕС, программное обеспечение задачи планирования строится на основе пакета LPS-360 [30]. Эта система позволяет при объеме оперативной памяти свыше 64 К эффективно решать задачи, системы ограничений которых включают до 1500 строк. Пакет осуществляет решение прямой и двойственной задачи линейного программирования, выдает информацию о значениях ошибок, позволяет создавать контрольные точки, объединять блоки, вносить изменения и дополнения в систему ограничений и целевую функцию. Разработанные с целью привязки пакета к задачам планирования нефтеперерабатывающих производств Генератор модели и Интерпретатор обеспечивают автоматическое построение модели планирования НПП на основе исходных данных о структуре производства, технологических агрегатов и установок, а также представление результатов решения в виде выходных документов, используемых планово-экономическими службами завода. [c.179]

Эти обстоятельства иногда позволяют использовать принцип двойственности в задачах линейного программирования для сокращения объема вычислений в процессе решения задачи и экономии необходимого объема запоминающих устройств вычислительной машины. Поскольку результаты решения исходной и двойственной задач совпадают, можно так выбрать представление решаемой задачи, чтобы обеспечить выполнение матричных операций с матрицами меньшего порядка. При этом руководствуются правилом если число независимых переменных п в исходной задаче меньше числа ограничений т, то имеет смысл решать двойственную задачу, поскольку вместо операций с матрицами порядка т будут производиться операции с матрицами порядка п (согласно числу ограничений двойственной задачи). [c.464]

Каждой прямой задаче линейного программирования соответствует другая, симметричная ей двойственная задача. Результаты решения двойственной задачи являются двойственными оценками прямой задачи линейного программирования. Математический смысл оценок широко описан в специальной литературе. См., например [41]. [c.37]

Уравнение (У1,47) справедливо только при ограничениях, изложенных в следующем разделе (стр. 318). В нем говорится, что основной оптимум может быть достигнут посредством подбора цен Р так, чтобы максимизировать прибыль, достигаемую при оптимизации подзадач. Уравнение ( 1,47) констатирует далее, что градиенты двойственной функции представляют собой просто разность между количеством товара, потребляемого одной подсистемой (например, х для первой подсистемы), и количеством товара (например, 2 ), которое другая подсистема решает поставить по существующей цене. Таким образом, градиенты двойственной функции имеются при условии выполнения небольших дополнительных вычислений, и задача подбора цены является просто задачей выпуклого программирования без ограничений. Оценку оптимальных цен можно получить, решая относительно и Р следующие линейные уравнения [c.316]

Если известно или установлепо распределение случайного вектора е, то критериальную функцию можно построить на основе принципа максимального правдоподобия. В условиях неопределенности, когда входные величины задаются в виде диапазона возможных значений без указаний на вероятностные характеристики, ип один М3 существующих критериев согласования не может быть приият безоговорочно как единственно правильный. В последнее время выполнены исследования по сравнительной характеристике различных критериев [50—55]. Как следует из этих работ, чебышевскнй критерий имеет ряд преимуществ по сравнению с другими сохраняется физический смысл решений независимо от малых колебаний входных данных, решение устойчиво к изменению законов расиределения, имеется (Возможность наложения двухсторонних ограничений на область решения, возможно применение аппарата двойственности линейного программирования для анализа структуры решений с целью определения выпадающих значений. [c.201]

Маргинальные значения Vi , описываемые соотношениями (VI 11,223), кроме этой чисто вспомогательной роли, представляют самостоятельный интерес в связи с так называемым принципом двойственности в задачах линейного программирования. Он заклю-чается в следуюн1,ем [c.460]

Еще Дж. Данциг показал [56], что симплекс-метод для сетевой задачи линейного программирования (ЛП) сводится к целенаправленному перебору деревьев этой сети. А теоретические основы построения и алгоритмизации сетевых потоковых моделей изложены в известной книге Л. Форда и Д. Фалкерсона [237], которые, в частности, раскрыли двойственность задач о максимальном потоке и минимальном разрезе сети. Имеется ряд монографий отечественных и зарубежных авторов, в которых рассматриваются различные вопросы теории и методов решения нелинейных сетевых транспортных и других экстремальных задач на графах [35, 66, 257]. Применительно к трубопроводным системам (ТПС) наиболее полное истолкование сетевых потоковых моделей (на примере задач оптимизации развития, текущего и перспективного планирования работы газотранспортных систем и Единой системы газоснабжения страны) дано в монографии [228]. [c.166]

Такую связь также можно получить путем использования информации о решении двойственных задач. В теории линейного программирования [9] имеет место общая фзрмула, связываотая величину приращения в решении с малыми колебаниями в правых частях, матрицы коэффициентов и решение двойственной задачи. Эта формула является обобщением соотношений (3-5). [c.41]

Прямая задача геометрического программирования имеет нелинейный критерий и содержит систему нелинейных ограничении в виде неравенств, а двойственная ей задача формулируется как поиск экстремума нелинейной функции специального вида нри линейных ограничениях. На практике чаще применяют алгоритмы решения двойственной задачи с последующим расчетом оптимальных значений переменных прямой задачи. Алгоритмы представляют собой итеративные процедуры решения задач ли-псппого или квадратичного программирования, получающихся п результате соответственпо линейной или параболической ап-п юксимации критерия двойственной задачи. [c.242]

Справочник химика 21

Химия и химическая технология