Постановка транспортной задачи (ТЗ)

Постановка транспортной задачи (ТЗ)

Пусть, X=(xij) – m* n матрица, где xij – объем перевозок от i-го поставщика к j-му потребителю. Тогда общие затраты на перевозку груза определяются функцией:

m n

z(X)= å å cijxij.

i=1 j=1

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

m n

z(X) = å å cij xij min, при условиях

i=1 j=1

 

m

å xij= bj, j=1,…., n,

i=1

n

å xij = ai, i= 1,….., m,

J= 1

 

xij ≥ 0

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

 

Открытая и закрытая модели.

Транспортная задача называется задачей с правильным балансом, а ее модель закрытой, если: m n

å ai = å bj,

i=1 j=1

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

Если: m n

å ai ≠ å bj

i=1 j=1

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

3. Методы построения опорного плана – метод минимального тарифа.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел ai и bj Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

 

Метод Фогеля.

 

Метод Фогеля состоит в вычислении для каждой строки транспортной таблицы разницы между двумя наименьшими тарифами. Аналогичное действие выполняют для каждого столбца этой таблицы. Наибольшая разница между двумя минимальными тарифами соответствует наиболее предпочтительной строке или столбцу (если есть несколько строк или столбцов с одинаковой разницей, то выбор между ними произволен). В пределах этой строки или столбца отыскивают ячейку с минимальным тарифом, куда пишут отгрузку. Строки поставщиков или столбцы потребителей, которые полностью исчерпали свои возможности по отгрузке или потребности которых в товаре были удовлетворены, вычеркиваются из таблицы, и вычисление повторяются до полного удовлетворения спроса и исчерпания отгрузок без учета вычеркнутых ячеек. Методом Фогеля обычно получается план, близкий к оптимальному, или сам оптимальный план.

 

Занятые и свободные клетки.

Клетки таблицы транспортной задачи, в которых находится отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные – незанятыми или свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку, т.е. стоящая в i-й строке и j-м столбце, имеет номер (i,j). Каждой клетке с номером (i,j) соответствует переменная, которой соответствует вектор-условие.

 

6. Вырожденные и невырожденные планы.

В общем случае опорный план транспортной задачи состоит из m+ n−1 занятой клетки (по числу базисных переменных). Такой план называется невырожденным. Нередко при решении транспортной задачи возникает вырожденный план с меньшим числом занятых клеток (когда какие-то из базисных переменных равны 0).

 

Метод потенциалов решения ТЗ.

Если опорный план Х=(хij) транспортной задачи является оптимальным, то существуют потенциалы поставщиков ui, i = 1, ….., m и потребителей vj, j=1,….,n, удовлетворяющие условиям:

ui+vj = cij при xij > 0 (для занятых клеток), (2.2)

Δij = ui + vj – cij ≤ 0 при xij = 0 (для свободных клеток) (2.3)

Условия (2.2) образуют систему с m+n неизвестными ui, vj и, в общем случае, m+n -1 уравнений. Так как число неизвестных системы на единицу больше числа уравнений, то одну из неизвестных можно задать произвольно, а остальные найти из системы.

 

8. Оценки опорного плана. Условия оптимальности опорного плана.

Числа Δij = ui + vj – cij называют оценками свободных клеток. Таким образом, согласно теореме: Если опорный план Х=(хij) транспортной задачи является оптимальным, то существуют потенциалы поставщиков ui, i = 1, ….., m и потребителей vj, j=1,….,n, удовлетворяющие условиям:

ui+vj = cij при xij > 0 (для занятых клеток), (2.2)

Δij = ui + vj – cij ≤ 0 при xij = 0 (для свободных клеток) (2.3)

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

Цикл. Перестановка по циклу.

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

В таблице выбираем свободную клетку с максимальной положительной оценкой и формируем цикл, одной из вершин которого является выбранная клетка, а остальные клетки занятые. Кроме того, сопоставим каждой вершине цикла знак и перевозку, при этом свободной клетке сопоставляем знак «+», а для остальных клеток знаки чередуются. Дальше делаем перестановку по циклу, а именно: из всех вершин, отмеченных минусом, вычтем минимум из всех перевозок, означенных этим знаком, т.е вычитаем Δ, а ко всем вершинам с «+» прибавим Δ. Таким образом с помощью цикла получаем новый опорный план.

 

Открытая модель ТЗ. Сведения открытой модели к закрытой.

Транспортная задача m*n называется задачей с неправильным балансом, а её модель

открытой, если: m n

å ai ≠ å bj

i=1 j=1

т.е суммарные запасы не равны суммарным потребностям.

Открытую задачу можно свести к закрытой:

1) Если: m n

åai >åbj, то вводят фиктивного потребителя Вn+1, с потребностью

i=1 j=1

 

m n

b n+1 = åai -å bj и нулевыми тарифами перевозок в столбце.

i=1 j=1

 

2) Если: m n

åai < åbj, то вводят фиктивного поставщика Аm+1, с запасом

i=1 j=1

 

n m

a m+1 = åbj -å ai и нулевыми тарифами перевозок в строке.

i=1 j=1

 

 

Фиктивные потребитель и поставщик.

1) Если: m n

åai >åbj, то вводят фиктивного потребителя Вn+1, с потребностью

i=1 j=1

 

m n

b n+1 = åai -å bj и нулевыми тарифами перевозок в столбце.

i=1 j=1

 

