Симплекс-метод

Содержание

Введение 3

1 Симплекс-метод 5

1.1 Общая характеристика  симплекс-метода 5

1.2 Общая идея  симплексного метода 12

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

2 Решение  задачи при помощи симплекс  – метода 20

2.1 Постановка  задачи 20

2.2 Решение  поставленной задачи 21

2.3 Решение задачи при помощи табличного процессора Microsoft Excel 25

Список используемых источников 32

Приложение  А – Решение элементов 33

Приложение  Б – Решение элементов 34

Приложение  В - Презентация 35

Приложение  Г - Диск 44

 

Введение

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

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

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

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

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

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

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

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

Задачи курсовой работы:

• изучить теоретический материал;
• на примерах рассмотреть симплекс метод.

В первой главе курсовой работы рассматриваются:

• общая характеристика симплекс-метода;
• алгоритм симплексного метода решения;
• понятие базисного решения – основа симплекс-метода;
• симплексный метод решения задач линейного программирования.

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

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

 

1 Симплекс-метод

1.1 Общая характеристика симплекс-метода

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

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

Одним из наиболее ярких событий в мире математике в XX веке явилось открытие Дж. Б. Данцигом в 1940 – годах метода решения общей задачи линейного программирования, получившего название «симплекс – метод».

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

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

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

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

В 1975 году академик Л.В.Канторович и американец профессор Т. Купманс получили Нобелевскую премию по экономическим наукам за «вклад в разработку теории и оптимального использования ресурсов в экономике».

Летом 1939 года была сдана в набор книга Л.В.Канторовича «Математические методы организации и планирования производства», в которой закладывались основания того, что ныне называется математической экономикой.

В 1939 год. Говорят, что истина рождается ересью и, увы, так случилось и с идеями Л.В.Канторовича в области экономики. Они не встретили понимания в момент их зарождения, были объявлены ересью, и его работа была прервана.

Концепции Леонида Витальевича  вскоре после войны были переоткрыты на западе. Американский экономист Т. Купманс в течение многих лет привлекал внимание математиков к ряду задач, связанных с военной тематикой. Он активно способствовал тому, чтобы был организован математический коллектив для разработки этих проблем.

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

Американский математик  А.Данциг в 1947 году разработал весьма эффективный  конкретный метод численного решения  задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в  течении пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.

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

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

Л.В.Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве. При  этом (одновременно с Данцигом, но, не зная его работ) он разрабатывает  метод, позже названный симплекс-методом.

Как только в 50-е годы образуется маленький просвет и кое-что из запретного становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методам оптимального планирования.

Начиная с 1960 года Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (ему присуждена совместно с В.С.Немчиновым и В.В.Новожиловым) и Нобелевской премией в 1975 году.

За прошедшие с тех  пор годы было предложено не только много разновидностей симплекс-метода, учитывающих особенности различных  подклассов задачи ЛП (блочные задачи, задачи со слабо заполненной матрицей условий A ={ai, j}), но и несколько принципиально иных методов решения задачи ЛП.

Некоторые из предложенных методов в теоретическом плане, например, с точки зрения характеристики сложности алгоритма, превосходят  симплекс-метод (известно, что симплекс-метод  обладает экспоненциальной сложностью, т.е. имеет экспоненциальную оценку трудоемкости на всем классе задач ЛП, тогда как такие алгоритмы, как метод эллипсоидов Хачияна (советского математика) и метод Крамаркара (американского исследователя) характеризуются полиномиальной сложностью).

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

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

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

Основная идея симплекс-метода достаточно просто иллюстрируется геометрически.

Каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей.

Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань.

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

Последовательность вычислений симплекс-методом можно разделить  на две основные фазы:

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

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

Существует двухфазный симплекс-метод. Если в условии задачи линейного программирования не все ограничения представлены неравенствами типа «≤», то далеко не всегда нулевой вектор будет допустимым решением.

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

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

Все ограничения задачи модифицируются согласно следующим правилам:

• ограничения типа «≤» переводятся на равенства созданием дополнительной переменной с коэффициентом «+1». Эта модификация проводится и в однофазном симплекс-методе, дополнительные переменные в дальнейшем используются как исходный базис;
• ограничения типа «≥» дополняются одной переменной с коэффициентом «−1». Поскольку такая переменная из-за отрицательного коэффициента не может быть использована в исходном базисе, необходимо создать ещё одну, вспомогательную, переменную. Вспомогательные переменные всегда создаются с коэффициентом «+1»;
• ограничения типа «=» дополняются одной вспомогательной переменной.

Соответственно, будет создано  некоторое количество дополнительных и вспомогательных переменных. В  исходный базис выбираются дополнительные переменные с коэффициентом «+1» и все вспомогательные. Решение, которому соответствует этот базис, не является допустимым.

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