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

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

Кафедра экономики недвижимости

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

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

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

Москва

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1

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

Объекты недвижимости	Удельные затраты на перевозку груза, руб/т					Ресурсы произведенной
Грузы	I	II	III	IV	V	продукции, Ai, т
Бетон	55	48	49	60	25	149
Кирпич	45	35	96	55	66	163
Блоки	47	66	90	97	20	382
Потребности в строительных материалах, Bj, т	139	165	120	130	140

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

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

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

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

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

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

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

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

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

- количество пунктов назначения;

- номер груза:

- номер объекта недвижимости:

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

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

объем перевозимой –го вида стройматериала на -ый объект недвижимости, т;

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

-потребность –ого объекта недвижимости в строительных материалах, т;

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

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

Исходная информация обычно заносится в матрицу специального вида (табл.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

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

Объекты недвижимости	Удельные затраты на перевозку груза, руб/т					Ресурсы произведенной
Грузы	I	II	III	IV	V	продукции, т
Бетон	55 X11	48 X12	49 X13	60 X14	25 X15	149
Кирпич	45 X21	35 X22	96 X23	55 X24	66 X25	163
Блоки	47 X31	66 X32	90 X33	65 X34	20 X35	382
Потребности в строительных материалах, Bj, т	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

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

элемента

Объекты недвижимости Грузы	Удельные затраты на перевозку груза, тыс.руб/т					Объемы производства
	I	II	III	IV	V	продукции, т
Бетон	55	48 2	49 120	60 27	25	149 29 27 0 (6)
Кирпич	45	35 163	96	55	66	163 0 (2)
Блоки	47 139	66	90	65 103	20 140	382 242 103 0
Потребности в строительных материалах, т	139 0	165 2 0	120 0	130 103 0	140 0	694 694

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

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

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

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

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

Объекты недв.		Удельные затраты на перевозку груза, тыс.руб/т					Ресурсы, т
		142	148	149	160	115
	Грузы	I	II	III	IV	V
100	Бетон	55 13	48 2	49 120	60 27	25 10	149
113	Кирпич	45 16	35 163	96 60	55 8	66 64	163
95	Блоки	47 139	66 13	90 36	65 103	20 140	382
Потребности объектов в стройматериалах, т		139	165	120	130	140	694 694

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

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

Z_контр =.

Z_контр. = (142*139+148*165+149*120+160*130+115*140) – (100*149+113*163+95*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 объект;

с 3-го завода изготовителя: 139 т на 1 объект, 103 т на 4 объект, 140 т на 5 объект.

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

Распределить потоки инвестиций объектам недвижимости таким образом, чтобы эффективность от вложения денежных средств (в тыс.руб.) был максимальным. Исходные данные приведены в табл 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