Транспортная задача

4.Лекция.  Транспортная задача

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

       транспортной задачи.                  

Постановка задачи:

Однородный груз сосредоточен у m  поставщиков в объемах а₁, а₂, …, а_m.

Данный груз необходимо доставить n потребителям в объемах, b₁, b₂, … , b_n.

Известен С_ij (i= 1, 2, … , m; j=1, 2 ,…, n) – стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю.

Рекомендуемые материалы

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

Исходные данные транспортной задачи записываются в таблице вида:

Переменными (неизвестным) транспортной задачи являются x_ij (i=1,2,…,m; j=1,2,…,n) – объемы перевозок от каждого i-го поставщика j-му потребителю. Эти переменные могут быть записаны в виде матрицы перевозок.

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

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

Целевая функция задачи Z(X) выражает требование обеспечить минимум суммарных затрат на перевозку всех грузов. Вторая группа из уравнений ограничений записанных в общем виде, выражает требование, что запасы всех m, поставщиков вывозятся полностью, а также полностью должны удовлетворятся запросы всех n потребителей. Последнее неравенство является условием неотрицательности всех переменных.

В рассмотренной математической модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.

такая задача называется сбалансированной, а её модель закрытой. Если же это равенство не выполняется, то задача называется несбалансированной (с неправильным балансом), а её модель – открытой.

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

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

если целевая функция Z’ стремится к минимуму то в системе ограничении меняется знак:  экономический смысл перемененных двойственной задачи:

U_i – условная оценка i-го поставщика (условная плата поставщика перевозчику);

V_j – условная оценка j-го потребителя (условная плата потребителя перевозчику).

U_i, V_j – называются потенциалами.

Определения:

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

2.Клетка в плане перевозок называется базисной (закрытой), если в нее ставится перевозка.

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

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

5.Если в задаче указана не только стоимость перевозки, но и стоимость производства товара, тогда необходимо сложить эти стоимости с учетом перевозки товара от i-го поставщика j-му потребителю. Кроме того, математическая модель составляется с учетом этой суммарной стоимости.

  4. 2 Алгоритм решения транспортных задач.

1.Составить опорный план, т.е. начальное приближение.

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

3.Пользуясь методом наименьшего (наибольшего) элемента и методом потенциалов найти улучшение исходного опорного плана до тех пор, пока он не будет удовлетворять условию оптимальности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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 аналогично алгоритма метода наименьшего элемента. В методе потенциалов проверяется выполнение неравенства .

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

Пример №1

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

Сумма = 198

Сумма = 249

Требуется:

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

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

Решение:

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

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

Задача является не сбалансированной.

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

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

табл.1

Сумма = 249

Сумма = 249

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

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

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

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

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

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

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

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

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

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

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

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

Составляем опорный план (табл. 2)

Табл.2

Проверяем на вырожденность.

     Z= m+n-1=3+5-1=7

    Базисных клеток 7. План не вырожден.

Проверяем опорный план на оптимальность.

Задаем U₂ = 0 и определяем значения потенциалов.

Вычисляем оценки для всех незаполненных клеток (D_ij)

Опорное решение не является оптимальным, так как имеются отрицательные оценки.

Переходим к следующему плану.

Для клетки (1,5) с наименьшей оценкой (-5) строим цикл. Ставим в эту клетку коэффициент W со знаком «+» и применяя метод наибольшего элемента находим цикл, (табл. 2). Определяем из цикла W =11

Осуществляем сдвиг по циклу и строим следующий план (табл. 3)

.

Табл.3

Проверяем план на оптимальность методом максимального элемента, как в п.З.

Задаем U₂ = 0 и определяем значения потенциалов.

Вычисляем оценки для всех незаполненных клеток (D_ij)

Определяем из цикла W=7

 Осуществляем сдвиг по циклу и строим следующий план (табл. 4).

Табл. 4

Проверяем план на оптимальность методом максимального

элемента, как в п.З.

Задаем U₂ = 0 и определяем значения потенциалов.

