Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. B) Соединение атома водорода одной молекулы с сильно электроотрицательным элементом другой молекулы
  2. B) Функцияның төрт нөлдері бар. D) Функция кесіндіде үзіліссіз болады.E) Функция сегментте қатан өседі.
  3. C) одновременно выполняются условия а) и б);
  4. C. Движение информации и ее трансформация от исходной в командную
  5. D) Отечественная культура в условиях тоталитарного общества.
  6. D. Условия пребывания и размещение
  7. D1. Задача
  8. E) задачи на вычисление боковой поверхности геометрических фигур
  9. E)задачина вычисление боковой поверхности геометрических фигур 1 страница
  10. E)задачина вычисление боковой поверхности геометрических фигур 2 страница

Из первой части теоремы следует, что равенство (3.25) является не только достаточным признаком оптимальности решений, но и необходимым условием оптимальности решений взаимно двойственных задач.

Рассмотрим примеры, подтверждающие справедливость первой теоремы двойственности.

Пример 3.11. Даны две взаимно двойственные задачи:

1) Ф = 2×x1 + 3×x2 ® max 2) F = 18×y1 + 16×y2 + 5×y3 + 21×y4 ® min

при ограничениях при ограничениях

x1 + 3×x2 £ 18, y1 + 2y2 + 3y4 ³ 2,

2x1 + x2 £ 16, 3×y1 + y2 + y3 ³ 3.

x2 £ 5,

3x1 £ 21.

x1 ³ 0, x2 ³ 0 yi ³ 0, i = 1,4

Решив эти задачи (например, первую графическим, вторую – симплексным методами), можно получить экстремумы целевых функций Фmax = 24, Fmin = 24, что подтверждает справедливость первой части первойтеоремыдвойственности.

Пример 3.12. Даны две взаимно двойственные задачи:

1) Ф = 3×x1 + 5×x2 ® max 2) F = 5×y1 - 7×y2 ® min

при ограничениях при ограничениях

3 ×x1 - 4×x2 £ 5, 3×y1 - 2 ×y2 ³ 3,

-2× x1 ³ -7, - 4×y1 ³ 5

x1 ³ 0, x2 ³ 0 y1 ³ 0, y2 ³ 0

Решив эти задачи (например, графическим методом), можно убедиться, что в исходной задаче (задача 1) целевая функция не ограничена Фmax = + ¥, в

ОДР не Система

ограни- ограничений

чена не совместна

 

 

двойственной задаче (задача 2) условия противоречивы, то есть, система ограничений несовместна, что подтверждает справедливость второй части теоремы.

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

Пример 3.13. Даны две взаимно двойственные задачи:

1) Ф = -8×х1 + 2×х2 ® min 2) F = y1 - y2 ® max

при ограничениях при ограничениях

1 + 2×х2 ³ 1, y1 +2×y2 ³ 8,

-2× х1 + х2 ³ -1, 2×y1 + y2 £ 2.

х1 ³ 0, х2 ³ 0 y1 ³ 0, y2 ³ 0

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

 

       
 
   
 


х2 Системы y2

ограничений

не совместны

 

 

х1 8 y1

 

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

Рассмотрим две взаимно двойственные задачи:

1) исходная задача 2) двойственная задача

Ф = cj ×xj ® max F = bi×yi ® min

при ограничениях при ограничениях

aij× xj £ bi (i = 1,m) (3.26) aji× yi ³ cj (j = 1,n) (3.27)

xj ³ 0 (j = 1,n) yi ³ 0 (i = 1,m)

Чтобы каждую из этих задач решить симплексным методом, необходимо привести их к каноническому виду, для чего в систему ограничений исходной задачи (3.26) следует ввести m неотрицательных переменных x n+1, x n+2,..., x n+i,..., x n+m, а в систему ограничений двойственной задачи (3.27) -n неотрицательных переменных ym+1, ym+2,..., ym+j,..., ym+n, где i(j) - номер неравенства, в которое введена дополнительная переменная x n+i ³ 0 (y m+j ³ 0).

Системы ограничений каждой из задач примут вид: aij× xj + x n+i = bi, (i = 1,m) (3.28)

aji× yi - y m+j = сj, (j = 1,n) (3.29)

Между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи существует следующая взаимосвязь:

 

Переменные исходной задачи 1
Первоначальные Дополнительные
x1, x2,..., xj,..., xn x n+1, x n+2,..., x n+i,..., x n+m
↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕
ym+1, ym+2,..., ym+j,..., ym+n y1, y2,..., yi, ..., ym
Дополнительные Первоначальные
Переменные двойственной задачи 2

 

Эту взаимосвязь можно сформулировать в виде следующей теоремы.

Теорема о взаимосвязях переменных. Положительным (ненулевым) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, то есть, для любых i = 1, m и j = 1, n:

если x*j > 0, то y*m+j = 0; если x*n+i > 0, то y*i = 0,




Дата добавления: 2014-12-20; просмотров: 100 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2025 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав