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

МИНЕСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ ЧЕЛЯБИНСКОЙ  ОБЛАСТИ

     ЧЕЛЯБИНСКИЙ ГОСУДАРСТВЕНЫЙ ПРОМЫШЛЕНО-ГУМАНИТАРНЫЙ ТЕХНИКУМ ИМЕНИ А.В ЯКОВЛЕВА 
 
 
 
 
 
 
 

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

     КП. 230105.51.ММ.-01

     Вариант-5 
 
 
 
 
 
 

     Выполнил:

     Студент 307 группы

     Русин Юрий

     Проверил  преподаватель:

     Еркибаева Л.Х.  
 

     Челябинск, 2010

 

      Содержание 

Введение…………………………………………………………………………...3

ГЛАВА I. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ МЕТОДОМ

     1. Линейное программирование………………………………………............5

     2. Основная задача линейного программирования………………….............7

     3. Графический метод решения задачи линейного

программирования…………………………………………………………...........9

     4. Методика решения задач линейного программирования               графическим методом…………………………………………………………...10

     5. Сведения о линейном программировании в электронной

таблице Excel…………………………………………………………………….12

ГЛАВА II. ПРИМЕНЕНИЕ ГРАФИЧЕСКОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ПРАКТИКЕ

     1. Построение математической модели……………………………………..14

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

методам…………………………………………………………………………...16

     3. Решение задачи с помощью электронной таблицы Excel………………18

Заключение ………………………………………………………………………23

Список литературы………………………………………………………………24

   
 
 
 
 
 
 
 

     Введение 

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

     Термин "Исследование операций" ("Operation Research") заимствован из западной литературы. Сейчас, пожалуй, нельзя точно назвать, ни дату его возникновения, ни автора, да и вряд ли найдется исчерпывающее определение этого понятия.

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

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

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

     Тема «Решение задач линейного программирования графическим методом» актуальна в современном мире,  потому что графический метод довольно прост и нагляден для решения задач линейного программирования. Графический метод применяется при решении задач линейного программирования возникшего во многих областях, например экономике. 

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

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

• Изучить теоретический материал по теме курсового проекта.
• Построить математическую модель данной задачи.
• Решить задачу графическим методом.
• Решить задачу с помощью электронных таблиц Excel.

 
 
 
 
 
 
 
 
 
 

ГЛАВА I. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ МЕТОДОМ 
 

1. Линейное программирование 
 

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

     Итак, линейное программирование возникло после  Второй мировой войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря  возможности широкого практического  применения, а так же математической «стройности».  
       Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.

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

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

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

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

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

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

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

2. Основная задача линейного программирования 

     Основная задача линейного программирования (ОЗЛП) ставится следующим образом: Имеется ряд переменных . Требуется найти такие их неотрицательные значения, которые удовлетворяли бы системе линейных уравнений:

                                       {1.1} 

     и, кроме того, обращали бы в минимум  линейную целевую функцию (ЦФ)

     

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

      

     Допустимым  решением ОЗЛП называют любую совокупность переменных , удовлетворяющую уравнениям (1.1).

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

     На  практике ограничения в задаче линейного  программирования часто заданы не уравнениями, а неравенствами. В этом случае можно перейти к основной задаче линейного программирования.

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

                                                {1.2}

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

         

     Введём уравнения:

                                                    {1.3} 
 
где - добавочные переменные, которые также как и являются неотрицательными.

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

     Коэффициенты  в формуле (1.3) перед  равны нулю. 
 
 
 
 
 
 

     3. Графический метод решения задачи линейного программирования 

     Графический метод довольно прост и нагляден для решения задач линейного  программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

     Каждое  из неравенств задачи линейного программирования (1.2) определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (1.2) ОДР является пустым множеством.