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

- чувствительность решения к изменению запасов сырья, т.е. значения приращения ресурсов, при которых сохраняется оптимальный набор переменных, входящих в оптимальное решение. После увеличения площади земли не более чем на 1000 га и уменьшения не более чем на 107,6923 га , уменьшения трудовых ресурсов не более чем на 1000 и увеличения не более чем на 1400 га, уменьшения соотношения площади пашни и сенокосов на 58,3333 га и увелечения на 1Е+30 га структура оптимального плана не изменится.

При выборе типа отчета «Пределы» появится лист «Отчет по пределам1» , который представлен на рисунке 9. В нем показано, в каких пределах может изменяться стоимость продукции, вошедшей в оптимальное решение, при сохранении структуры оптимального решения:

- приводятся значения Х1 и Х2 в оптимальном решении;

- приводятся нижние пределы изменения значений Х1 и Х2. Кроме этого, в отчете указаны значения целевой функции при трансформации земли на нижнем пределе: если неосвоенную землю не трансформировать в пашню, то стоимость продукции равна 344444,44 руб., если по нижнему пределу трансформировать в сенокосы 55,5556 га земли, то стоимость продукции составит 555555,58 руб. Далее приводятся верхние пределы изменения Х1 и Х2 и значения целевой функции при выпуске продукции, вошедший в оптимальное решение на верхних пределах: при трансформации в пашню 27,7778 га земли и 172,2222 га в сенокосы стоимость продукции составит 788888,87 рублей.

Microsoft Excel 10.0 Отчет по пределам
		Целевое
	Ячейка	Имя	Значение
	$D$4	коэфф в ЦФ ЦФ	788888,89
		Изменяемое			Нижний	Целевой	Верхний	Целевой
	Ячейка	Имя	Значение		предел	Результат	предел	результат
	$B$3	значение x1	27,777777		0	344444	27,777	788888
	$C$3	значение x2	172,22222		55,5556	555555,	172,22	788888

Рисунок 9 Лист «Отчет по пределам 1»

5. Задачи распределительного типа, решаемые в землеустройстве

ВВЕДЕНИЕ

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

5.1 Цель

Усвоить алгоритм решения задач распределительного типа методом потенциалов.

5.2 Задачи

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

5.3 Алгоритм решения

1. Составить экономико-математическую модель задачи.

2. Проверить задачу на сбалансированность и, при необходимости, привести к сбалансированному виду.

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

4. Решить задачу методом потенциалов (процесс решения отразить в таблицах). Метод потенциалов состоит из последовательности итераций и шагов.

ШАГ 1. Выписываю исходное базисное решение. Проверяем план на вырожденность. Если план вырожденный, то вводим в одну из пустых клеток поместить нулевую подставку и считать эту клетку занятой, при этом данная клетка не должна приводить к замкнутому контуру и занятых клеток

ШАГ 2. Проверяю план на оптимальность. Если план не оптимален, то переходим к шагу 3, если план оптимален, то переходим к 5 этапу.

ШАГ 3. Выполняю процесс улучшения плана.

Шаг 4. Строю новый план перевозок.

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

5.4 Пример решения задачи

В пунктах А1, А2 и А3 находятся соответственно 90, 120 и 150 т сырья. Пунктам В1, В2, В3 и В4 требуется соответственно 60, 90, 120 и 90 т сырья. Транспортные издержки перевозки из пункта А1 в пункты В1, В2, В3 и В4 равны 2, 4, 6, 8 у.е., соответственно из пункта А2 - 8, 6, 4, 0 у.е., А3 - 0, 4, 4, 2 у.е. Составьте план перевозок, минимизирующий общую сумму расходов.

Решение.

1. Составить экономико-математическую модель:

Переменные:

Х11 - количество перевозимого сырья из пункта А1 в пункт В1.

Х12 - количество перевозимого сырья из пункта А1 в пункт В2.

Х13 - количество перевозимого сырья из пункта А1 в пункт В3.

Х14 - количество перевозимого сырья из пункта А1 в пункт В4.

Х21 - количество перевозимого сырья из пункта А2 в пункт В1.

Х22 - количество перевозимого сырья из пункта А2 в пункт В2.

Х23 - количество перевозимого сырья из пункта А2 в пункт В3.

Х24 - количество перевозимого сырья из пункта А2 в пункт В4.

Х31 - количество перевозимого сырья из пункта А3 в пункт В1.

Х32 - количество перевозимого сырья из пункта А3 в пункт В2.

