Оптимизация с использованием модели транспортной задачи

В настоящее время задачи, стоящие в народном хозяйстве  планирование производства, обслуживания, транспортных перевозок и т. п., являются очень сложными и объемными. Каждая такая задача имеет множество параметров, от которых зависит эффективность тех или иных операций. Если еще в начале двадцатого века задачи производственного планирования можно было решить методом перебора вариантов, то сейчас это невозможно. Поэтому и возникла дисциплина, получившая название «Системный анализ и исследование операций».

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

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

1 Оптимизация с использованием модели транспортной задачи

1.1 Математическая модель задачи

Математическая модель задачи представляет собой следующее. Необходимо доставить от заводов i некоторый однородный товар в объеме Аi единиц потребителям j с минимальными транспортными издержками. Потребность каждого потребителя в товаре составляет Вj единиц. Известны также сij — величины стоимости перевозки единицы груза от i — того завода к j — потребителю.

Т.к., то мы имеем транспортную задачу открытого типа.

Введем переменные xij=Аij, обозначающие количество единиц груза, перевозимого от i-го завода j-му потребителю. Такие переменные должны удовлетворять следующим условиям:

1. ограничение по запасам: j=1n xij = Ai; (1.1.1)

2. ограничение по потребностям: i=1m xij = Bj; (1.1.2)

3. условия неотрицательности: xij0(i=1.m; j=1.n). (1.1.3)

Суммарные транспортные затраты на перевозки определяются следующей формулой:

L =i=1m j=1n cijxij (1.1.4)

Таким образом, математически транспортная задача представляется так. Найти m. n переменных xij, удовлетворяющих системам уравнений (1.1.1) и (1.1.2), и условиям неотрицательности (1.1.3), для которых целевая функция (1.1.4) принимает минимальное значение.

1.2 Выбор и описание метода решения

Прежде чем приступить к решению задачи необходимо построить исходный опорный план. Для этого воспользуемся методом минимальной стоимости. В таблице из всех значений выбираем наименьшее и в клетку (i, j) с наименьшей стоимостью записываем меньшее из чисел Аi и Bj (объемы поставок и потребностей соответственно). Исключаем из рассмотрения строку i, если запас Аi вывезен полностью, или столбец j, если потребность Bj полностью удовлетворена. Среди остальных стоимостей снова выбираем наименьшую и заполняем соответствующую клетку таблицы. Таким же образом продолжаем заполнять клетки таблицы, пока не будет найдено опорное решение.

Для решения воспользуемся методом потенциалов.

Теорема: Решение транспортной задачи будет оптимальным, если найдутся такие числа и, называемые соответственно потенциалами поставщиков и потребителей, которые будут удовлетворять условиям:

+ =сij для; (1.2.1)

+ <=сij для; (1.2.2)

где сij — стоимость перевозки от i -того поставщика к j — тому потредителю.

— объем перевозки груза.

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

1. находится первый опорный план методом минимальных стоимостей.

2. проверяется найденный опорный план на оптимальность для чего:

находятся потенциалы поставщиков ui и потребителей vj по формуле (1.2.1)

проверяется, выполнено ли условие (1.2.2) (или sij = cij — (ui + vj)>=0). если для всех клеток это условие выполнено, то опорный план является оптимальным (решение завершено). Если же для некоторых свободных клеток sij < 0, то клетка с наименьшим значением sij является ерспективной и выполняется следующий пункт алгоритма.

К перспективной клетке сроится цикл, расставляются знаки по циклу, при этом в перспективную клетку ставится +, а остальные знаки в вершинах цикла чередуются, и определяется величина перераспределения груза Qij = min xij, где xij — объем перевозки груза, записанный в клетках (вершинах) цикла таблицы, отмеченных знаком минус.

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

После перераспределения потенциалы пересчитываются.

1.3 Оптимизация решения вручную