3. Задача прикрепления потребителей к поставщикам (транспортная задача)

Рассмотрим проблему организации перевозки некоторого условного продукта между пунктами его производства, количество которых равно m, и n пунктами потребления. Каждый i–й пункт производства (i = 1,…, m) характеризуется запасом продукта а_i ≥0, а каждый j-ый пункт потребления (j = 1,…, n) – потребностью в продукте b_j≥0. Сеть коммуникаций, соединяющая систему рассматриваемых пунктов, моделируется с помощью матрицы С размерности m×n, элементы которой (с_ij) представляют собой нормы затрат на перевозку единицы груза из пункта производства A_i в пункт потребления B_j. То есть задана таблица (матрица):

bj аi	B1		B2		…	Bn
A1		c11		c12	…		c1n	a1
A2		c21		c22	…		c2n	a2
…	…		…		…	…		…
Am		cm1		cm2	…		cmn	am
	b1		b2		…	bn

Строки транспортной таблицы соответствуют пунктам производства А_i (в последней клетке каждой строки указан объем запаса продукта a_i), а столбцы – пунктам потребления В_j (последняя клетка каждого столбца содержит значение потребности b_j). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i–го пункта производства в j–ый пункт потребления.

План перевозки груза в данной транспортной сети представляется в виде массива элементов размерности m×n:

.

Ограничения на возможные значения х_ij имеют вид:

1) ограничения на удовлетворение потребностей во всех пунктах потребления:

(2.3.1)

2) ограничения на возможности вывоза запасов из всех пунктов производства:

(2.3.2)

3) условия неотрицательности компонент вектора плана х:

Существенной характеристикой описываемой модели является соотношение параметров а_i и b_j. Если суммарный объем производства равен суммарному объему потребления, а именно,

, (2.3.3)

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

Поскольку ограничения модели (3.3.1) и (3.3.2) могут быть выполнены только при сбалансированной ТЗ, то при построении транспортной модели необходимо проверять условие баланса (3.3.3). В случае, когда суммарные запасы превышают суммарные потребности, необходим дополнительный фиктивный пункт потребления, который будет формально потреблять существующий излишек запасов, то есть

(3.3.4)

На практике запас продукции у отправителей не будет исчерпан. Или, по-другому, план вывоза будет недовыполнен. Ситуация может быть охарактеризована как излишек продукции или дефицит спроса.

Если суммарные потребности превышают суммарные запасы, то необходим дополнительный фиктивный пункт отправления, формально восполняющий существующий недостаток продукции в пунктах отправления:

(3.3.5)

В данной постановке запас продукции у отправителей недостаточен для покрытия спроса. План завоза продукции потребителям будет недовыполнен. Ситуация может быть охарактеризована как дефицит продукции или ажиотажный спрос.

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

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

Тогда модель транспортной задачи имеет вид:

или в подробном виде:

Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (m+n)×mn. Ранг матрицы задачи равен m+n-1 , и ее невырожденный базисный план план должен содержать m+n-1 ненулевых компонент.

3. Графический метод решения задач

   1. Графически решаются задачи:

• Имеющие не более двух переменных;

• Заданные в каноническом виде с числом независимых переменных не более двух.

1. Допустимая область:

• Область допустимых значений пуста (рис. 1);

• Выпуклое многоугольное множество (ограниченное (рис. 2) или неограниченное (рис. 3))

1. Число оптимальных планов:

• ни одного оптимального плана (вследствие неограниченности целевой функции (рис. 4) или пустоты допустимой области (рис. 1));

• единственное решение (последняя точка касания целевой функции с многоугольником решений);

• бесконечно много решений (если последнее касание - отрезок).

4. Этапы решения:

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

1. На плоскости X₁OX₂ строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2. Находят полуплоскости, определяемые каждым из ограничений задачи.

3. Строят многоугольник решений.

4. Строят вектор который указывает направление возрастания целевой функции.

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

6. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.

Минимальное значение линейной функции находится путем передвижения начальной прямой в направлении, противоположном вектору .

Примечание: Если начальная прямая сливается с одной из сторон многоугольника решений, то множество оптимальных решений записывают как линейную выпуклую комбинацию углов точек отрезка по формуле:

,

где ,

А и В начальная и конечная точка отрезка.

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

Задача. Туристская фирма в летний сезон обслуживает в среднем 7500 туристов и располагает флотилией из двух типов судов, характеристики которых представлены в таблице.

Показатели	Судно
	I	II
Пассажировместимость, чел	2000	1000
Горючее, т	12000	7000
Экипаж, чел	250	100

В месяц выделяется 60.000 т горючего. Потребность в рабочей силе не превышает 700 человек.

Определите количество судов I и II типа, чтобы обеспечить максимальный доход, который составляет от эксплуатации судов I типа 20 млн руб., а II типа – 10 млн. руб. в месяц.

Составим математическую модель данной задачи. Для удобства все данные разделим на 1000. Обозначим: х₁ ‑ количество судов I типа, х₂ – количество судов II типа. Доход от эксплуатации этих судов составляет 20 х₁ + 10 х₂ тыс. руб. в месяц. Этот доход необходимо по условиям задачи максимизировать. Беспредельному увеличению количества судов препятствуют определенные ограничения. Ограничено количество горючего, которое выделяется для работы судов, отсюда неравенство: 12 х₁ + 7 х₂<=60 тыс. тонн. Ограничено потребность в рабочей силе, не более 700 человек, поэтому 0,25 х₁ + 0,1 х₂ <=0,7 человек. И в то же время количество судов I и II типов должны обеспечить перевозку 2500 туристов в месяц, т.е. 2 х₁ + х₂>=2,5 человек. Кроме того, количество судов – неотрицательное число, поэтому х₁ >=0, х₂ >=0.

Итак, математическая модель данной задачи записывается так:

Так как модель имеет только две переменные, то данную задачу можно решить геометрическим методом.

Построим на плоскости Х₁ОХ₂ многоугольник допустимых решений задачи. Для этого в неравенствах системы ограничений знаки неравенств заменим на знаки точных равенств:

(1.3.1)

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

Полученное пространство решений есть многоугольник ABCD. Для нахождения минимума и максимума целевой функции строим начальную прямую и вектор – градиент . Координатами вектора являются коэффициенты целевой функции при переменных x₁ и x₂. Для построения графика целевой функции задаем произвольное значение . Если , то прямая проходит через начало координат. Для ее построения, полагая x₁=1, получим x₂=-2, а при x₂=1, получим x₁=-¹/₂. Полагая , таким же образом построим линию целевой функции.

Таким же образом построим на графике ряд параллельных прямых, рис 1.3.1, где вектор – градиент показывает направление возрастания целевой функции.

Максимальное значение будет в точке D. Так как точка D получена в результате пересечения прямых (2) и (4), то для определения ее координат решим систему уравнений:

Максимальное значение целевой функции

=20x₁+10x₂=20 * 0 + 10 * 7=70 (млн. руб.)

Таким образом, во флотилии туристской фирмы суда первого типа не должны использоваться вообще (x₁=0), а суда второго типа необходимы в количестве 7 штук (x₂=7). Доход в этом случае будет максимальным и составит 70 млн. руб. в месяц.

9