![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Транспортная задача. Метод потенциалов.
Обозначим A1, A2, …, Am - поставщики, В1, В2, …, Вn – потребители. Объем потребления в j-м пункте (j=1, 2, …, n) обезначим bj. Расходы на перевозку еденицы продукта из пункта Аi в пункт Вj это Cij. Матрицу С=(Сij) называют матрицей транспортных расходов. Требуется составить план перевозок при котором весь продукт вывозится из пунктов Аi в пункты Вj в соответствии с потребностью причем общая величина транспортных издержек при этом минимально. Обозначим через xij – количество продуктов перевозимых из пункта Аi в пункт Вj.
Если выполняется условие (2), то транспортная задача является закрытой. Рассмотрим метод потенциалов, т.е. каждому i-му поставщику поставим в соответствие величину ui называется потенциалом. И каждому j-му потребителю поставим в соответствие потенциал vj. ui – цена продукта у i-го поставщика; vj – цена продукта н j-го потребителя. vj=ui+cij (3) Алгоритм решения транспортной задачи: 1) Строится начальный план перевозок; 2) Находим потенциалы ui и vj и анализируем полученный результат. 3) Если план не является оптимальным, то производим перераспределение начального плана и переходим к пункту 2. Таблица 1.
Применяется метод северо-западного угла и метод наименьшей стоимости. Базис будет содержать m+n-1 переменных.
|