Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 10 стр.

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


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




                                               12