68779

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

Конспект

Информатика, кибернетика и программирование

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

Русский

2014-09-25

467 KB

7 чел.

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

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

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

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

    ;                                                          (1)

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

     ;                     (2)

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

                (3)

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

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

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

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

,                (4)

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

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

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

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

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

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

найти        

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

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

    2.                                                (5)

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

                найти

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

      10. хj 0 для j=1,...,n   

         20.                                                 (6)

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

                найти    

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

        10. хj 0 для j=1,...,n,     

        20,                          (7)     

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

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

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

   

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

          10 ., ,  

20.

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

          

Теорема 1. Каждому решению  системы 20 в задаче (6) соответствует единственное решение  системы 20 задачи (7) и, наоборот, каждому решению  системы  20 задачи (7) соответствует единственное решение системы 20 в задаче (6).

Выпуклые множества

Определение 1. Множество выпукло, если оно вместе с любыми своими двумя точками , содержит соединяющий их отрезок.

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

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

Пусть , – две точки некоторого множества. Возьмем произвольную точку  (рис. 1). Выразим  через , :

;; .

Обозначая , имеем:

и .

               Рис.1.  Произвольные  точки  ,,выпуклого множества

Определение 2. Выражение  называют выпуклой линейной комбинацией, где 1, 2 – угловые (крайние) точки.

Замечание 1. Угловая точка не может быть представлена в виде выпуклой линейной комбинации.

Замечание 2. Для угловых точек  выпуклая линейная комбинация обобщается в виде:

Определение 3. Любой вектор х, удовлетворяющий ограничениям задачи линейного программирования, называется допустимым вектором. Множество всех допустимых векторов образует область допустимых решений.

Определение 4. Допустимый вектор, доставляющий максимальное или минимальное значение целевой функции задачи линейного программирования, называется оптимальным вектором.

Теорема 2. Множество всех допустимых решений задачи ЛП  выпукло.

Надо показать, что если , – допустимые решения задачи ЛП, то и , тоже допустимое решение.

Имеем: ▄

Теорема 3. Целевая функция задачи ЛП достигает своего максимального значения в угловой точке допустимой области. Если целевая функция принимает максимальное значение в более чем одной угловой точке, то она достигает того же значения в любой точке, являющейся линейной комбинацией этих точек.

Замечание. Из теоремы 3 следует, что, если задача ЛП имеет неединственное решение, т.е. решения , то , где также является решением.

Линейная зависимость векторов. Базис и базисные решения

 

Определение 5. Вектор -мерного векторного пространства называется пропорциональным вектору , если существует такое число , при котором выполняется соотношение .

Нулевой вектор пропорционален любому вектору , .

Определение 6. Вектор  называется линейной комбинацией векторов , если существуют числа , при которых выполняется соотношение:

.        (10)

Определение 7. Система векторов , r≥2, называется линейно зависимой, если хотя бы один из векторов системы является линейной комбинацией остальных, и линейно независимой – в противном случае. Или: система векторов , r≥2, является линейно зависимой, если существуют такие числа , не все равные нулю, при которых имеет место равенство: . Если такое соотношение возможно лишь в случае, когда все , то система векторов называется линейно независимой.

Пример 2. Показать, что следующие векторы линейно зависимы:

.

Составим линейную комбинацию вида (10):

или

Пример 3. Векторы - линейно независимы, поскольку

Определение 8. Максимальное число линейно независимых векторов в -мерном векторном пространстве равно .

Определение 9. Любая совокупность  линейно независимых векторов -мерного пространства образует базис -мерного пространства.

Определение 10. Какова бы ни была прямоугольная матрица :

,

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

Пусть матрица  в задаче линейного программирования имеет ранг . Тогда в матрице  имеется  линейно независимых столбцов и  система линейных уравнений 20 в (7) совместна. Любой набор из  линейно независимых столбцов будет базисом, как и матрица, составленная из этих столбцов.

Теорема 4. Любой вектор - мерного векторного пространства можно представить как линейную комбинацию векторов базиса, притом единственным образом.

Замечание. Система единичных векторов  -мерного векторного пространства линейно независима.

Имеем: . Вектор  тогда, когда все  Исходя из определения 7, это показывает линейную независимость единичных векторов.

С другой стороны, любой вектор  представляет собой линейную комбинацию единичных векторов:

.

Теорема 5. Если известно, что система векторов-столбцов линейно независима и такова, что , где все , то точка  является угловой точкой выпуклого множества решений задачи линейного программирования (4).

Теорема 6. Если - угловая точка области допустимых значений решений задачи линейного программирования (4), то векторы, соответствующие положительным компонентам , образуют линейно независимую систему. Угловая точка имеет не более чем положительных компонент (количество уравнений в (4)) .

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

Исходные данные задачи:

1

1

4

7

1

0

0

1

–5

–9

1

–3

–5

–1

Столбцы матрицы ограничений имеют вид:

 

Столбцы  и   - базисные столбцы, переменные - базисные.

Тогда ограничения 2) запишутся в векторной форме виде:

        или в матричной форме:

или

Поскольку количество ограничений =2, то число линейно независимых столбцов не может быть больше 2.

Замечания. 

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

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

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

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

Графический метод решения задач ЛП

При нахождении решения задачи ЛП графическим методом могут встретиться следующие случаи:

          Целевая функция m принимает              Целевая функция m принимает max в любой                

      max в единственной  точке А                           точке отрезка АВ

                                                                                                                              

