Экономико-математичеческие методы и модели

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

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

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

Остальные ячейки остаются пустыми. Кроме того, введем вспомогательный столбец в который внесем значения неизвестных U1 … U4 (4,это m — число складов) и вспомогательную строку в которую внесем значения неизвестных V1 … V5 (5,это n — число потребителей). На рисунке они представлены желтым цветом. Эти n+m неизвестных должны для всех (i, j), соответствующих загруженым клеткам, удовлетворять линейной системе уравнений Ui+Vj=Pij.

Эту систему всегда можно решить следующим способом: На первом шаге полагают V5=0. Если на k-м шаге найдено значение неизвестной, то в системе всегда имеется еще не определенная неизвестная, которая однозначно может быть найдена на (k+1)-м шаге из уравнения Ui+Vj=Pij, так как значение другой неизвестной в этом уравнении уже известно. То какую неизвестную можно найти на (k+1)-м шаге, определяют методом проб. Переменные Ui и Vj называются симплекс-множителями или потенциалами. Рабочая матрица затрат с рассчитанными потенциалами представлена ниже.

b1

b2

B3

b4

b5

a1

10 8 6 u1=

a2

9 6 u2=

a3

8 6 u3=

a4

8 u4=

v1=

v2=

v3=

v4=

— 1

v5=

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

1) Пусть V5 = 0 ;

2) U1 = P1,5 — V5 ;

3) V1 = P1,1 — U1 ;

4) V2 = P1,2 — U1 ;

5) U2 = P2,2 — V2 ;

6) V4 = P2,4 — U2 ;

7) U3 = P3,1 — V1 ;

8) V3 = P3,3 — U3 ;

9) U4 = P4,2 — V2 ;

Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij = Pij — Ui — Vj (зеленый цвет). Каждая такая оценка показывает на сколько изменятся общие транспортные затраты при загрузке данной клетки единицей груза. Таким образом, если среди оценок имеются отрицательные (затраты уменьшаются) то данный план можно улучшить переместив в соответствующую клетку некоторое количество продукции. Если же среди оценок нет отрицательных — план является оптимальным. Рабочая матрица затрат с заполнеными оценками клетками представлена ниже.

b1

b2

b3

b4

b5

a1

10 8 4 3 6 u1=

a2

1 9 1 6 1 u2=

a3

8 6 6 5 6 u3=

a4

2 8 2 7 9 u4=

v1=

v2=

v3=

v4=

— 1

v5=

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

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

3. Нелинейное и динамическое программирование

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

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

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

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

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

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

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

Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных — переменную состояния S и переменную управления X. Переменная S определяет, в каких состояниях может оказаться система на данном k-м шаге. В зависимости от S на этом шаге можно применить некоторые управления, которые характеризуются переменной X. Применение управления X на k-м шаге приносит некоторый результат Wk (S, Xk) и переводит систему в некоторое новое состояние S'(S, Xk). Для каждого возможного состояния на k-м шаге среди всех возможных управлений выбирается оптимальное управление X*k такое, чтобы результат, который достигается за шаги с k-го по n-й, оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана Fk (S) и зависит от номера шага k и состояния системы S.

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

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

В общем виде задача динамического программирования формулируется следующим образом: требуется определить такое управление X*, переводящее систему из начального состояния S0 в конечное состояние Sn, при котором целевая функция F (S0,X*) принимает наибольшее (наименьшее) значение.

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

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

целевая функция является аддитивной и равна сумме целевых функций каждого шага

;

выбор управления Xk на каждом шаге зависит только от состояния системы к этому шагу Sk-1 и не влияет на предшествующие шаги (нет обратной связи);

состояние системы Sk после каждого шага управления зависит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия Xk (отсутствие последействия) и может быть записано в виде уравнения состояния:

;

на каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние системы Sk зависит от конечного числа переменных;

оптимальное управление X* представляет собой вектор, определяемый последовательностью оптимальных пошаговых управлений:

X*=(X*1, X*2, …, X*k, …, X*n),

число которых и определяет количество шагов задачи.

Условная оптимизация. Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем n-м шаге найти оптимальное управление X*n и значение функции Беллмана Fn (S) не сложно, так как

Fn (S)=max{Wn (S, Xn)},

где максимум ищется по всем возможным значениям Xn.

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