2) Если: m n

åai < åbj, то вводят фиктивного поставщика Аm+1, с запасом

i=1 j=1

 

n m

a m+1 = åbj -å ai и нулевыми тарифами перевозок в строке.

i=1 j=1

 

Дополнительные ограничения в транспортной задаче.

1) Если в закрытой транспортной задаче перевозки от поставщика Аi к потребителю Bj не могут быть осуществлены (блокировка), тодляопределения оптимального решения задач предполагают, что тариф перевозки единицы груза от Ai к Bj равен сколь угодно большому числу М.

2) Если дополнительным условием в транспортной задаче является обеспечение перевозки от поставщика Ai кпотребителю Bj в точности aij единиц груза, то в клетку AiBj записывают указанное число aij, а эту клетку считают свободной со сколь угодно большим тарифом М.

3) Если от поставщика Аi к потребителю Bj должно быть перевезено не менее aij единиц груза, что запасы пункта Ai и потребности пункта Bj полагают меньше фактических на aij единиц. После нахождения оптимального плана перевозку, стоящую в клетке AiBj, увеличиваются на aij единиц.

4) Если от поставщика Ai к потребителю Bj требуется перевезти не более aij единиц груза, то вводят дополнительного потребителя Bn+1 = Bij, которому записывают те же тарифы, что и для Bj, за исключением тарифа в i-й строке, который считают равными сколь угодно большому числу М. Потребности пункта Bj считают равными aij, а потребности Bij полагают равными bj-aij.

Постановка задачи многокритериальной оптимизации.

Задача вида

fi (x) -> max (min)

x ÎD

где, I>1, DÎ Rn – допустимое множество, а f i(x) – гладкие функции на D, называется задачей многокритериальной оптимизации.

Методы решения задач многокритериальной оптимизации – метод обобщенного критерия (метод свертки).

Метод перехода от нескольких критериев f1, f2, …fm к одному, задаваемому новой функцией: m

z = å (aj*fj)

j=1

называется сверткой, или методом обобщенного критерия. Числа aj называются весовыми коэффициентами. Чем больше aj, тем больший «вклад» вносит j-й

m

критерий в обобщенный критерий z. Иногда требуют, чтобы åaj = 1

j=1

Основные понятия в игровых моделях: стратегии, матрица выигрышей.

Стратегией игрока называется совокупность правил, опреде-ляющих поведение игрока на каждом ходе в зависимости от сложив-шейся ситуации.

Оптимальная стратегия игрока обеспечивает ему при много-кратном повторении игры максимально возможный выигрыш.

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

а11 а12 ….. а1n

а21 а22 ….. а2n

Матрица … ….. …. ….

аm1 аm2 …. amn

 

называется платежной матрицей или матрицей выйгрышей.

 

Доминируемые стратегии.

Если в платежной матрице Р все элементы i –й строки не меньше соответствующих элементов k-й строки, а aij ≥akj, j=1,n, а по крайней мере один строго больше, то

i-я строка называется доминирующей, а k-я строка доминируемой.

Постановка транспортной задачи (ТЗ)

Пусть, X=(xij) – m* n матрица, где xij – объем перевозок от i-го поставщика к j-му потребителю. Тогда общие затраты на перевозку груза определяются функцией:

m n

z(X)= å å cijxij.

i=1 j=1

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

m n

z(X) = å å cij xij min, при условиях

i=1 j=1

 

m

å xij= bj, j=1,…., n,

i=1

n

å xij = ai, i= 1,….., m,

J= 1

 

xij ≥ 0

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

 

Открытая и закрытая модели.

Транспортная задача называется задачей с правильным балансом, а ее модель закрытой, если: m n

å ai = å bj,

i=1 j=1

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

Если: m n

å ai ≠ å bj

i=1 j=1

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

3. Методы построения опорного плана – метод минимального тарифа.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел ai и bj Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

 

Метод Фогеля.

 

Метод Фогеля состоит в вычислении для каждой строки транспортной таблицы разницы между двумя наименьшими тарифами. Аналогичное действие выполняют для каждого столбца этой таблицы. Наибольшая разница между двумя минимальными тарифами соответствует наиболее предпочтительной строке или столбцу (если есть несколько строк или столбцов с одинаковой разницей, то выбор между ними произволен). В пределах этой строки или столбца отыскивают ячейку с минимальным тарифом, куда пишут отгрузку. Строки поставщиков или столбцы потребителей, которые полностью исчерпали свои возможности по отгрузке или потребности которых в товаре были удовлетворены, вычеркиваются из таблицы, и вычисление повторяются до полного удовлетворения спроса и исчерпания отгрузок без учета вычеркнутых ячеек. Методом Фогеля обычно получается план, близкий к оптимальному, или сам оптимальный план.

 

Занятые и свободные клетки.

Клетки таблицы транспортной задачи, в которых находится отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные – незанятыми или свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку, т.е. стоящая в i-й строке и j-м столбце, имеет номер (i,j). Каждой клетке с номером (i,j) соответствует переменная, которой соответствует вектор-условие.

 

6. Вырожденные и невырожденные планы.

В общем случае опорный план транспортной задачи состоит из m+ n−1 занятой клетки (по числу базисных переменных). Такой план называется невырожденным. Нередко при решении транспортной задачи возникает вырожденный план с меньшим числом занятых клеток (когда какие-то из базисных переменных равны 0).