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

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

Конспект лекций

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

Пятецкий В.Е.,

Литвин И.З.,

Литвяк В.С.

Москва, 2012

Предисловие

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

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

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

В пособии многократно использованы материалы изданий [1-14].

Лекция 1. Введение

Начало применению математических методов в задачах бизнеса и экономики относят обычно к 40-м годам ХХ века.

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

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

Важно подчеркнуть, что решения всех рассматриваемых нами задач абсолютно невозможны без компьютерных пакетов. Современное программное обеспечение базируется, в частности, на электронных таблицах EXCEL и таких его инструментах как "поиск решений" (solver), "анализ данных" и др., находящихся среди пунктов меню СЕРВИС. Подробное описание компьютерной реализации алгоритмов находится, например, в [9].

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

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

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

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

Лекция 2. Балансовые модели

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

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

Модель представляют в таблице следующего вида (ее также называют "затраты - выпуск"):

Потребляющие отрасли	1	2				n	X	Y
Производящие отрасли
1	x11	x12				x1 n	x1	y1
2	x21	x22				x2 n	x2	y2
.
.
.
n	x n1	x n2	.	.	.	x n	x n	y n

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

2. В первой строке эти же отрасли представлены, как потребляющие

3. х i j - указывает количество продукции i-й отрасли, израсходованной на нужды j - й отрасли.

4. Столбец Х - совокупный (валовый) продукт каждой отрасли за год)

5. Столбец У - конечный продукт каждой отрасли за год, т.е. продукция, израсходованная на непроизводственные цели - личное потребление граждан, нужды государства, накопление и т.п.

Важное значение имеют коэффициенты:

a i j = xi j / xj - доля продукции i- й отрасли в единице продукции j-й отрасли (коэффициент прямых материальных затрат)

Так, а13 = 0,8 означает, что на единицу продукции 3-й отрасли расходуется 80% продукции 1-й отрасли.

В чем же баланс?

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

x1 = a11 x1 + a12 x2 +… a1n xn + y1

x2 = a21 x1 + a22 x2 +… a2n xn + y2 (2.1)

…………………………………..

xn = an1 x1 + an2 x2 +… ann xn + yn

В матричной форме система уравнений (2.1) записывается так:

Х = AХ + У,

где ,

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

Замечание:

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

Из матричного уравнения (2.1) сразу следует:

Х = (E - A)-1 У (2.2)

Формула (2.2) и отвечает на основной вопрос межотраслевого баланса - каким должен быть совокупный продукт каждой отрасли (Х=?), чтобы экономическая система в целом произвела заданный государством конечный продукт У.



Правую часть формулы (2.2) удобно вычислять в EXCEL:

1. Выделить диапазон ячеек для размещения обратной матрицы.

2. На верхней панели нажать f x.

3. Выбрать функцию МОБР в категории Математические.

4. Указать диапазон ячеек, в которых размещена матрица

Е-А.

5. Нажать клавиши SHIFT + СTRL + ENTER

6. Записать результат.

Чтобы умножить полученную обратную матрицу на вектор у нужно

1. Выделить диапазон ячеек для размещения результатов умножения.

2. На верхней панели нажать f x.

3. Выбрать функцию МУМНОЖ в категории Математические.

4. Указать диапазоны ячеек, в которых размещены матрица (Е-А)-1 и вектор У.

6. Нажать клавиши SHIFT + СTRL + ENTER

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

Пример: задана матрица "затраты - выпуск"

Потребители	металлургия	машиностроение	нефтянка	Х	У
Производители
металлургия	6	36	20	102	40
машиностроение	12	12	20	94	50
нефтянка	22	12	12	56	10

Допустим, что конечный продукт У не устраивает плановые органы государства. Ставится задача, найти новый совокупный продукт (Х=?), при котором конечный продукт достигнет нового уровня

Y=

1. Составляем матрицу прямых материальных затрат

А=

2. Е - А =

3. (Е - А)-1 =

4.

Вывод:

Чтобы обеспечить требуемый конечный продукт, металлургия должна произвести совокупный продукт в объеме 131, машиностроение - 181, нефтянка - 80.

Запишем, наконец, новую, пересчитанную таблицу "затраты-выпуск".

Потребители	металлургия	машиностроение	нефтянка	Х	У
Производители
металлургия	7,86	44,84	28,8	131	50
машиностроение	15,72	14,16	28,8	118	60
нефтянка	28,82	14,16	27,51	80	20

Пояснение: 7,86=0,06*131

44,84=0,38*118

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

Лекция 3. Примеры моделей линейного программирования

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

Становление этого класса задач относится к 50-м годам ХХ века и связано с решением академиком Канторовичем Л.В. ряда практических задач в экономике (наилучшая загрузка оборудования, раскрой материалов и т.д.). Рассмотрим постановки некоторых задач.

1. Задача оптимального использования ресурсов.

Фирма планирует начать выпуск шкафов и столов для компьютеров.

Исходные данные

Ресурсы	Запасы	Расх. коэфф.
		шкафы столы
Дсп, м2	350	3,5 1
Стекло, м2	240	1 2
Труд, чел-часы	150	1 1
Прибыль, у.е.		200 100

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

Построение матем. модели:

Пусть х1 - количество шкафов, х2- количество столов

По условию,

3,5 х1 + х2 ? 350

х1 + 2х2 ? 240

х1 + х2 ? 150 > ограничения модели

х1, х2 ? 0

F= 200x1 + 100x2 > max (целевая функция)

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

2. Задача о раскрое

Имеются прутки длиной 100 см. Требуется нарезать (раскроить) из них заготовки длиной 25 см. (200 штук), 30 см. (250), 35 см. (150).

Возможные варианты раскроя приведены в таблице:

Варианты раскроя	1	2	3	4	5	6	7	8	9	План
Вид заготовки
25	4	0	0	1	1	2	2	0	1	200
30	0	3	1	0	1	1	0	2	2	250
35	0	0	2	2	1	0	1	1	0	150
Обрезь	0	10	0	5	10	20	15	5	15

Требуется определить, сколько прутков нужно разрезать по каждому варианту (х1,х2,…х9), чтобы выполнить план по заготовкам и при этом минимизировать суммарную обрезь.

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

4х1 + х4 + х5+ 2х6 + 2х7 + х9 = 200

3х2 + х3 + х5+ х6 + 2х8 + 2х9 = 250 > ограничения

2х3 + 2х4 + х5+ х6 + х7 + х8 = 150

хi ? 0

F= 10х2 + 5х4 +10 х5+ 20х6 + 15х7 +5 х8+15x9 >min

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

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

Исходные данные приведены в таблице:

Потребители	1	2	3	Запасы, тонн
Поставщики
1	7	9	8	300
2	3	4	6	500
Спрос, тонн	500	200	100

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

Требуется составить оптимальный план перевозок топлива от поставщиков к потребителям, чтобы

а) вывезти все топливо

б) удовлетворить весь спрос

в) минимизировать суммарные затраты

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

Положим хi j - количество груза, перевозимого от i-го исходного пункта к j-му пункту назначения.

х11 + х12 + х13 =300

х21 + х22 + х23 =500

х11 + х21 =500> ограничения

х12 + х22 =200

х13 + х23 =100

хij ? 0

F = 7х11 + 9х12 + 8х13 + 3х21 + 4х22 + 6х23 > min

Лекция 4. Общая постановка задачи линейного программирования

1. Задача линейного программирования в канонической форме

а11х1 + а12х2+……а1nхn = в1

а21х1 + а22х2+……а2nхn = в2 (4.1)

……………………………

аm1х1 + аm2х2+…аmnхn = вm

xi ? 0, i = 1,n

F = c1х1 + c2х2+……cnхn > max

Матричная запись:

Ах = в

х ? 0

F = c x > max

Здесь А - матрица коэффициентов, х - столбец переменных, в- столбец правых частей, с - строка коэффициентов целевой функции.

Какие возможны ситуации?

1. Система (4.1) не имеет решений. Интерес такая ситуация не представляет.

2. Система (4.1) имеет единственное решение. Ясно, что оно и будет оптимальным решением.

3. Система (4.1) имеет бесконечное множество решений, но целевая функция не ограничена на множестве допустимых решений. Экономически такой случай не интересен.

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

Этот случай рассмотрим более подробно. Итак, пусть имеет место последняя ситуация.

Основной принцип линейного программирования

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

2. Вершины многогранника называются угловыми точками.

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

2. Задача линейного программирования в стандартной форме

а11х1 + а12х2+……а1nхn ? в1

а21х1 + а22х2+……а2nхn ? в2 (4.2)

……………………………

аm1х1 + аm2х2+…аmnхn ? вm

xi ? 0, i = 1,n

F = c1х1 + c2х2+……cnхn > max

Геометрический смысл тот же, что и в п.1 (для задачи в канонической форме).

Пример:

Участок цеха выпускает изделия двух видов.

Исходные данные указаны в таблице стандартного вида:

Ресурсы	Запасы	Расх. коэфф.
		1 2
Медь	45	5 3
Алюминий	16	1 2
Прибыль		2 3

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

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

Пусть х1, х2 количество изделий каждого вида, соответственно.

5х1 + 3х2 ? 45 (4.3)

х1 + 2х2 ? 16 (4.4)

х1, х2 ? 0

F = 2x1 + 3x2 > max

Далее эту задачу с двумя переменными можно решать или графоаналитически или в EXCEL.

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

Систему ограничений в стандартной форме перепишем так:



Рис. 4.1

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

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

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

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

Чтобы найти ее координаты заметим, что она лежит на прямых (4.5) и (4.6):

5х1 + 3х2 = 45

х1 + 2х2 =16

хопт = (6,5) Fmax = 27

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

Следует прорешать ту же задачу в EXCEL.

Пример:

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

- общее число акций не превышает 6000

- число акций каждого вида не превышает 5000.

Ожидаемая прибыль 1,2 и 1 у.е. на каждую акцию, соответственно.

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

х1, х2 - количество акций каждого вида.

х1 + х2 ? 6000 (4.7)

х1 ? 5000 (4.8)

х2 ? 5000 (4.9)

6х1 + 4х2 ? 30000 (4.10)

х1, х2 ? 0

F = 1,2х1 + х2 >max

Воспользуемся графоаналитическим методом:



Рис. 4.2

Оптимальная точка лежит на пересечении прямых (4.7) и (4.10).

х1 + х2 = 6000

6х1 + 4х2 = 30000

хопт = (3000, 3000), Fmax = 6600

Лекция 5. Симплекс-метод

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

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

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

Ясно, что для реализации симплекс- метода необходимо математически:

- выбрать начальное опорное решение (угловую точку)

- проверить его на оптимальность

- при необходимости перейти к лучшему

- уметь распознавать ситуации отсутствия оптимального решения.

Ограничимся, пока этапами "ручного" cимплекс-метода, когда необходимые преобразования осуществляются в таблицах стандартного вида.

Пример:

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

Исходные данные приведены в таблице стандартного вида.

Ресурсы	Запасы	Расх. коэфф.
		1 2 3
труд	120	6 5 4
сырье	96	3 2 4
оборудование	180	5 3 3
Прибыль, у.е.		9 10 16

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

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

х1, х2, х3 - количество изделий каждого вида.

6х1 + 5х2 + 4х3 ? 120

3х1 + 2х2 + 4х3 ? 96

5х1 + 3х2 + 3х3 ? 180

х1, х2, х3 ? 0

F= 9х1 + 10х2 + 16х3 > max

1. Приводим задачу к каноническому виду:

6х1 + 5х2 + 4х3 + х4 = 120

3х1 + 2х2 + 4х3 + х5 = 96

5х1 + 3х2 + 3х3 + х6 = 180

х1,.. х6 ? 0

F= 9х1 + 10х2 + 16х3 > max

2. Составляем исходную симплекс-таблицу (заметим, что в разных учебных пособиях форма симплекс-таблицы различна!):

Базисн. перем.	х1	х2	х3	х4	х5	х6	вi	Оцен. отн.
х4	6	5	4	1	0	0	120	30
х5	3	2	4	0	1	0	96	24
х6	5	3	3	0	0	1	180	60
Оцен. строка	-9	-10	-16	0	0	0	0

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

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

По составленной таблице прочитаем исходное опорное решение (исходную угловую точку):

х1 = (0,0,0,120,96,180).

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

3. Проверяем опорное решение на оптимальность: если все элементы оценочной строки неотрицательны, то опорное решение оптимально. В нашем случае это не так.

4. В оценочной строке находим наименьший отрицательный элемент. Соответствующий столбец назовем разрешающим.

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

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

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

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

Правило прямоугольника поясним схемой:

Базисн. переем.	х!	х"	х3	х;	х5	х:	вi	Оцен. отн.
х4	3	3	0	1	-1	0	24	8
х3	3/4	1/2	1	0	1/4	0	24	48
х6	11/4	3/2	0	0	-3/4	1	108	72
Оцен. строка	3	-2	0	0	4	0	384

8. Новое опорное решение х2 = (0, 0, 24, 24, 0, 108).

Оно вновь не оптимально.

Перейдя к п. 4. получим уже последнюю таблицу:

Базисн. перем.	х1	х2	х3	х4	х5	х6	вi	Оцен. отн.
х2	1	1	0	1/3	-1/3	0	8
х3	1/4	0	1	-1/6	5/12	0	20
х6	5/4	0	0	-1/2	-1/4	1	96
Оцен. строка	5	0	0	2/3	10/3	0	400

Новое опорное решение х3 = (0, 8, 20, 0, 0, 96), Fmax = 400

Итак, х3 оптимальное решение. Следуя ему, нужно выпускать 8 единиц 2-го изделия и 20- третьего. Выпуск 1-го изделия экономически не выгоден. Ожидаемая максимальная прибыль 400 у.е.

Заметим, также, что т.к. х4 = х5 = 0, а х6 = 96, то, следуя оптимальному решению, первый и второй ресурсы будут израсходованы полностью (т.е. они дефицитны), а третий ресурс будет недоиспользован в количестве 96. (не дефицитен).

Отметим также, что в оценочной строке последней таблицы х1 = 5. Экономический смысл: если, все - таки, включить в оптимальный план первое изделие, то прибыль уменьшится на 5 у.е.

Особенности

1. Если в оценочной строке последней симплекс- таблицы все коэффициенты при свободных переменных больше 0, то оптимальное решение единственно.

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

Лекция 6. Двойственные задачи (Dual problem)

С каждой задачей линейного программирования тесно связана другая задача линейного программирования - двойственная задача (их так и называют - пара двойственных задач):

а11х1 + а12х2+……а1nхn ? в1 а11у1 + а21у2+……аm1ym ?с1

а21х1 + а22х2+……а2nхn ? в2 а12y1 + а22y2+……аm2ym ? c2

…………………………… ……………………………

аm1х1 + аm2х2+……аmnхn ? вm а1ny1 + а2ny2+……аmnyn ? cn

xi ? 0, i = 1,n yi ? 0, i = 1,m

F = c1х1 + c2х2+……cnхn > max G = b1y1 + b2y2+……bm> min

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

Пример:

исходная задача: двойственная задача:

-2х1 + х2 ? 2 -2у1 + у2 + у3 ? 1

х1 - 2х2 ? 2 у1 - 2у2 + у3 ? -1

х1 + х2 ? 5

х1, х2 ? 0 у1,у2,у3 ? 0

F= x1 - x2 > max G = 2y1 +2y2 +5y3 > min

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

Теоремы двойственности:

1. Если одна из двойственных задач имеет оптимальное решение, то симметричная ей двойственная задача также имеет оптимальное решение, причем сами оптимальные значения совпадают: Fmax = Gmin.

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

3. Если в оптимальном решении одной из задач значение переменной больше нуля, то соответствующее ограничение двойственной задачи обращается в равенство. Если при оптимальном решении одно из ограничений обращается в строгое неравенство, то соответствующая переменная двойственной задачи равна 0.

4.

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

5. Если одна из двойственных задач решена табличным симплекс методом, то оптимальное решение симметричной двойственной задачи легко находится по последней симплекс- таблице - достаточно найти абсолютные значения балансовых переменных. Так, в лекции 4 оптимальное решение двойственной задачи (2/3, 10/3, 0). Впрочем, ниже мы получим тот же результат из других соображений.

Экономическая интерпретация двойственной задачи.

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

Вновь вернемся к модели из лекции 4 (ресурсы: труд, сырье, оборудование).

6х1 + 5х2 + 4х3 ? 120 6у1 +3у2 + 5у3 ? 9

3х1 + 2х2 + 4х3 ? 96 5у1 +2у2 + 3у3 ? 10

5х1 + 3х2 + 3х3 ? 180 4у1 +4у2 + 3у3 ? 16

х1, х2, х3 ? 0 у1, у2, у3 ? 0

F= 9х1 + 10х2 + 16х3 > max G = 9y1 + 10х2 + 16y > min

Напомним, что х опт = (0, 8, 20), Fmax = 400

1. Из любого ограничения двойственной задачи следует, что размерность уi совпадает с размерностью правой части (рубли/ ед. ресурса). Поэтому уi имеют смысл цены единицы ресурса. Их так и называют - теневые цены ресурсов (shadow prices). Речь, конечно, идет не о реальных ценах ресурсов, по которым осуществляется их закупка. Это лишь некоторая экономическая мера, характеризующая ценность ресурса относительно полученного оптимального решения.

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

Выше мы отметили, что у1 = 2/3, у2=10/3. Таким образом, дополнительные средства выгоднее вкладывать в закупку сырья. Так, у2=10/3 указывает на величину ожидаемого прироста максимума прибыли от дополнительного вовлечения в производство 1 ед. сырья.

Это даст наибольший прирост максимума прибыли!

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

2. Отметим, что Fmax = 400, Gmin = 120* (2/3) + 96* (10/3) +180 *(0) =400.

Таким образом, пункт 1. теоремы двойственности выполнен!

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

цены должны быть не слишком низкими (в ограничениях знак ?) и покупателю должна быть выгодна покупка (G > min).

3. Так как х2 > 0 и х3 > 0, то в силу п. 3.

5у1 +2у2 + 3у3 = 10

4у1 +4у2 + 3у3 = 16

А так как третье ограничение исходной задачи обращается при оптимальном решении в строгое неравенство, то у3 = 0.

Итак, у1 =2/3, у2 =10/3.> уопт = (2/3, 10/3, 0)

4. Подчеркнем, что у3 = 0 означает недефицитность третьего ресурса,

у1 =2/3, у2 =10/3 - дефицитность первых двух ресурсов.

5. Увеличение запаса сырья на одну ед. приведет к увеличению прибыли на 10/3 у.е.

Пример:

Для производства четырех видов изделий А1, А2, А3 и А4 завод должен использовать три вида сырья I, II и III. Запасы сырья на планируемый период составляют, соответственно, 1000, 600 и 150 единиц.

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

Виды сырья	Технологические коэффициенты	Запасы сырья
	А1	А2	А3	А4
I	5	1	0	2	1000
II	4	2	2	1	600
III	1	0	2	1	150
Прибыль от реализации	6	2	2,5	4

Требуется, зная решение данной задачи, решить задачу, двойственную ей.

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

5х1 + х2 + 2х4 ? 1000

4х1 + 2х2 + 2х3 + х4 ? 600

х1 + 2х3 + х4 ? 150

хi ? 0

F = 6х1 +2х2 +2,5x3 + 4х4 > max

2. Решение исходной оптимизационной задачи

Воспользуемся файлом "новый" (этот файл входит в программное обеспечение кафедры БИСУП МИСиС).

