Студопедия

Главная страница Случайная лекция


Мы поможем в написании ваших работ!

Порталы:

БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика



Мы поможем в написании ваших работ!




Двойственная задача ЛП

Читайте также:
  1. В каких случаях задача определения напряжений считается плоской?
  2. Введение. Доктрина информационной безопасности России о системах, функциях и задачах государства
  3. Глава II. Транспортная задача
  4. Задача 1
  5. Задача 1
  6. Задача 1
  7. Задача 1.
  8. Задача 2
  9. Задача 2

Рассмотрим две следующие задачи:

Задача 1

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

( );

( ).

Задача 2

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

( );

( ).

Эти задачи образуют так называемую двойственную парузадач ЛП. Первая задача называется исходной, а вторая – двойственной.

В этих задачах используются одни и те же константы, однако исходная задача является задачей максимизации, а двойственная – задачей минимизации. Число переменных двойственной задачи равно числу ограничений исходной и наоборот; знаки неравенств в ограничениях являются обратными; коэффициенты целевой функции одной задачи являются свободными членами ограничений другой.

Пример записи двойственной задачи:

Исходная задача

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

Двойственная задача

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

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

1) Любое допустимое решение исходной задачиопределяет оценку снизудля оптимального значения целевой функции двойственной задачи;

2) Любое допустимое решение двойственной задачидает оценку сверхудля целевой функции исходной задачи;

3) Для оптимальных решений прямой и двойственной задач значения целевых функций совпадают.

Если и - допустимые решения прямой и двойственной задач соответственно, то первые два свойства означают, что всегда выполняется неравенство

Для оптимальных решений и справедливо выражение

Чтобы доказать эти положения: 1) умножимкаждое i – е ограничение прямой задачи на , наоборот, каждое j – е ограничение двойственной задачи на .

Так как ( ) и ( ), то знаки не изменяются:

( );

( );

Суммируем все соотношения в каждой группе:

или .

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

При этом, как следует из постановки прямой задачи справедливо неравенство

Отсюда получаем, что .

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

Одновременно имеем, что . Отсюда также получаем, что .

 


<== предыдущая страница | следующая страница ==>
Метод искусственного базиса | Табличная форма двойственной пары задач ЛП

Дата добавления: 2014-08-04; просмотров: 448; Нарушение авторских прав




Мы поможем в написании ваших работ!
lektsiopedia.org - Лекциопедия - 2013 год. | Страница сгенерирована за: 0.003 сек.