Открытая транспортная задача с промежуточными пунктами 2

Материал из ALL
Перейти к: навигация, поиск

Открытая транспортная задача с промежуточными пунктами 2 – это открытая транспортная задача оптимизации перевозок с использованием промежуточных (транзитных) пунктов с избытком грузов (для перевозок) в транзитных пунктах.

Обозначения:

n — число конечных пунктов (поставщиков и потребителей);

np — число поставщиков;

n-np — число потребителей;

m — число промежуточных пунктов (складов);

mp — число складов с дополнительными (внутренними) потребностями;

m-mp — число складов с излишками продукции или нулевыми остатками;

bj>0, j=1,np — объём потребностей (в продукции) потребителей;

bj<0, j=np+1,n — объём поставок продукции поставщиков;

ai>0, i=1,mp — дополнительные (внутренние) потребности продукции (на складе);

ai≤0, i=mp+1,m — излишки продукции или нулевые остатки (на складе);

cij>0, i=1,m, j=1,np — транспортные тарифы на перевозку единицы продукции от поставщика на склад;

cij<0, i=1,m, j=np+1,n — транспортные тарифы на перевозку единицы продукции со склада к потребителю;

xij≥0, i=1,m, j=1,np — объём перевозок продукции от поставщика на склад;

xij≤0, i=1,m, j=np+1,n — объём перевозок продукции со склада к потребителю.

Математическая модель

ОТЗПП02.JPG.

  • Заметим, что в системе ограничений открытой задачи должно быть хотя бы одно строгое неравенство.

Условия разрешимости

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

ОТЗПП05.JPG

Введём дополнительные обозначения:

bn+1<0 — объём потребностей (в продукции) фиктивного потребителя;

cin+1≤0, i=1,m — транспортные тарифы на перевозку единицы продукции со склада к фиктивному потребителю;

xin+1≤0, i=1,m — объём перевозок продукции со склада к фиктивному потребителю.

Пусть M — это достаточно большое положительное число.

Для построения вспомогательной эквивалентной закрытой задачи введём фиктивного потребителя с параметрами:

ОТЗПП08.JPG

ОТЗПП12.JPG

Вспомогательная задача

ОТЗПП22.JPG

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

Очевидно, что вспомогательная задача является закрытой транспортной задачей с промежуточными пунктами, которая разрешима по построению. Для определения начального решения используется метод северо-западного угла, а для решения применяется метод потенциалов. Очевидно, что M-множители и метод потенциалов приводят к нулевым соответствующим (со склада с дополнительными внутренними потребностями к фиктивному потребителю) перевозкам в оптимальном решении. В оптимальном решении вспомогательной задачи все перевозки через конечные (без фиктивного потребителя) и промежуточные пункты являются оптимальным решением исходной задачи. А перевозки к фиктивному потребителю являются не использованными остатками (излишками) складов.

Другие задачи:

Ссылки