Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 79 стр.

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
79
позволяют сформулировать следующие условия существования решения задачи
линейного программирования.
Теорема 6. Пусть допустимое множество задачи линейного
программирования на минимум не является пустым, а целевая функции задачи
ограничена снизу на этом множестве. Тогда существует угловая точка
допустимого множества, представляющая собой решение задачи линейного
программирования.
3.6. Алгоритм решения канонической задачи линейного
программирования. Дана задача линейного программирования в
канонической форме
min
1
1
®++
n
n
ucuc
L
1
1
1
11
buaua
n
n
=++
L
,
...
..........
..........
..........
(1)
mn
mnm
buaua =++
L
1
1
.
0,,0
1
³³
n
uu
L
.
Ниже приводится алгоритм решения канонической задачи линейного
программирования, базирующийся на результатах, изложенных в п.п. 2-4.
1. Привести ограничения(1) задачи к виду, когда mib
i
,,1,0
L
=³ .
2. Сконструировать вспомогательную задачу
(
)
min
1
1
®++=
m
wwzI
L
11
1
1
11
bwuaua
n
n
=+++
L
,
……………………………
mmn
mnm
bwuaua =+++
L
1
1
,
0,,0,0,,0
11
³³³³
mn
wwuu
L
L
.
3. Преобразовать ограничения вспомогательной задачи к виду (3.4). 
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


позволяют сформулировать следующие условия существования решения задачи
линейного программирования.

     Теорема     6.   Пусть       допустимое                множество     задачи   линейного
программирования на минимум не является пустым, а целевая функции задачи
ограничена снизу на этом множестве. Тогда существует угловая точка
допустимого множества, представляющая собой решение задачи линейного
программирования.

     3.6.   Алгоритм        решения              канонической           задачи     линейного
программирования.        Дана        задача           линейного        программирования    в
канонической форме

                                  c1u1 + L + cnu n ® min

                                  a11u1 + L + a1nu n = b1 ,

                                .................................                         (1)

                                 am1u1 + L + amnu n = b m .

                                      u1 ³ 0,L, u n ³ 0 .

     Ниже приводится алгоритм решения канонической задачи линейного
программирования, базирующийся на результатах, изложенных в п.п. 2-4.

     1. Привести ограничения(1) задачи к виду, когда bi ³ 0, i = 1,L, m .

     2. Сконструировать вспомогательную задачу

                               I1 (z ) = w1 + L + wm ® min

                               a11u1 + L + a1n u n + w1 = b1 ,

                            ……………………………

                              am1u1 + L + amnu n + wm = b m ,

                          u 1 ³ 0, L, u n ³ 0, w 1 ³ 0,L , w m ³ 0 .

     3. Преобразовать ограничения вспомогательной задачи к виду (3.4).

                                                79

Страницы