Двухэтапная транспортная задача

Раздел 1. СТРУКТУРА КУРСА

Структура (распределение часов) курса в соответствии с учебным планом

Цели и задачи курса «Математические методы исследования и моделирования экономических систем», его место в учебном процессе

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

Ø освоение основных типов экономико-математических моделей и подходов к моделированию;

Ø освоение возможностей моделирования и модельного анализа;

Ø построение модельной математической базы макро- и микроэкономического анализа, анализа проблем профессиональной предметной области;

Ø формирование навыков построения моделей, проведения экономико-математических расчетов и анализа.

Курс «Математические методы исследования и моделирования экономических систем» рассчитан на 12 часов аудиторных занятий и определенный объем индивидуальной самостоятельной внеаудиторной работы.

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

Раздел 2. СОДЕРЖАНИЕ КУРСА

Темы и их содержание

Тема 1. Теоретико-методологические основы математических методов исследования и моделирования экономических систем

Задачи экономико-математического моделирования. Классификация экономико-математических методов.

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

Основные этапы процесса моделирования. Основные типы связей, используемые при экономико-математическом моделировании. Переменные и параметры моделей. Типы переменных и параметров моделей.

Тема 2. Базовые экономико-математические модели

Классификация моделей финансово-кредитной сферы. Базовые экономико-математические модели и методы исследования финансово-кредитной сферы. Основные элементы моделей. Информационно-аналитические методы анализа модели.

Типы решений в системе моделирования. Экономическая интерпретация полученных результатов. Проверка адекватности модели. Основные свойства модели и возможности ее модификации.

Уортонская эконометрическая прогнозная модель. Брукинг-ская модель. Квартальная эконометрическая модель. Эконометрическая модель рынка ссудного капитала.

Тема 3. Модели и процедуры принятия, поддержки и анализа управленческих решений

Понятие управленческого (хозяйственного) решения. Сложные управленческие решения. Проблемы моделирования сложных хозяйственных решений. Специфика разработки методов и систем поддержки приятия и реализации решений в финансово-кредитной сфере. Условия принятия решений.

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

Модели приятия решений в условиях риска и неопределенности. Модели принятия решений в условиях действия несложных критериев.

Тема 4. Моделирование процессов функционирования и развития хозяйственных систем

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

Содержание самостоятельной работы

В ходе самостоятельной работы по курсу «Математические методы исследования и моделирования экономических систем» студенты разбирают и решают следующие типовые экономико-математические задачи:

Ø двухэтапную транспортную задачу;

Ø транспортную задачу в сетевой постановке;

Ø динамическую задачу о распределении ресурса.

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

Раздел 3. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ МОДЕЛЕЙ И ПРОЦЕДУР ПРИНЯТИЯ, ПОДДЕРЖКИ И АНАЛИЗА УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ

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

1. Математическая статистика:

Ø дисперсионный анализ;

Ø корреляционный анализ;

Ø факторный анализ;

Ø теория индексов и др.

2. Математическая экономия и эконометрия:

Ø теория экономического роста (модели макроэкономической динамики);

Ø теория производственных функций;

Ø межотраслевые балансы;

Ø национальные счета;.

Ø анализ спроса и потребления;

Ø региональный и пространственный анализ;

Ø глобальное моделирование и др.

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

Ø оптимальное (математическое) программирование:

~ линейное программирование;

~ нелинейное программирование;

~ дискретное программирование;

~ блочное программирование;

~ стохастическое программирование;

~ динамическое программирование;

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

Ø программно-целевые методы планирования и управления;

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

Ø теория массового обслуживания;

Ø теория игр;

Ø теория расписаний и др.

4. Экономическая кибернетика:

Ø системный анализ экономики;

Ø теория экономической информации, включая экономическую семиотику;

Ø теория автоматизированных систем управления.

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

Ø методы машинной имитации;

Ø деловые игры;

Ø методы реального экономического эксперимента.

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

Двухэтапная транспортная задача

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

- затраты на производство единицы продукции в i-ом пункте производства и ее транспортировку в k-ый промежуточный пункт;

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

Требуется определить реальные объемы переработки продукции в промежуточных пунктах (при условии ) и определить план перевозок из пунктов производства в пункты потребления через пункты переработки (из i-ых в k-ые, а из k-ых в
j-ые) так, чтобы суммарные затраты на производство, переработку и транспортировку были минимальными.

Экономико-математическая модель данной ситуации имеет вид:

      (1),

при ограничениях:

;                 ;

; ; ; ;  где

 - объемы перевозки из i-го пункта производства в k-ый промежуточный пункт;

 - объемы перевозки из k-го промежуточного пункта в
j-ый пункт потребления.

Необходимым и достаточным условием разрешимости данной задачи является:

                         (2)

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

Решение двухэтапной транспортной задачи осуществляется методом потенциалов и ведется в специальной таблице, содержащей 4 блока. Общее число строк в таблице - (т + s), a столбцов - (s + n).

Таблица 1

I блок соответствует перевозкам из пунктов производства в пункты переработки. Содержит m строк и s столбцов.

II блок соответствует перевозкам из пунктов производства в пункты потребления, что по условиям задачи запрещено. Для того, чтобы в этом блоке не появлялись перевозки, полагаем . Содержит m строк и n столбцов.

III блок отражает двойственный характер пунктов переработки: по отношению к пунктам производства они являются потребителями, а по отношению к пунктам потребления – постав-

                                             0, если k=k

щиками. Поэтому в этом блоке c_kk =                              ,

                                             +∞, если k≠ k

а остальные стоимости, как и во II блоке, равные +∞. Блок содержит s строк и s столбцов.

IV блок соответствует перевозкам из промежуточных пунктов в пункты потребления. Содержит s строк и n столбцов.

Начальный опорный план данной задачи строится методом наименьшей стоимости, начиная с I блока, затем переходят к III блоку, а после него - к IV блоку. Опорный план должен содержать ровно (n + m + 2s -1) положительных перевозок и не иметь замкнутых маршрутов.

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

 , для ,              (3)

где                                                               

 - потенциал пунктов производства,  ;

 - потенциал пунктов потребления, .

Найденные потенциалы позволяют проверить построенный опорный план на оптимальность:

 для любых ,               (4)

в этом случае найденные  являются составляющими оптимального плана перевозок X*.

В случае невыполнения условия (4) производится расчет невязок :

,

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

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

Пример.

Имеется 3 пункта с объемами производства продукции, задаваемыми вектором ; 3 промежуточных пункта с мощностями по переработке ; 4 пункта потребления с потребностями в продукции . Затраты на производство и транспортировку задаются матрицами  и :

;            .

Проверяем данную задачу на разрешимость, то есть, выполняется ли условие (2):

,

следовательно, возникает необходимость введения фиктивного пункта потребления с объемом потребления . Стоимость перевозки продукции в этот пункт :

следовательно, возникает проблема создания резервов мощностей по переработке.

В основной таблице, таким образом, 6 строк
(т +s = 3+3=6) и 8 столбцов (s + n = 3+5=8), с учетом фиктивного пункта производства). Данные в нее заносятся так, как указано в таблице 2:

Таблица 2

	14	12	13	26	23		23	27	13
10	6	7	3 11	м	м		м	м	м	11
9	5 10	5	4 9	м	м		м	м	м	19
6	8 2	6 16	9	м	м		м	м	м	18
14	0 7	м	м	12 4	8	8	11	13 8	0	19
					1
16	м	0	м	10 5	7 11		12	15	0	16
13	м	м	0	13		9	10 10	14 6	0 4	20
					1
	19	16	20	9	11		10	14	4

Здесь М = +∞.

Начальный опорный план строится, как уже говорилось, методом наименьшего элемента, при этом стоимости, равные 0 (в III и IV блоках) рассматриваются в последнюю очередь. Таким образом, наименьшая стоимости - с₁₃ = 3 в I блоке, и именно с этой клетки и начинается построение опорного плана. Величина перевозки х₁₃ определяется как наименьшая из двух величин – a₁ и q₃, т.е. х₁₃ = min {11;20}=11. После определения х₁₃ очередная перевозка вводится в клетку с наименьшей стоимостью из оставшихся, а именно в этом же столбце. Это - стоимость с₂₃ = 4 , а объем перевозки Х₂₃ = min {а_α; q₃ – х₁₃} = min {19;9} = 9. Процедура продолжается до тех пор, пока не будут израсходованы все объемы производства и потребления. Полученный план представлен в таблице 2. Он содержит 13 положительных перевозок, что соответствует требованию (m+n+2s-1 = 3+5+2*3-1=13) и не содержит циклов, что позволяет говорить о его опорности и невырожденности.

Определяем потенциал всех пунктов производства и потребления в соответствии с условием (3), при этом величину потенциала U₁ задаем произвольно, например, U₁ =10. Полученные потенциалы также заносим в таблицу 2 и проверяем найденный план на оптимальность, для чего используем условие (4). Данное условие не выполняется в двух случаях в IV блоке в клетках со стоимостями, равными 8 и 9. Следовательно, для этих клеток определяются невязки

η₄₅=23-14-8 = 1

η ₆₅=23-13-9 = 1.

Так как невязки равны, то ε -перевозка вводится в ту клетку, где меньше стоимость перевозки, т.е. в клетку со стоимостью, равной 8. Для сохранения баланса объемов производства и потребления необходимо построить ε -маршрут. В данном случае он проходит через клетки (4,4), (4,5), (5,5) и (5,4), т.е.

Определяем величину ε -перевозки как наименьшую из всех перевозок, стоящих на ε -маршруте в клетке с «-ε », т.е.
ε = min{4;11} = 4.

- ε

Определив ε -перевозку, строим новый план, в котором учитывается изменение перевозок на величину ε (см. табл. 3).

Таблица 3

	14	12	13	25	22	27	27	13	ai
10	6	7	3 11	м	м	м	м	м	11
9	5 10	5	4 9	м	м	м	м	м	19
6	8 2	6 16	9	м	м	м	м	м	18
14	0 7	м	м	12	8 4	11	13 8	0	19
15	м	0	м	10 9	7 7	12	15	0	16
13	м	м	0	13	9	10 10	14 6	0 4	20
	19	16	20	9	11	10	14	4

Для этого нового плана вновь строим систему потенциалов U_α и V_β и проверяем план на оптимальность. Для данного плана условие (4) полностью выполняется и, следовательно, он является оптимальным. Целевая функция для него имеет величину:

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