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

1. Постановка задачи и стратегия решения.

Предположим, что в пункте А₁, А₂,..,А_n хранится однородный груз в количестве а₁, а₂,..,а_m единиц. Этот груз следует доставить в n заданных пунктов назначения В₁, В₂,..,В_n, причем в каждый из них требуется завезти b₁,b₂,..,b_m единиц этого груза.

Обозначим C_ij стоимость перевозки груза из пункта A_i в пункт B_j.

Транспортные задачи делятся на 2 группы :

1. Задачи, удовлетворяющие условию баланса (закрытая транспортная задача) :

_I = _j

Это означает, что общий запас груза на всех пунктах хранения равен суммарной потребности всех пунктов потребления (назначения).

2. Задачи с нарушенным балансом (открытая транспортная задача). Среди них выделяют 2 случая :

а) _I > _j

б) _I < _j

Рассмотрим формализацию закрытой транспортной задачи.

Обозначим x_ij количество груза, перевозимого из A_i в B_j. Тогда суммарная стоимость перевозок имеет вид :

ƒ(x) = c_ij x_ij

Ограничения представляются уравнениями вывоза и привоза груза

Первое уравнение системы означает, что из каждого пункта а_i вывозится весь груз А.

Второе уравнение системы означает, что удовлетворяются все потребности b_j.

Третье уравнение системы – груз либо вывозится, либо нет.

Решение x_ij этой системы называют планом перевозки.

2. Метода нахождения начального плана перевозок.

Клетки матрицы перевозок, где x_ij>0 называются базисными клетками. Остальные, где x_ij=0 называются свободными клетками. В матрице перевозок имеется (m+n-1) базисных клеток. Их число совпадает с числом независимых уравнений-ограничений.

(Важно! Это условие необходимо проверять при расчетах)

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

x_ij = min (*)

Значение x_ij=0 в свободной клетке не пишется явно, а вместо этого в ней ставится прочерк.

• Метод северо-западного угла

Вычисления осуществляются по формуле :

x_ij = min , начиная с элемента x₁₁ стоящего в северо-западном углу матрицы перевозок.

• Метод наименьшей (min) стоимости

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

По формуле (*) последовательно заполняются клетки с наименьшей стоимостью перевозок. Если имеются несколько клеток с наименьшей стоимостью, то из них выбирается любая.

• Метод потенциалов :

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

Введем :

1)Цикл – замкнутая ломанная с вершинами расположенными в оль строк и столбцов матрицы перевозок.

В каждой вершине встречаются два звена причем одно из них располагается по строке а другое по столбцу .

Число вершин цикла всегда четно.

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

2)Означенный цикл – это цикл в котором некоторой вершине преписан знак «+» , а затем при обходе цикла в каком-либо направлении знаки чередуються.

3) сдвиг по циклу на число θ (тета) >= 0 , при этом значении X_ij стоящие в положительной вершине цикла увеличивается на число θ , а стоящие в отрицательной вершине уменьшается на θ.

4) Потенциал – это число (α_i, i= 1,m)( β_j,j=1,m) каждому свободному пункту хранения a_i ставиться в соответствие α_i , а пункту потребления в соответствии β_j.

• Алгоритм:

1)Найти начальный план любым методом.

2)Для каждой базисной клетки составить уравнение α_i+β_j = c_ij

Т.к. эти уравнения образуют систему n+m -1 уравнении с m+n неизвестными.(Она имеет бесконечное множество решении)то для определенности следует предположить что α₁= 0 , следует все остальные потенциалы находятся однозначно.

3) Для каждой свободной клетки вычислить оценки по следующей формуле Δ_ij= c_ij- α_i-β_j

4) проанализировав относительные оценки

а)если все относительные оценки отрицательны т.е. Δ_ij = 0

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

б)если есть Δ_ij<0 найти среди них наименьшее отрицательную оценку и отметить ее каким-нибудь знаком.(пример X)

5)для свободной клетки с выбранной оценкой Δ_ij (X)построить означенный цикл , все его вершины кроме 1-ой (X) должны находиться в базисных клетках.

Свободная клетка берется со знаком (+).

6) выполнить сдвиг по построенному на шаге 5 циклу на величину θ равную наименьшей из чисел, стоящих в положительных вершинах , при этом числа стоящие в отрицательных вершинах уменьшить на θ, а в положительных увеличить на θ.

Если наименьшее значение θ достигается в нескольких отрицательных вершинах цикла то при сдвиге следует поставить базисный 0 во всех кроме одной.

!!!!!!

Иногда число базисных клеток сохраняется и будет равно n+m-1 что необходимо проверять при расчетах !!!!

Элементы матрицы не ходящие в цикл остаются без изменении .

Перейти к шагу 2.

• Замечание:

1)При решении задач может возникнуть ситуация в которой θ тогда при сдвиге свободная клетка становиться базисной(точка заменяется на базисный 0(ноль))

