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

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

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

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

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

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

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

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

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

Магадан

2011

 

СОДЕРЖАНИЕ

 

  ВВЕДЕНИЕ

 

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

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

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

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

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

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

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

        Excel;

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

 

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

 
 

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

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

 

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

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

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

2. Актуальность  выбранной темы

 

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

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

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

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

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

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

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

 

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

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

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

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

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

 

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

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

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

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