МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РФ

ДЕПЕРТАМЕНТ КАДРОВОЙ ПОЛИТИКИ И ОБРАЗОВАНИЯ

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПО ЗЕМЛЕУСТРОЙСТВУ

КАФЕДРА ЗЕМЛЕУСТРОЙСТВА

С.Н. Волков, А.В. Купчиненко, В.В. Бугаевская

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИРОВАНИЕ

РАСПРЕДЕЛИТЕЛЬНЫЙ МЕТОД

Задания для выполнения лабораторных,

самостоятельных и контрольных работ

Для студентов высших учебных заведений по специальностям:

310900 – Землеустройство

311000 – Земельный кадастр

311100 – Городской кадастр

и направлению:

560600 – Землеустройство и земельный кадастр

Москва 2003

УДК 332.3:519.86

Подготовлены к печати кафедрой землеустройства Государственного университета по землеустройству (протокол № 13 от 22 апреля 2003 г.).

Рекомендованы учебно-методическим объединением по образованию в области землеустройства и кадастров в качестве рабочей тетради для межвузовского использования (протокол № 3 от 7 мая 2003 г.).

Составители: д.э.н, профессор С.Н. Волков;

к.э.н., профессор А.В. Купчиненко;

к.э.н., доцент В.В. Бугаевская.

Рецензенты: к.э.н., доцент В.И. Нилиповский

(кафедра экономической теории и менеджмента ГУЗ);

д.т.н., проф. А.Н. Безгинов

(кафедра землеустройства ГУЗ)

Задание III

Распределительная (транспортная) модель линейного

программирования

Порядок полного оформления решений задач

транспортного типа

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

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

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

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

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

6). Получить опорное решение заданным способом (процесс решения отразить в таблице).

7). Проверить опорное решение на оптимальность и, при необходимости, получить оптимальное решение методом потенциалов (процесс решения отразить в таблицах).

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

Схема оформления и методы решения задач транспортного типа

Демонстрационная задача №1

Найти минимум затрат на перевозку кормов с севооборотных массивов на животноводческие фермы. Данные по затратам на перевозку единицы груза с учетом удаленности участков от производственных центров приведены в табл. 1.

Таблица 1

Табличная форма записи исходных данных транспортной задачи

Фермы	Удельные затраты на перевозку груза, руб/т					Ресурсы
Севообороты	Ферма 1	Ферма 2	Ферма 3	Ферма 4	Ферма 5	севооборотов, Ai, т
Полевой-1	55	48	49	60	25	149
Полевой-2	45	35	96	55	66	163
Кормовой	47	66	90	65	20	382
Потребности ферм в кормах, Bj, т	139	165	120	130	140

Порядок выполнения задачи:

1. Записать математическую формулировку задачи в общем виде.

2. Дать развернутую запись условия задачи с числовым значением переменных и ресурсов.

3. Задачу решить, используя метод наилучшего элемента.

4. Записать ответ.

Определение опорного решения задачи методом минимального элемента

Формализация исходных данных задачи:

Введем следующие обозначения:

- количество севооборотов (пунктов отправления);

- количество ферм (пунктов назначения);

- номер севооборота:

- номер фермы:

, – индексы строк; , – индексы столбцов;

стоимость перевозки единицы объема продукции с –го севооборота на -ую ферму, руб/т;

объем перевозимой продукции с –го севооборота на –ую ферму, т;

- объем продукции, производимой на –ом севообороте и предназначенной для транспортировки на фермы, т;

-потребность –ой фермы в кормах, т;

Количество маршрутов равно mxn

- целевая функция (критерий оптимизации).

Исходная информация обычно заносится в матрицу специального вида (табл.2)

Таблица 2

Табличная форма записи

транспортной задачи

Пункты назначения Пункты отправ- ления	Характеристика оценки					Объемы производства
	1	2	3		n	продукции
1	с11 х11	с12 х12	с13 х13	с1j х1j	с1n х1n
2	с12 х21	с22 х22	с23 х23	с2j х2j	с2n х2n
	сi1 хi1	сi2 хi2	сi3 хi3	сij хij	сin хin
