В пунктах
А1 и
А2 производится продукт в объемах
а1 и
а2 единиц. В пунктах
В1 и
В2 этот продукт потребляется в объемах
b1 и
b2. Из каждого пункта производства возможна транспортировка в любой пункт потребления. Транспортные издержки по перевозке из пункта
Ai в пункт
Bj равны
cij. Необходимо решить транспортную задачу, т.е. найти такой план перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен, и суммарные транспортные издержки минимальны.Формальная постановка задачи:
Z = c11 x11 + c12 x12 + c21 x21 + c22 x22→ min
при ограничениях
x11+x12=a1x21+x22=a2x11+x21=b1x12+x22=b2
при условии неотрицательности решения,
xij≥ 0, и баланса:
a1+a2=b1+b2. Введем сквозную нумерацию переменных и исключим из рассмотрения последнее условие (устраним линейную зависимость уравнений на основе баланса). Система уравнений всех граней (действительных и возможных) многогранника допустимых решений имеет вид:
y1 | +y2 | | =a1 |
| | y3+y4 | =a2 |
y1 | | +y3 | =b1 |
y1 | | | =0 |
| y2 | | =0 |
| | y3 | =0 |
| | y4 | =0 |
Сколько вариантов решения систем линейных уравнений следует проанализировать при прямом переборе вершин в многограннике допустимых решений?
a1=012,
a2=0,
b1=70,
b2=50