Математическое программирование и моделирование экономических процессов. Коробов П.Н. - 135 стр.

UptoLike

ВУЗ: 

СПбГЛТУ | Санкт-Петербург

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

Рубрика: 

135
≥+++++
≥+++++
≥+++++
.......
................................................................
,......
................................................................
,......
2211
2211
111221111
nmmniinnn
jmmjiijjj
mmii
cyayayaya
cyayayaya
cyayayaya
(3.34)
Или в краткой записи
∑
=
==
m
i
iii
ybyG
1
min)( (3.33')
при условиях
∑
=
=≥
n
i
jiij
njcya
1
,1; (3.34')
.,1;0
miy
i
=≥
Если по вышеуказанным правилам составить задачу двойственную по отношению к
последней задаче (3.33), (3.34), то получится исходная задача (3.31), (3.32). Поэтому обе эти
задачи называются
взаимосопряженными.
Какую из этих задач называть прямой и какую
— двойственной, зависит каждый раз от нашего соглашения.
Напомним, что
допустимым решением
или
планом
задачи линейного
программирования называется любая совокупность значений неизвестных, входящих в
задачу, которая удовлетворяет всем условиям задачи, т. е. допустимое решение — это любое
неотрицательное решение системы ограничений задачи.
Оптимальное решение задачи —
это такое допустимое решение, при котором целевая
функция имеет наибольшее (или наименьшее) значение среди множества значений целевой
функции на бесчисленном множестве допустимых решений. Этими определениями мы
постоянно будем пользоваться при изложении основных соотношений между
взаимосопряженными стандартными задачами.
Лемма
.
Если x
1
, x
2
, ...,х
n
допустимое решение стандартной задачи на максимум
(3.31), (3.32) и y
1
, y
2
,..., y
m
допустимое решение двойственной стандартной задачи на
минимум (3.33), (3.34), то имеет место неравенство:
∑∑∑
==
≤≤
m
i
ii
ji
ijij
n
j
jj
ybyxaxc
1,1
.
(3.35)
Иными словами, значение целевой функции на любом из .допустимых решений
стандартной задачи на максимум не превосходит значения целевой функции на любом из
допустимых решений двойственной стандартной задачи на минимум.
Д о к а з а т е л ь с т в о . Умножим неравенства (3.34) соответственно на
неотрицательные числа
x
1
,
x
2
,
...,
х
п
и просуммируем их; в результате получаем:
.
,111
∑∑∑∑
=≤
=== ji
ijij
m
i
iij
n
j
j
n
j
jj
yxayaxxc
(3.36)
Аналогично, умножая неравенства (3.32) соответственно на неотрицательные числа
y
1
,
y
2
,. . . ,
y
m
и суммируя их, получаем:
.
1,11
∑∑∑∑
===
≤=
m
i
ii
ji
ijij
n
j
jij
m
i
i
ybyxaxay
(3.37)
Сопоставление неравенств (3.36) и (3.37) дает нам неравенство (3.35) и лемма доказана.
На основании доказанной леммы установим признак оптимальности допустимых
решений взаимосопряженных стандартных задач.

Страницы