Основные теоремы линейного программирования. Основные теоремы двойственности и их экономический смысл

ФГБОУ ВПО «Удмуртский Государственный Университет»

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

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

 

 

 

 

 

 

Реферат

по дисциплине: «Государственно  регулирование экономики»

на тему: «Основные теоремы линейного программирования. Основные теоремы двойственности и их экономический смысл.»

 

 

 

 

 

 

 

 

 

 

 

Выполнил: студент гр.611-41

                                                                                               И.Д. Ковальногих

Проверил: Доцент кафедры А.Ф. Гольман

 

 

г. Ижевск 2012

 

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ……………………………………………………………………….3

ОСНОВНЫЕ  ТЕОРЕМЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ…………6

ОСНОВНЫЕ  ТЕОРИИ ДВОЙСТВЕННОСТИ И ИХ ЭКОНОМИЧЕСКИЙ  СМЫСЛ……………………………………………………………………………9

ЗАКЛЮЧЕНИЕ……………………………………………………………….…11

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ……………………………..12

 

ВВЕДЕНИЕ

Каждый  человек ежедневно, не всегда осознавая  это решает проблему: как получить наибольший эффект, обладая ограниченными  средствами. Наши средства и ресурсы  всегда ограничены. Жизнь была бы менее  интересной , если бы это было не так. Не трудно выиграть сражение, имея армию  в 10 раз большую, чем у противника; Ганнибалу, чтобы разбить римлян при Каннах, командуя вдвое меньшей  армией, нужно было действовать очень  обдуманно.

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

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

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

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

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

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

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

ОСНОВНЫЕ  ТЕОРЕМЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

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

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

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

Начало  линейному программированию было положено в 1939 г. советским математиком-экономистом Л. В. Канторовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в экономике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач -- симплекс-метод. Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит в следующем:

• умение находить начальный опорный план;
• наличие признака оптимальности опорного плана;
• умение переходить к улучшенному опорному плану.

 

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

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

Решение какой-либо задачи управления можно  разбить на несколько этапов:

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

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

Итак, математическая модель означает перевод задачи на язык количественных терминов.

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

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

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

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

ОСНОВНЫЕ  ТЕОРИИ ДВОЙСТВЕННОСТИ И ИХ ЭКОНОМИЧЕСКИЙ  СМЫСЛ.

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

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

Количество  переменных в двойственной задаче равно  количеству неравенств в исходной.

Матрица коэффициентов двойственной задачи является транспонированной к матрице  коэффициентов исходной.

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

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

Транспонированной называется матрица, у которой строки и столбцы меняются местами. Поэтому  коэффициенты при переменных yi в  задаче II это, соответственно, коэффициенты i-ого неравенства в задаче I. Неравенства, находящиеся напротив друг друга, называются сопряженными .

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

Теорема 1 (первая теорема двойственности)

Если  одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных  планах совпадают, F(x*)=G(y*), где х*, у* - оптимальные решения задачи I и II

Теорема 2 (вторая теорема двойственности)

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

 

ЗАКЛЮЧЕНИЕ