Тема № 8

Математическое моделирование в экономике (4 часа)

 

Введение

В этой теме мы рассмотрим оптимизационные задачи, линейное, нелинейное, динамическое  программирование и сетевой анализ.

План:

1.      Целенаправленное управление. Оптимизационные задачи.

2.      Линейное программирование. Двойственная задача. Метод объективно обусловленной оценки. Транспортная задача.

3.      Нелинейное программирование: постановка задачи, особенности целевой функции и ограничений, методы решения.

4.      Динамическое программирование. Планирование.

5.      Сетевой анализ. Алгоритм нахождения потока максимальной величины в сети.

 

1. Целенаправленное управление. Оптимизационные задачи.

Целенаправленное управление

Особенности применения метода математического моделирования в экономике

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

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

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

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

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

Сложность экономики иногда рассматривалась как обоснова­ние невозможности ее моделирования, изучения средствами математики. Но такая точка зрения в принципе неверна. Моделировать можно объект любой природы и любой сложности. И как раз сложные объекты представляют наибольший интерес для моделирования; именно здесь моделирование может дать результаты, которые нельзя получить другими способами исследования.

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

Целенаправленное управление экономикой региона

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

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

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

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

Проект организации деятельности – необходимое условие преобразования, но одного его часто бывает недостаточно. Если преобразование затрагивает чьи-то интересы, то его реализация обязательно столкнется с явным или скрытым сопротивлением. Чем больше сила сопротивления, тем меньше шансов на успех. Игнорирование субъективного фактора – гарантия неуспеха.

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

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

Оптимизационные задачи

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

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

При постановке задачи оптимизации необходимо:

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

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

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

4.      Учет ограничений.

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

·     управляемых переменных;

·     неуправляемых переменных;

·     формы функции (вида зависимости между ними).

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

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

·        на линейные;

·        нелинейные;

·        детерминированные;

·        стохастические (группы кривых С i ).

Стохастические ограничения являются возможными, вероятностными, случайными.

Оптимизационные задачи решаются методами математического программирования, которые подразделяются на:

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

·     нелинейное программирование (целевая функция и ограничения могут быть нелинейными функциями);

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

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

·      выпуклое программирование;

·     исследование операций;

·      геометрическое программирование и др.

Главная задача математического программирования - это нахождение экстремума функций при ограничениях в форме уравнений и неравенств.

2. Линейное программирование. Двойственная задача. Метод объективно обусловленной оценки. Транспортная задача.

Линейное программирование

Одно из направлений в экономике – линейное программирование.

Линейное программирование – это направление, посвященное теории и методам решения задач об экстремумах (max, min) линейных функций на множествах, задаваемых системами линейных неравенств и/или равенств.

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

Математическая модель любой задачи линейного программирования включает в себя:

·         максимум или минимум целевой функции (критерий оптимальности);

·         систему ограничений в форме линейных уравнений и неравенств;

·         требование неотрицательности переменных.

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

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

·     рационального использования сырья и материалов; задачи оптимизации раскроя;

·      оптимизации производственной программы предприятий;

·      оптимального размещения и концентрации производства;

·      составления оптимального плана перевозок, работы транспорта;

·      управления производственными запасами;

·     и многие другие, принадлежащие сфере оптимального планирования.

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

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

Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода.

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

Рассмотрим оптимизационную задачу, решаемую методами линейного программирования.

Оптимизационная задача с линейной зависимостью между переменными

Пусть:

b i  - количество ресурса вида i ( i  = 1, 2, ..., m );

a i ,  j  - норма расхода i -того ресурса на единицу j -того вида продукции;

x j  - количество продукции вида j ( j  = 1, 2, ..., n );

c j  - прибыль (доход) от единицы этой продукции (в задачах на минимум  себестоимость продукции).

 

Тогда оптимизационная задача линейного программирования в общем виде может быть сформулирована и записана следующим образом:

Найти переменные x j ( j =  1, 2, ...,  n ), при которых целевая функция

была бы максимальной (минимальной), не нарушая следующих ограничений:

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

где k - количество дополнительных переменных, и условие неотрицательности искомых переменных: x j  ³ 0.

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

Пример.

 

Фирма производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3 м2 досок, а для модели В - 4 м2. Фирма может получать от своих поставщиков до 1700 м2 досок в неделю. Для каждого изделия модели А требуется 12 мин. машинного времени, а для изделия модели В - 30 мин. В неделю можно использовать 160 часов машинного времени.

Сколько изделий каждой модели следует выпускать фирме в неделю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В - 4 дол. прибыли?

Построение математической модели.

 

Пусть x1 - количество выпущенных за неделю полок модели А, а x2 - количество выпущенных полок модели В. Тогда:

3x1 - количество досок требуемых на неделю для изготовления полок модели А

4x2- количество досок требуемых на неделю для изготовления полок модели В

3x1 + 4x2- количество досок требуемых на неделю для изготовления книжных полок двух моделей, а по условию задачи это число не должно превышать 1700 м2, следовательно, получаем первое ограничение:

3x1+ 4x2<=1700 (1)

 

Найдем ограничение на использование машинного времени.

12 мин. составляют 0,2 часа, а 30 мин. - 0,5 часа, таким образом:

0,2x1 - количество времени, требуемое на неделю для обработки полок модели А;

0,5x2 - количество времени, требуемое на неделю для обработки полок модели В;

0,2x1 + 0,5x2 - количество времени, требуемое на неделю для обработки двух моделей, а по условию задачи это число не должно превышать 160 часов, следовательно, получаем второе ограничение:

0,2x1 + 0,5x2<=160 или 2x1 + 5x2<=1600 (2)

 

Кроме того, поскольку x1 и x2 выражают еженедельный объем выпускаемых изделий, то они не могут быть отрицательными, то есть

x1>=0, x2>=0 (3)

 

Наша задача состоит в том, чтобы найти такие значения x1 и x2, при которых еженедельная прибыль будет максимальной. Составим выражение для еженедельной прибыли:

2x1 - еженедельная прибыль, получаемая от продажи полок модели А

4x2 - еженедельная прибыль, получаемая от продажи полок модели В

F=2x1 + 4x2 - еженедельная прибыль, которая должна быть максимальной. Таким образом, имеем следующую математическую модель для данной задачи.

F=2x1 + 4x2->max

 

Полученная модель является задачей линейного программирования. Функция F - это целевая функция, она является линейной функцией своих переменных (x1 и x2). Ограничения на эти переменные (1) и (2) тоже являются линейными. Выполнено условие неотрицательности для переменных x1 и x2.

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

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

Двойственная задача линейного программирования. Метод объективно обусловленной оценки

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

Исходная модель предполагает, сколько и какой продукции необходимо изготовить с заданной стоимостью cj (j=) и при заданных ресурсах bi (i=) и получить максимальную прибыль в стоимостном выражении.

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

 

Двойственная задача линейного программирования может быть сформулирована следующим образом:

найти переменные y i ( i  = 1, 2, ...,  ), при которых целевая функция была бы минимальной

не нарушая ограничений:

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

 

Компоненты решения двойственной задачи называются объективно обусловленными оценками.

Прямая и обратная задачи линейного программирования связаны между собой теоремами двойственности.

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

или

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

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

 

(1)

 

(2)

Следствие 1 . Пусть оптимальное значение некоторой переменной двойственной задачи строго положительно

Тогда из условия (1) получим

или

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

Следствие 2 . Пусть для оптимального значения некоторой переменной x i прямой задачи выполняется условие строгого неравенства

Тогда, основываясь на том же первом условии (1), можно заключить, что y i  = 0.

Экономически это означает, что если в оптимальном плане какой-то ресурс используется не полностью, то его объективно обусловленная оценка обязательно равна нулю.

Свойства объективно обусловленных оценок и их анализ

1.      Объективно обусловленные оценки являются устойчивыми в некоторых пределах изменения исходных условий задачи.

2.      Они выступают как мера дефицитности ресурсов.

3.      Выступают как мера влияния ограничений на целевую функцию при приращении данного ресурса на единицу.

4.      Объективно обусловленные оценки выступают как меры взаимозаменяемости резервов (ограничений).

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

 

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

 

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

 

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

 

