ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 346
Скачиваний: 11
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
15 методы линейного целочисленного программирования. К комбинаторным относят метод ветвей и границ.
Рис. 1.3. Важнейшие области применения основных классов ЭММ
3. Математическая статистика используется для корреляционного, ре- грессионного и дисперсионного анализа экономических процессов и явле- ний. Корреляционный анализ применяется для установления тесноты связи между двумя или более стохастически независимыми процессами или явле- ниями. Регрессионный анализ устанавливает зависимость случайной величи- ны от неслучайного аргумента. Дисперсионный анализ - установление зави- симости результатов наблюдений от одного или нескольких факторов в целях выявления важнейших.
4. Динамическое программирование используется для планирования и анализа экономических процессов во времени. Динамическое программиро- вание представляется в виде многошагового вычислительного процесса с по- следовательной оптимизацией целевой функции. Некоторые авторы относят сюда же имитационное моделирование.
5. Теория игр представляется совокупностью методов, используемых для определения стратегии поведения конфликтующих сторон.
Электронный архив УГЛТУ
16 6. Теория массового обслуживания - большой класс методов, где на ос- нове теории вероятностей оцениваются различные параметры систем, харак- теризуемых как системы массового обслуживания.
7. Теория управления запасами объединяет в себе методы решения за- дач, в общей формулировке сводящихся к определению рационального раз- мера запаса какой-либо продукции при неопределенном спросе на нее.
8. Стохастическое программирование. Здесь исследуемые параметры яв- ляются случайными величинами.
9. Нелинейное программирование относится к наименее изученному, применительно к экономическим явлениям и процессам, математическому направлению.
10. Теория графов - направление математики, где на основе определен- ной символики представляется формальное описание взаимосвязанности и взаимообусловленности множества элементов (работ, ресурсов, затрат и т.п.).
До настоящего времени наибольшее практическое применение получили так называемые сетевые графики.
1.4. Классификация задач
математического программирования
Все модели могут быть классифицированы в зависимости от природы и свойств операции, характера решаемых задач, особенностей применяемых математических методов [1,3].
Прежде всего необходимо выделить большой класс оптимизационных моделей. Такие модели нужны при попытке оптимизировать планирование и управление сложными системами, в первую очередь экономическими систе- мами. Оптимизационную задачу можно сформулировать следующим обра- зом: найти значения переменных x
1
,x
2
,…,x
n
,
которые при заданных условиях
a
1
,a
2
,…,a
m
, удовлетворяют системе неравенств (уравнений)
(
)
(1.1) и обращают в экстремум (минимум или максимум) целевую функцию, т.е. критерий эффективности:
( ) (
) (1.2)
Если имеются условия неотрицательности значений переменных x
1
,
x
2
,..., x
n
, то они так же входят в ограничение (1.1). В тех случаях, когда функ- ции f и g
i
дважды дифференцируемы, для поиска условного экстремума
Электронный архив УГЛТУ
17
(максимума или минимума) функции f можно использовать классические ме-
тоды оптимизации. Однако их применение в исследовании операций весьма ограничено или вообще невозможно, если множество допустимых значений аргументов дискретно или же функция f представлена в табличном виде. В этих случаях для решения задачи, представленной отношениями (1.1) и (1.2), используются методы математического программирования.
В основе классификации задач математического программирования ле- жит вид функций, задающих критерий эффективности и ограничения, зави- симость их от такого параметра, как время, стохастический характер поведе- ния и т.п.
Если критерий эффективности F(X) представляет собой линейную функцию, а функции g
i
(x) в системе ограничений также линейны, то такая за- дача является задачей линейного программирования(ЗЛП).
Если, исходя из содержательного смысла ЗЛП, её решения должны быть целыми числами, то это - задача целочисленного программирования.
Если критерий эффективности F(X) и (или) система ограничений g
i
(x) задаются нелинейными функциями, то это – задача нелинейного программи-
рования. В частности, если указанные функции обладают свойствами выпук- лости, то это задача выпуклого программирования. В свою очередь среди за- дач выпуклого программирования выделяют наиболее простые задачи квад-
ратичного программирования, в которых целевая функция представляет со- бой полином второй степени (квадратичную форму) относительно перемен- ных x
1
, x
2
,..., x
n
, а область допустимых значений решений задается линейны- ми ограничениями.
Если в задаче имеется переменная времени и критерий эффективности
F(X) выражается не в явном виде, как функция переменных, а косвенно – че- рез уравнения, описывающие протекание операций во времени, то это задача
динамического программирования.
Если критерий эффективности F(X) и система ограничений g
i
(x) задают- ся функциями вида то имеет место задача геометрическо-
го программирования.
Если функции F(X) и / или g
i
(x) зависят от параметров, то получается задача параметрического программирования.
Если эти функции носят случайный, точнее вероятностный, характер, то это - задача стохастического программирования.
Если точный оптимум найти алгоритмическим путем невозможно из-за чрезмерно большого числа вариантов решений, прибегают к методам эври-
стического программирования, которые позволяют существенно сократить просматриваемое число вариантов и получить, если не оптимальное, то вполне удовлетворительное с точки зрения практики, решение.
Электронный архив УГЛТУ
18
1.5. Принципы построения
экономико-математических моделей
В основе построения ЭММ и процесса моделирования принято считать важными следующие принципы.
1. Принцип достаточности исходной информации. В каждой модели должна использоваться только та информация, которая известна с точностью, требуемой для получения результатов моделирования.
2. Принцип инвариантности (однозначности) информации требует, что- бы входная информация, используемая в модели, была независима от тех па- раметров моделируемой системы, которые еще неизвестны на данной стадии исследования.
3. Принцип преемственности. Сводится к тому, что каждая последую- щая модель не должна нарушать свойств объекта, установленных или отра- женных в предыдущих моделях.
4. Принцип эффективной реализуемости. Необходимо, чтобы модель могла быть реализована при помощи современных вычислительных средств.
Некоторые исследователи при построении ЭММ и моделировании ис- пользуют следующие правила:
● необходимо соизмерять точность и подробность модели, во-первых, с точностью тex исходных данных, которыми располагает исследователь, и, во- вторых, с теми результатами, которые требуется получить;
● ЭММ должна отражать существенные черты исследуемого явления и при этом не должна его сильно упрощать;
● ЭММ не может быть полностью адекватна реальному явлению, по- этому для его исследования лучше использовать несколько моделей, для по- строения которых применены разные математические методы, если при этом получаются сходные результаты, то исследование заканчивается, если ре- зультаты сильно различаются, то следует пересмотреть постановку задачи;
● любая сложная экономическая система всегда подвергается внешним и внутренним воздействиям, следовательно, экономико-математическая модель должна быть устойчивой (сохранять свойства и структуру при этих воздействи- ях).
1.6. Этапы экономико-математического
моделирования
Основные этапы процесса моделирования были рассмотрены выше (см. рис. 1.2). В различных отраслях знаний они приобретают свои специфиче-
Электронный архив УГЛТУ
19 ские черты. Проанализируем последовательность и содержание этапов одно- го цикла экономико-математического моделирования (рис. 1.4).
Рис. 1.4. Этапы экономико-математического моделирования
Первый этап. Постановка проблемы (задачи) и её качественный анализ.
Главное на этом этапе - чётко сформулировать сущность проблемы, опреде- лить принимаемые допущения, а также определить те вопросы, на которые требуется получить ответ.
Этап включает выделение важнейших черт и свойств моделируемого объекта, основных зависимостей, связывающих его элементы. Здесь же про- исходит формулирование гипотез, хотя бы предварительно объясняющих по- ведение объекта.
Второй этап. Построение математической модели. Это этап формали- зации задачи, т.е. выражения ее в виде математических зависимостей и от- ношений (функций, уравнений, неравенств, схем). Как правило, сначала определяется тип математической модели, а затем уточняются детали.
Неправильно полагать, что, чем больше факторов учитывает модель, тем лучше она работает и дает лучшие результаты. Излишняя сложность модели затрудняет процесс исследования. При этом нужно учитывать не только ре- альные возможности информационного и математического обеспечения, но и сопоставлять затраты на моделирование с получаемым эффектом (при воз- растании сложности модели прирост затрат может превысить прирост эф- фекта).
Третий этап. Математический анализ модели. Цель - выявление общих свойств и характеристик модели. Применяются чисто математические приё- мы исследования. Наиболее важный момент - доказательство существования решений в сформулированной модели. Если удастся доказать, что задача не имеет решения, то необходимость в последующей работе по данному вариан- ту модели отпадает; следует скорректировать либо постановку задачи, либо способы ее математической формализации.
Электронный архив УГЛТУ
20
Однако модели сложных экономических объектов с большим трудом поддаются аналитическому исследованию. В тех случаях, когда не удается выяснить общие свойства модели аналитическими методами, а упрощение модели приводит к недопустимым результатам, прибегают к численным ме- тодам исследования.
Четвертый этап. Подготовка исходной информации. Численное моде- лирование предъявляет жесткие требования к исходной информации. В то же время реальные возможности получения информации существенно ограни- чивают выбор используемых моделей. При этом принимается во внимание не только возможность подготовки информации (за определенный срок), но и затраты на подготовку соответствующих информационных массивов. Эти за- траты не должны превышать эффекта от использования данной информации.
Пятый этап. Численное решение. Это составление алгоритмов, разра- ботка программ и непосредственное проведение расчётов на ЭВМ.
Шестой заключительный этап. Анализ результатов и их применение: проверяются правильность, полнота и степень практической применимости полученных результатов.
Естественно, что после каждого из этапов возможен возврат к одному из предыдущих в случае необходимости уточнения информации, пересмотра результатов выполнения отдельных этапов. Например, если на этапе 2 фор- мализовать задачу не удается, то необходимо вернуться к постановке про- блемы (этап 1). Соответствующие связи на рис. 1.4 не показаны, чтобы не за- громождать схему.
Электронный архив УГЛТУ
21
1 2 3 4 5 6 7 8 9 ... 18
2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
2.1. Общая постановка задачи
линейного программирования
Линейное программирование – направление математики, изучающее мето- ды решения экстремальных задач, которые характеризуются линейной зависи- мостью между переменными и линейным критерием оптимальности.
В данном случае программирование - это, конечно, не составление про- грамм для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий.
К математическим задачам линейного программирования (ЗЛП) относят исследования конкретных производственно-хозяйственных ситуаций, кото- рые в том или ином виде интерпретируются как задачи об оптимальном ис- пользовании ограниченных ресурсов.
Круг задач, решаемых при помощи методов линейного программирова- ния достаточно широк. Это, например:
● задача об оптимальном использовании ресурсов при производствен- ном планировании;
● задача о смесях (планирование состава продукции);
● задача о нахождении оптимальной комбинации различных видов про- дукции для хранения на складах (управление товарно-материальными запа- сами или «задача о рюкзаке»);
● транспортные задачи (анализ размещения предприятия, перемещение грузов).
Линейное программирование – наиболее разработанный и широко при- меняемый раздел математического программирования (кроме того, сюда от- носят: целочисленное, динамическое, нелинейное, параметрическое про- граммирование). Это объясняется следующим:
● математические модели большого числа экономических задач линей- ны относительно искомых переменных;
● данный тип задач в настоящее время наиболее изучен; для него разра- ботаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;
● многие задачи линейного программирования, будучи решенными, нашли широкое применение;
● некоторые задачи, которые в первоначальной формулировке не явля- ются линейными, после ряда дополнительных ограничений и допущений мо- гут стать линейными или могут быть приведены к такой форме, что их мож- но решать методами линейного программирования.
Электронный архив УГЛТУ
22
Экономико-математическая модель любой задачи линейного програм- мирования включает целевую функцию, оптимальное значение которой
(максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование не отрицательности пере- менных.
В общем виде модель записывается следующим образом: целевая функция:
F(x)= c
1
x
1
+ c
2
x
2
+ ... + c
n
x
n
→ max(min); (2.1) ограничения:
{
{ }
{ }
{ }
(2.2) требование неотрицательности:
̅̅̅̅̅
(2.3)
При этом a
ij
, b
i
, c
j
̅̅̅̅̅̅
̅̅̅̅̅- заданные постоянные величины.
Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3).
Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми.
Вектор
̅ (
) удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программиро- вания. План при котором функция (2.1) достигает своего максимального
(минимального) значения, называется оптимальным.
Далее приведем примеры некоторых типовых задач, решаемых при по- мощи методов линейного программирования. Такие задачи имеют реальное экономическое содержание. Сейчас лишь сформулируем их в терминах ЗЛП, а методы решения подобных задач рассмотрим ниже.
1. Задача об оптимальном использовании ресурсов при производствен-
ном планировании.
Общий смысл задач этого класса сводится к следующему.
Предприятие выпускает n различных изделий. Для их производства тре- буется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют со- ответственно b
1
, b
2
,..., b
m условных единиц.
Электронный архив УГЛТУ