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

2. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


    Определение 2. Задачу линейного программирования будем называть
стандартной, если для нее l = n и k = s .

    Таким образом, ограничениями канонической задачи являются только
равенства, а стандартной задачи – только неравенства. В обеих задачах все
переменные неотрицательны.

    Любую задачу линейного программирования можно записать как в
канонической, так и в стандартной форме.

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

    Задача 2.

                             I (u ) = c, u ® min (max), u Î R n ,

                                  a1 , u £ b1 ,L, am , u £ b m ,

                               am+1 , u ³ b m +1 ,L, ak , u ³ b k ,
                                                                      .
                              u³0

                                             æu ö
    В пространстве переменных çç ÷÷÷ Î R n+k рассмотрим задачу линейного
                               çè v ÷ø

программирования в канонической форме

    Задача 3.

                   I * (u , v) º I (u ) = c, u ® min (max), u Î R n , v Î R k ,

                            a1 , u + v1 = b1 ,L, am , u + v m = b m ,

                         am+1 , u - v m+1 = b m+1 ,L, ak , u - v k = bk ,

                                          u ³ 0, v ³ 0 .

                     æu ö
    Очевидно, что çç * ÷÷÷ Î R n+k – решение задачи 3 тогда и только тогда, когда
                   çè v* ÷ø

u* – решение задачи 2 и

                                               49