Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Двойственность в линейном программировании

Электронная библиотека

Двойственная задача – это вспомогательная задача ЛП, формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой задачи.

Прямая задача в исходной форме:

Чтобы сформулировать условия двойственности задачи, составим следующую схему (рис. 7.1).

Из приведенной схемы видно, что двойственная задача получается путем симметричного структурного преобразования условий прямой задачи в соответствии с правилами:

1) каждому ограничению прямой задачи соответствует переменная двойственной задачи;

2) каждой переменной прямой задачи соответствует ограничение двойственной задачи;

1) коэффициенты при переменной ( -й), фигурирующие в ограничениях прямой задачи, становятся коэффициентами левой части соответствующего ограничения двойственной задачи;

2) коэффициент при переменной в целевой функции прямой задачи, становится постоянной правой части соответствующего ограничения двойственной задачи;

3) постоянная правой части некоторого ограничения прямой задачи, становится соответствующим коэффициентом при переменной в целевой функции двойственной задачи;

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

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

Стандартная форма прямой задачи:

Из указанных правил следует: двойственная задача имеет переменных ( , , , ) и ограничений (соответствующих переменным прямой задачи , , , ).

Доказано, что для каждой пары двойственных задач справедливы свойства:

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

2) На любой итерации процесса решения прямой задачи:

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

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

4) для каждой пары сопряженных условий в оптимальном решении выполняются следующие соотношения: если одно из них выполняется как простое равенство, то другое – как строгое неравенство и наоборот, т.е.

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

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

