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

>      Для данной задачи построим исходную симплексную  таблицу.

      В заголовке столбцов записываются все  векторы системы ограничений  и 

      соответствующие  коэффициенты  при  переменных  целевой  функции.  Столбец состоит из  правых  частей  уравнений.  На  пересечении  4-го,       5-го,…,  n-го столбцов и первых m строк записываются коэффициенты при соответствующих переменных в уравнениях.

      Столбец  Б (базис)  определяет  базисные  векторы,  причём  они  записываются в той последовательности, в какой выражены базисные переменные в системе ограничений.

      Столбец определяет  коэффициенты  целевой  функции  при  соответствующих базисных переменных.

      Последняя строка называется индексной или оценочной и определяет оценки соответствующих векторов, за исключением первой и второй клетки. Значения клеток индексной строки при опорном плане вычисляются следующим образом:

       ,

      .     .      .

       .

      Оценки  всех базисных векторов всегда равны  нулю. 

      1.4 Алгоритм симплексного метода

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

      1.  Проверяется, находится ли задача  линейного программирования в канонической форме. Если нет, то необходимо её преобразовать.

      2.  Проверяется  наличие  исходного   опорного  плана.  При  его   отсутствии задача не может  быть решена обычным симплекс–методом. Существуют другие модифицированные методы для решения таких задач.

      3.  Проводится построение исходной  симплексной таблицы. 

      4.  Проверяются значение оценок  в индексной строке.  Если нет положительных оценок, то выписывается оптимальное решение и алгоритм заканчивает свою работу. В противном случае выполняется пункт 5.

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

      6.  Из  базиса  выводится  вектор,  которому  соответствует  наименьшее симплексное  отношение  (см.  5.3).  Данная  строка  называется  разрешающей

строкой.

      7.  Строится  новая  симплексная   таблица.  Соответствующим образом изменяются  столбцы Б  и .  Остальная  часть  таблицы  заполняется  из  предыдущей с помощью гауссовских преобразований, причём индексная строка считается m+1 строкой и также преобразуется с помощью гауссовских преобразований. Переходим на выполнение пункта 4 данного алгоритма.

      После  построения  каждой  таблицы  можно  проверить  правильность  вычислений с использованием формул вычисления оценок приведённых в предыдущем пункте. 

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

Решение.

1. Задачу необходимо  привести к каноническому виду:

2. Задача имеет  исходный опорный план: =(0;0;1;1;2). Строим исходную симплексную таблицу:

      Рассмотрим  первую  таблицу.  Критерием  оптимальности являются  неположительные  оценки  в  индексной  строке.  В  таблице  имеются  положительные оценки, следовательно, данный опорный план не является оптимальным.  Наибольшая  положительная  оценка  в  индексной  строке  соответствует  вектору .

      Вводим  в базис вектор . Для определения вектора, выводимого из базиса, вычисляется симплексное отношение:

      

.

      Минимум достигается в строке , поэтому выводим из базиса вектор .

      Переходим ко второй таблице. Вносим соответствующие  изменения в столбцы  и . Делаем пересчет остальных строк таблицы по методу Жордана–Гаусса.

      Третья  строка  переписывается  без  изменения,  так как разрешающий элемент равен единице. Третья (разрешающая) строка новой (второй) таблицы умножается на 1 и прибавляется к первой строке старой таблицы. Результат записывается в качестве первой строки новой таблицы. Затем разрешающая строка умножается  на  (–1)  и  прибавляется  ко  второй  строке  старой  таблицы.  Результат записывается в качестве второй строки новой таблицы. И, наконец, третья (раз решающая) строка новой таблицы умножается на (–7) и прибавляется к индексной строке старой таблицы. Результат записывается в качестве индексной строки новой таблицы. Необходимо проверить правильность проведённых преобразований. Для этого получим значения элементов новой индексной строки с помощью формул, приведённых в предыдущем параграфе. Если значения некоторых  элементов  не  совпадают  с  полученными  значениями  с  помощью  метода Жордана–Гаусса,  то  при  проведении  преобразований  допущена  ошибка,  которую необходимо устранить.

      Рассматриваем индексную строку второй таблицы. Положительная оценка в ней соответствует вектору . Вводим в базис вектор . Симплексное отношение считать не нужно, так как в данном столбце имеется единственное положительное число,  соответствующее  вектору  . Выводим из  базиса  вектор .  Переходим к третьей таблице. Вносим соответствующие изменения в столбцы и . Выполняем пересчет остальных строк таблицы по методу Жордана–Гаусса.

      Рассматриваем  индексную  строку  третьей  таблицы.  Поскольку  оценки  в индексной  строке отрицательные и нулевые, то полученный опорный план является  оптимальный,  а  значение  целевой  функции  z′  является минимальным.

      Напомним,  что  вычислять  оптимальное  значение  целевой функции не  нужно, оно находится во второй клетке индексной строки последней симплексной таблицы = -17/2. Из последней симплексной таблицы выписываем оптимальные  значения  переменных    =  (3/2;  1/2;  2;  0;  0)  Поскольку исходная  задача была преобразована, запишем её ответ: = (3/2; 1/2; 2; 0)  = 17/2. 

