Формулировка транспортной задачи

Транспортная задача

Содержание

Введение

Алгоритмы решения транспортной задачи

Формулировка транспортной задачи

Опорное решение транспортной задачи

Методы построения начального опорного решения.

Метод минимальной стоимости

Переход от одного опорного решения к другому

Означенный цикл

Метод потенциалов

Алгоритм решения транспортной задачи методом потенциалов

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

Введение

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

Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.

Цель заданной работы - освоить математическую постановку транспортной задачи линейного программирования.

Алгоритмы решения транспортной задачи

Формулировка транспортной задачи

Однородный груз сосредоточен у m поставщиков в объемах . Данный груз необходимо доставить n потребителям в объемах . Известны , i=1,2,,…,m, j=1,2,…,n- стоимости перевозки единицы груза от каждого I-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.

Исходные данные транспортной задачи обычно записываются в таблице 1.

			…
			…
			…
…	…	…	….	….
			…

Таблица 1.

Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков А=( ), вектора запросов потребителей

В=( ) и матрицы стоимостей .

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

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

Такая задача называется задачей с правильным балансом,а ее модель – закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом,а ее модель – открытой .

Дата добавления: 2015-06-30; просмотров: 153; Нарушение авторских прав

Мы поможем в написании ваших работ!