C) транспортная задача

m пунктов производства однородной продукции
a_i – объём производства в i -ом пункте производства
n пунктов потребления продукта
b_j – объём потребностей j -го потребителя
c_ij – стоимость перевозки 1-цы груза с i -го пункта производства в j -ый пункт потребления

Требуется так организовать перевозку, чтобы полностью вывезти продукт из каждого пункта производства, полностью удовлетворить потребности каждого потребителя и минимизировать при этом суммарные транспортные издержки. (Считается, что суммарный объём производства равен суммарному объёму потребления).

x_ij – искомый объём перевозки из i -го пункта производства в j -ый пункт потребления

Модель:

– минимизировать стоимость перевозки

– вывести из каждого пункта производства всю продукцию

– полностью удовлетворить потребности каждого потребителя

m + n ограничений и m · n переменных.

Если поменяем индексы (i, j)→ (k) (вытянем матрицу в вектор), то модель будет выглядеть:

x = (x ₁, …, x_{m · n})

, либо 0, либо 1