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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

2.2 Преобразование целевой функции при переходе
от одного опорного решения к другому
Пусть имеется опорное решение задачи линейного программирования )0...,,0,,...,,(
20101 mo
xxxX = с ба-
зисом )....,,,(
211 m
AAAB = Значение целевой функции задачи на этом решении
∑
=
=
m
i
i
xcXZ
1
011
.)( Используя
преобразование Жордана с разрешающим элементом
lk
a , перейдем к другому опорному решению:
)0...,,0,,0...,,0,...,,...,,,(
1000)1(20101
xxxxxX
ml
′′′′′
=
+
с базисом ),...,,,...,,,(
11212 kmll
AAAAAAB
+−
=
т.е. введем в базис
вектор
k
A и исключим
l
A .
Пересчитав правые части с помощью преобразований Жордана, получим выражение для целевой
функции задачи на новом опорном решении Х
2
:
kk
QXZXZ
∆
−
=
012
)()( .
Здесь через
k
∆ обозначена величина, называемая оценкой разложения вектора условий
k
A по ба-
зису опорного решения и вычисляемая по формуле
k
m
i
iklk
cxc −=∆
∑
=1
или в векторной записи
kkk
cXC
−
=
∆
б
, (2.6)
где ),...,,(
21б m
ccсC = – вектор коэффициентов целевой функции при базисных переменных;
−= ),...,,(
21 mkkkk
xxxX вектор коэффициентов разложения вектора
k
A по базису опорного решения;
k
c – ко-
эффициент целевой функции при переменной
k
x .
Находим приращение целевой функции при переходе от одного опорного решения к другому
kkk
QXZXZZ
∆
−
=
−
=
∆
012
)()( .
2.3 Улучшение опорного решения
Теорема 2.3.1 Если в задаче линейного программирования на максимум (минимум) хотя бы для
одного вектора условий оценка разложения по базису невырожденного опорного решения отрицатель-
ная (положительная), то опорное решение может быть улучшено, т.е. можно найти новое опорное ре-
шение на котором значение целевой функции будет больше (меньше).
Следствие 1 (условие наискорейшего нахождения оптимального решения). Наибольшее изменение
целевой функции при переходе от одного опорного решения к другому обеспечивает выбор векторов,
выводимого и вводимого в базис опорного решения задачи на:
– максимум
{
}
{
}
kk
k
k
k
QZ ∆−=∆
0
maxmax
; (2.7)
– минимум
{
}
{
}
kk
k
k
k
QZ ∆−=∆
0
minmin
. (2.8)
В упрощенном варианте вектор, вводимый в базис, можно выбрать, в задаче на:
– минимум
{
}
k
k
∆
min
; (2.9)
– максимум
{
}
k
k
∆
max . (2.10)
Этот вариант перехода к новому опорному решению обычно используется при расчетах на ЭВМ.
Следствие 2 (признак оптимальности опорного решения). Опорное решение задачи линейного
программирования на максимум (минимум) является оптимальным, если для любого вектора условий
оценка разложений по базису опорного решения неотрицательная (неположительная).

Страницы