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

ВВЕДЕНИЕ

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

5.1 Цель

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

5.2 Задачи

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение.

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

Переменные:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Х₁₁+ Х₁₂+ Х₁₃+ Х₁₄ = 90.

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

Х₂₁+ Х₂₂+ Х₂₃+ Х₂₄ = 120.

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

Х₃₁+ Х₃₂+ Х₃₃+ Х₃₄ = 150.

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

4. Пункта В₁:

Х₁₁+ Х₂₁+ Х₃₁=60.

5. Пункта В₂:

Х₁₂+ Х₂₂+ Х₃₂=90.

6. Пункта В₃:

Х₁₃+ Х₂₃+ Х₃₃=120.

7. Пункта В₄:

Х₁₄+ Х₂₄+ Х₃₄=90.

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

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

Z = 2Х₁₁+ 4Х₁₂+ 6Х₁₃+ 8Х₁₄+ 8Х₂₁+ 6Х₂₂+ 4Х₂₃+ 0Х₂₄+ 0Х₃₁+4Х₃₂+4Х₃₃+ 2Х₃₄→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) на основании следующего условия:

Х₁₁ = min {a₁;b₁} = min {90;60}= 60

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

Х₁₂ = min {a₁;b₂} = min {30;60}= 30; ∆ b₂ = 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 поставщик) устанавливается потенциал U_i, который можно интерпретировать как цену продукта пункта поставщика, а к каждому столбцу j-го потребителя устанавливается потенциал V_j , который можно интерпретировать как цену продукта у потребителя. Простейший случай: цена пункта потребителя равна цене продукта поставщика + расходы перевозок.

V_j = U_i + C_ij

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

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

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

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

0 0 4 8

d_ij = 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 1 20	+ 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

d_ij = 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

d_ij = 8 6 0 0

0 2 0 2

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

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