Основоположники математического программирования Данциг и Канторович

DISC">

«Приближенные методы решения уравнений в частных производных», 1936 (соавтор — В.И. Крылов)

«Математические методы организации и планирования производства», 1939, 1960

«Приближенные методы высшего анализа», 1941

«Функциональный анализ и прикладная математика», 1948 (статья в УМН)

«Функциональный анализ в полуупорядоченных пространствах», 1950 (соавторы — Б.З. Вулих, А.Г. Пинскер)

«Рациональный раскрой промышленных материалов», 1951, 1972 (соавтор — В.А. Залгаллер)

«Экономический расчет наилучшего использования ресурсов», 1959

«Функциональный анализ в нормированных пространствах», 1959 (соавтор — Г.П. Акилов)

4 О задачах оптимизации 
 

     Самым  важным научным достижением своей  жизни Леонид Витальевич считал  “линейное  программирование”.  Что  же  это  такое?   Этим термином  обозначают  обширный раздел науки, посвященный  линейным оптимизационным  моделям, то  есть построению,  теоретическому  и численному  анализу и решению задач, в которых требуется найти оптимальное значение, некоторой системы показателей в процессе, поведение и состояние которого описывается той или иной  системой линейных неравенств.

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

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

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

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

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

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

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

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

     Слово  “оптимальный”  весьма  популярно  в  средствах  массовой информации. Почти ежедневно государственные чиновники  толкуют  об оптимальных  способах преодоления кризисных явлений,  кандидаты  в депутаты, губернаторы и президенты в своих предвыборных программах предлагают оптимальные пути развития республик, областей, регионов или  же  всей  страны. Как нам следует к этому относиться?  Очень просто:  все эти проекты и программы следует признавать  лишенным всякого содержания,  если не просматриваются (явно  или неявно) управляемые   переменные,  целевая функция   и   ограничения   той оптимизационной задачи, которая имеется в виду.  Иными словами, разговор  об оптимальном бессмысленен, если не обозначены критерии оптимальности,  совокупность возможных альтернатив и ограничения, которые продиктованы  техническими, технологическими,  природными или иными обстоятельствами. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

5 Примеры задач Д.Данцига и Л.Канторовича 

5.1 Разработка Канторовича  
 

     Разработка  линейного программирования началась с поиска решения практической задачи. К Канторовичу обратились инженеры фанерного треста с просьбой найти эффективный способ распределения ресурсов, обеспечивающий наиболее высокую производительность оборудования. Работники предприятия ломали голову над тем, как при пяти станках, восьми видах сырья обеспечить оптимальный вариант выпуска фанеры. Иными словами, нужно было найти решение конкретной технико-экономической задачи с целевой функцией (“функционалом”) — максимизировать выпуск готовой продукции.

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

     Канторович  не был “чистым” экономистом, но прекрасно  понимал, какое значение имеет метод  максимизации при ограниченных ресурсах, а значит, и создание математической основы для решения типичных хозяйственных задач.

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

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

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

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

Допустим, требуется  решить транспортную задачу, обосновать наиболее рациональное распределение  грузопотоков. Для примера, всего  нужно перевезти 180 т груза из трех источников к трем потребителям, общий спрос которых также равен 180 т. Сложность в том, что груз распределен неравномерно: у одного поставщика имеется 50 т, у другого — 60, у третьего — 70 т. Также неравнозначен спрос потребителей, он составляет соответственно 40, 85 и 55 т. Неодинаковы и расстояния (плечи) перевозки грузов — от 1 до 6 км. Задача заключается в том, чтобы составить такой план перевозок, который отвечал бы требованию минимизации грузооборота (минимальному количеству тонно-километров).

     Как решить эту задачу? В повседневной практике менеджеры могут заняться монотонной работой по длительному  перебору возможных вариантов. Постепенно они смогут прийти от плана перевозок, скажем, 750 т/км к плану 655 т/км. Поиск  потребует массу усилий, значительного количества расчетов. Главное же, трудно установить, какой из предлагаемых вариантов” является оптимальным. Допустим, найден вариант плана с грузооборотом в 575 т/км. Но остается неизвестным, есть ли еще один или несколько более выгодных вариантов плана, требующих меньших затрат.

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

5.2 Алгоритм Данцига 
 

     Алгоритм  Данцига — алгоритм для нахождения кратчайших путей ко всем вершинам планарного направленного графа. Назван в честь американского математика Джорджа Данцига.

     Теория  графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.