Математическая формулировка транспортной задачи

       От каждого i-того производителя, произведенный им ресурс a_i может перемещаться к j-тому потребителю ресурса в объеме, не превышающим b_j. Таким образом x_ij будет означать, перемещение некоторого числа единиц ресурса от i-того производителя к j-тому потребителю.

       c_ij обозначим стоимость перемещения единицы ресурса, тогда матрица X={x_ij} будет называться матрицей или планом перевозок, C={c_ij} – матрицей стоимости. Любой план перевозок X, обеспечивающий распределение ресурсов между потребителями будет допустимым.

       Суммарная стоимость всех перевозок, вычисленная по любому допустимому плану, будет равна

       Оптимальным планом перевозок X* будет называться тот из допустимых планов перевозок, который обеспечивает минимальную сумму затрат на перевозку всех ресурсов.

       Исходные данные транспортной задачи задаются вектором произведенных ресурсов A = {a_i}, вектором потребления ресурсов b_j, и матрицей стоимости C, где 1<i<n, 1<j<m. n – общее число производителей, m – общее число потребителей.

       Математическая модель транспортной задачи

При заданных ограничениях:

Метод наименьшего элемента

1) Сбалансировать задачу (убедиться, что задача сбалансирована).

2) Определить свободную клетку с наименьшей стоимостью перевозки. Если таких клеток несколько, то выбрать клетку с наибольшей потенциальной грузоперевозкой. Если и таких клеток несколько, то выбирается любая из этих клеток.

3) В выбранную клетку поставить максимально возможную грузоперевозку для потребителя от поставщика.

4) Проверить, остался ли нераспределенным груз у этого поставщика.

5) Если груз распределен не полностью, то применяем п.2 относительно строки этого поставщика. Продолжать до тех пор, пока груз этого поставщика будет полностью распределен.

Если груз поставщика распределен полностью, проверить, полностью ли удовлетворен объем потребителя.

Если потребитель полностью удовлетворен, то применить пункт 2 относительно оставшихся поставщиков и потребностей в таблице.

Если объем потребителя полностью не удовлетворен, тогда применяется пункт 2 относительно соответствующего столбца.

6) Проверить план на вырожденность. Количество базисных клеток должно быть равным r=m+n-1.

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

7) Проверить на оптимальность и по возможности дальше улучшить, перейдя к методу потенциалов.

       Метод потенциалов

1) Для всех базисных клеток создать систему уравнений вида .

Выбрать переменную U_i или V_j, которой соответствует наибольшее количество занятых клеток, приравнять её к нулю, решить систему уравнений относительно U_i и V_j и найти эти значения.

2) Для всех свободных клеток составить и проверить выполнение неравенств:

Условия оптимальности: если для всех свободных клеток выполняется это неравенство, то тогда найден оптимальный план.

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

3) Находим клетку, где сильнее всего не выполняется неравенство. Если таких клеток несколько, то выбирается любая. В эту клетку ставим W со знаком «+».

4) Построить контур перераспределения груза, начиная с выбранной клетки, исходя из следующих правил:

- В строке и столбце должно быть четное число W;

- Контур меняет направление только в базисных клетках;

- Коэффициент W меняет свой знак с «+» на «-» поочередно в углах контура.

5) После построения контура отметить, в каких базисных клетках коэффициент W стоит с отрицательным знаком. Из этих клеток найти клетку с наименьшим значением перевозки, коэффициент W будет равен перевозке в выбранной клетке.

6) Найти новый план, перераспределив найденное значение W по контуру с учетом знаков «+» и «-», прибавляя или уменьшая стоящую в клетке перевозку.

7) Проверить новый план в соответствии в п.2. если неравенства для свободных клеток выполняются, значит найденный план оптимален.

Если в математической модели целевая функция на максимум (Z_max), то задача решается методом максимального элемента. т.е. грузоперевозка (X_ij) распределяется при составлении опорного плана с учетом наибольшего значения C_ij аналогично метода наименьшего элемента. В методе потенциалов проверяется выполнение неравенства

Примеры решения транспортных задач

Пример 1. Студенческие отряды СО-1, СО-2 и СО-3 численностью 70, 99 и 80 человек принимают участие в сельскохозяйственных работах. Для уборки картофеля на полях П₁, П₂, П₃ и П₄ необходимо выделить соответственно 47, 59, 49 и 43 человека. Производительность труда студентов зависит от урожайности картофеля, от численности отряда и характеризуется для указанных отрядов и полей в центнерах на человека за рабочий день и представлена в матрице:

Требуется:

       Распределить студентов по полям так, чтобы за рабочий день было собрано максимально возможное количество картофеля;

       Определить, сколько центнеров картофеля будет убрано с четырех полей при оптимальном распределении студентов

Решение:

Проверяем задачу на сбалансированность.

Общее количество человек в студенческих отрядах на 51 больше требуемого общего количества человек для уборки картофеля. Задача является не сбалансированной.

Чтобы сбалансировать задачу, добавляем фиктивное картофельное поле, для уборки которого нужно выделить 51 человека. Производительность труда студентов на фиктивном поле принимаем равной НУЛЮ.

Составляем исходную таблицу

Обозначения:

П₅ – фиктивное картофельное поле;

С _ij – производительность труда студентов i -го СО на j – м картофельном поле;

X_ij – количество студентов, направляемое из i -го СО на j-ое картофельное поле;

U_i – условные оценки СО;

V_j – условные оценки картофельных полей

Составляем математическую модель прямой и двойственной задач.

Математическая модель прямой задачи:

Целевая функция (на максимум)

Система ограничений:

Математическая модель двойственной задачи.

Решаем задачу по методу максимального элемента.

Составляем опорный план

СО-1