Транспортная задача линейного программирования

1.

Нижегородский государственный технический университет им. Р.Е. Алексеева
Институт радиоэлектроники и информационных технологий
Кафедра «Электроника и сети ЭВМ»
К.т.н., доцент кафедры ЭСВМ
Калинина Н.А.
[email protected]

2.

2

3.

Транспортная задача линейного программирования (Т-задача) является
одной из самых распространенных задач линейного
программирования, для ее решения разработаны специальные методы,
основанные на симплекс-методе.
Имеется m пунктов А1,...,Аm производства однородного
продукта и n пунктов В1,...,Вn потребления этого продукта.
Для каждого пункта производства Аi задан объем
производства аi., i=1,…m, а для каждого пункта потребления
Вj - объем потребления bj, j=1,…n. Из каждого пункта
производства Аi в каждый пункт потребления Вj возможна
транспортировка продукта. Транспортные издержки по
транспортировке единицы продукта из Аi в Вj составляют Сij
единиц, i=1,…m, j=1,…n.
Требуется составить план перевозок, удовлетворяющий
следующим условиям:
транспортные издержки реализации плана перевозок минимальны;
спрос каждого потребителя удовлетворен;
из каждого пункта производства вывезен весь произведенный в
нем продукт.
3

4.

Обозначим xij - количество продукта, перевозимого из пункта Аi в
пункт Вj, i=1,…m, j=1,…n, тогда выполнение условий задачи
запишется так:
суммарные транспортные издержки:
4
условие полного удовлетворения спроса в пункте Вj:
условие полного вывоза продукта из Аi:
Таким образом, получаем математическую постановку Т-задачи:

5.

В Т-задаче переменные xij называются перевозками, их записывают
в виде матрицы X, которая называется планом перевозок.
Матрица С называется матрицей транспортных издержек.
Теорема. Т-задача имеет допустимые решения тогда и только
тогда, когда выполняется условие баланса – суммарный объем
производства равен суммарному объему потребления:
Т-задачи, у которых выполняется условие баланса, называются
замкнутыми.
Т-задачи с нарушением условия баланса называются открытыми.
При этом возможны два случая:
◦ Спрос превышает предложение.
◦ Производство превышает спрос.
5

6.

Пусть спрос превышает предложение, т.е. спрос в полном объеме не может быть удовлетворен:
Введем еще один фиктивный пункт производства Аm+1, положив в нем объем производства (тоже
фиктивный), равным объему неудовлетворенного спроса:
Введем также фиктивные перевозки xm+1,j.
Пусть за недопоставку единицы продукции в пункт Вj выплачивается штраф rj. Тогда за
стоимость фиктивной перевозки xm+1,j примем величину штрафа rj: Cm+1,j = rj, а перевозки из
фиктивного пункта составят:
В результате имеем целевую функцию:
Ограничения задачи:
, следовательно,
6
Ограничения вида
остались, но добавилось еще одно:
Следовательно можно записать:
При этом условие баланса выполняется:
В результате получена замкнутая Т – задача:

7.

при этом объемы перевозок составят:
За стоимость фиктивной перевозки Сi,n+1 возьмем величину ri, равную штрафу за не вывоз
единицы продукта из Аi. Тогда целевая функция:
К ограничениям
значит:
Кроме того,
тогда можно записать:
При этом условие баланса выполняется:
Тогда получена замкнутая Т-задача следующего вида:
7
Пусть производство превышает спрос, т.е. не весь продукт будет вывезен из пунктов А1,...,Аm:
Очевидно, что остаток продукта в пункте Аi, i=1,…m:
Считаем, что весь этот продукт будет, как бы вывезен в фиктивный пункт потребления Вn+1,
объем спроса в котором будет равен объему не вывезенных из пунктов А1,...,Аm товаров:
добавится еще одно:

8.

8
Таким образом, открытая Т-задача всегда может быть сведена к замкнутой.
При этом фиктивные перевозки определяет
либо объемы перепроизведенной продукции для каждого Аi,
либо объемы недопоставок для каждого Вj,

9.

9

10.

Рассмотрим следующую Т-задачу:
Запишем переменные xij в следующем порядке:
Поскольку Т-задача является задачей линейного программирования, то
матрицу левых частей ограничений А задачи можно записать так:
Строки матрицы А линейно
зависимы:
сумма первых m строк равна
сумме последних n строк.
Из этого следует, что ранг
матрицы А≤m+n–1.
Чтобы определить ранг
матрицы, нужно найти
максимальный порядок
отличных от нуля миноров
матрицы А.
10

11.

Составим минор порядка m+n–1, для этого выберем из матрицы А все
строки, кроме последней (всего получится m+n–1 строка), последние
столбцы из каждой группы (соответствующие переменным xin, i = 1,…,m) всего m столбцов, и остальные n-1 столбцов последней группы:
Этот минор отличен от нуля, порядок минора m+n–1, значит
rangА = (m+n–1).
Следовательно, в Т-задаче (m+n–1) базисная переменная, а остальные
mn–(m+n–1) переменные – свободные. Поэтому в любом базисном
решении отличны от нуля (m+n–1) переменная, а остальные равны нулю.
Допустимое базисное решение Т-задачи называют опорным планом.
11

12.

12
Опорный план, содержащий ровно (m+n–1) ненулевой элемент, называется
невырожденным.
Опорный план, содержащий меньше, чем (m+n–1) ненулевой элемент,
называется вырожденным.
Т-задача называется невырожденной, если любой ее опорный план
невырожденный.
Процесс решения состоит в:
нахождении начального опорного плана перевозок, являющегося
допустимым решением Т-задачи, но, как правило, не являющегося
оптимальным;
и в последующем улучшении этого плана до оптимального по
стоимости.

13.

13
Существуют разные методы нахождения начального опорного плана Тзадачи.
Наиболее распространенны
Метод северо-западного угла
Метод минимального элемента

14.

1-й шаг. Заполним клетку х11: полагаем х11 = min(а1, b1).
Корректируем:
а1 = а1 - х11, если получим а1 = 0, то исключаем первую строку;
b1 = b1 - х11, если получим b1 = 0, то исключаем первый столбец.
Пусть выполнено k шагов (k = 1,2,...).
(k +1)-й шаг. В оставшейся части таблицы выбираем самую верхнюю,
самую левую клетку (северо-западную клетку). Пусть эта клетка
соответствует хij. Заполняем ее: хij = min(аi, bj).
Корректируем:
аi = аi - хij, если в результате получим аi = 0, то исключаем из таблицы i-ю строку;
bj = b j - хij, если b j = 0, то исключаем j-й столбец.
14
Процедуру продолжаем до тех пор, пока не будет заполнена клетка,
соответствующая хmn.

15.

15

16.

16
В отличие от метода северо-западного угла метод минимального элемента
учитывает стоимость перевозок, и позволяет получить достаточно
экономичный план.
Формальное описание метода
k-й шаг (k≥1). В матрице стоимостей С выбираем клетку
минимальной стоимости.
Пусть эта клетка находится в i-й строке и j-м столбце. Заполняем
выбранную клетку в матрице перевозок X: xij=min(ai, bj).
Корректируем:
аi = аi - хij, если в результате получим аi = 0, то исключаем из
таблицы i-ю строку;
bj = b j - хij, если b j = 0, то исключаем j-й столбец.
Процедуру выполняем до полного исключения матрицы С.

17.

17

18.

18
И в методе минимального элемента, и в методе северо-западного угла
общее число шагов не более m+n–1.
Действительно, на каждом шаге исключается не менее одной строки или
одного столбца. Исключение составляет последний шаг, когда обязательно
исключается и последняя строка, и последний столбец.
Таким образом, любой из рассмотренных методов позволяет получить
допустимый опорный план Т-задачи с числом базисных переменных не
менее чем (m+n–1).
Теорема. Т-задача является вырожденной тогда и только тогда, когда
суммарный запас товара в нескольких, но не во всех пунктах производства
равен суммарной потребности нескольких, но не всех пунктов
потребления, т.е. существуют такие подмножества G∈{1,2,…,m};
H∈{1,2,…,n} для которых
.

19.

19

20.

