РЕФЕРАТ НА ТЕМУ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАМИРОВАНИЕ. История развития линейного программирования
 Скачать 199.96 Kb.
|
КАК НАУКИ Основой реализации любой задачи управления является принятие конкретным лицом оптимального решения. Оптимальным считается такое решение, которое обеспечивает достижение цели в рассматриваемых условиях с максимальным эффектом. Назрела объективная необходимость повышения научного уровня экономических решений, которые отыскиваются посредством математических методов количественного анализа вариантов, который позволяет исключить субъективные, волевые факторы, тем самым ставит планирование и управление на научную основу. Математические исследования конкретных экономических проблем с целью установления экономических зависимостей и закономерностей относятся к концу XIX и началу ХХ столетия. Классическое применение математических методов для формализованного описания дано К. Марксом в его знаменитой модели расширенного воспроизводства. Эта модель была, по-видимому, первой макроэкономической моделью, позволяющей вскрыть целый ряд важных особенностей производства. Основатель математической школы в буржуазной политэкономии Л. Вальрас в 1874 г. создал общую статистическую экономико-математическую модель хозяйства в целом, известную под названием системы общего экономического равновесия. Рациональные элементы модели Вальраса заключаются в постановке экстремальной задачи для хозяйства в целом (достижение максимального эффекта при минимальных затратах) и подходе к ценам как составному элементу нахождения общего оптимума. Далее, в 1897 г., известный буржуазный экономист-математик Парето на основании статистического материала установил закономерность распределения доходов населения в капиталистических странах в форме гиперболы («кривая Парето»). Затем в 1904 г. русским экономистом-математиком В.К. Дмитриевым были созданы уравнения связи затрат и выпуска продукции, которые в дальнейшем (в 30-х годах) были использованы американским экономистом В.Леонтьевым для построения балансов «затраты – выпуск». Указанные работы можно считать первыми построениями экономико-математических моделей (Э.-М.М). Они наметили два направления экономико-математического анализа статистических данных: применение математических методов, во-первых, для описания экономических явлений, во-вторых, для установления зависимости между ними. Оба типа исследований относятся к области математической статистики; они и получили дальнейшее развитие в последующие два десятилетия. В 1939 г. в издании Ленинградского государственного университета появилась небольшая книга известного математика – профессора того же университета Л.В.Канторовича «Математические методы организации и планирования производства». Только примерно через 10 лет метод линейного программирования в другой форме был переоткрыт в США. Первые статьи по линейному программированию были опубликованы в США лишь в 1949 г. В них американский ученый Дж.Б.Данциг выступил тогда с изложением своего симплексного метода. Симплексный метод Дж.Б. Данцига имеет очень много общего с методом последовательного улучшения плана, применявшимся в дальнейшем (после 1939 г.) Л.В. Канторовичем и его сотрудниками для решения ряда практических задач, представляющих конкретную реализацию метода разрешающих множителей. Однако есть и отличия их в некоторых существенных частях. Еще до Л.В. Канторовича в нашей стране были опубликованы работы, которые можно считать зародышами линейного программирования. Так, в 1930 г. советские экономисты-транспортники (А.Н. Толстой и др.) для построения оптимального плана перевозок составили транспортную задачу в сетевой форме и решили ее без математического обоснования, применяя метод последовательного улучшения плана. В 1941 году Хичкок поставил транспортную задачу. Расцвет работ по линейному программированию падает на 50-е годы ХХ столетия. В эти годы были детально разработаны основные методы решения, создано много разных алгоритмов, началось практическое применение новых методов, появилась обширная литература. В 1949 г. Л.В. Канторовичем и М.К. Гавуриным в совместной статье был изложен метод потенциалов (в сетевой постановке) для решения транспортных задач. Несколько позднее (в 1951г.) Дж.Б.Данцигом был разработан аналогичный метод, получивший название модифицированного распределительного метода. Это название является общим и относится по существу к целой группе близких друг другу методов, включающей как частные виды симплексный метод Дж.Б. Данцига, метод разрешающих слагаемых А.Л. Лурье и др. В 1958 г. советский ученый А.Л. Лурье разработал метод разрешающих слагаемых для решения транспортных задач. В 50-е годы кроме различных методов и их модификаций для решения задач линейного программирования появляется целый ряд работ, в которых излагаются методы нелинейного и динамического программирования. Так, в 1951 г. американские ученые Х. Кун и А. Таккер опубликовали работу по решению нелинейных задач. В 1954 г. А. Чарнс и Лемке разработали и опубликовали метод решения задач с сепарабельной выпуклой целевой функцией и линейными ограничениями. В этом же году появляются работы по методам целочисленного линейного программирования. К ним относится и метод Го- мори, опубликованный в США в 1958 г. Также в 50-е годы американским математиком Р. Беллманом разрабатываются методы динамического программирования, появляется ряд работ, посвященных квадратичному программированию, например работы Е. Баранкина, Р. Дорфмана, Е. Била и др. Внедрение экономико-математических методов и ПК создаёт реальную научную базу совершенствования планирования. На основе сочетания трех фундаментальных наук математики, экономики и кибернетики учеными разработан значительный арсенал экономико-математических методов, которые можно объединить под одним названием – методы разработки оптимальных решений (или исследования операций), которые, в то же время, по праву могут рассматриваться как самостоятельные науки:
Таким образом, математическое или оптимальное, программирование включает в себя: линейное, нелинейное, целочисленное, динамическое, дискретное и выпуклое программирование. 2. Методы линейного программирования.  2.1. Симплекс-метод. Переход от одной вершины к другой Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях. Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено. Последовательность вычислений симплекс-методом можно разделить на две основные фазы:
При этом в некоторых случаях исходное решение очевидно или его определение не требует сложных вычислений, например, когда все ограничения представлены неравенствами вида «меньше или равно» (тогда нулевой вектор совершенно точно является допустимым решением, хотя и, скорее всего, далеко не самым оптимальным). В таких задачах первую фазу симплекс-метода можно вообще не проводить. Симплекс-метод, соответственно, делится на однофазный и двухфазный. 2.2. Двухфазный симплекс-метод. Причины использования Если в условии задачи линейного программирования не все ограничения представлены неравенствами типа «≤», то далеко не всегда нулевой вектор будет допустимым решением. Однако каждая итерация симплекс-метода является переходом от одной вершины к другой, и если неизвестно ни одной вершины, алгоритм вообще не может быть начат. Процесс нахождения исходной вершины не сильно отличается от однофазного симплекс-метода, однако может в итоге оказаться сложнее, чем дальнейшая оптимизация. Модификация ограничений Все ограничения задачи модифицируются согласно следующим правилам:
Соответственно, будет создано некоторое количество дополнительных и вспомогательных переменных. В исходный базис выбираются дополнительные переменные с коэффициентом «+1» и все вспомогательные. Осторожно: решение, которому соответствует этот базис, не является допустимым. Различия между дополнительными и вспомогательными переменными. Несмотря на то, что и дополнительные, и вспомогательные переменные создаются искусственно и используются для создания исходного базиса, их значения в решении сильно отличаются:
То есть ненулевое значение дополнительной переменной может (но не должно) сигнализировать о неоптимальности решения. Ненулевое значение вспомогательной переменной сигнализирует о недопустимости решения. Фазы решения. После того, как было модифицировано условие, создаётся вспомогательная целевая функция. Если вспомогательные переменные были обозначены, как  {\displaystyle y_{i}}, {\displaystyle i\in \left\{1,\dots ,k\right\}}  , то вспомогательную функцию определим, как  }{\displaystyle z'=\sum _{i=1}^{k}y_{i}\to min}После этого проводится обыкновенный симплекс-метод относительно вспомогательной целевой функции. Поскольку все вспомогательные переменные увеличивают значение {\displaystyle z'}  , в ходе алгоритма они будут поочерёдно выводится из базиса, при этом после каждого перехода новое решение будет всё ближе к множеству допустимых решений.Когда будет найдено оптимальное значение вспомогательной целевой функции, могут возникнуть две ситуации:
Во втором случае мы имеем допустимый базис, или, иначе говоря, исходное допустимое решение. Можно проводить дальнейшую оптимизацию с учётом исходной целевой функции, при этом уже не обращая внимания на вспомогательные переменные. Это и является второй фазой решения. МЕТОД ВЕТВЕЙ И ГРАНИЦ Метод ветвей и границ (англ. branch and bound) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений. Метод ветвей и границ впервые предложили в 1960 году Аилсой Ленд и Элисон Дойг для решения задач целочисленного программирования. Общая идея метода может быть описана на примере поиска минимума функции {\displaystyle f(x)}  на множестве допустимых значений переменной {\displaystyle x}  . Функция {\displaystyle f}  и переменная {\displaystyle x} могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).Процедура ветвления состоит в разбиении множества допустимых значений переменной {\displaystyle x} на подобласти (подмножества) меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево, называемое деревом поиска или деревом ветвей и границ. Узлами этого дерева являются построенные подобласти (подмножества множества значений переменной {\displaystyle x} ).Процедура нахождения оценок заключается в поиске верхних и нижних границ для решения задачи на подобласти допустимых значений переменной {\displaystyle x} .В основе метода ветвей и границ лежит следующая идея: если нижняя граница значений функции на подобласти {\displaystyle A}  дерева поиска больше, чем верхняя граница на какой-либо ранее просмотренной подобласти {\displaystyle B} , то {\displaystyle A} может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно минимальную из полученных верхних оценок записывают в глобальную переменную {\displaystyle m} ; любой узел дерева поиска, нижняя граница которого больше значения {\displaystyle m}, может быть исключён из дальнейшего рассмотрения.Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти. Метод используется для решения некоторых NP-полных задач, в том числе задачи коммивояжёра и задачи о ранце. https://ru.wikipedia.org/wiki/ Метод_ветвей_и_границ |