84272 (675685), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Примем следующие обозначения:

Тогда, при наличии баланса производства и потребления:

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

найти план перевозок

, где ;

минимизирующий общую стоимость всех перевозок

при условии, что из любого пункта производства вывозиться весь продукт

и любому потребителю доставляется необходимое количества груза

причем, по смыслу задачи

, …,

Для решения транспортной задачи чаще всего применяется метод потенциалов, при котором вводят обозначение вектора симплексных множителей или потенциалов:

Тогда:

, где ;

Откуда следует:

, где ;

При этом один из потенциалов можно выбирать произвольно, т.к. в системе (4.1) и (4.2) одно уравнение линейно зависит от остальных, а остальные потенциалы находятся, что для базисных значений .

Предположим, что однородный продукт, находящийся в трех пунктах производства (m=3), необходимо доставить в четыре пункта потребления (n=4). При этом матрица транспортных затрат на перевозку единицы продукта из любого пункта отправления в любой пункт назначения, вектор объемов запасов продукта в пунктах производства и вектор объемов продукта, необходимых пунктам потребления, имеют вид:

Тогда получается, что общий объем продукта в пунктах производства

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

Для того чтобы превратить открытую модель транспортной задачи в закрытую, необходимо ввести фиктивный пункт потребления с объемом потребления

единиц,

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

Тогда, первое базисное допустимое решение легко построить по правилу «северо-западного угла». А т.к. оценки базисных клеток транспортной таблицы равны нулю, то, приняв, что , первая транспортная таблица и потенциалы имеют вид:

Т.к. наибольшая положительная оценка всех свободных клеток транспортной таблицы, соответствует клетке 14, то строим цикл пересчета: 14-13-23-24 и производим перераспределение поставок вдоль цикла пресчета:

То получаем второе базисное допустимое решение и находим новые потенциалы, полагая :

Т.к. теперь наибольшая положительная оценка всех свободных клеток транспортной таблицы, соответствует клетке 22, то строим цикл пересчета: 22‑12‑14‑24 и производим перераспределение поставок вдоль цикла пресчета:

Отсюда получаем третье базисное допустимое решение и находим новые потенциалы, принимая :

Т.к. наибольшая положительная оценка всех свободных клеток транспортной таблицы, теперь соответствует клетке 21, то строим цикл пересчета: 21-11-14-24 и производим перераспределение поставок вдоль цикла пресчета:

Получаем четвертое базисное допустимое решение и находим новые потенциалы, принимая :

Т.к. наибольшая положительная оценка всех свободных клеток транспортной таблицы, соответствует клетке 33, то строим цикл пересчета: 33-23-21-11‑14‑34 и производим перераспределение поставок вдоль цикла пресчета:

Получаем пятое базисное допустимое решение и находим новые потенциалы, опять принимая :

Теперь наибольшая положительная оценка всех свободных клеток транспортной таблицы, соответствует клетке 25, отсюда строим цикл пересчета: 25-23-33- и производим перераспределение поставок вдоль этого цикла пресчета:

Получаем пятое базисное допустимое решение и снова находим новые потенциалы, принимая :

Находим оценки всех свободных клеток таблицы:

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

Характеристики

Список файлов реферата