20
Будем рассматривать невырожденные, замкнутые Т-задачи. Метод потенциалов
является модификацией симплекс-метода. Он позволяет, отправляясь от начального
опорного плана, получить оптимальное решение за конечное число итераций.
Для пунктов производства и потребления вводятся потенциалы в виде целых чисел.
Потенциалы пунктов А1,...,Аm обозначим α1... αm, а потенциалы В1...Вn обозначим
β1... βn. Числа α1... αm и β1... βn могут быть как положительными, так и
отрицательными.
Обозначим C ij i j и назовем эту сумму псевдостоимостью клетки (i,j).
Потенциалы выбираются так, чтобы C ij Cij .
Теорема 1. Для заданных потенциалов α1... αm и β1... βn cуммарная псевдостоимость
сохраняет одно и то же значение для любого допустимого планах хij, т.е. L const
Теорема 2. Если для всех базисных клеток плана {хij’} (т.е. для таких, что хij’>0)
можно подобрать такие значения потенциалов, что i j C ij Cij , а для всех
свободных клеток плана (т.е. для таких, что хij’ = 0) такие, что i j C ij Cij , то план
{хij’} является оптимальным.
Метод потенциалов позволяет за конечное число шагов построить план,
удовлетворяющий теореме 2.

21.

1.
2.
3.
Методом северо-западного угла или методом минимального элемента
построить начальный опорный план Т-задачи.
Определить из полученного плана потенциалы, исходя из условия для всех
хij > 0.
Так как в опорном плане Т - задачи (m+n–1) ненулевой элемент, то мы получим
систему из (m+n–1)-го уравнения с (m+n) неизвестными αi , βj. Следовательно,
при решении системы одному из неизвестных значение можно назначить
произвольно, например α1 = 0.
Для всех свободных клеток подсчитываем величину C . Если для всех
свободных клеток C C , то построенный план оптимален.
Выход из алгоритма.
Если хотя бы в одной из свободных клеток C C , то план не оптимален, и
выполняется следующая группа шагов.
ij
ij
ij
ij
21
ij
i
j

22.

4.
22
Выбирается любая свободная клетка, для которой C C .
Начиная от этой клетки, строим цикл пересчета – замкнутую ломаную линию,
проходящую через выбранную свободную клетку и некоторые базисные и в
каждой из этих клеток поворачивающуюся на 90 градусов.
Доказано, что для любой свободной клетки такой цикл существует и он
единственный.
ij
ij

23.

5.
23
Клетки, стоящие в цикле на нечетных местах, начиная от свободной, назовем
положительными и пометим знаком (+).
Клетки, стоящие в цикле на четных местах, назовем отрицательными и
пометим знаком (–).
Перевозки, соответствующие отрицательным клеткам, будем уменьшать, а
положительным - увеличивать.
В каждом столбце и в каждой строке таблицы X число положительных клеток
цикла будет равно числу отрицательных клеток. Поэтому, если в
положительных клетках увеличить перевозки на некоторую величину Q, а в
отрицательных уменьшить на эту же величину, суммы перевозок по строкам и
столбцам не изменятся, т.е. план остается допустимым.
При этом выбранная свободная клетка станет базисной хij = Q > 0. Для того
чтобы план остался опорным, необходимо, чтобы, по крайней мере, одна из
базисных клеток стала свободной. Для этого в качестве величины Q возьмем:
Q =min{хij}, где минимум выбирается из перевозок, соответствующих
отрицательным клеткам цикла. Таким образом, по всем положительным
клеткам цикла получим: хij’= хij+ Q, а по всем отрицательным: хij’= хij– Q.
Далее выполняем шаг 2.

24.

24

25.

25

26.

26
Одной из задач, приводящихся к Т-задаче, является задача о назначении или
задача выбора. Эта задача заключается в наиболее эффективном распределении
n работ между n исполнителями:
Пусть Сij – производительность j-го исполнителя на i-й работе.
Требуется так распределить работы между исполнителями, чтобы:
каждая работа выполнялась лишь одним исполнителем,
каждый исполнитель выполнял только одну работу,
суммарная производительность выполнения всех работ была
максимальна.

27.

Введем переменные хij следующим образом:
хij= 1, если на i - ю работу назначен j - й исполнитель и
хij= 0 в противном случае.
Суммарная производительность при выполнении всех работ:
Каждая работа выполняется каким-нибудь одним исполнителем:
Каждый исполнитель назначается на какую-то одну работу:
Таким образом, математическая постановка задачи о назначении (задачи
выбора) имеет следующий вид:
27

28.

28

29.

