Задача 6. Оптимизация строительства жилых и нежилых помещений в черте города на основе транспортной модели. Решение задачи на пэвм по программе «rasp».

Таблица - Исходные данные к задаче

Типы зданий	Стоимость Сij 1 м^2 жилья, руб					Предполагаемый объем строительства, м^2
	ЦАО	СВАО	ЮАО	ЮЗАО
Панель	700	500	600	500	12000***^)
Кирпич	900*^)	800	850	800	5000
Блоки	800	700	750	750	6000
Коттедж	1000	850	1000**)	900	4000
Общие потребность в жилье по округам, м^2	10000***)	5000**^)	5000	7000

Провести индивидуальную корректировку задания:

*) +N, где N = 82;

**) - 10*N;

***) -100*N.

Таблица - Исходные данные к задаче с корректировкой

Типы	Стоимость Сij 1 м^2 жилья, руб				Предполагаемый объем строительства, м^2
зданий	ЦАО	СВАО	ЮАО	ЮЗАО
Панель	700	500	600	500	3800
Кирпич	982	800	850	800	5000
Блоки	800	700	750	750	6000
Коттедж	1000	850	180	900	4000
Общие потребность в жилье по округам, м^2	1800	4180	5000	7000	18800 17980

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

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

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

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

4. Решить задачу на ПЭВМ по программе RASP.exe

5. Расшифровать результаты расчета и записать ответ задачи

Типы	Стоимость Сij 1 м^2 жилья, руб					Предполагаемый объем строительства, м^2
зданий	ЦАО	СВАО	ЮАО	ЮЗАО	Ф
Панель	700	500	600	500	0		3800
Кирпич	982	800	850	800	0		5000
Блоки	800	700	750	750	0		6000
Коттедж	1000	850	180	900	0		4000
Общие потребность в жилье по округам, м^2	1800	4180	5000	7000	820		18800 18800

Таблица – Нахождение опорного решения методом минимального элемента

	бетта	1682	1450	1550	1500
		1	2	3	4	5(ф)	Предполагаемый объем строительства, м2
	Типы зданий
альфа
	1	700	500	600	500	0	3800
1000		x	x	x	3800	х	0	3
	2	982	800	850	800	0	5000
700		1800	x	1820	1380	х	1380	5
							0
	3	800	700	750	750	0	6000
750		x	4180	x	1820	х	1820	7
							0
	4	1000	850	180	900	0	4000
1370		x	x	3180	x	820	3180	8
							0
	Общие потребность в жилье по округам, м2	1800	4180	5000	7000	820	18800
		0	0	1820 0	3200 1380 0	0	18800
		2	4	6	9	1

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

Значение целевой функции для этого опорного плана равно:

Z= Z = 500*3800 + 982*1800 + 850*1820 + 800*1380 + 700*4180 + 750*1820 + 180*3180 + 0*820 = 11 182 000

Балансовые условия

1800+4180+5000+7000+820=18800

3800+5000+6000+4000=18800

18800=18800

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

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

Х₁₁₊ Х₁₂₊ Х₁₃₊ Х₁₄ =3800

Х₂₁ +Х₂₂₊Х₂₃₊ Х₂₄ =5000

Х₃₁ +Х₃₂₊Х₃₃₊ Х₃₄ =6000

Х₄₁ +Х₄₂₊Х₄₃₊ Х₄₄ =4000

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

Х₁₁₊ Х₂₁₊ Х₂₁₊ Х₂₁ =1800

Х₁₂ +Х₂₂₊Х₃₂₊ Х₄₂ =4180

Х₁₃ +Х₂₃₊Х₃₃₊ Х₃₃ =5000

Х₁₄ +Х₂₄₊Х₃₃₊ Х₃₄ =7000

Х₁₅ +Х₂₅₊Х₃₅₊ Х₃₅ =820

Условие не отрицательности неизвестных