m	сm1 хm1	сm2 хm2	сm3 хm3	сmj хmj	сmn хmn
Максимальные объемы переработки продукции

Запись задачи транспортного типа в структурной форме:

Найти такие объемы ( ) транспортировки кормов с севооборотных массивов на фермы, при которых целевая функция примет минимальное значение:

Ограничения по строкам:

Сумма перевозимых кормов с –го севооборотного массива на –у ферму должна быть равна запасу кормов данного севооборота:

.

Ограничения по столбцам:

Сумма объемов продукции, доставляемых на –ую ферму со всех севооборотных массивов, должна быть равна потребности в кормах на данной ферме:

.

Балансовое условие:

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

.

Условие не отрицательности переменных:

.

Матричная запись исходных данных задачи после учета требований сбалансированности представлена в табл.3.

Таблица 3

Табличное представление исходных данных задачи

Фермы	Удельные затраты на перевозку груза, тыс.руб/т					Ресурсы
Севообороты	Ферма 1	Ферма 2	ферма 3	Ферма 4	Ферма 5	севооборотов, т
Полевой-1	55 X11	48 X12	49 X13	60 X14	25 X15	149
Полевой-2	45 X21	35 X22	96 X23	55 X24	66 X25	163
Кормовой	47 X31	66 X32	90 X33	65 X34	20 X35	382
Потребности ферм в кормах, т	139	165	120	130	140	694 694

Запись задачи в развёрнутом виде с конкретными технолого-экономическими коэффициентами.

1) Требования к целевой функции:

Z=55x₁₁+48x₁₂+49x₁₃+60x₁₄+25x₁₅+45x₂₁+35x₂₂+96x₂₃+55x₂₄+66х₂₅+

+47x₃₁+66x₃₂+90x₃₃+65x₃₄+20x₃₅ min;

Балансовое условие: .

149+163+382=694

139+165+120+130+140=694;

694=694 – модель задачи закрытая.

2) Граничные условия

Ограничения по строкам исходной матрицы:

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅=149,

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅=163,

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅=382.

Ограничения по столбцам исходной матрицы:

x₁₁+x₂₁+x₃₁=139,

x₁₂+x₂₂+x₃₂=165,

x₁₃+x₂₃+x₃₃=120,

x₁₄+x₂₄+x₃₄=130,

x₁₅+x₂₅+x₃₅=140.

3) условие не отрицательности неизвестных:

x₁₁ 0, x₁₂ 0, x₁₃ 0, x₁₄ 0, x₁₅ 0, x₂₁ 0, x₂₂ 0, x₂₃ 0, x₂₄ 0, x₂₅ 0, x₃₁ 0,x₃₂ 0, x₃₃ 0, x₃₄ 0, x₃₅ 0.

Получение опорного решения методом минимального элемента удобно проводить в таблице специального вида (табл.4).

Таблица 4

Получение опорного решения методом минимального

элемента

Фермы Севообороты	Удельные затраты на перевозку груза, тыс.руб/т					Ресурсы
	Ферма 1	Ферма 2	Ферма 3	Ферма 4	Ферма 5	севооборотов, т
Полевой-1	55 х	48 2	49 120	60 27	25 х	1 49 29 27 0 (6)
Полевой-2	45 х	35 163	96 х	55 х	66 х	163 0 (2)
К ормовой	47 139	66 х	90 х	65 103	20 140	382 242 1 03 0
П отребности ферм в кормах, т	1 39 0	165 2 0	120 0	1 30 103 0	1 40 0	694 694

(3) (4) (5) (7) (1)

Порядок заполнения маршрутов показан цифрами в скобочках (1), (2) и т.д. до получения опорного решения.

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

1. Из всех оценок выбираем минимальную С₃₅=20

В данную клетку вносим максимальную поставку равную x₃₅₌140

Из соответствующего ресурса и потребности вычитаем эту поставку A₃-140=242; B₅-140=0

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

Контроль вычислений

1) Проверка по числу занятых клеток .

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

, где – число строк, – число столбцов.

В нашем случае 7 и (m+n-1)=3+5-1=7; то есть решение верное и невырожденное.

2) Проверка опорного решения на выполнение граничных условий:

а) по строкам:

2+120+27=149,

