Cтраница 3
Указанная процедура перехода может быть повторена, если повое базисное решение допускает дальнейшее улучшение г. Симплекс-алгоритм состоит в последовательных повторениях подобных операций до тех пор, пока не будет найдено либо оптимальное решение исходной задачи линейного программирования, либо множество допустимых ее решений, для которых г - - оо. Полезно обратить внимание на то, что рассмотренный процесс поиска X, 2 закончится за конечное число шагов, если ни на одном из них не возникают вырожденные базисные решения. [31]
Если найденные управления допустимы, то решение расширенной задачи является оптимальным и для исходной, если же среди допустимых управлений нет таких, которые удовлетворяли бы равенству (9.270), то найденное решение позволяет судить о характере оптимального решения исходной задачи. [32]
Любое из решений уравнения г / 3 F ( у3), с одной стороны, является допустимым, так как удовлетворяет связям, а, с другой, является решением расширенной задачи и, следовательно, оптимальным решением исходной задачи. [33]
Здесь возможны случаи, когда оптимальное решение исходной задачи для отдельной модели может оказаться предпочтительнее оптимального решения для измененной задачи. Однако во имя общей цели приходится поступиться частью интересов модели. [34]
Свойство 3 не требует доказательства. Из определения эквивалентности расширения следует, что оптимальное решение исходной задачи является одним из оптимальных решений эквивалентной расширенной задачи, а следовательно, удовлетворяет необходимым условиям ее оптимальности. Это свойство позволяет выразить необходимые условия оптимальности исходной задачи через необходимые условия оптимальности расширенной задачи, доказав предварительно эквивалентность расширения. [35]
Эти вершины являются прозондированными, поскольку ЛП-4 обладает целочисленным решением, а задача ЛП-5 не имеет допустимых решений. Наилучшее решение из полученных в прозондированных вершинах представляет собой оптимальное решение исходной задачи. [36]
Если в одной из задач получено целочисленное решение, то ее ветвление далее не производится. Если соответствующее значение целевой функции не меньше /, решение считается принадлежащим множеству X возможных оптимальных решений исходной задачи. [37]
На первом этапе проектировщик находит исходное допустимое опорное решение, а на втором - отыскивает оптимальное решение исходной задачи. [38]
Разумеется, в случае применения настоящего метода к решению практической задачи необходимо уделять внимание вопросам построения сетки для каждой аппроксимации. Вообще говоря, желательно такое построение сетки, которое позволяет отыскать решение, близкое к оптимальному решению исходной задачи. Хотя для этого необходима сетка густо расположенных точек, ее использованию препятствует такой фактор, как большая размерность возникающих аппроксимирующих задач. [39]
Подставляя У в 1, 4 и 5 - е неравенство, убеждаемся, что последние два не удовлетворяются. Следовательно, необходимое условие II теоремы двойственности не выполняется, а значит X не является оптимальным решением исходной задачи. [40]
Такая вновь полученная область обладает двумя важными свойствами: во-первых, она содержит все допустимые целочисленные точки исходной задачи линейного программирования ( поскольку она является выпуклой оболочкой этих точек), во-вторых, все крайние точки новой области - целочисленны. Поэтому любое базисное оптимальное решение модифицированной задачи линейного программирования имеет своими компонентами целые числа и является оптимальным решением исходной задачи целочисленного программирования. [41]
В этих задачах максимизируется целевая функция, причем bt представляют собой объемы капиталовложений, доступные на период i, ati - количества капиталовложений, используемые для проекта / в периоде t, Cj представляют собой значения всех будущих доходов от проекта /, и наконец, Xj - l означает, что проект / принимается для использования. Так как Ь редко известно точно, то решения, получаемые для у ( и), близких к Ь, могут быть столь же хороши, как и оптимальные решения исходной задачи. [42]
Оптимальные значения переменных двойственной задачи часто называют скрытыми доходами. В случае когда константы в правых частях ограничений задают объемы имеющихся ресурсов, скрытые доходы определяют вклад в прибыль, полученный за счет единицы каждого из ресурсов, в соответствии с видом оптимального решения исходной задачи. В задаче, рассмотренной в разд. Увеличение же объема материала Y не приводит к увеличению прибыли. Причина заключается в том, что запас материала Y превышает имеющиеся в нем потребности, что видно из того обстоятельства, что своболная переменная ze входит в оптимальный базис. [43]
Такие задачи могут быть решены путем решения конечного числа стандартных транспортных задач. При этом просто принимают наклон каждого линейного сегмента функции затрат в качестве общего коэффициента затрат для предприятия. Оптимальное решение исходной задачи может быть получено путем перебора всех возможных различных комбинаций таких сегментов ( цен) и решения транспортной задачи для каждой комбинации. Пусть имеется NT комбинаций. Если, например, характеристика одного предприятия имеет три участка линейности, а второго имеет четыре участка, то требуется решить NT12 отдельных транспортных задач. [44]
Как только это будет сделано, можно решать модифицированную задачу линейного программирования любым обычным методом, и полученное базисное оптимальное решение автоматически будет целочисленным. Представленный ниже целочисленный алгоритм обладает следующими свойствами: 1) все дополнительные ограничения сохраняют допустимые точки исходной целочисленной задачи; 2) за конечное число шагов создается достаточное количество дополнительных ограничений для того, чтобы оптимальное решение модифицированной задачи было целочисленным; 3) дополнительные ограничения ( гиперплоскости) проходят по крайней мере через одну целочисленную точку, хотя и не обязательно находящуюся внутри выпуклой оболочки; 4) к. Следует подчеркнуть, что оптимальное решение исходной задачи может быть получено прежде, чем допустимая область сократится до размеров выпуклой оболочки. [45]