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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ Факультет заочно-послевузовского обучения КУРСОВАЯ РАБОТА По дисциплине: "Методы оптимизации" На тему: " Решение задач транспортного типа методом потенциалов " Воронеж 2003 г. СОДЕРЖАНИЕ 1. Линейная транспортная задача. 3 2. Математическая модель транспортной задачи. 4 3. Составление опорного плана. 5 4. Распределительный метод

достижения оптимального плана. 8 5. Решение транспортной задачи методом потенциалов. 11 Список использованной литературы 16 1. Линейная транспортная задача. Линейные транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных затрат. Если потребитель j получает единицу продукции

(по прямой дороге) со склада i, то возникают издержки Сij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы k С i j. Далее, предполагается, что где ai есть количество продукции, находящееся на складе i, и bj – потребность потребителя j. Замечание. 1. Если сумма запасов в пунктах отправления превышает сумму поданных заявок то количество

продукции, равное остается на складах. В этом случае мы введем "фиктивного" потребителя n +1 с потребностью и положим транспортные расходы pi,n+1 равными 0 для всех i. 2. Если сумма поданных заявок превышает наличные запасы то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления m + 1 с запасом и стоимость перевозок из фиктивного

пункта отправления во все пункты назначения принять равным нулю. 2. Математическая модель транспортной задачи. где xij количество продукции, поставляемое со склада i потребителю j, а С i j издержки (стоимость перевозок со склада i потребителю j). 3. Составление опорного плана. Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ северо-западного угла, способ