Fk (S)=max{Wk (S, Xk)+Fk+1(S'(S, Xk))}. (1)

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый (на первом шаге k=1 состояние системы равно ее начальному состоянию S0), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге X1, применение которого приведет систему в состояние S1(S, x1*), зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага.

Рассмотрим пример решения задачи методом динамического программирования.

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

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

руб. с дискретностью 50 млн.

руб. На одно предприятие можно осуществить только одну инвестицию.

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

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

Инвестиции, млн.

руб. Прирост выпуска продукции, млн.

руб. Пр-е 1 Пр-е 2 Пр-е 3 Пр-е 4 50 10 9 7 8 100 15 16 13 14 150 24 22 20 21 200 33 34 31 35 250 40 39 41 41

Решение.

Запишем уравнение Беллмана для метода обратной прогонки и разобьем решение задачи на 4 этапа.

Этап 4. F5(C5)=0

C4 X4 F4(C4) X4* 0 50 100 150 200 250 0 0 — - - - - 0 0 50 — 10 — - - - 10 50 100 — - 15 — - - 15 100 150 — - - 24 — - 24 150 200 — - - - 33 — 33 200 250 — - - - - 40 40 250

Этап 3.

C3 X3 F3(C3) X* 0 50 100 150 200 250 0 0+0=0 — - - - - 0 0 50 0+10=10 9+0=9 — - - - 10 0 100 0+15=15 9+10=19 16+0=16 — - - 19 50 150 0+24=24 9+15=24 16+10=26 22+0=22 — - 26 100 200 0+33=33 9+24=33 16+15=31 22+10=32 34+0=34 — 34 200 250 0+40=40 9+33=42 16+24=40 22+15=37 34+10=44 39+0=39 44 200

Этап 2.

C2 X3 F2(C2) X* 0 50 100 150 200 250 0 0+0=0 — - - - - 0 0 50 0+10=10 7+0=7 — - - - 10 50 100 0+19=19 7+10=17 13+0=13 — - - 19 50 150 0+26=26 7+19=26 13+10=23 20+0=20 — - 26 0,50 200 0+34=34 7+26=33 13+19=32 20+10=30 31+0=31 — 34 0 250 0+44=44 7+34=41 13+26=39 20+19=39 31+10=41 41+0=41 44 0

Этап 1.

C1 X3 F1(C1) X* 0 50 100 150 200 250 0 0+0=0 — - - - - 0 0 50 0+10=10 8+0=8 — - - - 10 0 100 0+19=19 8+10=18 14+0=14 — - - 19 0 150 0+26=26 8+19=27 14+10=24 21+0=21 — - 27 50 200 0+34=34 8+26=34 14+19=33 21+10=31 35+0=35 — 35 200 250 0+44=44 8+34=42 14+26=40 21+19=40 35+10=45 41+0=41 45 200 Из таблицы этапа 1 находим оптимальное значение целевой функции при распределении между предприятиями всей суммы С1=250: F1(250)=45. При этом первому предприятию должно быть выделено x1*=200 ден.

ед. Тогда остальным трем предприятиям остается распределить С2=С1-x1*=250−200=50 ден.

ед. Из таблицы этапа 2 выделению суммы С2=50 соответствует значение x2*=50, тогда С3=С2- x2*=50−50=0 ден.

ед. Тогда получаем x3*=0, x4*=0.

Таким образом, оптимальный план инвестирования предприятий: X*= (200,50,0,0), который обеспечит максимальный доход, равный F (250)=g1(200)+g2(50)+g3(0)+g4(0)=35+10+0+0=45 млн.

руб.

Заключение

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

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

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

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

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

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

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

Список литературы

Аветисян Р.Д., Аветисян Д. О. Теоретические основы информатики. — М.: РГГУ, 2007 — 168 с.

Линейное программирование: Учебно-метод. пособие к контрольной работе для студ. эконом. факультета /И.В. Большакова, М. В. Кураленко. − Мн.: БНТУ, 2004. − 148 с.

Пенроуз, Р. Новый ум короля / Р. Пенроуз. — М.: УРСС, 2008. — 384 с.

Схрейвер А. Теория линейного и целочисленного программирования: в 2-х томах; перевод с английского. 1991 г. — 360с.

Уэбстер, Ф. Теории информационного общества / Ф. Уэбстер. — М.: Аспект Пресс, 2004. — 400 с.

Экономико-математические методы. Математические методы и модели в экономике. Раздаточный материал/ сост. Аксенова Р.Н.- Владивосток, ДВГАЭУ, 2011.