Основные предпосылки метода динамического программирования. Динамическое программирование, основные принципы. Этап II. Безусловная оптимизация

1.6.1. Понятие двойственной задачи ЛП . Пусть задана КЗЛП (1.7). Если целевая функция f (x ) = cx достигает макси­мального значения на множестве D , то обоснованным представ­ляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некото­рый m -мерный вектор, то

Предположим, что и можно выбрать таким образом, чтобы иА ≥ с . Тогда при любых х ≥ 0 справедливо неравенство

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

F Если задана каноническая задача ЛП

то задача ЛП

называется двойственной по отношению к ней. Соот­ветственно, задача (D, f ) no отношению к

(D*,f *) назы­вается прямой (или исходной).

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

F Если задана общая задача ЛП

f (x ) = c 1 x 1 + ... + с j х j + с j +1 х j+ 1 + ... + с n x n → max, x Î D, (1.50)

где D определяется системой уравнений и неравенств:

то двойственной по отношению к ней называется об­щая задача ЛП

где D* определяется системой уравнений и неравенств:

Правила построения задачи, двойственной по отношению к ОЗЛП, наглядно представлены схемой, показанной на рис. 1.9.

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

1. Тип оптимума меняется на противоположный, т. е. макси­мум на минимум, и наоборот.

2. Вектор коэффициентов целевой функции с и столбец огра­ничений b меняются местами.

3. Матрица ограничений задачи A транспонируется.

4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, х j ≥ 0 или u j ≥ 0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (a j u ≥ с j или a i x ≤ b j ).

5. Множество номеров ограничений, имеющих форму нера­венств в прямой задаче (например, a i x ≤ b j или a j u ≥ с j) , опреде­ляют множество индексов переменных, на которые накладыва­ется условие неотрицательности, в двойственной задаче (u i ≥ 0 или x i ≥ 0).

F F Из приведенного определения вытекает важное свой­ство - симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, со­впадает с прямой (исходной) задачей :

Тем самым имеет смысл говорить о паре взаимно двой­ственных задач.

В матричной форме пара двойственных общих задач линей­ного программирования может быть кратко записана как:

Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП (D , f ):

тогда двойственной к ней будет задача (D* , f* ):

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

Доказательство.

Достаточно доказать теорему для случая, когда задача (D , f ) является канонической. Рассмотрим пару двойственных задач

Из того, что вектор и является допустимым планом задачи (D *, f *), следует, что иА ≥ с . Умножив левую и правую части дан­ного неравенства на вектор х ≥ 0 , получим равносильную сис­тему неравенств

Одновременно для вектора х, являющегося допустимым планом задачи (D, f ), справедливо равенство Ax=b . Тем самым доказа­но, что иb ≥ сх. A

Замечание. Теорема 1.4, разумеется, верна и для оптималь­ных планов взаимно двойственных задач: f(x*) ≤ f*(u*), где х* и u*- любые оптимальные планы задач (D, f ) и (D*,f *). На самом деле, как будет видно из дальнейшего, справедливо равенство f(x*) = f*(u*).

Доказательство.

Согласно теореме 1.4, для всех допустимых планов х задачи (D, f ) справедливо неравенство сх < b . По условию теоремы f()=f() или, что то же самое, с = b . Следовательно, верно утверждение: для любого x Î D с >сх , т. е. х является опти­мальным планом для задачи (D, f ).

Рассуждения, доказывающие оптимальность плана для за­дачи (D* ,f *), проводятся аналогично. A

Доказательство.

Если предположить, что у двойственной задачи (D *,f *) су­ществует хотя бы один допустимый план и̃ , то, согласно теоре­ме 1.4, для любого допустимого плана х задачи (D, f ) справед­ливо неравенство f(x) ≤ f *( ) <+∞. Последнее означает, что целевая функция f задачи (D, f ) ограничена сверху. Поскольку это противоречит условию теоремы, предположение о сущест­вовании допустимых планов двойственной задачи (D*,f *) не­верно. A

Следующее утверждение, известное как теорема равнове­сия , используется при проверке оптимальности планов ЗЛП.

Доказательство.

Векторы х* и и*, будучи допустимыми планами соответствую­щих задач, удовлетворяют условиям: Ах* = b , х* > 0 и и*А-с ≥ 0 . Найдем скалярное произведение