Примером типичной транспортной задачи является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям.

Стандартная транспортная задача - это задача разработки наиболее экономичного плана перевозки продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции. [1]

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

 

Пусть имеется m складов, в которых сосредоточен некоторый однородный продукт (ГСМ, боеприпасы и т.д.) в количествах соответственно аi(i=1,2,…,m) единиц. Имеется n потребителей этого продукта в количествах соответственно bj(j=1,2,…,n) единиц. На основании опытов и расчетов известно, что на доставку одной единицы продукта с i-того склада j-тому потребителю затрачивается сij денежных единиц.

Все значения cij являются постоянными величинами. Перечисленные исходные данные помещены в таблице 1.

Обозначим через xij³0 (i=1,2,…,m; j=1,2,…n) количество продукта, планируемого для доставки с i-того склада j-тому потребителю. Естественно, что если xij=0, то доставка продукта с i-того склада j-тому потребителю не планируется. План обеспечения всех потребителей определяется таблицей (матрицей):

 

                  (1)

 

 

Таблица 1

Склады

               Потребители

Запасы на складах

    1

    2

    …

   N

   1

 

cn                  

 

c12          

   

      

 c1n

   a1

   2

 c21

 c22

   

 c2n

   a2

  

   

   

   

   

  

   M

 cm1

 cm2

   

cmn

   am

Потребность

    b1

    b2

   

bn

 

 

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

 

              (2)

 

               (3)

 

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

 

 

Последнее выражение означает, что запасов на складах достаточно для снабжения всех потребителей.

Суммарная стоимость перевозок для любого выбранного плана (1) определяется выражением:

 

                (4)

 

Транспортная задача линейного программирования по критерию стоимости формулируется следующим образом:

 

Найти такие значения xij (т.е. найти такой план перевозок (1)), удовлетворяющий условиям (2), (3), при которых суммарная стоимость перевозок (4) будет минимальной.

 

При больших m и n эта задача решается на ЭВМ. Для этого нужно ввести в машину исходные данные, помещенные в таблице 1 и воспользоваться разработанной программой. При небольших m и n задача может быть решена вручную с использованием общих методов решения. Для значений m и n до 5-6 задачу часто удается решить путем прикидочных расчетов, перебором вариантов и логических размышлений.

 

Задача. Для обеспечения ГСМ четырех танковых соединений имеется три склада. Известны запасы ГСМ и потребности в нем соединений. Определение стоимости доставки одной тонны ГСМ из каждого склада в любое соединение. Все исходные данные записаны в таблице 2.

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

 

Решение: Обозначим через xij(i=1,2,3; j=1,2,3,4) количество ГСМ, планируемых для доставки с i-того склада (i=1,2,3) j-тому соединению (j=1,2,3,4).

  

Таблица 2

Склады

Соединения

Запасы ГСМ на складах

1

2

3

4

1

x11=350

x12=0

x13=50

x14=500

900

2

x21=0

x22=200

x23=0

x24=0

300

3

x31=0

x32=250

x33=350

x34=0

60

Потребность в ГСМ

350

450

400

500

 

 

 

Выбор планов зависит от запасов ГСМ на складах и потребностей в нем соединений, что математически определяется выражениями:

 

        (21)

             (31)

 

Суммарные расходы на перевозку ГСМ определяются линейными выражениями:

 

 (41)

 

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

Эта задача решается элементарными подсчетами и рассуждениями.

 

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

Очевидно, в 1-е и 4-е соединение целесообразно завозить ГСМ полностью из 1-го склада, поэтому целесообразно выбрать x11=350, x14=500. Во второе соединение выгодно доставить горючее целиком с 3-го склада. Но тогда будут большие расходы при доставке ГСМ в 3-е соединение из 2-го склада. Поэтому целесообразно выбрать x13=50, x33=350, т.е. завести горючее в 3-е соединение с 1-го и 3-го складов, а 200 т. для 2-го соединения завести из склада, x22=200, x32=250.

Результаты расчетов занесены в таблице 2, по которой удобно проверить выполнение условий (21), (31), найдя суммы xij по строкам и столбцам.

При таком плане расходы будут минимальными:

 

 

Для сравнения, какую можно иметь экономию в средствах, выбрав оптимальный план, рассмотрим один из возможных планов:

x11=350, x12=450, x13=x14=0, x21=x22=x23=0,

x24=300, x31=x32=0, x33=400, x34=200.

 

При этом плане стоимость перевозок будет равна:

 

 

Она больше на 1950 единиц Kmin, что составляет более чем 30%.

Полученное оптимальное решение является основой для применения объективного решения на снабжение ГСМ соединений с учетом конкретной обстановки.

 

3. Нелинейное программирование: постановка задачи, особенности целевой функции и ограничений, методы решения.

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

Постановка и классификация задач нелинейного программирования

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

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

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

В самом общем виде классификация представлена в таблице 3. [2]

Таблица 3

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

В каждом конкретном случае способ выбирается в зависимости от вида функции F(x).

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

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

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

Общая характеристика методов решения задач нелинейного программирования

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

 

Основные классы методов нелинейного программирования:

·        метод штрафных функций;

·        метод барьерных функций;

·        метод центров;

·        методы Лагранжа;

·        метод возможных направлений;

·        метод проекции градиента;

·        метод условного градиента;

·        метод линеаризации.

 

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

Большинство методов нелинейного программирования используют идею движения в n-мерном пространстве в направлении оптимума. При этом из некоторого исходного или промежуточного состояния Uk осуществляется переход в следующее состояние Uk+1 изменением вектора Uk  на величину DUk, называемую шагом, т.е.

 

Uk+1=Uk+DUk 

(26) 

 

В ряде методов шаг ,т.е. его величина и направление определяется как некоторая функция состояния Uk

 

DUk=f(Uk

(27) 

 

Следовательно, согласно (26) новое состояние Uk, получаемое в результате выполнения шага (27) может рассматриваться как функция исходного состояния Uk

 

Uk+1=Uk+f(Uk) 

(28) 

В некоторых методах DUk обусловлен не только состоянием Uk, но и рядом предшествующих состояний

 

        DUK=f(Uk) ,Uk-1...,Uk-2 

(29)

        Uk+1=Uk+f(Uk),Uk-1...,Uk-2 

 (30) 

 

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

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

Методы нелинейного программирования в соответствии со способом определения шага поиска R() можно отнести к одному из 3-х типов:

1. Безградиентные методы.

2. Градиентные методы.

3. Методы случайного поиска.


Все эти методы можно назвать прямыми итеративными методами. [3]

 

Пример: нелинейная задача размещения производства.

Пусь имеется m мест строительства новых предприятий, производящих однородный продукт. Известны n пунктов потребления данного продукта. Заданы:

bj - потребность в продукте j-го пункта потребления;

ai - проектная мощность производства в i-ом месте строительства;

cij - затраты на транспортировку единицы продукта из i-го места производства в j-ый пункт потребления;

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

 

Требуется определить объемы производства хi и объемы xij перевозок от i-го поставщика j-му потребителю, удовлетворяющие условиям:

формула

формула      j=1,...,n

формула      i=1,...,m

формула      (i=1,...,m;j=1,...,n)

 

4. Динамическое программирование. Планирование.

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

Метод динамического программирования - один из наиболее мощных и широко известных математических методов современной теории управления, был предложен в конце 50-х годов американским математиком Р. Беллманом и быстро получил широкое распространение.

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

Метод динамического программирования - широко известный и мощный математический метод современной теории управления.

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

u(t) k U(x(t), t),

где U(x(t), t) - множество в m-мерном пространстве, зависящее от n-мерного вектора x и от времени t.

2. Соотношение, определяющее переход системы из одного состояния в другое, может явно зависеть от времени. В этом случае  имеем

x(t + 1) = f (x(t), u(t), t),

где f (x, u, t) - заданная функция своих аргументов.

3. Критерий оптимальности также может содержать слагаемые, явно зависящие от времени, то есть иметь вид

где R(x, u, t) - заданная функция.

Соответствующие очевидные изменения следует внести и в другие соотношения.

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

Метод динамического программирования используется для исследования и решения задач оптимального управления процессами в условиях неопределенности. Здесь имеются в виду два различных типа проблем:

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

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

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

Отдельно следует сказать о задачах оптимального управления с непрерывным временем, описываемым дифференциальными уравнениями. В этом случае метод динамического программирования приводит к нелинейному дифференциальному уравнению в частных производных первого порядка. Теория решений этого уравнения, иногда называемого уравнением Гамильтона-Якоби - Беллмана - Айзекса, активно разрабатывается в последние годы.

Сетевое планирование

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

Ограничения на структуры сетевых графов:

·         в сетевом графике не должно быть тупиков, т.е. не должно быть событий, из которых не выходит ни одной работы;

·         сеть не должна иметь хвостовых событий, которым не предшествует ни одна работа.

·         в сети не должно быть замкнутых контуров;

·         в сетевой работе не допускается работы, имеющие одинаковые шифры;

·         любые два события должны быть непосредственно связаны не более чем одной работой;

·         в сети не рекомендуется иметь одно исходное и одно завершающее событие.

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

 

Количественные характеристики работы, продолжительность от времени:

1) события S(i) 3 параметра:

