Cтраница 2
Областью допустимых решений задачи линейного программирования является пересечение полупространств, определенных множеством ее ограничений. Целевая функция достигает максимума в одной из вершин выпуклого полиэдра, способ описания которого отличается от того, что рассматривался в гл. Здесь у нас нет множества точек, среди которых следует найти вершины оболочки, вместо этого имеется набор полуплоскостей, ограничивающих эту оболочку, а нам нужно найти вершины. Очевидно, что после построения общей области для данных N объектов мы сможем получить решение задачи линейного программирования. Однако нам нужно найти лишь ту вершину, на которой целевая функция экстремальна ( максимальна или минимальна) и нет оснований полагать, что даже для случая малой размерности необходимо построение всей полиэдральной области. [16]
На первом этапе постановки и решения оптимизационной задачи определяются границы изучаемой системы, которые задаются пределами, отделяющими систему от внешней среды. Выявленные границы определяют область допустимого решения задачи. В общем случае ограничения могут задаваться равенствами и неравенствами любого знака, содержащими независимые параметры. [17]
Целевая функция данной задачи представляет собой отрицательно-определенную квадратичную форму и, значит, вогнута. В то же время область допустимых решений задачи, определяемая ограничениями ( 74) и ( 75), - выпуклая. Следовательно, задача ( 73) - ( 75) является задачей выпуклого программирования. Для нахождения ее решения применим метод штрафных функций. Точка касания одной из этих окружностей с областью допустимых решений и является искомой точкой максимального значения целевой функции. [18]
Вектор X, удовлетворяющий также условиям неотрицательности ( 149), называется допустимым решением ( планом) задачи. Все возможные допустимые решения образуют область допустимых решений задачи. [19]
Очевидно, что расширенная задача удовлетворяет данному выше определению и в том частном случае, когда Я и 1 не зависят от х, переходит в расширение Пагранжа. Так как выбором 1 ( х) и К ( х) можно деформировать R только вне области допустимых решений D задачи нелинейного программирования, то их нужно выбирать так, чтобы максимальное значение R на множестве, дополняющем D до Vx, было как можно меньшим. [20]
Задача Штейнберга является тестовой задачей размещения одно-габаритных элементов. В этом случае условия непересечения объектов и размещения их внутри области выполняются автоматически. Sn разногабаритные, а посадочные места заданы так, что условия попарных непересечений выполняются не при любых размещениях объектов, задача резко усложняется. Трудности появляются прежде всего за счет необходимости учета геометрических ограничений. Вместе с тем, формализовав эти ограничения, можно сузить область допустимых решений задачи, что, в свою очередь, позволяет сократить перебор. [21]