Согласно замечанию к теореме 1.2, оптимальные значения целевых функций взаимно двойственных задач совпадают, т. е. u*b=сх*. Последнее означает, что (u*А-с)х* = 0 . Однако ска­лярное произведение двух неотрицательных векторов может быть равно нулю только в том случае, когда все попарные про­изведения их соответствующих координат равны нулю. Следо­вательно, если x j * > 0, то u*а j – с j = 0, если же x j = 0, то возмож­но u*а j – с j ≥ 0 , что и утверждается в теореме. A

Практическое значение теорем двойственности состоит в том, что они позволяют заменить процесс решения основной задачи на решение двойственной, которое в определенных случаях может оказаться более простым. Например, задача, область до­пустимых значений которой описывается двумя уравнениями, связывающими шесть переменных (m = 2, n = 6), не может быть решена графическим методом. Однако данный метод может быть применен для решения двойственной к ней задачи, которая име­ет только две переменные.

Еще раз вернемся к таблице Т 2 ( q ) (рис. 1.8 ), получаемой на финальной итерации процедуры модифицированного симплекс-метода. Более подробно рассмотрим нулевую строку матрицы Δ -1 (β ( q )), для которой было введено обозначение δ 0 (β ( q )). По­элементно она может быть записана в следующем виде:

Введем вектор = (δ 0,1 (β (q )), δ 0,2 (β (q )),..., δ 0,m (β (q ))). Нетруд­но проверить, что строка оценок a 0 (β ( q )) может быть представ­лена следующим образом:

Согласно критерию оптимальности, на последней итерации данная строка неотрицательна, т. е. ũА≥с . Следовательно, век­тор и является допустимым планом двойственной задачи.

В то же время элемент b 0 (β ( q )), содержащий текущее значе­ние целевой функции и равный на последней итерации f(x*), до­пускает представление

Согласно теореме 1.5 из равенства f (х* ) = f *(ũ ) вытекает, что вектор ũ служит оптимальным планом двойственной задачи: u = ũ.

Окончательно можно утверждать, что для оптимального базиса

F F Таким образом, существенным преимуществом модифи­цированного симплекс-метода является то, что он по­зволяет одновременно найти оптимальные планы как, прямой, так и двойственной задачи.

Читателю в качестве самостоятельного упражнения предла­гается построить задачу, двойственную к (1.34)-(1.35), реше­ние которой было приведено в п. 1.5.2, и убедиться, что вектор u = (-10, 32, 2), полученный в таблице Т 2 (3) , является для нее допустимым и оптимальным планом.

1.6.4. Экономическая интерпретация. Традиционная экономическая интерпретация двойственной задачи ЛП бази­руется на модели простейшей задачи производственного планирования , описанной во введении. Напомним, что в ней каждый (j -й) элемент вектора х рассматривается как план вы­пуска продукции данного вида в натуральных единицах, с j - цена единицы продукции j -го вида, а j - вектор, определяющий технологию расходования имеющихся m ресурсов на производ­ство единицы продукции j -го вида, b - вектор ограничений на объемы этих ресурсов.

Предположим, что для некоторых значений A, b и с найден оптимальный план х* , максимизирующий суммарный доход max{cx }=cx *. Достаточно естественным представляется во­прос: как будет изменяться оптимальный план х * при измене­нии компонент вектора ограничений b и, в частности, при ка­ких вариациях b оптимальный план х * останется неизменным? Данная задача получила название проблемы устойчивости оптимального плана. Очевидно, что исследование устойчи­вости х * имеет и непосредственное практическое значение, так как в реальном производстве объемы доступных ресурсов b i ; могут существенно колебаться после принятия планового решения х *.

Когда вектор ограничений b изменяется на Δb или, как еще говорят, получает приращение Δb , то возникают соответству­ющие вариации для оптимального плана х*(b+ Δb) и значения целевой функции f(х *(b+ Δb )). Допустим, приращение Δb та­ково, что оно не приводит к изменению оптимального базиса задачи, т. е. х*(b+ Δb) ≥0. Определим функцию F (b ), возвраща­ющую оптимальное значение целевой функции задачи (D (b ), f ) для различных значений вектора ограничений b

