Матэкономика Симплекс метод

Симплекс - метод  решения задач линейного программирования 

Исходную  стандартную задачу линейного программирования (СЗЛП) приведем к каноническому  виду (КЗЛП). Для этого введем дополнительные переменные, учитывая знаки неравенств-ограничений. Если ограничение-неравенство имеет  знак «≥», то дополнительную переменную вводим со знаком «-», в противном случае – со знаком «+».

       СЗЛП         КЗЛП

В качестве базисных переменных удобно выбрать  , так как относительно этих переменных легко решить систему линейных уравнений: - базисные переменные; - свободные переменные.

      Составим  первую симплекс-таблицу: свободные  члены записываем без изменения  знаков, а коэффициенты при свободных  переменных – с противоположными знаками.

     Базисное  решение  - недопустимое, т.к. имеются отрицательные элементы ( ).Ограничения совместны, т.к. в строках с отрицательными свободными членами имеются ещё отрицательные элементы. Необходимо найти  разрешающий элемент и провести преобразование симплекс-таблицы.

      Найдём  разрешающий элемент. Выберем наименьший отрицательный элемент в строках  с отрицательными свободными членами. Это  -6. Столбец, в котором находится этот элемент ( ), принимаем в качестве разрешающего столбца.

      Для нахождения разрешающей строки определяем минимальное положительное отношение  свободных членов к элементам  разрешающего столбца. Так как , то в качестве разрешающей строки получаем .

      Элемент, находящийся на пересечении разрешающих столбца и строки, является разрешающим элементом (выделен рамкой). Он указывает, что базисную переменную переводим в свободные, а свободную переменную - в базисные.

      Преобразуем симплекс-таблицу, используя правила  преобразования:

      Ячейку  разрешающего элемента, равного «-6», заполняем значением, обратным значению разрешающего элемента( ).

      Ячейки  разрешающей строки заполняем элементами, стоящими в этих ячейках, деленными на разрешающий элемент «-6».

      Ячейки  разрешающего столбца заполняем  элементами, стоящими в этих ячейках, деленными на разрешающий элемент  с обратным знаком «6».

      Остальные ячейки  заполняем значениями, стоящими в этих ячейках, минус произведение элементов, стоящих в соответствующем  разрешающем столбце и в соответствующей  разрешающей строке, деленное на разрешающий  элемент «-6».

      В результате преобразования симплекс-таблицы  получим: 

     Базисное  решение  - недопустимое, т.к. есть  отрицательный элемент ( ). Ограничения совместны, т.к. в строке с отрицательным свободным членом имеется ещё отрицательные элементы.

     В качестве разрешающего столбца выбираем столбец  . Вычисляя , получаем, что в качестве разрешающей строки следует выбрать . Базисную переменную переводим в свободные, а свободную переменную - в базисные.

     В результате преобразования симплекс-таблицы  получили следующую таблицу:

     Базисное  решение  - допустимое, т.к. все свободные члены положительные. Решение оптимальное (минимум целевой функции), поскольку в строке целевой функции, кроме столбца свободных членов, все элементы одного знака (отрицательные). Оптимальное решение единственное, т.к. в строке целевой функции нет нулевых элементов. Но поскольку требуется найти еще и максимальное значение целевой функции, то итерации продолжаются.

     В качестве разрешающего столбца можно  выбрать любой столбец таблицы, т.к. они оба не удовлетворяют  признаку оптимальности (максимуму). Выбираем столбец . Тогда разрешающей строкой будет строка , т.к. .

     В результате преобразований получим  следующую симплекс-таблицу:

     Базисное  решение  - допустимое, т.к. все свободные члены положительные. Решение оптимальное (максимум целевой функции), поскольку в строке целевой функции все элементы одного знака (положительные). Оптимальное решение единственное, т.к. в строке целевой функции нет нулевых элементов.

      Таким образом, наибольшее значение целевая функция имеет при а наименьшее значение целевая функция имеет при .