1.6 Типы оптимальных решений задач линейного программирования при решении симплекс-методом

      При решении задач симплекс-методом возможны следующие виды оптимальных решений.

      1. Единственность. Если оценки всех свободных векторов строго отрицательные,  то  полученный  опорный  план  является  оптимальным  и  единственным.

      2.  Альтернативный  оптимум  (множество  оптимальных  решений).

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

      3. Задача линейного  программирования  не имеет оптимального решения, так как целевая функция не ограничена снизу. Если в симплекс-таблице имеется положительная оценка, а все элементы данного столбца отрицательны и нулевые, то данный вектор можно ввести в базис. Однако никакой из базисных векторов нельзя из него вывести. Следовательно, дальнейшее уменьшение целевой функции возможно только при переходе к неопорному плану.

      4. Задача линейного  программирования  не имеет оптимального  решения, так как  система ограничений  противоречива. Поскольку при решении задачи  обычным  симплекс–методом  должен  быть  исходный  опорный  план,  то система линейных уравнений заведомо непротиворечива. Следовательно, такой случай не может встретиться при решении обычным симплекс-методом.

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

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

      Графический метод является наглядным и простым методом решения задач линейного программирования. Однако область его применения ограничена размерностью задачи. Если задача представлена в стандартной форме, то количество переменных должно быть не более трёх. Если исходная представлена в канонической  форме,  то  она  должна  быть  предварительно  преобразована  к стандартной форме.

      Можно оценить возможность решения такой задачи. Пусть задача в канонической форме имеет n переменных и m ограничений. Задача может быть решена графическим методом, если n – m ≤ 3, когда все уравнения системы линейно независимы или в общем случае, если n – r ≤ 3, где r – количество линейно  независимых  уравнений,  или  ранг  матрицы,  состоящей  из  коэффициентов при переменных в уравнениях системы ограничений.

      Алгоритм  графического метода

      1.  Проверяется  находится  ли  исходная  ЗЛП  в  стандартной   форме,  если нет, то задачу  необходимо преобразовать к стандартной форме.

      2.  Определяется количество неизвестных переменных. Если это количество больше трёх, то задача не может быть решена графическим методом. Существуют другие эффективные методы решения таких задач.

      3.  Строится область допустимых значений переменных для ЗЛП.

      4. Строится направляющий вектор  .

      5.  Перпендикулярно  направляющему   вектору  через  ОДЗ  проводится  исходная изоцель.

      6.  Проводится мысленное перемещение  исходной изоцели в направлении

вектора  ,  если  определяется  максимальное  значение  целевой функции или в противоположном направлении,  если  определяется  её  минимальное значение, до тех пор, пока изоцель не станет опорной к ОДЗ. Точки пересечения опорной изоцели и ОДЗ и будут оптимальными точками задачи.

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

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

2.2 Типы оптимальных решений задач линейного программирования при решении графическим методом

             При решении задач линейного программирования графическим методом возможны следующие случаи.

      1.  Единственность оптимального решения.  В этом случае опорная изоцель  имеет с ОДЗ только одну  общую точку.

      2.  Альтернативный  оптимум  (множество   оптимальных  решений).  В   этом случае опорная изоцель  совпадает с одной из сторон ОДЗ многоугольника в двухмерном  пространстве,  а  в  трёхмерном  пространстве  с  одной  из  граней многогранника.

      В данном случае целевая функция достигает  своего максимального значения в  любой точке отрезка [A;B]:  [A;B]  и записывается в виде выпуклой комбинации  , .

      3.  Задача  линейного  программирования  не  имеет  оптимального  решения,  так как целевая функция не  ограничена сверху, если требуется найти максимум целевой функции (или снизу, если требуется найти минимум).

      4.  Задача линейного программирования  не имеет решения, так как  система ограничений противоречива,  то есть ОДЗ=∅.

      5.  Если ОДЗ состоит из одной  точки, то в этой точке z принимает своё максимальное и минимальное значение.

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

      Решить  следующую  задачу  линейного  программирования графическим методом:

      Задача  находится в стандартной форме  и имеет две переменные и, следовательно, может быть решена графическим методом.