сколько ограничений возникнет в классической транспортной задаче из m поставщиков и n потребителей

В классической транспортной задаче, которая является частью линейного программирования, у нас есть m поставщиков и n потребителей. Задача заключается в том, чтобы минимизировать стоимость транспортировки товаров от поставщиков к потребителям с учетом ограничений по запасам у поставщиков и потребности у потребителей.

Общая форма транспортной задачи

Задача может быть записана в следующем виде:

• Целевая функция: минимизация общей стоимости транспортировки товаров с учётом расстояний и количеств товаров.

• Переменные: $x_{ij}$ — количество товара, которое поставщик $i$ должен отправить потребителю $j$.

• Ограничения:

  • Для каждого поставщика: сумма всех товаров, отправленных этим поставщиком, не должна превышать его запас.

  • Для каждого потребителя: сумма всех товаров, полученных этим потребителем, должна быть равна его потребности.

Теперь давай рассмотрим ограничения более подробно.

Количество ограничений в задаче

1. Ограничения на поставки: для каждого поставщика $i$ сумма товаров, отправленных этим поставщиком на всех потребителей, должна быть не больше его запаса:

   $$\sum _{j=1}^n{x}_{ij}\le s_i\text{для каждого}i=1,2,\dots ,m,$$

   где $s_i$ — запас поставщика $i$.

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

2. Ограничения на потребности: для каждого потребителя $j$ сумма товаров, полученных этим потребителем от всех поставщиков, должна быть не меньше его потребности:

   $$\sum _{i=1}^m{x}_{ij}=d_j\text{для каждого}j=1,2,\dots ,n,$$

   где $d_j$ — потребность потребителя $j$.

   Количество таких ограничений будет равно количеству потребителей $n$.

Итоговое количество ограничений

Итак, в классической транспортной задаче общее количество ограничений будет равно:

$$m+n.$$

Это потому что для каждого из $m$ поставщиков существует одно ограничение на сумму отправленных товаров, а для каждого из $n$ потребителей — одно ограничение на сумму полученных товаров.

Случаи с дополнительными ограничениями

• Невозможность выполнения задачи: Если сумма всех запасов поставщиков не равна сумме всех потребностей потребителей, то транспортную задачу нельзя решить. Это условие называется условием балансировки. В этом случае добавляются дополнительные ограничения, которые проверяют этот баланс, но это уже не влияет на количество основных ограничений.

• Негативные поставки: Часто в транспортной задаче предполагается, что количество товара $x_{ij}$ не может быть отрицательным (то есть $x_{ij}\ge 0$). Это накладывает дополнительное ограничение на каждую переменную:

  $$x_{ij}\ge 0\text{для всех}i\text{и}j.$$

  В данном случае количество таких ограничений будет равно $m\times n$ (по одному на каждую переменную).

Пример

Для наглядности, рассмотрим задачу с 2 поставщиками и 3 потребителями:

• Пусть поставщики имеют запасы $s_1=20$ и $s_2=30$.

• Пусть потребители имеют потребности $d_1=25$, $d_2=15$ и $d_3=10$.

У нас будет 2 ограничения для поставок:

$$x_{11}+x_{12}+x_{13}\le 20,x_{21}+x_{22}+x_{23}\le 30.$$

И 3 ограничения для потребностей:

$$x_{11}+x_{21}=25,x_{12}+x_{22}=15,x_{13}+x_{23}=10.$$

Итого — 2 (поставщики) + 3 (потребители) = 5 ограничений.

Если добавить ограничения на неотрицательность переменных $x_{ij}$, то получим 6 дополнительных ограничений (по одному для каждого значения переменной).

Заключение

В классической транспортной задаче из $m$ поставщиков и $n$ потребителей количество ограничений составит $m+n$. Если учитываются дополнительные условия, такие как неотрицательность переменных, количество ограничений увеличится.