Х33 - количество перевозимого сырья из пункта А3 в пункт В3.

Х34 - количество перевозимого сырья из пункта А3 в пункт В4.

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

I. По запасам сырья, т:

1. В пункте А1:

Х11+ Х12+ Х13+ Х14 = 90.

2. В пункте А2:

Х21+ Х22+ Х23+ Х24 = 120.

3. В пункте А3:

Х31+ Х32+ Х33+ Х34 = 150.

II. По потребностям, т:

4. Пункта В1:

Х11+ Х21+ Х31=60.

5. Пункта В2:

Х12+ Х22+ Х32=90.

6. Пункта В3:

Х13+ Х23+ Х33=120.

7. Пункта В4:

Х14+ Х24+ Х34=90.

8. Условие неотрицательности переменных: Хij ? 0, i=1..3, j=1..4.

Целевая функция - минимальная сумма расходов:

Z = 2Х11+ 4Х12+ 6Х13+ 8Х14+ 8Х21+ 6Х22+ 4Х23+ 0Х24+ 0Х31+4Х32+4Х33+ 2Х34>min.

Таблица 5.1. Исходные данные

	В1	В2	В3	В4	Запасы
А1	2	4	6	8	90
А2	8	6	4	0	120
А3	0	4	4	2	150
Потребность	60	90	120	90	360

2. Проверить задачу на сбалансированность и, при необходимости, привести к сбалансированному виду.

Проверим задачу на сбалансированность по следующей формуле:

?Аi =?Вj.

Так как 90+120+150 = 60+90+120+90, то данная задача закрытого типа.

3. Получить опорное решение. Начальный план составим наиболее простым способом - методом северо - западного угла. Согласно этому правилу загружаем первую клетку (I;j)=(1;1) на основании следующего условия:

Х11 = min {a1;b1} = min {90;60}= 60

Таким образом, первый пункт назначения загружен, а первый пункт отправления имеет остатки груза ?а1 = 90-60=30, которые и распределяем на второй пункт назначения:

Х12 = min {a1;b2} = min {30;60}= 30; ? b2 = 60.

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

Таблица 5.2 Начальный план перевозок.

	В1	В2	В3	В4	Запасы
А1	2 60	4 30	6	8	90
А2	8	6 60	4 60	0	120
А3	0 Х	4	4 60	2 90	150
Потребность	60	90	120	90	360

Итерация 1.

Шаг 1.

Значение целевой функции равно:

Z = 60*2 + 4*30 + 60*6 + 60*4 +60*4 +2*90 = 1260 у.е.

Проверим план на вырожденность по следующей формуле:

N=m+n-1.

В нашем примере m=3, n=4, а число загруженных клеток 6, т.е. 6=6. Таким образом, план невырожден.

ШАГ 2. Проверяю план на оптимальность.

Проверяю методом потенциалов при которой каждый i-строки (I поставщик) устанавливается потенциал Ui, который можно интерпретировать как цену продукта пункта поставщика, а к каждому столбцу j-го потребителя устанавливается потенциал Vj , который можно интерпретировать как цену продукта у потребителя. Простейший случай: цена пункта потребителя равна цене продукта поставщика + расходы перевозок.

Vj = Ui + Cij

Потенциал первой строки равен 0.

Таблица 5.3 Транспортная схема 1

	В1	В2	В3	В4	Запасы	Ui
А1	- 2 60	+ 4 30	6	8	90	0
А2	8	- 6 60	+ 4 60	0	120	-2
А3	+ 0 Х	4	- 4 60	2 90	150	-2
Потребность	60	90	120	90	360
Vj	2	4	2	0

Затем определяю при оптимальности распределения через их оценки dij = ( Ui + Cij )- Vj. Условием оптимальности распределения служит условие не отрицательности оценок свободных клеток матрицы перевозок.

0 0 4 8

dij = 4 0 0 -2

--4 -2 0 0

План требует улучшения.

ШАГ 3. Выполняю процесс улучшения плана.

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

Шаг 4. Строю новый план перевозок.

Таблица 5.4 Транспортная схема 2

	В1	В2	В3	В4	Запасы	Ui
А1	2 0	4 90	6	8	90	0
А2	8	6	- 4 120	+ 0 Х	120	-2
А3	0 60	4	+ 4 0	- 2 90	150	-2
Потребность	60	90	120	90	360
Vj	2	4	2	0

Итерация 2

Шаг 1. Z = 0*2 + 4*90 + 120*6 + 0*4 +60*0 +2*90 = 1020 у.е.

