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

UptoLike

ВУЗ: 

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

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

Рубрика: 

68
Отметим следующий очевидный факт. Точка
X
,
в которой функция
f
(
X
)
принимает
наибольшее (наименьшее) значение, одновременно является точкой, в которой функция
—
f
(
X
)
принимает наименьшее (наибольшее) значение, при этом
[
]
[
]
minmax
)()(
XfXf
−−=
и
[
]
[
]
.)()(
maxmin
XfXf
−−= Таким образом, любая задача максимизации (минимизации)
может быть заменена эквивалентной задачей минимизации (максимизации).
Так, если в задаче линейного программирования требуется минимизировать
функцию
СХ
,
то, заменив, вектор
С
= (
с
1
,
с
2
, . . .,
с
n
)
противоположным вектором —
С
=(
-
с
1
,
-
c
2
, . . ., -
с
п
), придем к эквивалентной задаче максимизации функции -
СХ
,
но при этом,
конечно, (
СХ
)
min
= - (-
СХ
)
max
.
Приведение задач линейного программирования к канонической форме
Каноническая форма задачи линейного программирования оказывается
необходимой при дальнейшем изложении основного метода решения задачи —
симплексного метода.
Покажем, каким образом можно преобразовать любую задачу линейного программирования в эквивалентную каноническую
задачу. Начнем с рассмотрения стандартной задачи (2.2.7) – (2.2.8)
Введем в рассмотрение неизвестный неотрицательный
т-
мерный вектор
[
]
,,...,,
21
'
mnnn
xxxX
+++
=
связанный с неизвестным вектором
X
=[
x
1
,
x
2
, . . .,
х
п
]
соотношением
АХ
+
Х
'
=
В.
(2.2.11)
Вектор
X
'
назовем
балансовым (выравнивающим) вектором.
Ясно, что
неотрицательные векторы
X
и
X
',
удовлетворяющие векторному уравнению (2.2.11), будут
удовлетворять векторному неравенству (2.2.8) . Обратно, если вектор
X
неотрицательный
и удовлетворяет неравенству (2.2.8), то балансовый вектор
X
',
найденный из уравнения
(2.2.11), окажется неотрицательным. Таким образом, условия (2.2.8) и (2.2.11) для
искомого вектора
X
являются эквивалентными. Поэтому каноническая задача —
найти
максимум (минимум) целевой функции
z
=
CX+OX
'
(2.2.12)
при условиях:
АХ + Х
'
= В
,
(2.2.13)
Х
≥0
,
'
X
≥0 (2.2.14)
будет эквивалентна стандартной задаче (2.2.7) — (2.2.8), поскольку вектор
X
,
входящий в
оптимальное решение задачи (2.2.12) — (2.2.14), будет, очевидно, являться оптимальным
решением стандартной задачи (2.2.7) — (2.2.8). Действительно, неотрицательный вектор
X
,
взятый из решения канонической задачи (2.2.12) — (2.2.14), будет удовлетворять
условию (2.2.8) стандартной задачи и давать то же значение (
СХ
)
макс
или (
СХ
)
мин
.
При решении канонической задачи (2.2.12) — (2.2.14) надо иметь в виду, что эта
задача содержит
п+т
неотрицательных переменных
х
1
,
х
2
,...,
х
n
,
х
n+1
,...,
х
n+т
,
и балансовые
переменные
х
n+1
,
x
n+2
, . . .,
х
п+т
следует считать входящими слагаемыми в целевую
функцию (2.2.12) с нулевыми коэффициентами.
Пример 1
. Привести к канонической форме следующую стандартную задачу
линейного программирования. Найти неотрицательные числа
х
1
,
х
2
, x
3
,
x
4
, при которых
целевая функция
4321
42
xxxxz
+++=
имеет максимальное значение при условиях:

Страницы