2. Если ресурс в оптимальном плане израсходован полностью, то его оценка положительна (см. формулу (7.2)), если же ресурс не полностью израсходован в оптимальном плане, то его оценка равна нулю (см.

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

Проиллюстрируем рассмотренные положения на следующем примере.

Пусть в производстве 4-х видов продукции используется 4 вида ресурсов. Известны нормы расхода ресурсов на производство единицы продукции, цены ее реализации

и запасы ресурсов. Определить план производства продукции, максимизирующий выручку от реализации произведенной продукции.

Пусть – матрица коэффициентов расхода ресурсов на производство единицы каждого вида продукции, – матрица-столбец объемов ресурсов, – матрица-строка цен реализации единицы продукции, причем для рассматриваемой задачи они следующие:

Решение. Модель задачи примет вид:

Найти , , и (объемы производства каждого вида продукции), удовлетворяющие ограничениям:

при которых функция достигает максимума.

Для решения задачи симплексным методом приведем ее к стандартному виду:

Значения балансовых переменных показывают объемы неизрасходованных ресурсов в соответствующем плане. Последняя симплексная таблица при решении этой задачи имеет вид табл. 7.1.

Итак, для получения максимального дохода от реализации произведенной продукции необходимо выпустить ее в объемах:

При этом . – это остаток неизрасходованного второго ресурса.

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

Найти значения переменных , удовлетворяющих ограничениям

,

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

; ; ; . .

При этом оптимальные значения целевых функций получились одинаковыми (см. формулу (7.1)).

Проиллюстрируем свойства двойственных оценок на основе этой задачи.

1. Каждая из оценок указывает, на сколько изменится максимальное значение целевой функции (максимальная выручка), если изменить на единицу запасы соответствующих ресурсов. Как видим, наибольшее изменение выручки произойдет, если изменить объем первого ресурса , а изменение второго ресурса не приведет к изменению целевой функции. По крайней мере, его увеличение не приведет к увеличению выручки, так как (как мы видим) этот ресурс остался в излишке в оптимальном решении, но если мы его изменим до величины, меньшей 61 , то выручка уменьшится. Проверьте самостоятельно, что, подставив оптимальное решение во второе ограничение исходной задачи, получим, что для выполнения этого плана второго ресурса понадобится как раз 61 ед., а 1-й, 3-й и 4-й ресурсы израсходованы полностью.

2. Наиболее дефицитным является 1-й ресурс, так как его оценка наибольшая, недефицитным – 2-й (его оценка равна нулю), в 3-й и 4-й ресурсы по дефицитности равнозначны (их оценки равны).

3. Рентабельными являются 2-я, 3-я и 4-я продукции (эти виды продукции выпускаются), а нерентабельной – 1-я . Подставив в первое ограничение двойствен-

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

,

что на 0,6 больше цены единицы этой продукции, равной 4 (обратите внимание, что число 0,6 находится в оценочной строке столбца «x1» в таблице 7.1).

Теоремы двойственности в линейном программировании;

Понятие о двойственных задачах

ПРОГРАММИРОВАНИЯ

ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО

Контрольные вопросы к разделу 2

1. Чем каноническая форма задачи отличается от исходной модели линейного программирования?

2. В каких случаях для решения задачи симплекс-методом в ограничения вводятся дополнительные переменные? дополнительные и искусственные переменные?

3. При выполнении каких условий итерационный процесс нахождения оптимального плана симплекс-методом завершается?

4. Каков экономический смысл дополнительных переменных в ресурсных ограничениях задачи линейного программирования?

5.С какими коэффициентами вводятся в целевую функцию искусственные переменных в задачах минимизации? максимизации?

Читать еще:  Mom exe ошибка инициализации платформы

6 Как по последней симплекс-таблице определить максимально возможное увеличение дефицитного ресурса при котором ассортимент выпускаемой предприятием продукции не изменится?

7 Как по оптимальному плану, полученному в результате решения задачи симплекс-методом, определить какие ресурсы и в каком количестве остались недоиспользованными?

8 Как по оптимальному плану, полученному в результате решения задачи симплекс-методом, определить виды нерентабельной продукции?

9. Что является признаком завершения первого этапа решения задачи симплекс-методом с искусственными переменными?

10. Что является признаком завершения второго этапа решения задачи симплекс-методом с искусственными переменными?

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

В качестве исходной задачи возьмем задачу производственного планирования. Формулировка ее такова. В распоряжении предприятия имеются видов ресурсов соответственно в количествах, равных b1, b2, … , bm. Эти ресурсы должны быть использованы для производства n видов продукции, стоимость единицы которой известна и равна cj (j=1,2, … , n). Кроме того, известны нормы aij потребления каждого из ресурсов на производство единицы всех видов продукции. План производства следует составить из условия максимизации общей стоимости продукции

(3.1)

при ограничениях на использование ресурсов

(3.2)

. (3.3)

По исходным данным задачи (3.1)-(3.3) сформулируем другую экономическую задачу. Для этого предположим, что нужно решить вопрос о том,

что выгоднее: продать имеющиеся на предприятии ресурсы или произвести из них продукцию согласно оптимальному плану задачи (3.1)-(3.3)? В связи с этим возникает необходимость вычислить оптимальные цены у1, у2, …, уm на эти ресурсы, исходя из следующих соображений:

1) покупатель ресурсов стремится минимизировать их общую стоимость;

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

Приведенная формулировка позволяет получить следующую математическую модель. Минимизировать общую стоимость всех ресурсов

(3.4)

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

(3.5)

. (3.6)

Задача (3.4)-(3.6) является двойственной по отношению к задаче (3.1)-(3.3) и, наоборот, если исходной является задача (3.4)-(3.6), то двойственной к ней будет модель (3.1)-(3.3). Такие задачи называются симметричными.

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

1) коэффициенты cj (j=1,2, … , n) целевой функции (3.1) прямой задачи служат свободными членами основных ограничений (3.5) двойственной задачи, а свободные члены b1, b2, … ,bm основных ограничений (3.2) исходной задачи являются коэффициентами целевой функции (3.4) двойственной задачи.

Итак, число переменных у1, у2, …, уm в двойственной задаче равно m – числу основных ограничений исходной задачи, а число основных ограничений двойственной задачи равно n – числу переменных исходной задачи;

2) матрица коэффициентов основных ограничений двойственной задачи является транспонированной по отношению к матрице А коэффициентов при переменных в основных ограничениях исходной задачи;

