7. Условная оптимизация. Линейное программирование. Пример постановки задачи оптимизации.

1. Пример постановки задачи оптимизации.

Для изготовления 3-х видов изделий А, В и С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия приведены в таблице.

Определить, сколько изделий и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной. Составить математическую модель задачи. Решение: Пусть будет изготовлено Х₁ единиц изделия А Х₂ единиц изделия В Х₃ единиц изделия С. Тогда при использовании фрезерного оборудования потребуется затратить 2Х₁ + 4Х₂ + 5Х₃ станко-часов. Но по условию ограничения общего фонда времени 2Х₁ + 4Х₂ + 5Х₃  120. Аналогично для токарного, сварочного и шлифовального оборудования: 1)Х₁ + 8Х₂ + 6Х₃  280 2)7Х₁ + 4Х₂ + 5Х₃  240 3)4Х₁ + 6Х₂ + 7Х₃  360 При этом, т.к. количество изготовляемых деталей не может быть отрицательным, то Х₁  0, Х₂  0, Х₃  0. Далее, если будет изготовлено Х₁ изделий А, Х₂ изделий В и Х₃ изделий С, то прибыль от их реализации составит F = 10Х₁ + 14Х₂ + 12Х₃ Итак, мы получаем систему четырех линейных неравенств с тремя неизвестными (X_j (j = 1…3): 1)2Х₁ + 4Х₂ + 5Х₃  120 2)Х₁ + 8Х₂ + 6Х₃  280 3)7Х₁ + 6Х₂ + 7Х₃  360 Х₁  0, Х₂  0, Х₃  0. И линейную функцию F = 10Х₁ + 14Х₂ + 12Х₃ относительно этих же переменных. Требуется среди всех неотрицательных решений системы неравенств найти такое, при котором целевая функция F принимает максимальное значение. Постановка задачи линейного программирования Найти оптимум (наибольшее или наименьшее значение) целевой функции (линейной формы) на области допустимых значений системы ограничений при наличии дополнительных условий неотрицательности переменных х_j  0, j = 1,…, n. Если в системе ограничений l = m, т.е. она состоит только из уравнений, то соответствующая форма записи называется канонической.

9. Нелинейное программирование. Постановка задачи нелинейного программирования.

В общем виде задача НП состоит в определении max/min значения f (x₁, x₂, … x_n) (1) при условии, что ее переменные удовлетворяют соотношениям g_i(x₁, x₂, …, x_n)  b_i (i = 1, k) (2) g_i(x₁, x₂, …, x_n) = b_i (i = k + 1, m) (2), где f и g_i некоторые известные функции n переменных, а b_i – заданные числа. Имеется в виду, что в результате решения задачи будет определена точка Х* = (х₁*, х₂*, … х_n*), координаты которой удовлетворяют соотношению (2), причем для всякой другой точки, отвечающей условиям (2), выполняется F* (x*₁, x*₂, … x*_n)  f (x₁, x₂, … x_n) Если f и g_i – линейные функции, то это будет задача линейного программирования. Соотношения (2), образующие систему ограничений, включают в себя и условия неотрицательности переменных, если таковые имеются. Последние могут быть заданы и отдельно. В евклидовом пространстве En система ограничений (2) определяет ОДР. В отличие от задачи ЛП она не всегда является выпуклой. Если определена ОДР, то нахождение решения задачи НП сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня: f (x₁, x₂, … x_n) = h, причем эта точка может находиться как на границе ОДР, так и внутри нее.