ВУЗ:
Составители:
Рубрика:
137
Стандартная постановка задачи линейного программирования формулиру-
ется следующим образом:
Найти значения переменных х
1
, х
2
, … х
n
, которые:
1) удовлетворяют системе линейного уравнения
=+++
−−−−−−−−−−−−−−−−−−
=+++
=+++
;bxа...хаха
,bxа...хаха
,bxа...хаха
nnnn22n11n
2nn2222121
1nn1212111
(103)
2) являются неотрицательными, т. е
х
1
≥ 0, х
2
≥ 0, …, х
n
≥ 0; (104)
3) обеспечивают наименьшее значение линейной целевой функции
f(x
1
, x
2
, …, x
n
) = c
0
+ c
1
x
1
+ c
2
x
2
+ … + c
n
x
n
. (105)
Всякое решение системы уравнений (103), удовлетворяющее системе не-
равенств (104), называется допустимым решением. Допустимое решение, ко-
торое минимизирует целевую функцию (105), называется оптимальным ре-
шением.
Задачи линейного программирования можно решать геометрическим ме-
тодом.
Введем некоторые понятия.
Областью решения линейного неравенства с двумя переменными
а
0
+ а
1
х
1
+ а
2
х
2
≥ 0 (106)
является полуплоскость.
Для того, чтобы определить, какая из двух полуплоскостей соответствует
этому неравенству, нужно привести его к виду х
2
≥ kx
1
+ b или х
2
≤ kx
1
+ b.
Тогда искомая полуплоскость в первом случае расположена выше прямой
а
0
+ а
1
х
1
+ а
2
х
2
= 0, во втором – ниже нее.
Если а
2
= 0, то неравенство (106) имеет вид а
0
+ а
1
х
1
≥ 0; в этом случае по-
лучим либо х
1
≥ h – правую полуплоскость, либо х
1
≤ h – левую полуплоскость.
Областью решений системы неравенств двух переменных является пе-
ресечение конечного числа полуплоскостей, каждая из которых описывается
отдельным неравенством.
Это пересечение представляет собой многоугольную область G. Она может
быть как ограниченной, так и неограниченной и даже пустой (если система не-
равенств противоречива).
Область решений G обладает важным свойством выпуклости.
Область G
1
называется выпуклой (рис. 7.10, а), если две ее произвольные
точки можно соединить отрезком А
1
В
1
, целиком принадлежащим данной области.
В
невыпуклой области G
2
можно выбрать такие две ее точки, что не все
точки отрезка А
2
В
2
принадлежат области G
2
(рис. 7.10, б).
Страницы
- « первая
- ‹ предыдущая
- …
- 137
- 138
- 139
- 140
- 141
- …
- следующая ›
- последняя »