Проверим условие N=m+n-1. Число загруженных клеток равен 4, а N=6, то условие не выполняется. В двух клетках нужно проставить нули и считать их условно загруженными.

ШАГ 2. Проверяю план на оптимальность.

Расчет потенциалов представлен в таблице 4.

Нахожу матрицу оценок.

0 0 4 8

dij = 4 0 0 -2

0 -2 0 0

План требует улучшения.

ШАГ 3. Выполняю процесс улучшения плана.

Клетку (2;4) или (3;2) нужно загрузить за счет перераспределения ресурсов из других загруженных клеток. Клетка (3;2) «плохая». Маршрут представлен в таблице 3.4.

Шаг 4. Строю новый план перевозок.

Таблица 5.4. Оптимальный план перевозок.

	В1	В2	В3	В4	Запасы	Ui
А1	2 0	4 90	6	8	90	0
А2	8	6	4 30	0 90	120	2
А3	0 60	4	4 90	2	150	2
Потребность	60	90	120	90	360
Vj	2	4	6	2

Итерация 3.

Шаг 1. Z = 0*2 + 4*90 + 30*4 + 90*0 +60*0 +4*90 = 840 у.е.

Проверим условие N=m+n-1. План невырожденный.

Шаг 2. Проверяю план на оптимальность. Расчет потенциалов представлен в таблице 3.4.

Нахожу матрицу оценок.

0 0 0 6

dij = 8 6 0 0

0 2 0 2

Матрица оценок состоит из неотрицательных клеток, следовательно, план оптимален.

Ответ: Транспортные издержки по оптимальному плану равны 840 у.е. Если их А1 в В2 перевезти 90 ц., из А2 в В3 30 ц., в В4 90 ц.; из А3 в В1 60 ц., в В3 90 ц. сырья.

5.5 Задачи

5.1 Составить экономико-математическую модель и решить методом потенциалов

1. На трех складах имеется сортовое зерно в количестве а1, а2, а3 ц (табл.1). Потребности четырех пунктов назначения в зерне соответственно в1, в2, в3, в4 ц (табл. 1). Расстояния в километрах между складами и пунктами даны в матрице расстояний D и являются одинаковыми для всех вариантов:

2 6 7 8

D = 1 3 4 5

9 7 5 9

Критерий оптимальности - минимальный объем грузоперевозок в т/км.

Таблица 5.5 Исходные данные

Варианты	Запасы зерна на складах, ц	Потребности пунктов назначения в зерне, ц
	а1	а2	а3	в1	в2	в3	в4
1	2000	3000	4000	1500	2300	3700	1500
2	2100	3200	3700	1600	2300	3700	1400
3	2150	3000	3850	1610	2390	2500	2500
4	2160	2840	4000	1720	2830	3000	1450

2. В хозяйстве имеется 4 участка пастбищ площадью 130, 93, 120, 82 га. Средняя урожайность на этих пастбищах составляет 100 ц зеленой массы с 1 га. В этом же хозяйстве есть 3 молочные фермы с потребностью в зеленых кормах 27000, 10000 и 5500 соответственно. Необходимо так распределить пастбища между фермами, чтобы суммарные потери молока в стоимостном выражении были минимальными. Исходные данные к задаче (в том числе потери в расчете на 2 ц зеленой массы с учетом расстояний между фермами и участками) приведены в таблице 3.6.

Таблица 5.6. Исходные данные

Участки пастбищ	1	2	3	4	Потребности в зеленых кормах
МФ-1	2	2	4	7	27000
МФ-2	3	1	8	4	10000
МФ-3	5	3	9	6	5500
Запас зел. массы на участках	13000	9300	12000	8200	42500

3. Три ближайших хозяйства имеют 7 чересполосных участков, продукция которых используется на кормовые цели. Необходимо так перераспределить чересполосные участки между хозяйствами, чтобы транспортные затраты на перевозку кормов были минимальными при условии, что общий объем потребления кормов в каждом хозяйстве сохраняется. Объем производства кормов в хозяйствах на первоначально закрепленных за ними участках составил: « 1 Мая» - 6000 т корм. ед. , « Луч» - 4000, « Победа» - 10000 т корм. ед. Объемы производства кормов на указанных участках ( т корм. ед. ): I - 1000, II - 2000, III - 3000, IV - 2500, V - 1500, VI - 9000, VII - 1000. Стоимость транспортировки кормов с участков в хозяйства в рублях и первоначальное закрепление участков за хозяйствами показаны в таблице 3.8

Таблица 3.8 Исходные данные

