Студопедия
Случайная страница | ТОМ-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=1aijxj≤ bi,i ∈ I1

n
n
j=1aij xj = bi,i ∈ I2

 j=1aijxj≥ bi,i ∈ I3

j 1
x ≥ 0, j ∈ N ,

xj∈ R, j ∈ N2,

xj≤ 0, j ∈ N3,

 

где cj, aij, bi– заданные числовые параметры, множества I1, II3попарно не пересе- каются, I1∪ I2∪ I3= {1, . . . , m}, R – множество действительных чисел, множества N1, N2 и N3 попарно не пересекаются, и N1 ∪ N2 ∪ N3 = {1, . . . , n}. Cуществует несколько

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

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

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

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

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

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

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

 

−x1 − x2 + x5 min


x1 + x2 = 1

 x2 2x3 = 3

x3 x4 + x5 = 1

xj≥ 0

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

 

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

 

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


 x1 = 2 (2x4 2x5) 0

x2 = 1 (2x4 + 2x5) 0

 x3 = 1 (−x4 + x5) 0


 

2 + 2x4 2x5 1 + 2x4 2x5 + x5 = 3 + 4x4 3x5 min


 2x4


2x5 2


 2x4 + 2x5 ≤ −1

 −x4 + x5 1

x4, x5 0

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

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

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

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

j j j j

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

 

cx → max, Ax ≤ b,

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

 

yb → min,

yA = c, y ≥ 0,

 

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




 

Прямая задача Двойственная задача
max{cx} Aix≤ bi,i ∈ I1 Aix= bi,i ∈ I2 xj≥ 0, j ∈ N1 xj∈ R, j ∈ N2 xj ≤ 0, j ∈ N3 min{yb} yi≥ 0, i ∈ I1 yi ∈ R, i ∈ I2 yAj≥ cj , j ∈ N1 yAj= cj , j ∈ N2 yAj≤ cj, j ∈ N3

 

Теорема 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.

 

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

4x1 3x2 6x3 − x4 max,

2x1 − x2 + 5x3 + 2x4 2

3x1 + x2 − x3 − x4 1

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

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

2y1 + y2 min,

2y1 3y2 4

−y1 + y2 ≥ −3

5y1 − y2 ≥ −6


 2y1 − y2 ≥ −1

yj ≥ 0, j = 1, 2

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

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

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

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


x∗ ∗ ∗


∗ ∗ ∗ ∗


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

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



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


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

mybiblioteka.su - 2015-2018 год. (0.011 сек.)