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

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

на  тему: 

 

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

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

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), при котором линейная функция