3) неравенства основных ограничений исходной задачи имеют знак « », а неравенства двойственной задачи – « »;

4) целевая функция (3.1) исходной задачи – на максимум, а двойственной (3.4) – на минимум.

Если в исходной задаче ограничения выражены равенствами, то соответствующая ей двойственная задача будет иметь ограничения- неравенства. Такие задачи называются несимметричными:

Основные утверждения о взаимно двойственных задачах содержатся в следующих теоремах.

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

.

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

Вторая теорема двойственности.Для того, чтобы два допустимых решения и У=(у1, у2, …, уm) пары двойственных задач были оптимальными необходимо и достаточно, чтобы они удовлетворяли так называемым «условиям дополняющей нежесткости»:

1)

2)

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

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

.

Двойственность в линейном программировании

Принцип двойственности в линейном программировании позволяет получить аналогичные результаты для следующей задачи [c.291]

ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ [c.56]

Все результаты по двойственности в линейном программировании распространяются и на квадратичный случай. [c.7]

Экономическая интерпретация двойственности в линейном программировании [c.205]

Существует много методов оценки напряженности заданий коэффициентный метод оценки напряженности плана по темпам роста к предыдущему периоду метод оценки напряженности плана с точки зрения нормативного использования производственных ресурсов метод применения апостериорного статистического критерия качества планирования. Для этих же целей широко применяются методы линейного программирования, объективно обусловленные оценки В. Новожилова, вытекающие из процедуры решения двойственных задач линейного программирования. В последние годы для оценки напряженности плана разработаны специальные методики, базирующиеся на методах теории статистических распределений, компонентного анализа, современного факторного анализа, других математико-статистических методах. [c.236]

В тех случаях, когда задачи АСУ решаются с использованием дисковой операционной системы ДОС ЕС, программное обеспечение задачи планирования строится на основе пакета LPS-360 [30]. Эта система позволяет при объеме оперативной памяти свыше 64 К эффективно решать задачи, системы ограничений которых включают до 1500 строк. Пакет осуществляет решение прямой и двойственной задачи линейного программирования, выдает информацию о значениях ошибок, позволяет создавать контрольные точки, объединять блоки, вносить изменения и дополнения в систему ограничений и целевую функцию. Разработанные с целью привязки пакета к задачам планирования нефтеперерабатывающих производств Генератор модели» и Интерпретатор» обеспечивают автоматическое построение модели планирования НПП на основе исходных данных о структуре производства, технологических агрегатов и установок, а также представление результатов решения в виде выходных документов, используемых планово-экономическими службами завода. [c.179]

Наоборот, если L (b, с) ), если решение ЛП-задачи на максимум или на минимум существует, то оптимальное (максимальное или минимальное) значение целевой функции в исходной задаче должно быть в точности равно оптимальному (минимальному или максимальному) значению целевой функции двойственной задачи. [c.72]

Читать еще:  Код ошибки 0x80070103

ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ [duality in linear programming] — принцип, заключающийся в том, что для каждой задачи лилейного программирования можно сформулировать двойственную задачу, [c.71]

Рассмотрим двойственную задачу линейного программирования, которая получается по общей схеме. Ограничениям вида (2.17) поставим в соответствие переменные щ, а ограничени- [c.486]

Следующее свойство оптимальных стратегий игроков в матричной игре называется «дополняющей нежесткостью» по аналогии со сходным свойством решений пар двойственных задач линейного программирования (ср. далее в 26). По своей формулировке и своему доказательству оно сходно с частью 1) теоремы предыдущего пункта и двойственным ей утверждением. [c.60]

Итак, получается, что двойственные оценки (множители Лаг-ранжа) являются ценами и выполняют, по крайней мере, распределительную функцию цен (в силу единственности решения двойственной задачи линейного программирования). [c.69]

