Cтраница 2
При стандартном базисе следует прекратить расчеты, как только все двойственные переменные прилгут неотрицательные значения. При наличии отрицательных двойственных переменных нужно выбрать для ввода в базис небазисную прямую переменную, которая является взаимодополняющей для отрицательной базисной двойственной переменной с наибольшим абсолютным значением, б) При нестандартном базисе следует выбрать для ввода в базис двойственную переменную из пебазисной взаимодополняющей пары. [16]
Поскольку транспортная задача является канонической задачей линейного программирования, то на двойственные переменные не накладывается условие неотрицательности. Поэтому знак минус перед ut никакой информации не несет и служит лишь для удобства изложения. [17]
Теперь мы изложим несколько двойственных методов для решения различных выпуклых задач оптимального управления, а именно задач с линейными динамическими связями, выпуклыми целевыми функциями, а также выпуклыми ограничениями. Двойственные методы отличаются от прямых тем, что в процессе итераций преобразуются векторы множителей ( двойственные переменные), которые входят в условия оптимальности (1.2.25) - (1.2.30) ( вектор pk) или (1.2.36) - (1.2.38) ( вектор p ( tf)), а не последовательности управлений ( или управляющие функции), как это делается в прямых методах. [18]
Ег представляют собой произведение элементарных матриц типа ( 47), отличающихся от единичной только одной строкой. Поскольку ( т - Н) - е строки матриц Б - и Во 1 идентичны, эти матрицы определяют те же самые двойственные переменные, что и доказывает пункт а) теоремы 5 в многоблочном случае. Обоснование справедливости пункта б) остается тем же самым, что и для задач с одним блоком. [19]
Реальная трудность линейного программирования состоит в том, чтобы определить, какой именно угол является оптимальным. Следует отметить, что в решении этой задачи дифференциальное исчисление может оказаться полезным и даже весьма полезным, поскольку метод множителей Лагранжа вновь возвращает нас к нулевым производным в точках максимума, а двойственные переменные у как раз и являются множителями Лагранжа в задаче минимизации сх. [20]
Таккера для прямой и двойственной задач. Используя результаты раздела 1.4 и теорему 5.2, немедленно получаем итерационный алгоритм нахождения стратегий для полумарковского процесса с переоценкой. Заметим, что двойственные переменные (5.81) являются одновременно симплекс-множителями для прямой задачи. [21]
Сравнение с ( 4) показывает, что задача Р2 в процедуре Бен-дерса и двойственная к координирующей задаче в схеме декомпозиции являются идентичными. Задача МР2 двойственная к сокращенной координирующей задаче, содержащей только подмножество допустимых столбцов. Пусть ( у, У) - двойственные переменные, соответствующие оптимальному решению некоторой сокращенной координирующей задачи. [22]
Ниже доказано, что В определяет те же самые двойственные переменные, что и В0, и что она является оптимальным, но недопустимым базисом для новой сокращенной задачи. Отсюда следует, что новая сокращенная задача может быть эффективно решена при использовании В в качестве начального базиса в двойственном симплекс-методе. [23]
Вектором правой части ограничений в (3.3) служит вектор коэффициентов максимизируемой линейной формы в (3.1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3.3) выступает линейная форма, коэффициенты которой задаются вектором правой части ограничений задачи (3.1), при этом символ max меняется на min. На двойственные переменные PI накладывается условие неотрицательности. Задачу (3.1), в отличие от двойственной задачи (3.3), будем называть прямой. [24]
Во многих алгоритмах, обсуждавшихся в предшествовавших главах, цены использовались в качестве координирующего механизма. Выдающимся примером такого рода является принцип декомпозиции Данцига - Вулфа ( гл. Цены вычислялись как двойственные переменные в координирующей задаче. При соответствующем изменении этих цен подзадачи вырабатывали предложения для координирующей задачи, которые, будучи скомбинированы с предшествующими предложениями, позволяли сокращать полные затраты. Оно определяет оптимальное решение, как выпуклую комбинацию предложений, а также определяет новые цены, направляемые к подзадачам. Подзадачи только вырабатывают предложения, и данное предложение не обязательно должно быть включено в конечное решение. Таким образом, процесс принятия решений только частично децентрализован. [25]
Характерной особенностью этого метода является использование так называемой координирующей задачи, которая по сравнению с исходной имеет небольшое число строк ( не намного превышающее число связывающих ограничений) и, вообще говоря, очень много столбцов. При этом для решения координирующей задачи не требуется задание всех столбцов в явном виде. Они генерируются в процессе использования симплекс-метода. Поэтому такой подход мы называем методом генерации столбцов. Алгоритм включает итерационный обмен между множеством независимых подзадач, целевые функции которых включают варьируемые параметры, и координирующей задачей. В подзадачи вводится ряд параметров ( двойственные переменные, оценки), получаемые при решении координирующей задачи. В свою очередь в координирующую задачу вводятся решения подзадач, которые оптимальным образом комбинируются и служат для получения новых оценок. Последние вновь вводятся в подзадачи, и итеративный процесс продолжается вплоть до этапа, на котором удовлетворяется критерий оптимальности. Такая процедура имеет изящную экономическую интерпретацию: ее, например, можно понимать как процедуру децентрализованного планирования, когда основной планирующий ( управляющий) орган системы координирует функционирование отдельных подсистем с помощью цен на ограниченные ресурсы. [26]