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

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


2. Проверить, является ли точка x 0 решением задачи ЛП:
                    a) 2 x1 −4 x 2 +x3 −x 4 +3x 5 → max
                      −5 x1 +6 x 2 −7 x3 +x 4 +14 x 5 =−7
                       x1 −5 x 2 −10 x3 −4 x 4 +20 x 5 =−10
                       x j ≥0, j =1,5
x 0 =(2,0,0,3,0 )
                     b) x1 −3 x 2 +4 x 3 −2 x 4 −3 x5 → min
                       −x1 +x 2 −x 3 +x 4      =−1
                        2 x1 − 2 x 3 −6 x 4 +2 x5 =4
                          x j ≥0, j =1,5
x 0 =(2,1,0,0,0 )
3. Используя теорию симплекс- метода, найти все значения к, при которых
точка x * =(1,2,0,1,0 ) является решением задачи
                       3x1 +12 x 2 +kx 3 −5 x 4 −2kx 5 → max
                           −x1 +x 2 +3 x 3 −x 4 +2 x 5 =0
                           3x1 − x3 +2 x 4 −x5 =5
                        −x1 −3x 2 +x 3       + x 5 =−7 ;
                           x j ≥0, j =1,5

            §5. Метод искусственного базиса и M-метод решения
            произвольной задачи линейного программирования

      В случае, если задача линейного программирования задана в произ-
вольной форме, то отсутствует необходимая информация для использования
базового симплексного метода, то есть исходный базис. Для отыскания на-
чальной базисной точки может быть использован прием, заключающийся в
создании специальной задачи, связанной с исходной следующим образом:
при решении созданной задачи симплексным методом либо будет получена
искомая базисная точка, либо будет обнаружена пустота допустимого мно-
жества исходной задачи.
      Пусть ЗЛП задана в каноническом виде (1)-(3). Введем новые (искусст-
венные) переменные в ограничения задачи так, чтобы в результате образо-
вался единичный базис (появилась возможность выписать исходную базис-
ную точку):
                             Ax + Ez=b (b≥0)
                                x ≥0, z ≥0.



                                        23