МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ Факультет заочно-послевузовского обучения КУРСОВАЯ РАБОТА По дисциплине: "Методы оптимизации" На тему: " Решение задач транспортного типа методом потенциалов " Воронеж 2003 г. СОДЕРЖАНИЕ 1. Линейная транспортная задача. 2. Математическая модель транспортной задачи. 3. Составление опорного плана. 4. Распределительный метод достижения оптимального плана. 5. Решение транспортной задачи методом потенциалов. 11 Список использованной литературы 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.
Для этого существуют различные способы. Например, способ северо-западн... В составе заявки пункта В3 остались неудовлетворёнными 39 единиц. Из них 30 покроем за счёт пункта А2, чем его запас будет исчерпан, и е... Их отличие состоит в том, что во втором способе мы распределяем продук... Их число должно равняться m + n - 1.
Распределительный метод достижения оптимального плана. Теперь попробуе... Перенесем, например, 18 единиц из клетки (1,1) в клетку (2,1) и чтобы ... Подсчитав стоимость опорного плана (она ровняется 1039) и стоимость но... Таким образом, при любом циклическом переносе, оставляющем перевозки н... Очевидно, для улучшения плана имеет смысл перемещать перевозки только ...
Пусть имеется транспортная задача с балансовыми условиями Стоимость пе... Идея метода потенциалов для решения транспортной задачи сводиться к сл... Таким образом, при пользовании методом потенциалов для решения транспо... После этого из m + n - 1 уравнений (3) можно найти остальные платежи &... Если хотя бы в одной свободной клетке псевдостоимость превышает стоимо...