Линейное программирование в примерах и задачах. Методические указания. Корытов И.В - 2 стр.

                                                              Решение задачи линейного программирования
                        Введение                                          симплекс-методом
      Пособие содержит материал, относящийся к основным
вопросам темы «Линейное программирование». Здесь рас-            Пример 1. Решить задачу линейного программирова-
сматривается только алгебраический подход к решению         ния симплекс-методом, введя при необходимости искусст-
задач. Предполагается, что студент знаком с теоретически-   венный базис.
ми сведениями, касающимися излагаемых вопросов, и уме-
ет решать основную задачу линейного программирования                              F = 3 x1 + 5 x2 → min
геометрическим методом. Основным математическим аппа-
ратом решаемых ниже задач являются элементарные преоб-                              ⎧2 x1 + 4 x2 ≥ 12
                                                                                    ⎪ 3 x + 2 x ≥ 10
разования матриц, применяемые в виде метода Жордана –                               ⎪ 1          2
Гаусса с выбором ведущего элемента.                                                 ⎨
                                                                                    ⎪           x2  ≤ 6
      Пособие посвящено практическому решению задач.                                ⎪⎩ x1           ≤ 5
Ход решения построен с выделением этапов и шагов, снаб-
женных необходимыми комментариями, и может одновре-                                     x1 ≥ 0, x2 ≥ 0
менно служить образцом оформления при выполнении сту-
дентом самостоятельной работы. Разбираемые примеры по-
добраны в определенной последовательности по схеме: ре-     Приведение условия к каноническому виду
шение исходной задачи линейного программирования – со-              Так как система ограничений состоит из неравенств,
ставление условий двойственной задачи – решение двойст-     для приведения условия к каноническому виду нужно вве-
венной задачи двумя способами. Метод искусственного ба-     сти в каждое неравенство балансовые переменные
зиса с точки зрения вычислительных процедур не отличает-    x3 , x 4 , x5 , x 6 :
ся от стандартного симплекс-метода, дополнительные дей-
ствия связаны с видоизменением целевой функции путем
добавления специального слагаемого, называемого штраф-           ⎧2 x1   + 4 x2   − x3                         = 12
                                                                 ⎪3x     + 2 x2          − x4                  = 10
ной функцией. Смысл этих действий понятен из примера,            ⎪ 1
поэтому метод искусственного базиса рассматривался не            ⎨
                                                                 ⎪           x2                 + x5           = 6
под отдельным заголовком, а в ходе решения одной из за-          ⎪⎩ x1                                  + x6   = 5
дач.
      Задания типового расчета составлены таким образом,                          x j ≥ 0, j = 1,K ,6
что одна из взаимно двойственных задач решается обычным
симплекс-методом, а другая – методом искусственного ба-          Матрица системы ограничений
зиса.
      Пособие адресовано студентам третьего курса эконо-
мических специальностей.
2                                                                                                                     3