Хозяйства	« 1 Мая »	« Луч »	« Победа »	Объем пр-ва кормов в хоз-х, т. корм. ед
	I	II	III	IV	V	VI	VII
«1Мая»	5	10	18	22	8	17	6	6000
«Луч»	16	2	31	3	46	17	25	4000
«Победа»	8	25	36	14	13	4	28	10000
Объем пр-ва кормов на участках	1000	2000	3000	2500	1500	9000	1000	20000

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

Таблица 5.7. Исходные данные

Культуры	Интенсивность смыва почв т/га	Площадь культур, га
	1	2	3	4
1. Оз пшеница	1,2	4,7	12,7	27	640
2. Ячмень	2,4	5,7	12	34,5	860
3.Пар чистый	6	10	30	60	500
4. Площ. катег. земель	780	520	220	490

В роли удельных транспортных расходов будет выступать интенсивность смыва почвы.

5. Распределить посевы кормовых культур по 4 участкам земли различного плодородия таким образом, чтобы сбор кормов (в кормовых единицах) был максимальным. Исходные данные приведены в таблице 5.9.

Таблица 5.9 Исходные данные

Культуры	Урожайность культур по участкам, ц корм. ед. с 1 га	Площадь посева, га
	I	II	III	IV
1. Кукуруза на силос	35	38	40	47	550
2. Вико-овсяная смесь	18	18	21	26	1300
3.Однолетние травы на сено	10	11	13	12	900
4. Картофель	20	25	30	40	150
5. Кормовые бахчи	15	22	18	24	600
6. Многолетние травы на сено	20	18	19	22	800
Площади участков, га	2100	1700	1050	1000

6. В сельскохозяйственном предприятии на пахотных землях выделено 3 категории земли различной степени эродированности. Площадь земель различной категории первой- 50 га, второй -100 га, третей -120 га. Необходимо так разместить культуры на землях различной категории, чтобы смыв с поверхности почвы был минимальным. Площади пашни под различными культурами составляют озимая пшеница - 150 га, ячмень - 100 га, пар - 50 га. Интенсивность смыва представлена в таблице 5.11

Таблица 5.11.Дополнительная информация

Культура	Интенсивность смыва почвы при размещении на землях определенной категории, т. на 1 га в год	Площадь культур
	1	2	3
Озимая пшеница	5	4	5	150
Ячмень	2	3	2	100
Пар чистый	2	4	6	50
Площади категории земель, га	50	100	120

6. Освоение ППП PER - пакета экономических расчетов. Решение транспортной задачи

ВВЕДЕНИЕ

Алгоритмы задач принятия решений настолько сложны, что без применения компьютера реализовать их практически невозможно. Компьютер с помощью программного обеспечения реализует алгоритмы поиска оптимального решения, которые преобразуют исходные данные в результат. Комплекс программ «PER» предназначен для решения задач линейного и нелинейного программирования. Поиску оптимальных решений транспортных задач с помощью «PER» и посвящено методическое указание.

6.1 Цель

Усвоить алгоритм решения транспортных задач на «PER».

6.2 Задачи

Составить математическую модель задачи, матрицу модели, ввести условие задачи в «PER», решить задачу в «PER», создать отчет по результатам решения в «PER», провести анализ решения.

6.3 Описание пакета экономических расчетов «PER»

Пакет состоит из нескольких программ, среди которых важное место занимает «Транспортная задача» (рисунок 10).



Рисунок 10 ПЭР

При нажатии на «ENTER», в момент, когда курсор находится на 3 -Транспортная задача мы войдем в главное меню программы которое состоит из 10 опций (рисунок 11).

Рисунок 11 Главное меню

При входе в «Обзор для системы принятия решений» можно получить справочную информацию о программе. Ввод новой задачи можно осуществить войдя во 2 опцию «Ввод новой задачи». Открыть файл, имеющийся на диске возможно с помощью опции 3 - Чтение существующей задачи с диска. Исходную информацию можно просмотреть с помощью опции 4 - Вывод или печать входных данных. Решение задачи можно увидеть в опции 5 - Решение задачи. Исправить или заменить входные данные задачи возможно в 7 опции - Корректировка. Опция 8 и 9 предназначены для окончания работы в программе «Транспортная задача».

6.4 Рассмотрение примера решения задач в «PER»