Рассмотрим отношение ее приращения F(b+ Δb)-F(b) к при­ращению аргумента Δb . Если для некоторого i устремить Δb i → 0, то мы получим

Учитывая, что в соответствии с теоремой 1.5

и подставив (1.57) в (1.56), приходим к выражению

F F Из формулы (1.58) вытекает экономическая интерпре­тация оптимальных переменных двойственной зада­чи . Каждый элемент u i * может рассматриваться как предель­ная (мгновенная) оценка вклада i -го ресурса в суммарный доход F при оптимальном решении х *. Грубо говоря, величи­на u i * равна приросту дохода, возникающему при увеличе­нии ресурса i на единицу при условии оптимального ис­пользования ресурсов.

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

На основе теорем двойственности для пары задач ЛП в об­щей форме могут быть сформулированы некоторые важные (с точки зрения экономической интерпретации) следствия.

F F Если при использовании оптимального плана прямой за­дачи i-e ограничение выполняется как строгое неравен­ство, то оптимальное значение соответствующей двой­ственной переменной равно нулю, т.е. если

В рамках рассматриваемой задачи производственного плани­рования это означает, что если некоторый ресурс b i , имеется в избыточном количестве (не используется полностью при реа­лизации оптимального плана), то i -e ограничение становится несущественным и оценка такого ресурса равна 0.

F F Если при использовании оптимального плана двойствен­ной задачи j-e ограничение выполняется как строгое не­равенство, то оптимальное значение соответствую­щей переменной прямой задачи должно быть равно нулю, т. е. если a 1, j u 1 * +...а m , j и m – с j > 0, то х j * = 0.

Учитывая экономическое содержание двойственных оценок u 1 *,...,u m , выражение а 1, j u 1 * +…a m , j u m * может быть интерпретиро­вано как удельные затраты на j -й технологический процесс. Сле­довательно, если эти затраты превышают прибыль от реализа­ции единицы j -го продукта, то производство j -го продукта является нерентабельным и не должно присутствовать в опти­мальном производственном плане (x j * =0).

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

1.6.5. Анализ параметрической устойчивости реше­ний ЗЛП . В предыдущем пункте мы затронули некоторые ас­пекты чувствительности и устойчивости оптимального плана по отношению к изменению вектора ограничений b . Очевидно, что аналогичные вопросы могут быть поставлены для случая вариации коэффициентов целевой функции с j , j Î1:n .

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

Также содержание проблемы устойчивости оптимального плана ЗЛП по отношению к вариациям целевой функции может быть проиллюстрировано с помощью первой геометрической интерпретации. На рис. 1.10 изображено множество допусти­мых планов D некоторой задачи ЛП. Как видно из рисунка, це­левая функция f (ее поведение отражает линия уровня, пока­занная жирным пунктиром) достигает экстремального значе­ния в точке х *, а изменению ее коэффициентов от с к с" или с" на рисунке соответствует поворот линии уровня относительно х *. Активным, т. е. обращающимся в равенство, ограничениям в точке х * соответствуют линии (1) и (2). До тех пор, пока при повороте, вызванном изменением вектора с , линия уровня целе­вой функции не выходит за пределы образуемого линиями огра­ничений конуса, х* остается оптимальным планом. Как показа­но на рис. 1.10 , этот план не меняется при переходе от с к с" , и, наоборот, при переходе от с к с" линия уровня целевой функции f(x)=c"x пересечет линию (2), что вызовет изменение опти­мального базисного плана, которым теперь станет точка .

Используя условия оптимальности плана ЗЛП

нетрудно получить количественные оценки для пределов коле­баний коэффициентов целевой функции, при которых не проис­ходит изменение оптимального плана. Допустим, вариации под­вергся некоторый элемент с r : с r ′ = с r + ε r . Возможны два случая:

1. Столбец r не входит в оптимальный базис (r Î N (β ( q ))). Тог­да для неизменности оптимального плана необходимо и доста­точно выполнение условия

Отсюда можно получить значение для допустимой вариации

2. Столбец r входит в оптимальный базис (r Î N (β ( q ))). В этом случае для сохранения оптимальности текущего плана потре­буется выполнение для всех небазисных столбцов (j Ï N (β ( q ))) условий

