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

5.1 Понятие двойственности 83

5.2 Экономическая интерпретация двойственной задачи 87

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

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

5.5 Третья теорема двойственности 92

5.6 Пример решения сопряженных задач 96

5.6.1 Задача, двойственная задаче о диете 96

5.6.2 Выполнение основной теоремы двойственности 97

5.6.3 Выполнение теоремы о равновесии 99

5.6.4 Выполнение теоремы об оценке 99

5.7 Вопросы и упражнения 106

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

5.1 Понятие двойственности

Рассмотрим задачи линейного программирования в стандартной форме, записанные в матричной форме:

где С = (с 1 . . . с n), X =, B =, A =

,

где Y= (y 1 . . .y m).

Здесь X, Y - переменные * ; A, B, C - константы.

Задача (21) и любая эквивалентная ей задача линейного программирования называется двойственной задаче (20) и любой эквивалентной ей задаче.

Подчеркнем, что новых переменных вводится ровно столько, сколько в задаче (20) ограничений, т.е. m.

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

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

Теорема (о сопряженных задачах). Задача, двойственная двойственной, эквивалентна исходной.

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

Приведем задачу (21) к стандартной форме на максимум:

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

mах -B Т Y Т

Теперь можно построить двойственную задачу в соответствии со сформулированным определением. Введем строку переменных Z.

Эта задача является двойственной к двойственной. Преобразуем ее.

Эта задача эквивалентна задаче (20) с точностью до обозначения.

Теорема доказана.

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

Рассмотрим задачу в канонической форме. Чтобы построить задачу, двойственную к ней, преобразуем ее к стандартной форме.

Построим теперь двойственную задачу. Отметим, что число ограничений задачи возросло в два раза (каждое уравнение преобразовано в два неравенства). Вектор-строку переменных двойственной задачи разобьем на две части, в каждую из которых будет входить равное число переменных, и обозначим его (U,V) = (u 1 , …,u m ,v 1 , …,v m).

При этом во всех линейных выражениях компоненты вектора В и матрицы А можно вынести за скобки, а в скобках останется разность векторов U = (u 1 , …,u m) и V = (v 1 , …,v m). Например, при перемножении строки переменных на первый столбец матрицы А будет получено: (a 11 u 1 +a 21 u 2 + …+ a m1 u m - a 11 v 1 - a 21 v 2 - … - a m1 v m = a 11 (u 1 - v 1) + a 21 (u 2 – v 2) + … + a m1 (u m – v m); - и т.д.

Обозначим U - V = Y. При этом переменные Y = (u 1 -v 1 ; …;u m –v m) = = (y 1 . . .y m) не ограничены по знаку. Тогда двойственная задача примет вид:

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

На основании проведенных рассуждений можно сделать вывод, что для построения двойственной задачи не обязательно каждый раз приводить задачу линейного программирования к стандартной форме, а именно нет необходимости преобразовывать уравнения к неравенствам, а не ограниченные по знаку переменные - к неотрицательным. Пусть в задаче в смешанной форме первые m` ограничений – уравнения, а остальныеm-m` - неравенства; и первыеn` переменных неотрицательны, а остальныеn-n` переменных по знаку могут быть любыми. Между задачей линейного программирования в смешанной форме и двойственной ей задачей линейного программирования можно установить следующее соответствие:

max c j x j	min b i y i
a ij x j = b i ,	a ij y i c j ,
a ij x j b i ,	a ij y i = c j ,
x j 0,	y i 0,
x j 0,	y i 0,

Сформулируем ряд правил построения двойственной задачи:

а) Переменные двойственной задачи соответствуют ограничениям исходной задачи, а ограничения - переменным.

б) Если исходная задача линейного программирования задана на максимум, то двойственная строится на минимум, и наоборот.

в) В задаче линейного программирования на максимум в ограничениях-неравенствах должен стоять знак , а на минимум -.

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

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

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

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

min 2х 1 + 3х 2 - 4х 3 + х 5

4х 1 - 3х 2 - х 3 + х 4 + х 5 10

х 1 + 4х 2 + х 3 + х 5 = 15

2х 1 - 4х 2 - х 3 + х 4 3

Так как задача на минимум, умножим обе части первого ограничения на -1, чтобы получить знак неравенства : -4х 1 + 3х 2 + х 3 - х 4 - х 5  -10.

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

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

Первое ограничение двойственной задачи соответствует переменной х 1 прямой задачи, поэтому коэффициенты этого ограничения берут из столбца коэффициентов при х 1 , а свободный член – из целевой функции прямой задачи. Так как х 1 0, это ограничение – неравенство. Так как двойственная задача на максимум, знак неравенства. Аналогично строятся второе, третье и пятое ограничения. Четвертое ограничение соответствует переменной х 4 , знак которой может быть любым. Поэтому оно – уравнение.

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

max -10y 1 + 15y 2 + 3y 3

4y 1 + y 2 + 2y 3  2

3y 1 + 4y 2 - 4y 3  3

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 ))) условий

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

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

Введение
Под двойственной задачей понимается вспомогательная задача линейного программирования , формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных.
Целью курсового проекта является изучить литературу по выбранной теме и научиться применять на практике симплекс – метод для решения прямой и двойственной задачи линейного программирования , а также решить двойственную задачу линейного программирования с помощью программы MS Excel .
Курсовой проект состоит из введения, двух глав и заключения.
В первой главе рассматриваются основные понятия и предложения теории двойственности ЗЛП, виды математических моделей двойственных задач и их экономическая интерпретация.
Во второй главе рассматривается решение двойственной задачи с помощью программы MS Excel.

1. Двойственность в линейном программировании
1.1 Прямые и двойственные задачи линейного программирования
С экономической точки зрения двойственную задачу можно интерпретировать так: какова должна быть цена единицы каждого из ресурсов , чтобы при заданных количествах ресурсов b i и величинах стоимости единицы продукции C j минимизировать общую стоимость затрат? А исходную задачу определим следующим, образом: сколько и какой продукции x j (j =1,2,…, n) необходимо произвести, чтобы при заданных стоимостях C j (j =1,2,…, n) единицы продукции и размерах имеющихся ресурсов b i (i =1,2,…, n) максимизировать выпуск продукции в стоимостном выражении. Большинство задач линейного программирования изначально определяются как исходные или двойственные задачи. Сделав вывод можно говорить о паре двойственных задач линейного программирования.
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования , состоящей, как мы уже знаем, в нахождении максимального значения функции :
F=c 1 x 1 +c 2 x 2 +…c n x n
при условиях

Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:
1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной на минимум.
2. Матрица

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

