Математические методы в коммерческой деятельности. Буравлева О.Ю. - 18 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

венности используются четыре пары двойственных задач. Приведем их в матричной форме записи.
Исходная задача Двойственная задача
Симметричные пары
1
;
,
max,)(
0
QX
AAX
CXXZ
≥
≤
→=
2
;
,
min,)(
0
QX
AAX
CXXZ
≥
≥
→=
;
,
min,)(
0
QY
CYA
YAYF
≥
≥
→=
(4.6)
.
,
max,)(
0
QY
CYA
YAYF
≥
≤
→=
(4.7)
Несимметричные пары
3
;
,
max,)(
0
QX
AAX
CXXZ
≥
=
→=
4
;
,
min,)(
0
QX
AAX
CXXZ
≥
=
→=
,
min,)(
0
CYA
YAYF
≥
→
=
(4.8)
.
max,)(
0
CYA
YAYF
≤
→=
(4.9)
Здесь ),...,,,(
21 n
cccC = ),...,,,(
21 m
yyyY
=
,
...
.................
...
...
21
22221
11211
=
mnmm
n
n
aaa
aaa
aaa
A
,
...
2
1
0
=
m
b
b
b
A
.
...
2
1
=
n
x
x
x
X
4.1 Общие правила составления двойственных задач
При составлении двойственных задач используют следующие правила:
Правило 1 Во всех ограничениях исходной задачи свободные члены должны находиться в правой
части, а члены с неизвестными – в левой.
Правило 2 Ограничения-неравенства исходной задачи должны быть записаны так, чтобы знаки нера-
венств у них были направлены в одну сторону.
Правило 3 Если знаки неравенств в ограничениях исходной задачи «≥», то целевая функция
nn
xcxcxccXZ ++++= ...)(
22110
должна максимизироваться, а если «≤», то минимизироваться.
Правило 4 Каждому ограничению исходной задачи соответствует неизвестное в двойственной за-
даче; при этом неизвестное, отвечающее ограничению-неравенству, должно удовлетворять условию не-
отрицательности, а неизвестное, отвечающее ограничению-неравенству, может быть любого знака.
Правило 5 Целевая функция двойственной задачи имеет вид: ,...)(
110 mm
ybybcYF +++
=
где
0
c – сво-
бодный член целевой функции Z(X) исходной задачи;
m
bbb ...,,,
21
– свободные члены в ограничениях ис-
ходной задачи, при этом
i
b – свободный член именно того ограничения, которому соответствует неиз-
вестная −
mi
yyyy ...,,,;
21
неизвестные в двойственной задаче.
Правило 6 Целевая функция F(Y) двойственной задачи должна оптимизироваться противополож-
ным по сравнению с Z(X) образом, т.е. если max,)( →XZ то min,)( →YF и если min,)( →XZ то .max)( →YF
Правило 7 Каждому неизвестному
njx
j
...,,2,1, =
исходной задачи соответствует ограничение в
двойственной задаче. Совокупность этих n ограничений (вместе с условиями неотрицательности неиз-
вестных
i
y , соответствующих ограничениям-неравенствам исходной задачи) образует систему ограни-
чений двойственной задачи. Все ограничения двойственной задачи имеют вид неравенств, свободные
члены которых находятся в правых частях, а члены с неизвестными
−
m
yyy ...,,,
21
в левых. Все знаки не-
равенств имеют вид «≥», если
min,)( →YF и «≤», если .max)( →YF
Коэффициенты, с которыми неизвестные
m
yyy ,...,,
21
входят в ограничение, соответствующее неиз-
вестному
,
j
x совпадают с коэффициентами при этом неизвестном
j
x в ограничениях исходной задачи, а
именно: коэффициент при
i
y совпадает с тем коэффициентом при
j
x , с которым
j
x входит в ограничение
исходной задачи, соответствующее неизвестному
i
y .

Страницы