3.12. Многомерная безусловная оптимизация

Пусть целевая функция зависит от n проектных параметров:

Для простоты изложения условимся отыскивать экстремум целевой функции, зависящей от двух проектных параметров . Зададим координаты начальной точки M⁰(x₁₀, x_20). На первом этапе параметр зафиксируем, а x₂ будем считать переменным. Целевая функция будет зависеть только от одного параметра. x₂, так что, применив к ней вышеописанный метод решения задач одномерной оптимизации, находим экстремальное значение по этому свободному параметру, то есть, при фиксированном значении параметра x₁=х₁₀. На этом первый шаг заканчиваем. Взяв полученную точку в качестве начальной и, приняв теперь в качестве свободного параметра , находим экстремум по этому параметру, зафиксировав, соответственно, х₂. В результате получаем конечную точку M первого этапа. Взяв её в качестве стартовой на втором этапе, и, повторив схему движения первого этапа, получим возможность продолжения пути на третьем этапе и т.д. Процесс следует закончить, если для двух соседних этапов: k-го и (k+1)-го выполнятся соотношения

для ,

где -точность вычислений i-го параметра. Впрочем, точность может быть одинаковой по всем параметрам.

3.13. Условная оптимизация при решении инженерных задач

До сих пор мы рассматривали численные методы для задач безусловной оптимизации. На практике довольно часто задача кроме целевой функции предполагает наличие дополнительных условий и становится задачей условной оптимизации. Наиболее простой случай такой оптимизации имеет вид:

т.е. для каждого проектного параметра введены граничные условия.

Такую задачу можно решить по той же схеме решения, что и для безусловной оптимизации. В том случае, когда значение переменной на k-ой итерации выходит на ( или за ) нижнюю границу, т.е. оказывается а , то за минимальное значение принимают а и поиск продолжается по остальным переменным. Аналогично осуществляется поиск и для верхней границы.

3.14. Линейное программирование

Мы рассмотрели задачи условной оптимизации, которые могут быть сформулированы при решении инженерных задач. В экономике такой класс задач является предметом изучения раздела науки – математического программирования. Последнее слово появилось в наименовании по той причине, что широкое решение таких задач стало возможным только с появлением электронной вычислительной техники. Совокупность проектных параметров называется планом, а сами параметры – компонентами плана. Ограничений в таких задачах может быть сколько угодно. Самый простой случай ограничений - это когда количество ограничений равно количеству проектных параметров. В этом случае задача имеет единственное решение. Такие задачи практически не представляют интереса, т.к. не предоставляют возможности выбора.

В настоящее время уже выделился определённый класс задач, эффективно решаемых методами математического программирования. Это задачи: распределительные; управления запасами; замены оборудования; упорядочения и согласования; выбора оптимальных режимов движения и др.

Если в решаемой задаче целевая функция и ограничения линейно зависят от проектных параметров, то задача относится к разделу линейного программирования, в противном случае к нелинейному. Мы рассмотрим только задачи линейного программирования.

Рассмотрим пример: Цех располагает четырьмя группами оборудования А, В, С, D и выпускает 2 вида продукции. Количество единиц оборудования и его занятость приведены в таблице. Там же даны величины прибыли, получаемой за счет выпуска единицы продукции каждого вида.

Задача: определить план выпуска продукции каждого вида, обеспечивающий максимальную прибыль.

Группы оборудования	Количество единиц оборудования в группе	Количество единиц оборудования, используемых при выпуске единицы продукции
		Вида 1	Вида 2
А	12	2	2
В	10	1	2
С	16	4	0
D	12	0	4
Прибыль		200 руб.	300 руб.

Математическая постановка задачи:

Обозначим через x₁ и x₂ – количество единиц продукции 1-го и 2-го вида соответственно, планируемое к выпуску. Тогда целевая функция выразится:

L (x ,x ) = 200x₁ + 300x_{2 .} (54)

Ограничения, определяющие занятость оборудования по группам:

А: 2x₁ + 2x₂  12 x₁ + x₂  6,

B: x₁ + 2x₂  10 или x₁ + 2x₂  10,

C: 4x₁ + 0x₂  16 x₁  4, (55)

D: 0x₁ + 4x₂  12 x₂  3.

Естественные ограничения:

x₁  0, x₂  0. (56)

Требуется определить наибольшее значение целевой функции L(x , x₂) при ограничениях (55) и (56).

Рассмотрев пример, можем сформулировать задачу линейного программирования в общем виде: необходимо найти наибольшее (наименьшее ) значение целевой функции

(57)

при ограничениях: ресурсных:

, (i = 1, 2, …, m) (58)

и естественных:

, (j = 1, 2, …, n), (59)

где - коэффициенты при неизвестных в ограничениях.

В задачах линейного программирования ограничения формируют область допустимых решений.

Если задача имеет только два параметра, то она может быть решена графически. При большем числе параметров для решения надо использовать специальный метод, называемый симплекс – методом.

Проиллюстрируем суть графического метода на примере решения задачи, поставленной выше

1. На плоскости построим систему координат x₁, x₂.

2. Построим область допустимых решений. Из естественных ограничений (47) следует, что она расположена в первой координатной четверти, т.е. выше оси Оx₁ и правее оси Оx₂.

На первом ресурсном ограничении покажем как строится область. Сохранив в ограничении только знак равенства, превращаем это ограничение в уравнение прямой x₁ + x₂ = 6. Строим эту прямую. Она делит плоскость на две полуплоскости: полуплоскость, лежащую выше и полуплоскость лежащую ниже её. Для определения требуемой полуплоскости возьмём любую точку, принадлежащую одной из полуплоскостей, и поставим её координаты в рассматриваемое ограничение – неравенство. Для простоты вычислений возьмём точку начала координат, т.е. точку O(0,0), поставив её координаты в неравенство, получим верное выражение: 0  6. Из этого следует вывод о том, что в область допустимых решений входит полуплоскость, расположенная ниже прямой x₁ + x₂ = 6.

Аналогично определяем полуплоскости, соответствующие остальным ограничениям. Общая часть всех полуплоскостей образует область проектирования OABCD, выделенную на рисунке.

Вершинами образованного пятиугольника OABCD являются точки пересечения прямых. Любая точка, принадлежащая этому пятиугольнику, определяет допустимое решение задачи или допустимый план, который может быть выполнен при имеющихся ресурсах.

3. Для нахождения оптимального плана нам необходимо найти такую точку, принадлежащую пятиугольнику, в которой целевая функция достигает наибольшего значения.

Рассмотрим на плоскости x₁x₂ линии уровня этой целевой функции; они представляют семейство прямых линий, параллельных прямой

L = 200x₁ + 300x₂

Зададим значение L таким, чтобы прямая проходила через область допустимых решений. При L = 600 получим прямую 2x₁ + 3x₂ = 6. Построим её. Параллельный перенос этой прямой вверх соответствует возрастанию целевой функции, вниз – убыванию. Строим семейство параллельных прямых до тех пор, пока одна из них не соприкоснется с областью допустимых решений в единственной точке. В нашем случае общей последней точкой является точка В с координатами x₁ = 3 и x₂ = 3, полученная пересечением линий : x₁ + x₂ = 6 и x₁ = 3. Решение x₁ = 3 и x₂ = 3 – единственное из возможных, позволяющих нам получить наибольшую прибыль; при данных значениях параметров она достигнет 1500 руб.

В общем случае предельная прямая может совпасть с одной из границ области допустимых решений. Тогда любая точка этой границы является оптимальным решением, что дает право говорить о бесчисленном множестве решений задачи.