Х11≥0Х12≥0 Х₁₃≥00 Х₁₄≥0 Х₂₁ ≥0Х₂₂≥0Х₂₃ ≥0Х₂₄ ≥0 Х₃₁ ≥0Х₃≥0Х₃₃≥0 Х₃₄ ≥0 Х₄₁≥0Х₄₂≥0Х₄₃≥0 Х₄₄ ≥0 Х₁₁≥0 Х₂₁≥0 Х₂₁≥0 Х₂₁≥0 Х₁₂ ≥0Х₂₂≥0Х₃₂≥0Х₄₂ ≥0 Х₁₃ ≥0 Х₂₃≥0Х₃₃≥0 Х₃₃ ≥0 Х₁₄ ≥0Х₂₄≥0Х₃₃≥0 Х₃₄ ≥0 Х₁₅ ≥0Х₂₅≥0Х₃₅≥0 Х₃₅ ≥0

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

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

Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.

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

По строкам

3800=3800

1800+1820+1380=5000

4180+1820=6000

3180+820=4000

По столбцам

1800=1800

4180=4180

1820+3180=5000

3800+1280+1820=7000

820=820

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

Z = 500*3800 + 982*1800 + 850*1820 + 800*1380 + 700*4180 + 750*1820 + 180*3180 + 0*820 = 11 182 000

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

Для осуществления проверки опорного плана на оптимальность введем новые характеристики, так называемые условные оценки, которые будем называть потенциалами поставщиков и потребителей продукции (α_i, β_j)

Вычисление потенциалов α_i, β_j производится по занятым клеткам по формуле δ_ij= α_i+C_ij- β_j. Вычисление потенциалов для решаемой задачи записываем в дополнительной строке и столбце, а рассчитанные для свободных клеток оценки размещаем в левом нижнем углу свободной клетки.

Условие оптимальности

При решении задач на min решение является оптимальным, если для всех клеток их оценки неотрицательны δ_ij≥0. Оценки свободных клеток вычисляются по формуле δ_ij=α_i+C_ij-β_j

Вычисленные потенциалы (α_i, β_j) для решаемой задачи записываем в дополнительной строке и столбце, а рассчитанные для свободных клеток оценки δ_ij размещаем в левом нижнем углу свободной клетки

	бетта	1600	1500	1550	1500	890
		1	2	3	4	5(ф)	Предполагаемый объем строительства, м2
	Типы зданий
альфа
	1	700	500	600	500	0
1000		x	x	x	3800	х	3800
		18	50	50		-370
	2	982	800	850	800	0
666		1800	x	1820	1380	х	5000
			50			-670
	3	800	700	750	750	0
800		x	4180	x	1820	х	6000
		-132		-50		-620
	4	1000	850	180	900	0
890		x	x	3180	x	820	4000
		688	770		770
	Общие потребность в жилье по округам, м2						18800
		1800	4180	5000	7000	820	18800

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых: α_i + C_ij ≥β_j или δ_ij < 0

Необходимо провести улучшение плана методом построения улучшающего многоугольника или замкнутого прямоугольного цикла для клетки (1,4). Она в данном цикле будет свободной, все остальные вершины будут лежать в занятых клетках, стороны многоугольника параллельны строкам и столбцам матрицы, поворот осуществляется под прямым углом. Свободной клетке присваивается знак "+" и далее знаки чередуются "-", "+".

Таблица - Построение улучшающего многоугольника

	1	2	3	4	5(ф)	Предполагаемый объем строительства, м2
Типы зданий
1	700	500	600	500	0	3800
	x	x	x	3800	x
				-	+
2	982	800	850	800	0	5000
	1800	x	1820	1380	х
			-	+
3	800	700	750	750	0	6000
	x	4180	x	1820	х
4	1000	850	180	900	0	4000
	x	x	3180	x	820
			+		-
Общие потребность в жилье по округам, м2	1800	4180	5000	7000	820	18800
						18800

Таблица -Улучшенное на 2-м шаге решения

	1	2	3	4	5(ф)	Предполагаемый объем строительства, м2
Типы зданий
1	700	500	600	500	0	3800
	x	x	x	2980	820
				-	+
2	982	800	850	800	0	5000
	1800	x	1000	2200	x
			-	+
3	800	700	750	750	0	6000
	x	4180	x	1820	х
4	1000	850	180	900	0	4000
	x	x	4000	x	0
			+		-
Общие потребность в жилье по округам, м2	1800	4180	5000	7000	820	18800
						18800

После каждого улучшения значение целевой функции должно уменьшаться и так до получения оптимального решения. Значение целевой функции для контроля (со второй итерации) вычисляют по формуле: Z_посл=Z_пред+ΔZ; Z= δ_ij*Δx_min

РЕЗУЛЬТАТЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

======================================

(целевая функция минимизируется)

Опорное решение (метод минимального элемента):

===============================================

Zoporn = 11182000.00000

=============================================================================

i\ j|| 1 | 2 | 3 | 4 | 5 || a[i] | Alf[i]

=============================================================================

1 c|| 700.000| 500.000| 600.000| 500.000| 0.000|| | 1000.000

sigma|| 18.000| 50.000| 50.000| | -370.000|| |

x|| | | | 3800.00| ||3800.00|

-----------------------------------------------------------------------------

2 c|| 982.000| 800.000| 850.000| 800.000| 0.000|| | 700.000

sigma|| | 50.000| | | -670.000|| |

x|| 1800.00| | 1820.00| 1380.00| ||5000.00|

-----------------------------------------------------------------------------

3 c|| 800.000| 700.000| 750.000| 750.000| 0.000|| | 750.000

sigma|| -132.000| | -50.000| | -620.000|| |

x|| | 4180.00| | 1820.00| ||6000.00|

-----------------------------------------------------------------------------

4 c|| 1000.000| 850.000| 180.000| 900.000| 0.000|| | 1370.000

sigma|| 688.000| 770.000| | 770.000| || |

x|| | | 3180.00| | 820.00||4000.00|

=============================================================================

B[j] || 1800.00| 4180.00| 5000.00| 7000.00| 820.00||

============================================================

Bet[j]|| 1682.000| 1450.000| 1550.000| 1500.000| 1370.000||

============================================================

Оптимальное решение:

====================

Количество итераций = 4

Zmin=10394000.00000

=============================================================================

i\ j|| 1 | 2 | 3 | 4 | 5 || a[i] | Alf[i]

=============================================================================

1 c|| 700.000| 500.000| 600.000| 500.000| 0.000|| | 1000.000

sigma|| 100.000| 0.000| 50.000| | 300.000|| |

x|| | | | 3800.00| ||3800.00|

-----------------------------------------------------------------------------

2 c|| 982.000| 800.000| 850.000| 800.000| 0.000|| | 700.000

sigma|| 82.000| 0.000| | | || |

x|| | | 980.00| 3200.00| 820.00||5000.00|

-----------------------------------------------------------------------------

3 c|| 800.000| 700.000| 750.000| 750.000| 0.000|| | 800.000

sigma|| | | | 50.000| 100.000|| |

x|| 1800.00| 4180.00| 20.00| | ||6000.00|

-----------------------------------------------------------------------------

4 c|| 1000.000| 850.000| 180.000| 900.000| 0.000|| | 1370.000

sigma|| 770.000| 720.000| | 770.000| 670.000|| |

x|| | | 4000.00| | ||4000.00|

=============================================================================

B[j] || 1800.00| 4180.00| 5000.00| 7000.00| 820.00||

============================================================

Bet[j]|| 1600.000| 1500.000| 1550.000| 1500.000| 700.000||

============================================================

значения целевой функции в итерациях

=====================================

Nitera Z Nitera Z

1 11182000.00000 2 10632600.00000

3 10395000.00000 4 10394000.00000

	бетта	1600	1500	1550	1500	700
		1	2	3	4	5(ф)	Предполагаемый объем строительства, м2	Столбец разностей
	Типы зданий
альфа
	1	700	500	600	500	0	3800
1000		х	x	х	3800	х	0	100	100
	2	982	800	850	800	0	5000
700		x	x	980	3200	820	4180	50	50		50		50		50
							980 0
	3	800	700	750	750	0	6000 4200
800		1800	4180	20	х	х	20	50	50		50		50
							0
	4	1000	850	180	900	0	4000
1370		х	х	4000	х	х	0	190	190		190
	Общие потребность в жилье по округам, м2	1800	4180	5000	7000	820	18800
		0	0	1000 980 0	3200 0	0	18800
	Строка разностей	100	200	60	250	0
		100	200	60		0
		134	100	90		0
		134	100	100		0
			100	100		0
				100		0
						0

Таблица – Проверка оптимальности опорного решения методом потенциала для аппроксимации

	бетта	1600	1500		1550		1500		700
		1		2		3		4		5(ф)	Предполагаемый объем строительства, м2
	Типы зданий
альфа
	1	700		500		600		500		0	3800
1000		х		x		х		3800		х
		100		0		50				300
	2	982		800		850		800		0	5000
700		x		x		980		3200		820
		82		0
	3	800		700		750		750		0	6000
800		1800		4180		20		х		х
								50		100
	4	1000		850		180		900		0	4000
1370		х		х		4000		х		х
		770		720				770		670
	Общие потребность в жилье по округам, м2	1800		4180		5000		7000		820	18800
											18800

Вывод: получен план со всеми оптимальными клетками, улучшать опорный план не нужно.

Проверим с помощью программы:

РЕЗУЛЬТАТЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

======================================

(целевая функция минимизируется)

Оптимальное решение:

====================

Количество итераций = 1

Zmin=10394000.00000

===========================================================================

i\ j|| 1 | 2 | 3 | 4 | 5 || a[i] | Alf[i]

===========================================================================

1 c|| 700.000| 500.000| 600.000| 500.000| 0.000|| | 1000.000

sigma|| 100.000| 0.000| 50.000| | 300.000|| |

x|| | | | 3800.00| ||3800.00|

---------------------------------------------------------------------------

2 c|| 982.000| 800.000| 850.000| 800.000| 0.000|| | 700.000

sigma|| 82.000| 0.000| | | || |

x|| | | 980.00| 3200.00| 820.00||5000.00|

---------------------------------------------------------------------------

3 c|| 800.000| 700.000| 750.000| 750.000| 0.000|| | 800.000

sigma|| | | | 50.000| 100.000|| |

x|| 1800.00| 4180.00| 20.00| | ||6000.00|

---------------------------------------------------------------------------

4 c|| 1000.000| 850.000| 180.000| 900.000| 0.000|| | 1370.000

sigma|| 770.000| 720.000| | 770.000| 670.000|| |

x|| | | 4000.00| | ||4000.00|

===========================================================================

B[j] || 1800.00| 4180.00| 5000.00| 7000.00| 820.00||

============================================================

Bet[j]|| 1600.000| 1500.000| 1550.000| 1500.000| 700.000||

============================================================

Значения целевой функции в итерациях

=====================================

Nitera Z

1. 10394000.00000

Формирование окончательного решения

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

Фиктивный столбец удаляем из матрицы, а поставки их этих элементов записываем в скобках рядом с соответствующими значениями потребности, показывая оптимального потребителя в случае увеличения объемов производства.

Типы	Стоимость Сij 1 м^2 жилья, руб					Предполагаемый объем строительства, м^2
зданий	ЦАО	СВАО	ЮАО	ЮЗАО
Панель	700	500	600	500 3800	3800
Кирпич	982	800	850 980	800 3200	5000
Блоки	800 1800	700 4180	750 20	750	6000
Коттедж	1000	850	180 4000	900	4000
Общие потребность в жилье по округам, м^2	1800	4180	5000	7000	18800 17980 (18800)

Вывод: значение целевой функции при решении методом аппроксимации вручную и с помощью программы - Z=10 394 000.

Стоимость 1 м2 жилья в Москве будет минимальна и равны 15598400 рублей при следующем распределении площадей по типам зданий в округах:

Панельные здания: площадь 3800 м2 в округе ЮЗАО;

Кирпичные здания: площадь 980 м2 в округе ЮАО, 3200 м2 в округе ЮЗАО;

Блочные здания: площадь 1800 м2 в округе ЦАО, площадь 4180 м2 в округе СВАО, площадь 20 м2 в округе ЮАО;

Коттеджи: площадь 4000 м2 в округе ЮАО.