Материал: Математическое моделирование в экологии

Ф_p=φ_p(х₁, х₂, ..., х_n) ≤ b_p

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

При оптимизации методом дифференцирования оптимум находится приравниванием частных производных целевой функции и затем из решений совместной системы n-уравнений находится значение всех переменных х_i.

i=

Пример. Стоимость продукта зависит от степени его очистки х, ма- териалов на очистку k₁ и затрат труда k₂ что выражается зависимостью

При этом чистота продукта (х) изменяется в пределах от 25% до 90%, а имеющиеся средства на очистку равны , где — максимальная сумма денежных средств.

Требуется найти такое значение х, при котором затраты С ми- нимальны.

Р е ш е н и е. Находим производную

Откуда

.

Это оптимальное значение получено без учета ограничений 25% < х < 90% и .Если они при этом удовлетворяются, то обычно решение находится путем использования в качестве ограничения соответствующего предельно допустимого значения, т.е. для нашего примера нижнего (25%-ного) или верхнего(90%-ного) уровня. При наличии функциональных ограничений их обычно можно использовать до начала дифференцирования для уменьшения числа параметров и, таким образом, основная задача не меняется.

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

Оптимизировать целевую функцию

Y= f(х₁, х₂, ..., х_n) (9.3)

при ограничениях

Ф₁= φ₁(х₁, х₂, ..., х_n) = 0

Ф₂= φ₂(х₁, х₂, ..., х_n) = 0

………………………. (9.4)

Ф_m= φ_m(х₁, х₂, ..., х_n) = 0.

Дифференцируя целевую функцию, найдем ее дифференциал и приравняем его к нулю

Дифференцируем каждые т ограничений

……………………..

Умножаем каждое из т уравнений (9.4) на неизвестный параметр λ_i, i=, называемый множителем Лагранжа. Эти множители различны для разных уравнений.

Имеем

……………………

Если теперь сложить вместе все эти уравнения, прибавив уравнение dY, то получим:

или

Поскольку все параметры х_i независимы, чтобы это уравнение удовлетворялось, каждый из n заключенных в скобки членов предыдущего уравнения должен равняться нулю. Отсюда получим n уравнений вида:

i=

Имеется также m уравнений. Таким образом, имеется всего (n + m) уравнений с (n + m) неизвестными: n неизвестных х_i, и т неиз- вестных . Решение этой системы даст искомое оптимальное реш ение.

Пример. Требуется построить цилиндрический резервуар емкостью 10м³ при наименьшем расходе материала. Таким образом, целевой функцией является площадь поверхности А= 2πr²+ 2 πrl, где r — радиус цилиндра; l — высота цилиндра. Функциональное ограничение V= πr²l = 10м³.

Р е ш е н и е. Находим производные

Уравнение ограничения :

Отсюда получим три уравнения

,

определяющих три неизвестных r, l и , т.е.

4πr+2πl+λ(-2πl)=0;

-2πr+ λ(πr²)=0;

V= -πr²l =0

Решая уравнения, получим:

λ =l=2r; r=

при V= 10м³; r = 1,167м; l = 2,334м.

назад

Лекция 10. Метод линейного программирования.

Методы математического программирования составляют раздел математики, в котором изучаются методы нахождения минимума или максимума функции конечного числа переменных при условии, что переменные удовлетворяют конечному числу дополнительных условий (ограничений), имеющих вид уравнений или неравенств. Различают линейное и нелинейное математическое программирование. Рассмотрим элементы линейного программирования (ЛП).

Линейным программированием называется раздел математики, в котором изучаются методы нахождения минимума или максимума линейной функции конечного числа переменных при условии, что переменные удовлетворяют конечному числу дополнительных ограничений, имеющих вид линейных уравнений или неравенств. Таким образом, задача линейного программирования (ЗЛП) в общем случае формулируется следующим образом: найти такие значения действительных переменных х₁, х₂ ..., х_m для которых целевая функция

Q(x) = р₁х₁ + р₂ х₂ + ... + р_nх_n (10.1) (5.5)

принимает минимальное значение на множестве точек, координаты которых удовлетворяют условиям

(10.2) (5.6)

где коэффициенты а_ij, b_j, р_j, (i =1, j =1,n) — действительные числа.

Можно предполагать, что

b₁≥0, b₂≥0, ..., b_n ≥0.

В матричном виде ЗЛП формулируется

АХ= b; х ≥0; Q_min(х) ≥ р^rх,

где х =(х₁, х₂, ..., x_n)^T Rⁿ, А — матрица размера тn;

р = (p₁, p₂, …, p_n)^T;

b =(b₁, b₂, …, b_m)^T ≥ 0

где Rⁿ — область возможных решений.

Если имеется максимум целевой функции

G(x) = р₁х₁ + р₂х₂ + ... + р_nр_n,

то это равнозначно отысканию минимума функции

Q(x) = -G(x) = (-p_i)x_i + (-р₂)x₂+ ... + (-р_n)x_n.

Если в дополнительных условиях имеется неравенство, например,

а_i1х₁ + а₂х₂ + ... + а_in х_n ≤ b_i

то введением вспомогательного переменного множителя у можно перейти к уравнению

а_i1х₁ + а₂х₂ + ... + а_in х_n= b.

Для нового переменного также справедливо неравенство у ≥ 0; в целевую функцию оно входит с коэффициентом Θ. Если для переменной х_i, не задано условие х ≥ 0, то могут быть введены, например, новые переменные х_j' и х_j" с дополнительными условиями х_j' ≥ 0 и х_j"≥ 0, причем х_j = х_j' - х_j". Поэтому в дальнейшем будем рассматривать в основном, задачи минимизации целевой функции Q(x) при условиях, заданных линейными уравнениями с неотрицательными членами b_i в предположении неотрицательных переменных. Эти задачи и будем называть задачами линейного программирования (ЗЛП). В математической литературе ЗЛП записывается в виде

(10.3)(5.7)

Любая ЗЛП может быть приведена к виду (5.7). Двойственной к выражению (5.7) будем называть задачу

Точка х = (х₁, х₂, …, х_n)^T, удовлетворяющая всем условиям, называется допустимой. Множество всех допустимых точек называется допустимой областью. Если после отбрасывания одного условия допустимая область не меняется, то такое условие называется лишним. В задачах с двумя переменными можно отказаться от перехода от неравенств к уравнениям, так как линейное неравенство а₁х₁+ а₂х₂ ≤ b допускает непосредственную геометрическую интерпретацию: все точки, удовлетворяющие этому неравенству, лежат на прямой а₁х₁+ а₂х₂ = b и в одной из двух полуплоскостей, на которые эта прямая делит всю плоскость.