На самом деле вероятность однозначна, если при анализе того или иного расчетного состояния системы под ней понимать не факт наличия дефицита мощности в ЭЭС, зависящего как раз от принятого принципа взаиморезервирования, а факт потенциальной возможности распределения дефицита мощности (РДМ) в рассматриваемую ЭЭС. В линейной постановке вероятность дефицита мощности в отдельных ЭЭС объединения однозначно определяется по двойственным оценкам линейного программирования [164]. Можно констатировать, что эти вероятности первичны по отношению к вероятностям дефицита мощности, полученным в результате решения задачи устранения неоднозначности РДМ (локальный или другие принципы). Такой трактовке вероятностей отвечает коллективный принцип РДМ, при котором в ЭЭС, потенциально определяющие дефицит мощности объединения, распределяется его часть. В связи с вышесказанным, чтобы не вносить путаницу, ПН, пригодные для целей нормирования при централизованной системе управления объединением ЭЭС, правильнее именовать интегральными вероятностями потенциального дефицита генерирующей мощности (J — для отдельных ЭЭС и Ju — для связей). Эти показатели являются част- [c.77]

Описанные выше свойства пары двойственных задач линейного программирования являются идейной основой двойственного симплекс-метода, который представляет собой итеративный процесс целенаправленного перебора сопряженных (двойственно допустимых) базисов и соответствующих псевдопланов. В этом и заключено его принципиальное отличие от обычного симплекс-метода, в котором последовательно рассматриваются допустимые базисные планы прямой задачи1. Нетрудно догадаться, что при определенной структуре задачи путь, предлагаемый двойственным алгоритмом, может оказаться более коротким. [c.71]

Разберите ход вычислений в методе Лемке с искусственной переменной применительно к паре двойственных задач линейного программирования. [c.29]

