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

Оглавление

  Введение…………………………………………………………………………..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 Описание симплексной таблицы

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

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

      

                                            , 
                                                             , 

      

,

      

.