Задача транспорта

Следовательно, при решении задач модифицированным распределительным методом наличие  одного или нескольких альтернативных оптимальных базисных решений можно  обнаружить по равенству суммы потенциалов  с элементами целевой матрицы  в одной или нескольких свободных клетках. Но если имеется хотя бы одно альтернативное базисное решение, то существует множество оптимальных решений. В этом нетрудно убедиться, если в клетках А₁В₃, А₁В₄, А₃В₃ и А₃В₄ изменить загрузку в различных вариантах, не нарушая ограничений по спросу и предложению.

Распределительный метод достаточно прост, он позволяет  решать широкий круг различных задач. Существенным недостатком этого  метода является то, что им можно  пользоваться только тогда, когда имеем  дело с однородными величинами (однородный груз, однородный подвижной состав и т.п.).

14. Закрепление потребителей за поставщиками неоднородного взаимозаменяемого продукта

Во многих случаях перевозке подлежат разные, но взаимозаменяемые продукты (например, уголь, нефть, мазут или цемент разных марок). Рассмотрим постановку и метод  решения такой задачи.

В пунктах а₁, А₂, ..., А_i, ..., А_m хранится соответственно а₁, а₂, …, а_i, …, а_m тонн топлива разных сортов, причем в каждом из них имеется топливо только одного сорта. Таким образом, число пунктов отправления и число сортов топлива в этой задаче совпадают. Под топливом разного сорта подразумевается не только горючее разных видов (например, уголь, нефть, мазут), но и топливо одного вида, но разного качества (например, уголь разных сортов). Предприятиям, расположенным в пунктах В₁, В₂, ..., В_j, ..., В_n, требуется соответственно b₁, b₂, ..., b_j, …,b_n тонн условного топлива. Каждый из потребителей может использовать любой из имеющихся видов топлива. Коэффициенты приведения топлива разных сортов к условному топливу известны и составляют k₁, k₂, …, k_i, …,k_m. Известны также расстояния l_ij между пунктами А_i и В_j. Требуется составить план перевозок (закрепления потребителей топлива за поставщиками) так, чтобы полностью удовлетворить запросы всех потребителей при минимальном объеме транспортной работы.

Обозначим через x_ij количество топлива 1-го сорта (т. е. из i-го пункта), поставляемое j-му потребителю. Тогда рассматриваемая задача формально записывается следующим образом: минимизировать транспортную работу

                                                                       x_ij l_ij                                                   (14)

при условиях

                                     k_i x_ij = b_j , j = 1, 2, …, n                                               (15)

                                          x_ij < a_i , i = 1, 2, …, m                                               (16)

                                    x_ij > 0, I = 1, 2, …, m; j = 1, 2, …, n                           (17)

Ограничения (15) означают, что объем доставляемого в каждый пункт потребления топлива должен в условных единицах равняться спросу этого пункта. Условия (16) означают, что общий объем топлива, направляемый во все пункты потребления из i-го пункта, не должен превышать запасов топлива i-го сорта (имеющегося в i-м пункте).

Задача (14) — (17) отличается от классической транспортной наличием в условиях (15) коэффициента k_i. Поэтому актуальной является проблема сведения подобной задачи к классической транспортной. Анализ показывает, что в данном случае это возможно.

Обозначим запасы топлива на складах в тоннах условного топлива (условных тоннах) через а`<sub>1</sub>, а`₂, ..., а`<sub>i</sub>, ..., а`_m. При этом а`<sub>i</sub> = а<sub>i</sub> k<sub>i</sub>. Поскольку произведение условных тонн и условного расстояния перевозки не дают теперь величины реальной транспортной работы (тонно-километров), заменим l<sub>ij</sub> на l`_ij = l_ij /k _i.

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

l`<sub>ij</sub> x`_ij = l_ij x _ij ,

где х` — количество условного топлива, поставляемого из пункта А_i в пункт В _j).

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

                                                l`<sub>ij</sub> x`_ij                                                                          (18)

при условиях

                                                x`<sub>ij</sub> = b`_j , j = 1, 2, …, n;                                             (19)

                                           x`<sub>ij</sub> < a`_i, i = 1, 2, …, m;                                                   (20)

                                    x`_ij >0, i = 1, 2, …, m , j = 1, 2, …, n.                                   (21)

Задача (18) — (21) является открытой моделью классической транспортной задачи, и, следовательно, для ее решения можно использовать алгоритм метода потенциалов. При этом процедуру вычислений можно представить в следующем виде.

1. Пересчитать матрицу расстояний || l_ij || на || l`_ij || = l_ij /k_i.

2. Выразить  запасы топлива в пунктах А₁, А₂, ..., А_i, ..., А_m в тоннах условного топлива.

3. Составить  матрицу условий, используя величины а`<sub>i</sub>, b<sub>j</sub> и l`_ij.

4. Решить  поставленную задачу (найти оптимальный  план перевозок топлива, выраженного  в условных единицах) методом  потенциалов.

5. Заменить  величины а`<sub>i</sub>, х`_ij и l`_ij матрицы оптимального плана числами а_i, х_ij и l_ij, рассчитанными по формула

a _i = а`<sub>i</sub> / k<sub>i</sub> , x<sub>ij</sub> = x`_ij/ k_i , l _ij = l`_ij / k_i .

Поясним процедуру вычислений на конкретном примере. Пусть в пунктах А₁ и А₄ имеется соответственно 30 и 20 т угля марки А, в пункте А₂ —50 т угля марки Бив пункте А₃— 40 т угля марки В. Коэффициенты перевода угля в тонны условного топлива для марок А, Б и В соответственно 1,00; 1,20 и 1,25. Потребителям В₁, В₂, В₃ и В₄ требуется соответственно 40, 70, 40 и 10 т условного топлива, причем удовлетворять эту потребность можно углем любой марки. Расстояния между пунктами приведены в табл. 11. Требуется закрепить потребителей угля за поставщиками так, чтобы при полном удовлетворении спроса суммарный объем транспортной работы при перевозке угля был минимальным.

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

1. Расстояния в первой и четвертой строках таблицы (табл. 11) умножаем на 1,00, во второй — на 1,20 и в третьей — на 1,25; в результате получаем новую таблицу расстояний (табл.12).

Таблица 11