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

Федеральное Государственное образовательное  учреждение

среднего  профессионального образования

Магаданский политехнический техникум 
 
 
 
 

КУРСОВОЙ  ПРОЕКТ 

ПО ДИСЦИПЛИНЕ:               МАТЕМАТИЧЕСКИЕ МЕТОДЫ

          НА ТЕМУ:                РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО                        ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ 
           

КП-1. 3-ПЭВМ-23.0189.2011 
 
 
 

Выполнил:         Аноним М.В. 

Преподаватель-руководитель курсового проекта:  Гунькина Т.В. 
 
 
 
 
 
 

Магадан

2011

 

СОДЕРЖАНИЕ

 

  ВВЕДЕНИЕ

 

Тема  данной курсовой работы «Определение оптимального плана производства пушнины для зверофермы»

     В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся  в нахождении в заданной области  точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства. Изучение этого круга задач и методов их решения привело к созданию новой научной дисциплины, получившей позднее название линейного программирования. В конце 40-х годов американским математиком Дж. Данцигом был разработан эффективный метод решения данного класса задач – симплекс-метод. К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Определение наилучшего состава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие. Решение таких задач дает большие выгоды как народному хозяйству в целом, так и отдельным его отраслям.

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

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

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

      Для достижения цели следует реализовать следующие задачи:

  1. изучение раздела математического программирования;
  2. изучение метода решения задачи;
  3. составление алгоритма решения задачи;
  4. решение задачи с использованием изученного метода;
  5. проверка решение задачи с использованием табличного процессора Microsoft                                                                                          

        Excel;

  1. анализ полученных результатов решения задачи.

 

1. ОБЩАЯ ЧАСТЬ

 
 

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

    1. Цель  курсового проектирования
 

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

      Для достижения цели следует выполнить  следующие задачи:

  1. изучение раздела математического программирования;
  2. выбор метода решения задачи;
  3. составление алгоритма решения задачи;
  4. решение задачи с использованием выбранного метода;
  5. проверка решение задачи с использованием  электронных таблиц Microsoft Excel;
  6. анализ полученных результатов решения задачи.
    1. Актуальность  выбранной темы
 

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

      Оптимальное решение – это выбранное по какому-либо критерию оптимизации наиболее эффективное из всех альтернативных вариантов решение. К методам  оптимизации относятся анализ, прогнозирование и моделирование. Моделирование может быть физическое и математическое. Физическое моделирует предметы, а математическое – процессы.

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

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

      Теоретической основой и практическим инструментом анализа и прогнозирования решений  в экономике и бизнесе являются экономико-математические модели и  проводимые по ним расчёты.

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

    1.3. Описание теоретического  материала

 

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

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

     Применение  симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1, ..., Xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1, ..., Xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1.

     Данная  формальная модель задачи линейного  программирования обычно задается в  форме, так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода:

                                                  Симплекс-таблица

  1 X1 X2 ... Xm Xm+1 ... Xn
