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

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


некоторого номера i = 1,L, m - r окажется, что все g r + i k = 0, k = r + 1,L , n , то
соответствующее равенство превращается в тождество, и его можно отбросить.
В силу того, что u k ³ 0, k = r + 1, L , n , неравенство g r + i k < 0 , имеющее место хотя

бы для одного i = 1,L, m - r , влечет за собой u k = 0 , поэтому столбец,
отвечающий такому номеру k , можно вычеркнуть из таблицы. После
вычеркивания в колонках 2-6 нижней части таблицы останутся только нули, и
эту часть таблицы можно отбросить. В результате в таблице остаются только
основные переменные u 1 ,L , u r . В этом случае rang ( A) = r < m .

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

     Проиллюстрируем алгоритм выбора начальной угловой точки на решении
конкретной задачи.

     Пример 6. Решить задачу линейного программирования

                     I (x1 , x 2 , x 3 , x 4 , x 5 ) = -40 x1 + 7 x 2 - 3 x 3 + 6 x 4 + 3 x 5 ,

                                    4 x1 + x2 + 2 x3 + x4 + 3x5 = 55,

                              - 17 x1 + 16 x 2 - 4 x 3 + 2 x 4 + 5 x 5 = 46 ,

                              - 33x1 + 26 x 2 - 7 x 3 + 4 x 4 + 8 x 5 = 66 ,

                          - 108 x1 + 96 x 2 - 21x 3 + 16 x 4 + 35 x 5 = 354 ,

                                 x1 ³ 0, x 2 ³ 0, x 3 ³ 0, x 4 ³ 0, x 5 ³ 0 .

     Заметим, что последнее ограничение в форме равенства здесь намеренно
взято в виде линейной комбинации первых трех ограничений. По существу
задача линейного программирования, сформулированная в этом примере, есть
в точности та же задача, что и в примерах 2 и 5.

                                                        83