2) Значение суммарной стоимости перевозок при переходе от одной к другой матрице связаны следующим соотношением : f^k+1=f^k + θ* Δ_ij

Где k это номер итерации.

θ и Δ_ij находятся на шагах 3 и 6.

Пример решения транспортной задачи методом потенциалов

Математическая модель транспортной задачи: F = ∑∑c_ijx_ij, (1) при условиях: ∑x_ij = a_i, i = 1,2,…, m, (2) ∑x_ij = b_j, j = 1,2,…, n, (3) Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	4	5	Запасы
1	5	8	7	10	3	200
2	4	2	2	5	6	450
3	7	3	5	9	2	250
Потребности	100	125	325	250	100

Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 200 + 450 + 250 = 900 ∑b = 100 + 125 + 325 + 250 + 100 = 900 Занесем исходные данные в распределительную таблицу.

	1	2	3	4	5	Запасы
1	5	8	7	10	3	200
2	4	2	2	5	6	450
3	7	3	5	9	2	250
Потребности	100	125	325	250	100

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

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[100]	3	200
2	4	2[125]	2[325]	5	6	450
3	7	3	5	9[150]	2[100]	250
Потребности	100	125	325	250	100

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.  Строим новый план. Значение целевой функции для этого опорного плана равно:

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[100]	3	200
2	4	2[125]	2[325]	5	6	450
3	7	3	5	9[150]	2[100]	250
Потребности	100	125	325	250	100

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.  Строим новый план. Значение целевой функции для этого опорного плана равно:

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[100]	3	200
2	4	2[125]	2[325]	5	6	450
3	7	3	5	9[150]	2[100]	250
Потребности	100	125	325	250	100

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.  Строим новый план. Значение целевой функции для этого опорного плана равно:

	1	2	3	4	5	Запасы
1	5[100]	8	7	10	3[100]	200
2	4	2[125]	2[325]	5	6	450
3	7	3	5	9[250]	2	250
Потребности	100	125	325	250	100

2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.  Строим новый план. Значение целевой функции для этого опорного плана равно:

	1	2	3	4	5	Запасы
1	5	8	7	10[200]	3	200
2	4[100]	2	2[325]	5[25]	6	450
3	7	3[125]	5	9[25]	2[100]	250
Потребности	100	125	325	250	100

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: Этап II. Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=9	v2=4	v3=7	v4=10	v5=3
u1=0	5	8	7	10[200]	3
u2=-5	4[100]	2	2[325]	5[25]	6
u3=-1	7	3[125]	5	9[25]	2[100]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij Выбираем максимальную оценку свободной клетки (1;1): 5 Для этого в перспективную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	5[+]	8	7	10[200][-]	3	200
2	4[100][-]	2	2[325]	5[25][+]	6	450
3	7	3[125]	5	9[25]	2[100]	250
Потребности	100	125	325	250	100

Цикл приведен в таблице (1,1; 1,4; 2,4; 2,1; ). Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[100]	3	200
2	4	2	2[325]	5[125]	6	450
3	7	3[125]	5	9[25]	2[100]	250
Потребности	100	125	325	250	100

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=5	v2=4	v3=7	v4=10	v5=3
u1=0	5[100]	8	7	10[100]	3
u2=-5	4	2	2[325]	5[125]	6
u3=-1	7	3[125]	5	9[25]	2[100]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij Выбираем максимальную оценку свободной клетки (3;3): 5 Для этого в перспективную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[100]	3	200
2	4	2	2[325][-]	5[125][+]	6	450
3	7	3[125]	5[+]	9[25][-]	2[100]	250
Потребности	100	125	325	250	100

Цикл приведен в таблице (3,3; 3,4; 2,4; 2,3; ). Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 25. Прибавляем 25 к объемам грузов, стоящих в плюсовых клетках и вычитаем 25 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[100]	3	200
2	4	2	2[300]	5[150]	6	450
3	7	3[125]	5[25]	9	2[100]	250
Потребности	100	125	325	250	100

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=5	v2=5	v3=7	v4=10	v5=4
u1=0	5[100]	8	7	10[100]	3
u2=-5	4	2	2[300]	5[150]	6
u3=-2	7	3[125]	5[25]	9	2[100]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij Выбираем максимальную оценку свободной клетки (1;5): 3 Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[100][-]	3[+]	200
2	4	2	2[300][-]	5[150][+]	6	450
3	7	3[125]	5[25][+]	9	2[100][-]	250
Потребности	100	125	325	250	100

