Транспортная задача открытого типа

Если для транспортной задачи выполняется одно из условий

транспортная задача открытого типа - student2.ru или

транспортная задача открытого типа - student2.ru ,

то модель задачи называют открытой. Чтобы такая задача имела решение, необходимо ее привести к закрытому типу, т.е. чтобы выполнялось равенство транспортная задача открытого типа - student2.ru .

Это делают так: если транспортная задача открытого типа - student2.ru , то добавляют фиктивного потребителя со спросом транспортная задача открытого типа - student2.ru (в распределительной таблице появится дополнительный столбец), если транспортная задача открытого типа - student2.ru , то добавляют фиктивного поставщика с предложением транспортная задача открытого типа - student2.ru (в распределительной таблице появится дополнительная строка). В обоих случаях тарифы полагают равными нулю. Далее задача решается по такому же порядку, как было рассмотрено ранее.

Запишем алгоритм решения транспортной задачи:

1) Проверка типа модели ТЗ.

2) Построение начального опорного плана (любым способом).

3) Проверка плана на вырожденность.

4) Проверка плана на оптимальность методом потенциалов:

а) нахождение потенциалов из системы

транспортная задача открытого типа - student2.ru (для всех заполненных клеток);

б)проверка второго условия оптимальности

транспортная задача открытого типа - student2.ru (для всех пустых клеток).

5) Переход к нехудшему опорному плану (если это необходимо).

Пример. На складах имеются запасы однотипного товара в количестве а (35; 40; 40; 50), который необходимо доставить потребителям. Потребности потребителей задает вектор b (31; 52;17; 20). Матрица затрат на доставку единицы товара от i-го поставщика j-му потребителю:

с= транспортная задача открытого типа - student2.ru

Составить план перевозок с минимальными транспортными затратами.

Решение. Определим тип модели транспортной задачи. Суммарная мощность поставщиков: транспортная задача открытого типа - student2.ru 35+40+40+50=165 (единиц товара); Суммарный спрос потребителей: транспортная задача открытого типа - student2.ru 31+52+17+20=120 (единиц товара).

Т.к. транспортная задача открытого типа - student2.ru транспортная задача открытого типа - student2.ru , то имеем модель открытого типа.

Введем фиктивного потребителя, спрос которого равен

транспортная задача открытого типа - student2.ru транспортная задача открытого типа - student2.ru транспортная задача открытого типа - student2.ru 165 –120 =45 (единиц товара).

транспортная задача открытого типа - student2.ru Тарифы транспортная задача открытого типа - student2.ru 0. Т.о. получаем модель закрытого типа, m = 4 – число поставщиков, n = 5 – число потребителей. Ранг матрицы задачи транспортная задача открытого типа - student2.ru . Построим начальный опорный план методом минимального элемента (наименьшей стоимости).

транспортная задача открытого типа - student2.ru транспортная задача открытого типа - student2.ru транспортная задача открытого типа - student2.ru
         
     
         
     
         
       
         
   
транспортная задача открытого типа - student2.ru – 4 Таб.1

Число заполненных клеток распределительной таблицы 8 равно рангу матрицы задачи r = 8, следовательно, опорный план является невырожденным.

Транспортные затраты, соответствующие опорному плану:

транспортная задача открытого типа - student2.ru (ден. ед.).

Исследуем опорный план на оптимальность, используя метод потенциалов.

Дополним таблицу 1 столбцом и строкой потенциалов транспортная задача открытого типа - student2.ru и транспортная задача открытого типа - student2.ru . Систему потенциалов найдем, используя первое условие оптимальности: для заполненных поставками клеток транспортная задача открытого типа - student2.ru .

транспортная задача открытого типа - student2.ru ;

транспортная задача открытого типа - student2.ru ;

транспортная задача открытого типа - student2.ru ;

транспортная задача открытого типа - student2.ru ;

транспортная задача открытого типа - student2.ru ;

транспортная задача открытого типа - student2.ru ;

транспортная задача открытого типа - student2.ru ;

транспортная задача открытого типа - student2.ru ;

транспортная задача открытого типа - student2.ru .

Из записанной системы находим: транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru .

Проверим выполнение второго условия оптимальности. Для всех пустых клеток должно выполняться неравенство: транспортная задача открытого типа - student2.ru .

(1;1) транспортная задача открытого типа - student2.ru 0 + 1 – 5 = –4 транспортная задача открытого типа - student2.ru 0;

(1;2) транспортная задача открытого типа - student2.ru 0 + 2 – 4 = –2 транспортная задача открытого типа - student2.ru 0;

(1;5) транспортная задача открытого типа - student2.ru 0 – 4 – 0 = –4 транспортная задача открытого типа - student2.ru 0;

(2;3) транспортная задача открытого типа - student2.ru 1 + 3 – 5 = –1 транспортная задача открытого типа - student2.ru 0;

(2;4) транспортная задача открытого типа - student2.ru 1 + 1 – 8 = –6 транспортная задача открытого типа - student2.ru 0;

(2;5) транспортная задача открытого типа - student2.ru 1 – 4 – 0 = –4 транспортная задача открытого типа - student2.ru 0;

(3;1) транспортная задача открытого типа - student2.ru 4 + 1 – 6 = –1 транспортная задача открытого типа - student2.ru 0;

(3;2) транспортная задача открытого типа - student2.ru 4 + 2 – 8 = –2 транспортная задача открытого типа - student2.ru 0;

(3;3) транспортная задача открытого типа - student2.ru 4 + 3 – 7 = 0 транспортная задача открытого типа - student2.ru 0;

(3;4) транспортная задача открытого типа - student2.ru 4 + 1 – 10 = –5 транспортная задача открытого типа - student2.ru 0;

(4;1) транспортная задача открытого типа - student2.ru 4 + 1 – 5 = 0 транспортная задача открытого типа - student2.ru 0;

(4;4) транспортная задача открытого типа - student2.ru 4 + 1 – 2 = 3 транспортная задача открытого типа - student2.ru 0.



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

транспортная задача открытого типа - student2.ru Осуществим переход к нехудшему опорному плану. Наиболее перспективная для заполнения клетка (4;4), т.к. ей соответствует наибольшая положительная оценка

транспортная задача открытого типа - student2.ru 4 + 1 – 2 = 3.

Найдем цикл перераспределения груза для этой клетки.

Выбранной для заполнения клетке присваиваем знак «+», далее знаки чередуем. Среди вершин со знаком «–» выбираем наименьшую поставку.

транспортная задача открытого типа - student2.ru – объем перепоставки.

Перераспределим поставки по циклу, тем самым перейдем к новому опорному плану.

транспортная задача открытого типа - student2.ru транспортная задача открытого типа - student2.ru транспортная задача открытого типа - student2.ru
         
     
          –2
     
         
       
         
   
транспортная задача открытого типа - student2.ru –1 Таб.2

транспортная задача открытого типа - student2.ru Транспортные затраты, соответствующие опорному плану:

транспортная задача открытого типа - student2.ru (ден. ед.).

Исследуем опорный план на оптимальность. Найдем значения потенциалов, используя первое условие оптимальности. Для заполненных поставками клеток транспортная задача открытого типа - student2.ru .

транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru .

Проверим выполнение второго условия оптимальности. Для всех пустых клеток должно выполняться неравенство: транспортная задача открытого типа - student2.ru .

транспортная задача открытого типа - student2.ru Выпишем клетки, в которых условие нарушено:

(1;2) транспортная задача открытого типа - student2.ru 0 + 5 – 4 = 1 транспортная задача открытого типа - student2.ru 0.

транспортная задача открытого типа - student2.ru Осуществим переход к нехудшему опорному плану. Наиболее перспективная для заполнения клетка (1;2), т.к. ей соответствует положительная оценка транспортная задача открытого типа - student2.ru 1. Найдем цикл перераспределения груза для этой клетки.

транспортная задача открытого типа - student2.ru – объем перепоставки.

Число заполненных клеток распределительной таблицы 8 равно рангу матрицы задачи r = 8, следовательно, опорный план (таб. 3) является невырожденным.

транспортная задача открытого типа - student2.ru транспортная задача открытого типа - student2.ru транспортная задача открытого типа - student2.ru
         
     
          –1
     
         
       
         
   
транспортная задача открытого типа - student2.ru –2 Таб.3

Транспортные затраты, соответствующие опорному плану:

транспортная задача открытого типа - student2.ru (ден. ед.).

Исследуем опорный план на оптимальность.

Найдем значения потенциалов, используя первое условие оптимальности. Для заполненных поставками клеток транспортная задача открытого типа - student2.ru .

транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru , транспортная задача открытого типа - student2.ru .

Проверим выполнение второго условия оптимальности. Для всех пустых клеток должно выполняться неравенство: транспортная задача открытого типа - student2.ru .

Второе условие оптимальности выполняется для всех свободных клеток, следовательно план оптимален.

Наименьшие транспортные затраты транспортная задача открытого типа - student2.ru .

Ответ: транспортная задача открытого типа - student2.ru ; оптимальный план распределения поставок расположен в таб.3.

Задания для самостоятельной работы.

Составить план перевозок с минимальными транспортными затратами.

а) транспортная задача открытого типа - student2.ru   б) транспортная задача открытого типа - student2.ru

Наши рекомендации