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

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

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

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

.

Условия:

,

,

,

,

.

 

,

,

,

,

,

,

.

 

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

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

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

, , , → задача не сбалансирована.

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

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

.

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

Таблица 6

	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) Построим начальный план доставки газет по методу минимальной стоимости.

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

Таблица 7

	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

 

.

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

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

, , , , , , , , , , , .

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

Таблица 8

	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

 

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

.

, , , , ,

, ,

, , , , , , , ,

, , , , .

 

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

Выбираем наименьшую . Этому условию соответствуют 2 клетки: и .

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

Таблица 9

	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

 

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

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

 

Таблица 10

	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

 

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

.

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

Таблица 11

	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

 

, , ,

, , ,

, ,

, , ,

, ,

, , ,

, .

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

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

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

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

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

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

Таблица 12

	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

 

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

.

Условия:

,

,

,

,

.

,

,

,

,

,

,

.

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

.

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

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

	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	М	М	М	М

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

.

Условия:

,

,

,

,

.

,

,

,

,

,

,

.

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

.

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