МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

ВВЕДЕНИЕ

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

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

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

Экономическая наука давно использует модели. Одна из первых экономических моделей — модель воспроизводства Ф. Кене — относится к 1758 г. Совершенствование экономико-математических моделей привело к дальнейшему развитию моделирования в экономике. И сейчас ни одна экономическая теория не обходится без математического описания современных экономических процессов.

Одним из наиболее практически важных вопросов экономики является построение хозяйственного плана на разных уровнях эконо

3

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

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

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

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

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

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

Рассмотрим некоторые из задач планирования и управления, математические модели которых сводятся к оптимизационным задачам или так называемым задачам математического программирования.

4

Определение наилучшего состава смеси

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

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

Задача об оптимальном плане выпуска продукции

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

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

5

Оптимизация межотраслевых потоков

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

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

Транспортная задача

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

Простейшая задача размещения

Пусть в известных пунктах имеются или могут быть размещены предприятия, производящие некоторый продукт. Этот продукт потребляется в других известных пунктах.

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

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

6

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

Другие виды оптимизационных задач

Приведем типичные классы задач:

1) управление запасами (с увеличением запасов увеличиваются расходы на хранение, но при этом уменьшаются потери из-за возможной их нехватки);

2) распределение ресурсов (для определенных наборов работ необходимо так распределить ресурсы, чтобы получить наибольшую прибыль при выполнении этих работ либо минимизировать потери, связанные с неполным обеспечением ресурсами) ;

3) ремонт и замена оборудования (работающее оборудование со временем изнашивается, устаревает и подлежит замене, поэтому желательно определить наилучшие сроки восстановительного ремонта и момент замены оборудования модернизированным);

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

5) календарное планирование (позволяет составить такое расписание для загрузки оборудования, чтобы суммарная продолжительность комплекса завершенных работ была минимальной);

6) сетевое планирование и управление (имеет место при выполнении сложных и дорогостоящих объектов, когда необходимо согласование сроков завершения отдельных комплексов работ и моментов запуска операций всего комплекса);

7) выбор маршрута (при проектировании коммуникаций или трубопроводов необходимо выбирать наилучшее их расположение, чтобы оптимизировать потоки в сетях);

8) комбинированные задачи (содержат несколько типичных задач одновременно).

7

Разработка моделей и их типы

Остановимся подробнее на формализации моделей.

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

При построении математических моделей исходят из следующих принципов:

1) изучаются и анализируются причинно-следственные связи;

2) используются аналогии;

3) проводятся эксперименты (если это возможно) для выявления существенных переменных.

Управляемые переменные (значения которых можно изменять в определенных пределах) обозначим х\, Х2, ■ ■ ■, хп и объединим их в вектор х = (х±,... ,хп). Неуправляемые переменные (значения которых изменять нельзя) запишем в вектор у = (у\,..., ут). Размерности векторов при этом могут быть разными, т. е. п ф т.

Пусть функция, зависящая как от управляемых, так и неуправляемых переменных, Е = f(x\,X2,.. .,хп,1/1,1/2, ■■ ■, Ут)-, или Е = f(x, у), является показателем качества или эффективности системы.

Набор функций gi(x,y), і = 1, 2,..., т задает соотношения между показателями функционирования системы, а неравенства §і(х,у) < Ьі, і = 1,2,... ,т задают ограничения на все имеющиеся в системе ресурсы.

Тогда в наиболее общем случае задача оптимизации формулируется следующим образом: найти такое значение вектора х = = (х\,Х2, ■ ■ ■ ,хп), при котором целевая функция Е = f(x,y) достигает экстремального (максимального или минимального) значения и при этом удовлетворяются все существующие ограничения на вектор управляемых переменных.

В математическом представлении эта задача имеет такой вид:

найти

extr Е = /(ж, у) (1)

при ограничениях

9г{х,у) < h

її

г = 1,2,..., т.

(2)

8

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

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

В зависимости от вида целевой функции и ограничений экономико-математические модели делятся на виды:

1) если функции f(x,y) и gi(x,y), і = 1,... ,т линейны относительно X, то имеем задачи линейного программирования:

2) если хотя бы одна из этих функций нелинейна относительно х, то имеем задачи нелинейного программирования;

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

4) стохастическое программирование используется в том случае, если вектор неуправляемых переменных у случаен (в этих задачах рассматривается математическое ожидание функции цели при вероятностных ограничениях);

5) если на управляемые переменные накладывается ограничения целостности (переменные ж являются целыми либо натуральными числами), то используются методы дискретного программирования;

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

Цель настоящего пособия — привести подробные постановки перечисленных задач и основные методы их решения.

9

 

 ... 3



Обратная связь

По любым вопросам и предложениям

Имя и фамилия*

Е-меил

Сообщение*

↑ наверх