Имя материала: Динамическое программирование в экономических задачах

Автор: Лежнёв А. В.

Заключение

зано число выполненных творческих операций, а по вертикали — число выполненных рутинных операций. Точки на схемах, приведенных на рис. 3.37-3.40, отвечают промежуточным положениям в ходе выполнения операций, а числа между точками указывают время выполнения соответствующих операций.

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

Доказать, что в любом графе число вершин нечетной степени четно.

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

Доказать, что если число ребер графа порядка п > 2 больше C2_i, то граф является связным.

Доказать, что не существует графа, степени всех вершин которого попарно различны.

Указание. Применить метод математической индукции по порядку графа, учесть, что в графе порядка п максимальная степень вершин не превосходит п—1, и рассмотреть изолированные вершины.

 

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

Рассмотренные в пособии задачи иллюстрируют логику метода ДП, не представляют вычислительных сложностей и допускают «ручной» счет. В то же время большинство реальных производственных задач являются столь объемными, что не могут быть решены в разумные сроки без применения мощных вычислительных средств типа ЭВМ. Обозначенный «разрыв» между уровнями требуемых средств не должен создавать впечатление недостаточной «приспособленности» изученного метода для решения реальных задач; напротив, именно на объемных трудоемких задачах достоинства и преимущества передовых математических методов — в том числе и метода ДП — проявляются наиболее отчетливо.

В этой связи представляется целесообразным обучение студентов программным средствам, позволяющим решать подобные объемные задачи и в то же время не требующим глубокого знания программирования и нюансов математических методов. Среди таких программных средств можно отметить табличный процессор Excel пакета Microsoft Office с надстройкой «Поиск решения», специализированную систему QSB (Quantitative Systems for Business) для решения типовых задач математического программирования, а также математические пакеты MathCAD, Matlab, Maple. Такой подход в полной мере отвечает современным тенденциям математизации наук через посредство компьютерных технологий и позволяет эффективно сочетать устоявшиеся традиционные методы преподавания математики «с мелом у доски» с использованием современных программно-технических средств. Рассмотрение данного вопроса в силу его компьютерной специфики оставлено за пределами настоящего учебного пособия.

Остановимся коротко на некоторых направлениях развития и обобщения метода ДП, определяемых как потребностями практики, так и теоретическими интересами.

 

1. В рассмотренных задачах фазовые и управляющие переменные были одномерными, или скалярными, т. е. их значениями являлись числа. Реальные производственные задачи зачастую приводят к задачам ДП с многомерными переменными, являющимися величинами векторными. Справедливость общего принципа оптимальности при этом не нарушается, однако решение задач существенно загромождается рассмотрением огромного числа различных допустимых вариантов. Данное обстоятельство охарактеризовано известным выражением Р. Беллмана как «проклятие многомерности».

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

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

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

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

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

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |