Общая постановка прикладной задачи.

Все факторы, входящие в описание модели можно разделить на две группы: внешние факторы (условия проведения операции), на которые мы не можем влиять а₁,а₂,а₃,…;

Зависимые факторы (элементы решений), которые мы можем выбирать х₁,х₂,х₃,…

Величина критерия эффективности выражается некоторой функцией, называемой целевой функцией. Она зависит от факторов обеих групп и записывается в виде:

z = f (x₁ x₂ … a₁ a₂ …)

Оптимизационная задача формулируется в общем виде.

Найти переменные х₁,х₂,…х_n, удовлетворяющие системе неравенств (уравнений) φ_j (x₁ x₂…x_n) ≤ b_j, где j =1, 2, …m, и обращают в max или min целевую функцию:

z = f (x_1, x_2,…a_1, a_2,…) → max (min).

 

Классификация оптимизационных методов и моделей.

По характеру взаимосвязи между переменными: линейные и нелинейные.

По характеру изменения переменных: непрерывные и дискретные.

По учету факторов времени: статические и динамические.

По наличию информации о переменных: задачи полной определенности (детерминированные) и задачи в условиях неполной определенности.

По числу критериев: простые однокритериальные задачи и многокритериальные задачи.

 

Если критерий эффективности и система ограничений линейны, такая задача является задачей линейного программирования.

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

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

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

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

 

Основные этапы построения оптимизационных моделей.

Основные этапы построения оптимизационных моделей можно представить в виде схемы:

 

 

 

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

 

 

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

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

В качестве примера рассмотрим задачу об использовании ресурсов.

Пример.

Для изготовления 2-х видов продукции Р1 и Р2 используют 4 вида ресурсов S1, S₂, S3,S4. Запасы ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице:

 

X₁, X₂– число единиц продукции.

Прибыль, получаемая от единицы продукции Р1 и Р₂ соответственно равны С₁=2 и С₂=3.

Так как потребление ресурсов S1, S₂, S3,S4 не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

х₁ + 3х₂ ≤ 18

2х₁ + х₂ ≤ 16 (2.1) – система ограничений.

х₂ ≤ 5

3х₁ ≤ 21

 

По смыслу задачи переменные

x1≥0, x2≥0 (2.2)

Суммарная прибыль составит

F = 2x1 + 3x2→max (2.3)

Итак, экономико-математическая модель задачи найти план выпуска продукции, Х (х₁,х₂) удовлетворяющий системе ограничений (2.1) и условию (2.2), при которых функция (2.3) принимает максимальное значение.

Задачу легко обобщить на случай n видов продукции с использованием m видов ресурса.