в двойственной задаче получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов – строками).
3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче.
4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи.
5. Если переменная x j исходной задачи может принимать только лишь положительные значения, то j -е условие в системе двойственной задачи является неравенством вида «>». Если же переменная x j может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i – соотношение в системе исходной задачи является неравенством, то i -я переменная двойственной задачи . В противном случае переменная у j может принимать как положительные, так и отрицательные значения.
Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения прямой задачи и соотношения двойственной задачи являются неравенствами вида « «. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.
Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной. Решение двойственной задачи может быть получено из решения исходной и наоборот. Связующим фактом этих двух задач являются коэффициенты C j функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты B i системы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограничений двойственной задачи.
Рассмотрим задачу использования ресурсов. У предприятия есть t видов ресурсов в количестве b i (i=1, 2,…, m) единиц, из которых выпускается n видов продукции. На изготовление 1 ед. i-й продукции тратится a ij ед. t-гo ресурса, ее стоимость составляет C j ед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за x j (j=1,2,…, n) количество ед. j-й продукций и составляет максимальное значение линейной функции
Z=C 1 x 1 +C 2 x 2 + … +C n x n

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

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

Система ограничений исходной задачи в несимметричных двойственных задачах определяется как равенство. Двойственная же задача задается, как неравенство, причем переменные могут быть и отрицательными. Что бы проще понимать постановку задачи будем интерпретировать ее в матричной форме.
Сформулируем двойственную задачу. Необходимо определить матрицу-строку Y=(y 1 , y 2 ,…, y m), которая максимизирует линейную функцию f=YA 0 и удовлетворяет ограничениям
YA>С (1.1)
Сформулируем исходную задачу. Определить матрицу-столбец X=(x 1 , x 2 ,…, x n), которая минимизирует линейную функцию Z=СХ и. удовлетворяет ограничениям
AX=A0,Х>0 (1.2)
Как в исходной так и в двойственной задачах А=(a ij) – матрица коэффициентов системы ограничений, A 0 =(b 1 , b 2 ,…, b m) – матрица-столбец, C=(c 1 , c 2 ,…, c n) – матрица-строка. Теорема двойственности устанавливает связь между оптимальными планами пары двойственных задач.
Теорема двойственности гласит: если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем для экстремальных значений линейных функций выполняется соотношение minZ =maxf. Если линейная функция одной из задач не ограничена, то другая не имеет решения
Доказательство.
Будем считать, что исходная задача имеет оптимальный план. План определен симплексным методом. Можно считать, что конечный базис состоит из т первых векторов A 1 , A 2 ,…, A m .
Будем считать, что D является матрицей, составленной из компонент векторов конечного базиса A 1 , A 2 ., A m Приведенная выше таблица состоит из коэффициентов разложения векторов A 1 , A 2 ,…, A n исходной системы по векторам базиса. В этой таблице каждому вектору A j соответствует вектор X j .
Используя соотношения (1.3) и (1.4), получаем:
(1.5) A=D, D -1 A=
(1.6) A 0 =DX*; D -1 A 0 =X
(1.7) min Z= C*X*,
(1.8) = C* – C > 0,
где С=(C 1 , C 2 ,…, C m), С=(C 1 , C 2 ,…, C m , C m +1 ,…, C n), a=(CX 1 –C 1 ; СХ 2 – С 2, …, CX n –C n)=(Z 1 –С; Z 2 -C 2 ;…, Z n –C n) – вектор, компоненты которого неположительны, так как они совпадают с Z j –C j >0, соответствующими оптимальному плану.
Оптимальный план исходной задачи имеет вид X=D -1 А 0 , поэтому оптимальный план двойственной задачи ищем в виде
(1.9) Y = C*D -1
Покажем, что Y* действительно план двойственной задачи. Для этого ограничения (1.2) запишем в виде неравенства YA-С>0, в левую часть которого подставим Y*. Тогда на основании (1.9), (1.5) и (1.8) получим
YА–С=С*D -1 А–С=С-С>0, откуда находим Y*A>С
Так как Y* удовлетворяет ограничениям (1.2), то это и есть план двойственной задачи. При этом плане значение линейной функции двойственной задачи f(Y)=Y*A 0. Учитывая соотношения (1.9), (1.6) и (1.7), имеем
(1.10) f (Y) = Y*A 0 =C * D -1 A 0 = C*X = minZ(X)
Таким образом, значение линейной функции двойственной задачи от Y численно равно минимальному значению линейной функции исходной задачи
Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) – на любой план X исходной задачи: YAX=YA 0 =f(Y), YAX>СХ=Z(X), отсюда следует, что для любых планов Х и Y выполняется неравенство
(1.11) f(Y)>Z(X)
Этим же соотношением связаны и экстремальные значения maxf(Y)>minZ(Х). Из последнего неравенства заключаем, что максимальное значение линейной функции достигается только в случае, если maxf(Y)=minZ(X), но это значение f(Y) достигает при плане Y, следовательно, план Y – оптимальный план двойственной задачи.
Аналогично можно доказать, что если двойственная задача имеет решение, то исходная также обладает решением и имеет место соотношение maxf(Y)=minZ(X)
Для доказательства второй части теоремы допустим, что линейная функция исходной задачи не ограничена снизу. Тогда из (1.11) следует, что f(Y) – Y. Это выражение лишено смысла, следовательно, двойственная задача не имеет решений.
Аналогично предположим, что линейная функция двойственной задачи не ограничена сверху. Тогда из (1.11) получаем, что Z(X)+Y. Это выражение также лишено смысла, поэтому исходная задача не имеет решений.
Доказанная теорема позволяет при решении одной из двойственных задач находить оптимальный план другой. Здесь матрица-строка С = (0; 1; 0; –1; – 3, 0), матрица-столбец
1 1 2 0 -1 1 0
A 0 = 2 A = 0 -4 1 2 -1 0
3 0 3 0 0 1 1
1 0 0
2 -4 3
A «’ = 0 1 0
-1 2 0
1 -1 0
0 0 1
Двойственная задача. Найти максимальное значение линейной функции f=y 1 +2y 2 +5y 3 при ограничениях
y 1 > 0
2y 1 – 4y 2 + 3y 3 > 1,
y 2 > 0,
(-y 1) + 2y 2 >(-1),
y 1 – y 2 + y 3 = -3, y 3 > 0
Оптимальный план исходной задачи X = (0; 1/3; 0; 11/3; 4; 0), при котором получим Z min = -46/3. Используя эту итерацию, найдем оптимальный план двойственной задачи. Согласно теореме двойственности оптимальный план двойственной задачи находится из соотношения Y= C*D -1 , где матрица D -1 - матрица, обратная матрице, составленной из компонент векторов, входящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A 5, A 4, A 2 ; значит,
1 -1 2
D = (A 5, A 4, A 2) = -1 2 -4
1 0 3
Обратная матрица D -1 образована из коэффициентов, стоящих в столбцах A 1 , A 3 , A 6 четвертой итерации:
2 1 0
D -1 = -1/3 1/3 2/3
-2/3 -1/3 1/3
Из этой же итерации следует С = (–3; –1; 1). Таким образом
2 1 0
Y=С*D -1 =(-3; – 1; 1) -1/3 1/3 2/3
-2/3 1/3 1/3
Y=(-19/3; – 11/3; – 1/3),
т.е. y i =С*Х i , где Х i – коэффициенты разложения последней итерации, стоящие в столбцах векторов первоначального единичного базиса.
Итак, i-ю двойственную переменную можно получить из значения оценки (m+1) – й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный базис, если к ней прибавить соответствующее значение коэффициента линейной функции:
у 1 =–19/3+0=–19/3; y 2 =-11/3+0=-11/3; у 3 =-1/3+0=-1/3
При этом плане maxf=-46/3

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

