Для обеспечения приемлемой точности аппроксимации опорные планы Ajl должны быть линейно независимыми и число их должно быть не меньше размерности векторах. [c.20]
Перейдем к изложению схемы решения г-задачи. Пусть известны векторы базиса некоторого опорного плана г-задачи. Обозначим через Л вектор относительных оценок условий г-задачи. [c.66]
Поскольку задача линейного программирования (1.7) — (1.11) имеет оптимальный план х°, она должна иметь и опорный оптимальный план. Обозначим его через х. Тогда базисным компонентам вектора х соответствуют линейно-независимые столбцы матрицы [c.171]
Доказательство. Вектор х — опорный план системы ограничений задачи линейного программирования (3.1) — (3.2). Это значит, что существует базис Вг, образованный т вектор а ми -столбцами матрицы (А, Е) (Е — единичная матрица), такой, что xfl"> = В Ь О. [c.281]
Если траектория оптимальна, то существует определяемая вектором = — 1, gl,...,gm гиперплоскость, опорная к конусу Кр в его вершине, т. е. [c.63]
Целью дальнейшего является нахождение вектора g, определяющего гиперплоскость G, опорную к D в точке е. Этот искомый вектор g удовлетворяет уравнению [c.189]
Определение 3. Гиперплоскость G, проходящую через точку (ft dQ ортогонально некоторому вектору g, будем называть опорной к Q в точке дг, если [c.370]
Если тело Q замкнуто и ограничено, то каждому вектору g соответствует (быть может, не единственная) точка qlt в которой g определяет опорную к Q гиперплоскость. Эта точка qt есть решение простейшей задачи выпуклого программирования [c.370]
Теорема 1 утверждает, что каждому вектору g соответствует по крайней мере одна точка g (g) границы выпуклого множества Q, в которой g определяет опорную к Q гиперплоскость G. Наоборот, [c.371]
Лемма 2. max / (g) Л, м достигается этот максимум на векторе g, определяющем опорную к Q в точке Ле гиперплоскость. [c.374]
В самом деле, пусть g — вектор, ортогональный опорной к Q в точке Ae 8Q гиперплоскости G. Тогда [c.374]
Для построения прямой Z— Зх + 4х2 = 0 строим вектор-градиент С = (3 4) и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора С. Из рис. 7.5 следует, что по отношению к многоугольнику решений опорной эта прямая становится в точке С, где функция принимает максимальное значение. Точка С лежит на пересечении прямых Ь и 13- Для определения ее координат решим систему уравнений [c.205]
Для того чтобы новый допустимый план был опорным, необходимо исключить один из использовавшихся способов, так как (т + ) векторов в m-мерном пространстве всегда линейно зависимы и базиса не образуют. Подсчитаем величину 6 — [c.33]
Предположим, что уже имеется допустимый план х, причем такой, что способы, используемые в нем, являются базисными векторами (такой план называется опорным) . Можно считать, что базис состоит из первых т векторов av a2,. .., ат, так как этого всегда можно добиться изменением нумерации способов. Поскольку всякий вектор m-мерного пространства можно разложить по этому базису, найдем разложения всех векторов способов и вектора ограничений. Коэффициенты этих разложений объединены в табл. 3 (так называемая симплексная таблица). [c.37]
Эта задача отличается от рассматривавшейся задачи линейного программирования в канонической форме тем, что в ней требуется отыскать максимум, а не минимум. Понятно, что план ж такой задачи оптимален тогда и только тогда, когда k план опорный, так как векторы а, и 2 линейно независимы — образуют базис. [c.41]
Разность а3 — С3 = — 1 — 1 = — 2 [c.41]
Принцип выбора столбца, вводимого в базис, определяется необходимостью обеспечивать то, чтобы очередной базис определял опорную плоскость, ниже которой располагаются все небазисные векторы. Для этого требуется, чтобы оценки всех небазисных векторов а0/(р) (/еМр)), вычисляемые по формулам [c.72]
Процесс решения начинается с анализа исходного опорного плана задачи, т. е. с анализа некоторого набора неотрицательных чисел x t, xs,,. .., xs, определяющих интенсивность или время использования каждого из m технологических способов производства с линейно независимыми векторами затрат aS . .. as. Способы производства, отвечающие векторам базиса, назовем базисными технологическими способами. [c.184]
Решение задачи по этому методу начинается с анализа некоторого опорного плана сопряженной задачи. По существу, план сопряженной задачи представляет собой план, в котором приведена система предварительных оценок производственных факторов, удовлетворяющая условиям [152] и [153]. Опорному плану сопряженной задачи соответствует m рентабельных способов производства с линейно независимыми векторами затрат, называемых базисными способами. Базисные способы, определяющие технологию производства, обозначим Si, s2,. .., sm. Реализация плана производства не всегда может быть проведена, если ограничиться только способами производства, рентабельными относительно заданных предварительных оценок. [c.186]
План задачи X будем называть опорным, если система векторов Р,-, у, соответствующая всем коммуникациям, по которым согласно X намечены положительные перевозки, линейно независима. Систему векторов опорного плана, соответствующих положительным перевозкам, назовем базисом этого плана. [c.200]
Опорным планом называется любой вектор X=(Xj, X2,. .., Х ), удовлетворяющий условиям (4.5) и имеющий не более чем т ненулевых компонент. [c.47]
Если в столбце свободных членов все коэффициенты bio > О, то вектор Х= (Xj = Ъю, Х2 = Ь2о, -., Хт = Ьт0, Хт + 1 = 0,. .., Х = 0) называется начальным опорным планом. Значение целевой функции равно элементу 5-столбца в F-строке. [c.49]
Чтобы найти некоторое опорное решение задачи (9.7)— (9.9), достаточно выбрать базис системы А , Л2,. .., Л векторов условий этой задачи так, чтобы вектор ограничений В раскладывался по нему с неотрицательными коэффициентами. [c.193]
Базис Л,-,, Л/2,. .., Л,- системы векторов условий А , Аг,. .., Л задачи (9.7)—(9.9) называется базисом опорного решения a = (d1 d2 . .. dn) этой задачи, если d = Q при i =/i, i2,. .., ir. [c.193]
Вектор Р = (0 0 . . . 0 Ьг Ъ2 . . . Ьт) является опорным решением задачи (9.22) — (9.24). [c.201]
Таким образом, принимая вектор р за начальное опорное решение, вспомогательную задачу можно решить симплекс-методом. Пусть р°=С- 3 ... yl yl . . Ут)— оптимальное опорное решение задачи (9.22) — (9.24). [c.201]
Таким образом, для решения задачи выпуклого квадратичного программирования (9.68) — (9.7 0) достаточно найти опорное решение системы (9.73), базис которого не содержит сопряженных векторов условней. Такое опорное решение можно найти методом искусственного базиса. [c.232]
Решая эту задачу симплекс-методом, необходимо следить за тем, чтобы на каждом шаге базис опорного решения не содержал сопряженных векторов условий. [c.233]
Базис опорного решения 193 — системы векторов 47 Беллмана метод 224 [c.327]
Нетрудно показать, что D(/,) при /с=2 совпадает с третьим квадрантом плоскости, который разбивается векторами F, и F2 (векторами, опорными к V в точках (1,0) и ( 0,1)), на три сектора 5,, 5,, 5,. Если F(x) е 5,, то объект х в опорной классификации Н,, однозначно относится к первому классу, если F(jr)eS,, то х относится ко второму классу, и, наконец, если F(x) e S2, то х с некоторыми весами [c.65]
Альтернатива для выпуклого конуса выпуклый конус KF в конечномерном пространстве Ет+1 либо совпадает со всем пространством, либо занимает не более полупространства. В последнем случае существует опорный вектор g Em+l такой, что [c.46]
Опорный вектор 46 Особый режим 236, 313 Отделимость выпуклых тел 371j 3 Ошибка аппроксимации 225, 240, 293 [c.485]
Гиперплоскость Н = х е EJ (с, х) = h (см. Гиперпрострапство, Гиперплоскость, а также Скалярное произведение векторов) называется опорной по отношению к множеству М в его граничной точке х ), если удовлетворяются следующие условия (с, х) < h для всех х 6 М и (с, xt) = h для указанной точки ха. [c.241]
Как известно, на каждом шаге процесса решения в любом из методов линейного программирования выполняют следующие операции а) получают решение б) проверяют полученный план на оптимальность в) в случае неоптимальности выявляют тот вектор, который нужно ввести в базис (опорный план) улучшенного плана. В методе Данцига—Вулфа этот процесс распределяется между главной задачей, с одной стороны, и локальными задачами — с другой. [c.179]
Здесь я<°> — произвольный n-мерный вектор, принадлежащий множеству К — начальная точка процесса ps — величина шага на s-й итерации YS — нормирующий множитель gw — случайный вектор, условное математическое ожидание которого относительно х<-° х . . . , x(s> зависит линейно от обобщенного градиента срж (субградиента или опорного функционала) функции
Пусть i — некоторое целое число, 0 <[ г < N, рассмотрим траектории типа (1), отличающиеся от опорной траектории (1) только значением х в точке tf, а именно рассматриваются смещенные положения точки x(t() x(t ) + hkek, й = 1, 2,. . ., /г, где ek — Ахи орт в ге-мер-ном пространстве, hk — шаг по k-ii компоненте фазового вектора. В сумме (2) при этом меняются только два слагаемых — 8F J/ и gjpf+ /j. Перебрав таким образом 2га вариантов ), находим лучшую [c.127]
Обычно в конце процесса достигаются малые, но все же отличные от нуля величины x o, поэтому оценка Xmin сверху не является точной. Тем не менее, ее можно считать практически достоверной. Это следует из простой оценки обозначим через g вектор, определяющий гиперплоскость, опорную к Р в искомой точке Хт, е. Обычно в процессе итераций g - g. Имеем [c.442]
Следует обратить внимание на то, что не всем сопряженным базисам соответствуют допустимые базисные планы прямой задачи. В частности, вектор b не может быть разложен с неотрицательными коэффициентами по базисам a1, a2 , а3, а4 или а4, а5 . В связи с этим систему коэффициентов разложения вектора b по сопряженному базису называют псевдопланом. В то же время базис а2, а3 является допустимым для прямой задачи, и, более того, из иллюстрации видно, что он, с одной стороны, определяет максимум прямой задачи (наивысшую точку пересечения прямой, проходящей через конец b, с конусом /С), а с другой — минимум двойственной (низшую точку пересечения этой прямой с лежащей над К опорной гиперплоскостью) [c.70]
По теореме о разделяющей гиперплоскости существует вектор Аг, такой что qAz < и v z , /V