Задача оптимизации в конструировании

2. Метод линейного программирования
Метод применяется для решения задач, связанных с экономикой, организацией и планированием производства: транспортные, проблемы запасов, размещение оборудования, определение оптимального ассортимента продукции, распределение ресурсов, оптимальный раскрой материалов и т.д. Метод легко реализуется на ЭВМ.
Метод используется для решения линейных задач оптимизации, в которых целевая функция F(х) линейно зависит от управляемых параметров

и функции ограничений также линейны.

х₁  0, …, х_п1  0,
где п₁ ≤ п.
В этой задаче имеется m₁ ограничений типа равенств, (m – m₁) ограничений типа неравенств и п₁ ограничений типа неотрицательности.
При отсутствии ограничений типа неравенств и неотрицательности целевая функция не имеет экстремума.
Задача линейного программирования – ЛП – имеет смысл лишь, если
m < п₁.
Задачу ЛП можно решать аналитическими и графическими методами. Аналитические методы, которые представляют собой последовательность вычислений по некоторым правилам, являются основой для решения задач на ЭВМ. Их единственный недостаток заключается в том, что они недостаточно наглядны, в отличие от графических методов, которые используются для решения простых задач ЛП, допускающих графическую интерпретацию.
Общие результаты теории ЛП [18]:
1. Задача ЛП в зависимости от исходных данных имеет либо одно решение, либо континуум решений, либо вообще не имеет решения (лат. – continuum – непрерывное, сплошное – матем.).
2. Область допустимых значений переменных х₁, … х_п имеет вид выпуклого многогранника (при х₁ и х₂ – выпуклого многоугольника).
3. Если существует единственное решение, то оно соответствует одной из вершин многогранника (многоугольника) ограничений.
4. Если решений континуум, то они соответствуют двум и более вершинам многогранника (многоугольника) ограничений, а также всем его ребрам или граням, расположенными между этими вершинами.
5. Решения, соответствующие вершинам многогранника (многоугольника) ограничений называются базисными (опорными) решениями.
Из п. 3 и 4 следует, что при поиске экстремума не нужно просматривать внутренние области многогранника (многоугольника).
На рис. 4.23 представлен многогранник ограничений и определение вершины многогранника, сообщающей целевой функции максимальное значение.

Рисунок 4.23.

В случае простых задач решение получается непосредственно из графика. Для этого строится график, например при п = 2, на котором линии, соответствующие ограничениям, определяют область допустимых решений (рис. 4.24).

Рисунок 4.24.

Методика определений экстремума целевой функции следующая.
Построив многоугольник ограничений и зная, что экстремум находится в одной из вершин многогранника и не нужно исследовать его внутреннюю часть, на некотором расстоянии R от начала координат проводим прямую линию целевой функции. Для этого выбираем произвольно значение F(х), которое подставляем в уравнение целевой функции. Затем определяем точки, в которых целевая функция пересекает оси координат: х₁ (при х₂ = 0) и х₂ (при х₁ = 0). Проведя линию целевой функции, перемещаем ее параллельно самой себе, увеличивая расстояние R от начала координат. При этом растет и значение целевой функции. Далее фиксируется эта прямая в проходимых вершинах многогранника. Последняя вершина (в нашем случае – В) соответствует экстремуму целевой функции, а ее координаты х₁ и х₂ являются оптимальными переменными. Если прямая совпадает с какой-либо стороной многоугольника (например, ВС), то будет континуум решений.
При аналитическом решении основную идею методов составляет направленный перебор некоторых вариантов решения с его последовательным улучшением.
Задачи ЛП удобно решать симплекс-методом (simple – англ. – простой). Это метод последовательного улучшения плана, эффективная процедура проведения вычислений, специальный метод оптимального (направленного) перебора.