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

ВВЕДЕНИЕ

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

5.1 Цель

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

5.2 Задачи

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение.

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

Переменные:

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

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

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

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

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

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

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

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

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