Линейное программирование. Общие задачи оптимизации.

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

f (x) max (min), где x X

Определенная таким образом задача называется задачей оптимизации, где

Х – допустимое множество данной задачи

f(x) – целевая функция

в подавляющем большинстве случаев точке х задается несколькими числами

х (х₁, х₂, …, х_n), т.е. является точкой n-мерного арифметического пространства (Rⁿ), соответственно Х – это подмножество в Rⁿ, очень много зависит от того как задается множество Х.

в большинстве случаев Х выделяется из Rⁿ с помощью системы неравенств.

(2)

q₁, q₂ , …, q_m – заданные функции в R_n

Х – множество точек х₁, х₂, …, х_n, которые принадлежат R_n и удовлетворяют системе неравенств (2).

В этом случае задача оптимизации приобретает следующий вид: дана функция из n переменных f(x) и система неравенств (2). Требуется найти максимум или минимум f(x) при условиях (2). Надо найти не только само значение максимума или минимума функции, но и точку или точки, если их несколько, в которых это значение достигается, такие точки называются оптимальными решениями. Множество всех оптимальных решений называется оптимальным множеством и обозначается Х^*.

Данные задачи являются задачами математического программирования. При этом f(x) – целевая функция, а неравенства из системы (2) – ограничения. В большинстве случаев в эти ограничения входят условия неотрицательности самих переменных (тривиальные ограничения). В зависимости от вида функции f(x), а также функций q₁, q₂ , …, q_m различают разные виды математического программирования.

Когда функции линейные говорят о задаче линейного программирования.

Задачи линейного программирования

№1 Задача о банке.

Собственные средства банка в сумме с депозитами составляет 100 млн. $, часть этих средств, но не менее 35 млн.$ должна быть размещена в кредитах.

Кредиты – не ликвидные активы банка, поэтому существует правило, согласно которому банки должны покупать в определенной пропорции ликвидные активы (ценные бумаги), чтобы компенсировать не ликвидность кредитов.

Ликвидное ограничение: ценные бумаги должны составлять не менее 30 % средств размещенных в кредитах и ценных бумагах в сумме.

c₁ – доходность кредита

c₂ – доходность ценных бумаг

Цель банка: максимизация прибыли.

х₁ – средства, размещенные в кредитах

х₂ – средства, размещенные в ценных бумагах

f(x) = c₁x₁ + c₂x₂ max

№2 Задача о диете

Из имеющихся продуктов требуется составить диету, которая с одной стороны удовлетворяла бы минимальные потребности организма в питательных веществах, а с другой стороны требовала наименьших затрат

х₁ – оптимальное количество продукта 1 (кг)

х₂ – оптимальное количество продукта 2 (кг)

f(x) = s₁x₁ + s₂x₂ min

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

№3 Задача об использовании ресурсов

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

х₁ – оптимальное количество товара 1 (кг)

х₂ – оптимальное количество товара 2 (кг)

f(x) = c₁x₁ + c₂x₂ max

№4 Транспортная задача

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

х_1-6 – оптимальное количество перевозимого угля

Транспортная задача является открытой, если a₁ + a₂ b₁ + b₂ + b₃.

Транспортная задача закрытого типа a₁ + a₂ = b₁ + b₂ + b₃.

f(x) = c_11*x₁ + c_12*x₂ + c_13*x₃ + c_{21 *}x₄ + c_22*x₅ + c_23*x₆ min