Идея о построении системы цен на основе оптимального планирования производства была высказана Л. В. Канторовичем в процессе разработки методов линейного программирования и их использования для решения экономических задач [39J. Аналогично тому, как в нашей задаче множитель Лаг-ранжа являлся выражением рациональной цены продукта при единичной цене ресурса, так и двойственные оценки ограничений в линейных задачах планирования производства могут быть использованы для построения системы стимулирования, согласованной с плановым заданием. Рассмотрим этот важный вопрос более подробно. [c.346]

Построение систем стимулирования на основе двойственных оценок задач линейного программирования. Пусть изучаемая экономическая система состоит из п производственных единиц каждая из которых описывается в виде совокупности технологических процессов (см. 1 гл. 3). Мы не станем каким-либо образом помечать принадлежность технологических процессов к отдельным предприятиям и рассмотрим их в целом. При этом одинаковые технологические процессы, принадлежащие различным предприятиям, будем считать различными. Пусть всего в системе имеется т технологических процессов. Обозначим через х — = (xt,. . хт) вектор интенспвностей использования этих процессов. Будем считать, что всего в системе имеется k продуктов (внешних ресурсов), используемых и производимых в системе. Тогда вектор конечной продукции у = (у. . гд) связан с ин-тснсивностями производства соотношением [c.347]

Для решения подобных задач имеется ряд алгоритмов, которые строятся на основе принципа декомпозиции. Наиболее широко известны декомпозиционные алгоритмы, предложенные Данцигом и Вольфом [26], Корнай и Липтаком [61]. В терминах задачи распределения производственной программы отрасли с использованием моделей, решаемых методами линейного программирования, идея алгоритма Данцига-Вольфа следующая. Центральный орган управления отраслью устанавливает цены (двойственные оценки) на продукцию. Исходя из максимизации прибыли при этих ценах, каждое предприятие разрабатывает свою производственную программу. Центральный орган обобщает планы предприятий и сравнивает их с потребностями народного хозяйства в разных видах продукции отрасли. Затем производится корректировка цен если предложенный выпуск продукции данного вида меньше потребности, то цена на нее повышается если выпуск превышает потребность, то цена понижается. Новые цены сообщаются предприятиям для проведения следующей итерации и т. д. [c.189]

С помощью линейного программирования можно решить и следующую задачу имеет личсмысл увеличить количество доступного ресурса. Например, каков результат увеличения рабочего времени в сборочном цехе на 1 ч в неделю. Этот результат — добавочная валовая прибыль, которая может быть получена, называется двойственной оценкой данного ресурса. [c.113]

Двойственность в линейном программировании

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

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

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

Читать еще:  Ошибка crc hdd

Обозначив через yi, i=1, . m неизвестные двойственной задачи, запишем ее математическую модель в виде:

Найти min z =

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

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

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

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

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

Вторая теорема двойственности устанавливает соотношения между компонентами оптимальных решений прямой и двойственной задач. Для того, чтобы допустимые решения x1,x2, . xn; y1,y2, . ym прямой и двойственной задач были бы их оптимальными решениями, необходимо и достаточно выполнение условий:

Условиям второй теоремы двойственности можно дать следующую экономическую интерпретацию: i-й вид ресурса имеет ненулевую цену, если полностью расходуется в процессе производства (такой ресурс будем называть дефицитным); j-й вид продукции производится, если стоимость затраченных на его производство ресурсов по оптимальным ценам равна прибыли от реализации данной продукции (такой вид продукции будем называть базисным).

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

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

Диапазоном устойчивости оптимального плана при изменении запаса ресурса bi назовем множество значений bi, при которых остаются неизменными оптимальные цены ресурсов (оптимальные объемы выпуска базисных видов продукции линейно меняются при переходе от нижней к верхней границе диапазона устойчивости).

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

Сформулированные выше положения двойственности для базовой задачи планирования производства и симметричной к ней задачи об условных ценах ресурсов остаются в силе и в общем случае, когда имеют место не только потребляемые, но и накапливаемые ингредиенты. При этом потребляемым ингредиентам соответствуют неотрицательные значения условных цен (положительные — для дефицитных ингредиентов, полностью расходуемых в процессе производства, и нулевые — для недефицитных ингредиентов). Накапливаемым ингредиентам соответствуют неположительные значения условных цен. Если при оптимальном плане производства продукции объем накапливаемого ингредиента в точности равен заданному значению, то его условная цена отрицательна (подобная ситуация имеет место при госзаказе на невыгодный для предприятия вид продукции). При превышении заданного объема накапливаемого ингредиента его условная цена равна нулю (установлен госзаказ на выгодный вид продукции, которая производится в объеме, превышающем госзаказ).

Двойственность в линейном программировании

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

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

Двойственная задача — это вспомогательная задача линейного программирования, получаемая с помощью определенных правил непосредственно из условий исходной. Сформулируем правила построения двойственных задач:

1. Если целевая функция f исходной задачи максимизируется, то целевая функция z двойственной — минимизируется, и наоборот.

2. Количество ограничений (m) исходной задачи равно количеству переменных двойственной, а количество переменных (n) исходной равно количеству ограничений двойственной. Переменные двойственной задачи обозначим через .

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

4. Каждой переменной неограниченной по знаку, соответствует ограничение вида «=» двойственной задачи, и наоборот.

5. Свободные члены ограниченной исходной задачи в двойственной являются коэффициентами при переменных в целевой функции, а коэффициенты при переменных в целевой функции исходной задачи являются свободными членами ограничений двойственной.

6. Матрица А коэффициентов при неизвестных в ограничениях исходной задачи в двойственной транспонируется .

Для наглядности связь между исходной и двойственной задачами представлена в таблице 16.

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

Двойственная к этой задаче будет иметь вид:

Если применить правила построения двойственных задач, то получим исходную задачу.

В таблице 17 приведены частные виды исходных задач линейного программирования в матричном виде и соответствующие им двойственные задачи. Через обозначена матрица — строка неизвестных двойственной задачи.

Матрица-строка Y умножается слева на матрицу — столбец В (в целевой функции) и матрицу А (в ограничениях), исходя из правил умножения двух матриц, а также правил построения двойственных задач (в частности, в двойственной задаче матрица коэффициентов при неизвестных в ограничениях должна быть транспонированной).

Первые две пары взаимно двойственных задач в таблице 17 называются симметричными, вторые две — несимметричными из-за наличия ограничений вида «=».

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

Ссылка на основную публикацию
Adblock
detector