Условие задачи. В сельскохозяйственном предприятии на пахотных землях выделено 3 категории земель различной степени эродированности. Площадь земель различной категории - 50 га, второй -100 га, третьей - 120 га. Необходимо, так разместить культуры на землях различной категории, чтобы смыв с поверхности почв был минимальным. Площади пашни под различные категории составляет озимая пшеница -150га, ячмень - 100 га, пар - 50 га.

Таблица 1 Дополнительная информация

Культура	Интенсивность смыва почвы при размещении на землях определенной категории, т. на 1 га в год	Площадь культур
	1	2	3
Озимая пшеница	5	4	5	150
Ячмень	2	3	2	100
Пар чистый	2	4	6	50
Площади категории земель, га	50	100	120

6.4.1 Составим экономико-математическую модель

Введем обозначения:

номер культуры,

j - номер категории пшеницы,

m - количество культур (строк),

n - количество категорий земель (столбцов),

Хij - площадь i - ой культуры на землях j - ой категории,

Z - целевая функция (общий смыв почвы).

Имеем 2 группы ограничений:

Первая группа ограничений по площади под культуры:

X11 + X12 + X13 =150

X21 + X22 + X23 =100

X31 + X32 + X33 =50.

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

X11 + X21 + X31 =50

X12 + X22+ X32 =100

X13 + X23 + X33 =120.

Условие неотрицательности:

Xij ? 0 (i=1,2,3; j=1,2,3).

Целевая функция:

Z = 5X11 + 4X12 + 5X13 + 2X21 + 3X22 + 2X23 + 2X31 + 4X32 +6X33 => min.

6.4.2 Решение задачи на PER

Для решения задачи выбираем программу «Транспортная задача». Следующим шагом выбираем опцию 2 - Ввод задачи. После чего вводим имя файла «1». Появляется диалоговое окно, которое заполняем исходными данными (рисунок 3).

Рисунок 12 Входные данные

После нажатия на клавишу пробел вводим объемы поставок и запросы потребителей (рисунок 4). Нажимая на клавишу пробел, выводим следующее диалоговое окно, в которое вводим «тарифы» клеток (рисунок 5). При нажатии на клавишу пробел, выходит сообщение о том, что условие задачи сформулировано.

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



Рисунок 13 Объемы поставок и запросы потребителей

Рисунок 14 Коэффициенты затрат и прибыли

Программа первоначальный план распределения поставок выполняет методом «Северо-западного угла». Решает задачу методом потенциалов.

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

Рисунок 15 Результат решения задачи

Полученное решение означает, что минимальный смыв с поверхности почв составит 800 т, при размещении озимой пшеницы на 100 га земли второй категории, на 20 га третьей категории, ячменя на 100 га земли третьей категории, чистого пара на 50 га земли первой категории. 30 га пшеницы останется не размещенными.

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1 Волков, С.Н. Землеустройство.Т.4: Экономико-матаматические методы и модели [Текст] : учебник / С.Н.Волков. 2-е изд., стер. - М. : Колос, 2007. - 696 с.

2 Волков, С. Н. Экономические модели в землеустройстве [Текст] : учебное пособие / С. Н. Волков, А. Н. Безгинов - М.: Академический печатный дом, 2001. - 284 с.

3 Гатауллин, А.М. Математическое моделирование экономических процессов в сельском хозяйстве [Текст] : учебник / А. М. Гатауллин, Г. В. Гаврасов, Т. М. Сорокин. - СПб: ИТК Гранит, 2009. - 271 с.

4 Орлова, И.В. Экономико-математическое моделирование: практическое пособие по решению задач [Текст] : учебное пособие / И. В. Орлова. - 2-е изд, стер. - М.: Вузовский учебник: ВЗФЭИ, 2007. - 143 с.

5 Практикум по математическому моделированию экономических процессов в сельском хозяйстве / А. Ф. Кариенко, 2-е изд, стер. - М. : Агропромиздат, 1985. - 269 с.

6 Федосеев, В. В. Экономико - математические методы и модели [Текст] : учебное пособие / - М. : ЮНИТИ, 2005. - 391 с.

7 Экономическая информатика [Текст] : учебник / В. П. Косарева, 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2008. - 592 с.

Лицензия РБ на издательскую деятельность № 0261 от 10 апреля 1998 года.

Подписано в печать _____________ года. Формат 60х84. Бумага типографическая. Гарниткра Таймс. Усл. печ. л. ___ Тираж ____экз. Заказ №

Издательство Башкирского государственного аграрного университета.

Кафедра статистики и информационных систем в экономике.

Адрес издательства и типографии: 450001, г. Уфа, ул. 50 лет Октября, 34.

Размещено на Allbest.ru