Ответ (0, 225, 0,150)

3. Составление двойственной задачи:

5у1 + 4у2 + у3 ? 6

у1 + 2у2 ? 2

2у2 + 2у3 ? 2,5

2у1 + у2 + у3 ? 4

G = 1000у1 + 600у2 + 150у3 > min

4. Решение двойственной задачи:

Т.к. в оптимальном решении исходной задачи х2 и х4 не равны 0, то второе и четвертое ограничения двойственной задачи обращаются в равенства. Более того, т.к. первое ограничение исходной задачи обращается в строгое неравенство (проверить), то у1 =0.

Итак,

2у2 = 2

у2 + у3 = 4

Имеем у2 = 1, у3= 3, у1 = 0

5. Контроль:

Gmin = 1000*0 + 600*1 + 150*3 = 1050 =Fmax> Верно!

6. Экономический анализ:

1. Следует выпускать 225 изделий 2 типа и 150- 4 типа.

Изделия 1 и 3 типа экономически не выгодны!

Ожидаемая прибыль 1050.

2. Т.к. у1 = 0, то сырье 1 (первый ресурс) не дефицитно.

Однако сырье 2 и 3 дефицитны!

3. Т.к. у3 > у2, то дополнительные средства выгоднее вложить в закупку сырья 3. При этом, увеличение запаса этого сырья на одну ед. приведет к увеличению максимальной прибыли на 3 у.е.

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

Лекция 7. Транспортная задача (Transportation Problem)

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

Традиционная постановка транспортной задачи такова:



Рис. 7.1

Имеются m поставщиков и n потребителей. У поставщиков сосредоточен однородный груз (запас) в количестве a1, a2,…..am.

Спрос потребителей на груз: в1, в2,….вn.

Известны стоимости (тарифы) сij на перевозку единицы груза от i-го поставщика к j- му потребителю.

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

1. вывести весь груз поставщиков (запасы)

2. удовлетворить весь спрос потребителей

3. минимизировать суммарные затраты.

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

Пусть хij - количество груза, перевозимого от i-го исх. пункта к j-му пункту потребления.

х11 + х12+ ….+х1n= а1

х21 + х22+ ….+х2n= а2 >все грузы должны быть вывезены

……………………..

хm1 + хm2+ ….+хmn= аm

х11 + х21+ ….+хm1= b1

х12 + х22+ ….+хm2= b2 > весь спрос удовлетворен

…………………….

х1n + х2n+ ….+хmn= bn

F =

Замечание:

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

Метод потенциалов решения транспортной задачи.

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

Разберем этот метод на конкретном примере:

На трех железнодорожных станциях Череповца сосредоточено топливо для пяти цехов завода Северсталь. Необходимо составить оптимальный план перевозок топлива.

Исходные данные заданы в транспортной таблице стандартного вида:

Транспортная задача закрытая (почему?).

1. Нахождение начального опорного плана (угловой точки).

Используется метод минимальной стоимости. Его суть:

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

Результат записываем в левый нижний угол клетки.

(1,3),(2,4),(2,2),(1,5)

б) правило: "там, где 0 вычеркиваем"

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

в) контроль: общее число занятых клеток равно

m + n - 1. У нас 3+5-1=7.

г) F = 20*7 + 80*2+ 100*4 + 30*6 + 70*4 + 150*2 + 50*5= 1710

Начальный опорный план - в левом нижнем углу клеток.

2. Проверка опорного плана на оптимальность.

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

Правило 1: для всех занятых клеток должно быть:

u i + v j = c i j (7.1)

(сумма потенциалов равна стоимости). Это правило - для заполнения столбцов U, V.

Правило 2: для всех свободных клеток должно быть:

u i + v j ? c i j

Это правило проверки оптимальности. (7.2)

Условие оптимальности нарушено в клетке (1, 2)!

Итак, полученный опорный план не оптимален!

Экономический смысл потенциалов:

Потенциалы u и v можно рассматривать как платежи поставщиков и потребителей некоторому третьему лицу - назовем его " перевозчиком".