Метод предложен венгерским математиком Эгервари.
~
Перепишем постановку задачи выбора на минимум. Для этого положим d C :
ij
Эту задачу можно сформулировать так: из каждой строки и каждого столбца
~
~
матрицы D [ D ] выбрать ровно по одному элементу (всего n элементов), чтобы
их сумма была наименьшей.
ij
29
ij
Венгерский метод решения этой задачи основывается на следующих двух
утверждениях.

30.

Утверждение 1. Пусть сформулирована еще одна задача:
Оптимальное решение этой и предыдущей задач совпадут, если можно найти
~
такие числа αi , βj, что: d d .
Матрицы D и D~ , удовлетворяющие условию d d~ , называются
эквивалентными матрицами.
Нулевые элементы Z1,...,Zк матрицы D назовем независимыми нулями, если для
любого независимого нуля Zi = dij, i = 1,…,k строка и столбец, в которых он
стоит, не содержат ни одного независимого нуля, кроме Zi.
Утверждение 2. Пусть матрица D эквивалентная матрице предыдущей задачи,
содержит n независимых нулей:
, тогда выбор С1,j1, С2,,j2, …,
Сn,jn является оптимальным для задачи выбора
ij
30
ij
i
j
ij
ij
i
j

31.

31
Основная идея венгерского метода заключается в том, чтобы эквивалентными
преобразованиями привести матрицу D = –С задачи выбора к такому виду, при
котором в ней будет ровно n независимых нулей.
Тогда в силу утверждения 2 позиции этих нулей будут определять искомый
оптимальный выбор задачи.
Венгерский метод состоит из подготовительного этапа и не более, чем (n – 2)
итераций.
Каждая итерация заключается в проведении эквивалентных преобразований
матрицы, полученной на предыдущей итерации, и в выборе в ней
максимального числа независимых нулей.
Как только число независимых нулей станет равным n, задача выбора решена.

32.

32
Подготовительный этап: Для всех j = 1,…, n выполняем следующие действия: в
j -м столбце матрицы С отыскиваем максимальный элемент. Все элементы этого
столбца последовательно вычитаем из этого максимального элемента, и
результат записываем на то же место. В результате получаем матрицу, все
элементы которой, неотрицательны, и в каждом столбце имеется хотя бы один
нуль.
Для всех i = 1,…,n выполняем следующие действия: в i -й строке полученной
матрицы отыскиваем минимальный элемент и вычитаем его из всех элементов
i-й строки.
В результате получаем матрицу С0, все элементы которой неотрицательны, и в
каждой строке и в каждом столбце которой имеется, по крайней мере, один
ноль.
В первом столбце помечаем любой ноль звездочкой (*). Просматриваем второй
столбец. Если в нем найдется ноль, стоящий в строке без нуля со звездой (0*),
отмечаем его звездочкой. Аналогично просматриваем все оставшиеся столбцы
матрицы С0. Нули, отмеченные звездочкой, - это независимые нули.

33.

33
Итерация венгерского метода состоит из трех этапов. Допустим, что выполнена
k -я итерация и получена матрица Сk.
Перед началом (k + 1)-й итерации выделяем знаком + столбцы матрицы Сk,
содержащие 0*.
В дальнейшем элементы матрицы Сk, находящиеся в выделенных столбцах и
выделенных строках (появятся в процессе решения) будем называть
выделенными элементами.

34.

34
Цель этапа 1 - выяснить возможность увеличения числа независимых нулей на
один. Этап заключается в выполнении последовательности шагов. Один шаг
состоит в следующем:
Выбираем в матрице Сk невыделенный ноль. Если их нет, то переходим к этапу
3. Если невыделенный ноль нашелся, то возможны два случая:
строка, содержащая невыделенный ноль, не содержит 0*. В этом случае
невыделенный ноль помечаем штрихом (0’) и переходим к этапу 2.
строка, содержащая невыделенный ноль, содержит также 0*. В этом случае
невыделенный ноль помечаем штрихом (0’), помечаем строку, в которой он
стоит, знаком + (выделяем), уничтожаем знак + (обводим его кружком) над
столбцом, содержащим 0* в только что выделенной строке. Выполняем
следующий шаг этапа 1.
После выполнения конечного числа шагов этап 1 закончится либо случаем 1,
т.е. последует переход к этапу 2, либо все нули окажутся выделенными и
последует переход к этапу 3.

