Оптимальное управление в экономике. Матвейкин В.Г - 10 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

=
m
n
bbbX ...,,,;0...;;0;0
210
43421
,
m
bbbXw
−
−
−
−
=
...)(
210
.
Замечание. Если некоторые из ограничительных уравнений системы имеют предпочтительный вид (т.е. со-
держат базисную переменную), то искусственные переменные в них не вводят (что упрощает решение задачи).
1.4. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ И ГРАФИЧЕСКОЕ
РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Рассмотрим задачу линейного программирования симметричного вида относительно двух переменных:
max
2211
→xc+xc=z ; (1.13)
≤
≤
≤
,
.............................
;
;
2211
2222121
1212111
mmm
bxa+xa
bxa+xa
bxa+xa
(1.14)
2.1,,0 =ajx
j
≥ (1.15)
1.4.1. Геометрическая интерпретация области допустимых значений
1. Любое из неравенств (1.14) на плоскости
21
xOx определяет некоторую полуплоскость.
2. Система неравенств (1.14)–(1.15) определяет выпуклое множество (выпуклый многоугольник, неогра-
ниченную выпуклую многоугольную область, пустую область или точку), которое совпадает с многогранником
решений D.
1.4.2. Геометрическая интерпретация целевой функции
• Уравнение
2211
xc+xc=z при фиксированном значении
0
z=z определяет на плоскости
21
xOx прямую
22110
xc+xc=z . При изменении z получают семейство параллельных прямых, называемых линиями уровня.
• Вектор коэффициентов целевой функции
(
)
21
; cc=c
r
называется градиентом функции. Он перпендику-
лярен линиям уровня.
• Градиент функции
()
21
; cc=c
r
показывает направление наибольшего возрастания целевой функции.
• Антиградиент
(
)
21
; cc=c −
−
−
r
показывает направление наибольшего убывания целевой функции.
1.4.3. Графическое решение задач линейного программирования
Суть графического метода решения задач ЛП основывается на следующих утверждениях:
1) совокупность опорных планов задачи ЛП совпадает с системой вершин многогранника решений;
2) целевая функция достигает оптимального значения в вершине многогранника решений.
Для практического решения задачи (1.13) – (1.15) необходимо:
1) построить с учётом системы ограничений область допустимых решений D (многогранник планов);
2) построить вектор градиента c
r
;
3) построить перпендикулярно к нему в области допустимых решений одну из прямых семейства
const=z ;
4) искомая точка экстремума
opt
X
найдется параллельным перемещением вспомогательной прямой
const=z в направлении вектора c
r
(если ищется
max
z ) и в направлении вектора c
r
−
(если ищется
min
z );
5) координаты точки
opt
X
можно определить, решив совместно уравнения прямых, пересекающихся в
этой точке, или по чертежу.
Замечание. Если оптимальное значение целевая функция принимает более чем в одной вершине, то она
принимает его во всякой точке, являющейся выпуклой линейной комбинацией этих вершин. Выпуклой линейной
комбинацией
k
XXX ...,,,
21
точек называется сумма
,...
2211 kk
X++X+X
λ
λ
λ

Страницы