МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Пример транспортной задачи

Имеется два пункта производства продукции: "Северный" и "Южный". Эти пункты способны производить ежемесячно 1,5 тыс. тонн и 2 тыс. тонн продукции соответственно.

Имеется три пункта потребления этой продукции: "Горный", "Озерный" и "Лесной". Ежемесячные потребности этих пунктов в продукции составляют соответственно 0,8 тыс. тонн, 1,6 тыс. тонн и 1 тыс. тонн. Стоимость транспортирования 1 тонны груза от пункта производства к пункту потребления представлена в таблице 2.

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

Для удобства записи обозначим пункты производства числами 1 и 2 и пункты потребления числами 1, 2 и 3. Построение модели начнем с введения переменных. Обозначим посредством х_ij объем перевозки (в тоннах) от i-го пункта производства к  j-му пункту потребления.

Индекс i принимает одно из двух значений 1 или 2, а индекс j - одно из трех значений 1, 2 или 3. Таким образом, мы ввели 6 переменных. Из них, например, переменная х₁₁ соответствует объему перевозок от 1-го пункта производства ("Северный") к 1-му пункту потребления ("Горный"), а переменная х₂₃ - объему перевозок от 2-го пункта производства ("Южный") к 3-му пункту потребления ("Лесной").

Табл. 1.6

Набор значений переменных х_ij - это и есть план перевозок. Поскольку переменные имеют по два индекса, то план удобнее записывать не в виде вектора, а в виде матрицы:

Математическая модель задачи записывается в следующем виде.

Целевая функция задачи представляет собой сумму произведений стоимостей перевозки 1 т груза на объем перевозки для каждой пары поставщика-потребителя, то есть общую суммарную стоимость всех перевозок, соответствующих плану Х. Эту суммарную стоимость следует минимизировать при условии, что будут выполнены все ограничения.

Ограничения на перевозки можно разбить на три группы. Первая группа - это верхние два неравенства. В каждое из них входят переменные с одним и тем же первым индексом, но различными вторыми индексами, то есть переменные, соответствующие одному и тому же пункту производства, но различным пунктам потребления. Каждое из этих неравенств говорит о том, что суммарный объем всех грузов, вывозимых из одного и того же пункта производства в разные пункты потребления, не превосходит того количества продукции, которое может быть произведено в данном пункте производства.

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

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

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

В этом случае из пунктов производства должно быть вывезено все. Это значит, что ограничения первой группы, связанные с пунктами производства, должны выполняться в форме равенства. Точно так же и пункты потребления не могут быть в этом случае удовлетворены с избытком. Следовательно, и ограничения второй группы должны выполнятся в форме равенства.

Таким образом, если, например, потребность третьего пункта потребления равна не 1000 т, а 1100 т, так что суммарный груз в пунктах производства (3500 т) равен суммарной потребности в пунктах потребления (тоже 3500 т), то в математической модели неравенства первых двух групп ограничений могут быть заменены равенствами. Модель в этом случае будет иметь следующий вид.

Неравенства, связанные с пунктами производства и потребления, заменены здесь равенствами. Модель транспортной задачи с ограничениями-неравенствами называется открытой моделью. Модель с ограничениями-равенствами носит название закрытой модели.