Формула (7.2) означает, что при оптимальном плане перевозок стороны не хотят переплачивать сверх установленного тарифа.

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

3. Переход к новому опорному плану, лучшему, чем предыдущему.

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

а) помечаем эту клетку знаком + и строим цикл, начинающийся и заканчивающийся в этой же клетке.

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

Такой цикл всегда существует и только один!

б) размечаем вершины цикла знаками - + - … считая от исходной клетки.

в) находим, по всем клеткам, помеченным знаком - наименьшую перевозку. Обозначим ее ?. У нас ? = 20.

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

Получающийся "лишний нуль" стираем.

Результаты записываем в новую таблицу.

Не забываем проверять условие: число занятых клеток = m+n -1.

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

Вновь находим потенциалы и проверяем условие (7.2).

Условие оптимальности выполнено.

Получен оптимальный план перевозок!

Fmin = 20*4 + 80*2 + 100*4 + 50*6 + 50*4 + 150*2 + 50*5 = 1690

х12 = 20

х13 = 80

х15 = 100

х21 = 50

х22 = 50

х24 = 150

х31= 50

Графическая иллюстрация.



Рис. 7.2

Особенности решения открытой транспортной задачи.

Напомним, что в открытой транспортной задаче сумма запасов не равна сумме спроса:

1. Пусть сумма запасов превышает суммарный спрос.

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

2. Пусть сумма запасов меньше суммарного спроса.

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

Пример:

Решить транспортную задачу:

Задача открытая, т.к. суммарные запасы меньше суммарного спроса.

Следуя рекомендации, введем фиктивного поставщика (т.е. дополнительную строку в таблице).

1. Нахождение начального опорного плана (угловой точки).

Отметим, что фиктивные клетки следует рассматривать в последнюю очередь.

Проверяем условие m + n - 1.

2. Проверка опорного плана на оптимальность.

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

Условие оптимальности не выполнено! Условие оптимальности нарушено в клетке (3, 1)!

Итак, полученный опорный план не оптимален!

Получен оптимальный план перевозок!

Fmax = 35*1 + 5*2 + 20*3 + 40*3 + 25*4 + 65*2 + 0 =455

х12 = 35

х13 = 5

х21 = 20

х23 = 40

х34 = 65

х43 = 10

Заметим, что третий потребитель ничего не получит!

Выполним вычисления в EXCEL.

Лекция 8. Задача о назначениях (assignment problem)

Пусть имеются n кандидатов и n работ.

Известны затраты с i j , связанные с выполнением i-м кандидатом j - й работы.

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

Требуется так распределить (назначить) кандидатов на работы, чтобы суммарные затраты были минимальны.

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

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

хi j =1, если i -й кандидат назначен на j- ю работу

хi j =0, в противном случае.

По условию:

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

Его суть:

1. Образовать таблицу затрат С.

2. В каждом столбце найти минимальный элемент и вычесть его из всех элементов этого столбца. Результаты записать в новую таблицу.

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

4. Проставить у нулей новой матрицы звездочки (*) так, чтобы в каждой строке и каждом столбце было по одному 0*. Если это возможно, то каждому 0* сопоставляем xij =1, остальным элементам 0 - оптимальное решение получено.

5. Если указанным способом нельзя проставить 0*, то провести в таблице минимальное число прямых через некоторые 0*, так, чтобы все нули оказались вычеркнутыми.

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

Примеры:

1. Менеджеру фирмы нужно организовать с минимальными затратами производство изделий 4-х типов на 4-х филиалах.

Задана таблица затрат:

1	4	6	3
9	7	10	9
4	5	11	7
8	7	8	5

Следуя алгоритму, получим:

0	0	0	0
8	3	4	6
3	1	5	4
7	3	2	2
0	0	0	0
5	0	1	3
2	0	4	3
5	1	0	0

Не получается расставить 0* так, чтобы в каждой строке и каждом столбце было по одному 0*!

Fmin = 1 +5 +10 +5 = 21

Решить задачу в EXCEL!

Графическая иллюстрация:

Рис. 8.1

2. Мастер цеха должен оптимальным образом расставить четырех рабочих по четырем операциям.

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

15	20	18	24
12	17	16	15
14	15	19	15
11	14	12	3

Следуем алгоритму:

3. Некоторая компания имеет 4 сбытовых базы и 4 заказа, которые необходимо оптимальным образом доставить различным потребителям.

В таблице указана информация о расстояниях между каждой базой и потребителем:

База	расстояние, миль
	1 2 3 4
A	68	72	75	83
B	56	60	58	63
C	38	40	35	45
D	47	42	40	45

Решить в EXCEL.

4. В распоряжении некоторой компании имеются 5 торговых точек и 5 продавцов.

Эффективность работы продавцов в различных точках не одинакова:

База	объем продаж, ф. ст./тыс. шт.
	1 2 3 4 5
A	68	72	75	83	69
B	56	60	58	63	59
C	38	40	40	45	27
D	47	42	47	45	36
E	62	70	68	67	70

Коммерческий директор должен распределить продавцов по торговым точкам, так, чтобы достичь максимального объема продаж.

Решить в EXCEL.

Лекция 9. Задачи нелинейного программирования

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

1. Графический метод решения (число переменных равно 2).

Пример.

х12 + х22 ? 16

х1, х2 ? 0 > математическая модель.

F= 2 x1 + 3 x2 > max

1. Изображаем область допустимых решений:



Рис. 9.1

2. Изображаем линию уровня F = 0. Напомним, что линия уровня это линия на плоскости, состоящая из всех точек этой плоскости, в которых функция F имеет постоянное значение.

3. Из начала координат проводим вектор-градиент. Напомним, что он ортогонален линии уровня и указывает направление возрастания целевой функции (нам это и нужно!).

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

Напомним (матанализ), что точка касания находится приравниванием производных:

2х1 + 3х2 = с > х2 = - (2/3)х1 + с > х2' = - 2/3

х12 + х22 = 16 > 2х1 + 2х2 х2' =0 > х2' = - х1 / х2

х2 = (3/2) х1> х12 + (9/4)х12 = 16 > х1 = 8/ v 13, х2 = 12/ v 13

Пример:

х1 + 2х2 ? 12

х1 + х2 ? 9

х1, х2 ? 0 > математическая модель.

F= (x1-2)2 + (x2-3)2 > max

Решить самостоятельно.

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

2. Классический метод поиска экстремума (матанализ).

Пример:

Фирма производит два вида товаров и продает их по ценам 1000 и 800, соответственно. Известна функция издержек:

С= 2х12 + 2х1 х2 + х22,

где х1, х2 - объемы выпуска товаров каждого вида.

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

Составим целевую функцию (прибыль):

F = 1000 x1 + 800 x2 - 2x12 - 2х1 х2 - х22 > max

Находим стационарные точки, т.е. составляем и решаем систему:

Пример:

Металлургический завод СЕВЕРСТАЛЬ реализует часть проката на внутреннем рынке, а другую часть поставляет на экспорт. Пусть х1, х2 - количество реализуемой продукции на внутреннем рынке и на экспорт, соответственно.

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

р1 = 500 - х1, р2 = 360 - 1,5 х2.

Функция издержек

С= 50000 + 20(х1 + х2).

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

Образуем функцию прибыли:

F = (500 - х1) х1 + (360 - 1,5х2) х2 - 50000 - 20(х1 + х2) > max

Находим стационарные точки, т.е. составляем и решаем систему:



Лекция 10. Игры двух лиц с нулевой суммой (theory of games)

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

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

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

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

Наиболее изучены игры двух лиц с нулевой суммой. Это означает:

1. Наличие двух игроков А и В, с противоположными целями. Поэтому игру называют антагонистической.

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

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

4. Все возможные выигрыши аij игрока А перечисляются в платежной матрице:

Почему нет матрицы игрока В?

Номера строк матрицы отожд...