Цикл приведен в таблице (1,5; 1,4; 2,4; 2,3; 3,3; 3,5; ). Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[0]	3[100]	200
2	4	2	2[200]	5[250]	6	450
3	7	3[125]	5[125]	9	2	250
Потребности	100	125	325	250	100

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=5	v2=5	v3=7	v4=10	v5=3
u1=0	5[100]	8	7	10[0]	3[100]
u2=-5	4	2	2[200]	5[250]	6
u3=-2	7	3[125]	5[125]	9	2

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij. Минимальные затраты составят: F(x) = 5*100 + 3*100 + 2*200 + 5*250 + 3*125 + 5*125 = 3450 Все вычисления и комментарии к полученным результатам доступны в расширенном режиме. Также приведено решение двойственной транспортной задачи и анализ оптимального плана

Двойственная задача

Двойственные задачи

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

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

В зависимости от структуры модели исходной задачи различают симметричную, несимметричную и смешанную двойственные задачи.

Виды математических моделей двойственных задач

Симметричная двойственная задача

Рассмотрим неканоническую модель исходной задачи ЛП. Ищем максимум целевой функции

L(x) = c₁*x₁ + … + c_n*x_n → max

при следующих ограничениях

a₁₁*x₁ + … + a_1n*x_n ≤ b₁ | y₁

a₂₁*x₁ + … + a_2n*x_n ≤ b₂| y₂

…………………………………………

a_m1*x₁ + … + a_mn*x_n ≤ b_m| y_m

x_j ≥ 0 (j = 1, n)

Составим математическую модель следующим образом:

1. Каждое неравенство системы ограничений исходной задачи привести в соответствие переменным y_i.

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

3. Составить систему ограничений. Коэффициенты этой системы образуют транспонированием матрицы коэффициентов системы ограничений исходной задачи. При этом знаки неравенств меняются на противоположные. Свободные члены системы ограничений теперь являются коэффициентами целевой функции исходной задачи. Требование максимизации целевой функции заменить минимизацией и наоборот. Все переменные двойственной задачи неотрицательны.

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

S(y) = b₁*y₁ + … + b_m*y_m→ min

a₁₁*x₁ + … + a_1m*y_m≥c₁

a₂₁*x₁ + … + a_2m*y_m≥c₂

…………………………………………

a_n1*x₁ + … + a_nm*x_m≥c_n

y_i ≥ 0 (i = 1, m)

Несимметричные двойственные задачи

Рассмотрим математическую модель исходной задачи в канонической форме

L(x) = c₁*x₁ + … + c_n*x_n → max

a₁₁*x₁ + … + a_1n*x_n ≤ b₁ | y₁

a₂₁*x₁ + … + a_2n*x_n ≤ b₂ | y₂

…………………………………………

a_m1*x₁ + … + a_mn*x_n ≤ b_m| y_m

x_j ≥ 0 (j = 1, n)

Составим математическую модель двойственной задачи. Для ее составления пользуемся тем же правилом, что и для составления симметричной задачи, но с учетом следующих особенностей. Ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знаки “≥”, если максимум, то “≤”. Переменные y_iпроизвольные по знаку, то есть могут принимать как положительные, так и отрицательные значения.

S(y) = b₁*y₁ + … + b_m*y_m → min

a₁₁*x₁ + … + a_1m*y_m ≥ c₁

a₂₁*x₁ + … + a_2m*y_m ≥ c₂

…………………………………………

a_n1*x₁ + … + a_nm*x_m ≥ c_n

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

Смешанные двойственные задачи

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

Приведем основные теоремы, необходимые для решения двойственных задач:

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

L(x)_max = S(y)_min

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

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

Пример решения двойственной задачи

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

В общем виде задача нелинейного программирования состоит в определении максимального или минимального значения функции

при условии, что ее переменные удовлетворяют следующему условию

(2)

Здесь и – некоторые известные функции некоторых переменных, а - заданные числа.

В результате решения задачи будет определена точка ^T, координаты которой удовлетворяют соотношению (2) и такая, что для всякой другой точки , удовлетворяющей условию (2), выполнялось неравенство

, [ ]

Если являются линейными функциями, то задача 1.2 является задачей линейного программирования. Соотношение (2) образует систему ограничений и включает в себя условия неотрицательности переменных, если таковые условия имеются. Условия неотрицательности переменных могут быть заданы и непосредственно. В евклидовом пространстве система ограничений (2) определяет ОДР задачи. В отличие от задачи линейного программирования, она не всегда является выпуклой. Если определена ОДР, то нахождение решения задачи 1.2 сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня

Эта точка может быть как на границе, так и внутри области.

Процесс решения задачи в геометрической интерпретации включает этапы:

1. Находят ОДР задачи, определяемую соотношением (2) (если она пуста, то задача не имеет решения)

2. Строят гиперповерхность

3. Определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности функции (1) (сверху, снизу) на множестве допустимых решений.

4. Находят точку ОДР, через которую проходит гиперповерхность наивысшего (наинизшего) уровня и определяют в ней значение функции (1).

Пример решения задач НЛП графическим методом