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

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

 

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

 

Логин:

Пароль:

 

Запомнить

 

 

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

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

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

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


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


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

Информация:

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

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


 
Частное образовательное учреждение профессионального  образования
«КРАСНОДАРСКИЙ  ТЕХНИКУМ УПРАВЛЕНИЯ, ИНФОРМАТИЗАЦИИ И  СЕРВИСА»
Цикловая  комиссия информационных и технических  дисциплин 
 
 
 
 
 
 
 

Скачков Антон Юрьевич
Студент группы ПО-3.1 
 

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

Курсовая  работа
По дисциплине «Математические методы»
Специальность 230105 «Программное обеспечение ВТ и  АС» 
 
 
 
 
 
 

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

2009г.
 

       Содержание:

 

Введение

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

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

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

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

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

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

     Задачами  линейного программирования называются задачи, в которых линейны как  целевая функция, так и ограничения  в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств. 
           Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:
    рационального использования сырья и материалов; задачи оптимизации раскроя;
    оптимизации производственной программы предприятий;
    оптимального размещения и концентрации производства;
    составления оптимального плана перевозок, работы транспорта;
    управления производственными запасами;
    и многие другие, принадлежащие сфере оптимального планирования.
     Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций.
     Первые  постановки задач линейного программирования были сформулированы известным советским  математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская  премия по экономике.
     В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения.
     Итак, линейное программирование - это наука  о методах исследования и отыскания  наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции.
 

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

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

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

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

      A11X1 + A22X2 + ... + A1NХN = B1 

      A21X1 + A22X2 + ... + A2NХN = B2 

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

      AМ1X1 + AМ2X2 + ... + 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) называется прямой.

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

 
      Первая  теорема двойственности
      Рассмотрим  пару симметричных двойственных задач
      
      Первая  теорема двойственности.
      Если  одна из пары двойственных задач (I) и (II разрешима, то разрешима и другая задача, причем оптимальные значения целевых функций прямой и двойственной задач совпадают
      
      оптимальные планы задач (I) и (II) соответственно.
      Доказательство.
      1. Пусть задача (I) разрешима, и пусть
      
      т.е. х* - оптимальное решение. Обозначим  M= L(х*).
      Тогда по основной лемме существует
      
      для которого
      Но  по основному неравенству двойственности имеем :
      
      Объединяя последние два соотношения, имеем 
      откуда  следует, что у* - оптимальное решение  задачи (II) и
      
      2. Пусть теперь задача (II) -разрешима. Построим эквивалентную (II) задачу
      
      Задача (II') разрешима, так как задача (II) разрешима. Тогда по пункту 1 двойственная к (II') задача :
      
      Но  эта задача эквивалентна задаче (I). Следовательно, задача (I) разрешима.
      Теорема доказана.
      Первый  критерий оптимальности
      Решение   оптимально тогда и только тогда, когда существует решение
         такое, что
      Доказательство.
      Необходимость следует из первой теоремы двойственности.
      Достаточность следует из достаточного условия  оптимальности. 

      Вторая  теорема двойственности
      Рассмотрим  пару симметрических двойственных задач  ЛП
      
      Вторая  теорема двойственности
      Чтобы допустимые решения  х, у пары двойственных задач (I) и (II) были оптимальными необходимо и достаточно, чтобы выполнялись  условия :
      
      Доказательство.
      Необходимость. По условию допустимые решения х, у - оптимальны.
      
      то  из оптимальности решений х, у по первой теореме двойственности
      В результате имеем 
      Необходимость доказана.
      Достаточность. По условию
      
      
      По  первой теореме двойственности получаем, что х, у - оптимальные решения  задач (I) и (II).
      Допустимые  решения х, у задач (I) и (II) удовлетворяют условиям дополняющей нежесткости (УДН), если при подстановке этих векторов в ограничения задач (I) и (II) хотя бы одно из любой пары сопряженных неравенств обращается в равенство
      Второй  критерий оптимальности (следствие  из условий дополняющей нежесткости)
      Чтобы допустимые решения х, у пары двойственных задач (I) и (II) были оптимальны, необходимо и достаточно, чтобы выполнялись  соотношения :
        

      Доказательство. Распишем
      
      покоординатно :
      
      Из  допустимости решений х и у  следует, что
      
      
      тогда, когда каждое слагаемое в этих равенствах равно нулю
      
      Произведение  двух сомножителей, как известно, равно  нулю, тогда и только тогда, когда  хотя бы один из множителей равен нулю.
      Следовательно, равенства (*) или, что то же самое
      
      эквивалентны  условиям (1)-(4), и по второй теореме  двойственности получаем справедливость утверждения.
      Критерий  доказан. 

      Замечание Условия (1)-(4) есть условия дополняющей  нежесткости, поэтому критерий можно  сформулировать более лаконично.
      Второй  критерий оптимальности
      Чтобы допустимые решения х, у пары двойственных задач (I), (II) были оптимальны, необходимо и достаточно, чтобы выполнялись  УДН. 

      Критерий  разрешимости задачи ЛП
      Точной  верхней гранью (супремумом) функции L(х) на множестве D называется такое число М*, что
      

      Двойственный метод  решения ЗЛП

      Каждой  задаче линейного программирования можно определенным образом сопоставить  некоторую другую задачу (линейного  программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей, как мы уже знаем, в нахождении максимального значения функции
       (32)
      при условиях
       (33)
       (34)
      Задача, состоящая в нахождении минимального значения функции
       (35)
      при условиях
       (36)
       (37)
      называется  двойственной по отношению к задаче (32) – (34). Задачи (32) – (34) и (35) – (37) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам: 

      1. Целевая функция исходной задачи (32) – (34) задается на максимум, а целевая функция двойственной (35) – (37) – на минимум. 
 

      2. Матрица
       (38)
      составленная  из коэффициентов при неизвестных  в системе ограничений (33) исходной задачи (32) – (34), и аналогичная матрица
       (39)
      в двойственной задаче (35) – (37) получаются друг из друга транспонированием (т. е. заменой строк столбцами, а  столбцов – строками). 

      3. Число переменных в двойственной  задаче (35) – (37) равно числу ограничений  в системе (33) исходной задачи (32) – (34), а число ограничений  в системе (36) двойственной задачи  – числу переменных в исходной  задаче. 

      4. Коэффициентами при неизвестных в целевой функции (35) двойственной задачи (35) – (37) являются свободные члены в системе (33) исходной задачи (32) – (34), а правыми частями в соотношениях системы (36) двойственной задачи – коэффициенты при неизвестных в целевой функции (32) исходной задачи. 

      5. Если переменная xj исходной задачи (32) – (34) может принимать только  лишь положительные значения, то j–е условие в системе (36) двойственной  задачи (35) – (37) является неравенством  вида “? ”. Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе (54) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (33) исходной задачи (32) – (34) и переменными двойственной задачи (35) – (37). Если i – соотношение в системе (33) исходной задачи является неравенством, то i–я переменная двойственной задачи В противном случае переменная уj может принимать как положительные, так и отрицательные значения. 

      Двойственные  пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (33) прямой задачи и соотношения (36) двойственной задачи являются неравенствами вида “ ”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения. 

      Пример 11.  

      Составить двойственную задачу по отношению к  задаче, состоящей в максимизации функции
       (40)
      при условиях
       (41)
       (42)
      Решение. Для данной задачи
        и 
      Число переменных в двойственной задаче равно  числу уравнений в системе (41), т. е. равно трем. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений (41), т.е. числа 12, 24, 18. 

      Целевая функция исходной задачи (40) – (42) исследуется  на максимум, а система условий (41) содержит только уравнения. Поэтому  в двойственной задаче целевая функция исследуется на минимум, а ее переменные могут принимать любые значения (в том числе и отрицательные). Так как все три переменные исходной задачи (40) – (42) принимают только лишь неотрицательные значения, то в системе условий двойственной задачи должны быть три неравенства вида “? ”. Следовательно, для задачи (40) – (42) двойственная задача такова: найти минимум функции
      при условиях
      
      Пример 12.  

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

       Заключение

 

       Пример:

      Составить задачу, двойственную данной задаче:

 
      F=-4x1-18x2-30x3-5x4 > max
      при ограничениях:
        

        

        

      Составим  расширенную матрицу системы: 

              x1   x2    x3     x4
      
Найдём матрицу  А, транспонированную к А’:  

                y1     y2
        

      Сформулируем  двойственную задачу:
      F=-3y1+3y2 > min 

      при ограничениях: 

      
 

      
 
 

 

       Чтобы определить направление возрастания линейной функции, построим вектор q:
      F(y)=-3y1+3y2 , следовательно, по оси у1 ставим точку на -3, по оси у2  на 3  (т.к. коэффициент при у1=-3, при у2=3), затем от нуля к их точке пересечения проводим вектор.
      Так как рассматриваемая задача –  на отыскание минимума, то оптимальное решение в точке B, которая находится на пересечении 3 и 4 прямых. Следовательно, можно вычислить координаты этой точки для нахождения максимума целевой функции:
        

       (складываем обе функции) 

            -5y2      =        -10 

                    

      (?) B (7, 2)
      Fmin = -15=Zmax 
 

        

       (складываем обе функции) 

                     отсюда: 
      
Ответ:   Zmax = -15 = Fmin, при X* = (0, 0, 0, 3). 

Заключение 

     В ходе работы над курсовым проектом была рассмотрена задача линейного  программирования.
     В решение этой задачи я применил: свойства составления двойственной задачи, алгоритм составления двойственной задачи.
      Алгоритм  составления двойственной задачи:
    Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду «?», а если минимум – к виду «?». Для этого неравенства, в которых данное требование не выполняется, умножить на -1;
    Составить расширенную матрицу системы А1, в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции;
    Найти матрицу А1’, транспонированную к матрице А1;
Сформулировать  двойственную задачу на основании полученной матрицы А1’ и условия неотрицательности переменных.
 

      

Используемая  литература

    Акулич  И.Л. Математическое программирование в примерах и задачах.-М.: Высшая школа 1986.
    Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения.-М.: ИНФРА-М, 2003.
    Конюховский П.В. Математические методы исследования операций в экономике.-СПб.: Питер,2000.
  1. Кремер Н.Ш. Исследование операций в экономике, М.:2004

и т.д.................


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


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


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


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


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