35.

Начиная с 0', который стоит в строке, не содержащей 0* (это тот 0', который был
помечен штрихом самым последним и этим закончился этап 1), строим цепочку
нулей матрицы Сk следующим образом:
35
от последнего 0' к 0* в этом же столбце, если такой 0* есть,
затем от этого 0* к 0' в той же строке, что и 0*(0' должен быть обязательно),
от найденного 0' к 0* по столбцу, если такой найдется
и так далее.
Такая цепочка определяется однозначно и всегда заканчивается на 0'.
Все звездочки над нулями цепочки уничтожаются, а штрихи, стоящие над
нулями, заменяются звездочками.
Уничтожаем все штрихи над элементами матрицы Сk и знаки (+), выделяющие
строки.
После этого число независимых нулей матрицы Сk увеличилось на один.
(k + 1)-я итерация закончена, и матрицу Сk обозначим Сk+1.
Если в матрице Сk+1 есть n независимых нулей, то задача выбора решена.
Выход из алгоритма.
В противном случае переходим к (k + 2) -й итерации.

36.

36
К этому этапу переходим тогда, когда в результате выполнения этапа 1, все нули
матрицы Сk оказались выделенными.
Среди невыделенных элементов матрицы Сk выбираем минимальный. Пусть он
имеет величину h > 0.
Прибавляем h ко всем элементам выделенных столбцов, вычитаем h из всех
элементов невыделенных строк. Получаем новую матрицу Сk(1), эквивалентную
Сk.
Матрица Сk(1) уже имеет невыделенные нули (на местах элементов, равных h).
Переносим в матрицу Сk(1) все обозначения из матрицы Сk. Возвращаемся с
матрицей Сk(1) к этапу 1.
Завершив этап 1 с матрицей Сk(1), перейдем либо к этапу 2, либо к этапу 3, на
котором построим еще одну эквивалентную матрицу Сk(2), с которой вернемся
на этап 1 и так далее, пока этап 1 не завершится случаем 1, после которого
следует переход на этап 2, где число независимых нулей увеличится на один и
закончится очередная итерация.

37.

37

38.

38

39.

39
Первоначально венгерский метод был применен к задаче выбора. Однако задача
выбора – частный случай Т-задачи, поэтому венгерский метод был применен и
для решения Т-задачи. Пусть требуется решить Т- задачу следующего вида:
Алгоритм решения Т-задачи, основанный на венгерском методе, состоит из
предварительного этапа и конечного числа итераций.

40.

40
В результате предварительного этапа строится матрица X0 = [х0ij], элементы
которой удовлетворяют условиям:
- невязка i-й строки матрицы X0,
– невязка j-го столбца,
– суммарная невязка матрицы X0.
Величина Δ0 характеризует близость матрицы X0 к оптимальному плану.
На каждой k -й итерации (k≥1) метода строится новый план Xk, которому
соответствует матрица Сk.
Пусть для нового плана получена невязка
.
Если Δk = 0, то Xk - оптимальный план.
Если Δk > 0, то строится новый план Xk +1, для которого Δk +1 < Δk.

41.

41
В каждом столбце матрицы С отыскивается минимальный элемент и
вычитается из всех элементов этого столбца. Получим матрицу С'.
В каждой строке матрицы С' отыскиваем минимальный элемент и вычитаем его
из каждого элемента этой строки. Получим матрицу C0 = [C0ij]. Все элементы
C0ij ≥ 0, причем в каждой строке и в каждом столбце матрицы С0 имеется хотя
бы один ноль.
Затем строим матрицу перевозок X = [х0ij], таким образом, чтобы
положительные элементы матрицы X0 располагались на местах нулевых
элементов матрицы С0. Матрицу X0 заполняем по столбцам, начиная с первого,
следующим образом:
Пусть в первом столбце матрицы С0 нулевыми элементами являются
следующие:
Полагаем:
.
Корректируем: аi1 = аi1 - х0i1,1, b1 = b1 - х0i1,1 и так далее продвигаемся по первому
столбцу, пока не станет равным нулю b1 пли пока не заполним все i1 позиций.
Аналогично заполняются остальные столбцы матрицы Х0.

42.

