Если допустимая область ограничена и непуста, то она является выпуклым многогранником, и задача ЗЛП в этом случае всегда разрешима, а оптимальное значение целевой функции достигается, по крайней мере, в одной из вершин многогранника. [c.199]
У этой системы имеется очевидное решение, соответствующее вершине многогранника допустимых значений переменных [c.171]
Перейдем теперь к общему случав системы уравнений из относительных выходов. Задача заключается в том, чтобы найти координаты вершин многогранника, заданного условия- [c.40]
Помимо примеров оптимизации конкретных производств описан метод определения координат вершин выпуклых многогранников, задающих допустимые области варьирования коэффициентов и используемых в ходе решения задачи дана блок-схема программы для определения вершин многогранников на ЭВМ. [c.2]
В данной работе описываются примеры оптимизации конкретных производств, метод определения координат вершин многогранников и блок-схема программы определения вершив на ЭВМ. [c.3]
На рис. 4-6 графически иллюстрируются разложения векторов по вершинам многогранников, отражающих область возможных режимов раса установок.31 [c.26]
Излагаемый алгоритм реализует поиск вершин многогранника для случая разделяемых групп dt/ Задача имеет следующий вид [c.47]
Ограничения вида /2.24/ и ограничение-равенство типа /2.25/ на t .i определяют вершины многогранника как пересечение параллелепипеда и гиперплоскости. На практике часто встречаются случаи, когда помимо ограничения-равенства на все оЦ имеются ограничения на группы разделяемых (Aij вида /2.26/, /2.27/ и /2.28/. Яри этом вод разделяемыми группами оЦ понимается такие, для которых I/ пересечение множеств индексов <Аь пусто 2/ объединение вместе с теми индексами, для которых <Ли не вошли ни в одно из множеств, но заданы в ограничениях общего вида, есть множество всех индексов d.i.i. [c.47]
I этап. Определение вершин многогранника для сду- ая двусторонних ограничений на (А,, , , наличия общего ограничения-равенства на все Oil и условий-равенств на t которые группы -I [c.48]
Как известно из общей теории выпуклых тел, совокупность концов векторов М в условиях (I) образует выпуклый многогранник Р, являющийся выпуклой оболочкой концов векторов / ,,/ ,, . ., 7 ,v. Вершины многогранника Р лежат в концах некоторых из векторов Rk [c.285]
Всякая точка границы выпуклого многогранника принадлежит выпуклой оболочке тех вершин многогранника, которые попали в проходящую через эту точку опорную плоскость. Поэтому найдутся такие числа Я,А, при которых [c.285]
Она решается симплекс-методом [3,7], который с помощью аппарата линейной алгебры производит целенаправленный перебор вершин многогранника, определяемого (8.13). [c.174]
Оптимальное решение находится последовательным перебором вершин многогранника (8.13), при котором значение целевой функции z на каждом шаге не уменьшается, то есть [c.174]
Метод симплекс (8.1.) — метод решения основной задачи линейного программирования, заключающийся в целенаправленном переборе вершин многогранника ограничений с помощью методов линейной алгебры. [c.344]
Если в задачах линейного программирования точка экстремума является вершиной многогранника, то в задачах нелинейного программирования она может лежать в вершине многогранника, на ребре (грани) или внутри области. Если задача содержит нелинейные ограничения, то область допустимых решений не является выпуклой и кроме глобального оптимума могут существовать точки локального оптимума. [c.347]
В данном случае определить просто оптимальный план нельзя, так как он может изменяться при различных значениях 1. Поэтому задача формулируется следующим образом требуется разбить отрезок [а, Р]. на конечное число интервалов, в которых целевая функция Z, достигает максимума (минимума) в одной и той же вершине многогранника решений. [c.376]
Пример 12.1. Разбить отрезок / е [0 8] на такие интервалы, в которых целевая функция Z, = 4xi + (2 + t)x2 достигает максимума в одной и той же вершине многогранника решений, и найти соответствующее значение переменных [c.376]
Ясно, конечно, что и в этом случае оптимальным решением является одна или несколько вершин многогранника допустимых решений. Однако если число переменных и ограничений задачи сравнительно велико, то количество вершин выражается астрономическими числами и вычисление значений целевой функции во всех вершинах практически неосуществимо. Например, если п = 50 (число переменных) и т = 25 (число ограничений), тогда число вершин порядка Ю14. Если время, необходимое для вычисления значения целевой функции в каждой точке равно одной миллионной секунды, то перебор всех вершин многогранника займет примерно две тысячи лет. Срок явно неприемлемый. [c.18]
Итак, задача состоит в отыскании минимума линейной функции при линейных ограничениях, иначе говоря, минимума этой функции на выпуклом многограннике допустимых планов. Выше указывалось, что этот минимум обязательно достигается в одной или нескольких вершинах многогранника. Уточним так дело обстоит, если многогранник ограничен. В противном случае решение задачи может и не существовать. Для решения задачи необходимо иметь возможность устанавливать, оптимален ли план без непосредственного сравнения с планами, соответствующими остальным вершинам многогранника. Эта возможность и дается признаком оптимальности плана, формулируемым в виде такой теоремы. [c.29]
Задачи, в которых имеются ограничения типа (4) или сводящиеся к ним, получили название задач целочисленного программирования. Их отличает от линейно-программных моделей, казалось бы, сущий пустяк — добавление условия (4). Но из-за такого пустяка при решении подобных задач возникают большие трудности. Дело в том, что оптимальное решение в этом случае не обязательно находится в одной из вершин многогранника, задаваемого условиями (1) — (3), и обычные методы линейного программирования, использующие это обстоятельство, оказываются бессильными при решении задач целочисленного программирования. [c.110]
Решение задачи находится в вершинах многогранника линейных ограничений, т.е. в нашем случае в одной из двух точек [c.55]
В этом случае при условии С2 [/г - /г + 1 < 3 решение достигается в одной из вершин многогранника ограничений в точке (О, С2 lh l — /Z[+[ + 1). При условии, когда С2 J — h l + 1 > 3, решение достигается в вершине нового многогранника ограничений [c.56]
Решение реализуется в одной из вершин многогранника ограничений [c.66]
Если область D ограничена, то задача ЛП имеет либо единственное, либо бесконечно много решений. Если решение единственно, то оно совпадает с одной из вершин многогранника D. [c.45]
Аналогичная по математической постановке задача линейного программирования с переменными вектор-столбцами, заданными на выпуклых множествах, приведена в работе [14]. Показана принципиальная возможность применения декомпозиционной процедуры для данного типа задач. В результате решения определяются как основные переменные, так и значения элементов матрицы условий. Применение принципа декомпозиции для решения задачи линейного программирования с переменными параметрами модели (обобщенная задача линейного программирования) рассмотрено в работах [15, 16]. Особенностью алгоритма является то, что в процессе решения осуществляется одновременный поиск вершин выпуклых многогранников, на которых заданы варьируемые векторы, и значений интенсивностей технологических процессов. [c.15]
Другое направление решения задачи линейного программирования с переменными векторами условий, заданными на сепарабельных выпуклых множествах, связано с предварительным определением всех вершин" допустимых значений технологических коэффициентов и последующим формированием и решением задачи линейного программирования, в которой для процессов с переменными технологическими коэффициентами рассматривается несколько вариантов, полученных в результате определения вершин" [17-20]. Одна из первых задач подобного типа [17] включала элементарный случай варьирования технологических коэффициентов, когда область их допустимых значений представляла собой многогранник, образованный пересечением и-мерного параллелепипеда одной гиперплоскостью. [c.15]
При использовании метода разложения возникает необходимость нахождения вершин выпуклых многогранников G/. [c.30]
Задачу (9), (10) будем называть я-задачей, а задачу (11), (12) х -задачей. Так как любая точка многогранника (11), (12) является выпуклой комбинацией его вершин, то заменой переменной Xj на zv решение х-задачи сводится к решению следующей 2-задачи. [c.65]
Поэтому первым шагом должно быть получение координат одной из вершин многоугольника (многогранника) допустимых планов. Для этого необходимо преобразовать систему уравнений таким образом, чтобы с ее помощью можно было легко получать координаты вершин многоугольника (многогранника) области допустимых планов. [c.66]
Так как ограничения в виде уравнений представляют собой плоскости в -мерном пространстве, а также условия х,.> 0, то решение ЗЛП ищется в вершинах образованного в -мерном пространстве многогранника, который сам по себе представляет область допустимых решений. [c.200]
Понятие М. используется в геометрической интерпретации задач линейного программирования множество допустимых решений задачи является выпуклым М., базисное решение или опорный план — одной из его вершин. (См. Вершина допустимого многогранника). [c.198]
Вершина допустимого многогранника 47 [c.461]
Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно или случайно (метод случайного поиска) менять ее координаты на определенную величину А, каждый раз переходя в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней, находя одну из координат по уравнению ограничения. Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)... Остановка — в вершине линейного многогранника. Решение найдено (с точностью до А если необходимо, в окрестности найденного решения проводим направленный перебор с шагом Д/2, Д/4 и т.д.). [c.170]
Симплекс-метод. Это один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Он был предложен американцем Г.Данцигом в 1951 г. Симплекс-метод состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. [c.170]
В результате решения каждой из подзадач вида А и Б / 10 задач вида А и одна задача вида Б/ получаются некоторые наборы полувершин. Поэтому следующий шаг состоят в получении полных вершин. Различные комбинации полу вершин дают вершины многогранника для рассматриваемого случаи.. Затем полученные вершины проверяются на удовлетворение ими условий-неравенств типа /2.27/, /2.28/, ес-ш он заданы. [c.49]
Подводя итог описанию методов представления эффективного множества в виде совокупности эффективных вершин, можно сказать, что все они недостаточно эффективны при анализе ситуаций типа представленной на рис. 6.10. В двумерном случае можно, конечно, задать все эффективные точки как выпуклую комбинацию точек А и В, но в многомерном случае это сделать очень трудно, так как, скажем, в пятимерпом пространстве критериев совсем непросто определить, какие из точек являются соседними, чтобы на их основе построить четырехмерный многогранник эффективных точек. [c.312]
С точки зрения математической корректности эквивалентного преобразования и технологической интерпретации модели и ее решения, представляют интерес методы линеаризации, основанные на принципе разложения варьируемых векторов //(") технологических коэффициентов я,-Дм) по вершинам выпуклых многогранников PJ, заданных ограничениями (2.21). Коэффициент аг-Дм)еС/- при этом может быть определен через координаты - = qj, a2q/< > anqj вершин выпуклого многогранника PJ-. [c.29]
В моделях с переменными параметрами, допускающих в некоторых случаях эффективную линеаризацию, в зависимости от алгоритма решения предусмотрена 1) генерация аппроксимационных вариантов, осуществляемая по ходу реализации алгоритма решения, или 2) предварительное определение множества аппроксимирующих вариантов путем разложения варьируемых векторов технологических параметров по вершинам выпуклых многогранников, определяющих допустимые области технологических параметров. [c.43]
ВЕРШИНА ДОПУСТИМОГО МНОГОГРАННИКА [ orner point] (области допустимых решений в задачах линейного программирования) — точка пересечения линейных ограничений (напр., на рис. Л. 1 к ст. "Линейное программирование"). Поскольку множество допустимых решений в задаче линейного программирования всегда выпукло, вершинная точка является крайней точкой множества, и она может быть принята за допустимое базисное решение задачи. [c.47]
См. также Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткостъ, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна— Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Оптимальное распределение ресурсов, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача. [c.173]
Представим себе любую линейную оптимизационную задачу и кратко напомним основные особенности симплекс-метода. Его идея состоит в переходе от одного базисного (опорного) плана к другому таким образом, что линейная форма улучшается на каждом шаге и достигает экстремума. Переход происходит по вершинам выпуклого многогранника условий в я-мерном пространстве, причем на каждом шаге переход осуществляется в соседнюю вершину. При нахождении в такой вершине проводится проверка плана на оптимальность. Линейная форма (гиперплоскость) делит все пространство на две части. Вершинам, находящимся в верхней части, соответствуют отрицательные элементы целевой строки, а вершицам из нижней части — положительные. Переход осуществляется только в соседние вершины из верхнего полупространства до тех пор, пока в нем не останется ни одной вершины. Переход проводится в ту вершину, которой соответствует максимальный по абсолютной величине из отрицательных элементов целевой строки. Если на последнем шаге линейная форма имеет более одной общей точки с выпуклым многогранником условий, то имеется множество оптимальных пла- [c.60]