Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Критический путь

Читайте также:
  1. Вопрос № 38. Критический реализм К. Поппера. Постпозитивистские модели науки и ее развития
  2. Критический анализ действующей системы управления и обеспечения качества продукции на предприятии
  3. Критический анализ основных положений и выводов классической термодинамики
  4. Критический анализ произведения “Три разговора между Гиласом и Филонусом”.
  5. Критический анализ статьи Ю.Н. Жукова
  6. Критический объем производства или точку безубыточности (в экземплярах) можно определить как а / (с - b).

Математика это искусство называть разные вещи одним и тем же именем.

Анри Пуанкаре

Существенное усложнение организационных, экономических и производственных процессов, характерное для послевоенного периода (50-ые годы XX ст.), привело к потребности использования в соответствующих расчетах мощных математических и вычислительных средств, что стало возможным, в частности, с появлением компьютеров (ЭВМ).
На стыке математики и экономики возник и постепенно стал развиваться современное научное направление "Математическая экономика", где профессиональные экономисты в своих исследованиях активно используют математические методы, а математики обращаются к экономическим задачам, чтобы применить соответствующие полученые ими результаты. Основателем и активным разработчиком математической экономики считается В. В. Леонтьев.
Еще в середине 20-х годов XX ст., работая в России, В.В. Леонтьев определил проблему межотраслевого баланса (МОБ), сначала на уровне отдельного государства, а впоследствии - на уровнях региональной и мировой экономики. Он указал на важность учета межотраслевых взаимосвязей, которые и определяют общий результат экономической деятельности. То был новый подход к исследованию сложно организованных объектов или процессов, который значительно позже назвали системным. Для решения проблемы МОБ, которой он занимался всю свою жизнь уже как гражданин США, В.В. Леонтьев использовал классический аппарат линейной алгебры и матричного анализа для развязывания систем линейных уравнений достаточно большого размера, хотя для выполнения табличных расчетов на то время применялись лишь механические арифмометры.
В 1938 году 26-летний профессор-математик Л. В. Канторович (1912-1986), работая научным консультативным фанерной фабрики, впервые сформулировал задачу оптимального (то есть наилучшего из всех возможных вариантов при определенных ограничениях) использования ограниченных производственных ресурсов (тогдашняя закодированная тема исследования - „задача фантреста") и предложил соответствующий математический метод ее решения.
Этот принципиально важный результат, полученный Канторовичем в процессе серьезных математических исследований в условиях плановой экономики (нужно знать, что советские экономисты игнорировали математику вообще: тогда на экономические факультеты поступали учиться те, кто еще из школы не знал и „боялся" математики. Следствия такого ее невосприятия у нас чувствуется еще и до сих пор, поскольку теоретиками экономической науки и практики еще достаточно часто есть ученики тех первых „авторитетов" плановой экономики, построенной на принципах идеологии ленинизма-марксизма), опубликован в 1939 г., в виде скромной брошюры, долгое время сохранялся в „спецхранах" и оставался неизвестным передовой научной, инженерно-технической и экономической общественности. Это и не удивительно, потому что автор этого результата — Л.В. Канторович — за тогдашней марксистско-ленинской идеологией, не мог рассчитывать на заинтересованность со стороны плановой экономики СССР, когда все „лучшие" планы формировались „вверху" в московском Госплане и спускались для выполнения на конкретные предприятия, где не должно было и возникать сомнений относительно их качеств. Соответственно за этой схемой, на предприятиях не могла появиться потребность ставить и решать задачи оптимизации. А если бы такая потребность у кого-то возникла, то, возникла бы заинтересованность уже совсем других государственных „органов"...
Судьбы обоих научных работников, как видим, во многом похожие: высокообразованные и талантливые молодые выпускники Ленинградского университета экономист В. Леонтьев и математик Л. Канторович работали на новую экономику, сделали свои гениальные открытия, но оказалось — „не в том месте" и несвоевременно. Первый из них вынужден был покинуть родину навсегда, второй — хотя и остался, но долгие годы, находясь под пристальным присмотром власти, не должен был даже вспоминать о своем открытии. Результаты этих исследований лишь через много лет были оценены должным образом - Нобелевскими премиями из экономики.
Американский математик Дж. Данциг, занимаясь планированием в оборонной сфере, где разрабатывал программы совершенствования военно-воздушных сил США, в 1947 г. повторно и независимо сформулировал эту самую задачу оптимизации и соответствующий математический аппарат, который назвал „линейное программирование" и предложил для ее машинного решения эффективный „симплекс-метод". В 50-ые годы в США с появлением первых ЭВМ этим методом сразу же воспользовались и запрограммировали его. После этого начался бурный процесс применения линейного программирования в самых разнообразных сферах: военной, промышленной, бизнесовой и др.
Осенью 2004 г. мировая научная общественность торжественно отмечала 90-летие от дня рождения Дж. Данцига. В частности в Винницком филиале Европейского университета ежегодная научная конференция студентов второго курса была посвящена именно этому событию, в Стенфорский университет было послано приветствие.
С середины 50-х годов математическая оптимизация уже в виде всем известного линейного программирования начала применяться и в прежнем СССР. Давняя разработка Л. В. Канторовича (о которой ему и его ученикам было запрещено даже вспоминать) вернулась на родину в американской упаковке! Постепенно наши „чистые" математики начинают решать практические задачи оптимального планирования, которые существуют в экономике и производственной сфере, встречая со стороны признанных специалистов в политэкономике социализма подозрение и глухое сопротивление. Так в СССР формируется научное направление "экономико-математическое моделирование".
Мощный толчок в развитие и внедрение методов оптимизации для планирования и управления в стране, в частности в Украине, связанный с именем выдающегося математика и умелого организатора науки академика В.М. Глушкова. Он смог убедить партийное руководство государства о необходимости активного развития этих работ, в 1962 г. впервые в прежнем СССР он организовал академический Институт кибернетики в Киеве с научными отделами, где разрабатывались математические модели и методы оптимизации. Эти модели внедрялись в разных отраслях производства в составе автоматизированных систем управления (АСУ).
Линейное программирование дало толчок развитию новых математических моделей оптимизации — оно стало ядром более общего научного направления в прикладной математике - математического программирования. И теперь, как видим, математическое программирование стало составляющей математического образования студентов университетов.
"Исследование операций" является логическим продолжением дисциплины "Математическое программирование", оно имеет собственную интересную историю.
Научное направление „исследование операций" возникло перед Второй мировой войной, в 1938 г. Тогда так достаточно обобщенно и невыразительно (и понятно, потому что речь шла о достаточно секретных военных действиях) назвали многообразные организационные научно обоснованные действия, направленные на повышение обороноспособности Англии в борьбе с подводными лодками и авиацией немецких фашистов. Эти процедуры, которые предлагались и выполнялись силами штабных офицеров и научных работников разных направлений, оказались достаточно производительными благодаря эффективному использованию многообразных научно-технических ресурсов.
Именно тогда выдающийся американский математик и статистик Норберт Винер занимался проблемами противовоздушной обороны. Он положил начало новой математически обоснованной науке управления объектами разной природы, которую называл „кибернетика" и издал книгу с таким же названием в 1948 г.
Из первой опубликованной у нас монографии можно составить определенное представление о содержании операционных задач военного характера. Почти сразу после войны методы исследования операций стали использовать в менеджменте для планирования и управления экономическими процессами.
Исследование операций основывается на разработке и использовании математических методов, которые дают возможность определить тенденции развития определенных реальных процессов путем постановки конкретной математической задачи. ее решение дает возможность оценить ожидаемую эффективность соответствующих действий в числовом эквиваленте. Этот научный подход организации исследований получил впоследствии название „математическое моделирование" - он оказался достаточно универсальным и мощным, стимулировал активное развитие как математики в целом, так и аналоговой и цифровой вычислительной техники для машинной реализации достаточно сложных математических моделей.
Интересно, что активное развитие математических методов стимулировало разработку теории универсальных вычислительных машин, которые по определенной программе давали возможность получить соответствующий результат.
Выдающиеся математики, такие, как Джон фон Нейман (США) или В.М. Глушков (СССР), как никто понимали необходимость иметь мощные вычислительные средства. Они и стали известными в мире как основатели математической теории автоматов и руководители проектов по разработки компьютеров, активными проводниками внедрения методов математического моделирования в экономическую практику.
Следовательно, после войны методы и технологии операционного управления сложными организациями были перенесенные на задаче управления промышленными предприятиями, экономикой и процессами бизнеса и образовали отдельное направление научного управления производством, экономикой и бизнесом под названием "наука управления" (Management Science).
Как часто бывало в СССР, в начале 50-х годов военные специалисты первыми смогли ознакомиться с полученными по спецканалам еще не опубликованными у нас книгами и статьями американских авторов о линейном программировании и исследовании операций - ведь защита государства всегда была выше идеологии. Интерес военных к проблеме оптимального планирования объяснялся не экономическими задачами — тогда мы жили в разных экономических системах и считалось, что советская плановая экономика - "на высоте", а западная рыночная является загнивающей и бесперспективной. Военные интересовались эффективными и универсальными математическими моделями типа задач оптимального деления ограниченных ресурсов, потому что, если для экономистов ресурсами являются финансы, сырье или энергия, то для военных — это самолеты, ракеты, бомбы, тем, что это была часть общей теории управления системами, названной тогда странным сроком "исследования операций".
И это правильно, ведь линейное программирование впервые возникло в Пентагоне (Министерстве обороны США), где работал его изобретатель Дж. Данциг, а исследование операций, что возникло во время Второй мировой войны, понятно, касалось в первую очередь военных операций. Вне сомнения, много научных идей в те годы получали дополнительную поддержку, если у них были заинтересованные военные круги, и линейное программирование — один из примеров такого подхода к развитию в СССР (и не только) научных исследований.
Но правильно и то, что сразу же после войны в США методы оптимизации стали активно использовать в управлении производством (менеджменте), финансах и банковском деле, что чрезвычайно стимулировало развитие компьютерной индустрии, математического программирования и исследования операций, в частности и потому, что военные операционисты (как тот же Дж. Данциг) перешли работать в сферу бизнеса и образования.
Никто из наших военных специалистов (среди них были инженеры, которые очень неплохо знали математику; некоторые из них были взяты в армию по окончании математических и физических факультетов), обычно, никогда не слышал о работах Л.В. Канторовича и это не странно - запрещение действовало безотказно. В 1957-1958 гг. они лишь начинали знакомиться с переводами американской литературы из линейного программирования и ведомости о работах Канторовича от тех, кто об этом знал, были откровением. (Хотя запрещение относительно самого Канторовича на то время как будто было снято, в условиях "холодной войны" между СССР и США его научные результаты определенное время оставались секретными и недоступными даже для наших специалистов. Именно поэтому о работе Канторовича из математической оптимизации, опубликованной еще в 1939 г. в малоизвестном университетском сборнике, в США узнали достаточно поздно.
То же с легализацией у нас линейного программирования возник и длился лет двадцать научный спор о приоритете открытия линейного программирования, но справедливость восторжествовала - Л. В. Канторович заслуженно стал Нобелевским лауреатом из экономики, хотя «отцом линейного программирования» в США по традиции называют Дж. Данцига.
Следовательно, первыми отечественными авторами исследований из математического программирования стали те математики, которые имели определенную причастность к военной тематике и доступ к соответствующей документации.
В СССР экономистом-академиком В. С. Немчиновым термину "исследования операций" был найден "наш" аналог под названием "экономико-математические методы". Это название выполняло определенную пропагандистскую, подчеркнуто мирную, сугубо экономическую, ориентацию нашей математической оптимизации в отличие от военно-агрессивного названия "исследование операций" (хотя первыми пользователями этих методов у нас были именно военные). Этот "хитрый" ход позволил легализовать работы из математического программирования, создать соответствующие научные учреждения, реанимировать результаты Канторовича и активно развивать операционные исследования в нашем государстве.
На то время вычислительные методы линейного, а позже - математическое программирование уже приобрели статусу мощных инструментов решения многообразных задач оптимизации с применением ЭВМ. Это естественно, что модели и методы математического программирования вошли в арсенал средств для поиска оптимальных решений в экономических и организационных задачах.

……….

Задачи линейного программирования были первыми, подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 г. Ж. Фурье и затем в 1947 г. Дж. Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции — симплекс-метод, ставший основным при решении задач линейного программирования.

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

Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 30-м годам ХХ столетия. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман, знаменитый математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя; советский академик, лауреат Нобелевской премии (1975 г.) Л. В. Канторович, сформулировавший ряд задач линейного программирования и предложивший (1939 г.) метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода.

В 1931 г. венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название «проблема выбора», метод решения получил название «венгерского метода».

Л. В. Канторовичем совместно с М. К. Гавуриным в 1949 г. разработан метод потенциалов, который применяется при решении транспортных задач. В последующих работах Л. В. Канторовича, В. С. Немчинова, В. В. Новожилова, А. Л. Лурье, А. Брудно, А. Г. Аганбегяна, Д. Б. Юдина, Е. Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение её методов к исследованию различных экономических проблем. Методам линейного программирования посвящено много работ зарубежных ученых. В 1941 г. Ф. Л. Хитчкок поставил транспортную задачу. Основной метод решения задач линейного программирования — симплекс-метод — был опубликован в 1949 г. Дж. Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Г. Куна (англ.), А. Таккера (англ.), Гасса (Gass S. I.), Чарнеса (Charnes A.), Била (Beale E. M.) и др.

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

Начиная с 1955 г. опубликовано много работ, посвященных квадратическому программированию (работы Била, Э. Баранкина (Barankin E.) и Дорфмана (Dorfman R.), Франка (Frank M.) и Вольфа (Wolfe P.), Г. Марковица и др.). В работах Денниса (Dennis J. B.), Розена (Rosen J. B.) и Зонтендейка (Zontendijk G.) разработаны градиентные методы решения задач нелинейного программирования.

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

 

Критический путь

var begun_auto_pad = 88165774; var begun_block_id = 2360; Постановка задачи.

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

Основою этой задачи стала практика современного менеджмента относительно управления сложными проектами, основанная в США (1968 г.), моделями которых есть так званые сетевые графики. Соответственная методология получила название «сетевое планирование и управление» (СПУ).

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

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

Для расчета сетевого графика разработаны два методы:
критического пути (Critical Path Method, CPM), где длительность операций однозначно определенно и задано конкретными числами;
анализа и просмотра программ (Program Evaluation and Review Technique, PERT), где длительность операций неопределенно, потому их задают определенными вероятностными оценками.

Цель обоих методов одинакова – она состоит в определении минимальной продолжительности исполнения всех операций проекта. Оказалось, что, чтобы определить минимальный строк исполнения всего проекта, графической и математической моделью есть сетевой график, нужно найти конфигурацию та длину максимального пути, что соединяет начальный узел с конечным. Этот путь называют критическим путем, операции, что его образовывают, есть критическими, поскольку должны быть исполнены в определенный для них срок, их задержка приведет к увеличению длительности проекта. Все остальные операции некритические, поскольку имеют резерв времени. Следовательно, основное внимание менеджера должно быть сосредоточено на критических работах.

Пример: Задано сетевой график в виде ориентированного графа, который состоит из 9 узлов (событий) и 13 дуг (операций). Нужно найти критический путь от узла № 1 к узлу № 2.

Экономико-математическая модель.
Найти вектор неизвестных (Дуга), чтобы
Общая длина пути = Дуга*Продолжительность - mах
При условии сохранения балансу потоков для каждого узла: для узла-источника – Выход – Вход = 1; для промежуточных узлов - Выход – Вход = 0; для узла –стока - Выход – Вход = -1; все неизвестные больше нуля.

Реализация в Excel.
В таблице для операций определяем диапазон для неизвестных (Дуга) и вычисляем значение целевой ячейки (Длительность) за формулой =СУММПРОИЗВ(Дуга; Продолжительность).

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

Для вычисления потока в узлах используют функцию вычисления сумы величин, координаты которых удовлетворяют определенные условия (то есть, если определенная величина принадлежит соответствующему множеству). В Excel такую процедуру исполняет функция =СУММЕСЛИ(). Например, сума входящих потоков узла определяется за формулой =СУММЕСЛИ(Все концы дуг; узел; потоки), то есть, суммируются потоки по тем дугам, концы которых совпадают с поточным узлом.
За формулой =СУММЕСЛИ(Все начала дуг; узел; потоки) суммируют выходящие потоки.

Запускаем программу Поиск решений командой Данные/Анализ / Поиск решенияExcel 2007) Сервис/Поиск решенияExcel 2003 и ниже). В полях Установить целевую ячейку, Изменяя ячейки, Ограничения вводим соответствующие адреса ячеек. Так как это линейная модель, то не забываем фиксировать в окне Параметры поиска решений переключатель на позицию Линейная модель и Неотрицательные значения. Нажимаем кнопку Выполнить и в появившемся окне Результаты поиска решения выводим отчет по устойчивости.

Анализ результата.
Найденные критические работы дают максимальную продолжительность проекта – 48.
Нормированные стоимости (Н-стоим) некритических работ указывают на резерв времени.
Теневые цены (Т-цена) для узлов-событий определяют частичные критические пути от узла 1 к всем остальным узлам, включительно узел 9.




Дата добавления: 2014-12-18; просмотров: 59 | Поможем написать вашу работу | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
История математического программирования/ исследование операций| Контрольная работа 1

lektsii.net - Лекции.Нет - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав