Составители:
Рубрика:
66
*
2211
1,122,111,1
;...
............................................
;...
≤+++
≤+++
++++
mnmnmm
knnkkk
bxaxaxa
bxaxaxa
(2.2.3)
Задачу (2.2.1) – (2.2.3) при неотрицательности всех чисел х
j
(x
j
≥0, j=1,2,…,n) будем
называть общей задачей линейного программирования.
Иногда не требуется неотрицательности всех чисел х
j
; в таком случае задача может
быть легко приведена к общей задаче линейного программирования. Как это делается, по-
кажем на конкретном примере.
Пусть требуется найти неотрицательные числа х
1
,х
2
и число х
3
без ограничения по
знаку, максимизирующие целевую функцию
321
2 xxxz −+=
при условиях:
≤−+
=+−
.62
;52
321
321
xxx
xxx
В этой задаче никакого условия на знак переменной х
3
не накладывается. Введем
две новые неотрицательные переменные
'
3
x и
''
3
x , связанные с х
3
соотношением
'
3
x -
''
3
x =
х
3
. Тогда поставленная задача окажется эквивалентной следующей общей задаче
линейного программирования.
Требуется найти неотрицательные числа х
1
, х
2
,
'
3
x ,
''
3
x
, которые обращают в
максимум целевую функцию
''
3
'
321
2 xxxxz +−+=
*Все неравенства (2.2.3) взяты для однообразия со знаком ≤, так как любое
неравенство противоположенного смысла (со знаком ≥) может быть превращено в
неравенство со знаком ≤ умножением обеих частей его на –1.
при выполнении условий:
≤+−+
=−+−
.62
;52
''
3
'
321
''
3
'
321
xxxx
xxxx
Если в решении последней задачи окажется, что
'
3
x ≥
''
3
x
, то значение переменной х
3
в решении исходной задачи будет неотрицательным, в противном случае х
3
окажется
отрицательным.
В общем случае, если в задаче линейного программирования условиям
неотрицательности подчинены не все переменные x
j
, то такая задача приводится к общей
задаче линейного программирования путем введения вместо каждой переменной, не
подчиненной условию х
j
≥0, двух неотрицательных переменных
'
j
x и
''
j
x , связанных с х
j
,
соотношением х
j
=
'
j
x -
''
j
x .
Примем следующую терминологию. Условия (2.2.2) и (2.2.3) будем называть
системой ограничений задачи, а каждое условие в отдельности — ограничением. Таблица
коэффициентов
nm
ij
aA
×
=
в системе ограничений (2.2.2) и (2.2.3) называется матрицей
условий задачи. Столбцы этой матрицы A
j
={a
1j
,a
2j
,..., a
mj
} называются векторами условий.
Страницы
- « первая
- ‹ предыдущая
- …
- 64
- 65
- 66
- 67
- 68
- …
- следующая ›
- последняя »