Графический метод решения задач ЛП

При нахождении решения задачи ЛП графическим методом могут встретиться следующие случаи:

Целевая функция не ограничена сверху             Система ограничений задачи несовместна 

на множестве    допустимых решений                (некорректная постановка задачи). Нет ОДР

Метод последовательного улучшения допустимого вектора (симплекс-метод) для решения задачи линейного программирования

Симплекс – это простейший выпуклый многогранник данного числа измерений . При =1 симплекс представляет отрезок, при  =2 - произвольный треугольник, при =3 – произвольный трехмерный тетраэдр. Нульмерный симплекс -  одна точка.

Таким образом, -мерный симплекс имеет  (+1) вершин.

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

найти        

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

       

      10. хj 0 для j=1,...,n   

    20.                             (14)


 

А также другие работы, которые могут Вас заинтересовать

11972. КРЕДИТУВАННЯ НАСЕЛЕННЯ В КОМЕРЦІЙНОМУ БАНКУ АВАЛЬ 949.47 KB
  МАГІСТЕРСЬКА ДИПЛОМНА РОБОТА на тему : КРЕДИТУВАННЯ НАСЕЛЕННЯ В КОМЕРЦІЙНОМУ БАНКУ АВАЛЬ РЕФЕРАТ Магістерська дипломна робота на тему: €œКредитування населення в комерційному банку АППБ €œАваль€ € складається із вступу 3 розділів та висновків. Робота викл...
11973. ФІНАНСОВИЙ МЕНЕДЖМЕНТ У КОМЕРЦІЙНИХ БАНКАХ (НА ПРИКЛАДІ АКБ ПРАВЕКСБАНК) 558.88 KB
  ДИПЛОМНА РОБОТА СПЕЦІАЛІСТА ФІНАНСОВИЙ МЕНЕДЖМЕНТ У КОМЕРЦІЙНИХ БАНКАХ НА ПРИКЛАДІ АКБ ПРАВЕКСБАНК ЗМІСТ ВСТУП РОЗДІЛ 1. ОСНОВИ ДІЯЛЬНОСТІ КОМЕРЦІЙНОГО БАНКУ ТА УПРАВЛІННЯ БАНКІВСЬКИМИ ОПЕРАЦІЯМИ 1.1 Сучасна банківська система України та її структур
11974. НА ТЕМУ:УДОСКОНАЛЕННЯ СИСТЕМИ НАГЛЯДУ НБУ ЗА КОМЕРЦІЙНИМИ БАНКАМИ 1018.51 KB
  ДИПЛОМНИЙ ПРОЕКТ на тему: УДОСКОНАЛЕННЯ СИСТЕМИ НАГЛЯДУ НБУ ЗА КОМЕРЦІЙНИМИ БАНКАМИ АНОТАЦІЯ Дипломної роботи магістра на тему: €œУДОСКОНАЛЕННЯ СИСТЕМИ НАГЛЯДУ НБУ ЗА КОМЕРЦІЙНИМИ БАНКАМИ€ Науковий керівник Актуальність теми дипломної роботи полягає в оці
11975. Развитие операций коммерческих банков с производными ценными бумагами на фондовом и финансовом рынках Украины 1.03 MB
  Исследование сущности и области применения класса производных ценных бумаг на фондовом и финансовом(валютном) рынках, особенности функционирования производных ценных бумаг в коммерческих банках Украины, эффективность и перспективность расширения операций с производными ценными бумагами в коммерческих банках.
11976. Облік та аудит кредитних операцій банку (на прикладі кредитних операцій з фізичними особами в ЗАТ КБ «Приватбанк») 492.32 KB
  ЗВІТ про переддипломну практику в комерційному банку ЗАТ КБ Приватбанк згідно дипломного проекту на тему: Облік та аудит кредитних операцій банку на прикладі кредитних операцій з фізичними особами в ЗАТ КБ Приватбанк Вступ Об’єкт пере
11977. Споживче кредитування населення (на матеріалах ТОВ Банк Ренесанс Капітал, м.Київ) 680.1 KB
  ЗВІТ за результатами переддипломної практики на тему Споживче кредитування населення на матеріалах ТОВ Банк Ренесанс Капітал м.Київ ЗМІСТ Вступ 1. Характеристика діяльності комерційного банку ТОВ Банк Ренесанс Капітал 2. Аналіз кредитної діяльності ТОВ
11978. Изучение практики выдачи и погашения кредитов физических лиц, а также проанализировать современное состояние организации кредитования физических лиц в ОАО «Белгазпромбанк» 586.18 KB
  ВВЕДЕНИЕ Цель данной дипломной работы ─ изучить практику выдачи и погашения кредитов физических лиц а также проанализировать современное состояние организации кредитования физических лиц в ОАО Белгазпромбанк и на основе этого анализа выработать предложения по
11980. РОЗРАХУНКОВІ ОПЕРАЦІЇ БАНКУ (НА МАТЕРІАЛАХ КОМЕРЦІЙНОГО БАНКУ ВАТ АКБ «УКРСОЦБАНК») 1.1 MB
  ЗВІТ за результатами переддипломної практики на тему № 2.1 РОЗРАХУНКОВІ ОПЕРАЦІЇ БАНКУ НА МАТЕРІАЛАХ КОМЕРЦІЙНОГО БАНКУ ВАТ АКБ УКРСОЦБАНК Зміст Вступ 1. Характеристика основних видів діяльності комерційного банку ВАТ АКБ Ук...