68779

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

Конспект

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

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

Русский

2014-09-25

467 KB

8 чел.

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

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

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

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

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


 

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

23139. Программа прикладного исследования 35.5 KB
  Программа прикладного исследования. Общая структура прикладного социологического исследования Социологическое исследование это инструмент изучения социальных явлений в их конкретном состоянии с помощью количественных и качественных методов. Содержание и функции программы Программа это изложение основных задач исследования и предпосылок их решения. Он начинается с целеориентации исследования а.
23140. ОЛЕНА ТЕЛІГА (1907—1942) 46.5 KB
  Олена Іванівна Шовгенева народилася 21 липня 1907р. Олена навчалась у гімназії Дучинської. Олена закінчила історикофілологічний факультет Високого педагогічного інституту ім.
23141. Олена Теліга 22 KB
  Олена Теліга належала до кола поетіввісниківців що об'єднувались довкола редагованого критиком та публіцистом Д. Теліга не встигла видати жодної прижиттєвої збірки.
23142. Олена Теліга (1907 — 1942) 36 KB
  Теліга розвивала кращі традиції української літератури передовсім Лесі Українки що не раз зазначала емігрантська критика. Маланюк Олена Теліга О. Теліга у статті Прапори духа пафос якої спрямовувався проти зловживання плакатністю та сірим позитивізмом що не мають нічого спільного з лірикою.
23143. КОСТЕНКО ЛІНА 32.5 KB
  За роман у віршах Маруся Чурай Ліні Костенко присуджено Державну премію імені Т. Костенко . Своєрідним феноменом є жінкипоетеси: Леся Українка Олена Теліга Ліна Костенко. Ліна Костенко.
23144. Мова. Поняття літературної мови та мовної норми 105.5 KB
  Розмовний стиль. Художній стиль. Науковий стиль. Публіцистичний стиль.
23145. Провідні мотиви лірики І. Драча 25 KB
  Драча І. Драча характеризується перш за все нетрадиційністю поетичної форми та стилю. Драча неповторною і самобутньою. Драча.
23146. Роман «Третя Рота» 35 KB
  Пушкін дуже високо цінував твори такого жанру. Сосюри письменників лікарів учителів вчених розповідають цікаві епізоди що перетворилися в легенди як поет натхненно читав той чи інший твір який так і залишився неопублікованим і невідомим сучасному читачеві. Тепер же ця легенда став реальністю читач одержує твори які десятиліттями лежали в архівах і не були доступними навіть найвужчому колу дослідників. Павло Тичина даруючи авторові Червоної зими видання Вибрані твори 1957 у трьох томах на першій книзі зробив такий напис:...
23147. Український князь бє чолом рiднiй Українi (Євген Маланюк) 28 KB
  До самої смертi вiн прожив у НьюЙорку працюючи в iнженерному бюро. Малоросiйству вiн протиставляє мазепинство : опертя на прикладi гетьмана Iвана Мазепи на власнi сили церкву культуру. Найважливiшим етапом подолання цiєї хвороби Україною вiн вважає набуття державностi незалежностi нашого краю. 1923 року вiн ще повен надiй на революцiйне звiльнення своєї батькiвщини: Несамовитим криком крови Роздерлися твої уста: сурмиш у рупор пурпуровий Вагiтна бурями повстань .