Разновидностью двойственных задач линейного, программирования являются двойственные симметричные задачи, в которых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.
Исходная задача. Найти матрицу-столбец Х=(x 1 , x 2 ,…, x n), которая удовлетворяет системе ограничений
(1.12). АХ>А 0 , Х>0 и минимизирует линейную функцию Z=СХ
Систему неравенств с помощью дополнительных переменных можно преобразовать в систему уравнений, поэтому всякую пару симметричных двойственных задач можно преобразовать в пару несимметричных, для которых теорема двойственности уже доказана.
Используя симметричность, можно выбрать задачу, более удобную для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления.
Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду. Для этого второе неравенство следует умножить на -1.
1.3 Виды математических моделей двойственных задач
Основываясь на рассмотренных несимметричных и симметричных двойственных задач отметим, что пары двойственных задач математических моделей могут быть представлены следующим образом:
· Симметричные задачи
(1) Исходная задача Двойственная задача
Z min =CX; f max =Y>A 0 ;
AX=A 0 ; YA=С
X>0 Y>0
(2) Исходная задача Двойственная задача
Z max =CX; f min =YA 0;
AX=A 0 ; YA=С
X>0 Y>0
· Несимметричные задачи
(3) Исходная задача Двойственная задача
Z min =CX; f max =YA 0 ;
AX=A 0 ; YA=С
X>0
(4) Исходная задача Двойственная задача
Z max =CX; f min =YA 0 ;
AX=A 0 ; YA=С
X>0
Поэтому до того, как сформулировать двойственную задачу для данной исходной, необходимо систему ограничений исходной задачи преобразовать должным образом.

1.4 Двойственный симплексный метод

Для получения решения исходной задачи можно перейти к двойственной. А используя оценки ее оптимального плана, можно определить оптимальное решение исходной задачи.
Если рассмотреть первую симплексную таблицу с единичным дополнительным базисом, тогда переход к двойственной задаче не обязателен. Это связано с тем, что в столбцах определена исходная задача, а в строках – двойственная.
b i являются оценками плана двойственной задачи. С j являются оценками плана исходной задачи.
Найдем решение двойственной задачи по симплексной таблице. В симплексной таблице прописана исходная задача. Также определим оптимальный план двойственной задачи. Также найдем и оптимальный план исходной задачи.
Такой метод принято называть двойственным симплексным методом.
Допустим нужно определить исходную задачу линейного программирования, которая поставлена в общем виде: минимизировать функцию Z=СХ при АХ=A 0 , Х>0. Значит в двойственной задаче следует максимизировать функцию f=YA 0 при YA>С. Пусть определен следующий базис D=(A 1 , А 2 ,…, А i ,…, А m), причем в нем хотя бы одна из компонент вектора Х=D -1 A 0 =(x 1 , x 2 ,…, x i ,…, x m) отрицательная. Для всех векторов A j используется следующее соотношение Z j –C j >0 (i=1,2,…, n).
Пользуясь теоремой двойственности, Y=С баз D -1 является планом двойственной задачи. Этот план не оптимальный. Потому что оценки оптимального плана двойственной задачи должны быть неотрицательными и выбранный базис X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны.
Поэтому, следует исключить из базиса исходной задачи вектор А i , который соответствует компоненте x i <0. Данный вектор относится к отрицательной оценке, его необходимо включить в базис двойственной задачи.
Просматриваем i-ю строку для выбора вектора, включаемого в базис исходной задачи. Т.е. если строка не имеет x ij <0, тогда линейная функция двойственной задачи не ограничена на многограннике решений. Поэтому нет решений исходной задачи.
В противном случае для столбцов, имеющих отрицательные значения, определяем q 0j =min(x i /x ij)>0. Также находим вектор, который соответствует minq 0j (Z j –C j) при решении исходной задачи на максимум, а также maxq 0j (Z j –C j) при значении исходной задачи на минимум.
Найденный вектор включаем в базис исходной задачи. Направляющей строкой определяется вектор, который надо убрать из базиса исходной задачи.

Допустим, что q 0j =min(x i /x ij)=0, т.е. x i =0, тогда x ij выбирается как разрешающий элемент, но лишь тогда, когда x ij >0.
Данный подход к решению задачи не приводит к росту количества отрицательных компонент вектора X. Пока не будет получено Х>0, процесс не прекращается.
Определяя оптимальный план двойственной задачи, находим и оптимальный план исходной задачи.
Используя при решении, алгоритм двойственного симплексного метода условие Z j –C j >0 допускается не учитывать, пока не будут исключены все х i <0.
Обычным симплексным методом определяется оптимальный план. Этот метод обычно используется при условии, что все х i <0. Чтобы перейти к плану исходной, задачи за одну итерацию надо определить q 0j =max(x i /x ij)>0.
Задачи линейного программирования можно решать двойственным симплексным методом. Системы ограничений в задачах при положительном базисе имеют свободные члены любого знака. Двойственный симплексный метод позволяет значительно уменьшить размеры симплексной таблицы и количество преобразований системы ограничений.