Следовательно, в этом случае допустимая вариация должна удовлетворять условиям

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

Основные определения теории двойственности .

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

Рассмотрим задачу о планируемом выпуске продукции.

F = 3х 1 + 5х 2 + 4х 3 + 5х 4 → max.

Общие правила составления двойственной задачи :

Прямая	Двойственная
Целевая функция (min)	Правая часть ограничений
Правая часть ограничений	Целевая функция (max)
A - матрица ограничений	A T - матрица ограничений
i-ое ограничение: ≥ 0, (≤ 0)	Переменная y i ≥ 0, (≤ 0)
i-ое ограничение: = 0	Переменная y i ≠ 0
Переменная x j ≥ 0	j-ое ограничение: ≤ 0
Переменная x j ≠ 0	j-ое ограничение: = 0

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

1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.
2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.
3. Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.
4. Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.

Заметим, что строки матрицы задачи I являются столбцами матрицы задачи II. Поэтому коэффициенты при переменных y i в задаче II - это, соответственно, коэффициенты i -го неравенства в задаче I.
Полученная модель и есть экономико-математическая модель задачи, двойственной к прямой задаче.

Неравенства, соединенные стрелочками, будем называть сопряженными .
Содержательная постановка двойственной задачи : найти такой набор цен (оценок) ресурсов Y = (y 1 , у 2 ..., у m), при котором общие затраты на ресурсы будут минимальны при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции.
Цены ресурсов у 1 , у 2 ..., у m в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл этих названий состоит в том, что это условные, «ненастоящие» цены. В отличие от «внешних» цен с 1 , с 2 ..., с n на продукцию, известных, как правило, до начала производства цены ресурсов у 1 , у 2 ..., у m являются внутренними, ибо они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их чаще называют оценками ресурсов.
Связь прямой и двойственной задач состоит, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.

Теоремы двойственности

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

Первая теорема двойственности .

Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F (x *) = G (y *), где х *, у * - оптимальные решения задач I и II

Вторая теорема двойственности .

Планы х * и у * оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задач I и II соответственно хотя бы одно из любой пары сопряженных неравенств обращается в равенство.
Это основная теорема двойственности . Другими словами, если х * и у * - допустимые решения прямой и двойственной задач и если c T x*=b T y*, то х * и у * – оптимальные решения пары двойственных задач.

Третья теорема двойственности . Значения переменных y i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов b i системы ограничений - неравенств прямой задачи на величину целевой функции этой задачи:
Δf(x) = b i y i

Решая ЗЛП симплексным методом, мы одновременно решаем двойственную ЗЛП. Значения переменных двойственной задачи y i , в оптимальном плане называют объективно обусловленными, или двойственными оценками. В прикладных задачах двойственные оценки y i часто называются скрытыми, теневыми ценами или маргинальными оценками ресурсов.

Свойство взаимно двойственных задач

1. В одной задаче ищут максимум линейной функции, в другой - минимум.
2. Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой.
3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида ≤ , а в задаче минимизации все неравенства вида ≥ .
4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу:
5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.
6. Условия неотрицательности переменных имеются в обеих задачах.

Итак, имеем исходную задачу I и ее оптимальное решение х * = (0, 40, 0, 100) и F (х *) = 700.

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

Рассмотрим выполнение неравенств задачи I при подстановке х * в систему ограничений.

5x 1 +0,4x 2 +2x 3 +0,5x 4 ≤400	5*0+0,4*40+2*0+0,5*100=66<400	Ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y 1 = 0.
5x 2 +x 3 +x 4 ≤300	5*40 + 0 + 100 = 300 = 300	Ограничение прямой задачи выполняется как равенство. Это означает, что 2-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y 2 ≠ 0)
x 1 + x 3 + x 4 ≤ 100	0 + 0 + 100 = 100 = 100	y 3 ≠ 0
x 1 ≥ 0	x 1 = 0	Первое ограничение в двойственной задаче будет неравенством 5y 1 + y 3 ≥ 3
x 2 ≥ 0	x 2 = 40 > 0	Второе ограничение в двойственной задаче будет равенством 0,4y 1 + 5y 2 = 5
x 3 ≥ 0	x 3 = 0	Третье ограничение в двойственной задаче будет неравенством 2y 1 + y 2 + y 3 ≥ 4
x 4 ≥ 0	x 4 = 100 > 0	Четвертое ограничение в двойственной задаче будет равенством 0,5y 1 + y 2 + y 3 = 5

