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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


курсовая работа Задача линейного программирования: нахождение оптимального плана

Информация:

Тип работы: курсовая работа. Добавлен: 23.05.2012. Сдан: 2011. Страниц: 9. Уникальность по antiplagiat.ru: < 30%

Описание (план):


     Введение 
 

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


    1 Задача линейного программирования: нахождение оптимального плана 

         1.1 Теоретико-методическое описание метода линейного программирования

 
     В настоящее время линейное программирование является одним из наиболее употребительных  аппаратов математической теории оптимального принятия решений. Линейное программирование — математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование. Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Владение аппаратом линейного программирования необходимо каждому специалисту в области прикладной математики.
     Линейное  программирование - это наука о  методах исследования и отыскания  наибольших и наименьших значений линейной функции, на неизвестные которой  наложены линейные ограничения. Таким  образом, задачи линейного программирования относятся к задачам на условный экстремум функции. По типу решаемых задач методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования. Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.
     Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.
     В общем виде модель записывается следующим  образом:
    целевая функция представлена в формуле (1):
     f()= c1x1 + c2x2 + … + cnxn > max(min);                 (1)
    система ограничений выражена в формуле (2):
                                                    (2)
    требование неотрицательности представлено в формуле (3):
     xj ? 0,                       (3)
     При этом aij, bi, cj ( ,   ) – заданные постоянные величины.
     Задача  состоит в нахождении оптимального значения функции (1) при соблюдении ограничений (2) и (3).
     Систему ограничений (2) называют функциональными  ограничениями задачи, а ограничения (3) – прямыми.
     Решения, удовлетворяющие системе ограничений (2) условий задачи и требованиям  неотрицательности (3), называются допустимыми, а решения, удовлетворяющие одновременно и требованиям минимизации (максимализации) целевой функции, – оптимальными.
     Особенностью  задач линейного программирования является то, что экстремума целевая  функция достигает на границе  области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов  функции во внутренней точке области  допустимых значений. Отсюда -- необходимость разработки новых методов.
     К числу задач линейного программирования можно отнести задачи:
     1) рационального использования сырья и материалов;
     2) задачи оптимального раскроя;
     3) оптимизации производственной программы предприятий;
     4) оптимального размещения и концентрации производства;
     5) составления оптимального плана перевозок, работы транспорта (транспортные задачи);
     6) управления производственными запасами;
     7) и многие другие, принадлежащие сфере оптимального планирования.
     Линейное  программирование является одной из основных частей того раздела современной  математики, который получил название математического программирования.
     Задачи  линейного программирования с двумя  переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах, размерность  которых больше трех, графическое  решение невозможно.
     Графический метод довольно прост и нагляден. Он основан на геометрическом представлении  допустимых решений задачи. Каждое из неравенств задачи ЛП определяет на координатной плоскости некоторую  полуплоскость, а система неравенств в целом - пересечение соответствующих  плоскостей. Множество точек пересечения  данных полуплоскостей называется областью допустимых решений. ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлен выпуклым многоугольником, неограниченным выпуклой многоугольной областью, отрезком, лучом и т.д. В случае несовместности системы ограничений задачи ОДР является пустым множеством.
     При поиске оптимального решения задач  линейного программирования возможны следующие ситуации: существует единственное решение задачи, существует бесконечное  множество решений; ЦФ не ограничена; область допустимых решений- единственная точка; задача не имеет решений.
     Любая задача линейного программирования, независимо от вида записи, может быть приведена к стандартной и  канонической форме и решена симплексным  методом, который в определенном смысле является универсальным методом  ЛП. Алгоритм симплекс-метода носит  итерационный характер.
     Симплекс-метод  позволяет переходить от одного допустимого  базисного решения к другому, причем так, что значения целевой  функции непрерывно возрастают. Алгоритмы  симплекс-метода позволяют также  установить, является ли задача ЛП разрешимой.
     Переход от одного базиса к другому позволяет  находить решения почти всех задач  ЛП. Определив все крайние точки, можно вычислить значения целевой  функции и найти оптимальное  решение. Однако для больших значений m и n это практически невозможно.
     Алгоритм  решения задачи ЛП табличным симплексом-методом состоит из следующих этапов:
     1) рассчитывают и заполняют начальную симплекс-таблицу с допустимым единичным базисом, включая индексную строку.
     2) находят разрешающий столбец;
     3) находят разрешающую строку;
     4) рассчитывают методом Жордано-Гаусса все параметры матрицы;
     5) анализируют полученные данные в индексной строке.
     Таблицы симплекс-метода необходимо строить  до тех пор, пока не будет получен  оптимальный план. План будет считаться  оптимальным, если в последней индексной  строке симплекс-таблицы будут только нули и положительные числа.
     При построении симплексного метода предполагалось, что все опорные планы невырожденные, что обеспечивало получение оптимального плана за конечное количество шагов. В случае вырожденного плана вычисления производят аналогично, но в этом случае возможен возврат к старому базису, что приводи к так называемому  зацикливанию.
     Метод искусственного базиса применяется  при наличии в ограничении  знаков “равно”, “больше либо равно”, “меньше либо равно” и является модификацией табличного метода. Решение  системы производится путём ввода  искусственных переменных со знаком, зависящим от типа оптимума, т.е. для  исключения из базиса этих переменных последние вводятся в целевую  функцию с большими отрицательными коэффициентами , а в задачи минимизации - с положительными . Таким образом, из исходной получается новая - задача.
     Если  в оптимальном решении - задачи нет  искусственных переменных, это решение  есть оптимальное решение исходной задачи. Если же в оптимальном решении - задачи хоть одна из искусственных  переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.
     В основу модифицированного симплекс - метода положены такие особенности  линейной алгебры, которые позволяют  в ходе решения задачи работать с  частью матрицы ограничений. Иногда метод называют методом обратной матрицы.
     В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений  по частям, соответствующим текущим  базисным векторам. Указанная способность  делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени  счёта. Хорош для ситуаций, когда число переменных n значительно превышает число ограничений m.
     В целом, метод отражает традиционные черты общего подхода к решению  задач линейного программирования, включающего в себя канонизацию  условий задачи, расчёт симплекс-разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана-Гаусса.
     Особенности заключаются в наличии двух таблиц - основной и вспомогательной, порядке  их заполнения и некоторой специфичности  расчётных формул.
     Каждой  задаче линейного программирования можно определенным образом сопоставить  некоторую другую задачу, называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Сопоставляя формы записи прямой и двойственной задач, можно  установить между ними следующие  взаимосвязи:
     1. если прямая задача является  задачей максимизации, то двойственная  будет задачей минимизации, и  наоборот;
     2. коэффициенты целевой функции  прямой задачи становятся свободными  членами ограничений двойственной  задачи;
     3. свободные члены ограничений  прямой задачи становятся коэффициентами  целевой функции двойственной  задачи;
     4. матрица ограничений двойственной  задачи получается путем транспортирования  матрицы ограничений прямой задачи;
     5. знаки неравенств в ограничениях  изменяются на противоположные;
     6. число ограничений прямой задачи  равно числу переменных двойственной  задачи, и наоборот.
     Отыскание решения задачи двойственным симплекс-методом  включает в себя следующие этапы:
     1. Находят псевдоплан задачи.
     2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.
     3. Выбирают разрешающую строку  с помощью определения наибольшего  по абсолютной величине отрицательного  числа столбца вектора Р0 и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)-и строки к соответствующим отрицательным элементам разрешающей строки.
     4. Находят новый псевдоплан и повторяют все действия начиная со второго этапа.
     Двойственный  симплексный метод называют также  методом последовательного уточнения  оценок, поскольку угловые точки  задачи, возникающие при итерациях, можно рассматривать как приближенные значения точной оценки у*, т. е. как  приближенные оценки влияния условий  задачи на величину минимума целевой  функции.
     Задача  целочисленного программирования формулируется  так же, как и задача линейного  программирования, но включается дополнительное требование, состоящее в том, что  значения переменных, составляющих оптимальное  решение, должны быть целыми неотрицательными числами.
     Метод решения таких задач, предложенный Гомори, основан на симплексном методе и состоит в следующем. Симплексным  методом находится оптимальный  план задачи без учета условия  целочисленности. Если оптимальный план целочисленный, то вычисления заканчивают; если же оптимальный план содержит хотя бы одну дробную компоненту Xi, то накладывают дополнительное ограничение, учитывающее целочисленность компонент плана, и вычисления симплексным методом продолжают до тех пор, пока либо будет найден целочисленный оптимальный план, либо доказано, что задача не имеет целочисленных оптимальных планов.
     Особенно  широкое распространение линейное программирование получило в экономике, так как исследование зависимостей между величинами, встречающимися во многих экономических задачах, приводит к линейной функции с линейными  ограничениями, наложенными на неизвестные. Линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: рационального использования сырья и материалов; задачи оптимизации раскроя; оптимизации производственной программы предприятий; оптимального размещения и концентрации производства; составления оптимального плана перевозок, работы транспорта; управления производственными запасами; и многие другие, принадлежащие сфере оптимального планирования.
     Необходимым условием постановки задачи линейного  программирования являются ограничения  на наличие ресурсов, величину спроса, производственную мощность предприятия  и другие производственные факторы.
     Сущность  линейного программирования состоит  в нахождении точек наибольшего  или наименьшего значения некоторой  функции при определенном наборе ограничений, налагаемых на аргументы  и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных, которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции, называется оптимальным планом задачи.
     Методы, с помощью которых решаются задачи линейного программирования подразделяются на универсальные и специальные.
     Линейное  программирование – наиболее разработанный  и широко применяемый раздел математического  программирования.  

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

     Симплексный метод решения задач линейного  программирования – вычислительная процедура, основанная на принципе последовательного  улучшения решений – перехода от одной базисной точки  к другой, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум.
     Симплекс-метод  был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.
     Симплекс-метод является основным в линейном программировании. Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов (за исключением т. н. вырожденной задачи, при которой возможно явление “зацикливания”, т. е. многократного возврата к одному и тому же положению). Название метод получил от термина “n-мерный симплекс”. Геометрическая интерпретация метода состоит в последовательном движении по вершинам симплекса.
     Процесс применения симплексного метода предполагает реализацию трех его основных элементов:
     1) способ определения какого-либо  первоначального допустимого базисного  решения задачи;
     2) правило перехода к лучшему  решению; 
     3) критерий проверки оптимальности  найденного решения. 
     Симплексный метод включает в себя ряд этапов и может быть сформулирован в  виде четкого алгоритма. Это позволяет  успешно программировать и реализовывать  его на ЭВМ. Задачи с небольшим  числом переменных и ограничений  могут быть решены симплексным методом  вручную.
     Алгоритм  симплекс-метода позволяет также  установить, является ли задача линейного  программирования разрешимой.
     Алгоритм:
     - Исходная модель задачи линейного  программирования приводится к  канонической форме и определяются базисные и небазисные переменные.
     - Заполняется симплексная таблица.  Пример симплексной таблице к  математической модели показан в таблице 1. В столбике сi записываются коэффициенты взятые из целевой функции при базисных переменных. В строке сj – коэффициенты взятые из целевой функции. В столбце «Базис» – базисные переменные. В столбце В – свободные числа (правые части ограничений). Под переменными х1, х2, …,хn записываются коэффициенты взятые из ограничений при этих переменных. В нижней строке Z таблицы располагаются значение целевой функции, а в остальных кроме последней относительные оценки каждой переменной. Значение целевой функции вычисляется как сумма произведений сj и В. Аналогично вычисляются все относительные оценки с минус коэффициент сj.
     - Задача решается до тех пор пока:
     а) все относительные оценки неотрицательны в этом случае задача уже решена;
     б) среди относительных оценок соответствующих  исходным переменным есть 0, задача имеет  бесконечное множество решений;
     в) среди относительных оценок нет  отрицательных чисел, но в базисе есть искусственные переменные (задача не имеет решений);
     г) среди относительных оценок есть отрицательные (задача еще не решена, переход к следующей операции).
     - Переход к следующей итерации  начинается с выбора главного  столбца. Он соответствует наибольшему по модулю относительной оценки (выбираются только отрицательные оценки). Поиск главной строки выполняется следующим образом: числа столбца В делятся на числа главного столбца (0 и отрицательные числа в главном столбце пропускаются) результаты деления записываются в столбец Q. Главная строка соответствует минимальному Q. На пересечении главного столбца и главной строки находится главный элемент таблицы.
     - Пересчет таблицы. Переход к  новой итерации. Вместо переменной  главной строки и ее коэффициента  записывается переменная главного  столбца и ее коэффициент (переменная  входит в базис). Все числа главной  строки делятся на главный  элемент. Все остальные числа  главного столбца заполняются  0. Все остальные ячейки таблицы  вычисляются по правилу прямоугольника. Правило прямоугольника - из произведения  чисел главной диагонали вычитается  произведение побочной диагонали и результат делится на главный элемент. Диагональ проходящая через главный элемент называется главной диагональю.
    - Вычисляется  значение целевой функции и  относительных оценок.
    - Переход  к проверке оптимальности найденного  решения. Если не оптимально, то переход к следующей итерацие. 
     

     Таблица 1 – Пример симплексной таблицы к математической модели
№ табл. cj ci
Базис B c1 c2 0 0 0 Q
x1 x2 x3 x4 x5
0 0 x3 b1 a11 a12 1 0 0  
0 x4 b2 a21 a22 0 1 0  
0 x5 b3 a31 a32 0 0 1  
Z 0 - c1 - c2 0 0 0  
 

 

    2 Практическая часть 

    2.1 Построение математической модели задачи 

     Фирма рекламирует свою продукцию через 4 СМИ:
     1) Телевидение
     2) Радио
     3) Газеты
     4) Афиши
     Пусть х1 –это телевидение, х2 – радио, х3 – газеты и х4 – афиши.
     Тогда увеличение прибыли от использования всех 4 видов СМИ будет записан как целевая функция:
     F(x)=11 х1+3 х2+7 х3+4 х4 >max    
     Составим  ограничения:
    По  распределению полного рекламного бюджета:
     1 х1+1 х2+ 1 х3+1 х4?500000      
     По  распределению рекламного бюджета на телевидение:
     х1?200000       
    По  распределению рекламного бюджета  на афиши:
     1 х4
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.