В матрице Х0 считаем невязки по строкам:
и невязки по столбцам:
.
Анализируем суммарную невязку: если
, то Х0 - оптимальное
решение Т-задачи.
Если Δ0 > 0, то переходим к первой итерации.
Каждая итерация состоит из трех этапов.
Допустим, что выполнено k итераций, и получены матрицы Ск, Хк,
причем Δk > 0.
Перед началом (k + 1)-й итерации отмечаем знаком + те столбцы матрицы Ск,
которым соответствуют нулевые невязки по столбцам матрицы Хк, т.е. 0
В дальнейшем, если выделены знаком + строки или столбцы матрицы, то
элементы этих строк и столбцов будем называть выделенными.
(k )
j
42

43.

43
Состоит из последовательного выполнения ряда шагов. Каждый шаг этапа 1
состоит в следующем:
Выбираем в матрице Ск невыделенный ноль. Если их нет, переходим к этапу 3.
Пусть такой ноль найден, например, Сij(к) = 0, i-й строке соответствует невязка
матрицы Хк: δi(к). Возможны два случая:
а) δi(к) > 0, тогда Сij(к) = 0' помечаем штрихом и переходим к этапу 2,
б) δi(к) = 0. В этом случае помечаем знаком + i -ю строку матрицы Ск, а
элемент Сij(к)=0' помечаем штрихом. Затем просматриваем в матрице
перевозок Хк элементы i -й строки и выделенных в Ск столбцов. Если среди
них существует ненулевой: μ такой что xiμ(к) > 0, то снимаем значок
выделения над μ-м столбцом (обводим кружком), а соответствующий
элемент матрицы Ск помечаем звездочкой: Ciμ(к) = 0*.
Выполняем следующий шаг этапа 1.
После выполнения конечного числа шагов этап 1 закончится либо случаем а),
т.е. последует переход на 2-й этап, либо все нули будут выделены, и мы
перейдем на 3-й этап.

44.

Заключается в построении цепочки из нулей матрицы Ск, отмеченных
штрихами и звездочками. К этапу 2 переходим с этапа 1, когда в матрице Ск
найден невыделенный ноль Cλ1,μ1(к) = 0, для которого невязка по строке δλi(к) > 0.
Цепочку начинаем строить с этого последнего выделенного нуля Cλ1,μ1(к) = 0'. В
столбце μ1 матрицы Ск находим ноль со звездочкой Cλ2,μ1(к) = 0* (если он есть).
В строке λ2 находим ноль со штрихом Cλ2,μ2(к) = 0' (такой ноль найдется
обязательно). В столбце μ2 снова находим Cλ3,μ2(к) = 0*, если он есть, и так далее.
Такое построение выполняется до тех пор, пока возможно. В результате
однозначно строится цепочка, не содержащая замкнутых циклов, и всегда
заканчивающаяся на нуле со штрихом 0’:
C’λ1,μ1, C*λ2,μ1, C’λ2,μ2, C*λ3,μ2,…, C’λp,μp
Находим величину Q(к) = min{xλ2,μ1(к), xλ3,μ2, …, xλp,μ(p-1), δλ1(к), }, здесь xλ2,μ1(к),
xλ3,μ2, …, xλp,μ(p-1), – перевозки, соответствующие четным элементам цепочки в
матрице Ск; δλ1(к) – невязка строки, в которой начинается цепочка, – невязка
столбца, в котором кончается цепочка.
(k )
p
(k )
p
44

45.

45
Строим новое приближение к решению - матрицу Xк+1. Ее элементы xij(к+1)
получаются следующим образом:
Для новой матрицы Xк+1 определяем значения невязок по строкам и столбцам, а
также суммарную невязку:
Если Δк+1 = 0, то Xк+1 – оптимальное решение. В противном случае переходим
на следующую (k + 2)-ю итерацию.

46.

46
Выполняется после этапа 1, когда все нули матрицы Ск оказались
выделенными. В результате этапа 3 путем эквивалентных преобразований
матрица Ск приводится к виду, содержащему еще хотя бы один невыделенный
ноль.
Среди невыделенных элементов матрицы Ск находим минимальный. Пусть его
значение h > 0. К выделенным столбцам прибавляем h, а из невыделенных строк
вычитаем h. Полученную матрицу обозначаем Ск(1) и возвращаемся на этап 1.

47.

47

48.

49