2 . Разработка программы
2.1 Постановка задачи
Необходимо спланировать работу швейной мастерской на некоторый период. Установлен перечень выпускаемой продукции, известна рыночная цена каждого продукта. Для производства продукции используются ресурсы: материал , нитки, пуговицы, труд закройщиков, швей-мотористок и т.д. Установлен полный перечень этих ресурсов и общее количество каждого ресурса, которое может быть израсходовано в плановом периоде. Известен расход каждого ресурса на единицу каждого продукта. Необходимо определить, сколько каждой продукции нужно производить, чтобы суммарная рыночная цена всей продукции (выпуск, выручка) была наибольшей.
Введем следующие обозначения:
i =1,…, m - номера (индексы) используемых ресурсов;
- запас i -го ресурса, т.е. допустимый расход i -го ресурса в плановом периоде; другое название - ограничение по ресурсу i ;
j =1,…, n - номера (индексы) продуктов;
- рыночная цена j -го продукта;
- расход i -го ресурса на производство единицы j -го продукта;
- плановый объем производства j -го продукта, величина неизвестная, ее нужно найти в процессе решения задачи. Исходные данные задачи запишем в виде матрицы .


Рис. 2
Каждая строка матрицы соответствует одному ресурсу, каждый столбец – одному продукту. Справа от каждой строки записана величина ограничения по ресурсу (b 1 ,…, b i ,…, b m ); внизу каждого столбца - цена продуктов (с 1 ,…, с j ,…, с m ).
В каждой клеточке матрицы записаны так называемые технологические коэффициенты a ij , показывающие расход i -го ресурса на производство единицы j -го продукта.
Запишем конкретный числовой пример

Рис. 3

2.2 Построение математической модели
Теперь приступим к созданию математической модели, т.е. к математической записи задачи.
Целевая функция:

Ограничения:

x 1 ³ 0;
x 2 ³ 0;
x 3 ³ 0.
2.3 Описание решения данной задачи
Решим поставленную выше задачу с применением EXCEL.

Содержание ячеек:
B1:D1 – имена продуктов (технологических способов);
A2:A4 – имена ресурсов;
B2:D4 – технологические коэффициенты (расход ресурсов при единичных интенсивностях технологических способов);
B6:D6 – цены продуктов;
B8:D8 – переменные;
F2:F4 – запас ресурсов;
G2:G4 – плановые расходы ресурсов, получаются в результате решения;
G6 – значение целевой функции, получается в результате решения.
Формулы для вычислений:
G2=СУММПРОИЗВ (B$8:D$8; B2:D2);
G3:G4 – копируются из G2;
G6=СУММПРОИЗВ (B8:D8; B6:D6).
Запишем формулы в ячейки G2:G4. Установить курсор на G2. На панели инструментов выбрать значок формул (f ). Появятся два окна. В окне «категория» выбрать «математические», затем в окне «функция» выбрать «СУММПРОИЗВ». Появится окно «СУММПРОИЗВ». В нем нужно указать, где располагаются операнды. Первый операнд – строка B$8:D$8, второй операнд – стока B2:D2. В ячейки G3:G4 формулу скопировать из G2. Аналогичным образом записать формулу целевой функции в ячейку G6. Теперь нужно указать остальные условия решения задачи. Установить курсор на ячейку целевой функции G6. В главном меню выбрать «сервис», а потом «поиск решения». Появится окно, в котором нужно указать:
1. Целевая ячейка – G6;
2. Включить кнопку «максимальное значение»;
3. Указать изменяемые ячейки (расположение переменных) – B8:D8;
4. Записать ограничения. Их можно записать прямо в этом же окне, но лучше выбрать «добавить» и в появившемся окне «добавить» последовательно записать ограничения:
G2:G4 F2:F4 – плановый расход ресурсов меньше их запаса.
Теперь электронная модель сформирована и можно решать задачу. Для этого нужно вернуться в окно «поиск решения» и нажать «выполнить». Если электронная модель сформирована правильно, то будет получено сообщение, что задача решена. Результат решения находится на листе EXCEL и в трех отчетах: Результаты, Устойчивость , Пределы .

Рис. 4.1.4
Основные результаты видны в таблице (рис. 4.1.4.). По сравнению с условиями задачи, показанными на рис. 4.1.3., появились данные:
1. Значение целевой функции в ячейке G6 = 15880;
2. Значения переменных в ячейках B8:D8: х 1 = 86, х 2 = 0, х 3 = 268; это значит, что 1-й продукт должен производиться в объеме 86 единиц, 2-й – 0, а 3-й – 286.
3. Плановый расход ресурсов в ячейках G2:G4: расход 1-го ресурса = 271,6, расход 2-го ресурса = 310, расход 3-го ресурса = 2200.
Как видно 1-й ресурс недоиспользован, а 2-й и 3-й израсходованы полностью.
Кроме результатов в электронной таблице EXCEL готовит три отчета: Результаты, Устойчивость, Пределы. Отчет по результатам изображен на рис 4.1.5, где изображены три таблицы.
Отчет по результатам
Целевая ячейка (максимум)
$G$6 Цены ЦФ 15880
Изменяемые Ячейки

Ячейка Имя Исходно Результат

$B$8 Перем Пр1 0 86

$C$8 Перем Пр2 0 0

$D$8 Перем Пр3 0 268

Ограничения

Ячейка Имя Значение Формула Статус Разница

$G$2 Рес 1 Расход 271,6 $G$2 $F$2 не связан 228,4

$G$3 Рес 2 Расход 310 $G$3 $F$3 связанное 0

$G$4 Рес 3 Расход 2200 $G$4 $F$4 связанное 0

$B$8 Перем Пр1 86 $B$8 0 не связан 86

$C$8 Перем Пр2 0 $C$8 0 связанное 0

$D$8 Перем Пр3 268 $D$8 0 не связан 268

Рис. 4.1.5
1-я таблица – целевая ячейка – дает значение целевой функции, которая уже имеется в таблице EXCEL, значит, эти данные избыточны.
2-я таблица – изменяемые ячейки – дает значение переменных, которые уже имеются в таблице EXCEL, эти данные тоже избыточны.
3-я таблица – ограничения – дает оценку ограничений. Колонка «значение» дает значения планового расхода ресурсов и переменных – эти данные имеются в таблице EXCEL и здесь избыточны. Столбец «статус» значением «связанное» отмечает ограничения (не больше или не меньше), которые в результате решения превратились в строгие равенства, прочие ограничения имеют статус «несвязанные». Столбец «разница» показывает, на какую величину ограничения отклонились от строгого равенства. Так, например, ограничение 1-го ресурса 500, плановое значение 271,6, разница = 500 – 271,6 = 228,4.
Отчет по устойчивости изображен на рис. 4.1.6. Он состоит из двух таблиц.
Отчет по устойчивости
Изменяемые ячейки

Ячейка Имя Результат Норир. Значение градиент

$B$8 Перем Пр1 86 0

$C$8 Перем Пр2 0 -22,8

$D$8 Перем Пр3 268 0

Ограничения

Ячейка Имя Результат. Лагранжа значение Множитель

$G$2 Рес 1 Расход 271,6 0

$G$3 Рес 2 Расход 310 20

$G$4 Рес 3 Расход 2200 4,4

Рис. 4.1.6
Таблица «изменяемые ячейки» показывает значения переменных, которые уже имеются в таблице EXCEL. Столбец «нормируемый градиент» показывает, как влияет увеличение переменных на единицу на величину целевой функции. Таблица «ограничения» содержит важную информацию в столбце «Лагранжа множители». Эти величины в литературе имеют различные названия: объективно обусловленные оценки (О.О.О.) по Л. Канторовичу, двойственные оценки по Д. Данцигу, оптимальные цены, теневые цены и другие. В дальнейшем будем называть их наиболее распространенным именем – двойственные оценки и обозначать – v i , где i – номер ограничения. В данном примере v 1 = 0, v 2 = 20,0, v 3 = 4,4. Отчет по пределам показан на рис. 4.1.7.
Отчет по пределам

Ячейка Изменяемое Значение имя	Нижний Целевой предел результат	Нижний Целевой предел результат
$B$8 Перем Пр1 86	0 10720	86 15880
$C$8 Перем Пр2 0	0 15880	0 15880
$D$8 Перем Пр3 268	0 5160	268 15880

Рис. 4.1.7.
В этом отчете уже в третий раз дается значение целевой функции 15880, в пятый раз значение переменных (х 1 = 86, х 2 = 0, х 3 = 268). Нижний предел для всех переменных = 0, так, установлены ограничения по переменным. Верхний предел равен соответственно 86, 0 и 268, так устанавливают ограничения по ресурсам . Целевой результат показывает значение целевой функции при соответствующих значениях переменных. Если х 1 = 0, то ЦФ = 10720 и т.д.
Запишем математическую модель рассмотренной задачи в общем виде:

Пусть:
В- бюджет, т.е. количество денег, которое можно израсходовать на приобретение ресурсов для производства продукции, а s i – рыночная цена i -го ресурса. Тогда единственное ограничение по ресурсам будет выглядеть следующим образом:
.
Смысл этого ограничения - нельзя израсходовать ресурсов на сумму больше, чем В .
Здесь: - расход i -го ресурса в натуральном выражении по j -му технологическому способу;
- расход i -го ресурса в натуральном выражении по всем способам;
- суммарная цена i -го ресурса, израсходованного по всем способам;
- суммарная цена всех ресурсов по всем технологическим способам.
Решим задачу на максимум продукции с ограничением по бюджету . За основу возьмем электронную модель на рис. 4.1.3. и дополним ценами ресурсов s i и бюджетом В (рис. 4.1.8)

Рис. 4.1.8

Дополнительные величины:
H2:H4 – цены ресурсов (задаются);
I2:I4 – издержки (вычисляются);
I2 = G2*H2;
I3:I4 – копируется из I2;
H6 = 5000 – бюджет (задается);
I6 – издержки всего (вычисляются);
I6 = СУММ (I2:I4).
Ограничения:
B8:D8 0 – неотрицательности переменных;
I6 H6 – совокупные издержки не больше бюджета .
Будет получено решение
x 1 = 0; x 2 = 0; x 3 = 409,84.
v = 3,08 – двойственная оценка ограничения по бюджету – увеличение бюджета на единицу увеличивает валовой продукт на 3,28.
Если ограничения по ресурсам в модели имеют смысл и не больше () и не меньше (), причем все величины () не отрицательные, то в общем случае вывод о существовании или отсутствии допустимого плана сделать нельзя. Все зависит от конкретных значений величин и . Возможен случай , когда для некоторого k -го ресурса установлено такое ограничение , что оно не может быть выполнено из-за других ограничений. Тогда нет ни одного допустимого плана.

Заключение

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

Список используемой литературы

1. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование . «Наука», 1980 г.

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

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

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

Рассмотрим стандартную задачу ЛП с n переменными и m ограничениями в форме неравенств

f(x) = c1 x1 + c2 x2 + …+ cn xnmax,11 x1 + a12 x2 + … + a1n xn b1,21 x1 + a22 x2 + … + a2n xn b2,

…………………………………….……m1 x1 + am2 x2 + … + amn xn bm,j 0, j = 1, 2, …, n.

Двойственной к ней называется задача ЛП следующего вида:

g(y) = b1 y1+ b2 y2 + …+ bm ym??min11 y1 + a21 y2 + … + am1 ym c112 y1 + a22 y2 + … + am2 ym c2

………………………….………………1n y1 + a2n y2 + … + amn ym cn

yi 0, i = 1, 2, …, m.

Выписывая матрицы условий для прямой и двойственной задачи

видим, что Адв = АTпр.

Следовательно, пара двойственных задач может быть записана в матричной форме:

< c, x > max; Ax ?b, x ?0.g(y) = < b, y > min; ATy ?с, y ?0.

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

Пара двойственных задач, в которых прямая задача - стандартная, называется симметричной парой двойственных задач.

Правила построения двойственной задачи к стандартной задаче ЛП.

·Число переменных двойственной задачи равно числу основных ограничений прямой задачи и наоборот.

·Если прямая задача есть задача на max при ограничениях «», то двойственная задача - задача на min при ограничениях «».

·Правые части ограничений прямой задачи - числа bi - становятся коэффициентами целевой функции двойственной задачи.

·Коэффициенты целевой функции прямой задачи - числа cj - становятся правыми частями ограничений двойственной задачи ЛП.

·j - й столбец матрицы условий прямой задачи превращается в j - ю строку матрицы условий двойственной задачи.

·Переменные прямой и двойственной задачи неотрицательны.

Пример. Рассмотрим стандартную задачу ЛП с двумя переменными, тремя ограничениями в форме неравенств и условиями неотрицательности.

f(x)=2x1-4x2max;1+ 3x2 8,

3x1+ x2 -7,

2x1 - 5x2 10,

x1, x2 0.

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

g(y)=8 y1-7y2+10 y3 min;1 - 3 y2+ 2 y3 2,

3y1+ y2 -5 y3 -4,1, y2 0.

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

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

g(y)= -8y1+7y2-10y3 max;1+ 3y2 - 2y3 -2,

3y1 - y2+ 5y3 4,1, y2 0.

Построим к ней двойственную задачу по правилам 1-6, обозначая двойственные переменные через x1, x2.

f(x)= - 2x1+ 4 x2 min;

x1 - 3x2 -8,

x1 - x2 7,

2x1+ 5x2 -10,

x1, x2 0.

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

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

f(x) = < c, x > min; b, x 0,

то двойственной к ней будет задача

g(y) = < b, y > max;Ty с, y 0.

3. Экономический смысл двойственной задачи

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

Предприятие после выпуска основной продукции имеет излишки ресурсов двух типов: R1 - 10 единиц, R2 - 8 единиц. Существует два способа распорядиться этими ресурсами:

·организовать из них выпуск 3 новых видов продукции: P1, P2, P3.

·продать их.

Рассмотрим оба способа.

Исходные данные приведены в таблице:

РесурсыРасход ресурса на единицу продукцииЗапас ресурсовP1P2P3R112110R22138Удельная прибыль$6$4$4

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

Пусть xj - план выпуска продукции Pj.

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

f(x)=6x1+4x2+4x3 max;

Ограничения по ресурсам:

1+2x2+x3 10,

x1+x2+3x3 8,j 0, j=1,2,3.

Получили стандартную задачу ЛП.

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

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

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

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

Пусть y1 - цена одной единицы ресурса R1, y2 - цена одной единицы ресурса R2.

Интерес покупателя будет выражаться целевой функцией, равной суммарной стоимости приобретаемых ресурсов

g(y) = 10 y1+ 8 y2 min.

Интерес продавца будет описываться ограничениями:

y1+2y2 6,

y1+y2 4,

y1+3y2 4,

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

Присоединяя естественные условия неотрицательности цен:

y1, y2, y3 0,

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

Таким образом, симметричной паре двойственных задач можно придать определенный экономический смысл.

Прямая задача Определить такой план выпуска продукции x =(x1, x2,…, xn), используя ограниченные запасы ресурсов, при котором прибыль от реализации продукции будет максимальной.Двойственная задача Установить такой набор цен ресурсов y =(y1, y2,…, ym), при которых стоимость ресурсов, затраченных на выпуск единицы продукции будет не ниже прибыли от ее реализации, но при этом суммарная стоимость затрат будет минимальна.

Цены ресурсов y1, y2,…, ym носят названия теневых, неявных или внутренних цен. Эти названия отличают их от «внешних», заранее известных цен с1, с2,…, сn на выпускаемую продукцию. Цены y1, y2,…, ym на ресурсы определяются из решения двойственной задачи и характеризуют стоимость затрат на выпуск конкретных видов продукции, поэтому их часто называют двойственными оценками ресурсов.

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

Пусть теперь исходная задача - каноническая, то есть имеет вид:

f(x) = < c, x > max;(4.1)Ax = b,(4.2)x 0.(4.3)

Здесь x = (x1,…, xn), c = (c1,…, cn), b = (b1,…, bm), так что число уравнений в системе (4.2) равно m.

Для построения двойственной задачи к задаче (4.1) - (4.3) сведем ее к стандартной форме.

Каждое равенство в (4.2) заменим парой неравенств

или, что то же самое

Получим стандартную задачу ЛП с 2m ограничениями.

f(x)=< c, x > max;b,

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

Для этого введем двойственные переменные:

u = (u1,…, um) 0,

v = (v1,…, vm) 0.

Заметим, что, так как в прямой задаче ЛП было 2m ограничений, то в двойственной будет 2m переменных.

Целевая функция двойственной задачи примет вид:

g (u, v)=< b, u > + < - b, v > min,

а ограничения запишутся так:

ATu - ATv c,

Перепишем эту задачу более компактно:

g (u, v)=< b, u - v> min,T (u - v) c, 0, v 0.

Введем новый вектор двойственных переменных y = (y1, y2,…, ym) с координатами yi = ui - vi. Поскольку разность неотрицательных чисел может быть и отрицательной (например, 2-5= -3), то двойственные переменные yi не имеют ограничений по знаку.

Таким образом, двойственная задача к канонической будет иметь вид:

g(y) = < b, y > min;Ty 0,

Переменная любого знака !

5. Таблицы для построения двойственной задачи

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

Прямая задача линейного программированияДвойственная задача линейного программированияЦелевая функция< c, x > max< b, y > minЦелевая функцияТип i-го ограниченияi biyi 0Знак i-й переменнойi biyi 0i = biyij 0j cjТип j-го ограниченияxj 0j cjxj ? свободная переменнаяj = cj

Прямая задача линейного ПрограммированияДвойственная задача линейного программированияЦелевая функция< c, x > min< b, y > ?maxЦелевая функцияТип i-го ограниченияi biyi ?0Знак i-ой переменнойi biyi 0i = biyi - любого знакаЗнак j-ой переменнойxj 0j cjТип j-го ограниченияxj 0j cjxj ? свободная переменнаяj = cj

Задание . Составить двойственные задачи к следующим задачам ЛП.

1. f(x) = 2x1 - 2x2+ 3x3 - 6x4 max

x1+ x2 - 2x3 + x4 = -101 - 5x2 - x3 + 2x4 = 35j 0, j=1,2,3,4

F(x) = - x1 - 3x2+ x3 min1+ x2+ x3 61 - x2+ x3 8j 0, j=1,2,3

F(x) = 9x1+ 2x2+ 3x3+ 2x4 min

x1+ x2+ 2x3 = 2

x1+ x2 - x3 - 4x4 = -1j 0, j=1,2,3,4

F(x) = x1 - 2x2 max1+ x2 4

x1 - x2 8

x1+ x2 0

x2 0

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

Рассмотрим симметричную пару двойственных задач:

