Математическое моделирование экономических процессов

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

1. Балансовые модели

Балансовые модели предназначены для анализа и планирования производства и распределения продукции на различных уровнях - от отдельного предприятия до народного хозяйства в целом. Если вспомнить историю народного хозяйства как Советского Союза и России, так и других развитых стран, то можно наблюдать, что в экономики многих государств, в разное время случались экономические кризисы разных крайностей от кризисов перепроизводства (США, середина ХХ века), до дефицита (Россия, конец ХХ века). Все эти экономические кризисы связаны с нарушением баланса между производством и потреблением. Из этих фактов видно, что баланс между произведенной продукцией и потреблением является важными критериями как для макроэкономики, так и для микроэкономики.

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

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

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

Рассмотрим процесс производства за некоторый период времени (например, год). Так, как валовой объем продукции любой i-й отрасли равен суммарному объему продукции, потребляемой n отраслями, и конечного продукта, то уравнение баланса между производством и потреблением будет иметь вид:

, (i=1,2,…, n) (1)

Уравнения (1) называются соотношениями баланса.

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

. (2)

Все, ранее рассмотренные показатели, можно записать в основную балансовую таблицу:

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

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

. (3)

Они получаются в результате деления всех элементов каждого столбца матрицы  на соответствующий элемент матрицы межотраслевых производственных связей Х. Коэффициенты прямых затрат имеют смысл количества потребления продукции j-й отрасли, необходимой для производства единицы продукции i-й отраслью. Из выражения (3) можно получить: . Подставив последнее выражение в соотношение баланса (1), получим:

. (4)

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

. (5)

Из последнего выражения можно найти значение конечного продукта при известном значении валового:

, (6)

где  - единичная матрица того же размера, что и А.

2. Теория игр

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

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

Чтобы исключить трудности, возникающие при анализе практических конфликтных ситуаций в результате наличия многих несущественных факторов, строится упрощенная модель ситуации. Такая модель называется игрой. Конфликтная ситуация в игровой моде развивается по определенным правилам. Естественной базой для анализа конфликтных ситуаций служат широко распространенные игры - шахматы, шашки, карточные игры. Поэтому теории игр свойственна следующая терминология: «игроки» (стороны, участвующие в конфликте), «выигрыш» (исход конфликта) и т.д.

Неопределенность результата игры вызывается различными причинами, которые можно разбить на три группы:

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

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

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

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

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

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

Простейший вид стратегической игры - игра двух лиц с нулевой суммой (сумма выигрышей сторон равна нулю). Игра состоит из двух ходов: игрок А выбирает одну из своих возможных стратегий A_i (i = 1, 2,…. m), а игрок В выбирает стратегию В_j (j = 1, 2,…, n), причем каждый выбор производится при полном незнании выбору другого игрока.

Цель игрока А - максимизировать функцию ц (A_i, B_j), в свою очередь, цель игрока В-минимизировать эту же функцию. Каждый из игроков может выбирать одну из переменных, от которых зависит значение функции. Если игрок А выбирает некоторую из стратегий Ai, то это само по себе не может влиять да значение функции ц (A_i, B_j).

Влияние Ai, на величину значения ц (A_i, B_j) является неопределенным; определенность имеет место только после выбора, исходя из принципа минимизации ц (A_i, B_j), другим игроком переменной B_j. При этом B_j определяется другим игроком. Пусть ц (A_i, B_j)= a_ij. Составим матрицу А:

Строки матрицы соответствуют стратегиям A_i, столбцы - стратегиям B_j. Матрица А называется платежной или матрицей игры. Элемент a_ij матрицы - выигрыш игрока А, если он выбрал стратегию A_i, а игрок В выбрал стратегию B_j.

Пусть игрок А выбирает некоторую стратегию A_i; тогда в наихудшем случае (например, если выбор станет известным игроку В) он получит выигрыш, равный min a_ij. Предвидя такую возможность, игрок А должен выбрать такую стратегию, чтобы максимизировать свой минимальный выигрыш a:

а = max min a_ij

i j

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

Игрок В, выбирая стратегию, исходит из следующего принципа: при выборе некоторой стратегии В_j его проигрыш не превысит максимального из значений элементов j-го столбца матрицы, т.е. меньше или равен max a_ij

Рассматривая множество max a_ij для различных значений j, игрок В, естественно выберет такое значение j, при котором его максимальный проигрыш в минимизируется:

в = min miax a_ij

i j

Величина в называется верхней ценой игры, а соответствующая выигрышу в стратегия Вj0 - минимаксной.

Фактический выигрыш игрока А при разумных действиях партнеров ограничен нижней и верхней ценой игры. Если же эти выражения равны, т.е.

max min aij = min max aij = u

i j j i

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

3. Теория массового обслуживания

Часто приходится сталкиваться с такими ситуациями:

· очередь покупателей в кассах магазинов;

· колонна автомобилей, движение которых остановлено светофором;

· ряд станков, вышедших из строя и ожидающих ремонта; и т.д.

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

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

В промышленности СМО применяется при:

поступлении сырья, материалов, комплектующих изделий на склад и выдаче их со склада;

обработке широкой номенклатуры деталей на одном и том же оборудовании;

организации наладки и ремонта оборудования;

определении оптимальной численности обслуживающих отделов и служб предприятий и т.д.

Основными элементами СМО являются источники заявок, их входящий поток, каналы обслуживания и выходящий поток.

В зависимости от характера формирования очереди СМО различают:

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

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

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

По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.

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

Рассмотрим в отдельности элементы СМО.

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

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

Ординарность потока определяется невозможностью одновременного появления двух или более заявок.

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



где - интенсивность потока заявок, т.е. среднее число заявок в единицу времени:

