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

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


2. Проверить, является ли точка x 0 решением задачи ЛП:
                    a) 2 x1 −4 x 2 +x3 −x 4 +3 x5 → max
                      −5 x1 +6 x 2 −7 x3 +x 4 +14 x5 =−7
                       x1 −5 x 2 −10 x3 −4 x 4 +20 x5 =−10
                       x j ≥0, j =1,5
x 0 =(2,0,0,3,0)
                     b) x1 −3x 2 +4 x 3 −2 x 4 −3 x5 → min
                       −x1 +x 2 −x 3 +x 4      =−1
                        2 x1 − 2 x3 −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) является решением задачи
                      3 x1 +12 x 2 +kx 3 −5 x 4 −2kx 5 → max
                           −x1 +x 2 +3x3 −x 4 +2 x5 =0
                           3x1 − x3 +2 x 4 −x5 =5
                        −x1 −3 x 2 +x3        + x5 =−7 ;
                             x j ≥0, j =1,5

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

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



                                        22