Реферат по дисциплине

Системные методы обработки  данных

на  тему: 

Методы  линейного программирования 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

2010

Содержание:

Введение

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

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

В зависимости  от природы множества X задачи математического программирования классифицируются как:

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

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

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

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

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

История возникновения математического  программирования

Математическое  программирование возникло в 30-е годы XX века. Венгерский математик Б. Эгервари в 1931 году решил задачу, называемую проблемой выбора. Американский ученый Г.У. Куй обобщил этот метод, после чего он получил название венгерского метода. В 1939 году российский ученый Л.В. Канторович разработал метод разрешающих множителей решения задач линейного программирования. Большой вклад в развитие математического программирования внесли американские ученые. В 1949 году американский ученый Дж. Данциг опубликовал один из основных методов решения задач линейного программирования, получивший название симплексный. 

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

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

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

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

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

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

Временем  рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича "Математические методы организации и планирования производства". Поскольку методы, изложенные Л.В.Канторовичем, были малопригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В.Канторовича осталась почти не замеченной.

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

Эти премии получили свое название в честь их учредителя - известного химика и изобретателя Альфреда Нобеля, они должны были присуждаться за научные открытия в области  физики, химии, физиологии или медицины, за литературные произведения, "отражающие человеческие идеалы", а так же тем, кто "внесет весомый вклад в сплочение народов, уничтожение рабства, снижение численности существующих армий и содействие мирной договоренности". Математикам премия не предназначалась. Однако в 1969 году Шведский банк по случаю 300-летия со дня своего образования учредил премию памяти А.Нобеля - по экономическим наукам. Она то и была присуждена в 1975 году Л.В.Канторовичу и Т. Купмансу за создание новой математической науки (получившей название линейного программирования) и применение этой теории в экономике.

В автобиографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему, 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Уже летом 1939 года была сдана в набор книга Л.В.Канторовича "Математические методы организации и планирования производства", в которой закладывались основания того, что ныне называется математической экономикой.

Идеи  Л. В. Канторовича в области экономики не встретили понимания в момент их зарождения, были объявлены ересью, и его работа была прервана.

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

Американский  математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод  численного решения задач линейного  программирования (он получил название симплекс метода). Идеи линейного программирования в течении пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.

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

Л.В.Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует  и в конкретных разработках на производстве. При этом (одновременно с Данцигом, но не зная его работ) он разрабатывает метод, позже названный симплекс-методом. В 50-е годы он организует группу студентов на экономическом факультете ЛГУ, для обучения методам оптимального планирования. А начиная с 1960 года Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (присуждена ему совместно с В.С.Немчиновым и В.В.Новожиловым) и, как уже говорилось, Нобелевской премией в 1975 году. 
 
 
 
 
 
 
 

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

Задача  линейного целочисленного программирования

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

Задача  линейного целочисленного программирования формулируется следующим образом:

Найти такое решение (план) Х=(х₁, х₂,…, х_n), при котором линейная функция

принимает максимальное значение при ограничениях:

Методы  целочисленной оптимизации можно  разделить на три основные группы:

1. Методы отсечения;

2. Комбинаторные методы;

3. Приближенные методы. 

1. Методы отсечения  Гомори.

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

• оно должно быть линейным;
• должно отсекать найденный оптимальный нецелочисленный план;
• не должно отсекать ни одного целочисленного плана.

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

Далее задача решается с учетом нового ограничения. После этого в случае необходимости  добавляется еще одно ограничение и т.д.

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

Алгоритм:

1. Задача оптимизации решается симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования.
2. Если среди компонент оптимального решения есть нецелые, то выбирают компоненту с наибольшей целой частью и по соответствующему уравнению системы ограничений формируется правильное отсечение:

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

     и включить его в систему ограничений.

4. Полученную расширенную задачу решить симплексным методом. Если найденный оптимальный план будет целочисленным, то задача целочисленного программирования решена. В противном случае возвратиться к пункту 2.

Если задача разрешима в целых числах, то после  конечного числа шагов (итераций) оптимальный целочисленный план будет найден. 

2. Комбинаторные  методы.

Наиболее известным  комбинаторным методом является метод ветвей и границ.

Впервые метод  ветвей и границ был предложен  в работе Лэнд и Дойг в 1960 г. применительно  к задаче линейного целочисленного программирования. Второе рождение метода связано с работой Литтла, Мурти, Суини и Кэрел, 1963 г., посвященной  задаче о коммивояжере.

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

3. Приближенные методы.

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

Задача  линейного программирования 

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

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

В самом  общем виде задача математически  записывается так:

U = f(x) ® max; x Î w,

где x = (x₁, x₂,…, x_n);

w – область допустимых значений переменных x₁, x₂,…, x_n;

f(x) – целевая функция. 

Для того чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т.е. указать x* Î w такое, что f(x*) ³ f(x), при любом x Î w, или для случая минимизации - что f(x*) ≤ f(x), при любом x Î w.

Оптимизационная задача является неразрешимой, если она  не имеет оптимального решения. В  частности, задача максимизации будет  неразрешима, если целевая функция f(x) не ограничена сверху на допустимом множестве w.

Методы  решения оптимизационных задач  зависят как от вида целевой функции f(x), так и от строения допустимого множества w. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.

В математическом программировании принято выделять следующие основные задачи в зависимости  от вида целевой функции f(x) и от области w:

• задачи линейного программирования, если f(x) и w линейны;
• задачи целочисленного программирования, если ставится условие целочисленности переменных x₁, x₂,…, x_n;
• задачи нелинейного программирования, если форма f(x) носит нелинейный характер.

Задачей линейного программирования называется задача на условный экстремум (максимум или минимум) линейной функции нескольких переменных при наличии линейных ограничений типа равенство или нестрогое неравенство:

 ,

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

,

.  

Функция F(x) называется целевой функцией (или линейной формой) задачи.

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

Решение системы ограничений, при котором  целевая функция задачи принимает  свое максимальное (минимальное) значение, называется оптимальным. 

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

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

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

     2) если в ограничениях правая  часть отрицательна, то следует  умножить это ограничение на -1;

     3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

     4) если некоторая переменная x_k не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными:

где x_k – свободный индекс, . 

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

    Понятие критерия оптимальности 

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

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

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

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

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

Симплекс-метод 

Проблема  рационального перебора базисных решений задачи линейного программирования была впервые решена Дж. Данцигом. Предложенный им в 1951 г. симплекс-метод до настоящего времени является наиболее распространенным общим методом линейного программирования.

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

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

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