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)


 

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

54128. МОДЕЛЮВАННЯ СУЧАСНОГО ЕФЕКТИВНОГО УРОКУ УКРАЇНСЬКОЇ ЛІТЕРАТУРИ 190.5 KB
  У застосуванні методів навчання треба бути обережним інакше ефективний урок може перетворитися на ефектний. Павленко Питання моделювання ефективного уроку є надзвичайно актуальним для сучасних педагогів що працюють в умовах особистісно орієнтованого підходу запроваджують інноваційні технології.Опрацювати методи і прийоми що...
54129. Хто працює, той і має. Майстер-клас 351.5 KB
  Українська мова Корінь слова. Спільнокореневі слова. формувати в учнів уявлення про спільнокореневі слова корінь на основі споріднених слів; розвивати вміння виділяти споріднені слова виділяти спільну частину; збагачувати словниковий запас учнів; розвивати вміння спостерігати аналізувати зіставляти; виховувати акуратність уважність у роботі. Які виросли паростки діти називають Що спільного з словом лісце корінь тому вони і називаються спільнокореневі слова.
54130. СЦЕНАРИЙ РАЙОННОГО СЕМИНАРА ФИЗИКОВ 89.5 KB
  Смещение акцентов с содержания обучения на процесс учения выражающийся в активной познавательной деятельности школьников и в овладении ими рациональными способами этой деятельности; Создание для каждого ученика возможности реализовать свою потребность в познании и в творческой деятельности; Ориентация на овладение учащимися общекультурными ценностями коммуникативной информационной культурой культурой деятельности. Деятельностный подход к обучению предполагает что...
54131. Общая характеристика низкого (витального) уровня культуры 36.5 KB
  Деление культуры по уровням, каким бы условным оно ни было, - целесообразно. Уровень культуры - это показатель ее реального состояния, предельных возможностей ее осуществления в жизни.
54132. Застосування диференціального, інтегрального обчислень та інших елементів математики в фізиці та техніці 303 KB
  Розвивати уміння узагальнювати цілісну систему знань уміння реалізувати практичні звязки курсу математики і фізики з майбутньою професією уміння через організацію ділової рольової гри відображувати виробничу ситуацію. Розвязання Потужність Р в зовнішньому колі дорівнює різниці повної потужності джерела і P1=EI потужності що губиться всередині джерела Р2=I2rтобто P=P1P2 ; P=EII2r 1 напруга зовнішнього кола як функція сили струму. Доки Мальцев Павло розвязував задачу на дошці клас бере участь в її обговоренні. Йде засідання...
54133. Степенева функція, її графік та властивості. (Урок з використанням інформаційних технологій) 96.5 KB
  Завдання: Дослідити властивості степеневої функції y=x для різних значень параметра. Підготовка до роботи: повторення схеми дослідження функції. Домашнє завдання: закінчити заповнення таблиці: у двох останніх рядках узагальнити властивості функції для додатного та відємного значень показника степеня. Дослідити властивості степеневої функції у = х коли ― ціле додатне парне: 1 встановити масштаб min X = ― 5 mx X = 5 min Y = ― 5 mx Y = 5; 2 побудувати графіки функцій: 1 у = х2 2 у = х4 3 у = х8...
54134. МАТЕМАТИЧНІ ЗМАГАННЯ! 304.5 KB
  Мета: Перевірити вміння учнів застосовувати набуті знання у нестандартних ситуаціях; продовжувати розвивати уміння працювати самостійно, активізувати розумову діяльність учнів; розвивати бажання застосовувати здобуті знання для досягнення поставленої мети; прищеплювати любов до математики.
54135. ВІДНІМАННЯ ТРИЦИФРОВИХ ЧИСЕЛ У ВИПАДКУ КОЛИ В ЗАПИСУ ЗМЕНШУВАНОГО Є НУЛЬ 88 KB
  Уявіть що ми з вами на мить стали чарівниками у кожного з вас у долонях чарівна посмішка подаруйте її своєму товаришу по парті Прошепотіть один одному на вушко комплімент і почнемо працювати з гарним настроєм Актуалізація опорних знань учнів Цей урок нас навчить: зрозуміти особливість письмового віднімання з переходом через розряд; творчо розвязати задачу; виконувати логічні завдання. Розвязування прикладів № 691 частину коментовано частину самостійно. За...
54136. Решение логических, занимательных задач 43 KB
  Совершенствовать вычислительные навыки учащихся; способствовать развитию внимания, мышления, памяти, смекалки, познавательной и творческой активности учащихся; воспитывать трудолюбие, ответственность, интерес к изучению математики.