Содержание:

 

Введение

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

      Линейное  программирование представляет собой  наиболее часто используемый метод  оптимизации. К числу задач линейного  программирования можно отнести задачи:

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

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

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

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

      Математическое  программирование – это прикладная отрасль математики, которая является теоретической основой решения задач оптимального планирования.

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

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

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

      1. Изучить понятие методов математического программирования.

      2. Составить общую задачу линейного программирования.

      3.Рассмотреть на примерах  решения задач линейного программирования.

 

1. Методы линейного программирования

 

    Различают детерминированные и одноцелевые задачи, исследованием которых занимается математическое программирование. Слово программирование в данном случае означает "планирование".

    К математическому программированию относится:

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

    Нелинейное  программирование: целевая функция  и ограничения могут быть нелинейными  функциями;

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

    Динамическое  программирование: для отыскания  оптимального решения планируемая  операция разбивается на ряд шагов (этапов) и планирование осуществляется последовательно от этапа к этапу. Однако выбор метода решения на каждом этапе производится с учетом интересов операции в целом;

    Теория  графов: с помощью теории графов решаются многие сетевые задачи, связанные  с минимальным протяжением сети, построение кольцевого маршрута и т.д [7].

    Стохастическое  линейное программирование

    Бывает  много практических ситуаций, когда  коэффициенты ci целевой функции, коэффициенты aij в матрице коэффициентов, коэффициенты ограничений bi - являются случайными величинами. В этом случае сама целевая функция становится случайной величиной, и ограничения типа неравенств могут выполняться лишь с некоторой вероятностью. Приходится менять постановку самих задач с учётом этих эффектов и разрабатывать совершенно новые методы их решения. Соответствующий раздел получил название стохастического программирования [4].

    Геометрическое  программирование

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

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

    Теория  игр пытается математически объяснить  явления возникающие в конфликтных  ситуациях, в условиях столкновения сторон. Такие ситуации изучаются психологией, политологией, социологией, экономикой [8].

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

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

    

 ,                                 (1.1)  

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

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

    Специфика определения наиболее приемлемого  решения стала исследоваться  еще в древности, ее истоки проистекают  от задач поиска экстремума в математическом анализе и вариационном исчислении [9]. 

1.1. История проблемы поиска экстремума

 

 

    Общепринятыми являются такие утверждения:

    отрезок прямой линии отражает самое короткое расстояние между его конечными  точками;

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

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

    Феномены  максимизации и минимизации такого вида использовались еще древними греческими математиками. Но, стоит отметить, что те или иные формулировки не предполагали никакого доказательства [8]. В данном контексте, можно отметить ученого I в. н.э. Герона Александрийского. Еще в древности определили, что световой луч, исходящей точкой которого является тока Р и который совпадает с плоским зеркалом L, является отражаемым в направлении точки Q так, что PR и QR создают одинаковые углы с зеркалом (рис. 1.1, а). Герон выдвинул предположение — если - любая точка от зеркала, которая не является эквивалентной R, то сумма отрезков является больше по сравнению . Такое утверждение определяет истинный путь луча PRQ между P и Q, который представляется в виде кратчайшего пути от P к Q с накладкой на зеркало L. Это предположение и послужило основанием теории геометрической оптики.   

      
 

      
 

      
   

      
 

    

 
Рис. 1.1. Теорема Герона (а); проблема Штейнера (б); кратчайшая система путей, соединяющих данные точки (в); кратчайшие системы путей, соединяющих вершины квадрата (г, д)  

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

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

1.2. Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП

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

   Несколько слов о самом термине линейное программирование. Он требует правильного понимания. В данном случае программирование - это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий [8].

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

   Круг  задач, решаемых при помощи методов  линейного программирования достаточно широк. Это, например:

   ·  задача об оптимальном использовании ресурсов при производственном планировании;

   ·  задача о смесях (планирование состава продукции);

   ·  задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

   ·  транспортные задачи (анализ размещения предприятия, перемещение грузов).

   Линейное  программирование – наиболее разработанный  и широко применяемый раздел математического  программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим: