Специальные задачи линейного программирования

2.1. Постановка задачи и математическая модель транспортной задачи. Предположим, что существуют N потребителей и M поставщиков некоторого однородного груза, у каждого из поставщиков определенный запас этого груза (A_i единиц, i=1,2,…,M), а каждому из потребителей требуется B_j единиц груза (j=1,2,…, N). Известны также затраты c_ij на перевозку единицы груза от поставщика A_i к потребителю B_j. Требуется составить такой план перевозок от поставщиков к потребителям, чтобы суммарные затраты на перевозки оказались минимальными (при этом должны быть по возможности вывезены все запасы поставщиков и удовлетворены все запросы потребителей).

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

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

При составлении математической модели через x_ij обозначается количество единиц груза, который будет перевезен от поставщика A_i к потребителю B_j (объем перевозок от A_i к B_j). Эти значения будут вноситься в центр соответствующей ячейки.

С учетом сказанного целевая функция принимает вид

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

Таблица 2.1.

Заметим, что суммарные запасы (30+190+250=470) равны суммарным запросам (70+120+150+130=470). Разместим в основной (незаштрихованной) части таблицы искомые объемы перевозок x_ij и перейдем к составлению математической модели. Заметим, что нумерация соответствует привычной нумерации элементов в матрицах (i – номер строки, j – номер столбца). Итак, целевая функция принимает вид

(2.1)

(просуммировали произведения стоимостей на объемы перевозок по всем строкам). При построении системы ограничений сначала суммируем объемы перевозок по каждому столбцу (удовлетворяем все запросы), а потом суммируем объемы перевозок по каждой строке (вывозим все запасы). Учтем также неотрицательность значений x_ij и получаем следующие условия:

(2.2)

Итак, мы построили математическую модель предложенной задачи с целевой функцией (2.1) и системой ограничений (2.2).

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

Задание 2.2. Решить транспортные задачи (определить оптимальное значение целевой функции).