68779

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

Конспект

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

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

Русский

2014-09-25

467 KB

9 чел.

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

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

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

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

    ;                                                          (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)


 

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

35631. Творческий проект «Наряд спящей красавицы» 422.94 KB
  Последовательность изготовления ночной сорочки. Конструкция сорочки должна соответствовать выбранной модели. Ситец сатин Лён Хлопок Шёлк Ткань для ночной сорочки Мы с мамой купили ткань под название ситец Б. Раскрой ночной сорочки.
35632. Радиальный центробежный вентилятор. Творческий проект 366.86 KB
  Опыт работы показывает значительное повышение интереса учащихся к предмету если учитель привлекает на уроках при изучении различных тем наглядные пособия. Если использовать в технологическом образовании наглядные пособия которые 1 – отвечают основным характеристикам предъявляемым к таким пособиям; 2 – имеют свою сущность применения; 3 – имеют свою технологию изготовления; 4 – и для которых разработана методика применения то изучаемый материал будет усваиваться учащимися на более высоком уровне.Задачи: 1 изучить основные характеристики...
35636. Вышивка крестом. Творческий проект 64.52 KB
  Ведь если бы я умела вышивать то я смогла бы дарить красивые вышивки своим друзьям и близким. Такой рисунок вышивки как раз мне по душе. Виды швов отличаются разнообразием: для глухой вышивки по целой ткани характерны крест гладь набор роспись тамбур и др.; для строчной вышивки по ткани с предварительно вырезанными или выдернутыми на отдельных её участках нитями – мерёжка перевить настил гипюр и др.
35637. Творческий проект «Движение» 45.77 KB
  Получение базовых навыков в методике создания проектовбОсновные задачи проекта:1. Механизм и методы реализации АРеализуемый проект будет работать по следующим принципам: Использование нестандартных способов работыпроведение тематических вечеров собраний и прочего Проведение бесед тренингов дебатов для рационального использования гражданских инициатив Метод деления группы на структурные подразделения под названиямиаЕдинство для учащихся 911 кл. Методы творческой стимуляции группы: Мозговой штурм Корзина идей Метод...
35638. ФРУКТОША (Дерево из бисера.) Творческий проект 896.38 KB
  Фруктовое дерево потому что изделия из бисера во все века притягивали к себе восхищенные взоры. Чтобы изготавливать изделия из бисера не требуется специальная подготовка а достаточно лишь фантазии.Немного из истории бисера С доисторических времен и до наших дней бусины вырезанные из камня или из костей и зубов животных вызывали огромный интерес.