Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Транспортная задача. Метод потенциалов.




Обозначим A1, A2,…,Am - поставщики, В1, В2, …, Вn – потребители.

Объем потребления в j-м пункте (j=1,2,…,n) обезначим bj. Расходы на перевозку еденицы продукта из пункта Аi в пункт Вj это Cij. Матрицу С=(Сij) называют матрицей транспортных расходов. Требуется составить план перевозок при котором весь продукт вывозится из пунктов Аi в пункты Вj в соответствии с потребностью причем общая величина транспортных издержек при этом минимально.

Обозначим через xij – количество продуктов перевозимых из пункта Аi в пункт Вj.

(1)

(2)

Если выполняется условие (2), то транспортная задача является закрытой.

Рассмотрим метод потенциалов, т.е. каждому i-му поставщику поставим в соответствие величину ui называется потенциалом. И каждому j-му потребителю поставим в соответствие потенциал vj.

ui – цена продукта у i-го поставщика; vj – цена продукта н j-го потребителя. vj=ui+cij (3)

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

1) Строится начальный план перевозок;

2) Находим потенциалы ui и vj и анализируем полученный результат .

3) Если план не является оптимальным, то производим перераспределение начального плана и переходим к пункту 2.

Таблица 1.

Поставшики Потребители ui
b1 b2 bj bn
a1 c11 x11 c12 x12 … … c1j x1j … … c1n x1n  
a2 c21 x21 c22 x22 … … c2j x2j … … c2n x2n  
… … … … … … … … … … … …  
ai ci1 xi1 ci2 xi2 … … cij xij … … cin xin  
… … … … … … … … … … … …  
am cm1 xm1 cm2 xm2 … … cmj xmj … … cmn xmn  
vj              

Применяется метод северо-западного угла и метод наименьшей стоимости. Базис будет содержать m+n-1 переменных.


mylektsii.ru - Мои Лекции - 2015-2018 год. (0.005 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал