Постановки задач однокритериальной оптимизации

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

Среди задач условной однокритериальной оптимизации наиболее изучены следующие линейные задачи:

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

; (1)

задача целочисленного линейного программирования

; (2)

задача частично-целочисленного линейного программирования

(3)

задача булевого линейного программирования

, где векторы , матрицы - заданы, а - -мерные векторы переменных.

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

Будем далее рассматривать задачи линейного программирования. Любую задачу линейного программирования (1) можно привести к виду:

, (4)

где --мерный вектор.

Задача (4) называется задачей линейного программирования в канонической форме.

Для получения такой формы в ограничения ≤задачи (1) вводятся дополнительные переменные со знаком «+».

Если в ограничениях задачи (1) стоит знак «», то дополнительные переменные вводятся со знаком «-».

Если необходимо решить задачу на минимум, то делаются следующие простые преобразования:

Задача (1) в координатной форме запишется следующим образом:

найти

на множестве векторов х= (х₁,х₂, …х_n), удовлетворяющих условиям:

1. х_j ³0 для j= 1, ...,n

2. (5)

Используя знак суммирования, задача (5) запишется в следующем виде:

найти

на множестве векторов х= (х₁,х₂, …х_n), удовлетворяющих условиям:

1⁰. х_j ³0 для j= 1, ...,n

2⁰. (6)

Приведя ограничения 2⁰ в задаче (6) к равенствам, получим задачу в канонической форме:

найти

на множестве векторов х= (х₁,х₂, …х_n), удовлетворяющих условиям:

1⁰. х_j ³0 для j= 1, ..., n,

2⁰ , (7)

где - это дополнительная переменная, .

Пример 1. Привести к канонической форме следующую задачу линейного программирования:

найти максимум функции

на множестве векторов х = (х₁, х₂,х₃), удовлетворяющих условиям:

1⁰. , ,

2⁰.

Для приведения ограничений 2⁰ к каноническому виду, введем дополнительные неотрицательные переменные :

Дата добавления: 2014-01-04