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

17.04.2019

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

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

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

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

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

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

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

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

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

Таблица 16

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

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

Максимизация f Количество ограничений m Переменные

x j ³0 i -е ограничение вида «£» х j не ограничено по знаку i -е ограничение вида «=» Свободные члены ограничений b i Коэффициенты при x j в целевой функции (c j ) Матрица коэффициентов при неизвестных в ограничениях (А )

Минимизация z Количество ограничений n Переменные

j-е ограничение вида «³» y i ³0 j -е ограничение вида «=» не ограничено по знаку Коэффициенты при y i в целевой функции (b i ) Свободные члены ограничений (c j ) Транспонированная матрица коэффициентов при неизвестных в ограничениях (A T )

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

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

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

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

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

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

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

Таблица 17

Пример

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

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

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

Для построения двойственной задачи воспользуемся формами (II), (IV) и преобразуем данную задачу путем умножения обеих частей второго неравенства на (–1). Тогда исходная задача будет иметь вид:

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

Используя пример, поясним некоторые правила построения двойственных задач. Поскольку количество ограничений исходной задачи m =3, двойственная задача должна иметь три переменные: Количество переменных исходной задачи n =4, поэтому двойственная должна иметь четыре ограничения. Переменные x 1 и x 4 исходной задачи не ограничены по знаку. В силу этого первое и четвертое ограничения двойственной задачи имеют вид равенств. Третье ограничение исходной задачи имеет вид равенства, следовательно, переменная y 3 двойственной задачи не ограничена по знаку.

Контрольные вопросы и упражнения

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

2. В чем отличие симметричных задач двойственной пары от несимметричных?

3. Постройте задачи, двойственные к данным:

4. Дайте экономическую интерпретацию задачи, двойственной к задаче использования ресурсов.

5. Какая задача из пары взаимно двойственных задач может быть принята в качестве исходной и какая в качестве двойственной? Какие задачи на практике считают двойственными?

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

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

8. Постройте задачу, двойственную к данной:

Решите исходную и двойственную задачи графическим методом.

9. Постройте задачи, двойственные к данным:

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

10. Как по решению исходной задачи найти решение двойственной и наоборот?

Лекция 6.

Внешняя память

Стек МК

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

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

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

Необходимо помнить, что МК обеих архитектур имеют ограниченную емкость памяти для хранения данных. Если в процессоре имеется отдельный стек и объем записанных в него данных превышает его емкость, то происходит циклическое изменение содержимого указателя стека, и он начинает ссылаться на ранее заполненную ячейку стека. Это означает, что после слишком большого количества вызовов подпрограмм в стеке окажется неправильный адрес возврата. Если МК использует общую область памяти для размещения данных и стека, то существует опасность, что при переполнении стека произойдет запись в область данных либо будет сделана попытка записи загружаемых в стек данных в область ПЗУ.

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

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

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

Вопросы:

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

Понятия двойственности, теневой цены, двойственной задачи.

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

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

С 1 х 1 + … + С n x n =F(x) m ax , x j 0, j = .

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

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

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

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

В экономической литературе «теневые» цены часто называют объективно-обусловленными или оптимальными оценками, двойственными или учетными, неявными оценками.

Чтобы определить оптимальные «теневые» цены ресурсов необходимо составить и решить задачу оптимизации. Имеем те же исходные данные, что и для задачи оптимального использования ресурсов. Только теперь необходимо найти такие «теневые» цены ресурсов y = (y 1 , y 2 ,… ,y m), при которых стоимость всех ресурсов была бы минимальна, y i – «теневая» цена единицы i-го ресурса, y i 0.

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

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 )) может быть представлена следующим образом:

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

В то же время элемент 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 ))) условий

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

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

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

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

Связующим фактом этих двух задач являются коэффициенты 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) максимизировать выпуск продукции в стоимостном выражении.

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

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

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

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

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

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

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

3.3 Экономическая интерпретация двойственных задач

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

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

Согласно третьей теореме двойственности оценки ресурсовУ =(у 1 , у 2 , …, у m ) выступают как мера влияния объемов ресурсов на величину максимума товарной продукции (Z max ). Они показывают: на сколько увеличится значение целевой функции при приращении данного ресурса наединицу . Следовательно, еслиi -й ресурс увеличится на
единиц, то целевая функция соответственно возрастет на
ден. ед. Однако надо помнить, что это справедливо только для таких приращений ресурса, которые не вызовут изменение базиса исходной задачи.

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

для коэффициентов
.

Пример расчета предела увеличения ресурса для задачи 2.1 приведен в разделе 2.2. В этой задаче при увеличении ресурса 2, не превышающем 6000 ед., справедлива его оценка y 2 , являющаяся решением двойственной задачи.

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

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

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

Решение двойственной задачи получается в последней симплексной таблице исходной задачи (3.1)-(3.3), в (М+1)-й строке.

Если в качестве исходной задачи служит модель (3.4)-(3.6), то решение двойственной к ней (3.1)-(3.3) получается умножением на (-1) соответствующих элементов (М+1)-й строки последней симплекс-таблицы задачи (3.4)-(3.6).

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

– основным переменным прямой задачи соответствуют дополнительные переменные двойственной;

– дополнительным переменным исходной соответствуют основные переменные двойственной модели.

Значения основных переменных двойственной задачи расположены в столбцах дополнительных переменных (М+1)-й строки симплекс-таблицы прямой задачи, а значения дополнительных переменных – в столбцах основных переменных той же строки.

Рассмотрим оптимальный план задачи 2.1 (таблица 3.1).

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

Исходная задача	х 1	х 2	х 3	х 4	х 5	х 6
Двойственная задача	у 4	у 5	у 6	у 1	у 2	у 3

В таблице 3.1 скопирована последняя симплекс-таблица задачи 2.1 и подписаны обозначения двойственных переменных, значения которых получаются одновременно с решением исходной задачи.

Таблица 3.1 – Расположение оптимального плана двойственной

задачи в симплекс-таблице исходной модели