(чел./мин, р./ч, автом./дн., квт/ч),

где - среднее значение интервала времени между двумя соседними заявками.

Для такого потока заявок время между двумя соседними заявками распределено экспоненциально с плотностью вероятности

Случайное время ожидания в очереди начала обслуживания считают распределенным экспоненциально:

где v - интенсивность движения очереди, т.е. среднее число заявок, приходящихся на обслуживание в единицу времени:

где - среднее значение времени ожидания в очереди.

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

f(t_обс)=me^-mt_,

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

(чел./мин, р./дн., кг/ч, докум./дн.),

где среднее время обслуживания.

Важной характеристикой СМО, объединяющей l и m, является интенсивность нагрузки

p = l/m.

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

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

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

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

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

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

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

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

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

Пример. Пусть планируется деятельность некоторой системы S промышленных предприятий P1, P2, …, Pn на некоторый период времени T, состоящий из k хозяйственных лет t1 (i = 1, 2, …, k), причем

k

T = ? ti

I = 1

В начале периода T на развитие предприятий выделены основные средства D. В начале каждого хозяйственного года производится финансирование всей системы предприятий, т.е. выделяется доля основных средств. Известны первоначальное состояние системы S₀, характеризуемое количеством средств, уже вложенных в предприятия, и конечное состояние S_k, характеризуемое всей дополнительно вложенной суммой D. Как следует распределить по предприятиям и годам основные средства D, чтобы к концу периода T суммарный доход W от всей системы предприятий был максимальным?

Решение. Обозначим через x_ij сумму, выделяемую в начале i-ого года j-ому предприятию (i=1, 2, …, k; j=1, 2, …, n). Предположим, что средства на i-ом этапе распределены, т.е. выбрано определенное управление U_i, которое состоит в том, что в начале i-ого года предприятию P₁ выделены средства x_i1, предприятию P₂ - средства x_i2 и т.д. Тогда вектор U_i = (x_i1, x_i2, …, x_in) определяет распределение средств на i-ом этапе. Совокупность выделенных средств на k шагах выразится системой векторов n-мерного векторного пространства

U₁= (x₁₁; x₁₂; …; x_1n),₂= (x₂₁; x₂₂; …; x_2n),

U_k= (x_k1; x_k2; …; x_kn).

Суммарный доход за k лет зависит от совокупности управлений, т.е. является функцией от U_1, U_{2, …,} U_k:

W (U_1, U_{2, …,} U_k).

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

W = (x₁₁; x₁₂; …; x_1n; x₂₁; x₂₂; …; x_2n; x_k1; x_k2; …; x_kn),

т.е. как функцию многих переменных. Теперь решение задачи заключается в нахождении такой совокупности значений аргументов x_ij, при которой функция W достигает максимального значения. Казалось бы, найдя частные производные функции по всем аргументам, приравняв их к нулю и решив систему уравнений = 0, получим значение x_ij, при которых функция W имеет локальный максимум.

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

5. Сетевое планирование и управление

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

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

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

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

Сетевой график - это ориентированный граф без контуров. В сетевом моделировании имеются два основных элемента - работа и событие.

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

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

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

Рис. 1 Рис. 2

3. В сети не должно быть тупиков, т.е. промежуточных событий, из которых не выходит ни одна работа (рис. 1).

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

Рис. 3 Рис. 4

2. В сети не должно быть замкнутых контуров, состоящих из взаимосвязанных работ, создающих замкнутую цепь (рис. 4). Для правильной нумерации событий поступают следующим образом: нумерация событий начинается с исходного события, которому дается номер 1. Из исходного события 1 вычеркивают все исходящие из него работы, на оставшейся сети вновь находят событие, в которое не входит ни одна работа. Этому событию дается номер 2. Затем вычерчивают работы, выходящие из события 2, и вновь находят на оставшейся части сети событие, в которое не входит ни одна работа, ему присваивается номер 3, и так продолжается до завершающего события. Пример нумерации сетевого графика показан на рис. 5.

Рис. 5

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

6. Метод Гомори последовательных отсечений

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

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

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

Эта идея, принадлежащая Д. Данцигу и Р. Гомори, впервые была представлена в форме дополнительного ограничения:

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

К сожалению, для абсолютного большинства задач скорость сходимости процесса таких отсечений мала. Потому Р. Гомори предложена другая форма дополнительного ограничения. Так, если компонента плана, определяемая k-ым уравнением системы ограничений, нецелочисленна, то добавляется ограничение

где f_k - дробная часть компоненты плана (правой части ограничения) и f_kj - дробная часть коэффициента при X_j (целая часть числа - наибольшее целое, не превышающее это число; дробная часть числа равна разности между числом и его целой частью), S* - новая дополнительная переменная.

Например, если ограничение имеет вид

то дополнительное ограничение принимает вид

Можно уменьшить объем преобразований, если руководствоваться следующими правилами:

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

2. для ввода в базис опорного плана расширенной задачи выбирать переменную, для которой достигается минимум из отношений абсолютных значений D_j к значениям f_kj;

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

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

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

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

Литература

планирование балансовый гомори математический

1. Нефедов Ю.В., Базаров М.К. Математические методы в обосновании управленческих решений (Математические модели в управлении): Монография. - Оренбург: Издательство ООИПКРО, 2005.

2. Полунин И.Ф. Курс математического программирования: Учебник. / 3-е изд. ? 1975.

3. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование: Учебник. / 2-е изд. ? 1980.

4. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании: Учебник. / 3-е изд., испр. - М.: Дело, 2002.

5. Гатаулин А.М., Гаврилов Г.В., Сорокина Т.М. Математическое моделирование экономических процессов. / Под ред. Гатаулина А.М. - М.: Агропромиздат, 1990

Размещено на Allbest.ru