Линейное программирование. Азарнова Т.В - 9 стр.

                                                                              Линейное программирование


понятие эквивалентных задач оптимизации. Существует стандартное опреде-
ление: две оптимизационные задачи называются эквивалентными, если они
имеют одно и то же множество оптимальных точек. Однако так как при
переходе от одного вида задачи к другому возможно изменение размерности
задачи (увеличение числа переменных, увеличение числа ограничений), то
следует в каждом конкретном случае аккуратно формулировать, как понима-
ется эквивалентность данных задач. Сформулируем правила, позволяющие
осуществить эквивалентные перезаписи задач.
      1. Обеспечить нужное направление оптимизации целевой функции
возможно с помощью умножения исходной целевой функции на -1.
      2. Любое неравенство можно умножить на -1 и перейти к неравенству
другого знака.
                                        n
        3. Ограничение-равенство       ∑ aij x j         =bi можно записать в виде системы
                                       j =1
двух неравенств
                                               n
                                              ∑ a ij x j    ≤bi
                                              j =1
                                              n
                                            ∑ aij x j ≥bi .
                                              j =1
      4. От ограничений неравенств можно перейти к равенствам, добавляя
или отнимая неотрицательные новые переменные, которые в дальнейшем бу-
дут    называться дополнительными переменными. Так,         неравенство
 n                                                   n
∑ a ij x j   ≤bi эквивалентно системе                ∑ aij x j      +u i =bi , u i ≥0 . Аналогично
j =1                                                 j =1
                   n                                                     n
неравенство       ∑ aij x j ≥bi эквивалентно системе ∑ aij x j                    −u i =bi , u i ≥0 .
                  j =1                                                j =1
      5. Обеспечить условие неотрицательности переменной можно, исполь-
зуя очевидный факт: любое число может быть представлено в виде разности
двух неотрицательных чисел: x =x ′ −x ′′, x ′ ≥0, x ′′ ≥0 . Если в задаче при-
сутствовало требование x j ≤0 , осуществляется замена x j =−x ′j , x ′j ≥0 .
      В качестве примера сформулируем факт эквивалентности двух сле-
дующих задач линейного программирования:
 n                                                                   n
∑ c j x j → min                                                    −∑ c j x j → max
j =1                                                                 j =1
 n                                                          n
∑ aij x j ≤bi ,     i =1, m   (1)                           ∑ aij x j        +u i =bi , i =1, m (2)
j =1                                                        j =1

x j ≥0,       j =1, n                                       x j ≥0, j =1, n, u i ≥0, i =1, m




                                              11