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

Эквивалентные постановки задач ЛП

Читайте также:
  1. CИТУАЦИОННЫЕ ЗАДАЧИ
  2. CИТУАЦИОННЫЕ ЗАДАЧИ
  3. CИТУАЦИОННЫЕ ЗАДАЧИ
  4. CИТУАЦИОННЫЕ ЗАДАЧИ
  5. CИТУАЦИОННЫЕ ЗАДАЧИ
  6. CИТУАЦИОННЫЕ ЗАДАЧИ
  7. CИТУАЦИОННЫЕ ЗАДАЧИ

 

Общая постановка:


n

 

 

j =1

n


cjxj→ max(min),


j =1 aijxj≤ bi,i ∈ I 1

n
n
j =1 aij xj = bi,i ∈ I 2

 j =1 aijxj≥ bi,i ∈ I 3

j 1
x ≥ 0, j ∈ N,

xj∈ R, j ∈ N 2,

xj≤ 0, j ∈ N 3,

 

где cj, aij, bi – заданные числовые параметры, множества I 1, II 3попарно не пересе- каются, I 1 ∪ I 2 ∪ I 3= { 1 ,..., m}, R – множество действительных чисел, множества N 1, N 2 и N 3 попарно не пересекаются, и N 1 ∪ N 2 ∪ N 3 = { 1 ,..., n}. Cуществует несколько

эквивалентных постановок задач ЛП:

– Задачи максимизации и минимизации. Для перехода от одной задачи к другой коэффи- циенты целевой функции можно умножить на -1.

– Задачи с ограничениями типа ”=”, ” ” и ” ”. Для перехода от ограничения ” ” к ограни-

чению ” ” и наоборот достаточно домножать соответствующее ограничение на -1. Огра-

ничение типа ”=” может быть представлено в виде двух ограничений ” ” и ” ” с той же

левой и правой частью. Для перехода от ограничений типа ”=” к ограничениям типа

можно применить метод Гаусса. Например, рассмотрим задачу

 

−x 1 − x 2 + x 5 min


x 1 + x 2 = 1

 x 2 2 x 3 = 3

x 3 x 4 + x 5 = 1

xj≥ 0

При помощи метода Гаусса выделяем единичную подматрицу в матрице ограничений.

 

                                    -2  
    -2     -3     -2     -3       -2   -1
      -1             -1             -1    

 

Эквивалентная задача


 x 1 = 2 (2 x 4 2 x 5) 0

x 2 = 1 ( 2 x 4 + 2 x 5) 0

 x 3 = 1 (−x 4 + x 5) 0


 

2 + 2 x 4 2 x 5 1 + 2 x 4 2 x 5 + x 5 = 3 + 4 x 4 3 x 5 min


 2 x 4


2 x 5 2


 2 x 4 + 2 x 5 ≤ − 1

 −x 4 + x 5 1

x 4, x 5 0

Для перехода от ограничений типа к ограничениям типа = достаточно ввести дополни- тельные неотрицательные переменные, по одной для каждого ограничения . Эти пере-

менные войдут в целевую функцию с нулевыми коэффициентами.

Переменная xj∈ R может быть представлена в виде двух новых неотрицательных пере-

менных: xj = x + − x−, x + 0, x− ≥ 0.

j j j j

Для каждой задачи ЛП можно сформулировать двойственную ей задачу. Рассмотрим задачу максимизации с ограничениями ” ”. Представим эту задачу в матричной форме:

 

cx → max, Ax ≤ b,

где c = (c 1 ,..., cn) – вектор-строка, x = (x 1 ,..., xn) T – вектор-столбец, A = ||aij|| – матрица размерности m × n, b = (b 1 ,..., bm) T – вектор-столбец. Отметим, что ограничения x ≥ 0 отсутствуют. Они могут быть войти в ограничения Ax ≤ b путем введения эквивалентных ограничений −x ≤ 0. Введем в рассмотрение двойственную ей задачу:

 

yb → min,

yA = c, y ≥ 0,

 

где y = (y 1 ,..., ym) – вектор-строка двойственных переменных или потенциалов. Пусть Ai обозначает строку i матрицы A, а Aj – столбец j этой же матрицы. Соответствие между компонентами прямой и двойственной задач представлено в следую- щей таблице.


 

Прямая задача Двойственная задача
max {cx} Aix≤ bi,i ∈ I 1 Aix = bi,i ∈ I 2 xj≥ 0, j ∈ N 1 xj∈ R, j ∈ N 2 xj ≤ 0, j ∈ N 3 min {yb} yi≥ 0, i ∈ I 1 yi ∈ R, i ∈ I 2 yAj≥ cj, j ∈ N 1 yAj = cj, j ∈ N 2 yAj≤ cj, j ∈ N 3

 

Теорема 1 (Теорема двойственности) Справедливо одно из следующих утверждений:

а) обе задачи, прямая и двойственная ей, имеют допустимые решения и

 

max {cx} = min {yb},

 

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

в) обе задачи не имеют допустимых решений.

 

Теорема 2 (О дополняющей нежесткости) Пусть x и y – допустимые решения прямой и двойственной задач соответственно. Тогда следующие условия а), б) и в) эквивалент- ны:

а) x и y оптимальные решения прямой и двойственной задач, б) cx = yb,

в) (условие дополняющей нежесткости) yi (Aix− bi)= 0 i = 1 ,..., m, и (yAj− cj) xj = 0,

j = 1 ,..., n.

 

Из этой теоремы, например, следует, что если решения прямой и двойственной задач допу- стимы и выполняется условие в) дополняющей нежесткости, то эти решения оптимальны. Оптимальное решение прямой задачи может быть получено из оптимального решения двойственной задачи. Например, рассмотрим задачу

4 x 1 3 x 2 6 x 3 − x 4 max,

2 x 1 − x 2 + 5 x 3 + 2 x 4 2

3 x 1 + x 2 − x 3 − x 4 1

xi≥ 0, i = 1, 2, 3, 4

Построим двойственную ей задачу

2 y 1 + y 2 min,

2 y 1 3 y 2 4

−y 1 + y 2 ≥ − 3

5 y 1 − y 2 ≥ − 6


 2 y 1 − y 2 ≥ − 1

yj ≥ 0, j = 1, 2

Решим двойственную задачу графически: y∗ = ( 9 / 4 ,− 21 / 4), z∗ = 39 / 4. Оптимальное

решение определяется пересечением линий, соответствующих ограничению 2 и 3 двой-

 
ственной задачи. Эти ограничения выполняются как строгие равенства, а остальные - как нестрогие. Тогда по условию дополняющей нежесткости должно выполняться x∗ = 0,

4 = 0, x 2 и x 3 могут быть найдены из равенств −x 2 + 5 x 3 = 2 и x 2 − x 3 = 1 (рассмат-


x∗ ∗ ∗


∗ ∗ ∗ ∗


риваем подматрицу матрицы прямой задачи, состоящую из столбцов 2 и 3). Получаем

x∗ = (0, 7 / 4, 3 / 4, 0).



Дата добавления: 2015-07-08; просмотров: 393 | Нарушение авторских прав


Читайте в этой же книге: Классификация задач | Многокритериальные задачи | Транспортная задача ЛП | Задача о назначениях | Основы теории графов | Кратчайшие пути | Задача коммивояжера и метод ветвей и границ | Монте-Карло | Основы теории сложности вычислений | Динамическое программирование |
<== предыдущая страница | следующая страница ==>
Графический метод решения задач ЛП| Симплекс-метод.

mybiblioteka.su - 2015-2024 год. (0.02 сек.)