163=163,

139+103+140=382.

б) по столбцам:

139=139,

163+2=165,

120=120,

27+103=140,

140=140

Граничные условия по строкам и столбцам выполняются.

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

Z= =2*48+120*49+27*60+163*35+139*47+103*65

+140*20=29329.

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

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

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

За первый потенциал примем произвольное число т.е. сonst. Чтобы обеспечить положительность потенциалов за первый потенциал примем значение, равное максимальной оценке.

, так как

Вычислим и аналогично все остальные потенциалы.

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

Таблица 5

Потенциалы и оценки для опорного решения задачи

Фермы		Удельные затраты на перевозку груза, тыс.руб/т					Ресурсы, т
		132	138	139	150	105
	Севообороты	Ферма 1	Ферма 2	Ферма 3	Ферма 4	Ферма 5
90	Полевой-1	55 1 3	48 2	49 120	60 27	25 10	149
1 03	Полевой-2	45 16	35 163	96 60	55 8	66 64	163
85	Кормовой	47 139	66 13	90 36	65 103	20 140	382
Потребности ферм в кормах, т		139	165	120	130	140	694 694

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

5) Для контроля целевую функцию вычисляем по формуле, используя вычисленные потенциалы и :

Z_контр = .

Z_контр. = (132*139+138*165+139*120+150*130+105*140) – (90*149+103*163+85*382) =29329.

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

Таблица 6

Оптимальное решение задачи

j i	1	2	3	4	5	Ресурсы, т
1	55	48 2	49 120	60 27	25	149
2	45	35 163	96	55	66	163
3	47 139	66	90	65 103	20 140	382
Потребности, т	139	165	120	130	140	694 694

Ответ: затраты на перевозку кормов с севооборотных массивов на животноводческие фермы будут минимальны и равны 29329 рублей при следующем распределении перевозок с севооборотов на фермы:

с полевого севооборота -1: 2 т на 2 ферму, 120 т на 3 ферму, 27 т на 4 ферму;

с полевого севооборота -2: 163 т на 2 ферму;

с кормового севооборота: 139 т на 1 ферму, 103 т на 4 ферму, 140 т на 5 ферму.

Демонстрационная задача №2

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

Таблица 7

Табличная форма записи исходных данных задачи

№	Культуры	Урожайности культур по участкам (ц.к.е./га)				Площадь
п/п		I	II	III	IV	посева, га
1	Кукуруза на силос	44	41	42	46	1400
2	Одн.травы на з/к	43	40	40	45	2300
3	Одн. Травы на сено	28	26	27	29	1100
4	Картофель	67	65	66	69	950
5	Горох	18	19	17	22	2500
6	Мн.травы на сено	43	40	44	45	800
	Площади участков, га	2100	1900	2600	1554

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

2) Найти опорное решение методом аппроксимации.

3) Опорное решение проверить методом потенциалов, получить оптимальное решение.

4) Задачу решить с дополнительными ограничениями:

а) не менее половины площади посева однолетних трав на сено должно быть размещено на 3-м участке;

б) посевы однолетних трав на з/к на четвертом участке должны составлять точно 300 га;

с) весь картофель разместить на четвертом участке;

d) посевы кукурузы на втором участке должны занимать не более 900.

5) Записать ответ задачи.

1) Запись модели задачи в структурном виде:

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

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

а) по строкам:

б) по столбцам:

Балансовое условие:

Условие неотрицательности переменных:

Таблица 8

Табличное представление исходных данных задачи

№ п/п	Культуры	Урожайности культур по участкам (ц.к.е./га)				Площадь посева, га
		I	II	III	IV
1	Кукуруза на силос	44 X11	41 X12	42 X13	46 X14	1400
2	Одн.травы на з/к	43 X21	40 X22	40 X23	45 X24	2300
3	Одн. травы на сено	28 X31	26 X32	27 X33	29 X34	1100
4	Картофель	67 X41	65 X42	66 X43	69 X44	950
5	Горох	18 X51	19 X52	17 X53	22 X54	2500
6	Мн. травы на сено	43 X61	40 X62	44 X63	45 X64	800
Площади участков, га		2100	1900	2600	1554	9050 8154