Постановка и свойства транспортной задачи

Описание ситуации. Некоторый однородный продукт (груз) сосредоточен в m пунктах отправления (производства) в количествах а₁, а₂, …, a_m единиц соответственно. Его нужно доставить в n пунктов назначения (потребления), подавших заявки на этот продукт в количествах b₁, b₂, …, b_n единиц соответственно. Предполагается, что сумма всех заявок равна сумме всех запасов, т.е. выполнено следующее условие:

= . (1)

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

Известны тарифы (стоимости) c_ij () перевозки единицы груза из i‑го пункта отправления в j-й пункт назначения. Требуется найти план перевозок, который удовлетворяет заявки всех пунктов назначения и минимизирует суммарные затраты на перевозку.

Математическая модель. Для построения модели описанной выше ситуации, определим переменные x_ij — количество груза, перевозимого из i-го пункта отправления в j-й пункт назначения (). Ясно, что они должны принимать неотрицательные значения. Множество всех переменных (план перевозок) задается в виде матрицы X = (x_ij), имеющей размеры mхn.

Сама математическая модель задачи нахождения плана перевозок с наименьшими суммарными затратами выглядит так:

, (2)

, (3)

, (4)

. (5)

Формула (2) задает правило подсчета общих транспортных затрат Z, необходимых для реализации плана перевозок X = (x_ij). Таким образом, Z является целевой функцией, и решается задача ее минимизации на множестве планов перевозок, задаваемом ограничениями модели (3) – (5).

Условие (3) показывает, что общее количество груза, вывезенное из любого пунктаотправления должно равняться величине запаса этого пункта. Соответственно условие (4) показывает, что общее количество груза, доставленное в любой пункт назначениядолжно равняться потребности этого пункта.

Задача (2) – (5) называется транспортной задачей, а равенства (3) – (4) называются условиями сбалансированности плана перевозок X = (x_ij).

План перевозок X = (x_ij) (), удовлетворяющий соотношениям (3) – (5), называется допустимым планом задачи (2) – (5).

Допустимый план X^* = () называется оптимальным планом, если на нем общая величина затрат на перевозки S(X^*) минимальна.

Транспортная задача называется закрытой (сбалансированной),если выполнено условие (1). Это условие обеспечивает существование оптимального решения задачи (2) – (5).

Теорема 1. Транспортная задача имеет оптимальный план тогда и только тогда, когда она является закрытой.

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

Допустимый плантранспортной задачи называется опорным планом, если столбцы матрицы условий, соответствующие его положительным компонентам, линейно независимы. Известно, что максимальное число линейно независимых столбцов матрицы условий транспортной задачи равно m + n – 1. Поэтому опорный план не может иметь более m + n – 1положительных компонент. Если опорный план имеет ровно m + n – 1положительных компонент, то он называется невырожденным планом, а если меньше, то вырожденным.

Стандартный метод ее решения включает следующие пункты.

1. Построение начального опорного плана перевозок.

2. Проверка полученного плана на оптимальность. Если он не является оптимальным, то строится новый улучшенный план перевозок, на котором транспортные затраты меньше, или, по крайней мере, равны затратам предыдущего плана. Этот пункт повторяется до тех пор, пока не будет получено оптимальное решение.

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

При проверке на оптимальность допустимого плана используется следующий критерий.

Теорема 2. Допустимый план перевозок X^* = () в транспортной задаче будет оптимальным тогда и только тогда, когда найдутся числа u₁,…, u_m и v₁, …,v_n такие, что выполнены следующие соотношения:

v_j – u_i ≤ с_ij для всех i, j (6)

v_j – u_i = с_ij, если > 0.(7)

Числа u_i называются потенциалами пунктов отправления, а v_j — потенциалами пунктов назначения. Условия (6) и (7) означают, что разность потенциалов между двумя любыми пунктами отправления и назначения в оптимальном плане не должна превосходить затрат на перевозку единицы груза. Если же между пунктами осуществляется перевозка, то разность потенциалов между ними в точности равна затратам на перевозку единицы груза. Потенциалы могут интерпретироваться как цены продукции в этих пунктах.

С помощью этого критерия можно не только проверить на оптимальность любой план перевозок, но и указать способ улучшения неоптимального плана. Для этого обычно используется метод потенциалов.

Поиск по сайту: