Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 48 стр.

UptoLike

ВУЗ: 

ПГНИУ | Пермь

Составители: 

Рубрика: 

2. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
48
когда целевая функция достигает на допустимом множестве своего
наименьшего (наибольшего) значения, его называют значением задачи, а
допустимый вектор, на котором это значение достигается, - оптимальным
вектором или решением задачи линейного программирования. Множество всех
допустимых векторов, на которых достигается минимум (максимум) целевой
функции, обозначим символом
(
)
UU
*
*
. В случае, когда целевая функция
неограниченна снизу и задача решается на
min
(сверху и задача решается на
max
), говорят, что решение задачи линейного программирования
неограниченно или, что оно уходит на бесконечность.
В ограничениях задачи 1 первые
m
соотношений являются неравенствами
со знаком «
£
» следующие
km
-
соотношений – неравенствами со знаком «
³
»,
а заключительные
-
соотношений – равенствами. Такое соглашение о
порядке ограничений принято только для удобства записи общей постановки
задачи линейного программирования, и оно необязательно для конкретных
задач. Задача максимизации целевой функции
I
на некотором допустимом
множестве всегда может быть заменена эквивалентной ей задачей минимизации
функции
I
-
на том же множестве. Эквивалентность этих задач следует
понимать в том смысле, что экстремум целевых функций
I
и
I
-
достигается на
одних и тех же элементах множества
U
. Заметим, что экстремальные значения
целевых функций при этом будут совпадать только по абсолютной величине, а
знаки их будут противоположными. Указанная эквивалентность позволяет
иногда ограничиваться изучением задач линейного программирования только
на минимум целевой функции.
2.2. Каноническая и стандартная форма задачи линейного
программирования. Рассмотрим наиболее важные частные случаи общей
задачи линейного программирования.
Определение 1. Задачу линейного программирования будем называть
канонической, если для нее
ln
=
и
0
k
=
. 
2. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


когда      целевая    функция   достигает        на   допустимом    множестве   своего
наименьшего (наибольшего) значения, его называют значением задачи, а
допустимый вектор, на котором это значение достигается, - оптимальным
вектором или решением задачи линейного программирования. Множество всех
допустимых векторов, на которых достигается минимум (максимум) целевой
функции, обозначим символом U * (U * ) . В случае, когда целевая функция

неограниченна снизу и задача решается на min (сверху и задача решается на
max ),     говорят,    что   решение    задачи         линейного    программирования
неограниченно или, что оно уходит на бесконечность.

     В ограничениях задачи 1 первые m соотношений являются неравенствами
со знаком « £ » следующие k - m соотношений – неравенствами со знаком « ³ »,
а заключительные s - k соотношений – равенствами. Такое соглашение о
порядке ограничений принято только для удобства записи общей постановки
задачи линейного программирования, и оно необязательно для конкретных
задач. Задача максимизации целевой функции I на некотором допустимом
множестве всегда может быть заменена эквивалентной ей задачей минимизации
функции -I на том же множестве. Эквивалентность этих задач следует
понимать в том смысле, что экстремум целевых функций I и -I достигается на
одних и тех же элементах множества U . Заметим, что экстремальные значения
целевых функций при этом будут совпадать только по абсолютной величине, а
знаки их будут противоположными. Указанная эквивалентность позволяет
иногда ограничиваться изучением задач линейного программирования только
на минимум целевой функции.

         2.2.   Каноническая    и   стандартная          форма     задачи   линейного
программирования. Рассмотрим наиболее важные частные случаи общей
задачи линейного программирования.

     Определение 1. Задачу линейного программирования будем называть
канонической, если для нее l = n и k = 0 .



                                            48

Страницы