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

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

Построение математической модели - student2.ru - количество газет доставляемых из Построение математической модели - student2.ru – го п/о к Построение математической модели - student2.ru – му микрорайону.

Критерий – затраты на доставку газет.

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

Условия:

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения:

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

Выбор метода решения

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

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

a) Все переменные в условия входят с коэффициентом плюс единица.

b) Модель содержит два блока условий: по пунктам отправления (п/о) и по пунктам назначения (микрорайоны). При этом каждая переменная входит в условия два раза – по одному разу в каждый блок.

c) Задача имеет простые условия разрешимости: необходимо и достаточно, чтобы задача была сбалансирована Построение математической модели - student2.ru .

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

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

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

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

1. Проверяем задачу на сбалансированность Построение математической модели - student2.ru . Если задача не сбалансирована, то вводим фиктивного поставщика или потребителя с недостающими запасами или запросами и нулевыми стоимостями перевозок.

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

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

4. Переходим к новому опорному решению, на котором значение целевой функции будет меньше. Для этого находим клетку, которой соответствует наименьшая оценка Построение математической модели - student2.ru . Строим цикл пересчета, расставляя в клетках цикла поочередно знаки «+» и «-», начиная с «+» в свободной клетке. Осуществляем сдвиг по циклу на величину Построение математической модели - student2.ru , при этом из клеток со знаком «-» вычитаем Построение математической модели - student2.ru , а к клеткам со знаком «+» прибавляем Построение математической модели - student2.ru . Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным Построение математической модели - student2.ru . Вычисляем значение критерия для данного опорного решения. Далее возвращаемся к пункту 3 [5].

Реализация метода решения

1) Проверим задачу на сбалансированность:

Построение математической модели - student2.ru , Построение математической модели - student2.ru , Построение математической модели - student2.ru , Построение математической модели - student2.ru → задача не сбалансирована.

2) Приведем открытую транспортную задачу к закрытой.

Так как Построение математической модели - student2.ru , то введем фиктивного потребителя (киоски «Союзпечати»), потребности которого равны:

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

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

Таблица 6

Построение математической модели - student2.ru Построение математической модели - student2.ru Построение математической модели - student2.ru
2,5 3,1 2,7 2,4 2,2 М 2,0  
1,8 2,2 2,0 2,7 М 2,3 2,0  
М 1,6 2,0 М 1,8 2,5 М  
1,5 2,1 2,1 2,0 М 1,9 M  
1,5 1,2 M 2,3 2,7 М 3,5  

3) Построим начальный план доставки газет по методу минимальной стоимости.

Минимальная стоимость доставки: Построение математической модели - student2.ru . Заполнение таблицы начинаем с клетки Построение математической модели - student2.ru . Результаты занесем в таблицу 7.

Таблица 7

Построение математической модели - student2.ru   Построение математической модели - student2.ru
2,5 3,1   2,7     2,4   2,2   М 2,0  
1,8 2,2 2,0 2,7 М 2,3 2,0
М 1,6 2,0 М 1.8 2,5 М
1,5 2,1 2,1 2,0 М 1,9 M
1,5 1,2 M 2,3 2,7 М 3,5

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

4) Определим, будет ли данный план доставки газет оптимальным.

Находим значения потенциалов для занятых клеток, используя уравнения вида Построение математической модели - student2.ru :

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

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

Таблица 8

Построение математической модели - student2.ru   Построение математической модели - student2.ru  
2,5 3,1   2,7     2,4   2,2 М 2,0   Построение математической модели - student2.ru
1,8 2,2 2,0 2,7 М 2,3 2,0 Построение математической модели - student2.ru
М 1,6 2,0 М 1.8 2,5 М Построение математической модели - student2.ru
1,5 2,1 2,1 2,0 М 1,9 M Построение математической модели - student2.ru
1,5 1,2 M 2,3 2,7 М 3,5 Построение математической модели - student2.ru
  Построение математической модели - student2.ru Построение математической модели - student2.ru Построение математической модели - student2.ru Построение математической модели - student2.ru Построение математической модели - student2.ru Построение математической модели - student2.ru Построение математической модели - student2.ru Построение математической модели - student2.ru  

Для свободных клеток вычислим оценки по формуле:

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

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

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

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

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

5) Т.к. план доставки газет не оптимальный (среди оценок свободных клеток есть отрицательные), построим новый план доставки.

Выбираем наименьшую Построение математической модели - student2.ru . Этому условию соответствуют 2 клетки: Построение математической модели - student2.ru и Построение математической модели - student2.ru .

Выберем среди них клетку с минимальной стоимостью: Построение математической модели - student2.ru ( Построение математической модели - student2.ru . На соответствующей клетке построим цикл пересчета. Результаты занесем в таблицу 9.

Таблица 9

Построение математической модели - student2.ru   Построение математической модели - student2.ru  
2,5 3,1   2,7     2,4   2,2 - М + 2,0  
1,8 2,2 2,0 + 2,7 М 2,3 2,0 -
М 1,6 2,0 - М 1.8 + 2,5 М
1,5 2,1 2,1 2,0 М 1,9 M  
1,5 1,2 M 2,3 2,7 М 3,5
                 

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

Строим новый план доставки газет. Результаты заносим в таблицу 10.

Таблица 10

Построение математической модели - student2.ru   Построение математической модели - student2.ru  
2,5 3,1   2,7     2,4   2,2 М 2,0    
1,8 2,2 2,0   2,7 М 2,3   2,0  
М 1,6 2,0   М 1.8   2,5 М
1,5 2,1 2,1 2,0 М 1,9 M  
1,5 1,2 M 2,3 2,7 М 3,5
                 

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

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

Проверяем новый план на оптимальность. Находим значения потенциалов и оценки свободных клеток. Результаты заносим в таблицу 11.

Таблица 11

Построение математической модели - student2.ru   Построение математической модели - student2.ru  
2,5 3,1   2,7     2,4   2,2 М 2,0     Построение математической модели - student2.ru
1,8 2,2 2,0   2,7 М 2,3   2,0   Построение математической модели - student2.ru
М 1,6 2,0   М 1.8   2,5 М Построение математической модели - student2.ru
1,5 2,1 2,1 2,0 М 1,9 M Построение математической модели - student2.ru
1,5 1,2 M 2,3 2,7 М 3,5 Построение математической модели - student2.ru
  Построение математической модели - student2.ru Построение математической модели - student2.ru Построение математической модели - student2.ru Построение математической модели - student2.ru Построение математической модели - student2.ru Построение математической модели - student2.ru Построение математической модели - student2.ru Построение математической модели - student2.ru  

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

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

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

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

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

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

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

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

6) Решение задачи с помощью ППП «LINDO».

Для решения задачи математическая модель была введена в программу «LINDO». Существует несколько вариантов оптимального решения задачи, однако значение целевой функции во всех случаях равно Построение математической модели - student2.ru . Два различных оптимальных плана и результаты работы программы представлены в Приложении 1 и в Приложении 2.

7) Показать как измениться решение при следующих ситуациях:

a) п/о №1 доступны только районы А и Г, п/о №3 – Б и З.

Преобразуем таблицу 6, учитывая новые условия (недоступные районы отметим буквой М). Результаты занесем в таблицу 12.

Таблица 12

Построение математической модели - student2.ru Построение математической модели - student2.ru
2,5 М М 2,4 М М М
1,8 2,2 2,0 2,7 М 2,3 2,0
М 1,6 М М М М М
1,5 2,1 2,1 2,0 М 1,9 M
1,5 1,2 M 2,3 2,7 М 3,5

Построим математическую модель:

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

Условия:

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения:

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

Введем математическая модель в программу «LINDO». Результаты работы программы представлены в Приложении 3. Значение целевой функции равно Построение математической модели - student2.ru .

b) Время сортировки газет увеличиться на 20%.

Преобразуем таблицу 1, учитывая новые условия. Результаты занесем в таблицу 13.

Таблица 13

Номер п/о Микрорайоны
А Б В Г Д Ж З
119,6 99,6 129,6 121,6 124,6 133,6 124,6
Потребности микрорайона, тыс.экз.

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

Таблица 14

Номер п/о Микрорайоны
А Б В Г Д Ж З
М М
М М
М М М
М М М М
119,6 99,6 М М М М М
Потребности микрорайона, тыс.экз.

Преобразуем таблицу 7, учитывая новые условия. Результаты занесем в таблицу 15.

Таблица 15

Построение математической модели - student2.ru   Построение математической модели - student2.ru
2,5 М   2,7     2,4   2,2 М 2,0
1,8 2,2 2,0 М М 2,3 2,0
М 1,6 2,0 М 1.8 2,5 М
1,5 М М 2,0 М 1,9 M
1,5 1,2 M М М М М

Построим математическую модель:

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

Условия:

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения:

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

Введем математическая модель в программу «LINDO». Результаты работы программы представлены в Приложении 4. Значение целевой функции равно Построение математической модели - student2.ru .


Наши рекомендации