X0 A0,0 0 0 ... 0 A0,m+1 ... A0,n
X1 A1,0 1 0 ... 0 A1,m+1 ... A1,n
X2 A2,0 0 1 ... 0 A2,m+1 ... A2,n
... ... ... ... ... ... ... ... ...
Xm Am,0 0 0 ... 1 Am,m+1 ... Am,n
 

     Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует  определенному ограничению-равенству  задачи. Свободные члены ограничений  составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X1, ..., Xm). Сверху от таблицы приведен набор всех переменных задачи, где Xm+1, ..., Xn - свободные переменные задачи.

     На  начальном шаге алгоритма симплекс-метода должно быть выбрано базисное допустимое решение (X1, ..., Xm) >= 0 при Xj = 0 (j = m+1, ..., n), следовательно, все свободные члены ограничений Ai,0 >= 0 (i = 1, ..., m). Когда это условие выполнено, симплекс-таблица называется прямо-допустимой, так как в этом случае базисные переменные, равные Ai,0, определяют допустимое решение прямой задачи линейного программирования. Если все коэффициенты целевой функции A0,j >= 0 (j = 1, ..., m), то симплекс-таблица называется двойственно-допустимой, поскольку соответствующее решение является допустимым для двойственной задачи линейного программирования.

     Если  симплекс-таблица является одновременно прямо и двойственно допустимой, т.е. одновременно все Ai,0 >= 0 и A0,j >= 0, то решение оптимально.

     Действительно, поскольку допустимыми являются лишь неотрицательные значения управляемых  параметров, то изменение целевой  функции за счет вариации свободных переменных, через которые она выражена, возможно только в сторону увеличения, т.e. будет ухудшаться. Если среди ее коэффициентов имеются A0,j < 0, то значение целевой функции еще можно уменьшить (т.e. улучшить), увеличивая значение любой свободной переменной Xj с отрицательным коэффициентом A0,j при побочном уменьшении базисных переменных, чтобы оставались справедливы ограничения задачи. Теоретически можно использовать любую свободную переменную Xj с A0,j < 0, но на практике обычно действуют в соответствии со стратегией наискорейшего спуска, выбирая минимальный элемент A0,p < 0 из всех отрицательных A0,j <&nbsp0:

 

     Столбец p симплекс-таблицы, соответствующий выбранному коэффициенту A0,p < 0, называется ведущим столбцом. Свободная переменная ведущего столбца должна быть введена в базис вместо одной из текущих базисных переменных. Очевидно, из базиса следует исключить такую переменную Xq, которая раньше других обращается в нуль при увеличении переменной Xp ведущего столбца.

     Её  индекс легко определить, если среди положительных элементов ведущего столбца p найти элемент, минимизирующий отношение (Ai,0 / Ai,p):

     Элемент Aq,p называется ведущим элементом, cтрока q симплекс-таблицы, содержащая ведущий элемент, называется, соответственно, ведущей строкой. Переменная ведущей строки Xq заменяется в базисе переменной ведущего столбца Xp и становится свободной переменной с значением 0, в то время как новая базисная переменная Xp достигнет максимально возможного значения, равного:

     После указанного взаимообразного обмена переменными Xp и Xq между наборами свободных и базисных переменных нужно модифицировать исходную каноническую модель задачи путем приведения ее к диагональной форме относительно нового множества базисных переменных. Для указанного преобразования можно формально использовать процедуру исключения Гаусса, которая, как известно, состоит из двух элементарных операций, применяемых к системе алгебраических уравнений ( в данном случае ограничений - равенств):

  • умножение уравнения E1(X) = 0 на константу K1 и замена уравнения E1(X) = 0 уравнением K1*E1(X) = 0;
  • сложение уравнений E1(X) = 0 и E2(X) = 0 c последующей заменой уравнения E2(X) = 0 уравнением E1(X) + E2(X) = 0.

     Исключения  Гаусса позволяют привести систему  уравнений к диагональной форме  относительно желаемого множества переменных. В данном случае исключение Гаусса применяется так, чтобы все элементы симплекс-таблицы в ведущем столбце, кроме ведущего элемента Aq,p, стали нулевыми, а ведущий элемент стал равным единице: Ai,p = 0, если i не равно q и Ai,p = 1, если i = q.

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

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

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

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

      Любые m переменных системы m линейных уравнений с n переменными называются базисными (основными), если определитель матрицы размерности m×m коэффициентов при них отличен от нуля. Остальные переменных называются свободными (неосновными).

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

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

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

      На  практике удобнее для выяснения  вопроса: является ли найденный план оптимальным, пользоваться оценками переменных , которые вычисляются по формулам:

                                                                                 (1.3)

      Тогда критерии оптимальности решения  формулируются иначе, а именно:

  • при отыскании максимума функции: если оценки всех переменных неотрицательны, то значение целевой функции максимально и решение оптимально;
  • при отыскании минимума функции: если оценки всех переменных не положительны, то значение целевой функции минимально и решение оптимально.

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

      Практические  расчеты при решении реальных задач, если не используется ЭВМ, проводят в так называемых симплексных  таблицах.

      Рассмотрим одну из часто решаемых симплексным методом оптимизационных задач − задачу о распределении ресурсов.

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

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

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

      Решение задачи начнём с допущения, что неизвестная  x1 обозначает количество телевизоров, x3 − количество магнитофонов, а x3 − количество моноблоков, выпускаемых предприятием. Тогда получаем, что затраты по ресурсу "Пластиковые формы" на данном предприятии, согласно заданным табл. 1.1 технологическим коэффициентам определяются зависимостью . При этом затраты по ресурсу «Пластиковые формы» не должны превышать 150 единиц, заданных в качестве имеющегося на предприятии запаса.

          Технологические коэффициенты, прибыль и запасы ресурсов Таблица 1.1.

            
     
     
     

      Таким образом, получаем первое ограничение на количество выпускаемой продукции:                                            (1.4)

      Аналогично  составляются ограничения по другим ресурсам, и в результате получаются еще три ограничения по ресурсам:

                

                                      (1.5)

                

                                                (1.6)

                

                                                (1.7)

      Кроме того, поскольку количество выпущенной продукции не может быть отрицательной величиной, естественно потребовать, чтобы выполнялись неравенства

                                                                  (1.8)

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

                                              (1.9)

   Решение задачи оптимизации заключается в нахождении таких количеств выпускаемой продукции, которые обеспечивают функции прибыли максимальное значение при заданных ограничениях по количеству имеющихся на предприятии ресурсов. Каждое из решений системы неравенств (1.5) − (1.7),будет допустимым

решением (планом) для данной задачи. Оптимальным решением называется то из

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

       Таким образом, объединяя составленные по данным табл.1.1 зависимости (1.5) − (1.8), получаем математическую модель задачи о распределении ресурсов: 
 
 
 

                                    (1.10)

      Естественное  ограничение о не отрицательности количеств выпускаемой продукции вытекает из смысла производственной задачи.

      Решение сформулированной задачи может быть найдено, например, симплексным методом.

       Поскольку ограничения  задачи являются неравенствами "с  недостатком", введём дополнительные вспомогательные переменные которые называют "выравнивающими", и с помощью них превратим неравенства в равенства: 
 
 
 

            (1.11)

      Теперь  система (1.11) является системой четырёх  линейных алгебраических уравнений  относительно семи неизвестных. Решения  системы (1.11) находим симплексным методом в табл. 1.2, с использованием метода Жордана − Гаусса для решения систем линейных алгебраических уравнений.

      Метод Жордана − Гаусса − это метод нахождения базисных решений систем m линейных алгебраических уравнений относительно n неизвестных, если n≥ m, в специальных таблицах, позволяющих в ходе решения замещать базисный элемент одним из свободных переменных. Количество N различных базисных решений определяется формулой:   

                                                   (1.12)                                        

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

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

      При решении системы (1.11) и нахождении того её базисного решения, которое  обеспечивает максимум рассматриваемой  функции прибыли (целевой функции) F , использованы критерии симплексного метода для задач линейного программирования. Стрелки в табл. 1.2 указывают разрешающий столбец и разрешающую строку, на их пересечении находится разрешающий элемент.

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