Поскольку 1, 5, 7 неравенства строгие (имеют знак "<" или ">"), то соответствующие им неравенства в задаче II из пары сопряженных обязаны обратиться в равенства. имеем:

или

т.е. у * = (0, 1, 4) - оптимальное решение.

Заметим, что действительно G (y *) = 400y 1 + 300y 2 + 100y 3 = 400 · 0 + 300 · 1 + 100 · 4 = 700 = F (x *).

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

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

Установив такую связь, можно заметить, что, решив задачу I симплекс-методом и получив последнюю симплекс-таблицу (табл.), мы фактически решим и задачу II.

Запишем таблицу, учитывая соответствие между переменными х i и y j .

		у 4	у 2	у 6	у 3
	базисные	-х 1	-х 6	-х 3	-х 7	свободные
у 1	х 5					334
у 5	х 2					40
у 7	х 4					100
	-F	1	1	1	4	700

В силу соответствия и II теоремы двойственности переменные у 1 , у 5 , у 7 обязаны равняться 0, т.к. х 5 , х 2 , х 4 >0 строго. А переменные у 4 , у 2 , у 6 , у 3 принимают значения из индексной строки 1, 1, 1, 4 соответственно, т.к. им соответствующие переменные х 1 , х 6 , х 3 , х 7 = 0, как свободные. Итак, из последней таблицы задачи II, не проводя даже никаких вычислений и пользуясь лишь соответствием переменных:

у * = (у 1 *, у 2 *, у 3 *, у 4 *, у 5 *, у 6 *, у 7 *) = (0, 1, 4, 1, 0, 1, 0).

Мы научились по решению исходной задачи находить решение двойственной. Это оказалось возможно благодаря глубокой связи между переменными х i и y j . Осталось разобраться,

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

хорошую работу на сайт">

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

Размещено на http://www.allbest.ru/

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

План

1. Постановка и модель двойственной задачи

2. Методы решения

3. Теоремы теории двойственности и ее экономическое содержание

1. Постановка и модель двойственной задачи

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

Напомним, что в основе задачи линейного программирования рассматривается предприятие, имеющее ресурсы b i , где i = 1, 2, …, m . Оно тратит их на изготовление готовой продукции и эту продукцию реализует. При этом ставится цель - получить максимум продукции в стоимостном выражении не перерасходуя ресурсы. Модель задачи выглядит следующим образом: двойственный симплекс линейный программирование

I) Ж = с 1 х 1 + с 2 х 2 + … + с n х n max.

II) a 11 х 1 + а 12 х 2 + … + а 1 n х n ? b 1 ,

a 21 х 1 + а 22 х 2 + … + а 2 n х n ? b 2 ,

………………………………

a m 1 х 1 + а m 2 х 2 + … + а mn х n ? b m .

III) х j ? 0, j = 1, 2, …, n .

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

Тогда, в так называемой двойственной модели , целевая функция будет описывать интерес покупающей стороны, система ограничений - интерес продающей стороны (необходимо оценить ресурсы, которые пошли бы на изготовление единицы продукции и стоимость этих ресурсов ограничить ценой реализованной единицы продукции). Третье условие (неотрицательность переменных величин) будет выполняться в силу того, что цена единицы ресурса не может быть отрицательной. Введя в качестве цены единицы ресурса величину u i 0 (i = 1, 2, …, m ), ее еще называют оценкой ресурса (или двойственной оценкой), получим следующую модель:

I) F = b 1 u 1 + b 2 u 2 + … + b m u m min.

II) a 11 u 1 + a 21 u 2 + … + a m 1 u m c 1 ,

a 12 u 1 + a 22 u 2 + … + a m 2 u m c 2 ,

………………………………

a 1 n u 1 + a 2 n u 2 + … + a mn u m c n .

III) u i 0, i = 1, 2, …, m .

Сопоставим обе задачи:

Первая - задача на максимум (z max), вторая - на минимум (F min);

В первой система ограничений типа, во второй;

В первой задаче n неизвестных и m ограничений, во второй m неизвестных и n ограничений;

