Раздел 2. Применение линейного программирования. Распределительный метод Задача №10 - Распределение объемов обследовательских работ между производственными бригадами

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

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

Бригада	Стоимость обследования одного м2, тыс.руб.				Максимальная площадь, которую может обследовать бригада, м2
	1-й гараж. коопер.	2-й гараж. коопер.	3-й гараж. коопер.	4-й гараж. коопер.
№1	50	65	80	70	300
№2	60	65	75	80	500
№3	70	80	110	95	400
№4	55	85	150**	90	230*
Площадь, подлежащая обследованию, м2	130	275	715	380

Провести индивидуальную корректировку задания: *⁾ +10N (N – номер студента) **⁾ -10N

Дополнительное условие: 20% площади 1-го гаражного кооператива должна обследовать 2-я бригада.

Поставить задачу как распределительную (X_ij – площадь обследования земель i-й бригадой в j-м землепользовании гаражного кооператива, м2).

Порядок решения:

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

2. Записать условие задачи и целевую функцию с перечнем неизвестных, числовыми значениями ресурсов и коэффициентами.

3. Решить задачу без применения ПЭВМ, используя методы аппроксимации и потенциалов.

Опорное решение найти: для студентов с четным номером N – методом аппроксимации;

для студентов с нечетным номером N –методом минимального элемента.

4. Записать полный ответ решения задачи и проверить значение целевой функции.

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

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

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

Z=

Z_контр=

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

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

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

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

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

Таблица

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

	Бригада			Стоимость обследования одного м2, тыс.руб.								Максимальная площадь, которую может обследовать бригада, м2
				1-й гараж. коопер.		2-й гараж. коопер.		3-й гараж. коопер.		4-й гараж. коопер.
1		№1	50		65		80		70		300
2		№2	60		65		75		80		500
3		№3	70		80		110		95		400
4		№4	55		85				90
Площадь, подлежащая обследованию, м2			130		275		715		380

Таблица

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

№ п/п	Бригада	Стоимость обследования одного м2, тыс.руб.				Фиктивный столбец	Максимальная площадь, которую может обследовать бригада, м2
		1-й гараж. коопер.	2-й гараж. коопер.	3-й гараж. коопер.	4-й гараж. коопер.
1	№1	50	65	80	70		300
2	№2	60	65	75	80		500
3	№3	70	80	110	95		400
4	№4	55	85		90
Фиктивная строка
Площадь, подлежащая обследованию, м2		130	275	715	380

Запись ЭММ в расширенном виде с конкретными технолого-экономическими показателями

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

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

1. 1.

2. 2.

3. 3.

4. 4.

5. 5.

в) балансовое условие:

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

Целевая функция задачи Z=

Таблица 4

Определение опорного решения методом аппроксимации

i j	1	2	3	4	5	Ai	1	2	3	4	5	6
1	50	65	80	70		300
2	60	65	75	80		500
3	70	80	110	95		400
4	55	85		90
5
Bj	130	275	715	380
1
2
3
4
5
6

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

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

1. 1.

2. 2.

3. 3.

4. 4.

5. 5.

Проверка на число занятых клеток:

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

Z₁=

Таблица 5

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

№		1	2	3	4	5
1		50	65	80	70
2		60	65	75	80
3		70	80	110	95
4		55	85		90
5

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

Улучшающий многоугольник строим для клетки с максимальной по модулю оценкой =

Таблица 6

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

№		1	2	3	4	5
1		50	65	80	70
2		60	65	75	80
3		70	80	110	95
4		55	85		90
5

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

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

1. 1.

2. 2.

3. 3.

4. 4.

5. 5.

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

Z₂=

Таблица

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

№ п/п	Бригада	Стоимость обследования одного м2, тыс.руб.				Максимальная площадь, которую может обследовать бригада, м2
		1-й гараж. коопер.	2-й гараж. коопер.	3-й гараж. коопер.	4-й гараж. коопер.
1	№1	50	65	80	70	300
2	№2	60	65	75	80	500
3	№3	70	80	110	95	400
4	№4	55	85		90
Площадь, подлежащая обследованию, м2		130	275	715	380

Z_опт=

Ответ задачи: