Решение задачи методом потенциалов

1. Введем вспомогательные величины, называемые потенциалами:

_- – потенциалы поставщиков (строк),

-β_j– потенциалы потребителей (столбцов).

Проставим буквенные обозначения для потенциалов: для поставщиков

2. Потенциалы вычисляются из условия:

+ β_j = C _ij – для заполненных клеток, где С _ij – тарифы этих клеток. В нашей задаче:

Составляется для заполненных клеток!

3. Значение одного из потенциалов выбираем произвольно. Например, ₁ = 0. Тогда значения остальных потенциалов легко найдутся из указанной системы:

β₁=1; β₃ = 3; = 2; = 0; β₃ = -1; β₄ = 1.

Эти значения потенциалов проставим в таблице 4.6 сверху и слева.

4. Проверим план на оптимальность. Оптимальный план должен удовлетворять условию:

+ β_j C_ij – для пустых клеток.

Проверяем все пустые клетки:

клетка (1;2) 0 + (-1) < 2;

Составляется для пустых клеток!

клетка (1:4) 0 + 1 < 4;

клетка (2;1) 2 + 1 > 2;

клетка (2;4) 2 + 1 = 3;

клетка (3;1) 0 + 1 < 8;

клетка (3;2) 0 + (-1) < 6;

Как показывают вычисления, для клетки (2;1) условие оптималь­ности не выполняется, следовательно план не оптимален и его нужно улучшать. Для этого загружаем «неоптимальную» клетку (2;1) (или одну из них, если их несколько) за счет перераспределения груза в других клетках.

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

Циклом называется многоугольник, у которого:

1) все стороны лежат в строках и столбцах;

2) все углы прямые;

3) все вершины лежат в заполненных клетках, а одна вершина – в свободной неоптимальной клетке;

4) в цикл включены лишь те клетки, где находятся его вершины.

Циклы пересчета могут иметь следующую форму (рис. 2):

 

 

1) 2) 3)

 

Рисунок 2

 

Число их вершин обязательно четно. «Неоптимальная» клетка может находиться в любой вершине цикла. Для определенности «неоптимальная» клетка каждого цикла отмечается вопросом или знаком «+».

По циклу будем перемещать поставку. Для нахождения величины этой поставки сначала проставим знаки в вершинах цикла: в «неоптимальную» клетку ставим знак «+»(плюс), а далее, совершая обход по циклу, чередуем знаки «-» (минус) и «+»(плюс) в его вершинах. Из клеток, отмеченных знаком «-» (минус), выбираем наименьшую поставку.

В нашей задаче цикл, составленный к клетке (2;1),. В него входят клетки (2;1), (1;1). (1;3). (2;3). Наименьшая из поставок, отмеченных знаком «-», равна 10: min {100;10} = 10. Перемещаем ее по циклу. При этом прибавляем по 10 единиц к поставкам, находящимся в вершинах со знаком «+», вы­читаем по 10 единиц из поставок, находящихся в вершинах со знаком «-». В результате всех этих перемещений приходим к новому плану

 

Таблица 4.

Базы	Потребители	Запасы
β1 = 1 В1	β2 = 0 В2	β3 = 3 В3	β4 = 1 В4
1 =0; А1	90 1	2	30 3	4
2=1; А2	10 2	70 1	5	3
3=0; А3	8	6	20 3	20 1
Потребности

 

Этот план является опорным, т. к. удовлетворяет всем признакам опорного плана:

1) соблюдены балансы по всем строкам и столбцам;

2) число заполненных клеток равно: m + n -1 = 6;

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

Стоимость перевозок, соответствующая полученному опорному плану, уменьшается:

Z = 1·90 + 3·30 + 2·10 + 1·70 + 3·20 + 1·20 = 250 (тыс. руб.), т. е. новый опорный план лучше (дешевле) предыдущего.

Выясним, оптимален ли полученный план, с помощью метода потен­циалов повторяя весь ход рассуждений, начиная с пункта 1.

Вычисляем новые потенциалы поставщиков и потребителей с по­мощью системы уравнений,

 

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

x₁₁= 90; x₁₃ = 30; x₂₁ = 10; x₂₂ = 70; x₃₃ = 20; x₃₄ = 20.

Расходы по его осуществлению минимальны и составляют Z_min = 350 тыс. руб.

Замечание. Количество таблиц при решении транспортной задачи может оказаться любым. Это зависит от того, насколько первый опорный план окажется близким к оптимальному. Может случиться, что первая же таблица будет соответствовать оптимальному плану. Это устанавливается методом потенциалов.

Транспортная задача всегда имеет оптимальное решение (один или несколько опорных оптимальных планов).

Задание к практическому занятию:

Базовый уровень:

Задание 1

В транспортной задаче, где запасы поставщиков описываются вектором А(50;70), потребности – вектором В (30;40;50), а стоимость перевозки единицы груза от поставщиков потребителям задана матрицей

Д = , найти общую стоимость допустимого плана перевозок,

полученного по методусеверо-западного угла.

Ответ: 250

Задание 2

В транспортной задаче, где запасы поставщиков описываются вектором А(50;70), потребности – вектором В (35;50;35), а стоимость перевозки единицы груза от поставщиков потребителям задана матрицей

Д = , найти общую стоимость допустимогоплана перевозок,

полученного по методу северо-западного угла.

Ответ: 1)170

Задание 3

В транспортной задаче, где запасы поставщиков описываются вектором А(60;60), потребности – вектором В (35;50;35), а стоимость перевозки единицы груза от поставщиков потребителям задана матрицей

стоимость оптимального плана перевозок равна:

Д = , найти общую стоимость оптимального плана перевозок,

Ответ: 1) 120

 

Повышенный уровень:

Задание 4. Решить методом потенциалов транспортные задачи (табл. 5).

Таблица5. Варианты задания

Вариант	Задача	Вариант	Задача
	ai \ bj		ai \ bj
	ai \ bj		ai \ bj
	ai \ bj		ai \ bj
	ai \ bj		ai \ bj
	ai \ bj		ai \ bj

 

Задание 5. Решить методом потенциалов транспортные задачи с ограничениями на пропускную способность (табл. 6).

 

Таблица 6. Варианты задания

Вариант	Задача	Вариант	Задача
	x21£500, x44³500 ai \ bj		x21£500, x44³1000 ai \ bj
	x21£25, x32³20 ai \ bj		x42£50, x24³50 ai \ bj
	x23£30, x32³30 ai \ bj		x44£100, x23³50 ai \ bj
	x33£100, x42³100 ai \ bj		x43£50, x21³100 ai \ bj
	x32£100, x43³100 ai \ bj		x11£20, x33³30 ai \ bj

 

 

Вопросы для самостоятельной работы

Базовый уровень:

 

1. Чем отличается постановка транспортных задач от других ЗЛП?

2. Перечислите и охарактеризуйте основные методы построения опорного плана.

3. В чем суть метода потенциалов для решения транспортных задач?

 

Повышенный уровень:

4. Дайте экономическую интерпретацию метода потенциалов.

5. Можно ли решать транспортные задачи графическим или симплексным методами?

 

 

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

Базовый уровень:

Имеются три пункта поставки однородного груза и пять пунктов потребления этого груза. На пунктах находится груз соответственно в количестве тонн. В пункты требуется доставить соответственно тонн груза. Затраты на перевозку 1 тонны груза между пунктами поставки и потребления приведены в матрице Д (в рублях).

,

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

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

Поставить задачу и решить методом потенциалов.

3.1. .

3.2. .

 

 

3.3. .

3.4. .

3.5. .

3.6. .

3.7. .

3.8. .

3.9. .

3.10. .

3.11. .

3.12. .

3.13. .

3.14. .

3.15. .

3.16. .

3.17. .

3.18. .

3.19. .

3.20. .

3.21. .

3.22. .

3.23. .

3.24. .

3.25. .

3.26. .

3.27. .

3.28. .

3.29.. .

3.30.

.