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

Департамент кинематографии Министерства культуры РФ

Федеральное Государственное образовательное учреждение высшего профессионального образования Санкт-Петербургский Государственный Университет Кино и Телевидения. 

Институт  экономики и управления 

Кафедра управления экономическими и социальными процессами 
 
 

КУРСОВАЯ  РАБОТА

по  дисциплине

«Экономико-математические методы и модели» 

на  тему: 
 

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

Выполнила:

студентка ФПК 17 гр.

Карышева  А.А.

Проверил:

                                                                                 к.э.н. доцент Булочников П.А. 
 

Санкт-Петербург

2009

 

Содержание 

Стр.                 

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

Теоретическая часть……………………….. ………………….………………….4

Практическая часть………………………………………….………………..…..14

Вывод…….………………………………………………………………….….….22

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

Введение 

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

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

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

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

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

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

  

Теоретическая часть 

      Если в какой-либо системе (экономической, организационной, военной и

т.д.) имеющихся  в наличии ресурсов не хватает  для эффективного выполнения

каждой     из      намеченных       работ,      то    возникают    так       называемые

распределительные   задачи.   Цель    решения    распределительной задачи –

отыскание    оптимального      распределения      ресурсов   по  работам.   Под

оптимальностью  распределения может пониматься,    например, минимизация

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

        Для   решения   таких   задач   используются   методы    математического

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

математики,   занимающийся   разработкой методов отыскания экстремальных

значений    функции,   на аргументы которой наложены ограничения. Слово

"программирование"   заимствовано    из  зарубежной литературы,   где   оно

используется  в смысле "планирование".

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

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

        Характерные черты задач ЛП следующие:

1) показатель  эффективности L представляет собой  линейную функцию,

заданную  на элементах решения x1 , x2, xn;

2) ограничительные  условия, налагаемые на возможные  решения, имеют

вид линейных равенств или неравенств.

        В общей форме записи модель задачи ЛП имеет вид: 

целевая функция (ЦФ)

L=c1x1+c2x2+...+cnxn→max(min) ; 

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

а11х1+а12х2+…+а1nxn≤(≥,=)b1,

а21х1+а22х2+…+а2nxn≤(≥,=)b2,

……………………………

аm1х1+аm2х2+…+аmnxn≤(≥,=)bm,

x1,  x2,…, xк ≥ (к ≤ n). 

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

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

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

- перейти  от минимизации целевой функции к ее максимизации;

- изменить  знаки правых частей ограничений;

- перейти  от ограничений-неравенств к равенствам;

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

        Допустимое решение – это совокупность чисел X = (x1, x2,…, xn),

удовлетворяющих ограничениям задачи.

        Оптимальное решение   – это  план   X* = (x*1, x*2,…, x*n),   при   котором ЦФ принимает свое максимальное (минимальное) значение.

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

     Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

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

     Постановка  задачи оптимизации предполагает существование  конкурирующих свойств процесса, например:

   · количество продукции - расход сырья

   · количество продукции - качество продукции  
 

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

   При постановке задачи оптимизации необходимо:

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

   Типичный  пример неправильной постановки задачи оптимизации:

   «Получить максимальную производительность при  минимальной себестоимости».

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

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

   а) получить максимальную производительность при заданной себестоимости;

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

     В первом случае критерий оптимизации - производительность а во втором - себестоимость.

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

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

   4. Учет ограничений.  

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

     Критерием оптимальности  называется количественная оценка оптимизируемого качества объекта.

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

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

        Для     построения      математической    модели   необходимо  ответить  на