Российский экономический

Связи прямой и двойственной задач
 
х
1
 
х
2
 
≤
mах 
у
1
0,05 
0,5 
20 
у
2
1,1 
1 
180 
у
3
0,225 
0,25 
32 
v
1
–1 
0 
–90 
v
2
0 
–1 
–30 
≥
0,25 
1,2 
min 
Между прямой и двойственной задачами существует взаимооднозначное 
соответствие. Вид каждой из них строго определен другой. В нашем случае для 
каждого ресурса 
i 
в прямой задаче есть основное ограничение вида (4.13) по его 
использованию, а в двойственной задаче — ограничение вида (4.18) на неотри-
цательность его оценки. Каждая пара таких ограничений прямой и двойствен-
ной задачи называется 
взаимно сопряженными
. 
Для каждого вида продукции 
j 
взаимно cопряженными будут ограниче-
ния по производственной программе вида (4.14) прямой задачи и ограничения 
вида (4.19) на неотрицательность оценки. Аналогично взаимно сопряженными 
будут и пары ограничений видов (4.15) и (4.17). 
Из второй теоремы двойственности следует, что для оптимальных планов 
прямой и двойственной задач в каждой паре взаимно сопряженных ограниче-
ний, если одно из них свободно (выполняется как равенство), то другое закреп-
лено (выполняется как строгое неравенство), и наоборот. 
Обозначим звездочкой значения переменных прямой и двойственной за-
дач в оптимальном плане. Тогда по второй теореме двойственности имеем: 

для каждого 
i
-го ресурса: 
если 
∑
∑
𝑎
𝑖𝑗
𝑠
𝑥
𝑗
𝑠∗
< 𝑏
𝑖
𝑟
𝑗
𝑠=1
𝑛
𝑗=1
,то 
𝑦
𝑖
∗
= 0
, 
(4.20) 
если 
∑
∑
𝑎
𝑖𝑗
𝑠
𝑥
𝑗
𝑠∗
= 𝑏
𝑖
𝑟
𝑗
𝑠=1
𝑛
𝑗=1
, то 
𝑦
𝑖
∗
> 0
; 
(4.21) 

j
-го ограничения по производственной программе: 
если 
∑
𝑥
𝑗
𝑠∗
> 𝑏
𝑗
𝑟
𝑗
𝑠=1
, то 
𝑣
𝑗
∗
= 0,
(4.22) 
если 
∑
𝑥
𝑗
𝑠∗
= 𝑏
𝑗
𝑟
𝑗
𝑠=1
, то 
𝑣
𝑗
∗
> 0
; 
(4.23) 

s
-го технологического способа:
если 
𝑥
𝑗
𝑠∗
= 0
, то 
∑
𝑎
𝑖𝑗
𝑠
𝑦
𝑗
𝑠∗
− 𝑣
𝑗
∗
> 𝑝
𝑗
𝑠
𝑚
𝑖=1
, 
(4.24) 
если 
𝑥
𝑗
𝑠∗
> 0
, то 
∑
𝑎
𝑖𝑗
𝑠
𝑦
𝑗
𝑠∗
− 𝑣
𝑗
∗
= 𝑝
𝑗
𝑠
𝑚
𝑖=1
. 
(4.25) 
66

---

По первой теореме двойственности значения критериев оптимальности 
прямой и двойственной задач в точке оптимума равны, т.е.: 
∑
∑
𝑝
𝑗
𝑠
𝑥
𝑗
𝑠∗
=
𝑟
𝑗
𝑠=1
𝑛
𝑗=1
∑
𝑏
𝑖
𝑦
𝑖
∗
− ∑
𝑏
𝑗
𝑣
𝑗
∗
𝑛
𝑗=1
𝑚
𝑖=1
. 
(4.26) 
Полученные соотношения можно использовать, в частности, для получе-
ния плана двойственной задачи исходя из известного плана прямой (и наобо-
рот), а также для проверки планов на оптимальность. 
Пусть в нашей задаче на максимум условного топлива предлагается такой 
план добычи торфа и угля: 
𝑥
1
= 100 тыс.т; 
𝑥
2
= 30 тыс. т. Подставляя эти значе-
ния добычи в ограничения по использованию ресурсов, видим, что фонд обо-
ротных средств истрачен полностью. По электроэнергии же и трудовым ресур-
сам имеются неиспользованные остатки в размере 40 тыс. кВт ч и 2 тыс. чело-
веко-часов соответственно. Подставив значения неизвестных в ограничения по 
производственной программе, видим, что план добычи угля выполнен, а добы-
чи торфа перевыполнен на 10 тыс. т. 
Тогда по условию (4.20) оценки электроэнергии и трудовых ресурсов ну-
левые (
𝑦
2
= 
𝑦
3
= 0). По условию (4.21) оценка фонда оборотных средств поло-
жительна (
𝑦
1

0), по условию (4.22) оценка торфа нулевая (
𝑣
1
= 0), а по усло-
вию (4.22) оценка угля положительна (
𝑣
2

0). Таким образом, значения трех 
оценок уже известны (равны нулю), остается найти значения лишь двух оценок 
𝑦
1
и 
𝑣
2
. Оба значения неизвестных прямой задачи 
𝑥
1
и 
𝑥
2
ненулевые. Поэтому 
по условию (4.25) оба основных ограничения двойственной задачи выполняют-
ся как равенства: 
0,05
𝑦
1
+ 1,1
𝑦
2
+ 0,225
𝑦
3
– 
𝑣
1
= 0,25; 
0,5
𝑦
1
+ 
𝑦
2
+ 0,25
𝑦
3
– 
𝑣
2
= 1,2. 
Учитывая, что 
𝑦
2
= 
𝑦
3
= 
𝑣
1
= 0, имеем: 
0,05
у
1 
= 0,25; 
0,5
𝑦
1
–
 
𝑣
2
= 1,2. 
Откуда 
𝑦
1
= 5, а 
𝑣
2
= 1,3. Подставив значения неизвестных в целевые 
функции прямой и двойственной задач, проверим, выполняется ли условие 
(4.26): 
0,25 × 100 + 1,2 × 30 = 20 × 5 + 180 × 0 + 32 × 0 – 90 × 0 – 30 × 1,3 = 61. 
Выполняется. Следовательно, рассмотренный план добычи и соответ-
ствующая ему система оценок оптимальны. 
В таблице 4.2 представлен последний шаг решения симплекс-методом 
прямой задачи (ресурсы и технологические способы расположены в порядке 
возрастания индексов). 
Таблица 4.2