Коэффициенты в целевых функциях и величины в правых частях неравенств при переходе из одной задачи в другую меняются местами (в первой задаче c j - коэффициенты целевой функции, во второй c j - свободные члены; в первой задаче b i - свободные члены, во второй b i - коэффициенты целевой функции);

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

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

Алгоритм составления двойственной задачи:

1) тип экстремума целевой функции меняется;

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

3) свободные члены исходной задачи становятся коэффициентами при переменных в целевой функции двойственной задачи;

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

Рассмотрим конкретный пример построения двойственной модели:

исходная задача:

I) Z = 6x 1 + 4x 2 max.

II) 2x 1 +4 x 2 ? 8,

2x 1 + x 2 ? 6.

III) x 1 ? 0, x 2 ? 0.

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

I) F = 8u 1 + 6u 2 min.

II) 2u 1 + 2u 2 ? 6,

4u 1 + u 2 ? 4.

III) u 1 ? 0, u 2 ? 0.

Следует отметить, что:

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

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

2. Методы решения

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

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

исходная задача (введем y i 0):

I) Ж = с 1 х 1 + с 2 х 2 + … + с n х n max.

II) y 1 = -a 11 х 1 - а 12 х 2 - … - а 1 n х n + b 1 ,

y 2 = -a 21 х 1 - а 22 х 2 - … - а 2 n х n + b 2 ,

…………………………………..

y m = -a m 1 х 1 - а m 2 х 2 - … - а mn х n + b m .

III) х j ? 0, j = 1, 2, …, n .

двойственная задача (введем v j 0):

I) F = b 1 u 1 + b 2 u 2 + … + b m u m min.

II) v 1 = a 11 u 1 + a 21 u 2 + … + a m 1 u m - c 1 ,

v 2 = a 12 u 1 + a 22 u 2 + … + a m 2 u m - c 2 ,

……………………………………

v n = a 1 n u 1 + a 2 n u 2 + … + a mn u m - c n .

III) u i 0, i = 1, 2, …, m .

Обе модели записываются в двойственную симплекс-таблицу следующим образом (таблица 4):

Таблица 4 - Двойственная симплексная таблица

					v n
					-x n	Свободные члены
					a 1 n
					a 2 n
u m	y m	a m 1	a m 2		a mn	b m
Свободные члены					-c n

Замечания:

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

Прежде чем составлять модель двойственной задачи, необходимо у исходной модели «выровнять» знаки, т.е. если целевая функция стремится к max , то все знаки в системе ограничений должны быть ? , а если к min , то ? . Система приводится в соответствие путем домножения обеих частей «неподходящего» неравенства на (-1). Например, чтобы записать модель, двойственную к приведенной модели

I) Z = 4x 1 + 2x 2 + 3x 3 min.

II) -4x 1 - 3x 2 +x 3 ? -4,

5x 1 + x 2 +2x 3 ? 6.

III) x 1 ? 0, x 2 ? 0, x 3 ? 0,

необходимо исходную переписать в виде:

I) Z = 4x 1 + 2x 2 + 3x 3 min.

II) 4x 1 + 3x 2 - x 3 ? 4,

5x 1 + x 2 +2x 3 ? 6.

III) x 1 ? 0, x 2 ? 0, x 3 ? 0.

Тогда двойственная задача будет выглядеть так:

I) F = 4u 1 +6u 2 max.

II) 4u 1 + 5u 2 ? 4,

3u 1 + u 2 ? 2,

-u 1 + 2u 2 ? 3.

III) u 1 ? 0; u 2 ? 0;

В центр двойственной симплекс-таблицы (таблицы 4) всегда ставится задача на max, вне зависимости от того какова целевая функция исходной задачи.

3. Основные теоремы теории двойственности и ее экономическое содержание

В качестве основной теоремы двойственности выделяют следующую формулировку: если одна из взаимно двойственных задач имеет оптимальное решение, то и другая также имеет оптимальное решение, при этом соответствующие им оптимальные значения целевых функций равны (т.е. max z = min F ).

Кроме этого варианта возможны следующие взаимоисключающие случаи:

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

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

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

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

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

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

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

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

