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

Оглавление

  Введение…………………………………………………………………………..3 

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

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

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

     1.3 Описание симплексной таблицы. ……………………………………….8

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

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

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

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

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

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

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

Заключение………………………………………………………………………..20

Библиографический список……………………………………………………..21 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

      Успешная  реализация  достижений  научно-технического  прогресса  тесно связана  с  использованием  математических  методов  и  средств  вычислительной техники при решении задач  из различных областей человеческой деятельности.

      Большое  значение приобретает использование указанных методов и средств при решении экономических задач. Для эффективного функционирования экономических объектов необходимо установить оптимальное управление во всех структурных  подразделениях,  которое  позволяет  рационально  использовать трудовые и производственные ресурсы.

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

      Математическое  программирование  – это  раздел  прикладной  математики, который разрабатывает теоретические основы и методы решения экстремальных задач.

      К  математическому  программированию  относятся  ряд  разделов,  основными из которых являются следующие разделы.

      1.  Линейное  программирование.  К   данному  разделу  относятся   задачи,  в которых целевая  функция и ограничения задачи  являются линейными. 

      2.  Нелинейное программирование. Данный  раздел изучает задачи, в которых целевая функция и (или) ограничения могут быть нелинейными.

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

      4.  Целочисленное  программирование.  К  данному  разделу  относятся  задачи,  в  которых  неизвестные  переменные  могут  принимать только  целочисленные значения.

      5.  Стохастическое  программирование.  Данный  раздел  изучает  задачи,  в которых содержатся случайные  величины в целевой функции и (или) в ограничениях.

      6.  Параметрическое программирование. В этом разделе рассматриваются

      задачи,  в  которых  коэффициенты  при  неизвестных  переменных  в  целевой  функции и (или) в ограничениях зависят  от некоторых параметров.

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

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

      Если  задача  линейного  программирования  имеет  значительное  количество переменных, то она не может быть решена графическим методом. Для решения таких  задач  используются  другие  методы,  в частности  метод последовательного «улучшения» решения задачи – симплексный метод (или симплекс-метод).

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

      Симплекс–метод  основан на ряде следующих теорем.

      Теорема 1. О множестве планов задачи линейного программирования.

      Множество всех планов задачи  линейного программирования является выпуклым множеством.

      Доказательство.

      Возьмём два произвольных плана задачи линейного  программирования и 

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

       ,

       , где:

        – матрица коэффициентов  при переменных в ограничениях  задачи; 

        – вектор правых частей ограничений задачи.

      Возьмём два произвольных плана   и .

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

                                        ,  .                                   (*)

      Подставим данную точку в левую часть  системы ограничений 

        Полученная точка    удовлетворяет ограничениям задачи. Остаётся доказать неотрицательность координат точки  .

      Рассмотрим  выпуклую комбинацию (*). Так как      и    – планы задачи по предположению, то их координаты неотрицательные.

      Так как скаляры λ  и  (1-λ) − неотрицательные (по условию выпуклости), то произведение  неотрицательных  скаляров  на  неотрицательные  векторы  будет неотрицательными  векторами.  Сумма  неотрицательных  векторов  есть  вектор неотрицательный. Следовательно, координаты вектора   неотрицательные.

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

      Теорема 2. О целевой функции задачи линейного программирования

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

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

      Определение.  План  ,  положительным координатам которого  соответствуют линейно независимые векторы, называется опорным планом ЗЛП.

      Теорема 3. Достаточные условия угловой точки

      Пусть    система    векторов    , , …,  , (k  ≤ n)    в    разложении

        (**)  является  линейно независимой и такой,  что , где все (k ≤ n) , то      точка является угловой точкой ОДЗ.

      Теорема 4. Необходимые условия угловой точки

      Пусть точка  является угловой точкой ОДЗ, тогда векторы в  разложении (**),  соответствующие положительным значениям переменных будут линейно независимыми.

      Следствия из теорем

      Следствие  1.  Опорный план  имеет не  более m  положительных координат. Если он имеет ровно m положительных координат, то такой опорный план называется невырожденным, в противном случае – вырожденным.

      Следствие 2. Каждая угловая точка ОДЗ является опорным планом. 

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

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

      Симплекс-метод  является  целенаправленным  перебором  части  угловых точек (метод последовательного улучшения опорного плана).

      Для  решения  задачи  симплекс-методом  мы  должны  ответить  на  два вопроса:

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

      2. Как перейти от одного опорного  плана к другому. 

      1.3 Описание симплексной таблицы

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

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

                                            , 
                                                             , 

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

      соответствующие  коэффициенты  при  переменных  целевой  функции.  Столбец состоит из  правых  частей  уравнений.  На  пересечении  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 Пример  решения   задачи линейного   программирования графическим методом

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

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