Вычисляем оценки для всех незаполненных клеток (D_ij)

план табл. 4 оптимален.

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

Исходя из первой теоремы двойственности в условии нашей задачи Z_max=Z_min=1149 (Z=Z’) последний план оптимален

Ответ:

1.Чтобы за рабочий день было убрано максимально возможное количество картофеля, следует распределить студентов по полям следующим образом:

– Из СО-1 выделить 59 человек для уборки картофеля на втором поле П₂, а 11 человек останутся в СО;

– из СО-2 выделить 49 человек для уборки картофеля на П_З и 43 человека для уборки картофеля на П₄, а 7 человек останутся в СО;

– из СО-3 выделить 47 человек для уборки картофеля на П₁, а 33 человека оставить в СО.

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

Пример № 2

План перевозок:

Решение:

Проверяем на сбалансированность

Задача не сбалансированная. Введем фиктивного потребителя В₅ с потребностью в грузе, равной 200 ед. Стоимость перевозки для фиктивного потребителя определим равной нулю.

В качестве общей стоимости C_ij¹ будем брать сумму затрат на доставку единицы продукции C_ij из соответствующего пункта  и ее себестоимость C_i в этом пункте.

     C_ij¹=C_ij + C_i

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

 при условии что,

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

Экономический смысл переменных:

Z – целевая функция прямой задачи (суммарные затраты);

Z' – целевая функция двойственной задачи (суммарная потенциальная прибыль от перевозки груза);

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

X_ij – объем перевозок от i-го поставщика j-му потребителю;

U_i – условная плата перевозчику за вывоз единицы груза из i-го пункта отправления;

V_j – условная плата перевозчику за доставку единицы груза в j-ый пункт назначения.

Проверяем на вырожденность:

R=m+n-1=3+5-1=7

m= 3 – количество поставщиков;

n = 5 – количество потребителей.

Базисных клеток 7, план не вырожден.

Проверяем план на оптимальность, используя метод потенциалов. Для базисных клеток составляем систему уравнений U_i + V_j = С_ij находим значение потенциалов так как переменных на 1 больше, чем уравнений,

то переменной U₃ присваиваем значение 0 и решаем систему уравнений, получаем

Проверяем выполнение неравенства в свободных: клетках U_i + V_j ≤ С_ij

более всего не выполняется условие U_i + V_j ≤ С_ij, сюда ставим «+W» , строим контур перераспределения W и находим его значение:

Перераспределяем W=50 по контуру.

Составляем следующий план:

Так как переменных на i больше, чем уравнений, то переменной U₃ присваиваем значение 0 и решаем систему уравнений, получаем

проверяем выполнение неравенства в свободных клетках U_i + V_j ≤ С_ij,

– более всего не выполняется условие U_i + V_j ≤ С_ij, сюда ставим «+W», строим контур перераспределения W и находим его значение:  перераспределяем W=100 по контуру.

Составляем следующий план:

Для базисных клеток U_i + V_j = C_ij . Составляем для них систему уравнений. Принимаем U₃=0, так как в строке потенциала  U₃ наибольшее количество (три) базисных клеток, решаем систему уравнений и находим количественное значение U_i и V_j :

Проверяем выполнение неравенства U_i + V_j ≤ С_ij, в свободных клетках:

Неравенство U_i + V_j ≤ С_ij,в свободных клетках выполняется, построенной план является оптимальным.

Анализ решения.

Если Вам понравилась эта лекция, то понравится и эта - Тема 11 - Повреждения головы и позвоночника.

1.Оптимальный план перевозки продукции:

– от поставщика А₁ перевозится 250 ед. продукции потребителю В₁; 150 ед. продукции остается у поставщика;

– от поставщика А₂ перевозится 250 ед. продукции потребителю В₂; 50 ед продукции остается у поставщика;

– от поставщика А₃ перевозится 100 ед.продукции потребителю В₁, 150 ед, потребителю В₃, 250 ед. потребителю В₄ .

2.Суммарные затраты на изготовление и перевозку продукции:

 ден. ед.