f(x) = < c, x > max;(4.4)g(y) = < b, y > min;(4.7)Ax b(4.5)ATy c(4.8)x 0(4.6)(y 0(4.9)x = (x1,…, xn)y = (y1,…, ym)

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

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

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

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

(x*) = g(x*) или < c, x*> = < b, y*>.

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

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

Утверждение второй части теоремы легко доказывается от противного. Предположим, что в прямой задаче (4.4) - (4.6) целевая функция не ограничена сверху на множестве X, то есть max f(x) ¥ , xÎ X, но множество планов Y двойственной задачи не пусто - существует хотя бы одна точка yÎ Y. Тогда в силу основного неравенства теории двойственности: maxf(x) g(y), что противоречит неограниченности целевой функции прямой задачи. Таким образом, неограниченность сверху целевой функции исходной задачи влечет за собой несовместность ограничений двойственной задачи. Аналогично доказывается, что из неограниченности снизу двойственной целевой функции g(y) на множестве Y, следует пустота множества планов X прямой задачи.

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

Первая теорема двойственности позволяет исследовать любой заданный план на оптимальность.

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

Теорема 2.Планы x* = (x1*,…, xn*) и y* = (y1*,…, ym*) - оптимальны (каждый в своей задаче), тогда и только тогда, когда выполняются условия:

< Ax* - b, y* > = 0,(4.15)

< ATy* - c, x* > = 0,(4.16)

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

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

Прямая задача ЛПДвойственная задача ЛПf(x) = < c, x > maxg(y) = < b, y > min(4.17) Ax = bATy cx 0

Необходимость.

Пусть x*, y* - оптимальные планы прямой и двойственной задач соответственно. Покажем, что условия (4.15), (4.16) выполняются.

Заметим, что при x = x* из (4.17) следует (4.15). Так как Ax* - b= 0, значит и скалярное произведение * - b, y* > тоже равно нулю. По первой теореме двойственности для оптимальных планов x*, y* выполняется равенство: < c, x* > = < b, y* >. Подставим сюда выражение для b из (14): b = Ax*. Используя правило перекидки, получим:

< c, x* > = < Ax*, y* >= < x*, ATy* > = < ATy*, x* >,

откуда следует < ATy* - c, x* > = 0. А это не что иное как условие (4.16)

Достаточность.

Пусть для допустимых планов x*, y* справедливо (4.15), (4.16). Докажем их оптимальность.

Условия (4.15) и (4.16) можно записать следующим образом

< Ax*, y* > = < b, y* >, < ATy*, x* > = < c, x* >.

По правилу перекидки < Ax*, y* > = < ATy*, x* >. Так как левые части условий равны, то равны и правые части:

< b, y* > = < c, x* >,

отсюда по свойству 2 заключаем, что x* - оптимальный план прямой задачи,* - оптимальный план двойственной задачи. Что и требовалось доказать.

. Условия равновесия

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

< Ax* - b, y* > = 0,(4.18)

< ATy* - c, x* > = 0. (4.19)

Прямая задача ЛПДвойственная задача ЛП f(x) = c1 x1 + … + cn xn maxg(y) = b1 y1+ …+ bm ym??minai1 x1 + … + ain xn bi, i =1,…, ma1j y1 + … + amj ym cj, j = 1,…, nxj 0, j = 1,…, nyi 0, i = 1,…, m

Раскрывая скалярные произведения, распишем условия (4.18) и (4.19) более подробно.

å (ai1 x1*+ … + ain xn* - bi) yi* = 0,(4.20)

å (a1j y1*+ … + amj ym* - cj) xj* = 0.(4.21)

В сумме (4.20) каждое слагаемое есть произведение разности левой и правой частей ограничения прямой задачи на соответствующую двойственную переменную. Очевидно, что все слагаемые имеют один и тот же знак «0», так как разности в круглых скобках меньше или равны нулю, а yi 0. Отсюда следует, что сумма (4.20) равна нулю тогда и только тогда, когда каждое слагаемое в ней равно нулю.

(ai1 x1*+ … + ain xn* - bi) yi* = 0, i =1,…, m. (4.22)

двойственность неравенство равновесие линейный

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

(a1j y1*+ … + amj ym* - cj) xj* = 0, j = 1,…, n. (4.23)

Учитывая знаки сомножителей в произведении (4.22), из него можно получить пару условий

Если ai1 x1*+ … + ain xn* < bi, то yi* = 0. (4.22a)

Если yi* > 0, то ai1 x1*+ … + ain xn* = bi. (4.22b)

Аналогично, из (6) следует пара условий

Если a1j y1*+ … + amj ym* > cj, то xj* = 0. (4.23a)

Если xj* > 0, то a1j y1*+ … + amj ym* cj.(4.23b)

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

·если какое-либо ограничение одной задачи на оптимальном плане выполняется как строгое неравенство, то соответствующая координата оптимального плана другой задачи равна нулю (условия (4.22a) и (4.23a)).

·Если какая-либо координата оптимального плана одной задачи положительна, то соответствующее ограничение другой задачи обращается в равенство (условия (4.22b) и (4.23b)).

Эти условия называются условиями дополняющей нежесткости или условиями равновесия.

. Геометрический смысл условий равновесия

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

ai1 x1 + … + ain xn bi(4.24)

называется связным или активным на плане x", если на этом плане оно обращается в равенство

ai1 x1"+ … + ain xn" bi.

Определение 2 . Ограничение (4.24) называется несвязным (неактивным, пассивным) на плане x", если на этом плане оно выполняется как строгое неравенство

ai1 x1"+ … + ain xn" < bi.

Геометрически, ограничение, активное в точке x", проходит через эту точку, а неактивное - не проходит.

На рисунке в точке x" P1 и P3 - активные, связные ограничения; P2 - неактивное ограничение. В точке x» P1, P2 - активные ограничения; P3 - неактивное ограничение.

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

На оптимальных планах двойственных задач

·неактивному ограничению одной задачи соответствует нулевая переменная плана другой задачи.

·положительной переменной оптимального плана одной задачи соответствует активное ограничение другой задачи.

Литература

1. Айвазян С.А., Иванова С.С. Эконометрика. Краткий курс: учеб. пособие / С.А. Айвазян, С.С. Иванова. - М.: Маркет ДС, 2007. - 104 с.

Бородич С.А. Вводный курс эконометрики: Учебное пособие. - Мн.: БГУ, 2009. - 354 с.

Бывшев В.А. Эконометрика: учеб. пособие / В.А. Бывшев. - М.: Финансы и статистика, 2008. - 480 с.

Доугерти Кристофер. Введение в эконометрику: Учебник для экон. спец. вузов / Пер. с англ. Е.Н. Лукаш и др. - М.: ИНФРА-М, 2007. - 402 с.

Дубров А.М., Мхитарян В.С., Трошин Л.И. Многомерные статистические методы: Учебник. - М.: Финансы и статистика, 2009. - 352 с.

Дуброва Т.А. Прогнозирование социально-экономических процессов. Статистические методы и модели: учеб. пособие / Т.А. Дуброва. - М.: Маркет ДС, 2007. - 192 с.

Магнус Я.Р., Катышев П.К., Пересецкий А.А. Эконометрика. Начальный курс: Учебник. -3-е изд., перераб. и доп. - М.: Дело, 2008. - 400 с.

Методы математической статистики в обработке экономической информации: учеб. пособие / Т.Т. Цымбаленко, А.Н. Баудаков, О.С. Цымбаленко и др.; под ред. проф. Т.Т. Цымбаленко. - М.: Финансы и статистика; Ставрополь: АРГУС, 2007. - 200 с.

Палий И.А. Прикладная статистика: Учебное пособие. - М.: Издательско-торговая корпорация «Дашков и К», 2008. - 224 с.

Порядина О.В. Эконометрическое моделирование линейных уравнений регрессии: Учебное пособие. - Йошкар-Ола: МарГТУ, 2006. - 92 с.

Практикум по эконометрике: Учеб. пособие / И.И. Елисеева, С.В. Курышева, Н.М. Гордеенко и др.; Под ред. И.И. Елисеевой. - 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2007. - 344 с.

Прикладная статистика. Основы эконометрики: Учебник для вузов: В 2 т. 2-у изд., испр. - Т. 2: Айвазян С.А. Основы эконометрики. - М.: ЮНИТИ-ДАНА, 2009. - 432 с.

Симчера В.М. Методы многомерного анализа статистических данных: учеб. пособие. - М.: Финансы и статистика, 2008. - 400 с.

Чураков Е.П. Прогнозирование эконометрических временных рядов: учеб. пособие / Е.П. Чураков. - М.: Финансы и статистика, 2008. - 208 с.

Эконометрика: учеб. / под ред. д-ра экон. наук, проф. В.С. Мхитаряна. - М.: Проспект, 2008. - 384 с.

Эконометрика: учеб. / под ред. И.И. Елисеевой. - М.: Проспект, 2009. - 288 с.

Эконометрика: Учебник/И.И. Елисеева, С.В. Курышева, Т.В. Костеева и др., Под ред. И.И. Елисеевой. - 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2006. - 576 с.

Репетиторство

Нужна помощь по изучению какой-либы темы?

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

Можно сформулировать правила получения двойственной задачи из задачи исходной.

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

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

3. В исходной ЗЛП все функциональные ограничения - неравенства вида “≤”, а в задаче, двойственной ей, - неравенства вида “≥”.

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

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.

6. Условие неотрицательности переменных сохраняется в обеих задачах.

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

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

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

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

(2.8)

Компоненты оптимального решения двойственной задачи принято называть двойственными оценками . Часто употребляется также термин «объективно обусловленные оценки».

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

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

Формулировка прямой (исходной) задачи:

y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0.

В результате решения получим следующие оптимальные планы:

= (24, 4); = (1/3, 1/3, 0).

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

Перейдем к рассмотрению свойств двойственных оценок.

Свойство 1. Оценки как мера дефицитности ресурсов. Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки , тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.

В нашем примере нулевую оценку получил третий ресурс ( = 0), поэтому он не является дефицитным, т.е., с точки зрения задачи, фонд рабочего времени на участке С не ограничивает производство. Напротив, первый (участок А) и второй (участок В) ресурсы являются дефицитными, причем ограничивают производство в одинаковой степени ( = = 1/3).

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

4ּ24 + 6ּ4 = 120, 2ּ24 + 6ּ4 = 72, 4 < 10.

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

Свойство 2. Оценки как мера влияния ограничений на значение целевой функции. Величина двойственной оценки какого-либо ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на единицу. В связи с этим значение объективно обусловленной оценки иногда называют теневой ценой ресурса . Теневая цена - это стоимость единицы ресурса в оптимальном решении.

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

Для нашего примера увеличение (уменьшение) фонда времени на участке А или В должно приводить к увеличению (уменьшению) максимальной прибыли на $1/3. Соответственно, например, при увеличении фонда времени участка А на 12 н-часов общая прибыль должна увеличиться на $4 (1/3ּ12).

Свойство 3. Оценки как инструмент определения эффективности отдельных хозяйственных решений. С помощью двойственных оценок можно определить выгодность выпуска новых изделий, эффективность новых технологических способов производства. При этом эффективным может считаться тот вариант производства, для которого сумма прибыли, недополученной из-за отвлечения дефицитных ресурсов, будет меньше прибыли получаемой. Разница между этими величинами (Δ j) вычисляется как:

(2.9)

В том случае, если Δ j ≤ 0, вариант производства является выгодным, если Δ j > 0 – вариант невыгоден.

Вернемся к нашему примеру. Пусть предприятие планирует к выпуску новый вид изделий: бейсбольные биты. Для производства одной биты необходимо затратить 3 часа работы на участке А, 4 часа работы на участке В и 1 час работы на участке С. Прибыль, получаемая от продажи одной биты, составляет $3. Выгодно ли предприятию выпускать новую продукцию?

Для ответа на вопрос рассчитаем Δ j по формуле (2.9):

Δ j = 3ּ + 4ּ + 1ּ - 3 = 3ּ1/3 + 4ּ1/3 + 1ּ0 - 3 = -2/3,

Δ j < 0, значит производить бейсбольные биты выгодно.

Свойство 4. Оценки как мера относительной заменяемости ресурсов с точки зрения конечного эффекта. Например, отношение / показывает, сколько единиц k-го ресурса может быть высвобождено при увеличении объема i-го ресурса на единицу, для того чтобы максимум целевой функции остался на прежнем уровне; или наоборот, сколько единиц k-го ресурса необходимо дополнительно ввести при уменьшении на единицу объема i-го ресурса, если мы хотим, чтобы значение целевой функции не изменилось.

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

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

Проиллюстрируем это утверждение примером .

Для производства четырех видов изделий А 1 , А 2 , А 3 и А 4 завод должен использовать три вида сырья I, II и III. Запасы сырья на планируемый период составляют, соответственно, 1000, 600 и 150 единиц.

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

Таблица 2.12 - Исходные данные задачи о четырех видах изделий

Требуется, зная решение данной задачи, решить задачу, двойственную ей.

Сформулируем исходную ЗЛП.