68779

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

Конспект

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

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

Русский

2014-09-25

467 KB

14 чел.

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

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

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

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

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


 

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

67288. Формы государственно-территориального устройства 17.2 KB
  Тенденция: расширение предмета регулирования. Субсидиарность – принцип территориальной организация власти, при которой обеспечивается оптимальное разграничение полномочий между территориальными единицами и достигается эффективность управления и учет интересов населения.
67289. ИНСТРУМЕНТАЛЬНЫЕ СТАЛИ 54 KB
  Инструментальные стали делятся на четыре категории: 1 пониженной прокаливаемости преимущественно углеродистые; 2 повышенной прокаливаемости легированные; 3 штамповые; 4 быстрорежущие. Углеродистые и легированные стали применяются для режущего инструмента при легких условиях работы и для измерительного инструмента.
67290. Приближенные способы преобразования 279 KB
  Универсальный способ получения случайных чисел базируется на кусочной аппроксимации функции плотности. Для вычисления k воспользуемся следующим соотношением: Алгоритм машинной реализации этого способа получения случайных чисел сводится к выполнению следующих действий...
67291. КУЛЬТУРА 19 ВЕКА: ПОЗИТИВИЗМ 70 KB
  Вместе с изменением представлений о строении материи пространстве времени движении путях развития флоры и фауны месте человека в природе о происхождении жизни на Земле изменяется и отношение человека к природе и обществу. В отличие от героя-романтика герой-реалист активно участвует в жизни пытаясь изменить её в лучшую сторону.
67292. Выбор характеристик качества в проектах программных средств 93 KB
  Описание в стандарте ISO 9126:14 характеристик качества программных средств не содержит рекомендаций и методик выбора их значений в требованиях к конкретным проектам. Далее должны быть разработаны процессы выбора установления...
67293. РАНЫ 123.5 KB
  Раной называется любое механическое повреждение при котором нарушается целостность покровов тела кожи или слизистых с возможным нарушением глубжележащих тканей и органов. Классификация ран По механизму повреждения...
67294. Международное сотрудничество области безопасности жизнедеятельности 19.49 KB
  Международное сотрудничество по охране труда осуществляется в рамках Международной организации труда МОТ Всемирной организации здравоохранения ВОЗ Федерации специалистов по охране труда и промышленной гигиене ИФАС а также международной организации по безопасности и охране труда...
67295. Монотеистические религии 34.5 KB
  Согласно Библейским преданиям основы религиозного и нравственного учения Христа наиболее полно изложены в Нагорной проповеди которая начинается девятью Заповедями Блаженства. Блаженны нищие духом ибо их есть царство небесное. Блаженны плачущие ибо они утешатся. Блаженны кроткие ибо они наследуют землю.
67296. НОРМЫ ПРАВА 132 KB
  Право состоит из действующих в данном обществе юридических или правовых норм. Однако из этого положения не следует что понятия права и нормы права совпадают. Поскольку нормы права одна из разновидностей социальных норм на них распространяются общие черты присущие этим нормам.