Абсолютные значения оценок можно трактовать как некоторые расчетные «цены» ресурсов и потребностей, выраженные в тех же единицах, что и критерий, а знак «+» или «-» при этих «ценах» показывает, ведет ли увеличение данного фактора к возрастанию или уменьшению значения критерия;

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

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

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

Размещено на Allbest.ru

...

Подобные документы

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

курсовая работа , добавлен 31.10.2014


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

курс лекций , добавлен 14.07.2011


Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

курсовая работа , добавлен 21.03.2012


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

курсовая работа , добавлен 11.02.2011


Оптимальный план прямой задачи графическим, симплекс-методом. План двойственной задачи по первой теореме двойственности. Определение целочисленного решения графическим, методом Гомори. Сравнение значений функций целочисленного и нецелочисленного решений.

задача , добавлен 29.12.2013


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

контрольная работа , добавлен 08.09.2010


Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.

курсовая работа , добавлен 09.12.2008


Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.

контрольная работа , добавлен 11.04.2012


Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.

контрольная работа , добавлен 15.01.2009


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

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

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

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

.

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

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

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

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

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

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

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

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

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

Пример 7.1

Прямая задача:

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

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

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

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

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

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

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

, (7.1)

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

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

если , то , (7.2)

если , то , (7.3)

если , то , (7.4)

если , то . (7.5)

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

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

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

формулу (7.3)). В первом случае ресурс является дефицитным, во втором – недефицитным. Для недефицитного ресурса значение соответствующей балансовой переменной покажет его остаток после выполнения оптимального плана. Чем больше оценка ресурса, тем он дефицитнее с точки зрения его вклада в поставленную цель – максимизировать суммарную выручку.

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

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

Пример 7.2

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

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

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

; ; .

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

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

,

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

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

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

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

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

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

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

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

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

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

Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной.

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

Связующим фактом этих двух задач являются коэффициенты C j функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты B i системы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограничений двойственной задачи.

Рассмотрим задачу использования ресурсов.

У предприятия есть т видов ресурсов в количестве b i (i = 1, 2, ..., m) единиц, из которых выпускается n видов продукции. На изготовление1 ед. i -й продукции тратится a ij ед. t-гo ресурса, ее стоимость составляет C j ед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за x j (j =1,2, ..., n) количество ед. j -й продукций.

Сформулируем исходную задачу. Определить вектор Х =(x 1 , x 2 , …, x n), который удовлетворяет ограничениям

a 11 x 1 + a 12 x 2 + … + a 1n x n Ј b 1,

a 21 x 1 + a 22 x 2 + … + a 2n x n Ј b 2, x j і 0 (j =1,2, ..., n)

a m 1 x 1 + a m 2 x 2 + … + a mn x n Ј b m ,

и составляет максимальное значение линейной функции

Z = C 1 x 1 + C 2 x 2 + … + C n x n ,

Определим ресурсы, которые потребуются для изготовления товара. Обозначим за единицу стоимости ресурсов единицу стоимости выпускаемого товара. А через у i (j =1,2, ..., m) стоимость единицы i -го ресурса. Т.е. стоимость всех затраченных ресурсов, которые используются для изобретения единицы j -й продукции, составляет. Цена израсходованных ресурсов не должна превышать цены окончательного товара. Таким образом должно выполняться неравенство і C j , j =1,2, ..., n. Цена имеющихся ресурсов составляет.

Сформулируем двойственную задачу.

Необходимо определить вектор Y =(y 1 , y 2 , …, y n), удовлетворяющий ограничениям

a 11 y 1 + a 12 y 2 + … + a m1 y m Ј C 1,

a 12 y 1 + a 22 y 2 + … + a m2 y m Ј C 2, y j і 0 (i =1,2, ..., m)

a 1n y 1 + a 2n y 2 + … + a mn y m Ј C m ,

Вектор Y =(y 1 , y 2 , …, y n) составляет минимальное значение линейной функции

f = b 1 y 1 + b 2 y 2 + … + b m y m

Переменные у i называются оценками или учетными, неявными ценами

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

А исходную задачу определим следующим образом: сколько и какой продукции x j (j =1,2, ..., n) необходимо произвести, чтобы при заданных стоимостях C j (j =1,2, ..., n) единицы продукции и размерах имеющихся ресурсов b i (i =1,2, ..., n) максимизировать выпуск продукции в стоимостном выражении.

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