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

Введение
Под двойственной задачей понимается вспомогательная задача линейного программирования , формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных.
Целью курсового проекта является изучить литературу по выбранной теме и научиться применять на практике симплекс – метод для решения прямой и двойственной задачи линейного программирования , а также решить двойственную задачу линейного программирования с помощью программы 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. Если целевая функция 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.

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

Стек МК

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

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

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

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

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

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

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

Вопросы:

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

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

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

На производство 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) должны быть такими, чтобы «теневая» цена всех ресурсов, затраченных на производство единицы продукции каждого вида, была бы не меньше получаемого от ее реализации дохода. Другими словами, стоимость затраченных ресурсов не может быть меньше стоимости окончательного продукта (так как существуют неизбежные издержки).

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

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

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

Таблица 2.12

Составим математическую модель. Пусть количество продукции I, II, III, IV вида соответственно в плане. Тогда количество используемого сырья и его запасы выразятся в неравенствах:

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

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

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

.

I этап. Эта задача специального вида, базис составляют переменные , правые части уравнений неотрицательны, опорный план допустимый. Он соответствует симплекс-таблице (табл.2.13).

Таблица 2.13

свободные базис					правые части
		0,4		0,5
					100
	-3	-5	-4	-5

II этап . Проверим план на оптимальность. Так как в индексной F–строке есть отрицательные элементы, то план не оптимален, переходим к III этапу.

III этап. Улучшение опорного плана. Выберем в качестве разрешающего столбца четвертый, могли выбрать и второй, т.к. в обоих – 5. Выберем в качестве разрешающего элемента 1, т.к. именно на нем достигается минимум отношений . С разрешающим элементом проводим преобразование таблицы по правилам 3.1–3.5 (табл.2.14).

Таблица 2.14

свободные базис					правые части
	4,5	0,4	1,5	-0,5
	-1		-1	-1	200
		-5

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

Пересчитываем еще раз таблицу. Заметим, что пересчет удобно начинать с индексной строки, т.к. если в ней все элементы неотрицательны, то план оптимален, и чтобы его выписать, достаточно пересчитать столбец свободных членов, нет необходимости вычислять «внутренность» таблицы. Результаты запишем в таблицу 2.15.

Таблица 2.15

свободные базис					правые части

План оптимален, т.к. в индексной строке нет отрицательных элементов, выписываем его.

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

Действительно, Т.е. для получения максимальной прибыли в 700 руб., предприятие должно выпускать изделия II вида в количестве 40 штук, IV вида в количестве 100 штук, изделия I, III видов производить невыгодно. При этом напомним смысл дополнительных переменных – это излишки сырья, следовательно, сырье 2–го и 3–го видов будет израсходовано полностью, а сырья 1-го вида останется 334 единицы, т.к. .

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

1. Количество переменных в двойственной задаче равно количеству неравенств в исходной (без учета неравенств неотрицательности).

2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

3. Столбец свободных членов исходной является строкой коэффициентов для целевой функции двойственной и наоборот.

4. Целевая функция в одной задаче максимизируется, в другой минимизируется.

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

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