Математическое программирование (линейное программирование). Киселева Э.В - 14 стр.

UptoLike

ВУЗ: 

НГАСУ «Сибстрин» | Новосибирск

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

Рубрика: 

29 30
и условиям неотрицательности:
0≥
j
x
(
)
nj ,1= ,
для которых целевая функция:
∑
=
=
n
j
jj
xcZ
1
достигает максимума.
Если ввести в рассмотрение матрицу:
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
mnm
n
aa
aa
A
K
KKL
K
1
111
и векторы:
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
n
x
x
X
K
1
,
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
n
b
b
b
K
1
,
(
)
n
ccС ,,
1
K
=
,
то стандартная форма модели примет вид:
(max).
,0
,
CXZ
X
bAX
=
≥
≤
Задачу ЛП в стандартной форме удобно решать графически,
если число переменных равно двум (
2=n ).
3.1.3. Каноническая форма модели
Найти совокупность значений n переменных ,x,,x,x
n
K
21
удовлетворяющих системе уравнений:
∑
=
=
n
j
ijij
bxa
1
( mi ,1= )
и условиям неотрицательности:
0≥
j
x ( nj ,1= ),
для которых целевая функция
nn
xcxcZ
+
+= K
11
достигает мак-
симума.
Компактная форма модели имеет вид:
bAX
=
,
0≥X ,
(max)CXZ
=
.
3.2. Понятие допустимого решения, области допустимых
решений, оптимального решения задачи линейного
программирования
Определение 3.1.
Вектор X, удовлетворяющий системе
ограничений ЗЛП, в том числе и условиям неотрицатель-
ности, если они имеются, называется допустимым реше-
нием ЗЛП.
Определение 3.2. Совокупность всех допустимых ре-
шений образует область допустимых решений (ОДР) ЗЛП.
Определение 3.3.
Допустимое решение, для которого
целевая функция достигает максимума (или минимума),
называется оптимальным решением. Будем обозначать
оптимальное решение
.X
∗
3.3. Переход от задачи минимизации целевой функции
к задаче максимизации
Задача минимизации целевой функции Z легко может быть
сведена к задаче максимизации функции Z
1
при тех же ограниче-
ниях путем введения функции
ZZ
−
=
1
.
Обе задачи имеют одно и то же решение
,X
∗
и при этом
1
maxmin ZZ
−
=
.
Проиллюстрируем этот факт графически на примере функ-
ции одной переменной: 
и условиям неотрицательности:                                                    Компактная форма модели имеет вид:
                             xj ≥ 0           ( j = 1, n) ,                                              AX = b ,
для которых целевая функция:                                                                               X ≥ 0,
                                        n                                                               Z = CX (max) .
                                 Z = ∑cjxj
                                       j =1                                   3.2. Понятие допустимого решения, области допустимых
достигает максимума.                                                             решений, оптимального решения задачи линейного
    Если ввести в рассмотрение матрицу:                                                         программирования
                       ⎛ a11 K a1n ⎞
                       ⎜           ⎟                                            Определение 3.1. Вектор X, удовлетворяющий системе
                     A=⎜ L K K ⎟
                                                                            ограничений ЗЛП, в том числе и условиям неотрицатель-
                       ⎜a          ⎟
                       ⎝ m1 K a mn ⎠                                        ности, если они имеются, называется допустимым реше-
                                                                            нием ЗЛП.
                      ⎛ x1 ⎞              ⎛ b1 ⎞                                Определение 3.2. Совокупность всех допустимых ре-
                      ⎜ ⎟                 ⎜ ⎟
и векторы:        X = ⎜K⎟ ,           b = ⎜K⎟ ,         С = (c1,K, cn ) ,   шений образует область допустимых решений (ОДР) ЗЛП.
                      ⎜x ⎟                ⎜b ⎟                                  Определение 3.3. Допустимое решение, для которого
                      ⎝ n⎠                ⎝ n⎠
                                                                            целевая функция достигает максимума (или минимума),
то стандартная форма модели примет вид:                                     называется оптимальным решением. Будем обозначать
                        AX ≤ b,
                                                                            оптимальное решение X ∗ .
                        X ≥ 0,
                        Z = CX (max).                                            3.3. Переход от задачи минимизации целевой функции
                                                                                                 к задаче максимизации
      Задачу ЛП в стандартной форме удобно решать графически,
если число переменных равно двум ( n = 2 ).
                                                                                 Задача минимизации целевой функции Z легко может быть
              3.1.3. Каноническая форма модели                              сведена к задаче максимизации функции Z1 при тех же ограниче-
                                                                            ниях путем введения функции
     Найти совокупность значений n переменных x1 , x2 ,K , xn ,
                                                                                                         Z1 = − Z .
удовлетворяющих системе уравнений:
                      n                                                         Обе задачи имеют одно и то же решение X ∗ , и при этом
                     ∑ aij x j = bi              ( i = 1, m )                                     min Z = − max Z1 .
                      j =1                                                      Проиллюстрируем этот факт графически на примере функ-
и условиям неотрицательности:                                               ции одной переменной:
                          xj ≥ 0            ( j = 1, n ),
для которых целевая функция Z = c1 x1 + K + cn xn достигает мак-
симума.
                                      29                                                                    30

Страницы