Ранний срок свершения i-го события – определяется продолжительностью max пути, предшествующего этому событию.

tp(i)=max t(Lni) или

tp(i)=max (tp(i) + t(i, j))

Поздний срок свершения i-го события

tп(i)=tкр -max(LCI) или

tп(i)=min (tп(j) - t(i, ji))

Резерв времени для i-го события

R(i)=tп(i) – tp(i)

 

2) работа Rab(i, j) 6 параметров:

Продолжительность работыt(i, j)

Ранний срок начала работы

tрн(i, j) = tp(i)

Ранний срок окончания работы

tро(i, j) = tp(i) + t(i, j)

Поздний срок начала работы

tпн(i, j) = tп(j) – t(i, j)

Поздний срок окончания работы

tпо(i, j) = tп(j)

Резерв времени пути

R(L) = tкр t(L), L – продолжительность пути

Полный резерв времени:

Rп(i, j) = tп(j) - tр(j) – t(i, j)

 

3) путь L 3 параметра:

t(L) – продолжительность пути

tкр – продолжительность критического пути

R(L) - резерв времени пути

 

Полный резерв времени Rп(i, j)  показывает, на сколько можно увеличить время выполнения датой работы, при условии, что срок выполнения комплекса работ не изменится. Полный резерв времени работы = резерву максимального из путей, проходящих через данную работу. Важным свойством полного резерва времени является то, что он принадлежит не только этой работе, но и всем полным путям, проходящим через эту работу. Работы лежащие на критическом пути не имеют резерва.

Кроме полного резерва времени выделяют еще 3 разновидности резерва:

R1частный резерв времени 1-го вида – часть полного резерва времени, на которую можно увеличить продолжительность работы не изменив при этом позднего срока ее начальной работы. R1(i, j) =Rп(i, j) – R(i)

RCчастный резерв времени 2-го вида – часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события. RС(i, j) =Rп(i, j) – R(j)

RНнезависимый резерв времени – часть полного резерва, полученная для случая, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие начинаются в ранние сроки. RН(i, j) =Rп(i, j) – R(i) - R(j).

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

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

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

 

5. Сетевой анализ. Алгоритм нахождения потока максимальной величины в сети.

 

 

Заключение

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

В следующей теме мы узнаем, что такое катастрофы, рассмотрим примеры катастроф типа "сборки".

 

Литература:

1.      Городецкая Н.В. Системный анализ. Практикум (часть 2): Учеб. пособие / Под ред. Л.И. Долинера. Екатеринбург: Рос. гос. проф.-пед. ун-т, 2003. 64 с.

2.      Постановка и классификация задач нелинейного программирования // www.do.rksi.ru/library/courses/km/tema2_6.dbk.

3.      Общая характеристика методов решения задач нелинейного программирования // www.xtf.opu.odessa.ua/konsp/MMXTP/RAZDEL5/glava55.htm

4.      Мадера А.Г. Математические модели в управлении // www.meu.rsuh.ru/madera/HTML-LR6.htm.