Частное образовательное учреждение профессионального  образования

«КРАСНОДАРСКИЙ  ТЕХНИКУМ УПРАВЛЕНИЯ, ИНФОРМАТИЗАЦИИ И  СЕРВИСА»

Цикловая  комиссия информационных и технических  дисциплин 
 
 
 
 
 
 
 

Скачков Антон Юрьевич

Студент группы ПО-3.1 
 

ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ, ДВОЙСТВЕННОЙ ЗАДАЧЕ ОБ ИСПОЛЬЗОВАНИИ РЕСУРСОВ 
 

Курсовая  работа

По дисциплине «Математические методы»

Специальность 230105 «Программное обеспечение ВТ и  АС» 
 
 
 
 
 
 

Научный руководитель:

                                                                             Шихина Валентина Анатольевна 
 
 
 
 
 
 
 
 

2009г.

 

       Содержание:

 

Введение

 
 

 ПОСТАНОВКА  ЗАДАЧИ 

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

      Действительно, путь необходимо исследовать на экстремум  линейную функцию Z = С₁X₁+С₂X₂+... +С_NX_N 

      при линейных ограничениях  

      A₁₁X₁ + A₂₂X₂ + ... + A_1NХ_N = B₁ 

      A₂₁X₁ + A₂₂X₂ + ... + A_2NХ_N = B₂ 

      . . . . . . . . . . . . . . . 

      A_М1X₁ + A_М2X₂ + ... + A_МNХ_N = B_М 

      Так как Z - линейная функция, то = С_j (j = 1, 2, ..., n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами. 

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

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

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

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

      Основные  формы задачи ЛП.

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

      Стандартная задача ЛП.

      

      или, в матричной записи,

      

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

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

      Каноническая  задача ЛП.

      

      или, в матричной записи,

      

      Основные  вычислительные схемы решения задач  ЛП разработаны именно для канонической задачи.

      Общая задача ЛП.

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

      

      Здесь . Ясно, что стандартная задача получается как частный случай общей при ; каноническая — при .

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

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

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

      Рассмотрим  задачу ЛП

       (1)

      или, в матричной записи,

       (2)

      Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от переменных вида

       (3)

      или, в матричной записи,

       (4)

      где .

      Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3) переменных столько же, сколько строк в матрице задачи (1). Матрица ограничений в (3) — транспортированная матрица . Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.

      Теоремы двойственности

 

      Первая  теорема двойственности

      Рассмотрим  пару симметричных двойственных задач